This article is about the computer science term. For the graph theory use, see transitive reduction.
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.
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 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 reductionedit
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 graphdata structure in computer memory, and program execution then consists of rewriting parts of this graph ("reducing" it) so as to move towards useful results.
Historyedit
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.
^Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip. "A History of Haskell: Being Lazy with Class". History of Programming Languages Conference 2007.
Referencesedit
Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN0-13-484346-0.
graph, reduction, this, article, about, computer, science, term, graph, theory, transitive, reduction, computer, science, graph, reduction, implements, efficient, version, strict, evaluation, evaluation, strategy, where, arguments, function, immediately, evalu. This article is about the computer science term For the graph theory use see transitive reduction 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 Contents 1 Motivation 2 Combinator graph reduction 3 History 4 See also 5 Notes 6 References 7 Further readingMotivation editA 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 displaystyle begin aligned amp amp amp 2 2 2 2 3 3 amp amp amp 2 2 2 2 6 amp amp amp 2 2 4 6 amp amp amp 4 4 6 amp amp amp 8 6 amp amp amp 14 end aligned nbsp 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 displaystyle begin aligned amp amp amp 2 2 2 2 3 3 amp amp amp 2 2 4 3 3 amp amp amp 4 4 3 3 amp amp amp 4 4 6 amp amp amp 8 6 amp amp amp 14 end aligned nbsp 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 nbsp 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 nbsp 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 nbsp 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 editCombinator 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 editThe 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 editGraph reduction machine SECD machineNotes edit 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 A lazy evaluator Hudak Paul Hughes John Peyton Jones Simon Wadler Philip A History of Haskell Being Lazy with Class History of Programming Languages Conference 2007 References editBird Richard 1998 Introduction to Functional Programming using Haskell Prentice Hall ISBN 0 13 484346 0 Further reading editPeyton Jones Simon L 1987 The Implementation of Functional Programming Languages Prentice Hall ISBN 013453333X LCCN 86020535 Retrieved 2022 04 15 Retrieved from https en wikipedia org w index php title Graph reduction amp oldid 1106414698, wikipedia, wiki, book, books, library,
