Memoization in Factor

I implemented a simple memoization library in libs/memoize. If you're not familiar with this term, read about Memoization on Wikipedia.

This library can create memoized forms of words taking between 0 and 4 inputs, and one or more output. Usage is very simple -- just replace : with MEMO:, and ensure you have a stack effect declaration.

Here is the old inefficient fibonacci:

: fib ( m -- n )
    dup 1 <= [ drop 1 ] [ dup 1 - fib swap 2 - fib + ] if ;

  [ 34 fib ] time
1842 ms run / 0 ms GC time

Now lets define a memoized version:

MEMO: fib ( m -- n )
    dup 1 <= [ drop 1 ] [ dup 1 - fib swap 2 - fib + ] if ;

  [ 34 fib ] time
0 ms run / 0 ms GC time

Well, that's a nice improvement, 1842/0 = infinity times faster ;-) And only one change was necessary, the replacement of : with MEMO:.

I decided to implement this after seeing Dan's ONCE: word. Basically its a restricted form of memoization, where you have a word which performs a lengthy computation on no inputs the first time, and caches the result for subsequent calls:

ONCE: big-number 1000 factorial ;

This was used in the XML parser to build up fast lookup bit sets classifying Unicode characters from a more declarative description (see char-class.factor).

My MEMO: word generalizes ONCE:; if the word being memoized has no inputs, then it simply caches the result the first time it is called.

Take a look at libs/memoize/memoize.factor; I think it is pretty elegant.

Update Dan contributed some documentation, and made this work with words producing more than one output. Thanks Dan.