How do I evaluate only one step of an expression?

Question

I am looking for a simple, robust way to evaluate an expression only one step, and return the result in a held form.

The definition of a single step is ambiguous, and this itself is probably worthy of exploration. Some interpretations will raise the question of what should be returned. I am specifically thinking of capturing the right-hand side of function definitions and rules. Another view would be the first evaluation step that transforms the entire input expression.

Examples of desired output:

x = 1; y = 1;
q := 1 + 2 x + 3 y

(* step[q] -----> HoldForm[1 + 2 x + 3 y] *)

val = 1;
f[x_] /; x < 5 := ("X < 5"; val)
f[_, y_] := y val
f[x_] := f[x - 1]

(* step[ f[3] ]    -----> HoldForm["X < 5"; val] *)
(* step[ f[3, 4] ] -----> HoldForm[4 val]     *)
(* step[ f[5] ]    -----> HoldForm[f[5 - 1]]     *)

For an internal function:

x = 7; y = 4;

(* step[ Mod[x Pi, y] ]  -----> HoldForm[ Mod[7 Pi, 4] ] *)
(* step[ Mod[7 Pi, 4] ]  -----> HoldForm[ 7 Pi - Quotient[7 Pi, 4] 4 ] *)

each because that is the first step in Trace that transforms the entire expression.

I realize that for user-defined functions it is possible to manipulate *Values manually, but finding and matching all possible *Values is complicated, and I am looking for a universal approach using something like TraceScan. Trace keeps track of the level of evaluation with brackets, but TraceScan does not appear to provide this information to its given functions. It would be possible to use Trace and then extract the desired step afterward, but I want something that does not carry out the rest of the evaluation.

Answer 1

I believe I have found the solution I was seeking. It returns the first step that transforms the entire expression, and it does so without further evaluation.

The P = (P = part is to skip the untransformed expression.

SetAttributes[step, HoldAll]

step[expr_] :=
  Module[{P},
    P = (P = Return[#, TraceScan] &) &;
    TraceScan[P, expr, TraceDepth -> 1]
  ]

I hope that this function will be as helpful to others as I expect it will be to me.

Answer 2

We can explore the evaluation sequence using TraceScan. Let's start by defining a helper function, watch, that presents the results of TraceScan in a convenient form:

ClearAll[watch]
SetAttributes[watch, HoldAllComplete]
watch[expr_, fn_: Print] :=
  Module[{enter, exit, depth = 0}
  , SetAttributes[{enter, exit}, HoldAllComplete]
  ; enter[args__] := With[{d = depth++}, fn[Hold["enter", d, args]]]
  ; exit[args__] := With[{d = --depth}, fn[Hold["exit", d, args]]]
  ; TraceScan[enter, expr, _, exit]
  ]

Now, let's look at the evaluation of q from the supplied use cases:

In[10] := watch[q]

Hold[enter, 0, q]
Hold[enter, 1, 1+2x+3y]
Hold[enter, 2, Plus]
(* ... lots of lines omitted ... *)
Hold[exit, 3, 6, 6]
Hold[exit, 2, 1+2+3, 6]
Hold[exit, 1, 1+2x+3y, 6]
Hold[exit, 0, q, 6]

The second line of this output holds the desired result. However, things are not so easy in the next use case:

In[11] := watch[f[3]]

Hold[enter, 0, f[3]]
Hold[enter, 1, f]
Hold[exit, 1, f, f]
(* ... lines omitted ... *)
Hold[exit, 1, 3<5, True]
Hold[enter, 1, X < 5 val]
Hold[enter, 2, CompoundExpression]
Hold[exit, 2, CompoundExpression, CompoundExpression]
(* ... more lines omitted ... *)
Hold[exit, 2, 1, 1]
Hold[exit, 1, X < 5;val, 1]
Hold[exit, 0, f[3], 1]

In this case, the second line does not contain the desired result -- that result appears much further down in the trace. Note, however, that the desired result appears again in the second last line. This is also true for the q use case. Let's define step using the working hypothesis that the result of a "single step" is always the second-last line of trace output:

ClearAll[step]
SetAttributes[step, HoldAllComplete]
step[expr_] :=
  Module[{result}
  , watch[expr, # /. Hold[_, 1, r_, _] :> (result = HoldForm[r]) &]
  ; result
  ]

Here are the results for the requested use cases:

In[20]:= x=1;y=1;
         q:=1+2x+3y
         step[q]
Out[22]= 1+2x+3y

In[23]:= val=1;
         f[x_]/;x<5:=("X < 5";val)
         f[_,y_]:=y val
         f[x_]:=f[x-1]
         step[f[3]]
         step[f[3, 4]]
         step[f[5]]
Out[27]= X < 5;val
Out[28]= 4 val
Out[29]= f[5-1]

In[30]:= x=7;y=4;
         step[Mod[x Pi,y]]
         step[Mod[7 Pi, 4]]
Out[31]= Mod[7 Pi,4]
Out[32]= 7 Pi-Quotient[7 Pi,4] 4

The output in all cases matches the desired results. We seem to have a useful solution.

This solution has at least two undesirable drawbacks. First, it is based upon a heuristic that may not hold true in cases involving tricky attribute combinations or built-in functions that avoid the evaluator completely. Second, and more serious, the solution relies upon running the evaluation to completion. step would be a useful tool to debug non-terminating expressions, but the presented solution will not terminate in such cases.

It might be possible to fix the non-terminating problem by using some clever heuristics to locate the "enter" output line that corresponds to the penultimate "exit" line in trace output. The evaluation process could be terminated at that point.

Another approach would be to try to reproduce the Mathematica evaluation process ourselves. This is ambitious because some of the evaluation steps use machinery that is not exposed to us.

Yet another approach would be to lobby Wolfram to expose some kind of evaluation hook that would call a user-defined function at each evaluation step -- providing enough information to know what kind of "step" it is (e.g. head evaluation, argument evaluation, up-value resolution, down-value resolution, flattening, ordering, built-in invocation, etc).

Answer 3

I once wrote code to do a lot of things in the way of partial evaluation. Go to my collection of Mathematica tips & tricks at http://www.verbeia.com/mathematica/tips/Tricks.html

Click on "Clever Little Programs" near the bottom. Once there see my functions EvaluateAt, and EvaluatePattern. You could also see the tutorial (by Robby Villegas of Wolfram Research) that I refer to.

To learn details of the evaluation process see my sections on "the evaluation process" and "where definitions are stored".

Answer 4

There is a general way to capture the right hand side of definitions using DownValues and OwnValues.

For instance, using your definitions:

In[7]:= OwnValues[q]

Out[7]= {HoldPattern[q] :> 1 + 2 x + 3 y}

In[8]:= OwnValues[val]

Out[8]= {HoldPattern[val] :> 1}

In[14]:= DownValues[f]

Out[14]= {HoldPattern[f[x_] /; x < 5] :> ("X < 5"; val), 
HoldPattern[f[_, y_]] :> y val, HoldPattern[f[x_]] :> f[x - 1]}

I realize this is not quite the functionality you want--it is not a fully general notion of a "step". But as you point out, the "evaluation step" may be an ambiguous or inconsistent. Not knowing how the kernel works, I am not sure.