If we are willing to confine ourselves to functions like the example f
which:
- is defined using
DownValues
only, and
- has no special attributes such as
HoldAll
, etc.
... then the following lifting function might be useful:
ClearAll[stepper]
SetAttributes[stepper, HoldAll]
stepper[f_Symbol] :=
Module[{rules, g}
, rules =
Rule @@@ Cases[DownValues[f], (l_ :> r_) :> ((Hold[r] /. f -> g) /. _[rr_] :> Hold[l, rr])]
; Function[Null, Defer[#]&[Unevaluated@# /. rules] /. g -> f, HoldAll]
]
stepper[f]
returns an evaluator function which, when applied to an expression, evaluates the expression normally except that the rules associated with f
are not invoked recursively. So, for example:
sf = stepper[f];
f[3] // sf
(* f[1] + f[2] *)
f[1] + f[2] // sf
(* 1 + f[0] + f[1] *)
1 + f[0] + f[1] // sf
(* 3 *)
f[n+1] // sf
(* f[-1+n] + f[n] *)
f[-1+n] + f[n] // sf
(* f[-3+n] + 2*f[-2+n] + f[-1+n] *)
f[-3+n] + 2*f[-2+n] + f[-1+n] // sf
(* f[-5+n] + f[-4+n] + f[-3+n] + 2*(f[-4+n] + f[-3+n]) + f[-2+n] *)
Evaluation using stepper[f]
proceeds as follows:
- The
DownValues
of f
are copied and transformed so that all right-hand-side occurrences of f
are replaced with an inert symbol (this occurs once).
- An expression is evaluated by applying the transformed down-value rules, forestalling any recursive application of
f
since it no longer appears in any of the rule bodies.
- The result is wrapped in
Defer
.
f
is restored in place of all occurrences of the inert symbol within the deferred expression.
The implementation of stepper
is complicated somewhat by the need to dodge some inconvenient variable renaming within scoping constructs and to prevent early evaluation of the right-hand-sides of rules.
This methodology could be applied to a more elaborate evaluator that handles symbol attributes, UpValues
, and so on. But the evaluator complexity grows rapidly with these extra features and the exhibited form of stepper
might be useful enough as is.
i = 0;f[0] := 1;f[1] := 1;f[n_] /; i++ < 2 := f[n - 1] + f[n - 2];f[8]
$\endgroup$