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.

Memoize

cowan
2012-04-13 02:41:39
1history
source

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:

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 (which can be implemented directly in R5RS with no new data structures or lambda magic)?

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.