Extended remember mechanism for procedures
This functionality does not run in MATLAB.
prog::remember(f
, <depends
>, <PreventRecursion, <predef>
>)
prog::remember(f)
returns a modified copy
of the procedure f
that stores previously computed
results and additional information in a remember table. When you call f
with
arguments that you already used in previous calls, f
finds
the results in its remember table and returns them immediately.
If you assign f
to an identifier or a domain
slot, you also must assign the copy returned by prog::remember
to
the same identifier or slot, for example, f := prog::remember(f)
.
f :=
prog::remember(f)
remembers
results without context information, such as properties or the value
of DIGITS
.
The first time you call f
with any new combination
of input parameters, the remember table of f
stores `input`>`f(input)`
.
After that, when you call f
with the same input
parameters, it takes the result f(input)
from the
remember table instead of recomputing it. See Example 1.
f := prog::remember(f, depends)
remembers
results and additional context information. The dependency function depends
lets
you specify the context information to store along with computed results
in the remember table and verify in each function call. See Example 2.
Typically, it is useful to store and verify properties of the
input and the values of DIGITS
and ORDER
. To access properties
of the input, use property::depends
.
This dependency function verifies all three values:
() > [property::depends(args()), DIGITS, ORDER]
Another common problem is that an overloading function does
not register when its overloading slot changes in some other function
or domain. This dependency function that uses slotAssignCounter
lets
you avoid this problem:
() > [property::depends, slotAssignCounter("foo")]
To combine all three tasks, use this dependency function:
() > [property::depends(args()), DIGITS, ORDER, slotAssignCounter("foo")]
The first time you call f
with any new combination
of input parameters, the remember table of f
stores `[input,
depends(input)]`>`f(input)`
. After that, when you call f
with
the same input parameters, it checks whether depends(input)
returns
the same value as before. If it does, then f
takes
the result f(input)
from the remember table. Otherwise,
it computes f(input)
and adds the new values `[input,
depends(input)]`>`f(input)`
to the remember table. The
only exception to this rule is results computed with different values
of MAXEFFORT
.
If in previous calls f(input)
was computed with
lower MAXEFFORT
,
then the new call with higher MAXEFFORT
is evaluated and remembered
results are replaced with the new ones.
If the dependency function is constant or returns the value that does not depend on the input, then the remember mechanism disregards context information.
You can call the modified procedure with the Remember
option
as the first argument, and one of these special options as the second
argument:
Clear
clears the remember table
of the procedure.
ClearPrevent
clears the remember
table that prevents infinite recursions inside the procedure. For
details about preventing infinite recursions, see the description
of the PreventRecursion
option.
Print
returns the remember table
of the procedure.
For example, the call f(Remember, Clear)
clears
the remember table of f
. Also see Example 3.
Create this function:
f := X > if X > 1 then f(X  1)*f(X  2)  f(X  2) else 1 end_if:
Calling this function is timeconsuming because the function calls itself recursively and evaluates every call:
f(20), time(f(20))
Using the remember mechanism eliminates these reevaluations.
To enable the remember mechanism, use prog::remember
:
f := prog::remember(f):
f(200), time(f(200))
Create the procedure pos
that checks if its
parameter is positive:
pos := proc(x) begin is(x > 0) end_proc:
Enable the remember mechanism for pos
:
pos := prog::remember(pos):
pos
returns UNKNOWN
for variable a
:
pos(a)
Now use assume
to
specify that variable a
is positive:
assume(a > 0):
When you call pos
for variable a
,
it finds the value of pos(a)
in the remember table.
In this case, the remember table does not store the context information,
and therefore does not check for the new assumptions on variable a
.
It returns the remembered result, which is incorrect because of the
new assumption:
pos(a)
Calling pos
for a^3
returns
the correct result because pos(a^3)
is not in the
remember table yet:
pos(a^3)
Assume that a
is negative:
assume(a < 0):
Now both calls return incorrect values because the results are taken from the remember tables:
pos(a), pos(a^3)
To make the remember mechanism aware of the changes in assumptions,
use prog::remember
with the second argument property::depends
as
the dependency function:
unassume(a): pos := proc(x) begin is(x > 0) end_proc: pos := prog::remember(pos, property::depends): pos(a)
Now pos
reacts properly to the new assumption:
assume(a > 0): pos(a)
pos
also returns the correct result after
you clear the assumption:
unassume(a): pos(a)
Create the procedure pos
and enable the remember
mechanism for it:
pos := proc(x) begin is(x > 0) end_proc: pos := prog::remember(pos, getprop):
Call pos
for these parameters:
pos(a): assume(b > a, _and): pos(b):
After you call the procedure at least once, it creates the remember
table. To see the remember table of a procedure, use the special option Print
.
The value 10^{6} in
the second column is the value of MAXEFFORT
used during
computations.
pos(Remember, Print)
To clear the remember table of a procedure and thus force the
function to reevaluate all results, use the special option Clear
:
pos(Remember, Clear): pos(b)
Create the procedure deps
that collects all
operands of the properties of a given expression, including the identifiers
of assumed properties:
deps := proc(x) begin if domtype(x) <> DOM_IDENT then op(map(indets(x), deps)) else x, deps(getprop(x)) end_if end_proc:
Set the following assumption. Note that now deps
contains
potentially infinite recursions because the property of x
refers
to y
, and the property of y
refers
back to x
:
assume(x > y):
deps(x)
Error: Recursive definition [See ?MAXDEPTH]
To prevent infinite recursions, use prog::remember
with
the PreventRecursion
option:
deps := prog::remember(deps, PreventRecursion): deps(x)
To simplify the return value of deps
, rewrite
the function so that it returns a set of all identifiers:
deps := proc(x) begin if domtype(x) <> DOM_IDENT then _union(op(map(indets(x), deps))) else {x} union deps(getprop(x)) end_if end_proc: deps := prog::remember(deps, PreventRecursion):
deps(x)
Now deps
expects the return value to be a
set. By default, when recursion is detected, the procedure returns
the value of its input (which is not a set in this example). When
preventing recursion in a procedure where the type of the input differs
from the type of the return value, specify the value predef
that
the procedure returns when recursion is detected:
deps := proc(x) begin if domtype(x) <> DOM_IDENT then _union(op(map(indets(x), deps))) else {x} union deps(getprop(x)) end_if end_proc: deps := prog::remember(deps, PreventRecursion, () > {args()}):
Here predef
returns a set with the input
as an operand:
deps(x)

A procedure or function environment 

A procedure or expression 

A procedure or expression 

With this option, the procedure returned by
At the end of the function call, all remembered values are discarded. If you call the function with the same input parameters again, the function call is evaluated with the same costs as before. You can prevent recursion inside the function call and simultaneously
use the remember mechanism outside the function call by using this
syntax: 
Modified procedure or function environment