Option remember in Procedures

Calling Sequence


option remember or options remember


Description


•

Maple provides an option for procedures to remember previous results in a ``remember table''. Subsequent invocations of the procedure with the same arguments simply retrieve the result from the remember table.

•

The remember table is implemented as an ordinary Maple table, and can be manipulated as such. It is created when the first entry is inserted into it, and accessible as operand 4 of the procedure structureuse op(4, eval(f)) if the name f has a procedure definition assigned to it.

•

If the remember option is specified in the options field of a Maple procedure, then at the end of each invocation of the procedure, an entry is made in its remember table that records the result for the specified arguments.

•

Alternatively, a procedure's remember table may be explicitly updated by a function assignment of the form f(x) := y. A procedure's remember table may also be deleted by using forget(f). For more information about this, see the help page for forget.

•

Option remember allows for the coding of a function with a recursive definition in the most natural manner, without a loss of efficiency. For example, the Fibonacci numbers computed with

F := proc(n) if n<2 then n else F(n1)+F(n2) end if end proc;




takes exponential time to compute, whereas

F := proc(n) option remember;

if n<2 then n else F(n1)+F(n2) end if end proc;




requires linear time. Alternatively, we could write

F := proc(n) F(n) := F(n1)+F(n2) end proc;

F(0) := 0;

F(1) := 1;




In this version the remember table is explicitly updated.

•

As with all Maple tables, the time required for insertion, deletion and access is very small. The main cost of using a remember table is the space used by the table and its entries.

•

By also specifying the option system in the options field of the Maple procedure, entries in the remember table are removed by the garbage collector so that the space occupied by the remember table, and the entries in it, can be freed.

•

As an alternative to remember tables, Maple also provides option cache. A cache table has a maximum number of elements it will store. When full, old elements are removed as new ones are inserted. In addition one can manually add permanent elements so that base cases of recursive procedures can still be encoded in the table.

•

When a procedure is printed with the print function, and interface(verboseproc=3) is in effect, the contents of the remember table are printed after the procedure.

•

The remember table of the builtin procedure evalf is cleared whenever numeric event handling is changed by a call to NumericEventHandler. This is because a change in event handling has the potential to change the results that evalf might return, so remembered results may be invalid.

•

Remember that tables (option remember) should not be used for procedures that are intended to accept mutable objects (such as rtables) as input, because Maple does not detect that such an object has changed when retrieving values from remember tables.



Thread Safety


•

As of Maple 17, there is a separate remember table for each thread that executes a function. This means that results calculated and stored in one thread are not available in other threads. Although this may limit the ability for results to be shared, it allows functions to manipulate their remember tables without worrying about interfering with other threads. In addition, remember tables can be used with less contention between threads.

•

By specifying the shared option in the option sequence of the Maple procedure, the remember table will be shared between threads. This provides the same behaviour as in versions before Maple 17.

•

Certain common uses of remember tables are not thread safe when using a shared table. If a procedure requires certain entries in the remember table for correctness sake (like the termination condition in the Fibonacci example above) then threads must be careful when manipulating the remember table. Changing entries required by other threads will lead to incorrect behaviour.



Examples


The Fibonacci numbers.
>

F := proc(n) F(n) := F(n1)+F(n2); end proc:

>

$F\left(0\right):=1\:$

>

$F\left(1\right):=1\:$

>

$\mathrm{op}\left(4\,\mathrm{eval}\left(F\right)\right)$

${\mathrm{table}}\left(\left[{0}{\=}{1}{\,}{1}{\=}{1}{\,}{2}{\=}{2}{\,}{3}{\=}{3}{\,}{4}{\=}{5}{\,}{5}{\=}{8}\right]\right)$
 (2) 
Notice that in computing F(5), the values for F(2), F(3), and F(4) were also computed and are also stored in the remember table.
This next example shows how to compute the Chebyshev polynomials of the first kind. Like the Fibonacci numbers, they also satisfy a two term recurrence. This time we use the remember option.
>

T := proc(n::nonnegint,x) option remember;
printf("computing T(%d,x)\n",n);
if n=0 then 1
elif n=1 then x
else expand( 2*x*T(n1,x)T(n2,x) )
end if;
end proc:

>

$T\left(3\,x\right)$

computing T(3,x)
computing T(2,x)
computing T(1,x)
computing T(0,x)
 
${4}{}{{x}}^{{3}}{}{3}{}{x}$
 (3) 
>

$\mathrm{op}\left(4\,\mathrm{eval}\left(T\right)\right)$

${\mathrm{table}}\left(\left[\left({1}{\,}{x}\right){\=}{x}{\,}\left({3}{\,}{x}\right){\=}{4}{}{{x}}^{{3}}{}{3}{}{x}{\,}\left({2}{\,}{x}\right){\=}{2}{}{{x}}^{{2}}{}{1}{\,}\left({0}{\,}{x}\right){\=}{1}\right]\right)$
 (4) 
To compute T(4,x) we need T(3,x) and T(2,x). Notice that T(3,x) and T(2,x) are not recomputed but are retrieved from the remember table.
>

$T\left(4\,x\right)$

${8}{}{{x}}^{{4}}{}{8}{}{{x}}^{{2}}{\+}{1}$
 (5) 

