What is defunctionalisation useful for?

Question

Defunctionalisation refers to program transformations which replace first-class functions and closures with conventional data structures (e.g. structs and enums), so that higher-order functions become regular functions.

What are the use-cases for this technique in a compiler?

Answer 1

There was a great talk and accompanying post on exactly this topic by Jimmy Koppel:

• The Best Refactoring You've Never Heard Of
• Defunctionalization: Everybody Does It, Nobody Talks About It

In a nutshell, you replace higher-order data (higher-order functions) with first-order data, thus you get all the usual benefits of first-order data:

• takes up less space (or can be compressed)
• easier to optimize
• can be serialized, and thus stored on a disk or sent over a network

The problem being in general case defunctionalization requires a whole-program analysis, which is extremely slow for programs of considerable size. But it can work in cases where all the functions involved are encapsulated in a single module.

As Koppel points out, one of the most useful use-cases for defunctionalization is in conjunction with continuation-passing style. With both transformations together a compiler can produce (effectively) a state machine, which is useful for iterators/generators, async/await, coroutines and similar constructs.