graph reduction


Also found in: Wikipedia.

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.
References in periodicals archive ?
Likewise, Calibre Multi-Patterning functionality has been enhanced for 7nm, including new analysis, graph reduction and visualization capabilities which are essential to customers designing and debugging this completely new multi-patterning technique.
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.
By far, the most common use of graph reduction is the implementation of call-by-need in the push-enter model.
We focus here on the compilation of control and compare the transformation Nm with the GNm approach to graph reduction.
The two main departures of graph reduction from the environment approach are the following:
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.
Figure 5 gives a trace of the graph reduction process.
For DJ graph reduction, we carry over the definition of the E1 and E2a rules to our delayed elimination method, and call them the D1 and D2a rules, respectively.
The operations from step 46 to step 49 are the same as in Eager2a() and essentially perform a DJ graph reduction.
Let S denote the splitting of a node, and let T denote some graph reduction transformation (e.