1216:
716:
1211:{\displaystyle {\begin{aligned}&(\mathbf {\lambda } x.z)((\lambda w.www)(\lambda w.www))\\\rightarrow &(\lambda x.z)((\lambda w.www)(\lambda w.www)(\lambda w.www))\\\rightarrow &(\lambda x.z)((\lambda w.www)(\lambda w.www)(\lambda w.www)(\lambda w.www))\\\rightarrow &(\lambda x.z)((\lambda w.www)(\lambda w.www)(\lambda w.www)(\lambda w.www)(\lambda w.www))\\&\ldots \end{aligned}}}
2070:
1470:. There are only two possible ÎČ-reductions to be done here, on x and on y. Reducing the outer x term first results in the inner y term being duplicated, and each copy will have to be reduced, but reducing the inner y term first will duplicate its argument z, which will cause work to be duplicated when the values of h and w are made known.
1780:
2072:
The system can be proven to be confluent. Optimal reduction is then defined to be normal order or leftmost-outermost reduction using reduction by families, i.e. the parallel reduction of all redexes with the same function part label. The strategy is optimal in the sense that it performs the optimal
1366:. In fact, applicative order reduction was also originally introduced to model the call-by-value parameter passing technique found in Algol 60 and modern programming languages. When combined with the idea of weak reduction, the resulting call-by-value reduction is indeed a faithful approximation.
2092:
can be defined similarly to optimal reduction as weak leftmost-outermost reduction using parallel reduction of redexes with the same label, for a slightly different labelled lambda calculus. An alternate definition changes the beta rule to an operation that finds the next "needed" computation,
1369:
Unfortunately, weak reduction is not confluent, and the traditional reduction equations of the lambda calculus are useless, because they suggest relationships that violate the weak evaluation regime. However, it is possible to extend the system to be confluent by allowing a restricted form of
2093:
evaluates it, and substitutes the result into all locations. This requires extending the beta rule to allow reducing terms that are not syntactically adjacent. As with call-by-name and call-by-value, call-by-need reduction was devised to mimic the behavior of the
2076:
A practical algorithm for optimal reduction was first described in 1989, more than a decade after optimal reduction was first defined in 1974. The
Bologna Optimal Higher-order Machine (BOHM) is a prototype implementation of an extension of the technique to
712:
refers to leftmost-innermost reduction. In contrast to normal order, applicative order reduction may not terminate, even when the term has a normal form. For example, using applicative order reduction, the following sequence of reductions is possible:
551:
for all almost-orthogonal term rewriting systems, meaning that these strategies will eventually reach a normal form if it exists, even when performing (finitely many) arbitrary reductions between successive applications of the strategy.
1665:
2065:{\displaystyle {\begin{aligned}x^{\alpha }&=\alpha \cdot N&\quad (\lambda y.M)^{\alpha }&=(\lambda y.M)^{\alpha }\\y^{\alpha }&=y^{\alpha }&\quad (MN)^{\alpha }&=(MN)^{\alpha }\end{aligned}}}
1473:
Optimal reduction is not a reduction strategy for the lambda calculus in a narrow sense because performing ÎČ-reduction loses the information about the substituted redexes being shared. Instead it is defined for the
1309:
585:. Normal-order reduction is normalizing, in the sense that if a term has a normal form, then normalâorder reduction will eventually reach it, hence the name normal. This is known as the standardization theorem.
595:
the notions coincide, and similarly the leftmost-outermost redex is the redex with leftmost starting character when the lambda term is considered as a string of characters. When "leftmost" is defined using an
1558:
of labels. A labelled term is a lambda calculus term where each subterm has a label. The standard initial labeling of a lambda term gives each subterm a unique atomic label. Labelled ÎČ-reduction is given by:
1736:
163:
2205:
1785:
721:
654:
332:
1452:
Optimal reduction is motivated by the existence of lambda terms where there does not exist a sequence of reductions which reduces them without duplicating work. For example, consider
1362:
is the weak reduction strategy that reduces the leftmost innermost redex not inside a lambda abstraction. These strategies were devised to reflect the call-by-name and call-by-value
369:
190:
1562:
1556:
1529:
1331:
490:
680:
407:
99:
72:
27:
or rewriting strategy is a relation specifying a rewrite for each object or term, compatible with a given reduction relation. Some authors use the term to refer to an
704:
1687:
437:
280:
214:
216:(but not the reflexive closure). In addition the normal forms of the strategy must be the same as the normal forms of the original rewriting system, i.e. for all
1502:
1771:
457:
254:
234:
123:
1223:
526:
leftmost-outermost: in each step the leftmost of the outermost redexes is contracted, where an outermost redex is a redex not contained in any redexes
523:
leftmost-innermost: in each step the leftmost of the innermost redexes is contracted, where an innermost redex is a redex not containing any redexes
3138:
2996:
2773:
2554:
2356:
2215:
2544:
2833:
2805:
2748:
Processes, Terms and Cycles: Steps on the Road to
Infinity: Essays Dedicated to Jan Willem Klop on the Occasion of His 60th Birthday
2586:
2306:
2262:
1370:
reduction under an abstraction, in particular when the redex does not involve the variable bound by the abstraction. For example,
537:
parallel-innermost: reduces all innermost redexes simultaneously. This is well-defined because the redexes are pairwise disjoint.
1692:
2971:
2893:
543:
Gross-Knuth reduction, also called full substitution or Kleene reduction: all redexes in the term are simultaneously reduced
128:
3013:
1350:
Normal and applicative order reduction are strong in that they allow reduction under lambda abstractions. In contrast,
603:
2441:
Barendregt, H. P.; Eekelen, M. C. J. D.; Glauert, J. R. W.; Kennaway, J. R.; Plasmeijer, M. J.; Sleep, M. R. (1987).
3180:
1313:
2850:
2677:
40:
2912:
FernĂĄndez, Maribel; Siafakas, Nikolaos (30 March 2010). "Labelled Lambda-calculi with
Explicit Copy and Erase".
1358:
is the weak reduction strategy that reduces the leftmost outermost redex not inside a lambda abstraction, while
3185:
2966:. Second Franco-Japanese Symposium on Programming of Future Generation Computers. Cannes, France. p. 187.
556:
344:
285:
2751:
2334:
1338:
refers to the nondeterministic one-step strategy that allows reducing any redex at each step. Takahashi's
168:
2207:
Logic, Rewriting, and
Concurrency: Essays Dedicated to José Meseguer on the Occasion of His 65th Birthday
2465:
1774:
505:
3021:. 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '90. pp. 16â30.
2415:
1534:
1507:
2339:
2798:
The
Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones
2756:
2115:
2094:
1363:
592:
28:
2143:, and is constructed by making wrappers which make the identity function available to the binders
1478:, an annotated lambda calculus which captures a precise notion of the work that should be shared.
3144:
3095:
2939:
2921:
2685:. 1st International Conference on Formal Structures for Computation and Deduction. p. 32:3.
2288:
2081:. Lambdascope is a more recent implementation of optimal reduction, also using interaction nets.
597:
193:
2790:
2746:
Blanc, Tomasz; LĂ©vy, Jean-Jacques; Maranget, Luc (2005). "Sharing in the Weak Lambda-Calculus".
462:
659:
3134:
3050:
2992:
2967:
2889:
2829:
2801:
2769:
2582:
2550:
2352:
2302:
2258:
2211:
385:
77:
45:
2292:
689:
3126:
3022:
2931:
2859:
2761:
2719:
2686:
2518:
2480:
2446:
2344:
2250:
2110:
2078:
1672:
416:
410:
259:
2239:
2098:
1220:
But using normal-order reduction, the same starting point reduces quickly to normal form:
683:
574:
568:
199:
102:
3165:
1660:{\displaystyle ((\lambda x.M)^{\alpha }N)^{\beta }\to \beta {\overline {\alpha }}\cdot M}
2800:. Lecture Notes in Computer Science. Vol. 2566. Springer-Verlag. pp. 420â435.
1484:
3041:
2649:
1741:
442:
239:
219:
108:
2523:
2506:
3174:
3115:
2570:
2484:
2943:
2603:
2172:
A summary of recent research on optimal reduction can be found in the short article
3148:
1423:
can still be reduced under the extended weak reduction strategy, because the redex
16:
Relation specifying a rewrite for each object, compatible with a reduction relation
2382:
2323:
2958:
2254:
3130:
2864:
2691:
2574:
2445:. Parallel Architectures and Languages Europe. Vol. 259. pp. 141â158.
2348:
1481:
Labels consist of a countably infinite set of atomic labels, and concatenations
2858:. 24th International Conference on Types for Proofs and Programs (TYPES 2018).
2201:
2629:
3054:
2450:
2298:
20:
2724:
2707:
2204:. In MartĂ-Oliet, Narciso; Ălveczky, Peter Csaba; Talcott, Carolyn (eds.).
3097:] (Lambdascope): Another optimal implementation of the lambda-calculus
3094:
van
Oostrom, Vincent; van de Looij, Kees-Jan; Zwitserlood, Marijn (2004).
2543:
Mazzola, Guerino; Milmeister, GĂ©rard; Weissmann, Jody (21 October 2004).
3026:
1304:{\displaystyle (\mathbf {\lambda } x.z)((\lambda w.www)(\lambda w.www))}
3125:. Lecture Notes in Computer Science. Vol. 7211. pp. 128â147.
2935:
2765:
3076:
2333:. Lecture Notes in Computer Science. Vol. 4600. pp. 89â112.
1455:((λg.(g(g(λx.x)))) (λh.((λf.(f(f(λz.z)))) (λw.(h(w(λy.y)))))))
2322:
Klop, Jan Willem; van
Oostrom, Vincent; van Raamsdonk, Femke (2007).
2173:
1342:
is the strategy that reduces all redexes in the term simultaneously.
2926:
508:
a rewriting strategy specifies, out of all the reducible subterms (
2120:
1389:
is in normal form for a weak reduction strategy because the redex
509:
559:
designed specifically for programming term rewriting strategies.
591:
is sometimes used to refer to normal order reduction, as with a
3103:. Workshop on Algebra and Logic on Programming Systems (ALPS).
2886:
The optimal implementation of functional programming languages
2139:
Incidentally, the above term reduces to the identity function
706:
while the leftmost-outermost redex is the entire expression.
2852:
Normalization by
Evaluation for Typed Weak lambda-Reduction
2581:. Vol. I. Amsterdam: North Holland. pp. 139â142.
2159:(at first), all of which are applied to the innermost term
3049:(PhD) (in French). UniversitĂ© Paris VII. pp. 81â109.
2991:. Cambridge, UK: Cambridge University Press. p. 518.
581:
refers to leftmost-outermost reduction in the sense given
1731:{\displaystyle \beta \cdot T^{\alpha }=T^{\beta \alpha }}
2796:. In Mogensen, T; Schmidt, D; Sudborough, I. H. (eds.).
2914:
2631:
Non-Idempotent Typing
Operators, beyond the λ-Calculus
2604:"A Proof of the Standardization Theorem in λ-Calculus"
2549:. Springer Science & Business Media. p. 323.
1354:
reduction does not reduce under a lambda abstraction.
158:{\displaystyle \to _{S}\subseteq {\overset {+}{\to }}}
2202:"Rewriting Strategies and Strategic Rewrite Programs"
1783:
1744:
1695:
1675:
1565:
1537:
1510:
1487:
1316:
1226:
719:
692:
662:
606:
465:
445:
419:
388:
347:
288:
262:
242:
222:
202:
171:
131:
111:
80:
48:
3077:"Bologna Optimal Higher-Order Machine, Version 1.1"
2546:
Comprehensive Mathematics for Computer Scientists 2
1404:is contained in a lambda abstraction. But the term
600:the notions are distinct. For example, in the term
529:
rightmost-innermost, rightmost-outermost: similarly
3015:An algorithm for optimal lambda calculus reduction
2657:(PhD). University of North Carolina at Chapel Hill
2464:Antoy, Sergio; Middeldorp, Aart (September 1996).
2064:
1765:
1730:
1681:
1659:
1550:
1523:
1496:
1325:
1303:
1210:
698:
686:, the leftmost redex of the in-order traversal is
674:
648:
484:
451:
431:
401:
363:
326:
274:
248:
228:
208:
184:
157:
117:
93:
66:
649:{\displaystyle (\lambda x.x\Omega )(\lambda y.I)}
547:Parallel outermost and Gross-Knuth reduction are
2676:Van Oostrom, Vincent; Toyama, Yoshihito (2016).
2511:Electronic Notes in Theoretical Computer Science
519:One-step strategies for term rewriting include:
2960:Sharing in the Evaluation of lambda Expressions
2741:
2739:
2737:
2735:
3116:"The Call-by-Need Lambda Calculus, Revisited"
2888:. Cambridge, UK: Cambridge University Press.
2174:About the efficient reduction of lambda terms
8:
3114:Chang, Stephen; Felleisen, Matthias (2012).
2907:
2905:
2819:
2817:
2073:(minimal) number of family reduction steps.
2884:Asperti, Andrea; Guerrini, Stefano (1998).
2828:. Cambridge, Mass.: MIT Press. p. 42.
569:Lambda calculus § Reduction strategies
2879:
2877:
2875:
2538:
2536:
2534:
2247:Semantic Techniques in Quantum Computation
2195:
2193:
2957:LĂ©vy, Jean-Jacques (9â11 November 1987).
2925:
2863:
2791:"Demonstrating Lambda Calculus Reduction"
2755:
2723:
2690:
2522:
2409:
2407:
2338:
2238:Selinger, Peter; Valiron, BenoĂźt (2009).
2052:
1981:
1959:
1927:
1913:
1851:
1792:
1784:
1782:
1743:
1719:
1706:
1694:
1674:
1638:
1613:
1601:
1588:
1564:
1538:
1536:
1511:
1509:
1486:
1315:
1230:
1225:
730:
720:
718:
691:
661:
605:
473:
464:
444:
418:
393:
387:
352:
346:
310:
287:
261:
241:
221:
201:
172:
170:
145:
136:
130:
110:
85:
79:
47:
2390:Papers by Nachum Dershowitz and students
2283:
2281:
2637:(PhD). Sorbonne Paris Cité. p. 62.
2189:
2132:
3043:RĂ©ductions sures dans le lambda-calcul
2505:Kieburtz, Richard B. (November 2001).
2376:
2374:
2372:
2370:
2368:
1458:It is composed of three nested terms,
364:{\displaystyle \to _{S}\subseteq \to }
327:{\displaystyle \exists b'.a\to _{S}b'}
2648:Partain, William D. (December 1989).
2324:"Reduction Strategies and Acyclicity"
7:
2826:Semantics engineering with PLT Redex
185:{\displaystyle {\overset {+}{\to }}}
3166:Lambda calculus reduction workbench
2708:"Parallel Reductions in λ-Calculus"
2200:Kirchner, HĂ©lĂšne (26 August 2015).
582:
2507:"A Logic for Rewriting Strategies"
693:
663:
622:
289:
14:
3123:Programming Languages and Systems
2466:"A sequential reduction strategy"
2422:. University of Wisconsin Madison
2392:. Tel Aviv University. p. 77
1773:is defined as follows (using the
3040:LĂ©vy, Jean-Jacques (June 1974).
2651:Graph Reduction Without Pointers
2628:Vial, Pierre (7 December 2017).
2331:Rewriting, Computation and Proof
1551:{\displaystyle {\underline {a}}}
512:), which one should be reduced (
341:reduction strategy is one where
2679:Normalisation by Random Descent
2609:. Tokyo Institute of Technology
2294:Types and Programming Languages
1967:
1831:
1524:{\displaystyle {\overline {a}}}
2049:
2045:
2039:
2033:
2027:
2021:
2015:
2009:
1999:
1993:
1987:
1978:
1968:
1945:
1939:
1933:
1910:
1906:
1900:
1894:
1879:
1869:
1863:
1857:
1848:
1832:
1810:
1804:
1798:
1760:
1754:
1748:
1654:
1635:
1629:
1607:
1598:
1585:
1569:
1566:
1317:
1298:
1295:
1274:
1271:
1250:
1247:
1244:
1227:
1191:
1188:
1167:
1164:
1143:
1140:
1119:
1116:
1095:
1092:
1071:
1068:
1065:
1050:
1043:
1036:
1033:
1012:
1009:
988:
985:
964:
961:
940:
937:
934:
919:
912:
905:
902:
881:
878:
857:
854:
833:
830:
827:
812:
805:
798:
795:
774:
771:
750:
747:
744:
727:
643:
628:
625:
607:
533:Many-step strategies include:
470:
390:
349:
307:
266:
203:
174:
147:
133:
82:
61:
58:
49:
1:
2524:10.1016/S1571-0661(04)00283-X
1326:{\displaystyle \rightarrow z}
540:parallel-outermost: similarly
2824:Felleisen, Matthias (2009).
2750:. Springer. pp. 70â87.
2706:Takahashi, M. (April 1995).
2485:10.1016/0304-3975(96)00041-2
2473:Theoretical Computer Science
2255:10.1017/CBO9781139193313.005
1618:
1516:
3131:10.1007/978-3-642-28869-2_7
2865:10.4230/LIPIcs.TYPES.2018.6
2712:Information and Computation
2692:10.4230/LIPIcs.FSCD.2016.32
2349:10.1007/978-3-540-73147-4_5
2097:known as "call-by-need" or
710:Applicative order reduction
3202:
566:
485:{\displaystyle a\to _{S}b}
2849:Sestini, Filippo (2019).
2240:"Quantum Lambda Calculus"
675:{\displaystyle \Omega ,I}
41:abstract rewriting system
2383:"Term Rewriting Systems"
1476:labelled lambda calculus
557:domain-specific language
402:{\displaystyle \to _{S}}
94:{\displaystyle \to _{S}}
67:{\displaystyle (A,\to )}
2789:Sestoft, Peter (2002).
2451:10.1007/3-540-17945-3_8
1360:call-by-value reduction
699:{\displaystyle \Omega }
74:, a reduction strategy
3012:Lamping, John (1990).
2989:Term rewriting systems
2725:10.1006/inco.1995.1057
2090:Call by need reduction
2085:Call by need reduction
2066:
1767:
1732:
1683:
1682:{\displaystyle \cdot }
1661:
1552:
1525:
1498:
1356:Call-by-name reduction
1327:
1305:
1212:
700:
676:
650:
579:normal-order reduction
573:In the context of the
486:
453:
433:
432:{\displaystyle a\in A}
403:
382:strategy is one where
365:
328:
276:
275:{\displaystyle a\to b}
250:
230:
210:
186:
159:
119:
95:
68:
2067:
1775:Barendregt convention
1768:
1733:
1689:concatenates labels,
1684:
1662:
1553:
1526:
1499:
1464:y=((λf. ...) (λw.z) )
1460:x=((λg. ... ) (λh.y))
1364:evaluation strategies
1328:
1306:
1213:
701:
677:
651:
506:term rewriting system
487:
454:
439:there is at most one
434:
404:
366:
329:
277:
251:
231:
211:
187:
160:
120:
96:
69:
2443:Term graph rewriting
1781:
1742:
1693:
1673:
1563:
1535:
1508:
1485:
1340:parallel ÎČ-reduction
1314:
1224:
717:
690:
660:
604:
492:. Otherwise it is a
463:
443:
417:
386:
371:. Otherwise it is a
345:
286:
260:
240:
220:
209:{\displaystyle \to }
200:
169:
129:
109:
78:
46:
3027:10.1145/96709.96711
2289:Pierce, Benjamin C.
2116:Reduction semantics
2095:evaluation strategy
1738:, and substitution
593:pre-order traversal
29:evaluation strategy
2936:10.4204/EPTCS.22.5
2766:10.1007/11601548_7
2414:Horwitz, Susan B.
2062:
2060:
1763:
1728:
1679:
1657:
1646:
1548:
1546:
1521:
1497:{\displaystyle ab}
1494:
1438:does not refer to
1323:
1301:
1208:
1206:
696:
672:
646:
598:in-order traversal
589:Leftmost reduction
482:
449:
429:
399:
361:
359:⊆ →
324:
272:
246:
226:
206:
194:transitive closure
182:
155:
115:
91:
64:
25:reduction strategy
3181:Rewriting systems
3140:978-3-642-28868-5
3075:Asperti, Andrea.
2998:978-0-521-39115-3
2775:978-3-540-32425-6
2579:Combinatory Logic
2571:Curry, Haskell B.
2556:978-3-540-20861-7
2416:"Lambda Calculus"
2358:978-3-540-73146-7
2217:978-3-319-23165-5
1766:{\displaystyle M}
1639:
1621:
1539:
1531:and underlinings
1519:
1468:z=λw.(h(w(λy.y)))
1448:Optimal reduction
516:) within a term.
452:{\displaystyle b}
249:{\displaystyle b}
236:, there exists a
229:{\displaystyle a}
180:
153:
118:{\displaystyle A}
39:Formally, for an
3193:
3153:
3152:
3120:
3111:
3105:
3104:
3102:
3091:
3085:
3084:
3072:
3066:
3065:
3063:
3061:
3048:
3037:
3031:
3030:
3020:
3009:
3003:
3002:
2984:
2978:
2977:
2965:
2954:
2948:
2947:
2929:
2909:
2900:
2899:
2881:
2870:
2869:
2867:
2857:
2846:
2840:
2839:
2821:
2812:
2811:
2795:
2786:
2780:
2779:
2759:
2743:
2730:
2729:
2727:
2703:
2697:
2696:
2694:
2684:
2673:
2667:
2666:
2664:
2662:
2656:
2645:
2639:
2638:
2636:
2625:
2619:
2618:
2616:
2614:
2608:
2599:
2593:
2592:
2567:
2561:
2560:
2540:
2529:
2528:
2526:
2502:
2496:
2495:
2493:
2491:
2470:
2461:
2455:
2454:
2438:
2432:
2431:
2429:
2427:
2411:
2402:
2401:
2399:
2397:
2387:
2378:
2363:
2362:
2342:
2328:
2319:
2313:
2312:
2285:
2276:
2275:
2273:
2271:
2244:
2235:
2229:
2228:
2226:
2224:
2197:
2177:
2170:
2164:
2162:
2158:
2155:(at first), and
2154:
2150:
2146:
2142:
2137:
2111:Reduction system
2079:interaction nets
2071:
2069:
2068:
2063:
2061:
2057:
2056:
1986:
1985:
1964:
1963:
1932:
1931:
1918:
1917:
1856:
1855:
1797:
1796:
1772:
1770:
1769:
1764:
1737:
1735:
1734:
1729:
1727:
1726:
1711:
1710:
1688:
1686:
1685:
1680:
1666:
1664:
1663:
1658:
1647:
1622:
1614:
1606:
1605:
1593:
1592:
1557:
1555:
1554:
1549:
1547:
1530:
1528:
1527:
1522:
1520:
1512:
1503:
1501:
1500:
1495:
1469:
1465:
1461:
1443:
1437:
1422:
1403:
1388:
1336:Full ÎČ-reduction
1332:
1330:
1329:
1324:
1310:
1308:
1307:
1302:
1234:
1217:
1215:
1214:
1209:
1207:
1197:
734:
723:
705:
703:
702:
697:
681:
679:
678:
673:
655:
653:
652:
647:
549:hypernormalizing
494:nondeterministic
491:
489:
488:
483:
478:
477:
458:
456:
455:
450:
438:
436:
435:
430:
413:, i.e. for each
411:partial function
408:
406:
405:
400:
398:
397:
370:
368:
367:
362:
357:
356:
333:
331:
330:
325:
323:
315:
314:
299:
281:
279:
278:
273:
255:
253:
252:
247:
235:
233:
232:
227:
215:
213:
212:
207:
191:
189:
188:
183:
181:
173:
164:
162:
161:
156:
154:
146:
141:
140:
124:
122:
121:
116:
100:
98:
97:
92:
90:
89:
73:
71:
70:
65:
3201:
3200:
3196:
3195:
3194:
3192:
3191:
3190:
3186:Lambda calculus
3171:
3170:
3162:
3157:
3156:
3141:
3118:
3113:
3112:
3108:
3100:
3093:
3092:
3088:
3074:
3073:
3069:
3059:
3057:
3046:
3039:
3038:
3034:
3018:
3011:
3010:
3006:
2999:
2987:Terese (2003).
2986:
2985:
2981:
2974:
2963:
2956:
2955:
2951:
2911:
2910:
2903:
2896:
2883:
2882:
2873:
2855:
2848:
2847:
2843:
2836:
2823:
2822:
2815:
2808:
2793:
2788:
2787:
2783:
2776:
2745:
2744:
2733:
2705:
2704:
2700:
2682:
2675:
2674:
2670:
2660:
2658:
2654:
2647:
2646:
2642:
2634:
2627:
2626:
2622:
2612:
2610:
2606:
2601:
2600:
2596:
2589:
2569:
2568:
2564:
2557:
2542:
2541:
2532:
2504:
2503:
2499:
2489:
2487:
2468:
2463:
2462:
2458:
2440:
2439:
2435:
2425:
2423:
2413:
2412:
2405:
2395:
2393:
2385:
2380:
2379:
2366:
2359:
2340:10.1.1.104.9139
2326:
2321:
2320:
2316:
2309:
2287:
2286:
2279:
2269:
2267:
2265:
2242:
2237:
2236:
2232:
2222:
2220:
2218:
2199:
2198:
2191:
2186:
2181:
2180:
2171:
2167:
2160:
2156:
2152:
2148:
2144:
2140:
2138:
2134:
2129:
2107:
2099:lazy evaluation
2087:
2059:
2058:
2048:
2002:
1977:
1965:
1955:
1948:
1923:
1920:
1919:
1909:
1872:
1847:
1829:
1813:
1788:
1779:
1778:
1740:
1739:
1715:
1702:
1691:
1690:
1671:
1670:
1597:
1584:
1561:
1560:
1533:
1532:
1506:
1505:
1483:
1482:
1467:
1463:
1459:
1456:
1450:
1439:
1424:
1405:
1390:
1371:
1348:
1312:
1311:
1222:
1221:
1205:
1204:
1195:
1194:
1046:
1040:
1039:
915:
909:
908:
808:
802:
801:
715:
714:
688:
687:
658:
657:
602:
601:
575:lambda calculus
571:
565:
563:Lambda calculus
502:
469:
461:
460:
441:
440:
415:
414:
389:
384:
383:
348:
343:
342:
316:
306:
292:
284:
283:
258:
257:
238:
237:
218:
217:
198:
197:
167:
166:
132:
127:
126:
107:
106:
103:binary relation
81:
76:
75:
44:
43:
37:
17:
12:
11:
5:
3199:
3197:
3189:
3188:
3183:
3173:
3172:
3169:
3168:
3161:
3160:External links
3158:
3155:
3154:
3139:
3106:
3086:
3067:
3032:
3004:
2997:
2979:
2972:
2949:
2901:
2894:
2871:
2841:
2835:978-0262062756
2834:
2813:
2806:
2781:
2774:
2757:10.1.1.129.147
2731:
2718:(1): 120â127.
2698:
2668:
2640:
2620:
2602:Kashima, Ryo.
2594:
2587:
2562:
2555:
2530:
2517:(2): 138â154.
2497:
2456:
2433:
2403:
2364:
2357:
2314:
2307:
2301:. p. 56.
2277:
2263:
2230:
2216:
2188:
2187:
2185:
2182:
2179:
2178:
2165:
2131:
2130:
2128:
2125:
2124:
2123:
2118:
2113:
2106:
2103:
2086:
2083:
2055:
2051:
2047:
2044:
2041:
2038:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2005:
2003:
2001:
1998:
1995:
1992:
1989:
1984:
1980:
1976:
1973:
1970:
1966:
1962:
1958:
1954:
1951:
1949:
1947:
1944:
1941:
1938:
1935:
1930:
1926:
1922:
1921:
1916:
1912:
1908:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1881:
1878:
1875:
1873:
1871:
1868:
1865:
1862:
1859:
1854:
1850:
1846:
1843:
1840:
1837:
1834:
1830:
1828:
1825:
1822:
1819:
1816:
1814:
1812:
1809:
1806:
1803:
1800:
1795:
1791:
1787:
1786:
1762:
1759:
1756:
1753:
1750:
1747:
1725:
1722:
1718:
1714:
1709:
1705:
1701:
1698:
1678:
1656:
1653:
1650:
1645:
1642:
1637:
1634:
1631:
1628:
1625:
1620:
1617:
1612:
1609:
1604:
1600:
1596:
1591:
1587:
1583:
1580:
1577:
1574:
1571:
1568:
1545:
1542:
1518:
1515:
1504:, overlinings
1493:
1490:
1454:
1449:
1446:
1347:
1346:Weak reduction
1344:
1322:
1319:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1233:
1229:
1203:
1200:
1198:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1047:
1045:
1042:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
916:
914:
911:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
809:
807:
804:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
733:
729:
726:
724:
722:
695:
671:
668:
665:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
564:
561:
555:Stratego is a
545:
544:
541:
538:
531:
530:
527:
524:
501:
500:Term rewriting
498:
481:
476:
472:
468:
448:
428:
425:
422:
396:
392:
360:
355:
351:
322:
319:
313:
309:
305:
302:
298:
295:
291:
271:
268:
265:
245:
225:
205:
179:
176:
152:
149:
144:
139:
135:
114:
88:
84:
63:
60:
57:
54:
51:
36:
33:
15:
13:
10:
9:
6:
4:
3:
2:
3198:
3187:
3184:
3182:
3179:
3178:
3176:
3167:
3164:
3163:
3159:
3150:
3146:
3142:
3136:
3132:
3128:
3124:
3117:
3110:
3107:
3099:
3098:
3090:
3087:
3082:
3078:
3071:
3068:
3056:
3052:
3045:
3044:
3036:
3033:
3028:
3024:
3017:
3016:
3008:
3005:
3000:
2994:
2990:
2983:
2980:
2975:
2969:
2962:
2961:
2953:
2950:
2945:
2941:
2937:
2933:
2928:
2923:
2919:
2915:
2908:
2906:
2902:
2897:
2891:
2887:
2880:
2878:
2876:
2872:
2866:
2861:
2854:
2853:
2845:
2842:
2837:
2831:
2827:
2820:
2818:
2814:
2809:
2807:3-540-00326-6
2803:
2799:
2792:
2785:
2782:
2777:
2771:
2767:
2763:
2758:
2753:
2749:
2742:
2740:
2738:
2736:
2732:
2726:
2721:
2717:
2713:
2709:
2702:
2699:
2693:
2688:
2681:
2680:
2672:
2669:
2653:
2652:
2644:
2641:
2633:
2632:
2624:
2621:
2605:
2598:
2595:
2590:
2588:0-7204-2208-6
2584:
2580:
2576:
2572:
2566:
2563:
2558:
2552:
2548:
2547:
2539:
2537:
2535:
2531:
2525:
2520:
2516:
2512:
2508:
2501:
2498:
2486:
2482:
2478:
2474:
2467:
2460:
2457:
2452:
2448:
2444:
2437:
2434:
2421:
2417:
2410:
2408:
2404:
2391:
2384:
2377:
2375:
2373:
2371:
2369:
2365:
2360:
2354:
2350:
2346:
2341:
2336:
2332:
2325:
2318:
2315:
2310:
2308:0-262-16209-1
2304:
2300:
2296:
2295:
2290:
2284:
2282:
2278:
2266:
2264:9780521513746
2260:
2256:
2252:
2248:
2241:
2234:
2231:
2219:
2213:
2209:
2208:
2203:
2196:
2194:
2190:
2183:
2175:
2169:
2166:
2136:
2133:
2126:
2122:
2119:
2117:
2114:
2112:
2109:
2108:
2104:
2102:
2100:
2096:
2091:
2084:
2082:
2080:
2074:
2053:
2042:
2036:
2030:
2024:
2018:
2012:
2006:
2004:
1996:
1990:
1982:
1974:
1971:
1960:
1956:
1952:
1950:
1942:
1936:
1928:
1924:
1914:
1903:
1897:
1891:
1888:
1885:
1882:
1876:
1874:
1866:
1860:
1852:
1844:
1841:
1838:
1835:
1826:
1823:
1820:
1817:
1815:
1807:
1801:
1793:
1789:
1776:
1757:
1751:
1745:
1723:
1720:
1716:
1712:
1707:
1703:
1699:
1696:
1676:
1667:
1651:
1648:
1643:
1640:
1632:
1626:
1623:
1615:
1610:
1602:
1594:
1589:
1581:
1578:
1575:
1572:
1543:
1540:
1513:
1491:
1488:
1479:
1477:
1471:
1453:
1447:
1445:
1442:
1436:
1432:
1428:
1421:
1417:
1413:
1409:
1402:
1398:
1394:
1387:
1383:
1379:
1375:
1367:
1365:
1361:
1357:
1353:
1345:
1343:
1341:
1337:
1333:
1320:
1292:
1289:
1286:
1283:
1280:
1277:
1268:
1265:
1262:
1259:
1256:
1253:
1241:
1238:
1235:
1231:
1218:
1201:
1199:
1185:
1182:
1179:
1176:
1173:
1170:
1161:
1158:
1155:
1152:
1149:
1146:
1137:
1134:
1131:
1128:
1125:
1122:
1113:
1110:
1107:
1104:
1101:
1098:
1089:
1086:
1083:
1080:
1077:
1074:
1062:
1059:
1056:
1053:
1048:
1030:
1027:
1024:
1021:
1018:
1015:
1006:
1003:
1000:
997:
994:
991:
982:
979:
976:
973:
970:
967:
958:
955:
952:
949:
946:
943:
931:
928:
925:
922:
917:
899:
896:
893:
890:
887:
884:
875:
872:
869:
866:
863:
860:
851:
848:
845:
842:
839:
836:
824:
821:
818:
815:
810:
792:
789:
786:
783:
780:
777:
768:
765:
762:
759:
756:
753:
741:
738:
735:
731:
725:
711:
707:
685:
669:
666:
640:
637:
634:
631:
619:
616:
613:
610:
599:
594:
590:
586:
584:
580:
576:
570:
562:
560:
558:
553:
550:
542:
539:
536:
535:
534:
528:
525:
522:
521:
520:
517:
515:
511:
507:
499:
497:
495:
479:
474:
466:
446:
426:
423:
420:
412:
394:
381:
380:deterministic
376:
374:
358:
353:
340:
335:
320:
317:
311:
303:
300:
296:
293:
269:
263:
243:
223:
195:
177:
150:
142:
137:
112:
104:
86:
55:
52:
42:
34:
32:
30:
26:
22:
3122:
3109:
3096:
3089:
3080:
3070:
3058:. Retrieved
3042:
3035:
3014:
3007:
2988:
2982:
2959:
2952:
2917:
2913:
2885:
2851:
2844:
2825:
2797:
2784:
2747:
2715:
2711:
2701:
2678:
2671:
2659:. Retrieved
2650:
2643:
2630:
2623:
2611:. Retrieved
2597:
2578:
2575:Feys, Robert
2565:
2545:
2514:
2510:
2500:
2488:. Retrieved
2479:(1): 75â95.
2476:
2472:
2459:
2442:
2436:
2424:. Retrieved
2419:
2394:. Retrieved
2389:
2381:Klop, J. W.
2330:
2317:
2293:
2268:. Retrieved
2246:
2233:
2221:. Retrieved
2210:. Springer.
2206:
2168:
2135:
2089:
2088:
2075:
1668:
1480:
1475:
1472:
1457:
1451:
1440:
1434:
1430:
1426:
1419:
1415:
1411:
1407:
1400:
1396:
1392:
1385:
1381:
1377:
1373:
1368:
1359:
1355:
1351:
1349:
1339:
1335:
1334:
1219:
709:
708:
588:
587:
578:
572:
554:
548:
546:
532:
518:
513:
503:
493:
379:
377:
372:
338:
336:
38:
24:
18:
2927:1003.5515v1
2490:8 September
2420:CS704 Notes
35:Definitions
3175:Categories
2973:0444705260
2895:0521621127
2661:10 January
2184:References
567:See also:
514:contracted
496:strategy.
459:such that
375:strategy.
3060:17 August
3055:476040273
2920:: 49â64.
2752:CiteSeerX
2613:19 August
2426:19 August
2396:14 August
2335:CiteSeerX
2299:MIT Press
2270:21 August
2223:14 August
2054:α
2040:↦
2022:↦
1994:↦
1983:α
1961:α
1940:↦
1929:α
1915:α
1901:↦
1883:λ
1864:↦
1853:α
1836:λ
1824:⋅
1821:α
1805:↦
1794:α
1755:↦
1724:α
1721:β
1708:α
1700:⋅
1697:β
1677:⋅
1649:⋅
1644:_
1641:α
1636:↦
1624:⋅
1619:¯
1616:α
1611:β
1608:→
1603:β
1590:α
1573:λ
1544:_
1517:¯
1318:→
1278:λ
1254:λ
1232:λ
1202:…
1171:λ
1147:λ
1123:λ
1099:λ
1075:λ
1054:λ
1044:→
1016:λ
992:λ
968:λ
944:λ
923:λ
913:→
885:λ
861:λ
837:λ
816:λ
806:→
778:λ
754:λ
732:λ
694:Ω
664:Ω
632:λ
623:Ω
611:λ
471:→
424:∈
391:→
373:many step
350:→
308:→
290:∃
267:→
204:→
175:→
148:→
143:⊆
134:→
83:→
59:→
21:rewriting
2944:15500633
2577:(1958).
2291:(2002).
2105:See also
682:defined
339:one step
321:′
297:′
165:, where
3149:6350826
2149:f=λw...
2145:g=λh...
510:redexes
192:is the
3147:
3137:
3081:GitHub
3053:
2995:
2970:
2942:
2892:
2832:
2804:
2772:
2754:
2585:
2553:
2355:
2337:
2305:
2261:
2249:: 23.
2214:
2157:w=λz.z
2153:h=λx.x
2141:(λy.y)
1669:where
1466:, and
3145:S2CID
3119:(PDF)
3101:(PDF)
3047:(PDF)
3019:(PDF)
2964:(PDF)
2940:S2CID
2922:arXiv
2856:(PDF)
2794:(PDF)
2683:(PDF)
2655:(PDF)
2635:(PDF)
2607:(PDF)
2469:(PDF)
2386:(PDF)
2327:(PDF)
2243:(PDF)
2127:Notes
2121:Thunk
656:with
583:above
504:In a
409:is a
256:with
125:with
101:is a
3135:ISBN
3062:2021
3051:OCLC
2993:ISBN
2968:ISBN
2890:ISBN
2830:ISBN
2802:ISBN
2770:ISBN
2663:2022
2615:2021
2583:ISBN
2551:ISBN
2492:2021
2428:2021
2398:2021
2353:ISBN
2303:ISBN
2272:2021
2259:ISBN
2225:2021
2212:ISBN
2161:λy.y
1352:weak
684:here
282:iff
23:, a
3127:doi
3023:doi
2932:doi
2860:doi
2762:doi
2720:doi
2716:118
2687:doi
2519:doi
2481:doi
2477:165
2447:doi
2345:doi
2251:doi
1777:):
1410:.(λ
1376:.(λ
196:of
105:on
19:In
3177::
3143:.
3133:.
3121:.
3079:.
2938:.
2930:.
2918:22
2916:.
2904:^
2874:^
2816:^
2768:.
2760:.
2734:^
2714:.
2710:.
2573:;
2533:^
2515:58
2513:.
2509:.
2475:.
2471:.
2418:.
2406:^
2388:.
2367:^
2351:.
2343:.
2329:.
2297:.
2280:^
2257:.
2245:.
2192:^
2151:,
2147:,
2101:.
1462:,
1444:.
1425:(λ
1391:(λ
577:,
378:A
337:A
334:.
31:.
3151:.
3129::
3083:.
3064:.
3029:.
3025::
3001:.
2976:.
2946:.
2934::
2924::
2898:.
2868:.
2862::
2838:.
2810:.
2778:.
2764::
2728:.
2722::
2695:.
2689::
2665:.
2617:.
2591:.
2559:.
2527:.
2521::
2494:.
2483::
2453:.
2449::
2430:.
2400:.
2361:.
2347::
2311:.
2274:.
2253::
2227:.
2176:.
2163:.
2050:)
2046:]
2043:P
2037:x
2034:[
2031:N
2028:]
2025:P
2019:x
2016:[
2013:M
2010:(
2007:=
2000:]
1997:P
1991:x
1988:[
1979:)
1975:N
1972:M
1969:(
1957:y
1953:=
1946:]
1943:N
1937:x
1934:[
1925:y
1911:)
1907:]
1904:N
1898:x
1895:[
1892:M
1889:.
1886:y
1880:(
1877:=
1870:]
1867:N
1861:x
1858:[
1849:)
1845:M
1842:.
1839:y
1833:(
1827:N
1818:=
1811:]
1808:N
1802:x
1799:[
1790:x
1761:]
1758:N
1752:x
1749:[
1746:M
1717:T
1713:=
1704:T
1655:]
1652:N
1633:x
1630:[
1627:M
1599:)
1595:N
1586:)
1582:M
1579:.
1576:x
1570:(
1567:(
1541:a
1514:a
1492:b
1489:a
1441:x
1435:z
1433:)
1431:y
1429:.
1427:y
1420:z
1418:)
1416:y
1414:.
1412:y
1408:x
1406:λ
1401:z
1399:)
1397:x
1395:.
1393:y
1386:z
1384:)
1382:x
1380:.
1378:y
1374:x
1372:λ
1321:z
1299:)
1296:)
1293:w
1290:w
1287:w
1284:.
1281:w
1275:(
1272:)
1269:w
1266:w
1263:w
1260:.
1257:w
1251:(
1248:(
1245:)
1242:z
1239:.
1236:x
1228:(
1192:)
1189:)
1186:w
1183:w
1180:w
1177:.
1174:w
1168:(
1165:)
1162:w
1159:w
1156:w
1153:.
1150:w
1144:(
1141:)
1138:w
1135:w
1132:w
1129:.
1126:w
1120:(
1117:)
1114:w
1111:w
1108:w
1105:.
1102:w
1096:(
1093:)
1090:w
1087:w
1084:w
1081:.
1078:w
1072:(
1069:(
1066:)
1063:z
1060:.
1057:x
1051:(
1037:)
1034:)
1031:w
1028:w
1025:w
1022:.
1019:w
1013:(
1010:)
1007:w
1004:w
1001:w
998:.
995:w
989:(
986:)
983:w
980:w
977:w
974:.
971:w
965:(
962:)
959:w
956:w
953:w
950:.
947:w
941:(
938:(
935:)
932:z
929:.
926:x
920:(
906:)
903:)
900:w
897:w
894:w
891:.
888:w
882:(
879:)
876:w
873:w
870:w
867:.
864:w
858:(
855:)
852:w
849:w
846:w
843:.
840:w
834:(
831:(
828:)
825:z
822:.
819:x
813:(
799:)
796:)
793:w
790:w
787:w
784:.
781:w
775:(
772:)
769:w
766:w
763:w
760:.
757:w
751:(
748:(
745:)
742:z
739:.
736:x
728:(
670:I
667:,
644:)
641:I
638:.
635:y
629:(
626:)
620:x
617:.
614:x
608:(
480:b
475:S
467:a
447:b
427:A
421:a
395:S
354:S
318:b
312:S
304:a
301:.
294:b
270:b
264:a
244:b
224:a
178:+
151:+
138:S
113:A
87:S
62:)
56:,
53:A
50:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.