unk.clj -- A pluggable, manipulable memoization library for Clojure

by Michael Fogus - http://fogus.me/fun/unk Feb. 2011 unk is a memoization library offering functionality above Clojure's core memoize function in the following ways:

Pluggable memoization

unk allows for different back-end cache implmentations to be used as appropriate without changing the memoization modus operandi.

Manipulable memoization

Because unk allows you to access a function's memoization store, you do interesting things like clear it, modify it, and save it for later.

Plugging Interface

Returns a pluggable basic cache initialied to base

Returns a pluggable FIFO cache with the cache and FIFO queue initialied to base -- the queue is filled as the values are pulled out of seq. (maybe this should be randomized?)

Returns a pluggable LRU cache with the cache and usage-table initialied to base -- each entry is initialized with the same usage value. (maybe this should be randomized?)

Returns a pluggable TTL cache with the cache and expiration-table initialied to base -- each with the same time-to-live.

Returns a pluggable LU cache with the cache and usage-table initialied to base.

Returns a pluggable soft cache initialied to base

Auxilliary functions

The basic hit/miss logic for the cache system. Clojure delays are used to hold the cache value.

Public Utilities API

Returns a snapshot of an unk-placed memoization cache. By snapshot you can infer that what you get is only the cache contents at a moment in time.

Returns true if a function has an unk-placed cache, false otherwise.

Reaches into an unk-memoized function and clears the cache. This is a destructive operation and should be used with care.

Keep in mind that depending on what other threads or doing, an immediate call to snapshot may not yield an empty cache. That's cool though, we've learned to deal with that stuff in Clojure by now.

Takes an unk-populated function and a map and replaces the memoization cache with the supplied map. This is potentially some serious voodoo, since you can effectively change the semantics of a function on the fly.

(def id (memo identity))
(memo-swap! id '{[13] :omg})
(id 13)
;=> :omg

With great power comes ... yadda yadda yadda.

Public memoization API

Builds a function that given a function, returns a pluggable memoized version of it. build-memoizer Takes a cache factory function, a function to memoize, and the arguments to the factory. At least one of those functions should be the function to be memoized.

Used as a more flexible alternative to Clojure's core memoization function. Memoized functions built using memo will respond to the core unk manipulable memoization utilities. As a nice bonus, you can use memo in place of memoize without any additional changes.

The default way to use this function is to simply apply a function that will be memoized. Additionally, you may also supply a map of the form '{[42] 42, [108] 108} where keys are a vector mapping expected argument values to arity positions. The map values are the return values of the memoized function.

You can access the memoization cache directly via the :unk key on the memoized function's metadata. However, it is advised to use the unk primitives instead as implementation details may change over time.

Works the same as the basic memoization function (i.e. memo and core.memoize except when a given threshold is breached. Observe the following:

(def id (memo-fifo identity 2))

(id 42)
(id 43)
(snapshot id)
;=> {[42] 42, [43] 43}

As you see, the limit of 2 has not been breached yet, but if you call again with another value, then it will:

(id 44)
(snapshot id)
;=> {[44] 44, [43] 43}

That is, the oldest entry 42 is pushed out of the memoization cache. This is the standard First In First Out behavior.

Works the same as the basic memoization function (i.e. memo and core.memoize except when a given threshold is breached. Observe the following:

(def id (memo-lru identity 2))

(id 42)
(id 43)
(snapshot id)
;=> {[42] 42, [43] 43}

At this point the cache has not yet crossed the set threshold of 2, but if you execute yet another call the story will change:

(id 44)
(snapshot id)
;=> {[44] 44, [43] 43}

At this point the operation of the LRU cache looks exactly the same at the FIFO cache. However, the difference becomes apparent on further use:

(id 43)
(id 0)
(snapshot id)
;=> {[0] 0, [43] 43}

As you see, once again calling id with the argument 43 will expose the LRU nature of the underlying cache. That is, when the threshold is passed, the cache will expel the Least Recently Used element in favor of the new.

Unlike many of the other unk memoization functions, memo-ttl's cache policy is time-based rather than algortihmic or explicit. When memoizing a function using memo-ttl you should should provide a Time To Live parameter in milliseconds.

(def id (memo-ttl identity 5000))

(id 42)
(snapshot id)
;=> {[42] 42}

... wait 5 seconds ...
(id 43)
(snapshot id)
;=> {[43] 43}

The expired cache entries will be removed on each cache miss.

Similar to the implementation of memo-lru, except that this function removes all cache values whose usage value is smallest.

(def id (memo-lu identity 3))

(id 42)
(id 42)
(id 43)
(id 44)
(snapshot id)
;=> {[44] 44, [42] 42}

The Least Used values are cleared on cache misses.

Not fully tested and likely buggy, use at your peril.