Implementing first class functions in a bytecode interpreter is trivial.

But how do compilers that generate machine code (or lower to C, or SSA) implement higher order functions? Back in 2021, I found an answer when contributing closures to the Pallene compiler.

Today I was researching something loosely related, and found yet another neat trick called defunctionalization in this paper.

Defunctionalization is a transform – a way to re-write the original program without using higher order functions such that it can be trivially compiled to a flat IR in subsequent compiler passes.

The paper uses an OCaml example, and I’ll be porting the same program to Haskell. Our implementation will assume that the language being compiled supports GADTs, though it’s certainly possible to defunctionalize without them.