Documentation |
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 paramters, 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 time-consuming 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)
f |
A procedure or function environment |
depends |
A procedure or expression |
predef |
A procedure or expression |
PreventRecursion |
With this option, the procedure returned by prog::remember uses remembered information to prevent infinite recursion inside the procedure. f := prog::remember(f, PreventRecursion, predef ) stores the input parameters only during the function call. This approach lets you avoid reevaluating the same function call when the function calls itself recursively. Instead, it returns the input (by default) or the result of the call predef(input) (if you specify predef). If returning the input is not an appropriate result for the function call (for example, if the return value of f and the input are of different types), then you must specify the value predef. See Example 4. 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: f := prog::remember(f, depends, PreventRecursion, predef ). If you want to use the remember mechanism with the context information, specify the dependency function depends as usual. If you want to use the remember mechanism without the context information and prevent recursions inside a procedure, specify depends as a constant (or any function whose return value does not depend on the input). Note that if you omit the depends function and just use the syntax f := prog::remember(f, PreventRecursion, predef ), then the remember mechanism does not work outside the function call. In this case, you only prevent recursions. |