Memoize: Lightweight Dynamic Programming
by Dave Herman (dherman at ccs dot neu dot edu)
Memoize is a simple library for doing dynamic programming in Scheme with a minimum of effort. The library provides drop-in replacement forms for defining Scheme functions that cache their results.
| (require memoize) | package: memoize |
1 Example: Fibonacci
A typical example of a dynamic programming problem is computing the Fibonacci numbers, whose simplest implementation involves a heavy amount of duplicated computation. By simply defining the function with define/memo, previously computed answers are cached, avoiding the duplicated computation.
(define (fib n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))
> (time (fib 35)) cpu time: 354 real time: 355 gc time: 0
14930352
> (define/memo (fib n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))
> (time (fib 35)) cpu time: 0 real time: 0 gc time: 0
14930352
2 Forms
Just like the function definition forms in PLT Scheme, the formals list of a memoized function may be a single identifier, a proper list of identifiers, or an improper list of identifiers.
| formals | = | id | ||
| | | () | |||
| | | (id . formals) |
2.1 Definition Forms
syntax
(define/memo (name . formals) body ...)
syntax
(define/memo* (name . formals) body ...)
2.2 Expression Forms
syntax
(memo-lambda formals body ...)
syntax
(memo-lambda* formals body ...)