Memo Functions

Memo functions remember (`memorize') their results. If called again with the same arguments, they will return the remembered value. Memo functions are functional in their behaviour: a subsequent call with the same argument will yield the same result. In their performance they are not functional: the subsequent call will not need recomputation. Memo functions of course constitute a time/space trade off . Their performance comes at the expense of memory to store the results (and, in some schemes, memory to store the operands).

Using the term processor, memo-functions of one argument can be implemented as an attribute of the phylum of the argument term. Memo-functions of more than one argument can be implemented as an attribute of a uniquely represented term that represents the function call. E.g. for a function F of two arguments one introduces a term F_memo(x,y) of which the function result is an attribute. In both approaches it is essential that the arguments of the function are represented uniquely.

An example to illustrate memo functions is the Fibonacci function. This is a good example because the standard recursive definition recomputes the same result over and over again. For example, fib(5) uses fib(4) and fib(3), but for fib(4), fib(3) is also computed. It is also a silly example, because the best solution is a simple iteration. Furthermore we use abstract data type natural numbers, and the cost of the rewrite functions outweighs the costs of Fibonacci. The non-memo solution looks as follows, the phylum and rewrite definitions are from the previously discussed natural numbers example.       

/* Fibonacci */
%{
#include "rk.h"
%}


nat fib(nat $n) {
    zero():     { return s(zero()); }
    s(zero()):  { return s(zero()); }
    s(s(x)):    { return rewrite_nat( plus(fib(x), fib(s(x)))); }
}

The memo version looks as follows, the natural number phylum is made unique and has an attribute fib to store the result.

/* Fibonacci with memo function */
nat{uniq}:      zero()
|               s(nat)
|               plus(nat nat)
{               nat fib = (nat)0; }
;


/* rewrite rules omitted */


%{
#include "rk.h"
%}


nat fibm(nat n) {
    nat result;
    if (n->fib != (nat)0) return n->fib;
    with(n){
        zero():         { result = s(zero()); }
        s(zero()):      { result = s(zero()); }
        s(s(x)):        { result = rewrite_nat( plus(fibm(x), fibm(s(x)))); }
    }
    n->fib = result;
    return result;
}

Note the initialisation of the attribute fib. We take the nil pointer to mean `no value known yet'. In the second line of the function body the test is made for this, and in the second last line the result is stored. Measurements show that computing fib(15) (which is 987) takes 1973 calls on fib. In fibm the with-statement is entered only 16 times. However, as stated, using rewriting to compute addition makes this hardly noticeable on total run time. Both functions compute plus(377, 610) exactly once, and this takes most of the time.