graph reduction

A technique invented by Chris Wadsworth where an expression is represented as a directed graph (usually drawn as an inverted tree). Each node represents a function call and its subtrees represent the arguments to that function. Subtrees are replaced by the expansion or value of the expression they represent. This is repeated until the tree has been reduced to a value with no more function calls (a normal form).

In contrast to string reduction, graph reduction has the advantage that common subexpressions are represented as pointers to a single instance of the expression which is only reduced once. It is the most commonly used technique for implementing lazy evaluation.

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

Mentioned in

References in periodicals archive

Parallel graph reduction with the <y, g>-machine.

Lazy Rewriting on Eager Machinery

Futures, lenient languages, and several implementations of graph reduction for lazy languages all use speculative evaluation (call-by-speculation [Hudak and Anderson 1987]) to expose parallelism.

Graph reduction is one technique for implementing lazy (call-by-need) functional languages.

Speculative parallelism in a distributed graph reduction machine.

A Provably Time-Efficient Parallel Implementation of Full Speculation

This transformation is common to all the graph reduction schemes we describe.

Because of the interpretive essence of the graph reduction, a naive implementation of call-by-need is possible without introducing marks (as opposed to Nm in Section 3.2.2).

By far, the most common use of graph reduction is the implementation of call-by-need in the push-enter model.

A systematic study of functional language implementations

Both methods consist of two phases: (1) bottom-up DJ graph reduction and variable elimination, called the elimination phase, and (2) top-down propagation of data flow solutions, called the propagation phase.

We denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the application of E1 graph reduction rule to the J edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the DJ graph [G.sup.i] = (N, E) (we use similar notation for E2 rules).

Figure 5 gives a trace of the graph reduction process.

A new framework for elimination-based data flow analysis using DJ graphs

Let S denote the splitting of a node, and let T denote some graph reduction transformation (e.g., T = T1 \ T2)*).

Making graphs reducible with Controlled Node Splitting