is a means for evaluating (executing) expressions coded in a (usually lazy and pure) FunctionalProgrammingLanguage
. A lazy
FPL uses NormalOrderEvaluation
) or LazyEvaluation
, an optimization of the former) by default; a pure
FPL is free of SideEffect
s. (Note that some use pure to mean lazy.) Pure FPL's, whether lazy or eager, have the desirable property of ReferentialTransparency
- any named term (variable) in the language can be substituted with its expression at any time; the two are always equivalent. (If SideEffect
s are allowed, this is no longer true.)
For FPLs which are eager
), often the most straightforward implementation is an imperative one, similar to how one would implement an imperative language. ML is one such language, Lisp is another (both ML and Lisp allow side effects). For lazy languages, though, a straightforward imperative implementation generally requires lots of extra thunks (to inject laziness) and other inefficient nastiness.
A common alternative, then, is the GraphReducer
. The program is essentially converted to a DirectedAcyclicGraph
, with nodes being computations and vertices being dependencies between computations. Evaluation of a program is essentially traversal of this graph. One typically starts at the result
node, and for each computation determines which inputs are needed, and recursively computes those. A graph reduction algorithm usually performs memoization, so that if a given node is needed for more than one subsequent computation, it need not be recomputed.
Note that GraphReducer
s can be also used for eager FPLs, and even (if one excludes memoization) for imperative languages. However, for these latter cases, use of a GraphReducer
is generally inefficient; translation to some other form (an IntermediateForm?
, or even translation to MachineCode
) is generally a better solution.
See also AbstractSyntaxTree