glaebhoerl @glaebhoerl@schelling.pt

Just realized in the shower that Euclid's algorithm is kind of trivial if you think about it a) geometrically and b) recursively. Geometrically, the GCD problem becomes "given a rectangle with sides of integer length, what is the largest square with integer side that tiles the given rectangle?". Recursively, if you tile the rectangle with squares with sides equal to the rectangle's smaller side, the remaining rectangle either vanishes, in which case we are done, or the solution for the remaining rectangle is also the solution for the original rectangle (easy to verify). We know the algorithm terminates because the square with side 1 tiles any rectangle. This recursive algorithm is pretty straightforward to transform into the familiar iterative algorithm.

The PR is up for how we're thinking about complete-but-not-sound type systems...
https://github.com/Roblox/luau/pull/1037

I wish I had more time to be more seriously interested in what I call "hyperconnected" data structures. Those are data structures which are at least tree-like, but which are also wired up by extra pointer threads supporting rapid access patterns. Lists where you know the last cell are an example, as are doubly-linked lists. Gnarly invariants badly maintained, and sustainable only when managing uniqueness of ownership.

In my mind, there are red pointers, which characterise tree-like structures and obey a strictly linear discipline, but there are also black pointers, which give you short cuts into lumps of data for which you hold the red pointers. The logic that's needed should tell you, given which red pointers you own, which black pointers you also have.

Hello you fine Internet Folks,

Today's article is some more Hot Chips coverage but with a bit of a curve ball tossed in there; we have covered Zen 4's uarch before so today we are looking at where Zen 4's bottlenecks in 2 games are.

Hope y'all enjoy!

https://chipsandcheese.com/2023/09/06/hot-chips-2023-characterizing-gaming-workloads-on-zen-4/

Weird how characters in science fiction often go on about "the species". I care about "the species" about as much as I care about the charge on an electron or the melting point of caesium. It's *people* I care about - or not, as the case may be.

Breaking news: they finally found the artist who did the cover for _A Wrinkle In Time_; his name was Richard Bober. https://www.wbur.org/endlessthread/2023/09/01/artist-known-wrinkle

I still don't understand why free variables are called "free" variables. No variable is ever really free, no? It is just bound in a non-local context, and different decisions can be made at the language level about what that means. It doesn't have any meaning to consider a term outside of its context.

Mercator Projection

New blog post! This one, on (software) systems operating at or beyond their capacity, what goes wrong, and how to degrade gracefully.

https://blog.nelhage.com/post/systems-at-capacity/

Ihave just realized a very annoying thing: the "Austr-" in "Austria" means East, from German Öster. The "Austr-" in "Australia", on the other hand, means South, from Latin Australis.

Thank you, have a nice day.

I've been diving into runtime systems and low-level stuff recently. Here's a "blogpost" about garbage collection which has zero cost when we don't run garbage collection.

https://gist.github.com/AndrasKovacs/fc9e20b0976b7e236b5899fde8f5c95d

I feel that there's a bit of a connection to type theory here. Let me summarize shortly. When we compile down to C and want to have copying GC, one problem is that C believes that every function call invalidates the whole memory (because GC can write memory). LLVM fares slightly better; it believes that every function call invalidates every heap pointer in scope and actually wants us to mark all of these invalidations in the IR.

In an IR designed with copying GC in mind, we would just want everything to be invariant under relocation, and then we don't even have to care about relocation or represent it in the IR at all. We just have to make sure that relocation is able to relocate GC roots absolutely everywhere (including registers).

The "relocation hell" in C and LLVM is similar to "hell" in type theory, like setoid hell or groupoid hell. We want to work in a language where everything is implicitly well-behaved, not in a language where good behavior has to be manually enforced at every step.

Let me tell you an important thing about nasty sectarian wars. You have to let everyone who was engaged in that nasty sectarian war say "Stop! I don't want to be in a nasty sectarian war any more.". You really have to let them do that. You might feel like saying "You hypocrite! You used to be engaged in the nasty sectarian war!", but you shouldn't, because what you're saying is "Start the war again! It's the only way to be consistent!".

Don't know who needs to hear this, but the recent explainer about "Web Environment Integrity":

- will not ship in current form (I'll block it; and yes, I can do that)
- was not an "official" Google propsoal. Individuals with @google.com (and @microsoft.com, etc.) addrs do dumb stuff all the time (ask me how I know!)
- is very much worth worrying about as a direction of travel, but not without context