memo: Memoization with cache and finalization control🔗 i

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...+)#:hashhshbody...+)
(memoize (param...+)#:finalizefinalizerbody...+)

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 (nameparam...+)body...+)
(define/memoize (nameparam...+)#:hashhsh#:finalizefinalizerbody...+)

Same as memoize but defines a name in the surrounding scope.

Examples:

> (define/memoize (fibn)
(if (< n2)
1
(+ (fib(sub1 n))(fib(- n2)))))
> (fib100)

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 (fabc)(+ abc))
> (f123)

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 namebody...+)

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...)
#:hashhsh
#:finalizefinalizer
(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...)
#:hashhsh
#:finalizefinalizer
(memoized-body...)
(live-body...+))

Same as memoize-partial but defines the name.

Examples:

> (define/memoize-partial partial(xy)(a)
((writeln "Runs once for each unique x and y")
(define N(+ xy)))
((* Na)))
> (partial123)

"Runs once for each unique x and y"

9
> (partial)

'#&#hasheq((1. #hasheq((2. #<procedure:.../pkgs/memo/main.rkt:108:19>))))
> (partial124)

12
> (partial003)

"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>))))
> (partial000)

0

Examples:

> (define/memoize-partial f(xy)()
((writeln "Runs once for each unique x and y")
(define N(+ xy)))
((* N10)))
> (f12)

"Runs once for each unique x and y"

30
> (f)

'#&#hasheq((1. #hasheq((2. #<procedure:.../pkgs/memo/main.rkt:80:19>))))
> (f12)

30

If hash is desired, it can be specified:

Examples:

> (define/memoize (memoize-with-hashastr)#:hashhash
str)
> (memoize-with-hash1"A string")

"A string"
> (memoize-with-hash1(string-append "A ""string"))

"A string"
> (memoize-with-hash)

'#&#hash((1. #hash(("A string". "A string"))))

top ← prev up next →