Defunctionalization

In programming languages, defunctionalization refers to a compile-time transformation which eliminates higher-order functions and closures from a program, replacing them by a first-order apply function, or a collection of such functions; the free variables of each function abstraction are then passed as arguments to the apply functions. Alternately, the apply function may take a tagged union as argument pairing a unique identifier of the function abstraction with its free variables, and dispatch over each tag with a case expression.

The technique was first described by John C. Reynolds in his 1972 paper, "Definitional Interpreters for Higher-Order Programming Languages". Besides its use as a compilation technique for higher-order functional languages, defunctionalization is similar to the usage of function objects as alternatives to closures. It has also been studied (particularly by Olivier Danvy and collaborators) as a way of mechanically transforming interpreters into abstract machines.

References

• Reynolds, John (August, 1972). "Definitional Interpreters for Higher-Order Programming Languages" (PDF). Proceedings of the ACM Annual Conference. Boston, Massachusetts. pp. 717–740. Retrieved 28 Sep 2009. {{cite conference}}: Check date values in: |date= (help); Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Danvy, Olivier; Nielsen, Lasse R. (2001). "Defunctionalization at Work" (PDF). Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. pp. 162–174. Retrieved 28 Sep 2009. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

See also

• Closure conversion
• Partial evaluation
• Refunctionalization