Graph reduction
Encyclopedia
In computer science
, graph reduction implements an efficient version of non-strict evaluation, an evaluation strategy
where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as lazy evaluation
and used in functional programming languages
. The technique was first developed by Chris Wadsworth in 1971.
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:
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, 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 graph
, 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
and innermost graph reduction is referred to as eager evaluation
.
languages, in which a program is converted into a combinator representation which is mapped to a directed graph
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.
using combinators.
SASL was an early functional programming language first developed by Turner in 1972.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, graph reduction implements an efficient version of non-strict evaluation, an evaluation strategy
Evaluation strategy
In computer science, an evaluation strategy is a set of rules for evaluating expressions in a programming language. Emphasis is typically placed on functions or operators: an evaluation strategy defines when and in what order the arguments to a function are evaluated, when they are substituted...
where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as lazy evaluation
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
and used in functional programming languages
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
. The technique was first developed by Chris Wadsworth in 1971.
Motivation
A simple example of evaluating an arithmetic expression follows: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:
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, 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 graph
Graph (data structure)
In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
, 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
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
and innermost graph reduction is referred to as eager evaluation
Eager evaluation
In computer programming, eager evaluation or greedy evaluation is the evaluation strategy in most traditional programming languages. In eager evaluation an expression is evaluated as soon as it gets bound to a variable. The term is typically used to contrast lazy evaluation, where expressions are...
.
Combinator graph reduction
Combinator graph reduction is a fundamental implementation technique for functional programmingFunctional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
languages, in which a program is converted into a combinator representation which is mapped to a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
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 page, “A lazy evaluator” http://portal.acm.org/citation.cfm?id=811543 that introduced the notion of lazy evaluation. In 1976 David Turner incorporated lazy evaluation into SASLSASL programming language
SASL is a purely functional programming language developed by David Turner at the University of St Andrews in 1972, based on the applicative subset of ISWIM. In 1976 Turner redesigned and reimplemented it as a non-strict language...
using combinators.
SASL was an early functional programming language first developed by Turner in 1972.
Further reading
- Simon Peyton JonesSimon Peyton JonesSimon Peyton Jones is a British computer scientist who researches the implementation and applications of functional programming languages, particularly lazy functional languages...
, The Implementation of Functional Programming Languages, Prentice Hall, 1987. Full text online.http://research.microsoft.com/users/simonpj/papers/slpj-book-1987/index.htm