# How do I evaluate only one step of an expression?

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.

-
Interesting question. You can do something similar interactively using the built-in debugger (I know that this does not answer your question) –  acl Jan 20 '12 at 10:19
Have a look at this answer by WReach: stackoverflow.com/questions/6234701/…. I think this is as close to it as one gets. –  Leonid Shifrin Jan 20 '12 at 13:33
I asked a question about this on MathGroup a few years ago. It won't answer your question, but the replies are worth a look. See it here or here. –  Szabolcs Jan 20 '12 at 13:36
@Leonid I voted for that very answer, but I guess I forgot about it. I suppose it planted the idea to use TraceScan. I need to review that function to see if it can be easily adapted to stop at the "correct" step of evaluation. –  Mr.Wizard Jan 20 '12 at 13:40

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.

-
what's the second argument on Return? +1 for the P=(P –  Rojo Feb 7 '12 at 18:36
@Rojo the second argument of Return specifies which function to break out from. It's almost undocumented but there is this page in the help browser: ref/message/Break/nofunc –  Mr.Wizard Feb 7 '12 at 21:20
step[f[2*(1+1)]] returns f[4] while step[2*(1+1)] returns 2*2. This is somewhat counterintuitive for me but I admit I haven't thought much about what a single step should/could mean. –  Szabolcs Feb 8 '12 at 0:33
@Szabolcs thank you for examining this. I agree that is counter-intuitive and if I can think of any way to improve it I shall. This is however "the first step in Trace that transforms the entire expression" as described in the question. I believe this still has significant utility (if it indeed works that way) because it in essence allows one to extract the RHS of a complicated definition without digging through *Values. Certainly there are other interesting points at which to stop evaluating f[2*(1+1)] such as the evaluation of f itself. I am not sure how to address all of these. –  Mr.Wizard Feb 8 '12 at 0:37
If you change the return value from # to # /. HoldForm[x_] :> Defer[step[x]], then the resulting expression is in a convenient form for further stepping. One can repeatedly type SHIFT-CONTROL-L, SHIFT-ENTER to step through the surface evaluations until the expression goes inert. –  WReach Feb 8 '12 at 14:10

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).

-
Thank you for a lengthy reply. I have not walked through the code, but I notice you state: "the solution relies upon running the evaluation to completion." If I accept that I think it would work to use a simple Trace and just pick the first object for which Head[#] =!= List && # =!= HoldForm[original]. What do you think? –  Mr.Wizard Jan 22 '12 at 7:15
@Mr.Wizard Yes, that would seem to be a reasonable heuristic as well. I show the TraceScan solution because it offers the possibility of short-circuiting the evaluation if the right heuristic can be found -- a heuristic that has eluded me so far. –  WReach Jan 22 '12 at 16:52
Please tell me if the answer I added below is useful to you (and also if it works as I believe it does). –  Mr.Wizard Feb 8 '12 at 0:09
@Spartacus Very clever. TraceDepth -- well spotted! And a cheeky way to pick out the second evaluation. The definition certainly seems to handle conventional definitions correctly. Yes, it is useful. Well done. And +1. –  WReach Feb 8 '12 at 5:42
WReach this answer can be greatly simplified using TraceLevel[] as in: TraceScan[Print[TraceLevel[], " : ", ##] &, Sin[x]^2 + b] –  Mr.Wizard Feb 8 '12 at 10:01

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

Click on "Cleaver 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".

-
Welcome Ted Ersek! It's great having more and more of the people I learned Mathematica from joining this site. –  Mr.Wizard Feb 8 '12 at 5:40
Greetings Ted! Great to see you here. –  Verbeia Feb 8 '12 at 7:46
@Ted, over the years your tips/tricks have been invaluable to me. However, I cannot see how the two functions you mention specifically relate to this question. –  Mr.Wizard Feb 8 '12 at 7:50
+1 for the link to Verbeia! Like stepping into a candy store.. –  Lou Apr 1 '12 at 8:57
@Ted Ersek,Dear Ted Ersek, Is it possible for me to have a PDF file that sites verbeia.com/mathematica/tips/Tricks.html owned resourse? I'd like to print these good tricks out to learn. Thanks sincerely:-) –  ShutaoTang Sep 18 at 9:42

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

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.

-
I am aware of this functionality but it is not, by itself, what I am seeking. If I want only the (held) RHS for e.g. f[3] one would still have to search the DownValues for this. Further, I think that depending on Own/Down/Up/Sub etc. values that are defined, figuring out which matches may be complicated (unless you can propose and automatic approach). –  Mr.Wizard Jan 20 '12 at 12:46
Yes, I see. Sorry I cannot help further. –  JOwen Jan 20 '12 at 12:58
JOwen, if this functionality is of interest to you please see the answer I posted below. I think it works quite generally. –  Mr.Wizard Feb 8 '12 at 0:11