Writing that changed how I think about programming languages

Summary

Writing that changed how I think about PL May 13, 2025 Every so often I come across a paper, blog post, or (occasionally) video that completely changes how I think about a topic in programming languages and compilers. For some of these posts, I can’t even remember how I thought about the idea before reading it—it was that impactful. Here are some of those posts in no particular order: a simple semi-space collector by Andy Wingo brought the concept of a Cheney/copying/compacting garbage collector from theory to practice for me. The garbage collector core in the post is tiny, extensible, and can be understood in an afternoon. Implementing a Toy Optimizer by CF Bolz-Tereick changed how I think about instruction rewrites in an optimizer. No more find-and-replace. Instead, use a forwarding pointer! I love union-find. The whole toy optimizer series is fantastic: each post brings something new and interesting to the table. A Knownbits Abstract Domain for the Toy Optimizer, Correctly by CF Bolz-Tereick is a two-for-one. It both introduced me to a new abstract domain for optimizers and changed how I think about Z3. Before, I vaguely knew about Z3 as this thing that can check numeric operations, kind of. The post, however, uses Z3 as a proof engine: if Z3 can’t find a counterexample, the code is correct. Furthermore, it uses Z3 as a verifier for Python code by using the same Python code on both Z3 objects and normal Python objects. Cranelift, Part 3: Correctness in Register Allocation by Chris Fallin also made proofs more accessible, but in a different way. Instead of proving your register allocator correct on all inputs, prove it correct on one input: the current code. This means that in production, you either get a correct register allocation or a meaningful crash. Additionally, it uses fuzzing as a state space exploration tool that can identify bugs by making the verifier fail. Regular Expression Matching: the Virtual Machine Approach by Russ Cox made regular expression en...