682:
665:
648:
627:
336:
355:
64:
622:{\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+4)+(3+3)\\&{}&=&(4+4)+(3+3)\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}
331:{\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+(2+2))+6\\&{}&=&((2+2)+4)+6\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}
360:
69:
920:
733:
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
653:
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.
632:
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
877:
721:
in computer memory, and program execution then consists of rewriting parts of this graph ("reducing" it) so as to move towards useful results.
776:
856:
734:
887:
38:
where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as
925:
738:
930:
346:
342:
774:
Hudak, Paul (September 1989). "Conception, evolution, and application of functional programming languages".
750:
786:
707:
657:
43:
741:
using combinators. SASL was an early functional programming language first developed by Turner in 1972.
730:
47:
20:
791:
640:
35:
729:
The concept of a graph reduction that allows evaluated values to be shared was first developed by
873:
687:
Notice that evaluation now only requires four steps. Outermost graph reduction is referred to as
893:
883:
852:
796:
692:
681:
27:
688:
39:
718:
715:
670:
As for trees, outermost and innermost reduction also applies to graphs. Hence we have
914:
826:
755:
633:
813:
664:
19:
This article is about the computer science term. For the graph theory use, see
711:
647:
800:
677:
Now evaluation with outermost graph reduction can proceed as follows:
58:
A simple example of evaluating an arithmetic expression follows:
897:
825:
Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip.
34:
implements an efficient version of non-strict evaluation, an
341:
The above reduction sequence employs a strategy known as
879:
358:
67:
849:
Introduction to
Functional Programming using Haskell
921:Implementation of functional programming languages
710:languages, in which a program is converted into a
621:
330:
831:History of Programming Languages Conference 2007
691:and innermost graph reduction is referred to as
706:is a fundamental implementation technique for
827:"A History of Haskell: Being Lazy with Class"
345:. The same expression can be evaluated using
8:
656:The expression can also be represented as a
16:Efficient version of non-strict evaluation
790:
660:, allowing sub-expressions to be shared:
603:
580:
543:
494:
433:
364:
359:
357:
312:
289:
252:
203:
142:
73:
68:
66:
643:, the expression above looks like this:
766:
46:. The technique was first developed by
7:
714:representation which is mapped to a
349:, yielding the reduction sequence:
737:incorporated lazy evaluation into
14:
680:
663:
646:
44:functional programming languages
566:
554:
535:
523:
517:
505:
486:
474:
468:
459:
447:
444:
425:
413:
407:
404:
392:
386:
374:
371:
275:
263:
238:
229:
217:
214:
189:
186:
174:
168:
156:
153:
134:
122:
116:
113:
101:
95:
83:
80:
1:
947:
704:Combinator graph reduction
699:Combinator graph reduction
18:
347:innermost tree reduction
343:outermost tree reduction
751:Graph reduction machine
874:Peyton Jones, Simon L.
847:Bird, Richard (1998).
708:functional programming
658:directed acyclic graph
623:
332:
624:
333:
356:
65:
21:transitive reduction
801:10.1145/72551.72554
36:evaluation strategy
619:
617:
328:
326:
882:. Prentice Hall.
851:. Prentice Hall.
779:Computing Surveys
639:Represented as a
938:
926:Graph algorithms
907:
905:
904:
862:
835:
834:
822:
816:
814:A lazy evaluator
811:
805:
804:
794:
771:
693:eager evaluation
684:
667:
650:
628:
626:
625:
620:
618:
604:
601:
581:
578:
544:
541:
495:
492:
434:
431:
367:
365:
362:
337:
335:
334:
329:
327:
313:
310:
290:
287:
253:
250:
204:
201:
143:
140:
76:
74:
71:
28:computer science
946:
945:
941:
940:
939:
937:
936:
935:
931:Graph rewriting
911:
910:
902:
900:
890:
872:
869:
867:Further reading
859:
846:
843:
838:
824:
823:
819:
812:
808:
773:
772:
768:
764:
747:
731:Chris Wadsworth
727:
701:
689:lazy evaluation
672:graph reduction
616:
615:
610:
605:
599:
598:
587:
582:
576:
575:
550:
545:
539:
538:
501:
496:
490:
489:
440:
435:
429:
428:
366:
354:
353:
325:
324:
319:
314:
308:
307:
296:
291:
285:
284:
259:
254:
248:
247:
210:
205:
199:
198:
149:
144:
138:
137:
75:
63:
62:
56:
48:Chris Wadsworth
40:lazy evaluation
32:graph reduction
24:
17:
12:
11:
5:
944:
942:
934:
933:
928:
923:
913:
912:
909:
908:
888:
868:
865:
864:
863:
857:
842:
839:
837:
836:
817:
806:
792:10.1.1.83.6505
785:(3): 359–411.
765:
763:
760:
759:
758:
753:
746:
743:
726:
723:
719:data structure
716:directed graph
700:
697:
630:
629:
614:
611:
609:
606:
602:
600:
597:
594:
591:
588:
586:
583:
579:
577:
574:
571:
568:
565:
562:
559:
556:
553:
551:
549:
546:
542:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
507:
504:
502:
500:
497:
493:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
441:
439:
436:
432:
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
370:
368:
363:
361:
339:
338:
323:
320:
318:
315:
311:
309:
306:
303:
300:
297:
295:
292:
288:
286:
283:
280:
277:
274:
271:
268:
265:
262:
260:
258:
255:
251:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
211:
209:
206:
202:
200:
197:
194:
191:
188:
185:
182:
179:
176:
173:
170:
167:
164:
161:
158:
155:
152:
150:
148:
145:
141:
139:
136:
133:
130:
127:
124:
121:
118:
115:
112:
109:
106:
103:
100:
97:
94:
91:
88:
85:
82:
79:
77:
72:
70:
55:
52:
15:
13:
10:
9:
6:
4:
3:
2:
943:
932:
929:
927:
924:
922:
919:
918:
916:
899:
895:
891:
885:
881:
880:
875:
871:
870:
866:
860:
858:0-13-484346-0
854:
850:
845:
844:
840:
832:
828:
821:
818:
815:
810:
807:
802:
798:
793:
788:
784:
780:
778:
770:
767:
761:
757:
754:
752:
749:
748:
744:
742:
740:
736:
732:
724:
722:
720:
717:
713:
709:
705:
698:
696:
694:
690:
685:
683:
678:
675:
673:
668:
666:
661:
659:
654:
651:
649:
644:
642:
637:
635:
612:
607:
595:
592:
589:
584:
572:
569:
563:
560:
557:
552:
547:
532:
529:
526:
520:
514:
511:
508:
503:
498:
483:
480:
477:
471:
465:
462:
456:
453:
450:
442:
437:
422:
419:
416:
410:
401:
398:
395:
389:
383:
380:
377:
369:
352:
351:
350:
348:
344:
321:
316:
304:
301:
298:
293:
281:
278:
272:
269:
266:
261:
256:
244:
241:
235:
232:
226:
223:
220:
212:
207:
195:
192:
183:
180:
177:
171:
165:
162:
159:
151:
146:
131:
128:
125:
119:
110:
107:
104:
98:
92:
89:
86:
78:
61:
60:
59:
53:
51:
49:
45:
41:
37:
33:
29:
22:
901:. Retrieved
878:
848:
830:
820:
809:
782:
775:
769:
756:SECD machine
735:David Turner
728:
703:
702:
686:
679:
676:
671:
669:
662:
655:
652:
645:
638:
631:
340:
57:
42:and used in
31:
25:
636:operation.
634:associative
915:Categories
903:2022-04-15
889:013453333X
841:References
712:combinator
54:Motivation
787:CiteSeerX
50:in 1971.
898:86020535
876:(1987).
745:See also
725:History
896:
886:
855:
789:
762:Notes
894:LCCN
884:ISBN
853:ISBN
739:SASL
641:tree
797:doi
777:ACM
26:In
917::
892:.
829:.
795:.
783:21
781:.
695:.
674:.
613:14
322:14
30:,
906:.
861:.
833:.
803:.
799::
608:=
596:6
593:+
590:8
585:=
573:6
570:+
567:)
564:4
561:+
558:4
555:(
548:=
536:)
533:3
530:+
527:3
524:(
521:+
518:)
515:4
512:+
509:4
506:(
499:=
487:)
484:3
481:+
478:3
475:(
472:+
469:)
466:4
463:+
460:)
457:2
454:+
451:2
448:(
445:(
438:=
426:)
423:3
420:+
417:3
414:(
411:+
408:)
405:)
402:2
399:+
396:2
393:(
390:+
387:)
384:2
381:+
378:2
375:(
372:(
317:=
305:6
302:+
299:8
294:=
282:6
279:+
276:)
273:4
270:+
267:4
264:(
257:=
245:6
242:+
239:)
236:4
233:+
230:)
227:2
224:+
221:2
218:(
215:(
208:=
196:6
193:+
190:)
187:)
184:2
181:+
178:2
175:(
172:+
169:)
166:2
163:+
160:2
157:(
154:(
147:=
135:)
132:3
129:+
126:3
123:(
120:+
117:)
114:)
111:2
108:+
105:2
102:(
99:+
96:)
93:2
90:+
87:2
84:(
81:(
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
