Posts in Haskell (20 found)

Data-directed programming in Haskell (SICP 2.4.3)

I have a copy of SICP, or as it is also known, The Wizard Book . This book is widely praised, but I can’t take the time to work my way through all of it. Instead, I’m going to occasionally jump into the parts of it that look interesting. Last week, we looked at tagged data in Haskell. The authors of SICP weren’t convinced that’s the best approach, so they move on to data-directed programming. We’ll do the same. Complex numbers can be stored in their rectangular form, with a real and an imaginary part. They can also be stored in polar form, where there’s a magnitude and an angle. Whichever way a complex number is stored, we would like to be able to query it for all of these four quantities: (Continue reading the full article on the web.) The real coordinate in the rectangular form of the complex number. The imaginary coordinate in the rectangular form. The magnitude in the polar form. The angle in the polar form.

0 views

Tagged data in Haskell (SICP 2.4.2)

I have a copy of SICP, or as it is also known, The Wizard Book . This book is widely praised, but I can’t take the time to work my way through all of it. However, sometimes I jump into parts of it that look interesting. Today, we’ll see how to support multiple representations of data through tagging. This article is written in Haskell throughout, but at the start it will look a lot like the Lisp code in SICP. I have intentionally tried to recreate the SICP solution as closely as possible, including dynamic typing and all. See the appendix if you’re curious how it works. Complex numbers can be stored in their rectangular form, where there’s a real and an imaginary part. They can also be stored in polar form, where there’s a magnitude and an angle. The authors ask us to imagine that two people have been working on a library for mathematics, but ended up choosing different ways to store complex numbers. How can they write their code so that they don’t have to agree on one way to store the data? (Continue reading the full article on the web.)

0 views
Abhinav Sarkar 4 weeks ago

Nix for Haskell: Static Builds

In the previous post , we learned how to get started with managing and building a Haskell project with Nix . In this post, we learn how to easily create statically-linked executables for Haskell projects with Nix. This post was originally published on abhinavsarkar.net . This post is a part of the series: Nix for Haskell . I recommend going through the previous post , because we are going to start off from where we left last time (ignoring the bonus sections). This is how our project’s directory tree looks at this point: is the default generated main file that prints “Hello, Haskell!”. is the default generated Cabal file. are generated by Niv to pin Nixpkgs to a particular revision. provides the nixpkgs that we use for building tools and dependencies. and build the package and manage the Nix shell respectively. We are not going to touch any of these files in this post. Let’s get started. A static build is an executable that is statically-linked against all the libraries it depends on. This is in contrast to a dynamically-linked executable, which contains references to the libraries it depends on, and those libraries are loaded and linked when the executable runs. While dynamic linking has its benefits , the main advantage of static linking is that the executable can be shipped by itself, without needing to ship or install dependency libraries. This makes it quite attractive for deploying backend services. You download and deploy that one binary executable file and you are done! No need to care about installing and maintaining its dependencies. Many compilers support static builds— Go and Rust being two. Haskell compiler GHC also supports it, but not out-of-the-box. To statically link a Haskell executable, we need to configure GHC itself, and then configure the executable build as well. We also need to configure GHC to link with musl libc. That’s where Nix helps us by smoothing out the process 1 . As mentioned, first we need a GHC configured to do static builds. We create a nixpkgs derivation, separate from , that contains the custom configured GHC. Let’s go over it piece-by-piece. First, we take the and parameters, letting us build the package for different architectures ( X86-64 and AArch64 ), and for different GHC versions. We default the to the default GHC in nixpkgs. The derivation is same as , except we add some overlays. The first overlay adds the custom configured GHC for static builds. We enable certain configurations for that purpose: The related lines set the custom GHC as the compiler for Haskell-based tools used in Nix 2 . The second overlay makes —the tool used to convert files into Nix derivations—use the custom GHC. The third overlay disables documentation generation, testing, and profiling of all Haskell libraries built with the custom GHC. We do this to save the build time, assuming that static builds are for release only, and the docs, tests, and profiling are done using a normal GHC. Building this custom GHC may take anywhere from several minutes to several hours depending on the build machine configuration 3 4 . But this is a one-time price to pay, as long as we keep the GHC build around. Next, we configure our package to be built as a statically-linked executable. The file is equivalent of the file from the previous post, but builds statically-linked exes. Let’s go over the file in parts. also takes and as parameters, and passes them to to create the nixpkgs with the custom GHC as described above. This give us , from which we get the version. is same nixpkgs, except every executable in it links to musl libc. We capture this as , and use it to build our Haskell package. When linking the executable, we need to link it against static version of all the dependency libraries it depends on. That’s what file provides us. We’ll look at it in the next section, but for now, we see that it gives us the , , and libraries 5 . Finally, we get to the package configuration. It starts the same as , using to connect the Haskell project to Nix, but then, we provide a list of custom configurations. We disable Haddock docs, hyperlinked source docs, coverage tests, profiling, and shared library build. We enable static executable build and dead code elimination. Then we configure cabal to run builds with multithreading, and add to its list of build tools. Then, we add many configuration flags: Finally, the last function in the pipeline uses UPX to compress the output executable. This generally results in a large reduction in the binary size 7 . Now we can actually build the statically-linked exe: The first and second line above build the exe for the X86-64 and AArch64 architectures with the default GHC version. The third line specifies a different GHC version to build with. Here is the cleaned-up output log for the first command: The output log mentions: patchelf: cannot find section ‘.dynamic’. The input file is most likely statically linked We can also verify for ourselves: There is one last thing to take care of. Dynamically-linked Haskell builds contain references to their dependency libraries and GHC that was used to build it. If you use or install a dynamically-linked executable, it creates Nix GC roots for the libraries and GHC, preventing them from being garbage-collected by Nix. But statically-linked builds have no references to anything, as intended. So we need to create GC roots by ourselves to the libraries and the GHC toolchain. This is even more important because building the custom GHC may be an extremely time-consuming affair. First, we list all dependencies in a separate file: This file lists the dependency libraries and the GHC toolchain. Notice how we override each library’s config to make it statically-linkable. I’ve included some additional libraries here ( and ) that are generally used by Haskell projects, but we don’t use them in this project. You may have to add more of such libraries depending on your project’s dependencies. We already saw how we use this file in . Now, we use it to create Nix GC roots: simply gathers all dependencies from and creates a directory with symlinks to them. This brings us to the finale. We create a bash script that builds the statically-linked executable, and creates Nix GC roots for all dependencies and the toolchain: The root is created at for X86-64 architecture, for example. You can use to explore it. This concludes our short tutorial on how to build statically-linked executables for Haskell projects with Nix. One more thing static builds are great for: wrapping them into Docker images. Since they are much smaller than dynamically-linked executables and their dependencies combined, they are better to package as Docker images. Here’s how we do it: This image also shows how to package extra Nix packages in images, setting up a non-root user to run the executable, and setting up user-owned directories to expose as volumes. We can build the image by running: Then we can load and run the image on Docker like so: This post shows how to configure GHC and Haskell projects to build statically-linked executables that are fully portable and independent. If your Haskell project has any complex requirements, such as custom dependency versions, patched dependencies, custom non-Haskell dependencies etc., this setup may not scale. In such case you can either grow this setup by learning Nix in more depth with the help of the official Haskell with Nix docs and this great tutorial , or switch to using a framework like haskell.nix or haskell-flake . For dealing with complex static builds, static-haskell-nix project may be of help. If you have any questions or comments, please leave a comment below. If you liked this post, please share it. Thanks for reading! I have tested this setup for GHC 9.10+ and X86-64 and AArch64 architectures only. ↩︎ Without this config, Nix will build a separate GHC for building Haskell-based tools used in Nix. ↩︎ You may need a remote Nix Linux builder to build GHC and your package if you are not on Linux or not on the right architecture. You may set up a remote builder or Linux builder on macOS . ↩︎ Building GHC is memory intensive. You may require few GBs of RAM. ↩︎ Some of your project’s dependency libraries may link to GMP directly. In such cases, the libraries provide Cabal flags to remove GMP dependency. If you don’t want GMP linked to your executable, you’ll need to override the Nix derivation for such libraries to pass those Cabal flags. ↩︎ I learned about using these flags from the post “Linking Smaller Haskell Binaries” . It mentions few mores tricks that may be useful to you. ↩︎ Note that we get the tools and from , the original nixpkgs, not the musl one. We don’t need musl version of these tools for them to work, and doing that would simply cause our builds to take longer. ↩︎ This post is a part of the series: Nix for Haskell . Thanks for reading this post via feed. Feeds are great, and you're great for using them. ♥ This post was originally published on abhinavsarkar.net . Read more of my posts and notes . Getting Started Static Builds 👈 Static Builds Enabling Static Builds in GHC Configuring the Application Rooting Static Build Dependencies Bonus: Building a Docker Image I have tested this setup for GHC 9.10+ and X86-64 and AArch64 architectures only. ↩︎ Without this config, Nix will build a separate GHC for building Haskell-based tools used in Nix. ↩︎ You may need a remote Nix Linux builder to build GHC and your package if you are not on Linux or not on the right architecture. You may set up a remote builder or Linux builder on macOS . ↩︎ Building GHC is memory intensive. You may require few GBs of RAM. ↩︎ Some of your project’s dependency libraries may link to GMP directly. In such cases, the libraries provide Cabal flags to remove GMP dependency. If you don’t want GMP linked to your executable, you’ll need to override the Nix derivation for such libraries to pass those Cabal flags. ↩︎ I learned about using these flags from the post “Linking Smaller Haskell Binaries” . It mentions few mores tricks that may be useful to you. ↩︎ Note that we get the tools and from , the original nixpkgs, not the musl one. We don’t need musl version of these tools for them to work, and doing that would simply cause our builds to take longer. ↩︎ Getting Started Static Builds 👈

0 views
Giles's blog 1 months ago

On first looking into JAX

Much have I travell'd in the realms of gold, And many goodly states and kingdoms seen; Round many western islands have I been Which bards in fealty to Apollo hold. Oft of one wide expanse had I been told That deep-brow'd Homer ruled as his demesne; Yet did I never breathe its pure serene Till I heard Chapman speak out loud and bold: Then felt I like some watcher of the skies When a new planet swims into his ken; Or like stout Cortez when with eagle eyes He star'd at the Pacific -- and all his men Look'd at each other with a wild surmise -- Silent, upon a peak in Darien. John Keats, On First Looking into Chapman's Homer I've been working with PyTorch quite a lot for the last couple of years, and feel like I've come to a reasonably solid understanding of how it all fits together. Working through Sebastian Raschka 's book " Build a Large Language Model (from Scratch) ", training my own LLMs locally and in the cloud , rebuilding Andrej Karpathy's 2015-vintage RNNs -- over time, it all adds up! But, of course, there are other frameworks, and one I kept hearing about was JAX . While it's less dominant than PyTorch, it has a reputation for a certain cleanliness, a certain purity. And having spent time over the last couple of weeks working through the tutorials, and translating small PyTorch examples into it, I've been really impressed. In this post I want to give an overview -- to report back to beginners like me, still living in PyTorch-land, on my new discovery. Less like Herschel discovering Uranus, and more like a 16th-century European coming back after having discovered something that the people who lived there were perfectly well aware of. What is this JAX thing, and how does it differ from PyTorch? I think that the main differences between PyTorch and JAX are something like this, but a little less strident: Having overstated my claims, let me dig in and perhaps walk them back a bit. Once I've gone through them, I'll do a walkthrough of porting a simple PyTorch training loop to JAX, which should illustrate the points well. Finally, I'll wrap up with the counterargument. JAX is wonderful and shiny, and 30+ years of industry experience and cynicism makes me fear that it might be doomed :-( But let's start with the positive! [Happy face on.] A simple example that nicely contrasts the different philosophies of the two frameworks is what the core of a training loop looks like. Here's how you might write one in PyTorch: This is kind of mechanistic. You're telling the computer what to do, step by step: Now let's look at a parallel JAX implementation: It's clearly very different. No explicit backward pass, no gradient-zeroing, and the forward pass and loss calculation are baked into a separate function. But why is it shaped that way? Let's think about what we're actually doing in our training loop. The gradients are the partial derivative of the loss function ℒ against the weights W : Now, I'm being a bit sloppy with that notation, because ℒ is a function, and it -- in the mathematical formulation -- takes the weights as a parameter. So it would be better written like this: But that's still not quite right. In a real training loop, we're doing this in the context of a particular input batch, X , and its associated targets, Y . 2 We might write that mathematically as this: ...where you can read the colon as "given". Now let's look again at the JAX code to work out the gradients: That's an almost-perfect mirror of the maths! The function takes a function , and returns another function, , which takes the same arguments. When you call , instead of returning the result of , it will return the derivative of with respect to its first argument, given the values of the others. 3 How is it doing that magic? Let's look at a simple concrete example: If you do the initial call to : ...then it just wraps in a helper function. It's when you call that the magic happens. ...will print out this: The first parameter -- the one with respect to which we're asking for the derivative -- is replaced by a object. Because it's wrapping a float, it can be used like one, so the function executes as expected. But it also keeps track of what happens to this variable as the code executes, and essentially builds up what in PyTorch would be represented by the computation graph. So: while in PyTorch, the variables that you pass in to a function that you need gradients for need to be special PyTorch objects that can keep a reference to those gradients -- the parameter that pops up frequently in PyTorch code -- in JAX, it's all handled by variables being automatically wrapped in these special tracers. Once it has the results of the function as a whole, including the chain of operations that was traced, it can automatically do a backward pass, and we're done. That's really nifty! Now, the example above was a toy one, with just one parameter. In a real training loop, you're differentiating against a set of weights, and those will be something more complex. But handles that gracefully. Let's see what happens if we pass in an array as the first parameter: So, we've got partial derivatives with respect to the elements of the array that was the first parameter -- just what we'd need for a single-layer neural network without bias. But what about something more complicated? For something like (say) an LLM, we have quite a lot of structure to our weights: our input embeddings, output head, all of the layers with their attention and feed-forward weights, and so on. handles that by understanding basic Python structures -- things that can be mapped to what JAX calls PyTrees. PyTrees are nested tree structures of dictionaries, lists, tuples and so on, where the leaves are numbers or JAX arrays 4 . If you ask for gradients of a variable that can be represented by a PyTree, you get them back in a form that mirrors that PyTree: If you combine that with JAX's tree-aware function, you can combine those gradients with the original parameters to update them as you train. I'll show you how that works later on, when we go through an example of porting some PyTorch code to JAX. So, all of that cool stuff was made possible by the tracer objects, which are passed in instead of the real parameters, and keep track of the computation graph (just like the graph that PyTorch attaches directly to the variables). But tracers are more generally useful than that; they really come into their own with the next JAX difference: the JIT. Imagine that you've built some kind of nifty model in PyTorch. As part of it, you do a calculation something like this: You decide that this is generally useful, so you code it up as a CUDA kernel and make it available to the community, like Erik Kaunismäki has with his "MaxSim" kernel. Maybe later on, it will get added to the PyTorch library as a standard component. There are a lot of optimisations like that built into PyTorch; people found that there were higher-level abstractions on top of basic tensor operations that were generally useful, so they coded up lower-level optimised versions. For example, in the LLM I've been working with, there is an implementation of LayerNorm . But PyTorch has its own one built in . And there's a CUDA implementation that it will use automatically if it has the appropriate hardware available. There is a problem, though. Imagine that someone else is working on a different kind of model in the future. And for reasons completely unrelated to the MaxSim calculations that Kaunismäki nicely optimised, they happen to need to do the same calculations. Now, there are two things that can happen from there: The first is not ideal; but the second isn't great either, if what they're using it for is not a MaxSim operation in reality, just something that happens to look the same mathematically. In the general case: all optimisations that get into PyTorch have to be carefully named so that they reflect the exact level of abstraction that they're targeting. And when people are writing PyTorch models, they need to actually know which optimised abstractions are available, and where to apply them. Now let's look at JAX. It has an innocuous-looking decorator, , and you can use it by adding a single line before your function: Behind that single line is a huge amount of useful infrastructure. Just like , it's a function that takes one function and returns another, without necessarily running the underlying code. 5 But when you call the wrapped function for the first time, some impressive stuff happens: This will essentially execute the code twice: The first time through, it will create another of those tracer objects; this time, though, it won't wrap the number -- it will just know that it is a wrapper for a float. It will call the Python code with that tracer, and all of the operations in the function will be run, but the result that comes out at the end will essentially just be a representation of what calculations were done in an abstract sense -- like the computation graph that was used for working out gradients, but without specific numbers in it. JAX has a nice way to display these representations as what it calls JAXPRs, and the JAXPR for that function's representation when called with a float parameter will look something like this: That JAXPR can be compiled into the appropriate code for the platform where you're running it -- x86 machine code, compiled CUDA, the equivalent for AMD or Google Tensor Processing Units (TPUs), and will be cached. The key for the cache will be meta-information about the parameter -- in this case, something like "a 32-bit floating-point scalar". Next, the compiled code -- not the original Python -- is run with the actual value of the parameter, the that we provided. Now, of course, the advantage of doing this is that when you call it with a different floating-point number -- say, -- then you don't need to do the compilation again. You can just rely on the cached version. And the fact that the compiled code is cached based on the metadata means that if you call with a vector, then it will compile a new version for that, and likewise for a matrix version. 6 This is all really nifty, and you can see how it would help right away. But for me, at least, an excellent extra benefit is how it can save people like Erik Kaunismäki the bother of writing custom kernels. The compilation that happens, taking the representation that it got from the tracing process and turning it into backend code, goes through an optimising compiler, XLA . And that compiler can recognise "standard" operations and combine them together. This won't be at the level of "standard operations" like MaxSim, of course -- more, "this looks like a convolution, let's use the standard kernel". But it does mean that instead of someone having to take code written in Python and hand-port it over to CUDA to get a GPU speedup, the same expertise can be put into improving the optimisation part of XLA to get a speedup for all code. That's pretty amazing. However... If you want something like the JIT to work properly, you need to limit the kind of code that it works with. In particular, it needs to be functional. A function must always return the same value when given the same inputs -- so this is fine: ...but this will cause problems: ...because could be changed. Specifically -- because the global had the value during the initial traced run of the function, that value will essentially get hard-coded into the cached JITted version, so both prints in the second example will output . Something slightly surprising comes out of this -- something that makes JAX code look very different to PyTorch. How we handle randomness needs to completely change. Consider this code: As a whole, it's deterministic. But it breaks the functional requirement that the function can only depend on its inputs. Both calls to take the same input, but they return different results. Even worse, if we were to do something that consumed randomness between those two calls to , for example: ...we'd get different results. The state of the random number generator is global state kept outside the function, just like in the example above. A naive solution to this might be to make the state of the RNG explicit as a variable -- you can imagine a library that worked something like this: That looks more functional, but when you think about it, we haven't actually fixed the problem. We're passing the same variable in in both cases, along with the same number, but we're getting different results. It's not global, but it's still mutable behind the scenes. What you'd actually need to do to make it purely functional would be something like this: The function is generating a new random integer and returning both that and the new state of the RNG, then we pass that back along with our result. We've made the random state variables immutable, and so it's functional. But the API is getting pretty ugly pretty quickly. So JAX does something that is equivalent, but a bit cleaner. There's a concept of a key , which needs to be passed into any function that consumes randomness: That's kind of like the that we have in the first version of the code above. But it's immutable; when you use it, like this: ...it will not be changed, so no matter how many times you call it with the same key, that function will return the same value. (Note that takes an inclusive lower bound and an exclusive upper bound, like Python's , but unlike the stdlib's . It also needs to know the shape of the result -- for a scalar, for a 1x2 array, and so on.) If you want it to "move on" to a new state, you use the function, which takes an existing key and returns two (or more) new ones. So you can do something like this: Now, that and stuff is a bit ugly, but while it's not OK to mutate the contents of variables in functional code, it's absolutely fine to assign a new value to an existing one, so what I've found myself doing is writing stuff like this: However, there are more powerful ways to use ; I'm not confident enough at using it yet to go into that, though, so I'll hold back for now. I suspect (assuming I keep using JAX) I'll be posting about them in the future. OK: so the JIT means that we have to write functional code, which makes things a bit fiddly -- no more global state. And that has a surprisingly big knock-on effect with randomness. But there's another thing that comes out of the JIT and the way it does tracing. It's not a functional thing (though some of the docs seem to almost be treating it that way), but is caused by the same kind of constraints. It's not part of my four theses above, but I think it's important enough to call out in its own subsection. Imagine this function: It's purely functional, so no problem there. But let's think about what the JIT is trying to do. It wants to convert the function into a simple sequence of operations, so it will create a tracer for a floating-point scalar, then call with it. When it hits that statement, there will be a problem. The tracer is meant to represent any arbitrary float, so should it take the branch or not? There's no good answer. It doesn't know which branch to follow -- whether the sequence should be "square it and return the result" or just "return it directly" -- and will fail with a somewhat obscure error message: So this gives a hard constraint on functions that you want to JIT: by default, they can't base control flow on the values you pass in. There is a workaround -- but it comes with tradeoffs. Let's take a slightly sideways route to explain it. Firstly, although you cannot do control flow based on the value of a parameter -- which the tracer doesn't know -- you can base it on other information that actually is stored in the tracer. Let's say that we called like this: The tracer that would be passed in when trying to trace the function would be something representing a 2x2 array. The shape of the parameter is part of the tracer, even though the values aren't. So you could do something like this: ...and it would work. It's worth thinking explicitly why this is. When you call a JITted function, it will create a tracer that contains information about the type of thing you passed in as a parameter -- scalar versus array, and if it's an array, the array's shape. It then runs the function with the tracer, gets the sequence of operations, compiles them and then stores the result in a cache keyed on the metadata -- type and, if appropriate, shape -- that it used to create the tracer. So when we call that function with a 2x2 array, we get a 2x2 array version, then if we call it later with a one-dimensional array of length 2, we'll get a new version for that. One workaround for basing control flow on values is essentially to tell the function that it should treat the values of a particular variable as being like the metadata used for this cache keying: it should compile a new version for each value it sees, rather than just using the metadata. It takes a parameter , and a matching , which tell it which parameters to do that with. So, this will work: (Remember that the thing after the for a decorator needs to be a function that returns a function, so we have to use to "inject" in the extra argument.) However, the downside is pretty clear: every time we call with a new value, it's going to have to JIT a new version of the function and cache it -- that's going to be slow and take up memory. So, as an alternative, we can use the package . This provides more functional-looking alternatives for control flow, which are compatible with the way the JIT works. For example, there's a function, which we can use to replace s: That feels a little bit like a workaround, but it does solve the problem. How? Well, it's worth checking the JAXPR for it: What's happened here, I think, is that the JIT has recognised the call to as being a primitive function in its intermediate language, so has just kept it in there. It couldn't do that with the because when it was tracing, all JAX itself saw was what was happening to the tracer -- there was a boolean comparison, and then the stuff in the chosen branch happened. The fact that there was an there happened in Python itself, outside JAX, so it was "invisible" to the trace. That feels a little inelegant to me right now, and I'll come back to it later. Let's move on to the final difference between the two libraries that I want to cover: JAX's relative minimalism to PyTorch's more maximalist approach. I think the smaller size of JAX -- at least in terms of its API, if not in terms of the JIT and XLA magic under the hood -- compared to the sprawl of PyTorch is not entirely unrelated to the JIT being at its core. PyTorch, after some initial design, has almost been forced to grow organically; JAX feels more carefully designed, so it doesn't have the same need to grow (though of course it can). The reason for PyTorch's growth is, at least in part, because it needs to absorb optimisations. If something is slow, someone needs to write a CUDA kernel for it. If there's a CUDA kernel, it needs an API. And if it is generally useful, that API becomes part of PyTorch. Multi-head attention? There's a class for that . SELU? Yup . Very specific softmax approximations based on a paper published in 2016? PyTorch has you covered . By contrast, JAX doesn't even have linear layers or optimisers in the framework itself; if you want to use them, you can write them yourself (contraindicated), or you can use libraries built on top of JAX , like Flax for common neural network components and Optax for optimisers. This feels like a nice division of responsibilities, and it also seems like something that would have been very hard without the JIT. So while the JAX core may well grow in the future, the design it has now puts it in a good position to grow in a more planned, well-designed manner -- rather than having to grow to absorb more and more abstractions just to keep it fast. Those abstractions can more easily sit in libraries written on top of JAX. That's the 10,000-foot overview; four (or maybe four and a half) main differences between PyTorch and JAX. It's more maths-y, JITted, functional and minimalist. What does that actually mean when you get down to coding with it? Let's get into the weeds with an example. Let's use a really simple one: training a neural network with two inputs and one hidden layer to calculate the XOR function. The code is in this GitHub repo , but I'll put the relevant bits here in this post. Firstly, an idiomatic PyTorch implementation: If we run that, it trains a solid-looking model in about four seconds on my machine: Now, if we're porting to JAX we need to do something about the fact that JAX doesn't have optimisers and the neural network stuff built in. If this was a real codebase, we'd almost certainly do that by using the libraries built on top of JAX, like Flax and Optax. But for this toy example, I think it's more illustrative to strip down the PyTorch version so that it uses fewer parts of the API -- essentially so that it only uses the stuff that JAX has -- and then to port the result. The optimiser first. The code is here but the diffs are pretty simple. Instead of creating an optimiser, we just specify our learning rate: Instead of zeroing out the gradients using the optimiser, we can just ask the model to do it: And instead of stepping the optimiser, we call a new function passing in the model and the learning rate: The function is simple enough; we just switch into mode so that PyTorch doesn't try to track the computation graph (working out gradients for applying gradients and triggering some kind of crazy gradient-ception), then we just iterate over the model's parameters and follow the normal SGD process, subtracting the gradients times the learning rate: Running that on my machine actually works out slightly faster than the original 7 ! It's also quite nice to see that (within the bounds of the printing precision) the loss and the final results are identical. OK, so now that we've got rid of the optimiser, let's do the same with the s. Here's the code , but let's do a quick walk through the differences. Instead of creating an , we will just generate an array of layers: Zeroing out the existing gradients will also need to be done on those layers: ...and likewise our loss calculations and the function will need to use them: We used a couple of new helper functions there; this one generates the initial weights for the layers (based on the docs for ): Note that each of the tensors we created, the and the need to be explicitly told, using , that we're going to want PyTorch to track gradients on them. Zeroing out the gradients is just a case of chugging through each layer, and then for each setting the weights' and the biases' gradients to : Now, to calculate the loss, we're actually not changing much. We had this: ...and now we just change it to this: That is, we've added on a new function to do a forward pass through the given layers with the given parameters. That looks like this: Standard NN stuff . A quick tweak to use in the printing of the results at the end: ...and we're done! Let's run it: Even faster! Sounds like there aren't any nice pre-baked optimisations in that part of PyTorch, then... But again, within the bounds of our precision, that's exactly the same numbers as we got from the original PyTorch version, which is very reassuring. OK, now that we've got something that's kind of JAX-shaped, let's port it over. I think it's worth showing all of the code for that (though it's here on GitHub if you want to view it there), and then I'll highlight the important diffs separately. If you look at it side-by-side with the previous PyTorch implementation , you'll see that it's really similar! Running between them makes them look more different than they are because of the extra threading through of keys that we need to do in order to satisfy the strict constraints on random number handling in JAX, (and of course there are function name changes like becoming and becoming ). But the important changes are much smaller. Firstly, weights and biases no longer need to know that we'll want to track gradients for them, because that's all handled by the tracers that JAX wraps around them: Relatedly, the function that iterated over the layers and zeroed out the existing ones is completely gone. Because gradients are now stored on tracers that wrap around our parameters rather than on the parameters themselves, we don't need to zero them out. The step function is still there, though, but it's much simpler. Before we get to that, let's take a look at the way we're getting the gradients for it, in the main training loop. Here's the diff: Hopefully the change there will be nice and familiar from the start of this post: we've moved from the PyTorch procedural "do a forward pass then do the backward pass" to the JAX maths-y "work out the gradients for this function". is a utility function that does the same as the we encountered then, but rather than just returning the gradients, it also returns the value of with the given parameters, which is useful for our logging. Now, remember that is a list of dictionaries, something like this: And also remember that -- and likewise -- have that smart trick where they return the gradients in the same PyTree structure as the parameter that we're taking the derivative with respect to. So will also be a list of dictionaries, each of which has and . Now, as I mentioned earlier, JAX has a useful function called . Like the Python function that maps a function over one or more lists, JAX's version maps a function over one or more things with the same PyTree structure. So, because and have the same structure, our function can just use it to apply simple gradient descent like this: Very clean :-) That's it! A full JAX implementation of our toy example, and when we run it: ...it works! So, let's move on to... Yikes. It was almost 30 times slower than the PyTorch version. But then -- we did all of that work to port the code over to JAX, which is great because it has a JIT, and then we didn't use the JIT. Whoops! Adding a few calls to helps. If we add them to the , and function then we get this code , which is faster: ...but it's still almost eight times slower than the PyTorch code. How can we make it faster? Well, perhaps we can do more if we put more of the loop into the JITted stuff. Right now, the core of our training loop looks like this: and are JITted. But what happens if we try to JIT a larger step? We can move the forward pass and the step into a JITted function on their own: ...and then call it in the loop like this: With that, all of the JAX code apart from input and target wrangling is moved into a JITted function. We get this code , and running it gives us this: Woohoo! Almost 45% faster than the PyTorch version :-) So: porting to JAX alone gives us nice maths-y code, but we need to JIT it properly to get performance that matches PyTorch. (The fact that it's faster than PyTorch in this case is not something that I think you could rely on -- this is, after all, a toy example.) It's also an interesting indicator that you actually need to think about what to JIT. My initial thought, "just whack an on the inner stuff", was not enough. We needed to do more than that. I've just had an interesting chat with Claude Opus 4.8 about that, though, and will probably post more about it later. For now, I think a useful rule-of-thumb is to wrap stuff in at as high a level as you reasonably can, to maximise coverage. So, this completes the happy part of this post -- I've shown what it can do, how nicely it maps to the maths, and how it's (relatively) easy to make it fast. What are the downsides? Another deliberately overly-strident heading ;-) I've been programming for more than 40 years, and working professionally in the tech industry for more than 30. I'd like to feel that this makes me a better engineer than I was when I was first starting out, but I can confidently say that it has made me a much more cynical one. Over that period, I've come to categorise new APIs, languages, and tools into three approximate groups: godawful hacks, solid but not overly inspiring engineering, and things of beauty. They're loose categories, and most things are somewhere between one and another. But I think they hold reasonably well. My cynicism and experience tells me that: When we were building our programmable spreadsheet, Resolver One , some of the team pointed out that a functional language -- specifically, Haskell -- would be a better fit than Python. It was a tough decision to stick with Python, and I'm still not 100% sure it was the right one. But I do remember having sales meetings with quants at various financial firms about it, and in those meetings, some of the potential customers also suggested a Haskell port. I'm not saying that there's a perfect correlation between where we heard that, and the later notes in our sales status spreadsheet saying "client being acquired by a non-bankrupt competitor, all expenditure on hold" during the 2008 financial crisis. But I'm not not saying that either. If you've read this far, you can probably tell that I see PyTorch as solid engineering, and JAX as closer to a thing of beauty. Maybe it's just the cynicism of age, but let me try to articulate the things I worry might put JAX into the "beautiful but doomed" side of the "beautiful" category. Firstly, I'm not convinced by the way that JAX, with its JIT, requires you to try to write Python as if it were a functional language. It's easy enough to see that this isn't functional: ...but harder with this: Even worse, the way that tracing works means that you have even more constraints than "just" being functional would require -- remember this example from earlier? Python is not functional, and is deliberately so. Trying to make it so is always going to lead to weird bugs (for example, how the value of the global on the first run would be baked into that function) and hard-to-understand error messages (you really need to be clued-up to work out what means). The package -- for example, the function we used to work around the fact that JAX could not "see" the Python way back in this post -- feels like a bit of an ugly workaround. Python has control flow functions, but they don't work with the JIT's tracing, so we have to re-implement them in JAX. Hmmm. Now, I've written extensively above about how JAX's restrictions, however confusing, enable a lot of the amazing stuff that wouldn't be possible in normal PyTorch. What if there were some way to write PyTorch code and compile it directly to something that can execute on the hardware? It turns out that as of 2023, there is: . From what I understand, you're meant to be able to just attach it to your code and it gets JITted. But unlike JAX, you don't need to restrict the code you write. I've not investigated in much depth (after all, this post is already absurdly long and has taken more than a month on and off to put together), but it looks like it handles stuff that can't be compiled by using a concept of a "graph break" -- that is, it happily JITs what it can, then if it hits something that it can't JIT, it will cache the "work so far" as one compiled unit, run the Python code for the unJITable stuff, then (when it can) drop back into JIT mode. The best of both worlds? I don't know, and would need to spend much more time investigating in order to learn. But I can say that for my minimal-effort port of my toy XOR code , following the structure of the JITted JAX version, it really did not help: For those who are keeping track, that's slower than the uncompiled version, which came in at about 3.5s. And the issue doesn't seem to be an up-front cost of JITting that would be paid off if we ran for more epochs -- each individual "Loss at epoch XXX" print comes out slower. Again, for the sake of sanity I'm not going to dig into it further, especially given that this is a tiny toy model and probably about as far from the target use case of as you can get. But it's something well worth noting for the future. Stepping back: one other way of looking at this is that Python might just be the wrong language to try to build code that compiles to GPUs. I'm learning JAX right now so that I can re-implement my existing LLM from scratch project in something other than PyTorch, to make sure that I really understand it. I asked people on X/Twitter for votes or ideas , and while JAX won, Jeremy Howard suggested Mojo . Mojo is a Pythonic language that compiles directly to CPU or GPU code, so it explicitly only contains features that can be ported that way. Unfortunately, it's lower-level than I really wanted for this project (and, importantly, does not have built-in autograd support). But if it did -- if, for example, there was a library like JAX for it, perhaps it would be better than using Python as the foundation? I've looked for something like that, but to no avail. Some work-in-progress projects, but nothing ready for use. At the end of the day, I think further experience is essential if I'm going to come to a solid opinion on JAX. Experience with other tools can only get you so far, and it's easy to fail by pattern-matching what you're looking at with things that you've seen before, especially when you're old and cynical. All I can say at this point is that JAX is making my "beautiful but doomed" spidey-sense tingle. 8 The title of this post is important -- it is my impressions on first looking into JAX, not the considered thoughts of someone who's spent months or years working with it. I've only scratched the surface, and haven't even touched the larger JAX ecosystem, or indeed its powerful handling of memory sharding for multi-GPU or even multi-node setups (which may well be one of its biggest advantages). My next step is going to be to implement a GPT-2-style LLM in JAX, probably using Flax and Optax as helpers, and perhaps by the time I'm done with that I'll have changed my views. But at this point -- after working through the tutorials and porting some toy models to get at least an initial feel for it, I've come to the conclusion that I like it. The question is, do I like it like I liked Python when I first came to it -- "this thing is really neat and clean, even if it has flaws" or is it more like I liked Haskell -- "this is a stunning thing of beauty and is completely doomed in the real world"? Time will tell. But in the meantime, if you've been working with JAX for some time and want to counter any of the points I made, if I've completely misunderstood anything, or if you have any corrections, then please let me know! After all, explorers in areas new to them are prone to making mistakes from time to time... The forest of Skund was indeed enchanted, which was nothing unusual on the Disc, and was also the only forest in the whole universe to be called -- in the local language -- Your Finger You Fool, which was the literal meaning of the word Skund. The reason for this is regrettably all too common. When the first explorers from the warm lands around the Circle Sea travelled into the chilly hinterland they filled in the blank spaces on their maps by grabbing the nearest native, pointing at some distant landmark, speaking very clearly in a loud voice, and writing down whatever the bemused man told them. Thus were immortalised in generations of atlases such geographical oddities as Just A Mountain, I Don't Know, What? and, of course, Your Finger You Fool. Rainclouds clustered around the bald heights of Mt. Oolskunrahod ('Who is this Fool who does Not Know what a Mountain is') and the Luggage settled itself more comfortably under a dripping tree, which tried unsuccessfully to strike up a conversation. Terry Pratchett, The Light Fantastic Specifically, prior to the introduction of -- more about that later.  ↩ That's something I find myself constantly forgetting; I'll talk about "the loss landscape" as if it's something our training loop is exploring. And, of course, there is an overall loss landscape across all of the training data as a whole, but in any given iteration through the training loop, the loss is relative to the specific batch we're looking at.  ↩ You can also pass in an argument, zero by default, to tell it to do the derivative with respect to a different parameter or with respect to a sequence of parameter indexes. If you give a sequence, it will return a tuple of gradients. Additionally, there's a that returns a tuple of the value of and the gradients, which is useful for tracking loss as you train -- we'll use that later on.  ↩ You can also make classes "PyTree-compatible" by providing helper functions that map to and from that representation.  ↩ A reminder if your memory of Python decorator syntax is rusty -- this: ...is just syntactic sugar for this: It's a tad more complicated than that -- the metadata for array traces also contains the shape. More about that later.  ↩ For the pedantic: over ten runs of each, the numbers were pretty stable.  ↩ In case you're thinking that JAX is backed by Google and guaranteed to thrive because of that, remember Ada . Backed by the US Department of Defense. For its time, well-designed and elegant. It's still used, but it's hardly mainstream... I remember reading about it in Byte magazine back in 1988 or so, and had an "it's so beautiful" moment then too. To be fair to me, I was 14.  ↩ PyTorch is engineering; JAX is maths. PyTorch has historically 1 been optimised piecewise, JAX is JITted. PyTorch is procedural, JAX (tries to be) functional. PyTorch is maximalist; JAX is minimalist. Zero out the gradients that you currently have attached to the parameters. Do a forward pass to get the model's outputs. Work out the loss based on those outputs. Do the backward pass. Update the parameters based on the gradients that the backward pass attached to them. They don't know that the MaxSim kernel exists, so their code remains unoptimised. They do know that it exists, so they repurpose it for whatever their use case is. The first time through, it will create another of those tracer objects; this time, though, it won't wrap the number -- it will just know that it is a wrapper for a float. It will call the Python code with that tracer, and all of the operations in the function will be run, but the result that comes out at the end will essentially just be a representation of what calculations were done in an abstract sense -- like the computation graph that was used for working out gradients, but without specific numbers in it. JAX has a nice way to display these representations as what it calls JAXPRs, and the JAXPR for that function's representation when called with a float parameter will look something like this: That JAXPR can be compiled into the appropriate code for the platform where you're running it -- x86 machine code, compiled CUDA, the equivalent for AMD or Google Tensor Processing Units (TPUs), and will be cached. The key for the cache will be meta-information about the parameter -- in this case, something like "a 32-bit floating-point scalar". Next, the compiled code -- not the original Python -- is run with the actual value of the parameter, the that we provided. Horrible hacks can inexplicably become popular, but normally die off when people get tired of swearing at them. (Though sometimes a large installed base means that they linger.) Things of beauty get people excited, and often pull in the best engineers. But eventually, they drop by the wayside. Perhaps there's some hidden flaw that no-one noticed at the outset, or perhaps the mental model you need to build in order to use them effectively is too complicated for them to get to critical mass. Solid, boring engineering wins in the long term. Specifically, prior to the introduction of -- more about that later.  ↩ That's something I find myself constantly forgetting; I'll talk about "the loss landscape" as if it's something our training loop is exploring. And, of course, there is an overall loss landscape across all of the training data as a whole, but in any given iteration through the training loop, the loss is relative to the specific batch we're looking at.  ↩ You can also pass in an argument, zero by default, to tell it to do the derivative with respect to a different parameter or with respect to a sequence of parameter indexes. If you give a sequence, it will return a tuple of gradients. Additionally, there's a that returns a tuple of the value of and the gradients, which is useful for tracking loss as you train -- we'll use that later on.  ↩ You can also make classes "PyTree-compatible" by providing helper functions that map to and from that representation.  ↩ A reminder if your memory of Python decorator syntax is rusty -- this: ...is just syntactic sugar for this: ↩ It's a tad more complicated than that -- the metadata for array traces also contains the shape. More about that later.  ↩ For the pedantic: over ten runs of each, the numbers were pretty stable.  ↩ In case you're thinking that JAX is backed by Google and guaranteed to thrive because of that, remember Ada . Backed by the US Department of Defense. For its time, well-designed and elegant. It's still used, but it's hardly mainstream... I remember reading about it in Byte magazine back in 1988 or so, and had an "it's so beautiful" moment then too. To be fair to me, I was 14.  ↩

0 views
Corrode 1 months ago

Migrating from Go to Rust

Out of all the migrations I help teams with, Go to Rust is a bit of an outlier. It’s not a question of “is Rust faster?” or “does Rust have types?”, Go already gets you most of the way there. The discussion is mostly about correctness guarantees , runtime tradeoffs , and developer ergonomics . A quick disclaimer before we start: this guide is heavily backend-focused . Backend services are where Go is strongest, small static binaries, a standard library focused on networking, and an ecosystem of libraries for HTTP servers, gRPC, databases, etc. That’s also where most teams considering Rust are coming from (at least the ones who reach out to me), so I think that’s the comparison that’s actually useful in practice. If you’re writing CLI tools, embedded firmware, or game engines, some of this still applies, but to be honest, I’m afraid this is not the best resource for you. For context, I’ve written about Go and Rust before: “Go vs Rust? Choose Go.” back in 2017, and later the “Rust vs Go: A Hands-On Comparison” with the Shuttle team, which walks through a small backend service in both languages. What you will learn in this article I’ll be upfront: I’m not a fan of Go. I think it’s a badly designed language, even if a very successful one. It confuses easiness with simplicity , and several of its core design tradeoffs ( everywhere, error handling as a discipline rule rather than a type, the long absence of generics) point in a direction I disagree with. That said, success matters! Go has captured a real and persistent share of working developers, hovering around 17–19% in the JetBrains Developer Ecosystem Survey. Rust is growing steadily but is still a smaller slice: Go is clearly working for a lot of people, and a guide that pretends otherwise isn’t helpful. So I’ll do my very best to be objective in this guide rather than relitigate old arguments. But you should know my priors so you can calibrate. The other prior worth disclosing: I run a Rust consultancy; of course I’m biased! More people using Rust is good for my business. But I’ve also worked in both languages professionally and shipped Go services to production. This guide is for Go developers who want an honest, side-by-side look at what changes when you move to Rust. For a deliberately opposite take, I recommend reading “Just Fucking Use Go” by Blain Smith. Holding both views in your head at once is more useful than either one alone. If you prefer to watch rather than read, here’s a video from the Shuttle article above, read and commented by the Primeagen: Go developers already have one of the cleanest toolchains in the industry. Back in the day, it started off a trend of “batteries included” toolchains that give you a single, consistent interface for building, testing, formatting, linting, and managing dependencies. I’m glad that Rust followed suit, because it’s a great model. It’s one of my favorite parts about both ecosystems. has even more built-in: The big difference is that in Go you typically reach for third-party tools ( , , , ) to fill gaps. In Rust, the first-party ecosystem covers more out of the box. Things that do require external crates (e.g. , ) install with one command and feel native, e.g. gives you right away. Both communities have converged on the same insight about formatters: a single canonical style, even an imperfect one, is worth more than the bikeshedding it eliminates. Gofmt’s style is no one’s favorite, yet gofmt is everyone’s favorite. — Rob Pike, Go Proverbs The same is true of : not everyone likes every detail, but the absence of style debates in code review is worth far more than the occasional formatting preference you’d have made differently. The headline is that Go and Rust are both compiled, statically typed, single-binary-deploy languages with strong concurrency stories. The differences are about what guarantees you get from the compiler and how much control you have over runtime behaviour . Go developers don’t usually come to Rust because Go is “too slow.” For most backend workloads, Go is plenty fast. People are generally a bit frustrated with Go’s verbose error handling, the danger of segmentation faults from pointers, and the lack of generics (for a long time) or any sophisticated type system features, such as enums or traits. Interfaces are not a worthy replacement for traits, and the Go standard library has some weird gaps, such as the lack of a type. I call it my billion-dollar mistake. It was the invention of the null reference in 1965 … This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years. — Tony Hoare, inventor of , QCon London 2009 This is the one I hear most often. You ship a Go service, it runs fine for months, and then one Tuesday at 3 a.m. a code path runs where someone forgot to check whether a pointer was , and the goroutine panics. Go’s compiler does not force you to consider the absence case. Rust’s does: You literally cannot dereference an without acknowledging the case. Whole categories of pager-duty incidents disappear. is a great tool, but it’s a runtime detector, it only finds races that actually execute during your tests. Mutating a map from two goroutines without a lock compiles fine in Go and only blows up in production under load. In Rust, sharing mutable state across threads requires types that implement and . Try to share a plain between threads and the program does not compile . You’re forced to wrap it in an , an , or use a channel. That race condition becomes a type error. 1 is fine for a while. After a few years, you notice three things: It’s worth being honest about the counter-argument here, since it came up in the Lobste.rs thread on my Shuttle article: experienced Go developers point out that and catch most of the “forgot to handle the error” cases in practice, and that explicit is easier to read than dense chains. Both points are fair, and the explicit style is a deliberate cultural value, not an accident: I think that error handling should be explicit, this should be a core value of the language. — Peter Bourgon, GoTime #91 , quoted in Dave Cheney’s Zen of Go My take is that lints are an opt-in safety net you have to remember to set up, while Rust’s is the type signature itself, there’s no way to forget. The boilerplate-vs-readability tradeoff is more genuinely subjective. The operator handles propagation; handles wrapping; and a on is exhaustively checked . Add a new variant tomorrow and the compiler shows you every place that needs updating. Go got generics in 1.18, and they’re useful, but the implementation has constraints (no methods with type parameters, GC shape stenciling, occasional surprising performance characteristics). Rust generics monomorphize, each instantiation produces specialized code with zero runtime cost. Combined with traits, this gives you real zero-cost abstractions. This matters less in handler code and more in shared infrastructure (middleware, generic repositories, decoders, parsers), where Go often pushes you back to / plus type assertions. Go’s GC is excellent, concurrent, low-pause, well-tuned for typical service workloads. But “low-pause” is not “no-pause.” Under heavy allocation, P99 latency tails are noticeably worse than a Rust equivalent that simply doesn’t allocate on the hot path. I won’t oversell this, for the vast majority of services, Go’s GC is a non-issue. But for latency-sensitive systems (trading, real-time bidding, network proxies, high-throughput ingestion), the lack of GC pauses is a genuine selling point. Go is death by a thousand paper cuts. It is a very pragmatic language and if you are willing to glance over the above issues, you can be very productive in it. But at a certain codebase size, the problems start to compound. There is no single moment when Go loses its appeal, but teams find themselves wishing for more (more safety, more control, more expressiveness) and that’s when they start looking around for alternatives. The fastest way to feel comfortable in Rust is to map patterns you already know. For a longer, fully-worked example of building the same backend service in both languages, see the Shuttle comparison , the section below focuses on the patterns that come up most often. The operator does the dance for you, including type conversion if is implemented (idiomatic with ’s ). There is no in safe Rust. References can’t be null. Pointers can be, but you almost never use raw pointers in application code. Go’s interfaces are structural, a type satisfies an interface implicitly: Rust’s traits are nominal, you implement them explicitly: The Go style is great for ad-hoc duck typing. The Rust style is great for refactoring and discoverability, you can grep for every implementer of a trait. The closest equivalent of / in Rust is , but you almost never want it. The Go community knows the cost of reaching for too: interface{} says nothing. — Rob Pike, Go Proverbs Generic functions with trait bounds ( ) cover the vast majority of cases and give you monomorphization with no runtime dispatch. Where Go pre-1.18 would have forced you back to plus a type assertion, Rust’s traits + generics let you stay specific. When you do want runtime dispatch (e.g. heterogeneous storage of different implementers), reach for or . That’s the direct Rust analog of holding an value in Go. Go’s concurrency model is famously simple: Goroutines are cheap, the runtime schedules them across OS threads, and channels ( ) are the primary coordination primitive. The Go proverb captures the philosophy: Don’t communicate by sharing memory; share memory by communicating. — Rob Pike, Go Proverbs This is the area where Go genuinely shines, several commenters in the Lobste.rs discussion made the point that goroutines “just disappear” into normal-looking blocking code, and that’s worth giving Go credit for. Rust async is more powerful, but it’s also more visible in your code. Rust uses / on top of an executor (almost always for backend services): The shape is similar. The differences: For most backend code, the day-to-day feel is similar: spawn a task, communicate via channels, use timeouts liberally. In Go, you plumb a through every blocking call: Rust has no built-in . The closest equivalent for cancellation is : For timeouts, wraps any future. For deadlines/values, you typically pass them as explicit arguments or via spans rather than a single context object. Some Go developers miss the implicit-feel of . In practice, the explicit Rust style is easier to reason about, you always know exactly what’s cancellable and what isn’t. The deeper point is that neither language gives you cancellation for free, the discipline just shows up at different layers: Go doesn’t have a way to tell a goroutine to exit. There is no stop or kill function, for good reason. If we cannot command a goroutine to stop, we must instead ask it, politely. — Dave Cheney, The Zen of Go In Go that “asking politely” is a plumbed through every call site by convention. In Rust it’s a (or a channel) plumbed through every call site, but the compiler can actually tell you when you forgot. Both languages have channels. The translation is direct: Rust’s channels distinguish sender and receiver as separate types, which makes ownership and -ness explicit at the type level. Rust’s is the equivalent of a Go value receiver; is a pointer receiver with mutation. Owned (consuming the value) has no Go analog and is occasionally very useful (typestate, builders). Go’s is a UTF-8 byte slice with copy-on-assign semantics (the header is copied, the underlying bytes are shared and immutable). Rust splits this into two types: As a rule of thumb, take in arguments, return when you produce new data. This is mostly painless once you internalize it. The vs split is a microcosm of Rust’s broader “borrow vs own” model. Go got generics in 1.18 (March 2022), thirteen years after the language shipped. They are useful, but they feel tacked on, and in practice they have most of the downsides of a generic type system without delivering the upsides you’d expect coming from Rust, Haskell, or even modern C++. This is a strong claim, so let me back it up. The most telling signal is that three years after generics landed, Go’s own standard library still mostly avoids them. still takes a closure instead of a constraint. is still typed as / . The generic helpers that do exist live in a small handful of packages: , , , and a few entries under . Compare that to Rust, where generics permeate the standard library from day one: , , , , , / , , , every collection, every smart pointer. You cannot write idiomatic Rust without using generics, because the standard library is generic. In Go, generics are an opt-in feature for library authors who really need them. In Rust, they’re the substrate everything else is built on. Rust’s generics are tied to traits, which double as the language’s mechanism for ad-hoc polymorphism, supertraits, associated types, blanket impls, and coherence. Go’s constraints are just interfaces with an extra operator for type-set membership. There are no: The practical consequence is that the moment your abstraction needs more than “a function that works for any with these few operations,” Go pushes you back to plus type assertions, code generation, or runtime reflection. Rust uses a Hindley-Milner-style inference engine that propagates type information through entire expressions, including across closures, iterator chains, and operators. You routinely write: and the compiler figures out is from the range, and is from the target. Go’s inference is much shallower. It can usually infer type parameters from function arguments, but it cannot infer from return-position context , cannot chain inference through generic builders the way Rust does, and frequently forces explicit type arguments at call sites: In Rust this is the exception; in Go it’s still common. Rust monomorphizes: every and produces specialized machine code with zero runtime dispatch. Go uses GCShape stenciling with dictionaries , where types that share a “GC shape” share the same compiled function and dispatch through a dictionary at runtime. The result is a compile-time/runtime tradeoff that often surprises people: generic Go code can be measurably slower than the equivalent hand-written non-generic version, because every method call on a type parameter goes through an indirection. There’s a well-known PlanetScale post showing exactly this. In Rust, generic code is the fast path. Reaching for (the equivalent of Go’s interface dispatch) is a deliberate choice you make when you want runtime polymorphism. This is the part that bothers me most. A good generics system removes reasons to fall back to escape hatches. In Rust, generics + traits eliminate most of what you’d otherwise need or runtime reflection for. The type system gets stronger. In Go, generics did not remove , did not remove , did not remove code generation as the dominant pattern for things like ORMs, decoders, and mocks. still uses reflection. still uses . still generates code. The places where a real generics system would shine are the same places Go reaches for runtime mechanisms it had before 1.18. Generics in Go feel additive, a new tool in the box that’s useful in narrow cases. Generics in Rust feel foundational; remove them and the language collapses. That’s the difference, and it’s why generic Go code, in my experience, doesn’t read better than the -based code it replaced; it just reads differently, with more punctuation. If you’re already opinionated in Go, the Rust ecosystem has converged to a similar level of “default picks.” For a typical backend service: + + + + + covers 90% of what you need. I want to be straightforward here. Coming from Go, you will hit a wall . The wall has a name. Go’s runtime handles memory and aliasing for you. Rust pushes that decision into the type system. The first few weeks you’ll write code that “should obviously work” and the compiler will refuse it. The patterns that bite Go developers most often: With all of these rules, the borrow checker truly sounds like a “gatekeeper” of sorts, which keeps getting in the way and is just overall frustrating to deal with. That is not the mental mindset you should have when learning Rust. The borrow checker truly uncovers real and very existing bugs in your code, and if you don’t address them, your program will deal with safety issues. So whenever you get a compiler error from , take a step back and think how your code could break. A few questions you can ask yourself: That is the mindset you need to understand the borrow checker. Humans are genuinely bad at reasoning about memory. We forget that pointers can be null, that old references can outlive the data they point to, and that multiple threads can touch the same data at the same time. We tend to have a “linear” mental model of how data flows through a program, but in reality it’s closer to a complex graph with many paths and interactions. Every condition forces you to consider what happens in both branches. Every loop forces you to consider what happens on every iteration. That is exactly the kind of reasoning the borrow checker is designed to do for you! It enforces best practices at compile time, and it can feel annoying when your own mental model disagrees with the borrow checker’s (which is the more accurate one 99% of the time). There are cases where the borrow checker is genuinely too strict, but they are rare, and as a beginner you’ll almost never run into them. I got memory management wrong plenty of times in my early days, but I approached it with a learner’s mindset , which helped me ask “what’s wrong with my code?” instead of “what’s wrong with the compiler?”, a reaction I see a lot in trainings. The good news is that once you internalize borrowing, it stops fighting you. Most experienced Rust developers will tell you the borrow checker became an ally somewhere between weeks 4 and 12. The first month is the hardest. Be honest with your team, Rust compile times are a real downgrade from Go’s. A clean release build of a medium service can take minutes in comparison to Go’s near-instantaneous compiles. Incremental builds and are reasonable and compile times have gotten much better over the years, but you’ll feel the difference. To mitigate, use in your edit loop, split into a workspace once it pays off, and keep proc-macro-heavy crates in their own crate so they only recompile when they change. See tips for faster Rust compile times for a deeper dive. Go’s “one type of function, sync everywhere, the runtime handles concurrency” is genuinely simpler than Rust’s split between and . You’ll need to think about which of your functions are async, where you , and how that interacts with traits. Async traits (stable since Rust 1.75) help a lot, but there are still rough edges (especially around with async methods). Rust’s crate ecosystem is growing and libraries are high-quality across the board, but Go has a head start in some backend-adjacent domains: Kubernetes operators, cloud-provider SDKs, database drivers for certain niche stores. Before you commit, spend a day checking that the libraries you depend on have Rust equivalents you’re willing to use. Teams I help often have to hand-roll at least one or two core libraries themselves. For example, they might have to update an abandoned crate for XML schema validation, or write their own client for a lesser-known protocol. You don’t have to rewrite everything in one go. The strategies that work best, in order of how I usually recommend them: If one specific service in your fleet is the perpetual problem child (high CPU, latency-sensitive, or constantly hit with reliability issues), rewrite just that one in Rust, behind the same API contract. This is the lowest-risk migration. Other Go services keep talking to it via HTTP/gRPC, oblivious to the underlying language. Background workers, queue consumers, ingestion pipelines, and CPU-bound batch jobs are excellent first targets. They typically have a clear input/output boundary (a queue, a topic) and no shared in-process state with the rest of the system. You can call Rust from Go via cgo, and there are good guides on how to do it . (Reach out if you’d be interested in a guide on this from me.) In practice, I rarely recommend it for backend services. The build complexity and FFI overhead usually outweigh the benefits compared to “just stand up a Rust service and put it behind a network call.” For libraries and CLI tools, it’s more viable. If you have an API gateway or reverse proxy, you can route specific endpoints to a new Rust service while the rest stays in Go. This works particularly well when one bounded context (auth, search, billing) is the right unit to migrate. The pattern is often called “strangler fig,” because the new service grows around the old one until it eventually replaces it entirely. Start with a service that has a clear boundary. Don’t pick the most central, most-deployed service in your fleet. Pick the one where the contract with the rest of the system is well-defined and the blast radius is small. Keep the same API contract. If your Go service exposes a REST API, your Rust service should too: same paths, same JSON shapes, same error envelope. The migration is invisible to clients, and you can swap traffic incrementally with a gateway. Don’t translate idioms verbatim. Resist the urge to write Go-flavoured Rust. becomes . Goroutine-per-request becomes only when you actually need it (axum already concurrently handles requests). Interfaces with one method usually become trait bounds on a generic, not . Use the compiler as a pair programmer. Rust’s compiler errors are usually pretty good. Read them slowly. They almost always tell you the right answer. The team members who struggle longest are the ones who fight the compiler instead of treating it as a collaborator. Invest in training early. I’ve seen teams try to do a Rust migration “on the side,” learning as they go. It rarely ends well. It’s a bit like training for a marathon by signing up for the race and then trying to run it without any prior training. You can do it, but it’s going to be painful and you might not finish. Block off real time for learning: a workshop, an online course , paired sessions on real code. The upfront investment pays back many times over once the team is fluent. (Hey, if you want to talk about training options, I’m happy to chat .) Not everything should be migrated. Go is excellent for: A hybrid strategy is fine and common. Many of the teams I work with end up with a polyglot backend: Go for the “boring” services, Rust for the ones where reliability and performance pay back the extra effort. Numbers vary wildly by workload, so take these as rough guidance. Not promises! But here are some ballpark numbers, based on Go-to-Rust migrations I’ve helped with: Honestly, you’re unlikely to get a 10x throughput improvement going from Go to Rust the way you might from Python. What you get is fewer “silly errors” and flatter latency tails, plus the ability to expand into other domains like embedded development or systems programming while still using the same language. That’s often the most surprising side-effect of a migration: there’s a lot of opportunity for code-sharing across teams that previously had to use different stacks. You can use Rust for everything. Going from Go to Rust is a different kind of migration than coming from Python or TypeScript . Coming from Go, you know the benefits of a statically-typed, compiled language. So you’re not trading away dynamic typing or a slow runtime, you’re trading away in exchange for a more robust codebase with fewer footguns, and a stricter compiler that catches more mistakes at compile time. There is a steeper learning curve, however. For foundational services (services that your organization relies on, that have high uptime requirements, that are critical to your business), that trade is obviously worth it. For others, Go remains the right answer. The point of a migration is to put each problem in the language that solves it best. Ready to Make the Move to Rust? I help backend teams evaluate, plan, and execute Go-to-Rust migrations. Whether you need an architecture review, training, or hands-on help porting a critical service, let’s talk about your needs . Rust’s type system doesn’t catch all data races, but types that truly can’t be shared between threads without synchronization won’t compile. You can still have logic bugs in your synchronization, but you won’t have the kind of “oh no, I forgot to lock this” that often leads to silent data corruption. ↩ Where Go and Rust overlap, and where they diverge. How Go patterns map to Rust. What you gain from the borrow checker. Where I tell people to keep Go and where Rust is worth the migration cost. How to migrate Go services incrementally. The boilerplate dilutes the actual logic of your function. Wrapping with is a discipline rule, not a compiler rule. It’s easy to drop context on the floor. Sentinel errors via / work, but the compiler doesn’t tell you when you forgot to handle a new variant. Rust async functions return s. They don’t run until awaited or spawned. The compiler tracks / across points. If you hold a non- value across an await, you get a compile error explaining exactly why. There’s no built-in goroutine-style preemption. Long CPU-bound work in an async task starves the executor; you offload to or instead. Channels ( , , ) are first-class but live in libraries, not the language. , owned, heap-allocated, growable. Equivalent to you intend to mutate. , a borrowed view into someone else’s string data. Equivalent to a Go parameter most of the time. Supertraits / constraint hierarchies. In Rust you write , and any automatically satisfies and . Go has no equivalent; you stack interface embeddings, but the constraint solver doesn’t reason about hierarchies the way Rust’s trait system does. Associated types. Rust’s has , so is a first-class thing you can name in bounds. Go’s closest equivalent is a second type parameter, which leaks into every signature. Blanket impls. In Rust, automatically gives every type a method. Go has no way to add methods to a type from outside its defining package, generic or not. Methods with their own type parameters. This is an explicit, documented non-feature in Go. You cannot write . In Rust, generic methods on generic types are routine. Long-lived references. In Go, you’d happily hold a from a map for as long as you want. In Rust, that borrow blocks mutation of the map for its whole lifetime. The fix is usually to clone, or to scope the borrow tighter. Self-referential structs. Common in Go (a struct holding both data and an iterator over it). In Rust, this requires , , or a redesign. Almost always: redesign. Sharing mutable state across goroutines. What you’d write as becomes . Slightly more verbose, much more checked. Returning references from functions. Lifetime annotations show up. They’re not as bad as their reputation, but they’re new. If a value got moved from one place to another, what would happen if the original place tried to use it again? If a value is shared across threads, what would happen if one thread modified it while another thread is using it? If a pointer is dereferenced , what would happen if it was null or dangling? When a value goes out of scope , what would happen if it was still being used somewhere else? Kubernetes-native tooling : operators, controllers, CRDs. The ecosystem is overwhelmingly in Go. CLI utilities and dev tooling : fast compiles, easy cross-compilation, simple deployment. Glue services : thin API layers, proxies, format converters. The boilerplate ratio in Rust isn’t worth it here. Anywhere your team velocity matters more than absolute correctness guarantees . CPU usage: 20–60% reduction. Less dramatic than Python-to-Rust, because Go is already efficient. The wins come from no GC and tighter loops. Memory: 30–50% reduction, mostly from the absence of GC overhead and a smaller runtime. P99 latency: significantly more consistent. Rust services tend to flatline where Go services have visible GC-induced jitter. (This has gotten much better on the Go-side ever since they introduced their low-latency GC, but the difference is still there under heavy load.) Production incidents: this is the one teams report most enthusiastically. The classes of bugs that survive and reach production (data races, nil dereferences, missed error paths) just don’t compile in Rust. Oncall rotations are typically very boring after a Rust migration. Rust’s type system doesn’t catch all data races, but types that truly can’t be shared between threads without synchronization won’t compile. You can still have logic bugs in your synchronization, but you won’t have the kind of “oh no, I forgot to lock this” that often leads to silent data corruption. ↩

0 views
Neil Madden 2 months ago

Java sealed classes and exhaustive pattern matching

Java 17 introduced sealed classes , which allow you to explicitly list the allowed sub-types of an interface or base class. For example, here’s a toy example using a sealed interface and records (inner classes are implicitly added to the permitted sub-types if an explicit list is not given): If you are familiar with functional programming languages with algebraic datatypes, you can view this as similar to a datatype declaration in Haskell or ML: We can then use this in a simple Main class: OK, not so exciting. But one thing to note here is that we didn’t have to add a clause to the switch expression in our main method. This is because sealed classes (and enums) enable exhaustiveness checking : the compiler knows exactly what the possible cases are, and so can check if you have covered them all. If you have, then you don’t need a clause. If you forget one (and don’t have a default clause), then you get a compile-time error. This is great when you want to ensure that all uses of some type do cover all of the cases, but it does introduce a new type of breaking change: adding a new sub-type to a sealed class/interface may break consumers of that code. For example, adding a new case to our example will cause the main method to fail to compile due to the missing case. So if you export a sealed type in your API then adding a new subtype is a breaking change that would require a major version bump (if you’re following SemVer). Although Java will produce a compile-time error for a non-exhaustive switch when you compile the consumer (main in this case), it cannot do so if the consumer is not recompiled when the sealed type changes. For example, suppose that we extend our SealedType with another case: If we just recompiled SealedType.java and don’t recompile Main, then we end up with a runtime exception if we trigger the new case: Here we have the new MatchException being thrown. The Javadoc notes this potential issue with separate compilation, and also some corner-cases with nulls in patterns. So even if you were hoping that using sealed classes would statically ensure that you update all consumers when a new case is added, this is not the case unless you recompile everything. I think for me the conclusion is that sealed types are probably most useful within the implementation of a component, and are less useful when exposed in the public API that a component offers to other components (eg a library). For internal use, where you typically are going to recompile everything together, you get the nice properties of exhaustiveness checking and higher compile-time safety guarantees. But when used across module boundaries, you may just be introducing new ways to break code, often only detectable at runtime. (I discovered these subtleties when reviewing the preview support for PEM-encoded cryptographic objects , which makes exactly this mistake of baking a sealed interface into a public API and recommend clients to pattern match against that type. A predict a very high chance of breakage if they ever want to add a new case).

0 views
(think) 4 months ago

Learning OCaml: String Interpolation

Most programming languages I’ve used have some form of string interpolation. Ruby has , Python has f-strings, JavaScript has template literals, even Haskell has a few popular interpolation libraries. It’s one of those small conveniences you don’t think about until it’s gone. OCaml doesn’t have built-in string interpolation. And here’s the funny thing – I didn’t even notice when I was first learning the language. Looking back at my first impressions article, I complained about the comment syntax, the semicolons in lists, the lack of list comprehensions, and a dozen other things – but never once about string interpolation. I was happily concatenating strings with and using without giving it a second thought. I only started thinking about this while working on my PPX article and going through the catalog of popular PPX libraries. That’s when I stumbled upon and thought “wait, why doesn’t OCaml have interpolation?” The short answer: OCaml has no way to generically convert a value to a string. There’s no universal method, no typeclass, no runtime reflection that would let the language figure out how to stringify an arbitrary expression inside a string literal. In Ruby, every object responds to . In Python, everything has . These languages can interpolate anything because there’s always a fallback conversion available at runtime. OCaml’s type information is erased at compile time, so the compiler would need to know at compile time which conversion function to call for each interpolated expression – and the language has no mechanism for that. 1 OCaml does have , which is actually quite nice and type-safe: The format string is statically checked by the compiler – if you pass an where expects a string, you get a compile-time error, not a runtime crash. That’s genuinely better than what most dynamically typed languages offer. But it’s not interpolation – the values aren’t inline in the string, and for complex expressions it gets unwieldy fast. There’s also plain string concatenation with : This works, but it’s ugly and error-prone for anything beyond trivial cases. ppx_string is a Jane Street PPX that adds string interpolation to OCaml at compile time. The basic usage is straightforward: For non-string types, you specify the module whose function should be used: The suffix tells the PPX to call on , and calls on . Note that , , etc. are conventions from Jane Street’s / libraries – OCaml’s uses , and so on, which won’t work with the syntax. This is another reason really only makes sense within the Jane Street ecosystem. Any module that exposes a function works here – including your own: You can also use arbitrary expressions inside the interpolation braces: Though at that point you might be better off with a binding or for readability. A few practical things worth knowing: Honestly? Probably not as much as you think. I’ve been writing OCaml for a while now without it, and it rarely bothers me. Here’s why: That said, when you do need to build a lot of human-readable strings – error messages, log output, CLI formatting – interpolation is genuinely nicer than . If you’re in the Jane Street ecosystem, there’s no reason not to use . The lack of string interpolation in OCaml is one of those things that sounds worse than it actually is. In practice, and cover the vast majority of use cases, and the code you write with them is arguably clearer about types than magical interpolation would be. It’s also a nice example of OCaml’s general philosophy: keep the language core small, provide solid primitives ( , ), and let the PPX ecosystem fill in the syntactic sugar for those who want it. The same pattern plays out with for printing, for monadic syntax, and many other conveniences. Will OCaml ever get built-in string interpolation? Maybe. There have been discussions on the forums over the years, and the language did absorb binding operators ( , ) from the PPX world. But I wouldn’t hold my breath – and honestly, I’m not sure I’d even notice if it landed. That’s all I have for you today. Keep hacking! This is the same fundamental problem that makes printing data structures harder than in dynamically typed languages.  ↩︎ You need the stanza in your dune file: String values interpolate directly, everything else needs a conversion suffix. Unlike Ruby where is called implicitly, requires you to be explicit about non-string types. This is annoying at first, but it’s consistent with OCaml’s philosophy of being explicit about types. It’s a Jane Street library. If you’re already in the Jane Street ecosystem ( , , etc.), adding is trivial. If you’re not, pulling in a Jane Street dependency just for string interpolation might feel heavy. In that case, is honestly fine. It doesn’t work with the module. If you’re building strings for pretty-printing, you’ll still want or . is for building plain strings, not format strings. Nested interpolation doesn’t work – you can’t nest inside another . Keep it simple. is good. It’s type-safe, it’s concise enough for most cases, and it’s available everywhere without extra dependencies. Most string building in OCaml happens through . If you’re writing pretty-printers (which you will be, thanks to ), you’re using , not string concatenation or interpolation. OCaml code tends to be more compute-heavy than string-heavy. Compared to, say, a Rails app or a shell script, the typical OCaml program just doesn’t build that many ad-hoc strings. This is the same fundamental problem that makes printing data structures harder than in dynamically typed languages.  ↩︎

0 views
マリウス 4 months ago

Hold on to Your Hardware

Tl;dr at the end. For the better part of two decades, consumers lived in a golden age of tech. Memory got cheaper, storage increased in capacity and hardware got faster and absurdly affordable. Upgrades were routine, almost casual. If you needed more RAM, a bigger SSD, or a faster CPU or GPU, you barely had to wait a week for a discount offer and you moved on with your life. This era is ending. What’s forming now isn’t just another pricing cycle or a short-term shortage, it is a structural shift in the hardware industry that paints a deeply grim outlook for consumers. Today, I am urging you to hold on to your hardware, as you may not be able to replace it affordably in the future. While I have always been a stark critic of today’s consumer industry , as well as the ideas behind it , and a strong proponent of buying it for life (meaning, investing into durable, repairable, quality products) the industry’s shift has nothing to do with the protection of valuable resources or the environment, but is instead a move towards a trajectory that has the potential to erode technological self-sufficiency and independence for people all over the world. In recent months the buzzword RAM-pocalypse has started popping up across tech journalism and enthusiast circles. It’s an intentionally dramatic term that describes the sharp increase in RAM prices, primarily driven by high demand from data centers and “AI” technology, which most people had considered a mere blip in the market. This presumed temporary blip , however, turned out to be a lot more than just that, with one manufacturer after the other openly stating that prices will continue to rise, with suppliers forecasting shortages of specific components that could last well beyond 2028, and with key players like Western Digital and Micron either completely disregarding or even exiting the consumer market altogether. Note: Micron wasn’t just another supplier , but one of the three major players directly serving consumers with reasonably priced, widely available RAM and SSDs. Its departure leaves the consumer memory market effectively in the hands of only two companies: Samsung and SK Hynix . This duopoly certainly doesn’t compete on your wallet’s behalf, and it definitely wouldn’t be the first time it would optimize for margins . The RAM-pocalypse isn’t just a temporary headline anymore, but has seemingly become long-term reality. However, RAM and memory in general is only the beginning. The main reason for the shortages and hence the increased prices is data center demand, specifically from “AI” companies. These data centers require mind-boggling amounts of hardware, specifically RAM, storage drives and GPUs, which in turn are RAM-heavy graphics units for “AI” workloads. The enterprise demand for specific components simply outpaces the current global production capacity, and outbids the comparatively poor consumer market. For example, OpenAI ’s Stargate project alone reportedly requires approximately 900,000 DRAM wafers per month , which could account for roughly 40% of current global DRAM output. Other big tech giants including Google , Amazon , Microsoft , and Meta have placed open-ended orders with memory suppliers, accepting as much supply as available. The existing and future data centers for/of these companies are expected to consume 70% of all memory chips produced in 2026. However, memory is just the first domino. RAM and SSDs are where the pain is most visible today, but rest assured that the same forces are quietly reshaping all aspects of consumer hardware. One of the most immediate and tangible consequences of this broader supply-chain realignment are sharp, cascading price hikes across consumer electronics, with LPDDR memory standing out as an early pressure point that most consumers didn’t recognize until it was already unavoidable. LPDDR is used in smartphones, laptops, tablets, handheld consoles, routers, and increasingly even low-power PCs. It sits at the intersection of consumer demand and enterprise prioritization, making it uniquely vulnerable when manufacturers reallocate capacity toward “AI” accelerators, servers, and data-center-grade memory, where margins are higher and contracts are long-term. As fabs shift production toward HBM and server DRAM , as well as GPU wafers, consumer hardware production quietly becomes non-essential , tightening supply just as devices become more power- and memory-hungry, all while continuing on their path to remain frustratingly unserviceable and un-upgradable. The result is a ripple effect, in which device makers pay more for chips and memory and pass those costs on through higher retail prices, cut base configurations to preserve margins, or lock features behind premium tiers. At the same time, consumers lose the ability to compensate by upgrading later, because most components these days, like LPDDR , are soldered down by design. This is further amplified by scarcity, as even modest supply disruptions can spike prices disproportionately in a market where just a few suppliers dominate, turning what should be incremental cost increases into sudden jumps that affect entire product categories at once. In practice, this means that phones, ultrabooks, and embedded devices are becoming more expensive overnight, not because of new features, but because the invisible silicon inside them has quietly become a contested resource in a world that no longer builds hardware primarily for consumers. In late January 2026, the Western Digital CEO confirmed during an earnings call that the company’s entire HDD production capacity for calendar year 2026 is already sold out. Let that sink in for a moment. Q1 hasn’t even ended and a major hard drive manufacturer has zero remaining capacity for the year. Firm purchase orders are in place with its top customers, and long-term agreements already extend into 2027 and 2028. Consumer revenue now accounts for just 5% of Western Digital ’s total sales, while cloud and enterprise clients make up 89%. The company has, for all practical purposes, stopped being a consumer storage company. And Western Digital is not alone. Kioxia , one of the world’s largest NAND flash manufacturers, admitted that its entire 2026 production volume is already in a “sold out” state , with the company expecting tight supply to persist through at least 2027 and long-term customers facing 30% or higher year-on-year price increases. Adding to this, the Silicon Motion CEO put it bluntly during a recent earnings call : We’re facing what has never happened before: HDD, DRAM, HBM, NAND… all in severe shortage in 2026. In addition, the Phison CEO has gone even further, warning that the NAND shortage could persist until 2030, and that it risks the “destruction” of entire segments of the consumer electronics industry. He also noted that factories are now demanding prepayment for capacity three years in advance , an unprecedented practice that effectively locks out smaller players. The collateral damage of this can already be felt, and it’s significant. For example Valve confirmed that the Steam Deck OLED is now out of stock intermittently in multiple regions “due to memory and storage shortages” . All models are currently unavailable in the US and Canada, the cheaper LCD model has been discontinued entirely, and there is no timeline for when supply will return to normal. Valve has also been forced to delay the pricing and launch details for its upcoming Steam Machine console and Steam Frame VR headset, directly citing memory and storage shortages. At the same time, Sony is considering delaying the PlayStation 6 to 2028 or even 2029, and Nintendo is reportedly contemplating a price increase for the Switch 2 , less than a year after its launch. Both decisions are seemingly driven by the same memory supply constraints. Meanwhile, Microsoft has already raised prices on the Xbox . Now you might think that everything so far is about GPUs and other gaming-related hardware, but that couldn’t be further from the truth. General computing, like the Raspberry Pi is not immune to any of this either. The Raspberry Pi Foundation has been forced to raise prices twice in three months, with the flagship Raspberry Pi 5 (16GB) jumping from $120 at launch to $205 as of February 2026, a 70% increase driven entirely by LPDDR4 memory costs. What was once a symbol of affordable computing is rapidly being priced out of reach for the educational and hobbyist communities it was designed to serve. HP, on the other hand, seems to have already prepared for the hardware shortage by launching a laptop subscription service where you pay a monthly fee to use a laptop but never own it , no matter how long you subscribe. While HP frames this as a convenience, the timing, right in the middle of a hardware affordability crisis, makes it feel a lot more like a preview of a rented compute future. But more on that in a second. “But we’ve seen price spikes before, due to crypto booms, pandemic shortages, factory floods and fires!” , you might say. And while we did live through those crises, things eventually eased when bubbles popped and markets or supply chains recovered. The current situation, however, doesn’t appear to be going away anytime soon, as it looks like the industry’s priorities have fundamentally changed . These days, the biggest customers are not gamers, creators, PC builders or even crypto miners anymore. Today, it’s hyperscalers . Companies that use hardware for “AI” training clusters, cloud providers, enterprise data centers, as well as governments and defense contractors. Compared to these hyperscalers consumers are small fish in a big pond. These buyers don’t care if RAM costs 20% more and neither do they wait for Black Friday deals. Instead, they sign contracts measured in exabytes and billions of dollars. With such clients lining up, the consumer market in contrast is suddenly an inconvenience for manufacturers. Why settle for smaller margins and deal with higher marketing and support costs, fragmented SKUs, price sensitivity and retail logistics headaches, when you can have behemoths throwing money at you? Why sell a $100 SSD to one consumer, when you can sell a whole rack of enterprise NVMe drives to a data center with circular virtually infinite money? Guaranteed volume, guaranteed profit, zero marketing. The industry has answered these questions loudly. All of this goes to show that the consumer market is not just deprioritized, but instead it is being starved . In fact, IDC has already warned that the PC market could shrink by up to 9% in 2026 due to skyrocketing memory prices, and has described the situation not as a cyclical shortage but as “a potentially permanent, strategic reallocation of the world’s silicon wafer capacity” . Leading PC OEMs including Lenovo , Dell , HP , Acer , and ASUS have all signaled 15-20% PC price increases for 2026, with some models seeing even steeper hikes. Framework , the repairable laptop company, has also been transparent about rising memory costs impacting its pricing. And analyst Jukan Choi recently revised his shortage timeline estimate , noting that DRAM production capacity is expected to grow at just 4.8% annually through 2030, with even that incremental capacity concentrated on HBM rather than consumer memory. TrendForce ’s latest forecast projects DRAM contract prices rising by 90-95% quarter over quarter in Q1 2026. And that is not a typo. The price of hardware is one thing, but value-for-money is another aspect that appears to be only getting worse from here on. Already today consumer parts feel like cut-down versions of enterprise silicon. As “AI” accelerators and server chips dominate R&D budgets, consumer improvements will slow even further, or arrive at higher prices justified as premium features . This is true for CPUs and GPUs, and it will be equally true for motherboards, chipsets, power supplies, networking, etc. We will likely see fewer low-end options, more segmentation, artificial feature gating and generally higher baseline prices that, once established, won’t be coming back down again. As enterprise standards become the priority, consumer gear is becoming an afterthought that is being rebadged, overpriced, and poorly supported. The uncomfortable truth is that the consumer hardware market is no longer the center of gravity, as we all were able to see at this year’s CES . It’s orbiting something much larger, and none of this is accidental. The industry isn’t failing, it’s succeeding, just not for you . And to be fair, from a corporate standpoint, this pivot makes perfect sense. “AI” and enterprise customers are rewriting revenue charts, all while consumers continue to be noisy, demanding, and comparatively poor. It is pretty clear that consumer hardware is becoming a second-class citizen, which means that the machines we already own are more valuable than we might be thinking right now. “But what does the industry think the future will look like if nobody can afford new hardware?” , you might be asking. There is a darker, conspiratorial interpretation of today’s hardware trends that reads less like market economics and more like a rehearsal for a managed future. Businesses, having discovered that ownership is inefficient and obedience is profitable, are quietly steering society toward a world where no one owns compute at all, where hardware exists only as an abstraction rented back to the public through virtual servers, SaaS subscriptions, and metered experiences , and where digital sovereignty, that anyone with a PC tower under their desk once had, becomes an outdated, eccentric, and even suspicious concept. … a morning in said future, where an ordinary citizen wakes up, taps their terminal, which is a sealed device without ports, storage, and sophisticated local execution capabilities, and logs into their Personal Compute Allocation . This bundle of cloud CPU minutes, RAM credits, and storage tokens leased from a conglomerate whose logo has quietly replaced the word “computer” in everyday speech, just like “to search” has made way for “to google” , has removed the concept of installing software, because software no longer exists as a thing , but only as a service tier in which every task routes through servers owned by entities. Entities that insist that this is all for the planet . Entities that outlawed consumer hardware years ago under the banner of environmental protectionism , citing e-waste statistics, carbon budgets , and unsafe unregulated silicon , while conveniently ignoring that the data centers humming beyond the city limits burn more power in an hour than the old neighborhood ever did in a decade. In this world, the ordinary citizen remembers their parents’ dusty Personal Computer , locked away in a storage unit like contraband. A machine that once ran freely, offline if it wanted, immune to arbitrary account suspensions and pricing changes. As they go about their day, paying a micro-fee to open a document, losing access to their own photos because a subscription lapsed, watching a warning banner appear when they type something that violates the ever evolving terms-of-service, and shouting “McDonald’s!” to skip the otherwise unskippable ads within every other app they open, they begin to understand that the true crime of consumer hardware wasn’t primarily pollution but independence. They realize that owning a machine meant owning the means of computation , and that by centralizing hardware under the guise of efficiency, safety, and sustainability, society traded resilience for convenience and autonomy for comfort. In this dyst… utopia , nothing ever breaks because nothing is yours , nothing is repairable because nothing is physical, and nothing is private because everything runs somewhere else , on someone else’s computer . The quiet moral, felt when the network briefly stutters and the world freezes, is that keeping old hardware alive was never nostalgia or paranoia, but a small, stubborn act of digital self-defense; A refusal to accept that the future must be rented, permissioned, and revocable at any moment. If you think that dystopian “rented compute over owned hardware” future could never happen, think again . In fact, you’re already likely renting rather than owning in many different areas. Your means of communication are run by Meta , your music is provided by Spotify , your movies are streamed from Netflix , your data is stored in Google ’s data centers and your office suite runs on Microsoft ’s cloud. Maybe even your car is leased instead of owned, and you pay a monthly premium for seat heating or sElF-dRiViNg , whatever that means. After all, the average Gen Z and Millennial US consumer today apparently has 8.2 subscriptions , not including their DaIlY aVoCaDo ToAsTs and StArBuCkS cHoCoLate ChIp LaTtEs that the same Boomers responsible for the current (and past) economic crises love to dunk on. Besides, look no further than what’s already happening in for example China, a country that manufactures massive amounts of the world’s sought-after hardware yet faces restrictions on buying that very hardware. In recent years, a complex web of export controls and chip bans has put a spotlight on how hardware can become a geopolitical bargaining chip rather than a consumer good. For example, export controls imposed by the United States in recent years barred Nvidia from selling many of its high-performance GPUs into China without special licenses, significantly reducing legal access to cutting-edge compute inside the country. Meanwhile, enforcement efforts have repeatedly busted smuggling operations moving prohibited Nvidia chips into Chinese territory through Southeast Asian hubs, with over $1 billion worth of banned GPUs reportedly moving through gray markets, even as official channels remain restricted. Coverage by outlets such as Bloomberg , as well as actual investigative journalism like Gamer’s Nexus has documented these black-market flows and the lengths to which both sides go to enforce or evade restrictions, including smuggling networks and increased regulatory scrutiny. On top of this, Chinese regulators have at times restricted domestic tech firms from buying specific Nvidia models, further underscoring how government policy can override basic market access for hardware, even in the country where much of that hardware is manufactured. While some of these export rules have seen partial reversals or regulatory shifts, the overall situation highlights a world in which hardware access is increasingly determined by politics, security regimes, and corporate strategy, and not by consumer demand . This should serve as a cautionary tale for anyone who thinks owning their own machines won’t matter in the years to come. In an ironic twist, however, one of the few potential sources of relief may, in fact, come from China. Two Chinese manufacturers, CXMT ( ChangXin Memory Technologies ) and YMTC ( Yangtze Memory Technologies ), are embarking on their most aggressive capacity expansions ever , viewing the global shortage as a golden opportunity to close the gap with the incumbent big three ( Samsung , SK Hynix , Micron ). CXMT is now the world’s fourth-largest DRAM maker by production volume, holding roughly 10-11% of global wafer capacity, and is building a massive new DRAM facility in Shanghai expected to be two to three times larger than its existing Hefei headquarters, with volume production targeted for 2027. The company is also preparing a $4.2 billion IPO on Shanghai’s STAR Market to fund further expansion and has reportedly delivered HBM3 samples to domestic customers including Huawei . YMTC , traditionally a NAND flash supplier, is constructing a third fab in Wuhan with roughly half of its capacity dedicated to DRAM, and has reached 270-layer 3D NAND capability, rapidly narrowing the gap with Samsung (286 layers) and SK Hynix (321 layers). Its NAND market share by shipments reached 13% in Q3 2025, close to Micron ’s 14%. What’s particularly notable is that major PC manufacturers are already turning to these suppliers . However, as mentioned before, with hardware having become a geopolitical topic, both companies face ongoing (US-imposed) restrictions. Hence, for example HP has indicated it would only use CXMT chips in devices for non-US markets. Nevertheless, for consumers worldwide the emergence of viable fourth and fifth players in the memory market represents the most tangible hope of eventually breaking the current supply stranglehold. Whether that relief arrives in time to prevent lasting damage to the consumer hardware ecosystem remains an open question, though. Polymarket bet prediction : A non-zero percentage of people will confuse Yangtze Memory Technologies with the Haskell programming language . The reason I’m writing all of this isn’t to create panic, but to help put things into perspective. You don’t need to scavenger-hunt for legacy parts in your local landfill (yet) or swear off upgrades forever, but you do need to recognize that the rules have changed . The market that once catered to enthusiasts and everyday users is turning its back. So take care of your hardware, stretch its lifespan, upgrade thoughtfully, and don’t assume replacement will always be easy or affordable. That PC, laptop, NAS, or home server isn’t disposable anymore. Clean it, maintain it, repaste it, replace fans and protect it, as it may need to last far longer than you originally planned. Also, realize that the best time to upgrade your hardware was yesterday and that the second best time is now . If you can afford sensible upgrades, especially RAM and SSD capacity, it may be worth doing sooner rather than later. Not for performance, but for insurance, because the next time something fails, it might be unaffordable to replace, as the era of casual upgrades seems to be over. Five-year systems may become eight- or ten-year systems. Software bloat will hurt more and will require re-thinking . Efficiency will matter again . And looking at it from a different angle, maybe that’s a good thing. Additionally, the assumption that prices will normalize again at some point is most likely a pipe dream. The old logic wait a year and it’ll be cheaper no longer applies when manufacturers are deliberately constraining supply. If you need a new device, buy it; If you don’t, however, there is absolutely no need to spend money on the minor yearly refresh cycle any longer, as the returns will be increasingly diminishing. And again, looking at it from a different angle, probably that is also a good thing. Consumer hardware is heading toward a bleak future where owning powerful, affordable machines becomes harder or maybe even impossible, as manufacturers abandon everyday users to chase vastly more profitable data centers, “AI” firms, and enterprise clients. RAM and SSD price spikes, Micron ’s exit from the consumer market, and the resulting Samsung / SK Hynix duopoly are early warning signs of a broader shift that will eventually affect CPUs, GPUs, and the entire PC ecosystem. With large manufacturers having sold out their entire production capacity to hyperscalers for the rest of the year while simultaneously cutting consumer production by double-digit percentages, consumers will have to take a back seat. Already today consumer hardware is overpriced, out of stock or even intentionally being delayed due to supply issues. In addition, manufacturers are pivoting towards consumer hardware subscriptions, where you never own the hardware and in the most dystopian trajectory, consumers might not buy any hardware at all, with the exception of low-end thin-clients that are merely interfaces , and will rent compute through cloud platforms, losing digital sovereignty in exchange for convenience. And despite all of this sounding like science fiction, there is already hard evidence proving that access to hardware can in fact be politically and economically revoked. Therefor I am urging you to maintain and upgrade wisely, and hold on to your existing hardware , because ownership may soon be a luxury rather than the norm.

0 views

Type safe interpreters

It is well known that most software has bugs [Citation needed] . It is also well known that interpreters are software 1 . One issue that one might run into in an interpreter is type safety : It may very well be possible for your typed language's interpreter to nevertheless end up in a state where it is asked to evaluate . What can we do about that? GADTs are a technique for increasing type safety in a program, by "indexing" a constructor by a type. One of the canonical examples for this is an -like. Imagine we wanted a type-safe way to ensure that in some cases, we could always extract the value inside. One way of doing this is to add an extra type parameter, and use that to mark whether something is inside. We will use OCaml for this demonstration. Note that we have used a different syntax than usual. Normally, we put a type parameter in the constructor, like , and then use that throughout ( ). However, as we are changing that type in the "return" of the constructor, we need a syntax that allows us to change that. marks a type parameter we "don't need to name" (as we always specify it), and in this case, we always specify both. Then, we add our elements before a , mimicking a function. The general form of this in OCaml is . Now, if we have something of type , we know it contains a value! The only other way a can be formed is via , but that gives it type , so it'd be type-incorrect. This means we can write a function like and have it be total; there is no missing case, because the missing case is a type error. Note that when writing a function like , we need to use this interesting piece of syntax: This is as otherwise OCaml eagerly thinks "Ah, must be !" (or equivalent for ) when seeing the case in the pattern match. The designator tells it to keep as general as possible, instead of refining it. How does this allow us to get a more type-safe interpreter, though? Well, let's start by introducing our expression type: We've added space for a type parameter. What should integers and booleans look like? Maybe they should be indexed by their respective "meta" types. Now, we want to add a case for and . Naturally, we shouldn't be able to add two booleans, so let's restrict it to only taking in s. Similar for negate. We've already added type safety! It's impossible to write , because expects a , but is a . Let's keep going: (or ) should take two integers and return a boolean, and should take a boolean as its first argument, but anything for its second and third. Hence note that we can still use generic parameters - we just need to think about when it makes sense to do so, to get the type safety we want. Now for functions. What should a function look like here? One way of implementing them is with a "Higher-order abstract syntax"(HOAS) 3 approach, where we use the functions of the host language to make functions in the interpreted language. In that case, we should take a function as the argument to our constructor, but when what is our result type? That function type! We'll need to know it later to safely write , so we "store" it in the type now. We also want the function to take and return an , so we can do constructions like . Note that the function is not an at first, as otherwise we would have no way to construct it in the first place. (Remember, this is how we make functions.) Then . It should take in a function, and a value, and then return the function applied to the value. This hence translates as: As a finale, we'll add pairs and projections. I won't elaborate on these, hoping that it's becoming obvious how they work. Now let's look at some examples and their types. We have that a construction like is not just an error, but a type error ! This means it's caught at compile time! From here, the evaluator itself is very simple. We just write the interpretation of our language, as usual: The and cases are interesting. In the former, we need to return a function of type . We can start by introducing a function , but we have , so we just apply it. In the latter, we need to to get a function from , which is of type . We can then pass it , which is of type to get a , which we must then evaluate again to get a . Now we can run the above examples. Remember, all of the above is completely type safe! We have succesfully constructed an interpreter that can never type error. In short, it can be hard. One way is to have a "base" language that's parsed, and then have your typechecker produce a representation like the above that you then know is type correct. However, this does prevent typechecker bugs from sneaking through, which was our entire goal! To some extent, this is kicking the bucket down the road - you are now relying that your "host language"'s typechecker is correct. However, this is a numbers game; if you're writing in OCaml or Haskell or similar, the chances of that are very very high unless you're using extremely weird features. The astute may have noted that this is essentially a version of denotional semantics. We're interpreting into the type-safe domain of the host language to ensure that the types always line up (as they must, for the interpretation to succeed, and the typechecker of the host language ensures that). No, I won't do the same joke twice. Most of the time. ↩ I am not going into what "ADT" stands for, as it's a whole nother debate. ↩ Higher-order abstract syntax. A bit too in-depth to explore in full right now, but worth exploring. ↩ No, I won't do the same joke twice. Most of the time. ↩ I am not going into what "ADT" stands for, as it's a whole nother debate. ↩ Higher-order abstract syntax. A bit too in-depth to explore in full right now, but worth exploring. ↩

0 views
Abhinav Sarkar 6 months ago

Implementing Co, a Small Language With Coroutines #5: Adding Sleep

In the previous post , we added channels to Co , the small language we are implementing in this series of posts. In this post, we add the primitive to it, enabling time-based coroutine scheduling. We then use sleep to build a simulation of digital logic circuits. This post was originally published on abhinavsarkar.net . This post is a part of the series: Implementing Co, a Small Language With Coroutines . Sleep is a commonly used operation in concurrent programs. It pauses the execution of the current Thread of Computation (ToC) for a specified duration, after which the ToC is resumed automatically. Sleep is used for various purposes: polling for events, delaying execution of an operation, simulating latency, implementing timeouts, and more. Sleep is generally implemented as a primitive operation in most languages, delegating the actual implementation to the underlying operating system. The operating system’s scheduler removes the ToC from the list of runnable ToCs , places it in a list of sleeping ToCs , and after the specified duration, moves it back to the list of runnable ToCs for scheduling. Since Co implements its own ToC (coroutine) scheduler, we implement sleep as a primitive operation within the interpreter itself 1 . We start by exposing and as built-in functions to Co : The built-in function takes one argument—the duration in milliseconds to sleep for. The function returns the current time in milliseconds since the Unix epoch . Both of them delegate to the functions explained next. The function evaluates its argument to a number, checks that it is non-negative, and then calls the function in the monad. calls and returns the milliseconds wrapped as a . The implementation of sleep is more involved than other built-in functions because it interacts with the coroutine scheduler. When a coroutine calls , we want to suspend the coroutine, and schedule it to be resumed after the specified duration. There may be multiple coroutines in the sleep state at a time, and they must be resumed according to their wakeup time (time at which sleep was called + sleep duration), and not in any other order. To be efficient, it is also important that the scheduler does not poll repeatedly for new coroutines to wake up and run, but instead waits till the right time. These are the two requirements for our coroutine scheduler. And the solution is: delayed coroutines. The coroutines we have implemented so far were scheduled to run immediately. To implement sleep, we extend the coroutine concept with Delayed Coroutines —coroutines that are scheduled to run at a specific future time. Now the data type holds an to signal when the coroutine is ready to be run. The old-style coroutines that run immediately are created ready to run by the function. But delayed coroutines are different: The key difference from a regular coroutine is that the used for signaling is created empty. We fork a thread 2 that sleeps 3 for the specified sleep duration, and then signals that the coroutine is ready to run by filling the . An is a synchronization primitive 4 —essentially a mutable box that can hold a value or be empty. When we call on an empty , it blocks until another thread fills it. This is what makes it powerful for our use case: instead of the interpreter repeatedly polling the queue asking “is this coroutine ready yet?”, we let the interpreter wait on the . The forked thread signals readiness at the right time by filling the . The interpreter wakes up immediately—no wasted CPU cycles, no busy-waiting. We already have a of coroutines in our . It is a min-priority queue sorted by timestamps, which we have been using as a FIFO queue till now. Now we use it for its real purpose: storing delayed coroutines sorted by their wakeup times. The queue also tracks the maximum wakeup time of all coroutines in the queue. This information is useful for calculating how long the interpreter should sleep before termination. The core operations on the queue are: We saw the function earlier : The function enqueues the given value at the given time in the queue. The function enqueues the value at the current time, thus scheduling it to run immediately. The function dequeues the value with the lowest priority from the queue, which in this case, is the value that is enqueued first. The function returns the monotonically increasing current system time. The function dequeues the coroutine with lowest priority, so if we use the wakeup time as priority, it will dequeue the coroutine that is to be run next. That works! The function calculates and tracks the maximum wakeup times of the coroutines as well. Next, we implement the scheduling of delayed coroutines: The function enqueues a coroutine in the interpreter coroutine queue with the specified wakeup time. We also improve the function to wait for the coroutine to be ready before running it. The function call blocks till the thread that was forked when creating the coroutine wakes up and fills the . So we don’t have to poll the queue. That’s all we have to do for having delayed coroutines. With the infrastructure in place, the function becomes straightforward: When a coroutine calls , we capture the current environment and use to capture the continuation—the code that should run after the sleep completes. We then create a new delayed coroutine with this continuation, schedule it for the future, and run the next coroutine in the queue. The scheduler machinery takes care of running the delayed coroutine at the right time. We also modify the function from the previous post to handle delayed coroutines. It now sleeps till the last wakeup time before checking if the queue is empty: Notice how we use the function we just defined in . The function calculates how long to sleep before the last coroutine becomes ready: That’s all for sleeping. This may be too much to take in, so let’s go through some examples. Sleep can be used for polling/waiting for events, delaying execution, simulating latency, implementing timeouts, and more. Let’s see some simple uses. An interesting example of sleep is the infamous sleep sort , which sorts a list of numbers by spawning a coroutine for each number that sleeps for the duration of that number, then prints it: Running this program prints what we expect: Don’t use for sorting your numbers though. Moving on. With sleep, we can implement JavaScript-like and functions: The function spawns a coroutine that sleeps for the specified duration and then calls the callback function. The function repeatedly calls a callback at a fixed interval using to reschedule itself. Running the above code prints alternating and every 1 second, forever: Notice that the scheduling is not accurate up to milliseconds, but only approximate. As a more complex example of using sleep, we implement a simulator for digital logic circuits, from basic Logic gates to a Ripple carry adder . The idea is to model circuits as a network of wires and gates, where the wires carry digital signal values ( or ), and the logic gates transform input signals to output signals with a propagation delay. The digital circuit simulation example is from the Wizard Book . Quoting an example: An inverter is a primitive function box [logic gate] that inverts its input. If the input signal to an inverter changes to 0, then one inverter-delay later the inverter will change its output signal to 1. If the input signal to an inverter changes to 1, then one inverter-delay later the inverter will change its output signal to 0. But first, we’ll need to make some lists. We implement a simple cons list (a singly linked list) using a trick from the book itself : creates an empty list, and we grow the list by prepending an element to it by calling the function. returns the first element of a list, and returns the rest of them. Notice that a cell is just a closure that holds references to its first and rest parameters, and returns a selector function to retrieve them. Next, we define a helper function to call a list of actions, yielding after each one: A wire holds a mutable signal value and a list of actions to call when the signal changes: A wire provides three operations: The function connects two wires, causing the signal from one to propagate to another. First, we define the basic logic operations: And a utility function to schedule a function to run after a delay: With these building blocks, we define the logic gates. Each gate computes its output based on its inputs and schedules the output update after a propagation delay specific to the gate: We add the action to each input wire, which runs when the input signals change, and sets the signal on the output wire after a delay. Let’s test an And gate: For probing, we define a helper that logs signal changes with milliseconds elapsed since start of the run: The output: It works as expected. You can notice the sleep and the And gate delay in action. Using the basic logic gates, next we build adders. A Half adder is a digital circuit that adds two bits: It has two input signals/bits and , and two output bits and . We simply connect the And, Or and Not gates with input, output and intermediate wires in our code as shown in the diagram: Nice and simple. Let’s test it: And the output: In binary, . Correct! Notice again how the signal propagation through the gates is delayed. Next up is the full adder. A Full adder adds three bits, two inputs and a carry-in: Notice that a full adder uses two half adders. Again, we follow the diagram and connect the wires: Let’s skip the demo for full adder and jump to something more exciting. A Ripple-carry adder chains together multiple full adders to add multi-bit numbers. The diagram below shows a four-bit adder: We create a ripple-carry adder that can add any number of bits. First we need some helper functions: creates a list of wires to represent an N-bit input/output. sets the bits of a N-bit wire list to a given N-bit value. Now we write a ripple-carry adder: The ripple-carry adder uses one full adder per bit, cascading the carry-out bit of each input bit-pair’s sum to the next pair of bits. To demonstrate, let’s add two 4-bit numbers: This one runs for a while because of the collective delays. Let me pick out the final output: We add and in binary, resulting in , which is correct again. Everything works perfectly. With sleep, we’ve now implemented all major features of Co —a complete concurrent language with first-class coroutines, channels, and time-based scheduling. With the addition of sleep, we’ve completed our implementation of Co —a small language with coroutines and channels. Over these five posts, we went from parsing source code to building a full interpreter that handles cooperative multitasking using coroutines. The key insight was realizing that coroutines are just environments plus continuations. By designing our interpreter to use continuation-passing style, we gained the ability to suspend execution at any point and resume it later. Channels built naturally on top of that, providing a way for coroutines to synchronize and pass messages. And sleep extended the scheduler to handle time-based execution, unlocking patterns like timeouts and periodic tasks. The examples we built along the way—pubsub system, actor system, and digital circuit simulation—show what becomes possible once these primitives are in place. Starting with basic arithmetic and functions, we ended up with a language capable of expressing real concurrent programs. What comes next? Maybe a compiler for Co ? Stay tuned by subscribing to the feed or the email newsletter . The full code for the Co interpreter is available here . If you have any questions or comments, please leave a comment below. If you liked this post, please share it. Thanks for reading! The sleep implementation in Co is not interruptible. That is, if a coroutine is sleeping, it cannot be resumed before the specified duration. This is different from sleep implementations in most programming languages, where the sleep operation can be interrupted by sending a signal to the sleeping ToC. ↩︎ Threads in GHC are Green Threads and are very cheap to create and run. It is perfectly okay to fork a new one for each delayed coroutine. ↩︎ So in a way, we cheat here by using the sleep primitive provided by the GHC runtime to implement our sleep primitive. If we write a compiler for Co , we’ll have to write our own runtime where we’ll have to implement our sleep function using the functionalities provided by the operating systems. ↩︎ To learn more about how s can be used to communicate between threads, read the chapter 24 of Real World Haskell . ↩︎ This post is a part of the series: Implementing Co, a Small Language With Coroutines . If you liked this post, please leave a comment . The Interpreter Adding Coroutines Adding Channels Adding Sleep 👈 Introduction Adding Sleep Delayed Coroutines Queuing Coroutines Implementing Sleep Sleep in Action Sleep Sort JavaScript-like Timeouts and Intervals Bonus Round: Digital Circuit Simulation Conjuring Lists Logic Gates Ripple-carry Adder : returns the current signal value. : sets a new signal value and calls all actions if the value changed. : adds an action to be called when the signal changes, and calls it immediately. The sleep implementation in Co is not interruptible. That is, if a coroutine is sleeping, it cannot be resumed before the specified duration. This is different from sleep implementations in most programming languages, where the sleep operation can be interrupted by sending a signal to the sleeping ToC. ↩︎ Threads in GHC are Green Threads and are very cheap to create and run. It is perfectly okay to fork a new one for each delayed coroutine. ↩︎ So in a way, we cheat here by using the sleep primitive provided by the GHC runtime to implement our sleep primitive. If we write a compiler for Co , we’ll have to write our own runtime where we’ll have to implement our sleep function using the functionalities provided by the operating systems. ↩︎ To learn more about how s can be used to communicate between threads, read the chapter 24 of Real World Haskell . ↩︎ The Interpreter Adding Coroutines Adding Channels Adding Sleep 👈

0 views
seated.ro 6 months ago

glimpses of the future

Glimpse can now build call graphs, showing you exactly how functions relate to each other in your codebase. This works by parsing your code with tree-sitter, extracting function definitions and calls, then resolving those calls to their actual definitions. Sometimes tree-sitter based resolution isn’t enough. Maybe you’re dealing with dynamic dispatch, generics, or just a language with particularly complex module resolution. For this, Glimpse can use LSPs to resolve definitions semantically. This spins up actual LSP servers and uses goto-definition / goto-implementation to resolve calls. It’s slower, but accurate. Glimpse will attempt to auto-install the LSP servers for you. Glimpse eagerly caches whatever it finds into an incremental index. But you can choose to pre-build the index ahead of time for instant queries. The index stores all the definitions, calls, and resolutions so subsequent queries are fast. Glimpse now supports: Go, Rust, C, C++, Python, TypeScript, JavaScript, Zig, Java, Scala, Nix, Lua, Ruby, C#, Kotlin, Swift, and Haskell. Each language has custom tree-sitter queries for extracting definitions, calls, and imports. The grammars are downloaded and compiled automatically on first use.

0 views
Abhinav Sarkar 6 months ago

Polls I Ran on Mastodon in 2025

In 2025, I ran ten polls on Mastodon exploring various topics, mostly to outsource my research to the hivemind. Here are the poll results organized by topic, with commentary. How do you pronounce JSON? January 15, 2025 I’m in the “Jay-Son, O as in Otter” camp, which is the majority response. It seems like most Americans prefer the “Jay-Son, O as in Utter” option. Thankfully, only one person in the whole world says “Jay-Ess-On”. If someone were to write a new compiler book today, what would you prefer the backend to emit? October 31, 2025 LLVM wins this poll hands down. It is interesting to see WASM beating other targets. Which is your favourite Haskell parsing library? November 3, 2025 I didn’t expect Attoparsec to go toe-to-toe with Megaparsec . I did some digging, and it seems like Megaparsec is the clear winner when it comes to parsing programming languages in Haskell. However, for parsing file formats and network protocols, Attoparsec is the most popular one. I think that’s wise, and I’m inclined to make the same choice. If you were to write a compiler in Haskell, would you use a lens library to transform the data structures? July 11, 2025 This one has mixed results. Personally, I’d like to use a minimal lens library if I’m writing a compiler in Haskell. What do you think is the right length of programming related blog posts (containing code) in terms of reading time? May 18, 2025 As a writer of programming related blog posts, this poll was very informative for me. 10 minute long posts seem to be the most popular option, but my own posts are a bit longer, usually between 15–20 minutes. Do you print blog posts or save them as PDFs for offline reading? March 8, 2025 Most people do not seem to care about saving or printing blog posts. But I went ahead and added (decent) printing support for my blog posts anyway. If you have a personal website and you do not work in academia, do you have your résumé or CV on your website? August 30, 2025 I don’t have a public résumé on my website either. I’d like to, but I don’t think anyone visiting my website would read it. Would people be interested in a series of blog posts where I implement the C compiler from “Writing a C Compiler” book by Nora Sandler in Haskell? November 11, 2025 Well, 84% people voted “Yes”, so this is (most certainly) happening in 2026! If I were to release a service to run on servers, how would you prefer I package it? December 30, 2025 Well, people surely love their Docker images. Surprisingly, many are okay with just source code and build instructions. Statically linked executable are more popular now, probably because of the ease of deployment. Many also commented that they’d prefer OS specify package like deb or rpm. However, my personal preference is Nix package and NixOS module. If you run services on Hetzner, do you keep a backup of your data entirely off Hetzner? August 9, 2025 It is definitely wise to have an offsite backup. I’m still figuring out the backup strategy for my VPS. That’s all for this year. Let’s see what polls I come up with in 2026. If you have any questions or comments, please leave a comment below. If you liked this post, please share it. Thanks for reading! This post was originally published on abhinavsarkar.net . If you liked this post, please leave a comment . General Programming JSON Pronunciation Compilers Compiler Backend Targets Haskell Parsing Libraries Compiler in Haskell with Lenses Blogging & Web Blog Post Length Preferences Blog Post Print Support Résumés on Personal Website “Writing a C Compiler” Blog Series Self-hosting Service Packaging Preferences Hetzner Backup Strategy

0 views
matklad 6 months ago

Newtype Index Pattern In Zig

In efficiency-minded code, it is idiomatic to use indexes rather than pointers. Indexes have several advantages: First , they save memory. Typically a 32-bit index is enough, a saving of four bytes per pointer on 64-bit architectures. I haven’t seen this measured, but my gut feeling is that this is much more impactful than it might initially seem. On modern architectures, saving memory saves time (and energy) as well, because the computing bottleneck is often the bit pipe between the memory and the CPU, not the computation per se. Dense data structures use CPU cache more efficiently, removing prohibitive latency of memory accesses. Bandwidth savings are even better: smaller item size obviously improves bandwidth utilization, but having more items in cache obviates the need to use the bandwidth in the first place. Best case, the working set fits into the CPU cache! Note well that memory savings are evenly spread out. Using indexes makes every data structure slightly more compact, which improves performance across the board, regardless of hotspot distribution. It’s hard to notice a potential for such saving in a profiler, and even harder to test out. For these two reasons, I would default to indexes for code where speed matters, even when I don’t have the code written yet to profile it! There’s also a more subtle way in which indexes save memory. Using indexes means storing multiple items in an array, but such dense storage contains extra information in relative positions of the items. If you need to store a list of items, you can often avoid materializing the list of indexes by storing a range “pointing” into the shared storage. Occasionally, you can even do UTF-8 trick and use just a single bit to mark the end of a list. The second benefit of indexes is more natural modeling of cyclic and recursive data structures. Creating a cycle fundamentally requires mutability somewhere (“tying the knot” in Haskell relies on mutability of lazy thunks). This means that you need to make some pointers nullable, and that usually gets awkward even without borrow checker behind your back. Even without cycles and just recursion, pointers are problematic, due to a combination of two effects: The combination works fine at small scale, but then it fails with stack overflow in production every single time, requiring awkward work-arounds. For example, serializes error traces from nested macro expansions as a deeply nested tree of JSON objects, which requires using stacker hack when parsing the output (which you’ll learn about only after crashes in the hands of macro connoisseur users). Finally , indexes greatly help serialization, they make it trivial to communicate data structures both through space (sending a network message) and time (saving to disk and reading later). Indexes are naturally relocatable, it doesn’t matter where in memory they are. But this is just a half of serialization benefit. The other is that, because everything is in few arrays, you can do bulk serialization. You don’t need to write the items one by one, you can directly arrays around (but be careful to not leak data via padding, and be sure to checksum the result). The big problem with “naive” indexes is of course using the right index with the wrong array, or vice verse. The standard solution here is to introduce a newtype wrapper around the raw index. @andrewrk recently popularized a nice “happy accident of language design” pattern for this in Zig. The core idea is to define an index via non-exhaustive : In Zig, designates a strongly-typed collection of integer constants, not a Rust-style ADT (there’s for that). By default an backing integer type is chosen by the compiler, but you can manually override it with syntax: Finally, Zig allows making enums non-exhaustive with . In a non-exhaustive enum, any numeric value is valid, and some have symbolic labels: and builtins switch abstraction level between a raw integer and an enum value. So, is a way to spell “ , but a distinct type”. Note that there’s no strong encapsulation boundary here, anyone can . Zig just doesn’t provide language-enforced encapsulation mechanisms. Putting everything together, this is how I would model n-ary tree with parent pointers in Zig: Some points of note: P.S. Apparently I also wrote a Rust version of this post a while back? https://matklad.github.io/2018/06/04/newtype-index-pattern.html pointers encourage recursive functions, and recursive data structures lead to arbitrary long (but finite) chains of pointers. As usual with indexes, you start with defining the collective noun first, a rather than a . In my experience, you usually don’t want suffix in your index types, so is just , not the underlying data. Nested types are good! feels just right. For readability, the order is fields, then nested types, then functions. In , we have a couple of symbolic constants. is for the root node that is stored first, for whenever we want to apply offensive programing and make bad indexes blow up. Here, we use for “null” parent. An alternative would be to use , but that would waste of space, or making the root its own parent. If you care about performance, its a good idea to sizes of structures, not to prevent changes, but as a comment that explains to the reader just how the large the struct is. I don’t know if I like or more for representing ranges, but I use the former just because the names align in length. Both and are reasonable shapes for the API. I don’t know which one I prefer more. I default to the former because it works even if there are several node arguments.

0 views
Abhinav Sarkar 7 months ago

Solving Advent of Code 2025 in Janet: Days 5–8

I’m solving the Advent of Code 2025 in Janet . After doing the last five years in Haskell, I wanted to learn a new language this year. I’ve been eyeing the “New Lisps” 1 for a while now, and I decided to learn Janet. Janet is a Clojure like Lisp that can be interpreted, embedded and compiled, and comes with a large standard library with concurrency, HTTP and PEG parser support. I want to replace Python with Janet as my scripting language. Here are my solutions for December 5–8. This post was originally published on abhinavsarkar.net . This post is a part of the series: Solving Advent of Code 2025 in Janet . All my solutions follow the same structure because I wrote a template to create new empty solutions. Actually, I added a fair bit of automation this time to build, run, test and benchmark the solutions. Parsing the day 5 input was a bit involved because of the two different formats. Other than that, the function is the most interesting part. Since I sorted the ranges in , I needed to do only one linear scan of ranges, merging the current one with the previous one if possible. The trick here was to be correct about finding overlapping ranges and calculating the merged range. I made multiple mistakes but eventually figured it out. Day 6 was entirely a parsing-based problem, and Janet was well suited to it. Parts 1 and 2 required the input to be parsed differently, so the is parameterized. In part 1, I ignored whitespaces in numbers, while in part 2, they were significant. So I passed two different patterns to parse numbers in and . I had to write the function because it is not built into Janet. Rest of it was straightforward. Notice how I used threading macros to write the computations linearly. I solved part 1 of day 7 by simply folding over the input rows, propagating the beam, and splitting it when required. I used a set of indices to keep track of the current indices at which beam was present. Only tricky thing here was using a dict to simulate a set because Janet does not have sets built-in. That’s what the code is doing. Part 2 was harder. I first wrote a brute-force solution to count the number of paths, but it never finished running. The number of paths is \(O(2^n)\) , and impossible to solve with brute-force. I know that there may be better solutions possible, but I simply added a dict-based cache, and that made it work. Day 8 required me to do several new things. It was immediately clear to me that I needed a Disjoint Set to keep track of the connected points. So I wrote one in object-oriented Janet! Object-orientation in Janet is prototype-based , pretty much like JavaScript. You can see the and methods in the above. I first computed all unique pairs and distances between them, and sorted the pairs by distances. In part 1, I union-ed closest \(k\) pairs, while in part 2, I kept going till all points were connected in one circuit. This worked but it took really long to run: over 600ms. I was not satisfied. After a night’s sleep, I realized that I do not need to sort all pairs but only top \(k\) , where \(k\) is much smaller than total number of pairs (~500000). So I rewrote the function to use a max binary heap that keeps only the closest- \(k\) pairs. The function changed to pass \(k\) as a parameter to , which after a bit of experimentation, I set to 5500. The rest of the functions stayed unchanged. This change provided over 10x speedup, reducing the run time to under 60ms 2 ! You can see the mutable nature of Janet in all its glory in this solution. I had several gotcha moments when I tried to mix higher-order functions—such as , , and —with mutable date structures in Janet. Not only they are confusing, but they also result in slower code because Janet does not have Persistent data-structures like Clojure. Every etc. result in a new array being created. My advice is to not mix functional programming code with procedural programming code in Janet. That’s it for now. Next note will drop after 4 or 5 days. You can browse the code repo to see the full setup. If you have any questions or comments, please leave a comment below. If you liked this post, please share it. Thanks for reading! The new Lisps that interest me are: Janet, Fennel and Jank . ↩︎ You may ask why I didn’t write the max-heap as OO-Janet code. Well, I did and I found that it was 50% slower than the procedural version shown here. I guess the dispatch overhead for methods is too much. ↩︎ This post is a part of the series: Solving Advent of Code 2025 in Janet . If you liked this post, please leave a comment . Days 5–8 👈 The new Lisps that interest me are: Janet, Fennel and Jank . ↩︎ You may ask why I didn’t write the max-heap as OO-Janet code. Well, I did and I found that it was 50% slower than the procedural version shown here. I guess the dispatch overhead for methods is too much. ↩︎ Days 5–8 👈

0 views
Abhinav Sarkar 7 months ago

Solving Advent of Code 2025 in Janet: Day 1–4

I’m solving the Advent of Code 2025 in Janet . After doing the last five years in Haskell, I wanted to learn a new language this year. I’ve been eyeing the “New Lisps” 1 for a while now, and I decided to learn Janet. Janet is a Clojure like Lisp that can be interpreted, embedded and compiled, and comes with a large standard library with concurrency, HTTP and PEG parser support. I want to replace Python with Janet as my scripting language. Here are my solutions for Dec 1–4. This post was originally published on abhinavsarkar.net . All my solutions follow the same structure because I wrote a template to create new empty solutions. Actually, I added a fair bit of automation this time to build, run, test and benchmark the solutions. Day 1 was a bit mathy but it didn’t take too long to figure out. I spent more time polishing the solution to be idiomatic Janet code. , the PEG grammar to parse the input was the most interesting part for me on the day. If you know Janet, you can notice this is not the cleanest code, but that’s okay, it was my day 1 too. The most interesting part of the day 2 solution was the macro that reads the input at compile-time and creates a custom function to check whether a number is in one of the given ranges. This turned out to be almost 4x faster than writing the same thing as a function. Notice , the PEG grammar to parse the input. So short and clean! I also leaned into the imperative and mutable nature of the Janet data-structures. The code is still not the cleanest as I was still learning. The first part of day 3 was pretty easy to solve, but using the same solution for the second part just ran forever. I realized that this is a Dynamic Programming problem, but I don’t like doing array-based solutions, so I simply rewrote the solution to add caching. And it worked! It is definitely on the slower side, but I’m okay with it. The code has become a little more idiomatic Janet. Day 4 is when I learned more about Janet control flow structures. The solution for the part 2 is a straightforward Breadth-first traversal . The interesting parts are the , and statements. So concise and elegant! That’s it for now. Next note will drop after 4 or 5 days. You can browse the code repo to see the full setup. If you have any questions or comments, please leave a comment below. If you liked this post, please share it. Thanks for reading! The new Lisps that interest me are: Janet, Fennel and Jank . ↩︎ If you liked this post, please leave a comment . The new Lisps that interest me are: Janet, Fennel and Jank . ↩︎

0 views
Fernando Borretti 8 months ago

Ad-Hoc Emacs Packages with Nix

You can use Nix as a package manager for Emacs, like so: Today I learned you can also use it to create ad-hoc packages for things not in MELPA or nixpkgs . The other day I wanted to get back into Inform 7 , naturally the first stack frame of the yak shave was to look for an Emacs mode. exists, but isn’t packaged anywhere. So I had to vendor it in. You can use git submodules for this, but I have an irrational aversion to submodules. Instead I did something far worse: I wrote a Makefile to download the from GitHub, and used home-manager to copy it into my . Which is nasty. And of course this only works for small, single-file packages. And, on top of that: whatever dependencies your vendored packages need have to be listed in , which confuses the packages you want, with the transitive dependencies of your vendored packages. I felt like the orange juice bit from The Simpsons . There must be a better way! And there is. With some help from Claude, I wrote this: Nix takes care of everything: commit pinning, security (with the SHA-256 hash), dependencies for custom packages. And it works wonderfully. Armed with a new hammer, I set out to drive some nails. Today I created a tiny Haskell project, and when I opened the file, noticed it had no syntax highlighting. I was surprised to find there’s no in MELPA. But coincidentally, someone started working on this literally three weeks ago ! So I wrote a small expression to package this new : A few weeks back I switched from macOS to Linux, and since I’m stuck on X11 because of stumpwm , I’m using XCompose to define keybindings for entering dashes, smart quotes etc. It bothered me slightly that my file didn’t have syntax highlighting. I found in kragen’s repo , but it’s slightly broken (it’s missing a call at the end). I started thinking how hard it would be to write a Nix expression to modify the source after fetching, when I found that Thomas Voss hosts a patched version here . Which made this very simple: Somehow the version of in nixpkgs unstable was missing the configuration option to use a custom shell. Since I want to use nu instead of bash, I had to package this myself from the latest commit: I started reading Functional Programming in Lean recently, and while there is a , it’s not packaged anywhere. This only required a slight deviation from the pattern: when I opened a file I got an error about a missing JSON file, consulting the README for , it says: If you use a source-based package-manager (e.g. , Straight or Elpaca), then make sure to list the directory in your Lean4-Mode package recipe. To do this I had to use rather than :

0 views
mcyoung 8 months ago

Why SSA?

If you’ve read anything about compilers in the last two decades or so, you have almost certainly heard of SSA compilers , a popular architecture featured in many optimizing compilers, including ahead-of-time compilers such as LLVM, GCC, Go, CUDA (and various shader compilers), Swift 1 , and MSVC 2 , and just-in-time compilers such as HotSpot C2 3 , V8 4 , SpiderMonkey 5 , LuaJIT, and the Android Runtime 6 . SSA is hugely popular, to the point that most compiler projects no longer bother with other IRs for optimization 7 . This is because SSA is incredibly nimble at the types of program analysis and transformation that compiler optimizations want to do on your code. But why ? Many of my friends who don’t do compilers often say that compilers seem like opaque magical black boxes, and SSA, as it often appears in the literature, is impenetrably complex. But it’s not! SSA is actually very simple once you forget everything you think your programs are actually doing. We will develop the concept of SSA form, a simple SSA IR, prove facts about it, and design some optimizations on it. I have previously written about the granddaddy of all modern SSA compilers, LLVM. This article is about SSA in general, and won’t really have anything to do with LLVM. However, it may be helpful to read that article to make some of the things in this article feel more concrete. SSA is a property of intermediate representations (IRs), primarily used by compilers for optimizing imperative code that target a register machine . Register machines are computers that feature a fixed set of registers that can be used as the operands for instructions: this includes virtually all physical processors, including CPUs, GPUs, and weird tings like DSPs. SSA is most frequently found in compiler middle-ends , the optimizing component between the frontend (which deals with the surface language programmers write, and lowers it into the middle-end’s IR), and the backend (which takes the optimized IR and lowers it into the target platform’s assembly). SSA IRs, however, often have little resemblance to the surface language they lower out of, or the assembly language they target. This is because neither of these representations make it easy for a compiler to intuit optimization opportunities. Imperative code consists of a sequence of operations that mutate the executing machine’s state to produce a desired result. For example, consider the following C program: This program returns no matter what its input is, so we can optimize it down to this: But, how would you write a general algorithm to detect that all of the operations cancel out? You’re forced to keep in mind program order to perform the necessary dataflow analysis, following mutations of and through the program. But this isn’t very general, and traversing all of those paths makes the search space for large functions very big. Instead, you would like to rewrite the program such that and gradually get replaced with the expression that calculates the most recent value, like this: Then we can replace each occurrence of a variable with its right-hand side recursively… Then fold the constants together… And finally, we see that we’re returning , and can replace it with . All the other variables are now unused, so we can delete them. The reason this works so well is because we took a function with mutation, and converted it into a combinatorial circuit , a type of digital logic circuit that has no state, and which is very easy to analyze. The dependencies between nodes in the circuit (corresponding to primitive operations such as addition or multiplication) are obvious from its structure. For example, consider the following circuit diagram for a one-bit multiplier: This graph representation of an operation program has two huge benefits: The powerful tools of graph theory can be used to algorithmically analyze the program and discover useful properties, such as operations that are independent of each other or whose results are never used. The operations are not ordered with respect to each other except when there is a dependency; this is useful for reordering operations, something compilers really like to do. The reason combinatorial circuits are the best circuits is because they are directed acyclic graphs (DAGs) which admit really nice algorithms. For example, longest path in a graph is NP-hard (and because P ≠ N P P \neq NP P  = NP 8 , has complexity O ( 2 n ) O(2^n) O ( 2 n ) ). However, if the graph is a DAG, it admits an O ( n ) O(n) O ( n ) solution! To understand this benefit, consider another program: Suppose we wanted to replace each variable with its definition like we did before. We can’t just replace each constant variable with the expression that defines it though, because we would wind up with a different program! Now, we pick up an extra term because the squaring operation is no longer unused! We can put this into circuit form, but it requires inserting new variables for every mutation. But we can’t do this when complex control flow is involved! So all of our algorithms need to carefully account for mutations and program order, meaning that we don’t get to use the nice graph algorithms without careful modification. SSA stands for “static single assignment”, and was developed in the 80s as a way to enhance the existing three-argument code (where every statement is in the form ) so that every program was circuit-like, using a very similar procedure to the one described above. The SSA invariant states that every variable in the program is assigned to by precisely one operation. If every operation in the program is visited once, they form a combinatorial circuit. Transformations are required to respect this invariant. In circuit form, a program is a graph where operations are nodes, and “registers” (which is what variables are usually called in SSA) are edges (specifically, each output of an operation corresponds to a register). But, again, control flow. We can’t hope to circuitize a loop, right? The key observation of SSA is that most parts of a program are circuit-like. A basic block is a maximal circuital component of a program. Simply put, it is a sequence of non-control flow operations, and a final terminator operation that transfers control to another basic block. The basic blocks themselves form a graph, the control flow graph , or CFG. This formulation of SSA is sometimes called SSA-CFG 9 . This graph is not a DAG in general; however, separating the program into basic blocks conveniently factors out the “non-DAG” parts of the program, allowing for simpler analysis within basic blocks. There are two equivalent formalisms for SSA-CFG. The traditional one uses special “phi” operations (often called phi nodes , which is what I will call them here) to link registers across basic blocks. This is the formalism LLVM uses. A more modern approach, used by MLIR, is block arguments : each basic block specifies parameters, like a function, and blocks transferring control flow to it must pass arguments of those types to it. Let’s look at some code. First, consider the following C function which calculates Fibonacci numbers using a loop. How might we express this in an SSA-CFG IR? Let’s start inventing our SSA IR! It will look a little bit like LLVM IR, since that’s what I’m used to looking at. Every block ends in a , which transfers control to one of several possible blocks. In the process, it calls that block with the given arguments. One can think of a basic block as a tiny function which tails 10 into other basic blocks in the same function. aside Phi Nodes LLVM IR is… older, so it uses the older formalism of phi nodes. “Phi” comes from “phony”, because it is an operation that doesn’t do anything; it just links registers from predecessors. A operation is essentially a switch-case on the predecessors, each case selecting a register from that predecessor (or an immediate). For example, has two predecessors, the implicit entry block , and . In a phi node IR, instead of taking a block argument for , it would specify The value of the operation is the value from whichever block jumped to this one. This can be awkward to type out by hand and read, but is a more convenient representation for describing algorithms (just “add a phi node” instead of “add a parameter and a corresponding argument”) and for the in-memory representation, but is otherwise completely equivalent. It’s a bit easier to understand the transformation from C to our IR if we first rewrite the C to use goto instead of a for loop: However, we still have mutation in the picture, so this isn’t SSA. To get into SSA, we need to replace every assignment with a new register, and somehow insert block arguments… The above IR code is already partially optimized; the named variables in the C program have been lifted out of memory and into registers. If we represent each named variable in our C program with a pointer, we can avoid needing to put the program into SSA form immediately. This technique is used by frontends that lower into LLVM, like Clang. We’ll enhance our IR by adding a declaration for functions, which defines scratch space on the stack for the function to use. Each stack slot produces a pointer that we can from and to. Our Fibonacci function would now look like so: Any time we reference a named variable, we load from its stack slot, and any time we assign it, we store to that slot. This is very easy to get into from C, but the code sucks because it’s doing lots of unnecessary pointer operations. How do we get from this to the register-only function I showed earlier? aside Program Order We want program order to not matter for the purposes of reordering, but as we’ve written code here, program order does matter: loads depend on prior stores but stores don’t produce a value that can be used to link the two operations. We can restore not having program order by introducing operands representing an “address space”; loads and stores take an address space as an argument, and stores return a new address space. An address space, or , represents the state of some region of memory. Loads and stores are independent when they are not connected by a argument. This type of enhancement is used by Go’s SSA IR, for example. However, it adds a layer of complexity to the examples, so instead I will hand-wave this away. Now we need to prove some properties about CFGs that are important for the definition and correctness of our optimization passes. First, some definitions. The predecessors (or “preds”) of a basic block is the set of blocks with an outgoing edge to that block. A block may be its own predecessors. Some literature calls the above “direct” or immediate predecessors. For example, the preds of in our example are are (the special name for the function entry-point) . The successors (no, not “succs”) of a basic block is the set of blocks with an outgoing edge from that block. A block may be its own successors. The sucessors of are and . The successors are listed in the loop’s . If a block is a transitive pred of a block , we say that weakly dominates , or that it is a weak dominator of . For example, , and both weakly dominate . However, this is not usually an especially useful relationship. Instead, we want to speak of dominators: A block is a dominator (or dominates ) if every pred of is dominated by , or if is itself. Equivalently, the dominator set of is the intersection of the dominator sets of its preds, plus . The dominance relation has some nice order properties that are necessary for defining the core graph algorithms of SSA. We only consider CFGs which are flowgraphs, that is, all blocks are reachable from the root block , which has no preds. This is necessary to eliminate some pathological graphs from our proofs. Importantly, we can always ask for an acyclic path 11 from to any block . An equivalent way to state the dominance relationship is that from every path from to contains all of ’s dominators. proposition dominates iff every path from to contains . First, assume every to path contains . If is , we’re done. Otherwise we need to prove each predecessor of is dominated by ; we do this by induction on the length of acyclic paths from to . Consider preds of that are not , and consider all acyclic paths p p p from to ; by appending to them, we have an acyclic path p ′ p' p ′ from to , which must contain . Because both the last and second-to-last elements of this are not , it must be within the shorter path p p p which is shorter than p ′ p' p ′ . Thus, by induction, dominates and therefore Going the other way, if dominates , and consider a path p p p from to . The second-to-last element of p p p is a pred of ; if it is we are done. Otherwise, we can consider the path p p p made by deleting at the end. is dominated by , and p ′ p' p ′ is shorter than p p p , so we can proceed by induction as above. Onto those nice properties. Dominance allows us to take an arbitrarily complicated CFG and extract from it a DAG, composed of blocks ordered by dominance. The dominance relation is a partial order. Dominance is reflexive and transitive by definition, so we only need to show blocks can’t dominate each other. Suppose distinct and dominate each other.Pick an acyclic path p p p from to . Because dominates , there is a prefix p ′ p' p ′ of this path ending in . But because dominates , some prefix p ′ ′ p'' p ′′ of p ′ p' p ′ ends in . But now p p p must contain twice, contradicting that it is acyclic. This allows us to write when dominates . There is an even more refined graph structure that we can build out of dominators, which follows immediately from the partial order theorem. The dominators of a basic block are totally ordered by the dominance relation. Suppose and , but neither dominates the other. Then, there must exist acyclic paths from to which contain both, but in different orders. Take the subpaths of those paths which follow , and , neither of which contains . Concatenating these paths yields a path from to that does not contain , a contradiction. This tells us that the DAG we get from the dominance relation is actually a tree, rooted at . The parent of a node in this tree is called its immediate dominator . Computing dominators can be done iteratively: the dominator set of a block is the intersection the dominator sets of its preds, plus . This algorithm runs in quadratic time. A better algorithm is the Lengauer-Tarjan algorithm[^lta]. It is relatively simple, but explaining how to implement it is a bit out of scope for this article. I found a nice treatment of it here . What’s important is we can compute the dominator tree without breaking the bank, and given any node, we can ask for its immediate dominator. Using immediate dominators, we can introduce the final, important property of dominators. The dominance frontier of a block is the set of all blocks not dominated by with at least one pred which dominates. These are points where control flow merges from distinct paths: one containing and one not. The dominance frontier of is , whose preds are and . There are many ways to calculate dominance frontiers, but with a dominance tree in hand, we can do it like this: algorithm Dominance Frontiers. For each block with more than one pred, for each of its preds, let be that pred. Add to the dominance frontier of and all of its dominators, stopping when encountering ’ immediate dominator. We need to prove that every block examined by the algorithm winds up in the correct frontiers. First, we check that every examined block is added to the correct frontier. If , where is a pred of , and a is ’s immediate dominator, then if , is not in its frontier, because must dominate . Otherwise, must be in ’s frontier, because dominates a pred but it cannot dominate , because then it would be dominated by , a contradiction. Second, we check that every frontier is complete. Consider a block . If an examined block is in its frontier, then must be among the dominators of some pred , and it must be dominated by ’s immediate dominator; otherwise, would dominate (and thus would not be in its frontier). Thus, gets added to ’s dominator. You might notice that all of these algorithms are quadratic. This is actually a very good time complexity for a compilers-related graph algorithm. Cubic and quartic algorithms are not especially uncommon, and yes, your optimizing compiler’s time complexity is probably cubic or quartic in the size of the program! Ok. Let’s construct an optimization. We want to figure out if we can replace a load from a pointer with the most recent store to that pointer. This will allow us to fully lift values out of memory by cancelling out store/load pairs. This will make use of yet another implicit graph data structure. The dataflow graph is the directed graph made up of the internal circuit graphs of each each basic block, connected along block arguments. To follow a use-def chain is to walk this graph forward from an operation to discover operations that potentially depend on it, or backwards to find operations it potentially depends on. It’s important to remember that the dataflow graph, like the CFG, does not have a well defined “up” direction. Navigating it and the CFG requires the dominator tree. One other important thing to remember here is that every instruction in a basic block always executes if the block executes. In much of this analysis, we need to appeal to “program order” to select the last load in a block, but we are always able to do so. This is an important property of basic blocks that makes them essential for constructing optimizations. For a given , we want to identify all loads that depend on it. We can follow the use-def chain of to find which blocks contain loads that potentially depend on the store (call it ). First, we can eliminate loads within the same basic block (call it ). Replace all instructions after (but before any other s, in program order) with ’s def. If is not the last store in this block, we’re done. Otherwise, follow the use-def chain of to successors which use , i.e., successors whose case has as at least one argument. Recurse into those successors, and now replacing the pointer of interest with the parameters of the successor which were set to (more than one argument may be ). If successor loads from one of the registers holding , replace all such loads before a store to . We also now need to send into somehow. This is where we run into something of a wrinkle. If has exactly one predecessor, we need to add a new block argument to pass whichever register is holding (which exists by induction). If is already passed into by another argument, we can use that one. However, if has multiple predecessors, we need to make sure that every path from to sends , and canonicalizing those will be tricky. Worse still, if is in ’s domination frontier, a different store could be contributing to that load! For this reason, dataflow from stores to loads is not a great strategy. Instead, we’ll look at dataflow from loads backwards to stores (in general, dataflow from uses to defs tends to be more useful), which we can use to augment the above forward dataflow analysis to remove the complex issues around domination frontiers. Let’s analyze loads instead. For each in , we want to determine all stores that could potentially contribute to its value. We can find those stores as follows: We want to be able to determine which register in a given block corresponds to the value of , and then find its last store in that block. To do this, we’ll flood-fill the CFG backwards in BFS order. This means that we’ll follow preds (through the use-def chain) recursively, visiting each pred before visiting their preds, and never revisiting a basic block (except we may need to come back to at the end). Determining the “equivalent” 12 of in (we’ll call it ) can be done recursively: while examining , follow the def of . If is a block parameter, for each pred , set to the corresponding argument in the case in ’s . Using this information, we can collect all stores that the load potentially depends on. If a predecessor stores to , we add the last such store in (in program order) to our set of stores, and do not recurse to ’s preds (because this store overwrites all past stores). Note that we may revisit in this process, and collect a store to from it occurs in the block. This is necessary in the case of loops. The result is a set of pairs. In the process, we also collected a set of all blocks visited, , which are dominators of which we need to plumb a through. This process is called memory dependency analysis , and is a key component of many optimizations. Not all contributing operations are stores. Some may be references to globals (which we’re disregarding), or function arguments or the results of a function call (which means we probably can’t lift this load). For example gets traced all the way back to a function argument, there is a code path which loads from a pointer whose stores we can’t see. It may also trace back to a stack slot that is potentially not stored to. This means there is a code path that can potentially load uninitialized memory. Like LLVM, we can assume this is not observable behavior, so we can discount such dependencies. If all of the dependencies are uninitialized loads, we can potentially delete not just the load, but operations which depend on it (reverse dataflow analysis is the origin of so-called “time-traveling” UB). Now that we have the full set of dependency information, we can start lifting loads. Loads can be safely lifted when all of their dependencies are stores in the current function, or dependencies we can disregard thanks to UB in the surface language (such as loads or uninitialized loads). There is a lot of fuss in this algorithm about plumbing values through block arguments. A lot of IRs make a simplifying change, where every block implicitly receives the registers from its dominators as block arguments. I am keeping the fuss because it makes it clearer what’s going on, but in practice, most of this plumbing, except at dominance frontiers, would be happening in the background. Suppose we can safely lift some load. Now we need to plumb the stored values down to the load. For each block in (all other blocks will now be in unless stated otherwise). We will be building two mappings: one , which is the register equivalent to in that block. We will also be building a map , which is the value that must have in that block. Prepare a work queue, with each in it initially. Pop a block form the queue. For each successor (in ): If isn’t already defined, add it as a block argument. Have pass to that argument. If hasn’t been visited yet, and isn’t the block containing the load we’re deleting, add it to the queue. Once we’re done, if is the block that contains the load, we can now replace all loads to before any stores to with . There are cases where this whole process can be skipped, by applying a “peephole” optimization. For example, stores followed by loads within the same basic block can be optimized away locally, leaving the heavy-weight analysis for cross-block store/load pairs. Here’s the result of doing dependency analysis on our Fibonacci function. Each load is annotated with the blocks and stores in . Let’s look at . Is contributing loads are in and . So we add a new parameter : in , we call that parameter with (since that’s stored to it in ), while in , we pass . What about L4? The contributing loads are also in and , but one of those isn’t a pred of . is also in the subgraph for this load, though. So, starting from , we add a new parameter to and feed (the stored value, an immediate this time) through it. Now looking at , we see there is already a parameter for this load ( ), so we just pass as that argument. Now we process , which pushed onto the queue. gets a new parameter , which is fed ’s own . We do not re-process , even though it also appears in ’s gotos, because we already visited it. After doing this for the other two loads, we get this: After lifting, if we know that a stack slot’s pointer does not escape (i.e., none of its uses wind up going into a function call 13 ) or a write to a global (or a pointer that escapes), we can delete every store to that pointer. If we delete every store to a stack slot, we can delete the stack slot altogether (there should be no loads left for that stack slot at this point). This analysis is simple, because it assumes pointers do not alias in general. Alias analysis is necessary for more accurate dependency analysis. This is necessary, for example, for lifting loads of fields of structs through subobject pointers, and dealing with pointer arithmetic in general. However, our dependency analysis is robust to passing different pointers as arguments to the same block from different predecessors. This is the case that is specifically handled by all of the fussing about with dominance frontiers. This robustness ultimately comes from SSA’s circuital nature. Similarly, this analysis needs to be tweaked to deal with something like (a ternary, essentially). s of pointers need to be replaced with s of the loaded values, which means we need to do the lifting transformation “all at once”: lifting some liftable loads will leave the IR in an inconsistent state, until all of them have been lifted. Many optimizations will make a mess of the CFG, so it’s useful to have simple passes that “clean up” the mess left by transformations. Here’s some easy examples. If an operation’s result has zero uses, and the operation has no side-effects, it can be deleted. This allows us to then delete operations that it depended on that now have no side effects. Doing this is very simple, due to the circuital nature of SSA: collect all instructions whose outputs have zero uses, and delete them. Then, examine the defs of their operands; if those operations now have no uses, delete them, and recurse. This bubbles up all the way to block arguments. Deleting block arguments is a bit trickier, but we can use a work queue to do it. Put all of the blocks into a work queue. Pop a block from the queue. Run unused result elimination on its operations. If it now has parameters with no uses, remove those parameters. For each pred, delete the corresponding arguments to this block. Then, Place those preds into the work queue (since some of their operations may have lost their last use). If there is still work left, go to 1. There are many CFG configurations that are redundant and can be simplified to reduce the number of basic blocks. For example, unreachable code can help delete blocks. Other optimizations may cause the at the end of a function to be empty (because all of its successors were optimized away). We treat an empty as being unreachable (since it has no cases!), so we can delete every operation in the block up to the last non-pure operation. If we delete every instruction in the block, we can delete the block entirely, and delete it from its preds’ s. This is a form of dead code elimination , or DCE, which combines with the previous optimization to aggressively delete redundant code. Some jumps are redundant. For example, if a block has exactly one pred and one successor, the pred’s case for that block can be wired directly to the successor. Similarly, if two blocks are each other’s unique predecessor/successor, they can be fused , creating a single block by connecting the input blocks’ circuits directly, instead of through a . If we have a ternary operation, we can do more sophisticated fusion. If a block has two successors, both of which the same unique successor, and those successors consist only of gotos, we can fuse all four blocks, replacing the CFG diamond with a . In terms of C, this is this transformation: LLVM’s CFG simplification pass is very sophisticated and can eliminate complex forms of control flow. I am hoping to write more about SSA optimization passes. This is a very rich subject, and viewing optimizations in isolation is a great way to understand how a sophisticated optimization pipeline is built out of simple, dumb components. It’s also a practical application of graph theory that shows just how powerful it can be, and (at least in my opinion), is an intuitive setting for understanding graph theory, which can feel very abstract otherwise. In the future, I’d like to cover CSE/GVN, loop optimizations, and, if I’m feeling brave, getting out of SSA into a finite-register machine (backends are not my strong suit!). Specifically the Swift frontend before lowering into LLVM IR.  ↩ Microsoft Visual C++, a non-conforming C++ compiler sold by Microsoft  ↩ HotSpot is the JVM implementation provided by OpenJDK; C2 is the “second compiler”, which has the best performance among HotSpot’s Java execution engines.  ↩ V8 is Chromium’s JavaScript runtime.  ↩ SpiderMonkey is Firefox’s JavaScript runtime.  ↩ The Android Runtime (ART) is the “JVM” (scare quotes) on the Android platform.  ↩ The Glasgow Haskell Compiler (GHC), does not use SSA; it (like some other pure-functional languages) uses a continuation-oriented IR (compare to Scheme’s ).  ↩ Every compiler person firmly believes that P ≠ N P P \neq NP P  = NP , because program optimization is full of NP-hard problems and we would have definitely found polynomial ideal register allocation by now if it existed.  ↩ Some more recent IRs use a different version of SSA called “structured control flow”, or SCF. Wasm is a notable example of an SCF IR. SSA-SCF is equivalent to SSA-CFG, and polynomial time algorithms exist for losslessly converting between them (LLVM compiling Wasm, for example, converts its CFG into SCF using a “relooping algorithm”). In SCF, operations like switch statements and loops are represented as macro operations that contain basic blocks. For example, a operation might take a value as input, select a basic block to execute based on that, and return the value that basic block evaluates to as its output. RVSDG is a notable innovation in this space, because it allows circuit analysis of entire imperative programs. I am convering SSA-CFG instead of SSA-SCF simply because it’s more common, and because it’s what LLVM IR is. See also this MLIR presentation for converting between the two.  ↩ Tail calling is when a function call is the last operation in a function; this allows the caller to jump directly to the callee, recycling its own stack frame for it instead of requiring it to allocate its own.  ↩ Given any path from to , we can make it acyclic by replacing each subpath from to with a single node.  ↩ When moving from a basic block to a pred, a register in that block which is defined as a block parameter corresponds to some register (or immediate) in each predecessor. That is the “equivalent” of . One possible option for the “equivalent” is an immediate: for example, or the address of a global. In the case of a global , assuming no data races, we would instead need alias information to tell if stores to this global within the current function (a) exist and (b) are liftable at all. If the equivalent is , we can proceed in one of two ways depending on optimization level. If we want loads of to trap (as in Go), we need to mark this load as not being liftable, because it may trap. If we want loads of to be UB, we simply ignore that pred, because we can assume (for our analysis) that if the pointer is , it is never loaded from.  ↩ Returned stack pointers do not escape: stack slots’ lifetimes end at function exit, so we return a dangling pointer, which we assume are never loaded. So stores to that pointer before returning it can be discarded.  ↩ The powerful tools of graph theory can be used to algorithmically analyze the program and discover useful properties, such as operations that are independent of each other or whose results are never used. The operations are not ordered with respect to each other except when there is a dependency; this is useful for reordering operations, something compilers really like to do. Prepare a work queue, with each in it initially. Pop a block form the queue. For each successor (in ): If isn’t already defined, add it as a block argument. Have pass to that argument. If hasn’t been visited yet, and isn’t the block containing the load we’re deleting, add it to the queue. Pop a block from the queue. Run unused result elimination on its operations. If it now has parameters with no uses, remove those parameters. For each pred, delete the corresponding arguments to this block. Then, Place those preds into the work queue (since some of their operations may have lost their last use). If there is still work left, go to 1. Specifically the Swift frontend before lowering into LLVM IR.  ↩ Microsoft Visual C++, a non-conforming C++ compiler sold by Microsoft  ↩ HotSpot is the JVM implementation provided by OpenJDK; C2 is the “second compiler”, which has the best performance among HotSpot’s Java execution engines.  ↩ V8 is Chromium’s JavaScript runtime.  ↩ SpiderMonkey is Firefox’s JavaScript runtime.  ↩ The Android Runtime (ART) is the “JVM” (scare quotes) on the Android platform.  ↩ The Glasgow Haskell Compiler (GHC), does not use SSA; it (like some other pure-functional languages) uses a continuation-oriented IR (compare to Scheme’s ).  ↩ Every compiler person firmly believes that P ≠ N P P \neq NP P  = NP , because program optimization is full of NP-hard problems and we would have definitely found polynomial ideal register allocation by now if it existed.  ↩ Some more recent IRs use a different version of SSA called “structured control flow”, or SCF. Wasm is a notable example of an SCF IR. SSA-SCF is equivalent to SSA-CFG, and polynomial time algorithms exist for losslessly converting between them (LLVM compiling Wasm, for example, converts its CFG into SCF using a “relooping algorithm”). In SCF, operations like switch statements and loops are represented as macro operations that contain basic blocks. For example, a operation might take a value as input, select a basic block to execute based on that, and return the value that basic block evaluates to as its output. RVSDG is a notable innovation in this space, because it allows circuit analysis of entire imperative programs. I am convering SSA-CFG instead of SSA-SCF simply because it’s more common, and because it’s what LLVM IR is. See also this MLIR presentation for converting between the two.  ↩ Tail calling is when a function call is the last operation in a function; this allows the caller to jump directly to the callee, recycling its own stack frame for it instead of requiring it to allocate its own.  ↩ Given any path from to , we can make it acyclic by replacing each subpath from to with a single node.  ↩ When moving from a basic block to a pred, a register in that block which is defined as a block parameter corresponds to some register (or immediate) in each predecessor. That is the “equivalent” of . One possible option for the “equivalent” is an immediate: for example, or the address of a global. In the case of a global , assuming no data races, we would instead need alias information to tell if stores to this global within the current function (a) exist and (b) are liftable at all. If the equivalent is , we can proceed in one of two ways depending on optimization level. If we want loads of to trap (as in Go), we need to mark this load as not being liftable, because it may trap. If we want loads of to be UB, we simply ignore that pred, because we can assume (for our analysis) that if the pointer is , it is never loaded from.  ↩ Returned stack pointers do not escape: stack slots’ lifetimes end at function exit, so we return a dangling pointer, which we assume are never loaded. So stores to that pointer before returning it can be discarded.  ↩

0 views
Abhinav Sarkar 8 months ago

A Fast Bytecode VM for Arithmetic: The Virtual Machine

In this series of posts, we write a fast bytecode compiler and a virtual machine for arithmetic in Haskell. We explore the following topics: In this final post, we write the virtual machine that executes our bytecode, and benchmark it. This post was originally published on abhinavsarkar.net . This post is part of the series: A Fast Bytecode VM for Arithmetic . Bytecode Virtual Machines (VMs) are known to be faster than AST -walking interpreters. That’s why many real-world programming languages these days are implemented with bytecode VM s, for example, Java , Python , PHP , and Raku . The reason is partially, the flat and compact nature of bytecode itself. But VM s also have a few other tricks up their sleeves that make them highly performant. In this post, we write a VM for our arithmetic expression language, and explore some of these performance tricks. But first, we need to finish a pending task. We wrote some unit tests for our compiler in the last post, but unit tests cover only the cases we can think of. A compiler has to deal with any input, and with just unit tests we cannot be sure of its correctness. To test our compiler and other components for correctness, we use the QuickCheck library. QuickCheck is a Property-based Testing framework. The key idea of property-based testing is to write properties of our code that hold true for any input, and then to automatically generate a large number of arbitrary inputs and make sure that the properties are indeed true for them 1 2 . Since we are writing an arithmetic expression parser/compiler/ VM , we generate arbitrary expression AST s, and use them to assert certain invariants of our program. With QuickCheck, we write generators for the inputs for our tests. These generators are composable just like parser combinators are. We use the library provided generators to write small generators that we combine to create larger ones. Let’s start: First come the basic generators: Moving on to composite generators: generates binary expressions with arbitrary binary operations. It recursively calls to generate the operands. The parameter controls the complexity of the generated expressions, and we half the size of operands (and so on recursively) so that we don’t end up with infinitely large expressions. generates expressions by generating an identifier, and then generating the assignment and body expressions recursively. We do the same trick of halving sizes here as well. Notice that the assignment is generated with the passed variable names in scope, whereas the body is generated with the new identifier added to the scope. uses the above generators to generate all kinds of expressions. At smaller sizes, it prefers to generate base expressions, while at larger sizes, it prefers composite ones. Due to the careful recursive halving of size in composite generators, we end up with expressions of finite sizes. Finally, we have some instances of QuickCheck’s type class to tie everything together: We can apply them in GHCi: Notice that the generated samples increase in complexity. With the generators in place, we define our properties next. Let’s test our parser first: This property is a simple round-trip test for the parser and printer: we parse the string representation of a generated expression, and assert that it gives back the same expression. The second property is a more involved round-trip test for the compiler and decompiler: This asserts that compiling an expression, then disassembling and decompiling it, and finally compiling it again should result in the original bytecode 3 . This requires a helper function to get the size of an expression: We run these tests in a later section. This ends our short detour. Now for the main event: the virtual machine. Our VM is a stack-based machine that operates on a stack of values and executes the compiled bytecode. Our goal is to be as fast as possible. For a quick reminder, these are our s: And now, the heart of the VM : The function is where the action happens. It is way more complex than , but the complexity has a reason, namely performance. runs inside the monad wrapped with the monad transformer. monad lets us use mutable data structures locally while ensuring the function remains externally pure. monad transformer adds support for throwing and propagating errors in a pure manner. We use for our stack, which is a mutable array of unboxed primitive types, in our case an array of values. Using a mutable unboxed array is much faster than using an immutable and/or boxed one like or due to reduced allocation and/or pointer chasing. The core of the VM is the function, a tight, tail-recursive loop that GHC compiles into an efficient machine loop, as we see later. It takes the stack pointer ( ), instruction pointer ( ) 4 , and the stack as arguments. At the top of each loop, a block of guard clauses checks for stack overflow, underflow, and other error conditions before branching on the current opcode. Placing these checks at the top instead of inside the opcode cases is a deliberate choice. This may make the code slightly harder to understand, but it significantly improves the performance of the loop by moving all branching at the beginning of the loop, resulting in code that is more friendly to the CPU’s Branch Predictor . Also notice how we reduce the number of checks by working with a range of opcodes at once in the guard. The checks are also sorted so as to be most performant, guided by profiling and benchmarking 5 . The handling of each opcode is actually pretty straightforward. We use different specific operations to read and write to the stack, while taking care of doing the required bound and arithmetic checks. We also use the functions that we wrote earlier . After carrying out each operation, we reenter the loop by calling it tail-recursively with the right stack and instruction pointers. Finally, we make sure that the execution terminated correctly by checking the state of the stack, and return its first element. We see later that the VM is quite fast, but how does GHC achieve this performance? To see the magic, we can look at GHC ’s intermediate language: Core . Core is a simpler functional language than Haskell to which GHC compiles Haskell. The simpler nature of Core makes it easier for GHC to optimize it, and compile it further. We can get the Core code for a program by compiling with the GHC option . The actual Core code for our VM is too verbose to show here, but here is a simplified C-like pseudo-code version of our loop: A few key optimizations are worth pointing out: The loop: The tail-recursive function is compiled into a proper loop. The instruction is effectively a , which means there’s no function call overhead for each iteration of the VM loop. Unboxing: The Core code is full of primitive, unboxed types like , , and , and operations on them. These are raw machine integers and memory addresses, not boxed Haskell objects. This means operations on them are as fast as they would be in C. The stack operations are not function calls on a instance, but primitive memory reads and writes on a raw memory address . Inlining: The helper function is completely inlined into the main loop. For , the code for reading two values, adding them, and writing the result is laid out inline, and works on unboxed values and array address. In short, GHC has turned our high-level, declarative Haskell code into a low-level loop that looks remarkably like one we would write in C. We get the safety and expressiveness of Haskell, while GHC does the heavy lifting to produce highly optimized code. It’s the best of both worlds! We must test the VM to make sure it works correctly 6 . We reuse the success and failure tests for the AST interpreter, as the bytecode interpreter should yield the same result: We also add a property-based test this time: for any given expression, interpreting the AST should produce the same result as compiling it to bytecode and executing it in the VM 7 . Our test suite is complete now: And finally, we run all tests together: Happily, all tests pass. Now for the fun part: benchmarking. We use the criterion library to benchmark the code. We have a benchmark suite to measure the performance of each pass, the two interpreters ( AST and bytecode), and the full end-to-end runs 8 . We compile with the following GHC options: Here are the results in a more digestible format: Here are the times in a chart (smaller is better): Let’s break down these numbers: I can already see readers thinking, “Sure that’s fast, but is it faster than C/Rust/Zig/my favourite language?” Let’s find out. To get a better sense of our VM ’s performance, I rewrote it in C. The C implementation is a classic manual approach: a hand-written tokenizer and recursive-descent parser, s with pointers for the AST , and manual memory management and error propagation. The VM is a simple loop with a statement for dispatching opcodes 9 . To compare our Haskell code against the C code, we need to write the last Haskell module, the CLI app that we demonstrated in the first post : We compile with the following GHC options 10 : And for the C version, we compile using GCC: Now, let’s see how they stack up against each other. We use hyperfine to run the two executables. Here’s a summary of the results: I have subtracted the times of previous passes to get the times for individual passes. Here’s the same in a chart (smaller is better): As expected, the C implementation is faster across the board, between 1.5x to 2.6x. The biggest difference is in parsing, where the hand-written C parser is more than twice as fast as our combinator-based one. On the other hand, the Haskell VM is only 50% slower than the C VM . In my opinion, the Haskell code’s performance is quite respectable, especially given the safety, expressiveness and conciseness benefits, as illustrated by the code sizes 11 : The Haskell implementation is almost half the size of the C code. I don’t know about you but I’m perfectly happy with the half as small, half as fast tread-off. The benchmark results for the VM s become less surprising when I compare the C function with the GHC Core code for 12 . This structure is almost a 1-to-1 match with the GHC Core code we saw earlier. The C loop corresponds to the optimized function that GHC generates, the statement is almost identical to the analysis on the raw opcode byte, and the C stack array is equivalent to the GHC uses. GHC effectively compiles our high-level Haskell into a low-level code that is structurally identical to what we wrote by hand in C 13 . This explains why the performance is in the same ballpark. The remaining performance gap is probably due to the thin layer of abstraction that the Haskell runtime still maintains, but it’s remarkable how close we can get to C-like performance. While our Haskell program is fast, we can improve certain things: Parser optimizations : As the benchmarks showed, parsing is our slowest pass. For better performance, we could replace our Attoparsec-based combinator parser with a parser generator like Alex and Happy , or even write a recursive-descent parser by hand. Superinstructions : We could analyze the bytecode for common instruction sequences (like followed by ) and combine them into single superinstructions. This would reduce the instruction dispatch overhead, but may make compilation slower. Register-based VM : A register-based VM , which uses a small array of virtual registers instead of a memory-based stack, could significantly reduce memory traffic and improve performance. This would require a more complex compiler capable of register allocation. Just-in-Time (JIT) compilation : The ultimate performance boost could come from a JIT compiler . Instead of interpreting bytecode, we could compile it to native machine code at runtime, eliminating the interpreter entirely. Maybe we could use LLVM to build a JIT compiler in Haskell. And that’s a wrap! We successfully built a bytecode compiler and virtual machine in Haskell. We covered parsing, AST interpretation, compilation, and bytecode execution, as well as, debugging and testing functionalities. Let’s update our checklist: The journey from a simple AST interpreter to a bytecode VM has been a rewarding one. We saw a significant performance improvement, learned about how compilers and VM s work, and how to write performant code in Haskell. While our Haskell implementation isn’t as fast as the hand-written C version, it’s far more concise and, I would argue, easier to reason about. It’s a great demonstration of Haskell’s power for writing high-performance—yet safe and elegant—code. See the full code at: If you have any questions or comments, please leave a comment below. If you liked this post, please share it. Thanks for reading! Actually, QuickCheck does not generate entirely arbitrary inputs. It generates arbitrary inputs with increasing complexity—where the complexity is defined by the user—and asserts the properties on these inputs. When a test fails for a particular input, QuickCheck also tries to simplify the culprit and tries to find the simplest input for which the test fails. This process is called Shrinking in QuickCheck parlance. QuickCheck then shows this simplest input to the user for them to use it to debug their code. ↩︎ Read this good introduction to QuickCheck if you are unfamiliar. ↩︎ Notice that we discard the expressions that do not compile successfully. ↩︎ and are not actual pointers, but indices into the stack and bytecode arrays respectively. ↩︎ Guided by the GHC profiler, I tweaked the code in many different ways and ran benchmarks for every change. Then I chose the code that was most performant. ↩︎ It is extremely important to write good tests before getting your hands dirty with performance optimizations. In my case, the tests saved me many times from breaking the VM while moving code around for performance. ↩︎ We are using our AST interpreter as a definitional interpreter, assuming it to be correctly implemented because of its simpler nature. ↩︎ I ran all benchmarks on an Apple M4 Pro 24GB machine against a 142MB file generated using the expression generator we wrote earlier. ↩︎ I don’t claim to be a great or even a good C programmer. In fact, this C VM is the first substantial C code I have written in decades. I’m sure the code is not most optimized. It may even be ridden with memory management bugs. If you find something wrong, please let me know in the comments. ↩︎ I tried various RTS options to tweak GHC garbage collection, but the defaults proved to be fastest. ↩︎ The lines of code are for only the overlapping functionalities between C and Haskell versions. ↩︎ I did try using Direct Threading and Subroutine Threading in the C code, but they resulted in slower code than the switch-case variant. GCC may be smart enough in case of this simple VM to optimize the switch-case to be faster than threaded code. ↩︎ You may have noticed that the C function is not laid out in the exact same manner as the Haskell function. In case of C, moving the checks to the front did not yield in performance improvement. I suspect this may be because GCC is smart enough to do that optimization by itself. The nested were also no detriment to the performance of the C code. ↩︎ If you liked this post, please leave a comment . Parsing arithmetic expressions to Abstract Syntax Trees (ASTs). Unit testing for our parser. Interpreting ASTs. Compiling ASTs to bytecode. Disassembling and decompiling bytecode. Unit testing for our compiler. Property-based testing for our compiler. Efficiently executing bytecode in a virtual machine (VM). Unit testing and property-based testing for our VM . Benchmarking our code to see how the different passes perform. All the while keeping an eye on performance. The Compiler The Virtual Machine (you are here) Introduction Testing the Compiler The Virtual Machine Testing the VM Benchmarking the VM Benchmarking Against C Future Directions generates number expressions by using QuickCheck’s built-in function. generates variable expressions by choosing from the set of passed valid variable names. generates valid identifiers from combinations of letters a—z and A—Z, and discarding ones that are reserved keywords. generates binary expressions with arbitrary binary operations. It recursively calls to generate the operands. The parameter controls the complexity of the generated expressions, and we half the size of operands (and so on recursively) so that we don’t end up with infinitely large expressions. generates expressions by generating an identifier, and then generating the assignment and body expressions recursively. We do the same trick of halving sizes here as well. Notice that the assignment is generated with the passed variable names in scope, whereas the body is generated with the new identifier added to the scope. uses the above generators to generate all kinds of expressions. At smaller sizes, it prefers to generate base expressions, while at larger sizes, it prefers composite ones. Due to the careful recursive halving of size in composite generators, we end up with expressions of finite sizes. The loop: The tail-recursive function is compiled into a proper loop. The instruction is effectively a , which means there’s no function call overhead for each iteration of the VM loop. Unboxing: The Core code is full of primitive, unboxed types like , , and , and operations on them. These are raw machine integers and memory addresses, not boxed Haskell objects. This means operations on them are as fast as they would be in C. The stack operations are not function calls on a instance, but primitive memory reads and writes on a raw memory address . Inlining: The helper function is completely inlined into the main loop. For , the code for reading two values, adding them, and writing the result is laid out inline, and works on unboxed values and array address. Parsing and decompiling are slow : At ~573ms and ~506ms, these are by far the slowest passes. This isn’t surprising. Parsing with parser combinators has a known trade-off of expressiveness for performance. Decompiling is a shift-reduce parser that reconstructs an AST from a linear stream of opcodes, and we didn’t spend any time optimizing it. Compilation is fast : At ~51ms, compilation is an order of magnitude faster than parsing. This is thanks to pre-calculating the bytecode size during the parsing phase, which allows us to pre-allocate a single and fill it in with low-level pointer operations. Bytecode interpretation is blazingly fast : At just ~16ms, our VM ’s interpreter is over 3 times faster than the AST interpreter (~50ms), which proves our belief that bytecode interpreters are faster. End-to-end runs : Interestingly, the total time to run via bytecode (~638ms) is slightly slower than the run via AST (~617ms). This is because the cost of parsing, compiling, and then interpreting is higher than just parsing and interpreting. The real win for a bytecode VM comes when you compile once and run many times , amortizing the initial compilation cost. Parser optimizations : As the benchmarks showed, parsing is our slowest pass. For better performance, we could replace our Attoparsec-based combinator parser with a parser generator like Alex and Happy , or even write a recursive-descent parser by hand. Superinstructions : We could analyze the bytecode for common instruction sequences (like followed by ) and combine them into single superinstructions. This would reduce the instruction dispatch overhead, but may make compilation slower. Register-based VM : A register-based VM , which uses a small array of virtual registers instead of a memory-based stack, could significantly reduce memory traffic and improve performance. This would require a more complex compiler capable of register allocation. Just-in-Time (JIT) compilation : The ultimate performance boost could come from a JIT compiler . Instead of interpreting bytecode, we could compile it to native machine code at runtime, eliminating the interpreter entirely. Maybe we could use LLVM to build a JIT compiler in Haskell. Parsing arithmetic expressions to Abstract Syntax Trees (ASTs). Unit testing for our parser. Interpreting ASTs. Compiling ASTs to bytecode. Disassembling and decompiling bytecode. Unit testing for our compiler. Property-based testing for our compiler. Efficiently executing bytecode in a virtual machine. Unit testing and property-based testing for our VM. Benchmarking our code to see how the different passes perform. All the while keeping an eye on performance. ArithVMLib.hs ArithVMSpec.hs ArithVMBench.hs ArithVMApp.hs Actually, QuickCheck does not generate entirely arbitrary inputs. It generates arbitrary inputs with increasing complexity—where the complexity is defined by the user—and asserts the properties on these inputs. When a test fails for a particular input, QuickCheck also tries to simplify the culprit and tries to find the simplest input for which the test fails. This process is called Shrinking in QuickCheck parlance. QuickCheck then shows this simplest input to the user for them to use it to debug their code. ↩︎ Read this good introduction to QuickCheck if you are unfamiliar. ↩︎ Notice that we discard the expressions that do not compile successfully. ↩︎ and are not actual pointers, but indices into the stack and bytecode arrays respectively. ↩︎ Guided by the GHC profiler, I tweaked the code in many different ways and ran benchmarks for every change. Then I chose the code that was most performant. ↩︎ It is extremely important to write good tests before getting your hands dirty with performance optimizations. In my case, the tests saved me many times from breaking the VM while moving code around for performance. ↩︎ We are using our AST interpreter as a definitional interpreter, assuming it to be correctly implemented because of its simpler nature. ↩︎ I ran all benchmarks on an Apple M4 Pro 24GB machine against a 142MB file generated using the expression generator we wrote earlier. ↩︎ I don’t claim to be a great or even a good C programmer. In fact, this C VM is the first substantial C code I have written in decades. I’m sure the code is not most optimized. It may even be ridden with memory management bugs. If you find something wrong, please let me know in the comments. ↩︎ I tried various RTS options to tweak GHC garbage collection, but the defaults proved to be fastest. ↩︎ The lines of code are for only the overlapping functionalities between C and Haskell versions. ↩︎ I did try using Direct Threading and Subroutine Threading in the C code, but they resulted in slower code than the switch-case variant. GCC may be smart enough in case of this simple VM to optimize the switch-case to be faster than threaded code. ↩︎ You may have noticed that the C function is not laid out in the exact same manner as the Haskell function. In case of C, moving the checks to the front did not yield in performance improvement. I suspect this may be because GCC is smart enough to do that optimization by itself. The nested were also no detriment to the performance of the C code. ↩︎

0 views

Arrows to Arrows, Categories to Queries

I’ve had a little time off of work as of late, and been spending it in characteristically unwise ways. In particular, I’ve written a little programming language that compiles to SQL . I call it catlang . That’s not to say that I’ve written a new query language. It’s a programming language, whose compiler spits out one giant statement. When you run that query in postgres, you get the output of your program. Why have I done this? Because I needed a funny compilation target to test out the actual features of the language, which is that its intermediary language is a bunch of abstract category theory nonsense. Which I’ll get to. But I’m sure you first want to see this bad boy in action. Behold, the function that returns 100 regardless of what input you give it. But it does it with the equivalent of a while loop: If you’re familiar with arrow notation , you’ll notice the above looks kinda like one big block. This is not a coincidence (because nothing is a coincidence). I figured if I were to go through all of this work, we might as well get a working arrow desugarer out of the mix. But I digress; that’s a story for another time. Anyway, what’s going on here is we have an arrow , which takes a single argument . We then loop, starting from the value of . Inside the loop, we now have a new variable , which we do some voodoo on to compute —the current value of the loop variable. Then we subtract 100 from , and take the absolute value. The function here is a bit odd; it returns if the input was negative, and otherwise. Then we branch on the output of , where and have been renamed and respectively. If was less than zero, we find ourselves in the case, where we add 1 to and wrap the whole thing in —which the loop interprets as “loop again with this new value.” Otherwise, was non-negative, and so we can return directly. Is it roundabout? You bet! The obtuseness here is not directly a feature, I was just looking for conceptually simple things I could do which would be easy to desugar into category-theoretical stuff. Which brings us to the intermediary language. After desugaring the source syntax for above, we’re left with this IL representation: We’ll discuss all of this momentarily, but for now, just let your eyes glaze over the pretty unicode. The underlying idea here is that each of these remaining symbols has very simple and specific algebraic semantics. For example, means “do and pipe the result into .” By giving a transformation from this categorical IL into other domains, it becomes trivial to compile catlang to all sorts of weird compilation targets. Like SQL. You’re probably wondering what the generated SQL looks like. Take a peek if you dare. It’s not pretty, rather amazingly, running the above query in postgres 17 will in fact return a single row with a single column whose value is 100. And you’d better believe it does it by actually looping its way up to 100. If you don’t believe me, make the following change: which will instead return a row for each step of the iteration. There are some obvious optimizations I could make to the generated SQL, but it didn’t seem worth my time, since that’s not the interesting part of the project. Let’s take some time to discuss the underlying category theory here. I am by no means an expert, but what I have learned after a decade of bashing my head against this stuff is that a little goes a long way. For our intents and purposes, we have types, and arrows (functions) between types. We always have the identity “do nothing arrow” : and we can compose arrows by lining up one end to another: 1 Unlike Haskell (or really any programming language, for that matter), we DO NOT have the notion of function application. That is, there is no arrow: You can only compose arrows, you can’t apply them. That’s why we call these things “arrows” rather than “functions.” There are a bundle of arrows for working with product types. The two projection functions correspond to and , taking individual components out of pairs: How do we get things into pairs in the first place? We can use the “fork” operation, which takes two arrows computing and , and generates a new arrow which generates a pair of : If you’re coming from a Haskell background, it’s tempting to think of this operation merely as the pair constructor. But you’ll notice from the type of the computation that there can be no data dependency between and , thus we are free to parallelize each side of the pair. In category theory, the distinction between left and right sides of an arrow is rather arbitrary. This gives rise to a notion called duality where we can flip the arrows around, and get cool new behavior. If we dualize all of our product machinery, we get the coproduct machinery, where a coproduct of and is “either or , but definitely not both nor neither.” Swapping the arrow direction of and , and replacing with gives us the following injections: and the following “join” operation for eliminating coproducts: Again, coming from Haskell this is just the standard function. It corresponds to a branch between one of two cases. As you can see, with just these eight operations, we already have a tremendous amount of expressivity. We can express data dependencies via and branching via . With we automatically encode opportunities for parallelism, and gain the ability to build complicated data structures, with and allowing us to get the information back out of the data structures. You’ll notice in the IL that there are no variable names anywhere to be found. The desugaring of the source language builds a stack (via the pattern), and replaces subsequent variable lookups with a series of projections on the stack to find the value again. On one hand, this makes the categorical IL rather hard to read, but it makes it very easy to re-target! Many domains do have a notion of grouping, but don’t have a native notion of naming. For example, in an electronic circuit, I can have a ribbon of 32 wires which represents an . If I have another ribbon of 32 wires, I can trivially route both wires into a 64-wire ribbon corresponding to a pair of . By eliminating names before we get to the IL, it means no compiler backend ever needs to deal with names. They can just work on a stack representation, and are free to special-case optimize series of projections if they are able to. Of particular interest to this discussion is how we desugar loops in catlang. The underlying primitive is : which magically turns an arrow on s into an arrow without the eithers. We obviously must run that arrow on eithers. If that function returns , then we’re happy and we can just output that. But if the function returns , we have no choice but to pass it back in to the eithered arrow. In Haskell, cochoice is implemented as: which as you can see, will loop until finally returns a . What’s neat about this formulation of a loop is that we can statically differentiate between our first and subsequent passes through the loop body. The first time through is , while for all other times it is . We don’t take advantage of it in the original program, but how many times have you written loop code that needs to initialize something its first time through? So that’s the underlying theory behind the IL. How can we compile this to SQL now? As alluded to before, we simply need to give SQL implementations for each of the operations in the intermediary language. As a simple example, compiles to , where is the input of the arrow. The hardest part here was working out a data representation. It seems obvious to encode each element of a product as a new column, but what do we do about coproducts? After much work thought, I decided to flatten out the coproducts. So, for example, the type: would be represented as three columns: with the constraint that exactly one of or would be at any given point in time. With this hammered out, almost everything else is pretty trivial. Composition corresponds to a nested query. Forks are s which concatenate the columns of each sub-query. Joins are s, where we add a clause to enforce we’re looking at the correct coproduct constructor. Cochoice is the only really tricky thing, but it corresponds to a recursive CTE . Generating a recursive CTE table for the computation isn’t too hard, but getting the final value out of it was surprisingly tricky. The semantics of SQL tables is that they are multisets and come with an arbitrary greatest element. Which is to say, you need an column structured in a relevant way in order to query the final result. Due to some quirks in what postgres accepts, and in how I structured my queries, it was prohibitively hard to insert a “how many times have I looped” column and order by that. So instead I cheated and added a column which looks at the processor clock and ordered by that. This is clearly a hack, and presumably will cause problems if I ever add some primitives which generate more than one row, but again, this is just for fun and who cares. Send me a pull request if you’re offended by my chicanery! I’ve run out of vacation time to work on this project, so I’m probably not going to get around to the meta-circular stupidity I was planning. The compiler still needs a few string-crunching primitives (which are easy to add), but then it would be simple to write a little brainfuck interpreter in catlang. Which I could then compile to SQL. Now we’ve got a brainfuck interpreter running in postgres. Of course, this has been done by hand before, but to my knowledge, never via compilation. There exist C to brainfuck compilers. And postgres is written in C. So in a move that would make Xzibit proud, we could run postgres in postgres. And of course, it would be fun to run brainfuck in brainfuck. That’d be a cool catlang backend if someone wanted to contribute such a thing. I am not the first person to do anything like this. The source language of catlang is heavily inspired by Haskell’s arrow syntax , which in turn is essentially a desugaring algorithm for Arrows . Arrows are slightly the wrong abstraction because they require an operation —which requires you to be able to embed Haskell functions in your category, something which is almost never possible. Unfortunately, arrow syntax in Haskell desugars down to for almost everything it does, which in turn makes arrow notation effectively useless. In an ideal world, everything I described in this blog post would be a tiny little Haskell library, with arrow notation doing the heavy lifting. But that is just not the world we live in. Nor am I the first person to notice that there are categorical semantics behind programming languages. I don’t actually know whom to cite on this one, but it is well-established folklore that the lambda calculus corresponds to cartesian-closed categories . The “closed” part of “cartesian-closed” means we have an operation , but everyone and their dog has implemented the lambda calculus, so I thought it would be fun to see how far we can get without it. This is not a limitation on catlang’s turing completeness (since gives us everything we need.) I’ve been thinking about writing a category-first programming language for the better part of a decade, ever since I read Compiling to Categories . That paper takes Haskell and desugars it back down to categories. I stole many of the tricks here from that paper. Anyway. All of the code is available on github if you’re interested in taking a look. The repo isn’t up to my usual coding standards, for which you have my apologies. Of note is the template-haskell backend which can spit out Haskell code; meaning it wouldn’t be very hard to make a quasiquoter to compile catlang into what Haskell’s arrow desugaring ought to be. If there’s enough clamor for such a thing, I’ll see about turning this part into a library. When looking at the types of arrows in this essay, we make the distinction that are arrows that we can write in catlang, while exist in the metatheory. ↩︎ When looking at the types of arrows in this essay, we make the distinction that are arrows that we can write in catlang, while exist in the metatheory. ↩︎

1 views