This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home. For a version of this page that may be more recent, see Memoize in WG2's repo for R7RS-large.


2013-06-24 11:55:49

This isn't a proposal, just some ideas and discussion points.

The basic interface to memoizing is a variant of lambda, perhaps called lambda/memo as in Racket, or perhaps something else. It returns a procedure that memoizes the results of calls on it in a store, and then pulls the results out of the store on later calls with the same arguments. (Obviously you don't want to memoize impure procedures.) Plausible stores are a-lists, hash tables, mutable or immutable sets, and other data structures. It's easy to see how define/memo would work as a more convenient version of this.

The store can be abstracted into a record with four fields: a store creation procedure, a getter, a setter, and a SRFI 114 comparator which defines what counts as "the same arguments" and is passed to the store creation procedure. We need some standard stores, though unless memoization is tightly coupled to something like hash tables or trees, they won't be very efficient ones. On the other hand, if it happens that the range of the argument is 0 to a small exact integer, a vector store would be much better than a hash table store.