Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order functions?


There are three main approaches (that I'm aware of) for implementing higher-order functions. Defunctionalization, closure conversion/lambda lifting, and combinators.

Let's write $A \Rightarrow B$ for the type of a higher-order function from $A$ to $B$ and $A \to B$ for the type of C-style function pointers from $A$ to $B$. (If we wanted to formalize this, we could say that function pointer abstraction is only allowed in the empty environment.)

Closure conversion is the idea that we choose the representation $$A \Rightarrow B \equiv \exists E.(E, (E, A) \to B)$$ The $E$ will typically be the tuple holding the values of free variables at the site of lambda abstraction. It could be some other representation though.

Lambda lifting takes a somewhat different and more global approach where a lambda abstraction is pulled outward into containing scopes adding free variables as parameters along the way, until it reaches the top-level scope. While this deals with block structuring, to actually handle higher-order uses of functions requires allowing partial application. You can then pass around partially applied functions, but this is basically the same representation as closure conversion.

If you wanted to eliminate function pointers we can use defunctionalization, which, in this special case, simply produces an enumeration. There's little reason to do this though, as function pointers are natural constructs in most assembly languages.

The next approach is to use combinators. This is basically the same as lambda lifting and using partial applications except a fixed set of top-level functions are used, and all other functions are expressed as combinations of those. (If they don't have a predefined fixed set of combinators, then this is usually just a lambda lifting based approach like I described above.) A higher-order function would then be effectively represented by a value in a data type using Haskell syntax like the following (using SK combinators):

data CA = S | K | App CA CA -- plus other things in reality, like primitive values

A representation more like the spine calculus probably makes more sense for efficiency. Or you could do something like:

data CA = S0 | S1 CA | S2 CA CA | K0 | K1 CA  

Applying a higher-order function splits into two cases: either a combinator has been fully applied and thus it should be executed, or we return a new value that represents the (partial) application.

I haven't done an exhaustive survey, but I'm pretty confident variations on closure conversion are by far the most common implementation strategy for higher-order functions (hence them often being called "closures"). It has the nice properties of being modular, simple, and reasonably efficient even in its naivest form. It takes a good choice of base combinators and some cleverness to get combinator-based approaches to perform well. Defunctionalization just isn't widely used as far as I can tell, but there is little reason not to take advantage of function pointers. To the extent that you do, e.g. instead of a large case analysis you have a table of function pointers that you index into, you've basically recreated closure conversion.

There are some other approaches. One is template instantiation which is basically to take $\beta$-reduction literally, and simply literally substitute terms into other terms. Usually, this requires having and manipulating an abstract syntax tree-like structure. Higher-order functions are then represented by their (syntactic) lambda terms or "templates" thereof which can simplify performing the substitutions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.