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.

Source for wiki Memoize version 3

author

cowan

comment

ipnr

173.13.139.236

name

Memoize

readonly

text

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 do this if the procedure is impure.)

It's easy to see how `define/memo` would work as a more convenient version of this.

There are a bunch of issues, though:

 * The most fundamental question is "What counts as the 'same arguments'?"  In Racket, `lambda/memo` uses `eq?` and `lambda/memo*` uses `equal`.  That doesn't seem very flexible.

 * What is the type of the store?  In Racket, hash tables based on `eq?` and `equal?` are available.  But in R7RS-large, there is no guarantee that an implementation that wants to support memoizing will also provide hash tables, so either we closely couple the two packages, or we provide a hook for constructing a store.  If the function accepts only a single argument which belongs to a small range of exact integers, a vector would be a ''much'' better store.

 * If arbitrary stores like a-lists are allowed, how are multiple arguments packaged up as a key for the store?

 * How do we specify the getter and setter for an arbitrary store?

 * How can we provide all this flexibility without compromising convenience for elementary uses?

 * Should there be some way to let the function decide which return values to memoize?

 * Do we support multiple returned values?  Maybe not by default, only if specifically requested, because of the overhead.

Adding extra arguments to `lambda/memo` beyond the lambda-list and the body doesn't seem like a win to me (how do you know if the extra arguments are arguments, or part of the body?).  Are dynamic parameters the Right Thing here?  I don't think so, because all these factors should be bound to the static definition of the memoized functions.  Is this a place where we need keyword arguments in `lambda/memo`?

I think we need a record type `memoization-store` that provides a store constructor, comparator, getter, and setter.  But we still have the issue of associating an instance of `memoization-store` with a particular lambda.

time

2013-05-21 19:17:31