memo:   Memoization with cache and finalization control
memoize
define/  memoize
memoize-zero
define/  memoize-zero
memoize-partial
define/  memoize-partial
7.0

memo: Memoization with cache and finalization control

Kevin Robert Stravers

 (require memo) package: memo

This package provides macros for defining memoized functions. A memoized function stores its results in a hasheq table. Multiple arguments invoke nested hasheq tables.

It also provides manners to finalize or destroy memoized values.

syntax

(memoize (param ...+) body ...+)

(memoize (param ...+) #:finalize finalizer body ...+)
Creates a memoized lambda. It is the lambda that holds the memoized values internally. If the lambda goes out of scope, then so do the associated memoized values. A finalizer can be specified using the #:finalize keyword after the parameter list. The finalizer runs whenever a value has been removed from the cache, but no guarantee is made as to when this will happen as finalization depends on the racket garbage collector.

syntax

(define/memoize (name param ...+) body ...+)

(define/memoize (name param ...+) #:finalize finalizer body ...+)
Same as memoize but defines a name in the surrounding scope.

Examples:
> (define/memoize (fib n)
    (if (< n 2)
      1
      (+ (fib (sub1 n)) (fib (- n 2)))))
> (fib 100)

573147844013817084101

Accessing the cache is done by calling the function without any arguments. So it can be reset by doing the following:

> (set-box! (fib) (hasheq))

One can also simply remove the desired entries inside (fib), and then use set-box! to store it back to the function. Finalization occurs if a finalizer is specified and the GC happens to collect your removed value.

For multiple arguments the hash becomes nested with respect to the parameters:

Examples:
> (define/memoize (f a b c) (+ a b c))
> (f 1 2 3)

6

> (f)

'#&       #hasheq((1 . #hash((2 . #hash((3 . 6))))))

syntax

(memoize-zero body ...+)

Creates a memoized lambda that takes zero arguments. It runs the body once and only once when called for the first time. To access the content of the cache and first-time flag, give the function one argument. Memoize-zero has no finalizer.

syntax

(define/memoize-zero name body ...+)

Same as memoize-zero but defines the name.

Examples:
> (define/memoize-zero example
    (writeln "This runs once and only once")
    'value)
> (example)

"This runs once and only once"

'value

> (example)

'value

Access to the zero version is granted by providing a dummy argument. Here we use 'get-cache for clarity.

Examples:
> (define/memoize-zero example
    (writeln "This runs once and only once")
    'value)
> (example 'get-cache)

'#&#<void>

'#&#t

> (example)

"This runs once and only once"

'value

> (example 'get-cache)

'#&value

'#&#f

Two values are returned; the cache itself (inside a box), as well as the first-time? flag, also in a box. This flag indicates whether or not the cache should computed.

Sometimes we wish to write partially memoized functions, for instance, when we compute a side-effect and we want to cache some important result before doing the side-effect. A good use-case is OpenGL, where we may need to generate a texture or load a glProgram.

syntax

(memoize-partial (memoized-param ...)
                 (live-param ...)
                 (memoized-body ...)
                 (live-body ...+))
Creates a memoized function that memoizes memoized-body using memoized-param, but will apply the remaining arguments to the live-body. Similarly to other memoizations, one can use empty arguments to get the cached table. If live-param is empty, calling the memoized function with just the memoized-param will run the live-body. Otherwise, it will return a function taking live-param. If memoized-param is empty, then the function will run the memoized body once during the first invocation.

syntax

(define/memoize-partial name
                        (memoized-param ...)
                        (live-param ...)
                        (memoized-body ...)
                        (live-body ...+))
Same as memoize-partial but defines the name.

Examples:
> (define/memoize-partial partial (x y) (a)
    ((writeln "Runs once for each unique x and y")
     (define N (+ x y)))
    ((* N a)))
> (partial 1 2 3)

"Runs once for each unique x and y"

9

> (partial)

'#&       #hasheq((1 . #hash((2 . #<procedure:...gs/memo/main.rkt:93:19>))))

> (partial 1 2 4)

12

> (partial 0 0 3)

"Runs once for each unique x and y"

0

> (partial)

'#&       #hasheq((0 . #hash((0 . #<procedure:...gs/memo/main.rkt:93:19>))) (1 . #hash((2 . #<procedure:...gs/memo/main.rkt:93:19>))))

> (partial 0 0 0)

0

Examples:
> (define/memoize-partial f (x y) ()
    ((writeln "Runs once for each unique x and y")
     (define N (+ x y)))
    ((* N 10)))
> (f 1 2)

"Runs once for each unique x and y"

30

> (f)

'#&       #hasheq((1 . #hash((2 . #<procedure:...gs/memo/main.rkt:67:19>))))

> (f 1 2)

30