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.

The memo version looks as follows, the natural number phylum is made unique and has an attribute

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

%}

nat fib(nat $n) { zero(): {returns(zero()); } s(zero()): {returns(zero()); } s(s(x)): {returnrewrite_nat( plus(fib(x), fib(s(x)))); } }

Note the initialisation of the attribute

/* 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)returnn->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;returnresult; }