and rebuild that tree. For the same reason, memoized parser algorithms that generate calls to external code (sometimes called a semantic action routine) when a rule matches must use some scheme to ensure that such rules are invoked in a predictable order. Since, for any given backtracking or syntactic predicate capable parser not every grammar will need 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 slow down a parser. This effect can be mitigated by explicit selection of those rules the parser will memoize. See also Approximate computing – category of techniques to improve efficiency Computational complexity theory – more information on algorithm complexity Director string – rapidly locating free variables in expressions Flyweight pattern – an object programming design pattern, that also uses a kind of memoization Hashlife – a memoizing technique to speed up the computation of cellular automata Lazy evaluation – shares some concepts with memoization Materialized view – analogous caching in database queries Partial evaluation – a related technique for automatic program optimization References External links Examples of memoization in various programming languages groovy.lang.Closure#memoize() – Memoize is an Apache Groovy 1.8 language feature. Memoize – Memoize is a small library, written by Tim Bradshaw, for performing memoization in Common Lisp. IncPy – A custom Python interpreter that performs automatic memoization (with no required user annotations) Dave Herman's Macros for defining memoized procedures in Racket. Memoize.pm – a Perl module that implements memoized functions. Java memoization – an example in Java using dynamic proxy classes to create a generic memoization pattern. memoization.java - A Java memoization library. C++Memo – A C++ memoization framework. C-Memo – Generic memoization library for C, implemented using pre-processor function wrapper macros. Tek271 Memoizer – Open source Java memoizer using annotations and pluggable cache implementations. memoizable – A Ruby gem that implements memoized methods. Python memoization – A Python example of memoization. OCaml memoization – Implemented as a Camlp4 syntax extension. Memoization in Lua – Two example implementations of a general memoize function in Lua. Memoization in Mathematica – Memoization and limited memoization in Mathematica. Memoization in Javascript – Extending the Function prototype in JavaScript ( archived version of http://talideon.com/weblog/2005/07/javascript-memoization.cfm ). Memoization in Javascript – Examples of memoization in javascript using own caching mechanism and using the YUI library