If we are willing to confine ourselves to functions like the example
- is defined using
DownValues only, and
- has no special attributes such as
... then the following lifting function might be useful:
, 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 // sf
(* f + f *)
f + f // sf
(* 1 + f + f *)
1 + f + f // 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] *)
stepper[f] proceeds as follows:
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
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.