Memoize:   Lightweight Dynamic Programming
1 Example:   Fibonacci
2 Forms
2.1 Definition Forms
define/  memo
define/  memo*
2.2 Expression Forms
memo-lambda
memo-lambda*
7.7

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.

    1 Example: Fibonacci

    2 Forms

      2.1 Definition Forms

      2.2 Expression Forms

 (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.

Examples:
(define (fib n)
  (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))
> (time (fib 35))

cpu time: 318 real time: 318 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: 1 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 ...)

Defines a memoized function name with formal arguments formals and function body forms body .... Inputs are cached in a hash table and looked up with eq?.

syntax

(define/memo* (name . formals) body ...)

Like define/memo, but uses equal? to look up values in the cache.

2.2 Expression Forms

syntax

(memo-lambda formals body ...)

An anonymous memoized function with formal arguments formals and function body forms body .... Inputs are cached in a hash table and looked up with eq?.

syntax

(memo-lambda* formals body ...)

Like memo-lambda, but uses equal? to look up values in the cache.