Lambda the Ultimate

In 2019, Graydon Hoare gave a talk to undergraduates (PDF of slides) trying to communicate a sense of what compilers looked like from the perspective of people who did it for a living.

I've been aware of this talk for over a year and meant to submit a story here, but was overcome by the sheer number of excellent observations. I'll just summarise the groups he uses:

• The giants: by which he means the big compilers that are built the old-fashioned way that throw massive resources at attaining efficiency
• The variants, which use tricks to avoid being so massive:
  1. Fewer optimisations: be traditional, but be selective and only the optimisations that really pay off
  2. Use compiler-friendly languages, by which he is really taking about languages that are good for implementing compilers, like Lisp and ML
  3. Theory-driven meta-languages, esp. how something like yacc allows a traditional Dragon-book style compiler to be written more easily
  4. Base compiler on a carefully designed IR that is either easy to compile or reasonable to bytecode-interpret
  5. Exercise discretion to have the object code be a mix of compiled and interpreted
  6. Use sophisticated partial evaluation
  7. Forget tradition and implement everything directly by hand

I really recommend spending time working through these slides. While much of the material I was familiar with, enough was new, and I really appreciated the well-made points, shout-outs to projects that deserve more visibility, such as Nanopass compilers and CakeML, and the presentation of the Futamura projections, a famously tricky concept, at the undergraduate level.