memo: Memoization with cache and finalization control

8.16.0.1

memo: Memoization with cache and finalization control🔗ℹ

Kevin Robert Stravers

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 ...+) #:hash hsh 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. #:hash specifies a hash table to use for the memoized data. The default is hasheq. 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 ...+) #:hash hsh #: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 . #hasheq((2 . #hasheq((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 ...)
                 #:hash hsh
                 #:finalize finalizer
                 (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 ...)
                        #:hash hsh
                        #:finalize finalizer
                        (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 . #hasheq((2 . #<procedure:.../pkgs/memo/main.rkt:108:19>))))
> (partial 1 2 4)
12
> (partial 0 0 3)
"Runs once for each unique x and y"
0
> (partial)
'#&       #hasheq((0 . #hasheq((0 . #<procedure:.../pkgs/memo/main.rkt:108:19>))) (1 . #hasheq((2 . #<procedure:.../pkgs/memo/main.rkt:108: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 . #hasheq((2 . #<procedure:.../pkgs/memo/main.rkt:80:19>))))
> (f 1 2)
30

If hash is desired, it can be specified:

Examples:

> (define/memoize (memoize-with-hash a str) #:hash hash
str)
> (memoize-with-hash 1 "A string")
"A string"
> (memoize-with-hash 1 (string-append "A " "string"))
"A string"
> (memoize-with-hash)
'#& #hash((1 . #hash(("A string" . "A string"))))