rslt ← {larg} (⍺⍺ ##.memo cache) rarg ⍝ Function memoization.
sref ← ##.cache ivec ⍝ Ref to space with initial cache.
[memo] binds an ambi-valent function left operand with a cache right operand to
produce a derived function. On application to arguments, the derived function
retrieves previously-calculated values from the cache, which it extends when
necessary with newly-calculated ones.
fast_fn ← slow_fn memo cache ⍝ bind slow_fn with cache to produce fast_fn.
[cache] is a reference to a namespace containing two vectors [keys] and [vals],
whose items are previously encountered arguments together with their correspond-
ing results. The cache is initialised using the auxiliary function [cache],
which pre-populates it with any number of expected result-argument pairs.
The technique, proposed by Donald Michie in 1968 ["Memo" functions and machine
learning, Nature, 218, 19-22], was published as an APL2 operator by Andréas
Geyer-Schultz. This more self-contained version was suggested by Stefano Lanza-
vecchia and Phil Last.
As with any caching system, care must be taken to remove from the cache, items
that become "stale" when the cached result no longer reflects external reality.
An example might be a cached file read when the "real" file component is sub-
sequently updated.
Access to the cache for maintenance purposes (a kind of inspection hatch), can
be achieved by retaining an explicit reference to its namespace.
∆foo ← cache'' ⍝ initialise cache for slow function foo.
qfoo ← foo memo ∆foo ⍝ derive "quick" version of foo.
rslt ← qfoo args ··· ⍝ using qfoo extends its cache.
∆foo.(···) ⍝ maintain cache using space-reference.
Expunging the explicit reference leaves the cache intact within the derived
function but effectively seals off external access to it. Access can be re-
covered by stopping inside memo, tabbing to the session and assigning a new
external reference.
⎕ex'∆foo' ⍝ expunge handle to foo's cache.
rslt ← qfoo args ··· ⍝ qfoo continues to function normally.
qfoo arg [Ctrl-Enter] ⍝ trace into derived function,
[Ctrl-Tab] ⍝ ... tab to session and
∆foo←⍵⍵ ⍝ ... take new external ref.
Related ancillary functions [show] and [zap], included in the examples below,
may be of some use but are considered "hors d'oeuvre" and so not fixed in the
workspace.
Technical notes:
When called, the derived function: (slow_fn memo cache) examines its cache for
the supplied argument(s) and if found, returns the corresponding result. Other-
wise, it returns a freshly-calculated result, updating the cache en passant.
memo←{ ⍝ Function memoization.
⍺←⊢ ⍝ ambi-valent.
(⊂⍺ ⍵ ⍵)∊⍵⍵.keys:⍵⍵.((keys⍳⊂⍺ ⍵ ⍵)⊃vals) ⍝ arg(s) known: fetch result.
⎕IO⊃⍵⍵.(vals keys),∘⊂←(⍺ ⍺⍺ ⍵)(⍺ ⍵ ⍵) ⍝ else: calc & extend cache.
}
Notice that the "look-up key" is (⍺ ⍵ ⍵). This is so that a monadic call with
say, a 2-item right argument is distinct from a dyadic call with 1-item left and
right argument:
call key
---- ---
monadic: ∇ 3 4 (3 4)(3 4)
∇ 2 2 2
dyadic: 3 ∇ 4 3 4 4
2 ∇ 2 2 2 2
Auxiliary function [cache] returns a reference to an unnamed space containing
two vectors "vals" and "keys". The cache is populated by calling the function
with a vector of 2 or 3 item "tuples" denoting monadic: (rslt rarg) pairs, or
dyadic: (rslt larg rarg) triples.
cache←{ ⍝ Ref to space containing initialised cache.
vals keys←↓⍉↑{ ⍝ result values and keys.
(⊃⍵)(1↓⍵,¯1↑⍵) ⍝ rslt - {larg} rarg rarg.
}¨1↓(⊂0 0),⍵ ⍝ initial values of cache.
⎕NS'vals' 'keys' ⍝ unnamed ref containing cache variables.
}
In the penultimate line above, the phrase 1↓(⊂0 0),⍵ ensures that cache's argu-
ment vector has a viable prototypical item. This means that to create an empty
cache we may merely: (cache''), rather than (cache 0⍴⊂0 0).
To initialise the cache with values for:
÷ 1 2 ⍝ monadic ÷
1 0.5
1 ÷ 2 ⍝ dyadic ÷
0.5
We would call cache thus:
cache ((1 0.5)(1 2)) (0.5 1 2)
│ │
│ └────── triple => rslt larg rarg (dyadic case)
└───────────────────── pair => rslt rarg (monadic case)
Persistent Local Variables
--------------------------
The technique of binding a space reference to a function may be used in general
to implement persistent local variables. That is, variables that are local to a
function but whose values are retained between calls. The following function
can be used to generate a stream of integers on successive calls:
next←(⎕ns'')∘{ ⍝ space bound as left arg.
0=⍵:⍺.n←0 ⍝ next 0: reset number stream.
(⍳⍺.n+←⍵)+⍺.n ⍝ next ⍵: return next ⍵ numbers.
}
next 0 ⍝ reset count.
next 1 ⍝ next number.
1
next 1 ⍝ next number.
2
next 2 ⍝ next two numbers.
3 4
next 1 ⍝ next number.
5
next 0 ⍝ reset count.
next 3 ⍝ next three numbers,
1 2 3
As Ray Cannon observes, the technique may even be used to _share_ persistent
data among several functions with no additional workspace footprint; participat-
ing functions enjoy a strictly private communication. In the following example,
[brak], [join], [bkts] and [sepr] share the same space to access communal local
variables: [lft], [rgt] and [sep].
┌∇brak─┐ ┌∇bkts─┐
│ │ ┌─────────┐ │ │
│ ├─←─┼─┐ ┌─┼─←─┤ │
└──────┘ │ ├─lft─┤ │ └──────┘
│ └─rgt─┘ │
┌∇join─┐ │ ┌─sep─┐ │ ┌∇sepr─┐
│ ├─←─┼─┘ └─┼─←─┤ │
│ │ └─────────┘ │ │
└──────┘ └──────┘
'tmp'⎕ns'' ⍝ temporary external reference to space.
brak←tmp{⍺⍺.(lft,⍵,rgt)} ⍝ function to "bracket" its argument.
join←tmp{↑,∘(⍺⍺.sep∘,)/⍵} ⍝ function to join items with separators.
bkts←tmp{⍺⍺.(lft rgt)←⍵} ⍝ function to set bracket characters.
sepr←tmp{⍺⍺.sep←⍵} ⍝ function to set separator string.
⎕ex'tmp' ⍝ remove external reference to space.
bkts'[]' ⋄ sepr'-' ⍝ set bracket and separator strings.
join brak¨'tic' 'tac' 'toe' ⍝ join bracketed char vectors.
[tic]-[tac]-[toe]
sepr'' ⍝ change separator string.
join brak¨'tic' 'tac' 'toe' ⍝ join bracketed char vectors.
[tic][tac][toe]
bkts'''' ⋄ sepr', ' ⍝ change bracket and separator strings.
join brak¨'tic' 'tac' 'toe' ⍝ join bracketed char vectors.
'tic', 'tac', 'toe'
brak join'tic' 'tac' 'toe' ⍝ bracket joined char vectors.
'tic, tac, toe'
Caveat: Techniques such as these, should be used with caution, if at all. They
are included here in the spirit of exploration, rather than as a suggestion that
they form the basis for any operational software. While interesting in their own
right, they may prove difficult to maintain as the structures will almost cert-
ainly be unfamiliar to the maintenance programmer and impenetrable to workspace
administration tools such as those for name cross-referencing and documentation.
This operator could be coded in a more elegant way if APL provided "closures".
Closures are explored further in an experimental "Function Results Edition" of
Dyalog. See: http://dfns.dyalog.com/downloads/fre.pdf
Examples:
fread←⎕fread memo(cache ⍬) ⍝ Cached file read.
fread 1 19 ⍝ Read 'n cache file component.
···
fread 1 19 ⍝ Subsequent reads satisfied from cache.
afib←{⎕IO←0 ⍝ Naïve coding of ⍺-fibonacci number.
⍵∊⍳⍺:⍵ ⍝ small number: done,
+/⍺ afib¨⍵-1+⍳⍺ ⍝ otherwise: sum of preceding ⍺ fib numbers.
}
2 afib¨⍳20 ⍝ Fibonacci sequence.
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
time←{ ⍝ Coarse function timer.
⍺←⊢ ⍝ accept monadic operand.
ai←⎕AI ⍝ start the clock.
rslt←⍺ ⍺⍺ ⍵ ⍝ apply function.
secs←⍕0.001×1↑2↓⎕AI-ai ⍝ seconds elapsed.
↑,/⍕¨rslt': 'secs' Secs' ⍝ timed result.
}
2 afib¨time⍳20 ⍝ *slow* ⍺-fibonacci sequence.
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765: 1.262 Secs
afib←afib memo(cache ⍬) ⍝ Memoize afib.
2 afib¨time⍳20 ⍝ *fast* ⍺-fibonacci sequence.
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765: 0.1 Secs
⍝ Notice that afib is coded to use its own name explicitly, rather than '∇'
⍝ for the recursion. This is so that the recursive call references the newly-
⍝ assigned derived function, whereas '∇' would have referenced the original
⍝ function and circumvented the memoization.
⍝ Perhaps surprisingly, the cache can be relied upon to supply the "base values"
⍝ of the recursion, thus simplifying the initial function coding.
fib←{ ⍝ Naïve coding of regular fibonacci number.
+/fib¨⍵-1 2 ⍝ sum of preceding 2 fib numbers.
}
fib←fib memo(cache 2/¨0 1) ⍝ Cache pre-populated with base values.
fib¨time⍳20 ⍝ Fast fibonacci sequence.
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765: 0.1 Secs
div←÷ memo (cache ⍬) ⍝ Ambivalent operand function
2 div 7 ⍝ Dyadic use distinct from ...
0.2857142857
div 2 7 ⍝ ... monadic use.
0.5 0.1428571429
osc←{ ⍝ Oscillate - probably returns 1.
2|⍵:osc 1+3×⍵ ⍝ odd: triple 'n add-one,
osc ⍵÷2 ⍝ even: halve.
}
∆osc←cache⊂1 1 ⍝ Initialise cache for osc.
osc←osc memo ∆osc ⍝ derive "fast" osc function.
∆osc.⎕nl 2 ⍝ cache-space contents.
keys
vals
show←{ ⍝ Show cache [rslts ← args]
↑⍵.(vals{⍺'←',⊂¯1↓⍵}¨keys) ⍝ (dropping extra rarg).
}
show ∆osc ⍝ Show initial cache.
1 ← 1
osc 2 ⍝ Apply derived function, extending cache.
1
show ∆osc ⍝ Show extended cache.
1 ← 1
1 ← 2
osc 3 ⍝ Apply function again.
1
show ∆osc ⍝ Show extended cache.
1 ← 1
1 ← 2
1 ← 4
1 ← 8
1 ← 16
1 ← 5
1 ← 10
1 ← 3
zap←{ ⍝ Remove value ⍵ from cache ⍺.
⍺.{ ⍝ within cache:
mask←⍵∘≡¨↓⍉↑vals keys ⍝ mask of matches.
vals keys/⍨←⊂~mask ⍝ retain non-matches.
}(⊃⍵)(1↓⍵,¯1↑⍵) ⍝ target value and key.
}
∆osc∘zap¨(1 16)(1 10)(1 3) ⍝ Zap selected cache entries.
show ∆osc ⍝ Show compacted cache.
1 ← 1
1 ← 2
1 ← 4
1 ← 8
1 ← 5
osc 3 ⍝ Re-run function.
1
show ∆osc ⍝ Partially restored cache.
1 ← 1
1 ← 2
1 ← 4
1 ← 8
1 ← 5
1 ← 10
1 ← 3
⎕ex'∆osc' ⍝ Seal access to osc's cache.
osc¨⍳10 ⍝ Derived function still operates normally.
1 1 1 1 1 1 1 1 1 1
⍝ And finally ...
delay←⎕dl memo (cache ⍬) ⍝ Cached delay.
delay time 10 ⍝ Delay 10 seconds.
10.024: 10.034 Secs
delay time 10 ⍝ Side-effect-free delay :-)
10.024: 0 Secs
See also: UndoRedo fibonacci osc
Back to: contents
Back to: Workspaces