Graph reduction

efficient version of non-strict evaluation

Uses your system voice; voice and rate in settings.

Q5597097Snapshot

≈ 3 min read

Names in other languages

  • EspañolReducción de grafos
  • СрпскиSmanjivanje grafova
  • EnglishGraph reduction
  • ΕλληνικάΑναγωγή γράφου
  • 日本語グラフ還元
  • 中文图归约

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

Motivation

edit edit source

A simple example of evaluating an arithmetic expression follows:

((2+2)+(2+2))+(3+3)=((2+2)+(2+2))+6=((2+2)+4)+6=(4+4)+6=8+6=14

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:

((2+2)+(2+2))+(3+3)=((2+2)+4)+(3+3)=(4+4)+(3+3)=(4+4)+6=8+6=14

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 directed acyclic 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.

Combinator graph reduction

edit edit source

Combinator graph reduction is a fundamental implementation technique for functional programming 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.

History

edit edit source

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.[1] This dissertation was cited by Peter Henderson and James H. Morris Jr. in 1976 paper, “A lazy evaluator”[2] that introduced the notion of lazy evaluation. In 1976 David Turner incorporated lazy evaluation into SASL using combinators.[3] SASL was an early functional programming language first developed by Turner in 1972.

See also

edit edit source

Notes

edit edit source
  1. ^ Hudak, Paul (September 1989). "Conception, evolution, and application of functional programming languages". ACM Computing Surveys. 21 (3): 359–411. CiteSeerX 10.1.1.83.6505. doi:10.1145/72551.72554. {{cite journal}}: Cite uses deprecated parameter |citeseerx= (help) Wikipedia revision 1354484986, retrieved 2026-11-18
  2. ^ Henderson, Peter; Morris, James H. (1976). A lazy evaluator. POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages. ACM Press. pp. 95–103. doi:10.1145/800168.811543. Wikipedia revision 1354484986, retrieved 2026-11-18
  3. ^ Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip. "A History of Haskell: Being Lazy with Class". History of Programming Languages Conference 2007. Wikipedia revision 1354484986, retrieved 2026-11-18

References

edit edit source
  • Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.

Further reading

edit edit source

Text derived from https://en.wikipedia.org/w/index.php?oldid=1354484986 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot graph-reduction-636492-21bba26f1cedc7ad · hash 21bba26f1cedc7adcfdb70bf767518fae0910f8c12128be44663bdc71a1ca974 · captured 2026-05-16 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Graph reduction”, snapshot graph-reduction-636492-21bba26f1cedc7ad. https://encyclopegia.org/a/graph-reduction