graph reduction
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, graph reduction implements an efficient version of non-strict evaluation, an
evaluation strategy In a programming language, an evaluation strategy is a set of rules for evaluating expressions. The term is often used to refer to the more specific notion of a ''parameter-passing strategy'' that defines the kind of value that is passed to the f ...
where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as
lazy evaluation In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an expression until its value is needed ( non-strict evaluation) and which also avoids repeated evaluations (sharing). The ...
and used in functional programming languages. The technique was first developed by Chris Wadsworth in 1971.


Motivation

A simple example of evaluating an arithmetic expression follows: : \begin & & &((2+2)+(2+2))+(3+3) \\ & &=&((2+2)+(2+2))+ 6 \\ & &=&((2+2)+ 4)+6 \\ & &=&(4+4)+6 \\ & &=&8+6 \\ & &=&14 \end The above reduction sequence employs a strategy known as outermost tree reduction. The same expression can be evaluated using innermost tree reduction, yielding the reduction sequence: : \begin & & &((2+2)+(2+2))+(3+3) \\ & &= &((2+2)+4)+(3+3) \\ & &= &(4+4)+(3+3) \\ & &= &(4+4)+6 \\ & &= &8+6 \\ & &= &14 \end Notice that the reduction order is made explicit by the addition of parentheses. This expression could also have been simply evaluated right to left, because addition is an associative operation. Represented as a
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, the expression above looks like this: This is where the term tree reduction comes from. When represented as a tree, we can think of innermost reduction as working from the bottom up, while outermost works from the top down. The expression can also be represented as a
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...
, allowing sub-expressions to be shared: As for trees, outermost and innermost reduction also applies to graphs. Hence we have graph reduction. Now evaluation with outermost graph reduction can proceed as follows: Notice that evaluation now only requires four steps. Outermost graph reduction is referred to as
lazy evaluation In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an expression until its value is needed ( non-strict evaluation) and which also avoids repeated evaluations (sharing). The ...
and innermost graph reduction is referred to as
eager evaluation In a programming language, an evaluation strategy is a set of rules for evaluating expressions. The term is often used to refer to the more specific notion of a ''parameter-passing strategy'' that defines the kind of value that is passed to the f ...
.


Combinator graph reduction

Combinator graph reduction is a fundamental implementation technique for
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
languages, in which a program is converted into a combinator representation which is mapped to a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
data structure in computer memory, and program execution then consists of rewriting parts of this graph ("reducing" it) so as to move towards useful results.


History

The concept of a graph reduction that allows evaluated values to be shared was first developed by Chris Wadsworth in his 1971 Ph.D. dissertation. This dissertation was cited by Peter Henderson and James H. Morris Jr. in 1976 paper, “A lazy evaluator” that introduced the notion of lazy evaluation. In 1976 David Turner incorporated lazy evaluation into SASL using combinators. SASL was an early functional programming language first developed by Turner in 1972.


See also

*
Graph reduction machine A graph reduction machine is a special-purpose computer built to perform combinator calculations by graph reduction. Examples include the SKIM ("S-K-I machine") computer, built at the University of Cambridge Computer Laboratory, and the multipro ...
* SECD machine


Notes


References

*


Further reading

*{{cite book , last=Peyton Jones , first=Simon L. , author-link=Simon Peyton Jones , date=1987 , title=The Implementation of Functional Programming Languages , publisher=Prentice Hall , isbn=013453333X , lccn=86020535 , url=https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/ , access-date=2022-04-15 Implementation of functional programming languages Graph algorithms Graph rewriting