#lang scribble/doc

@begin[(require scribble/manual)
       (require scribble/eval)
       (require scribble/basic)
       (require (for-label "main.ss"))]

@(define the-eval
   (let ([the-eval (make-base-eval)])
     (the-eval '(require "main.ss"))
     the-eval))

@title[#:tag "top"]{@bold{Memoize}: Lightweight Dynamic Programming}

by Dave Herman (@tt{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.

@table-of-contents[]

@section[#:tag "intro"]{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 @scheme[define/memo], previously computed answers
are cached, avoiding the duplicated computation.

@defexamples[#:eval the-eval
             (define (fib n)
               (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))
             (time (fib 35))
             (define/memo (fib n)
               (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))
             (time (fib 35))]

@section[#:tag "forms"]{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.

@schemegrammar[formals id () (id . formals)]

@subsection[#:tag "definitions"]{Definition Forms}

@defform[#:id define/memo (define/memo (name . formals) body ...)]{
Defines a memoized function @scheme[name] with formal arguments @scheme[formals] and function body forms @scheme[body ...].
Inputs are cached in a hash table and looked up with @scheme[eq?].}

@defform[#:id define/memo* (define/memo* (name . formals) body ...)]{
Like @scheme[define/memo], but uses @scheme[equal?] to look up values in the cache.}

@subsection[#:tag "expressions"]{Expression Forms}

@defform[#:id memo-lambda (memo-lambda formals body ...)]{
An anonymous memoized function with formal arguments @scheme[formals] and function body forms @scheme[body ...].
Inputs are cached in a hash table and looked up with @scheme[eq?].}

@defform[#:id memo-lambda* (memo-lambda* formals body ...)]{
Like @scheme[memo-lambda], but uses @scheme[equal?] to look up values in the cache.}