447:
556:), automatic memoization can be implemented by replacing (at run-time) a function with its calculated value once a value has been calculated for a given set of parameters. The function that does this value-for-function-object replacement can generically wrap any referentially transparent function. Consider the following pseudocode (where it is assumed that functions are first-class values):
1345:
of the input that matches at some offset against a given rule, but also must store the sub-tree that is generated by that rule at that offset in the input, since subsequent calls to the rule by the parser will not actually descend and rebuild that tree. For the same reason, memoized parser algorithms
976:
of the parser through memoization, the augmented parser was still as time complex as Earley's algorithm, which demonstrates a case of the use of memoization for something other than speed optimization. Johnson and Dörre demonstrate another such non-speed related application of memoization: the use of
422:
of those will have been stored. If it is then called with a number greater than 5, such as 7, only 2 recursive calls will be made (7 and 6), and the value for 5! will have been stored from the previous call. In this way, memoization allows a function to become more time-efficient the more often it is
918:
grammars and Θ(n) for non left-recursive grammars). Their top-down parsing algorithm also requires polynomial space for potentially exponential ambiguous parse trees by 'compact representation' and 'local ambiguities grouping'. Their compact representation is comparable with Tomita's compact
961:, which enables the construction of directly executable specifications of CFGs as language processors. The importance of their polynomial algorithm's power to accommodate ‘any form of ambiguous CFG’ with top-down parsing is vital with respect to the syntax and semantics analysis during
141:
from all but the first call made to the function with those parameters. The set of remembered associations may be a fixed-size set controlled by a replacement algorithm or a fixed set, depending on the nature of the function and its use. A function can only be memoized if it is
977:
memoization to delay linguistic constraint resolution to a point in a parse where sufficient information has been accumulated to resolve those constraints. By contrast, in the speed optimization application of memoization, Ford demonstrated that memoization could guarantee that
923:. Their use of memoization is not only limited to retrieving the previously computed results when a parser is applied to a same input position repeatedly (which is essential for polynomial time requirement); it is specialized to perform the following additional tasks:
865:(CFG), it may need an exponential number of steps (with respect to the length of the input) to try all alternatives of the CFG in order to produce all possible parse trees. This eventually would require exponential memory space. Memoization was explored as a
896:, describing the result as a memoizing purely functional top-down backtracking language processor. Frost showed that basic memoized parser combinators can be used as building blocks to construct complex parsers as executable specifications of CFGs.
888:
to solve the problem of exponential time complexity. The basic idea in Norvig's approach is that when a parser is applied to the input, the result is stored in a memotable for subsequent reuse if the same parser is ever reapplied to the same input.
136:
A memoized function "remembers" the results corresponding to some set of specific inputs. Subsequent calls with remembered inputs return the remembered result rather than recalculating it, thus eliminating the primary cost of a call with given
1190:. The process of looking forward, failing, backing up, and then retrying the next alternative is known in parsing as backtracking, and it is primarily backtracking that presents opportunities for memoization in parsing. Consider a function
934:
The algorithm's memo-table ‘lookup’ procedure also determines the reusability of a saved result by comparing the saved result's computational context with the parser's current context. This contextual comparison is the key to accommodate
942:
When performing a successful lookup in a memotable, instead of returning the complete result-set, the process only returns the references of the actual result and eventually speeds up the overall computation.
302:
to arrive at a result, and each of these invocations, in turn, has an associated cost in the time it takes the function to return the value computed. Depending on the machine, this cost might be the sum of:
1357:
backtracking or predicate checks, the overhead of storing each rule's parse results against every offset in the input (and storing the parse tree if the parsing process does that implicitly) may actually
146:; that is, only if calling the function has exactly the same effect as replacing that function call with its return value. (Special case exceptions to this restriction exist, however.) While related to
201:
optimization. Moreover, strength reduction potentially replaces a costly operation such as multiplication with a less costly operation such as addition, and the results in savings can be highly
906:
In 2007, Frost, Hafiz and
Callaghan described a top-down parsing algorithm that uses memoization for refraining redundant computations to accommodate any form of ambiguous CFG in
899:
Memoization was again explored in the context of parsing in 1995 by Mark
Johnson and Jochen Dörre. In 2002, it was examined in considerable depth by Bryan Ford in the form called
54:
and returning the cached result when the same inputs occur again. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple
2123:– eXecutable SpecificAtIons of GrAmmars. Contains publications related to top-down parsing algorithm that supports left-recursion and ambiguity in polynomial time and space.
757:
is desired. In languages such as Lua, more sophisticated techniques exist which allow a function to be replaced by a new function with the same name, which would permit:
150:, since memoization often uses such tables in its implementation, memoization populates its cache of results transparently on the fly, as needed, rather than in advance.
1697:
Frost, Richard (1994). "Using
Memoization to Achieve Polynomial Complexity of Purely Functional Executable Specifications of Non-Deterministic Top-Down Parsers".
767:
to the created functor and forwarding calls to the original function being memoized via an alias when a call to the actual function is required (to avoid endless
1225:, or 0 if that rule does not accept any input at that offset in the string. In a backtracking scenario with such memoization, the parsing process is as follows:
630:. Each such call first checks to see if a holder array has been allocated to store results, and if not, attaches that array. If no entry exists at the position
945:
During updating the memotable, the memoization process groups the (potentially exponential) ambiguous results and ensures the polynomial space requirement.
414:
is first invoked with 5, and then invoked later with any value less than or equal to five, those return values will also have been memoized, since
1965:
1944:
1830:
485:
evaluation strategy. To avoid overhead with calculating argument values, compilers for these languages heavily use auxiliary functions called
1510:
2100:
845:(Note: Some of the steps shown above may be implicitly managed by the implementation language and are provided for illustration.)
189:
occurs (i.e., space used is speed gained), this differs from some other optimizations that involve time-space trade-off, such as
2070:
1749:
1578:
1104:.) Next, consider how this grammar, used as a parse specification, might effect a top-down, left-right parse of the string
927:
The memoization process (which could be viewed as a ‘wrapper’ around any parser execution) accommodates an ever-growing
194:
2178:
1882:
1626:
1393:
2396:
138:
110:
in
American English, and thus carries the meaning of 'turning a function into something to be remembered'. While
2401:
1996:
1563:
Algebraic and Logic
Programming: Third International Conference, Proceedings, Volterra, Italy, 2–4 September 1992
1377:
170:
39:
2427:
1900:
Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on
Principles of Programming Languages, 15–17 January 2003
958:
2432:
2130:
2064:
2000:
1989:
1969:
549:
1257:
in the memoization engine, and is returned a length of 5, thus saving having to actually descend again into
646:
with the supplied arguments. Finally, the entry in the array at the key position is returned to the caller.
1561:
Hoffman, Berthold (1992). "Term
Rewriting with Sharing and Memoïzation". In Kirchner, H.; Levi, G. (eds.).
1324:
are also able to memoize the results of predicate parses, as well, thereby reducing such constructions as:
272:
2406:
1350:) when a rule matches must use some scheme to ensure that such rules are invoked in a predictable order.
962:
892:
Richard Frost and
Barbara Szydlowski also used memoization to reduce the exponential time complexity of
2344:
2246:
2084:
978:
654:
545:
67:
1026:
2054:
1362:
a parser. This effect can be mitigated by explicit selection of those rules the parser will memoize.
1077:
949:
Frost, Hafiz and
Callaghan also described the implementation of the algorithm in PADL’08 as a set of
63:
1937:
2241:
2213:
885:
143:
2126:
2114:
1603:
Proceedings of the
Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95)
881:
of Cocke, Younger and Kasami, could be generated by introducing automatic memoization to a simple
458:
418:
will have been called recursively with the values 5, 4, 3, 2, 1, and 0, and the return values for
2349:
2292:
2251:
2108:
2016:
1732:
Frost, Richard (2003). "Monadic Memoization towards Correctness-Preserving Reduction of Search".
1347:
534:
186:
2060:
525:(the language in which his paper demonstrated automatic memoization), but also in various other
1353:
Since, for any given backtracking or syntactic predicate capable parser not every grammar will
478:
2090:
2374:
2354:
2218:
2171:
2117:– Examples of memoization in javascript using own caching mechanism and using the YUI library
2041:– Generic memoization library for C, implemented using pre-processor function wrapper macros.
1371:
950:
931:
parse by imposing depth restrictions with respect to input length and current input position.
489:
to compute the argument values, and memoize these functions to avoid repeated calculations.
2386:
1784:
1527:
869:
strategy in 1991 by Peter Norvig, who demonstrated that an algorithm similar to the use of
862:
526:
653:
wrapping at each call to a function that is to be memoized. In those languages that allow
8:
2391:
2359:
2297:
2275:
2019:– an example in Java using dynamic proxy classes to create a generic memoization pattern.
1321:
870:
858:
529:. Applications of automatic memoization have also been formally explored in the study of
506:
1788:
1565:. Lecture Notes in Computer Science. Vol. 632. Berlin: Springer. pp. 128–142.
1531:
290:
be assigned the value 6. The non-memoized implementation above, given the nature of the
2323:
1925:
1903:
1824:
1810:
1807:
Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics
1774:
1714:
1632:
1543:
1420:
954:
541:
513:
is implemented, referentially transparent functions may also be automatically memoized
350:
includes the cumulative cost of steps 2 through 6 proportional to the initial value of
190:
2369:
2313:
2230:
2140:
1978:– Memoize is a small library, written by Tim Bradshaw, for performing memoization in
1878:
1745:
1682:
1665:
1622:
1596:"Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems"
1595:
1574:
1491:
1414:
1403:
1389:
920:
893:
666:
572:
202:
71:
59:
43:
1718:
790:
has no attached array values then allocate an associative array called
684:
has no attached array values then allocate an associative array called
437:
2265:
2195:
2164:
1992:
interpreter that performs automatic memoization (with no required user annotations)
1913:
1852:
1805:
Johnson, Mark & Dörre, Jochen (1995). "Memoization of Coroutined Constraints".
1737:
1706:
1677:
1636:
1614:
1606:
1566:
1547:
1535:
1518:
1481:
1446:
854:
205:(non-portable across machines), whereas memoization is a more machine-independent,
55:
2047:– Open source Java memoizer using annotations and pluggable cache implementations.
1650:
338:
The cost to store the return result so that it may be used by the calling context.
1408:
1383:
1297:. While the call to S must recursively descend into X as many times as there are
986:
662:
158:
2120:
1447:"Techniques for Automatic Memoization with Applications to Context-Free Parsing"
966:
2150:
2044:
993:
982:
915:
911:
900:
530:
206:
2022:
2421:
2287:
2203:
2028:
1870:
1610:
1495:
878:
874:
91:
51:
1741:
2318:
882:
518:
482:
198:
147:
116:
20:
2038:
1917:
1710:
1486:
1469:
2270:
2094:
2010:
1979:
1237:
at offset 0, it memoizes the length 5 against that position and the rule
522:
1856:
446:
2381:
2280:
2104:
1815:
1779:
1666:"Memoizing Purely Functional Top-Down Backtracking Language Processors"
1618:
1570:
1338:
907:
213:
101:
47:
2050:
2006:
778:
is a function object parameter) allocate a function object called
676:
is a function object parameter) allocate a function object called
2260:
2208:
2156:
2146:
1985:
1736:. Lecture Notes in Computer Science. Vol. 2671. pp. 66–80.
1539:
768:
291:
217:
165:
27:
2136:
1849:
Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking
1305:
will never have to descend into X at all, since the return value of
1399:
2080:
1908:
2187:
866:
254:
121:
75:
1076:
This grammar generates one of the following three variations of
2083:– Two example implementations of a general memoize function in
2074:
1975:
969:
site has more about the algorithm and implementation details.
324:
The cost to set up the recursive call stack frame. (As above.)
235:
is 0 then return 1 else return factorial(
2109:
http://talideon.com/weblog/2005/07/javascript-memoization.cfm
2032:
665:
factory that returns a wrapped memoized function object in a
486:
95:
1898:
Acar, Umut A.; et al. (2003). "Selective Memoization".
553:
1851:(Master’s thesis). Massachusetts Institute of Technology.
1765:
Johnson, Mark (1995). "Memoization of Top-Down Parsing".
1346:
that generate calls to external code (sometimes called a
1207:
is the offset currently under consideration in the input.
327:
The cost to multiply the result of the recursive call to
1960:
Examples of memoization in various programming languages
1902:. Vol. 38. New Orleans, Louisiana. pp. 14–25.
1423:– a related technique for automatic program optimization
1402:– a memoizing technique to speed up the computation of
614:
In order to call an automatically memoized version of
423:
called, thus resulting in eventual overall speed-up.
1800:
1798:
802:; allocate a new function object called
680:; let memoized-version(arguments) be if
989:that resulted in worst-case backtracking behavior.
763:Essentially, such techniques involve attaching the
669:. In pseudocode, this can be expressed as follows:
509:in much the same way the above memoized version of
307:
The cost to set up the functional call stack frame.
174:. All functions have a computational complexity in
1897:
834:(arguments); end if; return self.
760:factorial = construct-memoized-functor(factorial)
1795:
1593:
708:(arguments); end if; return self.
638:are used as the key of the associative array), a
2419:
1386:– rapidly locating free variables in expressions
730:memfact = construct-memoized-functor(factorial)
1663:
1587:
1183:The key concept here is inherent in the phrase
407:slot return x end if end function
62:, distinct from other forms of caching such as
1643:
1374:– category of techniques to improve efficiency
618:using the above strategy, rather than calling
2172:
1341:during a parse, it must memoize not only the
540:In programming languages where functions are
477:Memoization is heavily used in compilers for
1891:
1804:
1664:Frost, Richard; Szydlowski, Barbara (1996).
1440:
1438:
1436:
1201:is the name of the rule under consideration.
733:The above example assumes that the function
497:While memoization may be added to functions
426:
384:else let x = factorial(n – 1) times
1842:
1840:
1758:
1192:RuleAcceptsSomeInput(Rule, Position, Input)
106:('to be remembered'), usually truncated as
99:
16:Software programming optimization technique
2179:
2165:
2133:example of memoization on a class webpage.
1863:
1829:: CS1 maint: location missing publisher (
1554:
1380:– more information on algorithm complexity
1136:'s are consumed, and then recognizing the
1025:(Notation note: In the above example, the
2143:while memoizing every step in a database.
2093:– Memoization and limited memoization in
1907:
1814:
1778:
1681:
1502:
1485:
1433:
431:
1837:
1725:
1690:
1657:
1281:may occur, allowing for strings such as
1249:then, rather than descending again into
1152:will then descend into B, which in turn
492:
372:is 0 then return 1 else if
178:(i.e. they take time to execute) and in
128:has a specialized meaning in computing.
74:languages, memoization is also known as
1997:Macros for defining memoized procedures
1943:CS1 maint: location missing publisher (
1764:
1560:
1511:"'Memo' Functions and Machine Learning"
1417:– analogous caching in database queries
1411:– shares some concepts with memoization
1221:be the length of the input accepted by
1194:, where the parameters are as follows:
1163:'s by means of many recursive calls to
563:is a function object parameter) if
2420:
2186:
2103:– Extending the Function prototype in
1875:Efficient Parsing for Natural Language
1869:
1508:
1467:
1444:
1396:, that also uses a kind of memoization
1317:will be 16 (in this particular case).
1253:, queries the position 0 against rule
607:(arguments); end if; return F.
2160:
2057:gem that implements memoized methods.
1731:
1696:
1594:Mayfield, James; et al. (1995).
1217:Let the return value of the function
774:function construct-memoized-functor (
672:function construct-memoized-functor (
153:Memoized functions are optimized for
42:technique used primarily to speed up
1846:
753:is called whenever the factorial of
441:
46:by storing the results of expensive
2013:that implements memoized functions.
937:indirect (or hidden) left-recursion
861:input with respect to an ambiguous
438:Thunk § Functional programming
267:, the final result of the function
13:
822:; end if; if self.
745:is made. From this point forward,
696:; end if; if self.
368:is a non-negative integer) if
342:In a non-memoized implementation,
294:algorithm involved, would require
231:is a non-negative integer) if
168:has a specific name in computing:
14:
2444:
1954:
1213:is the input under consideration.
58:descent parsing. It is a type of
2397:History of compiler construction
2137:Memoization in Combinatory Logic
445:
393:with the parameter 1 less than n
248:with the parameter 1 less than n
157:in exchange for a higher use of
94:in 1968 and is derived from the
2402:Comparison of parser generators
1468:Warren, David S. (1992-03-01).
1378:Computational complexity theory
1327:S → (A)? A A → /* some rule */
1320:Those parsers that make use of
826:is empty then self.
700:is empty then self.
410:In this particular example, if
120:(because they are etymological
1734:Canadian Conference on AI 2003
1461:
657:, memoization can be effected
1:
2025:- A Java memoization library.
1966:groovy.lang.Closure#memoize()
1427:
1273:In the above example, one or
521:have application not only in
517:. The techniques employed by
1809:. Cambridge, Massachusetts.
1683:10.1016/0167-6423(96)00014-7
1470:"Memoing for logic programs"
1128:, and again descending into
649:The above strategy requires
390:recursively invoke factorial
317:The cost to subtract 1 from
245:recursively invoke factorial
81:
7:
2407:Operator-precedence grammar
1365:
1096:here is understood to mean
979:parsing expression grammars
972:While Norvig increased the
963:natural language processing
481:languages, which often use
193:, in that memoization is a
164:. The time/space "cost" of
131:
10:
2449:
2149:– Cache method results in
2139:– A web service to reduce
2091:Memoization in Mathematica
1144:, and fail to recognize a
1120:(by first descending into
877:(1970), and tables in the
848:
838:; end let; return
786:(arguments) be if
743:construct-memoized-functor
712:; end let; return
435:
357:A memoized version of the
282:, the result is such that
250:] end if end function
216:function to calculate the
18:
2337:
2306:
2229:
2194:
2115:Memoization in Javascript
2101:Memoization in Javascript
1767:Computational Linguistics
1474:Communications of the ACM
1451:Computational Linguistics
1241:. After having failed at
1175:and finally recognizes a
771:), as illustrated below:
737:has already been defined
571:then allocate an
427:Some other considerations
144:referentially transparent
70:. In the context of some
1651:"Bricolage: Memoization"
1611:10.1109/CAIA.1995.378786
1392:– an object programming
1285:. In fact, there may be
1269:as many times as before.
1069:followed by an optional
886:recursive descent parser
765:original function object
723:, a new function object
624:memoized-call(factorial(
559:function memoized-call (
382:lookup-table-value-for-n
171:computational complexity
19:Not to be confused with
2350:Definite clause grammar
2067:example of memoization.
1742:10.1007/3-540-44886-1_8
1509:Michie, Donald (1968).
1348:semantic action routine
992:Consider the following
727:is created as follows:
622:directly, code invokes
535:artificial intelligence
212:Consider the following
114:might be confused with
2107:( archived version of
2035:memoization framework.
1445:Norvig, Peter (1991).
1265:it had descended into
1140:), and then return to
1057:." The production X →
951:higher-order functions
595:is empty then
567:has no attached array
479:functional programming
432:Functional programming
100:
2428:Software optimization
2355:Deterministic parsing
2127:Memoization in Scheme
1972:1.8 language feature.
1918:10.1145/640128.604133
1711:10.1145/181761.181764
1487:10.1145/131295.131299
1372:Approximate computing
1337:If a parser builds a
1307:RuleAcceptsSomeInput(
1148:. The next clause of
929:direct left-recursive
806:; attach
794:; attach
688:; attach
587:; end if; if
527:programming languages
493:Automatic memoization
2433:Computer performance
1847:Ford, Bryan (2002).
1670:Sci. Comput. Program
1330:to one descent into
1322:syntactic predicates
1219:RuleAcceptsSomeInput
1185:again descends into
1154:again descends into
863:context-free grammar
814:; self.
380:then return
364:function factorial (
310:The cost to compare
227:function factorial (
2392:Scannerless parsing
2360:Dynamic programming
2073:– Implemented as a
1789:1995cmp.lg....4016J
1532:1968Natur.218...19M
1159:and recognizes the
871:dynamic programming
542:first-class objects
507:computer programmer
187:space–time tradeoff
2188:Parsing algorithms
2081:Memoization in Lua
2061:Python memoization
1877:. Boston: Kluwer.
1605:. pp. 87–93.
1571:10.1007/BFb0013824
1421:Partial evaluation
1313:xxxxxxxxxxxxxxxxbd
1283:xxxxxxxxxxxxxxxxbd
955:parser combinators
919:representation of
894:parser combinators
875:Earley's algorithm
873:and state-sets in
857:tries to parse an
457:. You can help by
361:function follows:
346:top-level call to
191:strength reduction
56:mutually recursive
2415:
2414:
2214:Recursive descent
2141:Combinatory Logic
2077:syntax extension.
2071:OCaml memoization
1751:978-3-540-40300-5
1580:978-3-540-55873-6
1415:Materialized view
1404:cellular automata
1390:Flyweight pattern
1261:, and carries on
1171:, and returns to
1124:to recognize one
921:bottom-up parsing
719:Rather than call
667:decorator pattern
579:; attach
573:associative array
475:
474:
203:machine-dependent
72:logic programming
44:computer programs
2440:
2370:Parser generator
2293:Recursive ascent
2181:
2174:
2167:
2158:
2157:
2023:memoization.java
2017:Java memoization
1968:– Memoize is an
1949:
1948:
1941:
1935:
1931:
1929:
1921:
1911:
1895:
1889:
1888:
1867:
1861:
1860:
1844:
1835:
1834:
1828:
1820:
1818:
1802:
1793:
1792:
1782:
1762:
1756:
1755:
1729:
1723:
1722:
1694:
1688:
1687:
1685:
1661:
1655:
1654:
1647:
1641:
1640:
1600:
1591:
1585:
1584:
1558:
1552:
1551:
1540:10.1038/218019a0
1515:
1506:
1500:
1499:
1489:
1465:
1459:
1458:
1442:
1316:
1224:
1220:
1212:
1206:
1200:
1193:
985:time even those
840:memoized-version
784:memoized-version
780:memoized-version
752:
744:
736:
726:
722:
714:memoized-version
678:memoized-version
645:
642:call is made to
637:
633:
629:
621:
617:
512:
470:
467:
449:
442:
417:
413:
395:] store
360:
349:
330:
301:
281:
275:; if invoked as
270:
266:
105:
68:page replacement
2448:
2447:
2443:
2442:
2441:
2439:
2438:
2437:
2418:
2417:
2416:
2411:
2333:
2302:
2225:
2190:
2185:
2045:Tek271 Memoizer
1957:
1952:
1942:
1933:
1932:
1923:
1922:
1896:
1892:
1885:
1868:
1864:
1845:
1838:
1822:
1821:
1803:
1796:
1763:
1759:
1752:
1730:
1726:
1699:SIGPLAN Notices
1695:
1691:
1662:
1658:
1649:
1648:
1644:
1629:
1598:
1592:
1588:
1581:
1559:
1555:
1526:(5136): 19–22.
1513:
1507:
1503:
1466:
1462:
1443:
1434:
1430:
1409:Lazy evaluation
1384:Director string
1368:
1328:
1306:
1222:
1218:
1210:
1204:
1198:
1191:
1116:will recognize
1023:
981:could parse in
901:packrat parsing
855:top-down parser
851:
843:
842:; end function
761:
746:
742:
734:
731:
724:
720:
717:
716:; end function
643:
635:
631:
623:
619:
615:
612:
611:; end function
510:
495:
471:
465:
462:
455:needs expansion
440:
434:
429:
415:
411:
408:
358:
347:
328:
299:
298:invocations of
276:
268:
264:
261:
251:
159:computer memory
134:
84:
24:
17:
12:
11:
5:
2446:
2436:
2435:
2430:
2413:
2412:
2410:
2409:
2404:
2399:
2394:
2389:
2384:
2379:
2378:
2377:
2367:
2362:
2357:
2352:
2347:
2341:
2339:
2338:Related topics
2335:
2334:
2332:
2331:
2328:
2327:
2326:
2316:
2310:
2308:
2304:
2303:
2301:
2300:
2295:
2290:
2285:
2284:
2283:
2278:
2273:
2268:
2258:
2257:
2256:
2255:
2254:
2244:
2235:
2233:
2227:
2226:
2224:
2223:
2222:
2221:
2219:Tail recursive
2211:
2206:
2200:
2198:
2192:
2191:
2184:
2183:
2176:
2169:
2161:
2155:
2154:
2144:
2134:
2124:
2118:
2112:
2098:
2088:
2078:
2068:
2058:
2048:
2042:
2036:
2026:
2020:
2014:
2004:
1995:Dave Herman's
1993:
1983:
1973:
1962:
1961:
1956:
1955:External links
1953:
1951:
1950:
1934:|journal=
1890:
1883:
1871:Tomita, Masaru
1862:
1836:
1816:cmp-lg/9504028
1794:
1780:cmp-lg/9504016
1773:(3): 405–417.
1757:
1750:
1724:
1689:
1676:(3): 263–288.
1656:
1642:
1627:
1586:
1579:
1553:
1501:
1460:
1431:
1429:
1426:
1425:
1424:
1418:
1412:
1406:
1397:
1394:design pattern
1387:
1381:
1375:
1367:
1364:
1326:
1293:'s before the
1277:descents into
1271:
1270:
1233:descends into
1229:When the rule
1215:
1214:
1208:
1202:
1181:
1180:
1132:until all the
1053:followed by a
1045:followed by a
998:
947:
946:
943:
940:
932:
916:left-recursive
850:
847:
773:
759:
729:
671:
558:
531:term rewriting
494:
491:
473:
472:
452:
450:
436:Main article:
433:
430:
428:
425:
363:
340:
339:
336:
325:
322:
315:
308:
280:= factorial(3)
262:
226:
207:cross-platform
133:
130:
90:was coined by
83:
80:
52:pure functions
48:function calls
15:
9:
6:
4:
3:
2:
2445:
2434:
2431:
2429:
2426:
2425:
2423:
2408:
2405:
2403:
2400:
2398:
2395:
2393:
2390:
2388:
2385:
2383:
2380:
2376:
2373:
2372:
2371:
2368:
2366:
2363:
2361:
2358:
2356:
2353:
2351:
2348:
2346:
2343:
2342:
2340:
2336:
2329:
2325:
2322:
2321:
2320:
2317:
2315:
2312:
2311:
2309:
2305:
2299:
2296:
2294:
2291:
2289:
2286:
2282:
2279:
2277:
2274:
2272:
2269:
2267:
2264:
2263:
2262:
2259:
2253:
2252:Shunting-yard
2250:
2249:
2248:
2245:
2243:
2240:
2239:
2237:
2236:
2234:
2232:
2228:
2220:
2217:
2216:
2215:
2212:
2210:
2207:
2205:
2202:
2201:
2199:
2197:
2193:
2189:
2182:
2177:
2175:
2170:
2168:
2163:
2162:
2159:
2152:
2148:
2145:
2142:
2138:
2135:
2132:
2128:
2125:
2122:
2119:
2116:
2113:
2110:
2106:
2102:
2099:
2096:
2092:
2089:
2086:
2082:
2079:
2076:
2072:
2069:
2066:
2062:
2059:
2056:
2052:
2049:
2046:
2043:
2040:
2037:
2034:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2008:
2005:
2002:
1998:
1994:
1991:
1987:
1984:
1981:
1977:
1974:
1971:
1970:Apache Groovy
1967:
1964:
1963:
1959:
1958:
1946:
1939:
1927:
1919:
1915:
1910:
1905:
1901:
1894:
1886:
1884:0-89838-202-5
1880:
1876:
1872:
1866:
1858:
1854:
1850:
1843:
1841:
1832:
1826:
1817:
1812:
1808:
1801:
1799:
1790:
1786:
1781:
1776:
1772:
1768:
1761:
1753:
1747:
1743:
1739:
1735:
1728:
1720:
1716:
1712:
1708:
1704:
1700:
1693:
1684:
1679:
1675:
1671:
1667:
1660:
1652:
1646:
1638:
1634:
1630:
1628:0-8186-7070-3
1624:
1620:
1616:
1612:
1608:
1604:
1597:
1590:
1582:
1576:
1572:
1568:
1564:
1557:
1549:
1545:
1541:
1537:
1533:
1529:
1525:
1521:
1520:
1512:
1505:
1497:
1493:
1488:
1483:
1480:(3): 93–111.
1479:
1475:
1471:
1464:
1456:
1452:
1448:
1441:
1439:
1437:
1432:
1422:
1419:
1416:
1413:
1410:
1407:
1405:
1401:
1398:
1395:
1391:
1388:
1385:
1382:
1379:
1376:
1373:
1370:
1369:
1363:
1361:
1356:
1351:
1349:
1344:
1340:
1335:
1333:
1325:
1323:
1318:
1314:
1310:
1304:
1300:
1296:
1292:
1288:
1284:
1280:
1276:
1268:
1264:
1260:
1256:
1252:
1248:
1244:
1240:
1236:
1232:
1228:
1227:
1226:
1209:
1203:
1197:
1196:
1195:
1189:
1188:
1178:
1174:
1170:
1167:, and then a
1166:
1162:
1158:
1157:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
1119:
1115:
1111:
1110:
1109:
1107:
1103:
1099:
1095:
1091:
1087:
1083:
1079:
1074:
1072:
1068:
1064:
1060:
1056:
1052:
1048:
1044:
1041:is either an
1040:
1037:) reads: "An
1036:
1032:
1028:
1022:
1018:
1014:
1010:
1006:
1002:
997:
995:
990:
988:
984:
980:
975:
970:
968:
964:
960:
956:
952:
944:
941:
938:
933:
930:
926:
925:
924:
922:
917:
913:
909:
904:
902:
897:
895:
890:
887:
884:
880:
879:CYK algorithm
876:
872:
868:
864:
860:
856:
846:
841:
837:
833:
829:
825:
821:
817:
813:
809:
805:
801:
797:
793:
789:
785:
781:
777:
772:
770:
766:
758:
756:
750:
740:
728:
715:
711:
707:
703:
699:
695:
691:
687:
683:
679:
675:
670:
668:
664:
660:
656:
652:
647:
641:
627:
610:
606:
602:
598:
594:
590:
586:
582:
578:
574:
570:
566:
562:
557:
555:
551:
547:
543:
538:
536:
532:
528:
524:
520:
516:
508:
504:
500:
490:
488:
484:
480:
469:
460:
456:
453:This section
451:
448:
444:
443:
439:
424:
421:
406:
402:
398:
394:
391:
387:
383:
379:
375:
371:
367:
362:
355:
353:
345:
337:
334:
326:
323:
320:
316:
313:
309:
306:
305:
304:
297:
293:
289:
285:
279:
274:
259:
256:
249:
246:
242:
238:
234:
230:
225:
223:
219:
215:
210:
208:
204:
200:
196:
192:
188:
183:
181:
177:
173:
172:
167:
163:
160:
156:
151:
149:
148:lookup tables
145:
140:
129:
127:
123:
119:
118:
113:
109:
104:
103:
97:
93:
92:Donald Michie
89:
79:
77:
73:
69:
65:
61:
57:
53:
49:
45:
41:
37:
33:
29:
22:
2364:
2307:Mixed, other
2298:Shift-reduce
1899:
1893:
1874:
1865:
1857:1721.1/87310
1848:
1806:
1770:
1766:
1760:
1733:
1727:
1705:(4): 23–30.
1702:
1698:
1692:
1673:
1669:
1659:
1645:
1602:
1589:
1562:
1556:
1523:
1517:
1504:
1477:
1473:
1463:
1454:
1450:
1359:
1354:
1352:
1342:
1336:
1331:
1329:
1319:
1312:
1308:
1302:
1298:
1294:
1290:
1286:
1282:
1278:
1274:
1272:
1266:
1262:
1258:
1254:
1250:
1246:
1242:
1238:
1234:
1230:
1216:
1186:
1184:
1182:
1176:
1172:
1168:
1164:
1160:
1155:
1153:
1149:
1145:
1141:
1137:
1133:
1129:
1125:
1121:
1117:
1113:
1105:
1101:
1098:one or more
1097:
1093:
1089:
1085:
1081:
1075:
1070:
1066:
1062:
1058:
1054:
1050:
1046:
1042:
1038:
1034:
1030:
1024:
1020:
1016:
1012:
1008:
1004:
1000:
991:
973:
971:
948:
936:
928:
905:
898:
891:
883:backtracking
852:
844:
839:
835:
831:
827:
823:
819:
815:
811:
807:
803:
799:
795:
791:
787:
783:
779:
775:
764:
762:
754:
748:
741:the call to
738:
732:
718:
713:
709:
705:
701:
697:
693:
689:
685:
681:
677:
673:
658:
650:
648:
639:
625:
613:
608:
604:
600:
596:
592:
588:
584:
580:
576:
568:
564:
560:
539:
519:Peter Norvig
514:
502:
498:
496:
483:call by name
476:
463:
459:adding to it
454:
419:
409:
404:
401:lookup-table
400:
396:
392:
389:
385:
381:
378:lookup-table
377:
373:
369:
365:
356:
351:
343:
341:
332:
318:
311:
295:
287:
283:
277:
257:
252:
247:
244:
240:
236:
232:
228:
221:
211:
199:compile-time
197:rather than
184:
179:
175:
169:
161:
154:
152:
135:
125:
117:memorization
115:
111:
107:
87:
85:
40:optimization
35:
31:
25:
21:Memorization
2365:Memoization
2330:Statistical
2324:Left corner
2281:Generalized
2238:Precedence
2095:Mathematica
2011:Perl module
1988:– A custom
1980:Common Lisp
1619:11603/12722
1457:(1): 91–98.
523:Common Lisp
239:– 1) times
185:Although a
126:memoization
112:memoization
88:memoization
36:memoisation
32:memoization
2422:Categories
2382:Parse tree
2314:Combinator
2271:Look-ahead
2105:JavaScript
2051:memoizable
2007:Memoize.pm
1428:References
1339:parse tree
1287:any number
1061:reads "An
1027:production
908:polynomial
782:; let
659:implicitly
515:externally
503:explicitly
499:internally
466:April 2014
260:such that
253:For every
214:pseudocode
209:strategy.
166:algorithms
139:parameters
102:memorandum
2276:Canonical
2231:Bottom-up
1936:ignored (
1926:cite book
1909:1106.0447
1825:cite book
1496:0001-0782
1360:slow down
1112:The rule
1007:) A → X (
987:languages
859:ambiguous
769:recursion
735:factorial
721:factorial
644:factorial
636:arguments
620:factorial
616:factorial
544:(such as
511:factorial
416:factorial
412:factorial
359:factorial
348:factorial
329:factorial
300:factorial
292:recursive
273:invariant
269:factorial
218:factorial
86:The term
82:Etymology
64:buffering
28:computing
2247:Operator
2196:Top-down
1873:(1985).
1719:10616505
1400:Hashlife
1366:See also
1205:Position
1015:) B → X
953:(called
914:(n) for
747:memfact(
655:closures
651:explicit
195:run-time
132:Overview
122:cognates
2147:MbCache
2121:X-SAIGA
2029:C++Memo
1976:Memoize
1785:Bibcode
1637:8963326
1548:4265138
1528:Bibcode
1106:xxxxxbd
1092:(where
1033:) | (B
1029:S → (A
1003:) | (B
999:S → (A
994:grammar
967:X-SAIGA
959:Haskell
867:parsing
853:When a
849:Parsers
830:= self.
725:memfact
663:functor
634:(where
575:called
403:in the
255:integer
76:tabling
60:caching
2266:Simple
2242:Simple
2204:Earley
2131:Scheme
2075:Camlp4
2065:Python
2039:C-Memo
2001:Racket
1990:Python
1881:
1748:
1717:
1635:
1625:
1577:
1546:
1519:Nature
1494:
1343:length
1118:xxxxxb
1078:string
1065:is an
983:linear
965:. The
910:time (
836:values
828:values
824:values
796:values
792:values
739:before
710:values
702:values
698:values
690:values
686:values
661:via a
632:values
609:values
601:values
593:values
581:values
577:values
569:values
550:Python
487:thunks
376:is in
288:always
38:is an
2319:Chart
1986:IncPy
1904:arXiv
1811:arXiv
1775:arXiv
1715:S2CID
1633:S2CID
1599:(PDF)
1544:S2CID
1514:(PDF)
1311:, 0,
1263:as if
1211:Input
1088:, or
1049:or a
974:power
957:) in
832:alias
816:alias
808:alias
804:alias
552:, or
505:by a
344:every
314:to 0.
296:n + 1
286:will
180:space
162:space
155:speed
98:word
96:Latin
2375:LALR
2151:.NET
2129:– A
2063:– A
2055:Ruby
2053:– A
2031:– A
2009:– a
1945:link
1938:help
1879:ISBN
1831:link
1746:ISBN
1623:ISBN
1575:ISBN
1492:ISSN
1355:need
1301:'s,
1275:many
1223:Rule
1199:Rule
1073:.")
1019:X →
812:self
800:self
788:self
694:self
682:self
640:real
554:Perl
533:and
501:and
420:each
176:time
108:memo
66:and
2387:AST
2345:PEG
2288:CYK
2085:Lua
2033:C++
1999:in
1914:doi
1853:hdl
1738:doi
1707:doi
1678:doi
1615:hdl
1607:doi
1567:doi
1536:doi
1524:218
1482:doi
1289:of
1090:xbd
1086:xbc
1082:xac
810:to
798:to
692:to
583:to
546:Lua
461:.
399:in
331:by
271:is
265:≥ 0
220:of
124:),
50:to
34:or
26:In
2424::
2261:LR
2209:LL
2111:).
1930::
1928:}}
1924:{{
1912:.
1839:^
1827:}}
1823:{{
1797:^
1783:.
1771:21
1769:.
1744:.
1713:.
1703:29
1701:.
1674:27
1672:.
1668:.
1631:.
1621:.
1613:.
1601:.
1573:.
1542:.
1534:.
1522:.
1516:.
1490:.
1478:35
1476:.
1472:.
1455:17
1453:.
1449:.
1435:^
1334:.
1245:,
1108::
1102:'s
1084:,
1080::
996::
903:.
818:=
704:=
628:))
603:=
548:,
537:.
354:.
224::
182:.
78:.
30:,
2180:e
2173:t
2166:v
2153:.
2097:.
2087:.
2003:.
1982:.
1947:)
1940:)
1920:.
1916::
1906::
1887:.
1859:.
1855::
1833:)
1819:.
1813::
1791:.
1787::
1777::
1754:.
1740::
1721:.
1709::
1686:.
1680::
1653:.
1639:.
1617::
1609::
1583:.
1569::
1550:.
1538::
1530::
1498:.
1484::
1332:A
1315:)
1309:X
1303:B
1299:x
1295:b
1291:x
1279:X
1267:X
1259:X
1255:X
1251:X
1247:B
1243:d
1239:X
1235:X
1231:A
1187:X
1179:.
1177:d
1173:S
1169:b
1165:X
1161:x
1156:X
1150:S
1146:c
1142:S
1138:b
1134:x
1130:X
1126:x
1122:X
1114:A
1100:x
1094:x
1071:X
1067:x
1063:X
1059:x
1055:d
1051:B
1047:c
1043:A
1039:S
1035:d
1031:c
1021:x
1017:b
1013:b
1011:|
1009:a
1005:d
1001:c
939:.
912:Θ
820:F
776:F
755:n
751:)
749:n
706:F
674:F
626:n
605:F
599:.
597:F
591:.
589:F
585:F
565:F
561:F
468:)
464:(
405:n
397:x
388:[
386:n
374:n
370:n
366:n
352:n
335:.
333:n
321:.
319:n
312:n
284:x
278:x
263:n
258:n
243:[
241:n
237:n
233:n
229:n
222:n
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.