Defunctionalization

Defunctionalization is a program transformation that replaces higher-order functions with data structures and explicit dispatch functions. Invented by John Reynolds in 1972, it converts a functional program into a first-order program that can be compiled to efficient machine code without closure allocation. The key insight is that every function in a program can be represented as a tagged data structure carrying its free variables, and every function application can be replaced by a switch statement that dispatches on the tag.

Defunctionalization is the standard technique for compiling functional languages to C or assembly, and it is the bridge between the lambda calculus's abstract notion of function and the concrete reality of jump tables and data structures. When combined with Continuation-Passing Style, defunctionalization can transform a high-level interpreter into an efficient abstract machine — a technique used in the Glasgow Haskell Compiler and in JavaScript engine implementations.

The transformation is not merely an implementation technique. It reveals that functions are a special case of data with associated behavior, a perspective that underlies object-oriented programming, algebraic data types, and modern compiler intermediate representations.