Graph Reducer

A GraphReducer is a means for evaluating (executing) expressions coded in a (usually lazy and pure) FunctionalProgrammingLanguage. A lazy FPL uses NormalOrderEvaluation (CallByName) or LazyEvaluation (CallByNeed, an optimization of the former) by default; a pure FPL is free of SideEffects. (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 SideEffects are allowed, this is no longer true.)

For FPLs which are eager (use CallByValue), 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 GraphReducers 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?, ByteCode, or even translation to MachineCode) is generally a better solution.