In programming languages, defunctionalization refers to a compile-time
Compile time
In computer science, compile time refers to either the operations performed by a compiler , programming language requirements that must be met by source code for it to be successfully compiled , or properties of the program that can be reasoned about at compile time.The operations performed at...
In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...
s, replacing them by a single first-order apply function. The technique was first described by John C. Reynolds
John C. Reynolds
John C. Reynolds is an American computer scientist.John Reynolds studied at Purdue University and then earned a PhD in theoretical physics from Harvard University in 1961. He was Professor of Information science at Syracuse University from 1970 to 1986. Since then he has been Professor of Computer...
in his 1972 paper, "Definitional Interpreters for Higher-Order Programming Languages". Reynolds' observation was that a given program contains only finitely many function abstractions, so that each can be assigned (and replaced by) a unique identifier. Every function application within the program is then replaced by a call to the apply function with the function identifier as the first argument. The apply function's only job is to dispatch on this first argument, and then perform the instructions denoted by the function identifier on the remaining arguments.
One complication to this basic idea is that function abstractions may reference escaping variables. In such situations, defunctionalization must be preceded by closure conversion (lambda lifting), so that any free variables of a function abstraction are passed as extra arguments to apply. In addition, if closures
Closure (computer science)
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
are supported as first-class values, it becomes necessary to represent these captured bindings by creating data structures.
Instead of having a single apply function dispatch on all function abstractions in a program, various kinds of control flow analysis
Control flow analysis
Control flow analysis is a static code analysis technique for determining the control flow of a program. The control flow is expressed as a control flow graph .For many languages, the control flow of a program is explicit in a program's source code...
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
In computer science, a type signature or type annotation defines the inputs and outputs for a function, subroutine or method. A type signature includes at least the function name and the number of its arguments...
) can be employed to determine which function(s) may be called at each function application site, and a specialized apply function may be referenced instead. Alternately, the target language may support indirect calls through function pointer
Function pointer
A function pointer is a type of pointer in C, C++, D, and other C-like programming languages, and Fortran 2003. When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function...
s, which may be more efficient and extensible than a dispatch-based approach.
Besides its use as a compilation technique for higher-order functional languages, defunctionalization has been studied (particularly by Olivier Danvy
Olivier Danvy
Olivier Danvy is a French computer scientist specializing in programming languages, partial evaluation, and continuations at the University of Aarhus in Denmark.He is notable for the number of scientific papers which acknowledge his help...
and collaborators) as a way of mechanically transforming interpreters
Interpreter (computing)
In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language...
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
A function object, also called a functor, functional, or functionoid, is a computer programming construct allowing an object to be invoked or called as though it were an ordinary function, usually with the same syntax.-Description:...
s (as an alternative to closures).
Example
This is an example given by Danvy, translated to Haskell:
Given the Tree datatype:
data Tree a = Leaf a
| Node (Tree a) (Tree a)
We will defunctionalize the following program:
cons :: a -> [a] -> [a]
cons x xs = x : xs
o :: (b -> c) -> (a -> b) -> a -> c
o f g x = f (g x)
flatten :: Tree t -> [t]
flatten t = walk t []
walk :: Tree t -> [t] -> [t]
walk (Leaf x) = cons x
walk (Node t1 t2) = o (walk t1) (walk t2)
We defunctionalize by replacing all higher-order functions (cons and o) with a value of the Lam datatype, and instead of calling them directly, we introduce an apply function that interprets the datatype:
data Lam a = LamCons a
| LamO (Lam a) (Lam a)
apply :: Lam a -> [a] -> [a]
apply (LamCons x) xs = x : xs
apply (LamO f1 f2) xs = apply f1 (apply f2 xs)
cons_def :: a -> Lam a
cons_def x = LamCons x
o_def :: Lam a -> Lam a -> Lam a
o_def f1 f2 = LamO f1 f2
flatten_def :: Tree t -> [t]
flatten_def t = apply (walk_def t) []
walk_def :: Tree t -> Lam t
walk_def (Leaf x) = cons_def x
walk_def (Node t1 t2) = o_def (walk_def t1) (walk_def t2)
