The Evaluation Process

When evaluating an expression the mathematica kernel applies a collection  of rules to an expression until the expression no longer changes.  In the  discussion below I explain the evaluation process in greater depth.  This  discussion of the evaluation process is based on a tutorial by David Withoff  which is posted at   http://library.wolfram.com/infocenter/Conferences/4683/.   That tutorial applied to Mathematica 2.0, and further details to reflect changes in Mathematica 3.0 come from  Power Programming With Mathematica the kernel (by David Wagner).  The book by David Wagner is apparently out  of print.  As far as I know there were no changes to the evaluation process  in Mathematica 4 or Mathematica 5.

This discussion doesn't cover the use of MakeExpression, $PreRead,  $Pre, $Post, $PrePrint, FormatValues, and MakeBoxes.  That is all discussed  in an earlier section.  Each step discussed there requires completing the evaluation process  discussed in this section.

Furthermore, this discussion doesn't address  the pattern matching process.

Steps of Evaluating of  h[a1, a2, a3]

Below I talk about "external DownValues", "internal DownValues" and  likewise for UpValues, SubValues, and NValues.  External values are those  that are not part of the Mathematica kernel while internal values are those that are part of the kernel.  

The 17 steps below are repeated until an expression no longer changes, and  the decision to end the process happens in step 3 below.  When the expression  being evaluated does change the whole process starts again at the begininig  on the new expression.  In pathalogical cases such as in the next cell  evaluation completes due to exceeding $IterationLimit.  In other cases  evaluation completes due to exceeding $RecursionLimit.  I don't discuss how  counting iterarions and recursions fit into the evaluation process because I  have never seen an explanation of when that happens.

Clear[f] ;  f[x_] := f[x + 1] ;  f[2]

$IterationLimit :: itlim : Iteration limit of 4096 exceeded.

Hold[f[4097 + 1]]


This discussion overlooks the fact that NHoldAll, NHoldRest and NHoldFirst
prevent N from approximating one or more argument of affected expressions.



Also the functions Plus and Times use internal UpValues and internal
DownValues before external definitions, but that detail is overlooked
below.

Step 1
If the expression being evaluated is a symbol with an OwnValue replace  it with the OwnValue.  OwnValues are used when some value is assigned to a symbol (e.g.   x=5).

Step 2
Evaluate the head of the expression.

Step 3
If no part of the expression has changed during the last time around  this procedure, return the expression.  This is an optimazation that prevents  unecessary reevaluation of large expressions.

Step 4
If  (h) has the HoldAllComplete attribute skip to step 11 below. HoldAllComplete prevents any changes to  the arguments of a function.  

If (h) doens't have attributes that prevent  evaluation of some or all arguments, the argumenrts evaluate from left to  right.  When (h) has either attribute (HoldFirst, HoldRest, HoldAll) evaluation continues without evaluating the affected arguments.  If any  of the arguments have the head Unevaluated, then the head Unevaluated is removed and further evaluation of the  argument is prevented.  In step 17 the head Unevaluated may be restored to  the argument.

If (h) has either attribute (HoldFirst, HoldRest, HoldAll),  and an argument of (h) has the head Evaluate, then the argument evaluates  even if the attribute would have prevented evaluation.

Step 5
If (h) has the Flat attribute flatten layers of (h) as in the next cell.

ClearAll["Global`*"] ;  Attributes[h] = {Flat} ;  h[a1, h[h[a2], a3], h[a4]]

h[a1, a2, a3, a4]

Step 6
If (h) does not have the SequenceHold attribute splice together sequences.  
In the next cell Sequences are  spliced together.

ClearAll["Global`*"] ;  h[Sequence[a1, a2], Sequence[a3, a4], a5]

h[a1, a2, a3, a4, a5]


Next (h) has the SequenceHold attribute and sequences aren't spliced.

ClearAll["Global`*"] ;  Attributes[h] = {SequenceHold} ;  h[Sequence[a1, a2], Sequence[a3, a4], a5]

h[Sequence[a1, a2], Sequence[a3, a4], a5]

Step 7
If (h) has the Listable attribute thread (h) over Lists.  
This has the  same effect as evaluating  Thread[ h[a1,a2,a3] ]  when (h) isn't Listable.

ClearAll["Global`*"] ;  Attributes[h] = {Listable} ;  h[{a1, a2, a3, a4}]

{h[a1], h[a2], h[a3], h[a4]}

h[{a1, a2}, c, {b1, b2}]

{h[a1, c, b1], h[a2, c, b2]}

Step 8
If (h) has the Orderless attribute sort the arguments of (h).  
Note  the arguments are sorted in canonical order which may not be the same as  numeric order when the arguments are numeric.  This is seen in the next  cell.

ClearAll["Global`*"] ;  Attributes[h] = {Orderless} ;  h[π, 4, 2, 3]

h[2, 3, 4, π]

Step 9
Use external Upvalues for the symbolic head of of each argument of the expression.  For example  in the next cell we would use the external UpValues of (g1), then the  external UpValues of (g2),  then the external UpValues of Derivative are  used.

The "symbolic head" of an expression is the result of nesting Head  until a symbol is returned.    Notice Derivative is the symbolic head of  ( f ' [a] ).  Here we have to nest head three times to get a symbol.  The head of of   ( f ' [a] ) is (f ' ), and the head of that is Derivative[1], which finally has the  head Derivative.

ClearAll["Global`*"] ;  h[g1[a], g2[a], f '[a]] ;

Step 10
Use internal UpValues for the symbolic head of of each argument of the  expression.  For example in the previous cell we would use the internal  UpValues of (g1), then the internal UpValues of (g2),  then the internal  UpValues of Derivative are used.

Step 11
If (h) in  h[g1[a], g2[a], g3[a] ]  is a symbol, the external DownValues for (h) are used.

Step 12
If (h)  in h[g1[a], g2[a], g3[a]]  is not a symbol the external SubValues of (h) are used.  The head of the expression in the next cell is h[1].   Since (h[1]) isn't a symbol the Subvalues of (h) would be used.

h[1][a, b, c] ;

Step 13
If (h) in  h[g1[a], g2[a], g3[a] ]  is a symbol, the internal DownValues for (h) are used.

Step 14
If (h)  in h[g1[a], g2[a], g3[a]]  is not a symbol the internal  SubValues of (h) are used.

Step 15
Use external NValues if the expression being evaluated has the head N.   More precisely the NValues of the symbolic head of the first argument of N are used.

Step 16
Use internal NValues if the expression being evaluated has the head N.   As in the previous step the NValues of the symbolic head of the first  argument of N are used.

Step 17
If no UpValues, DownValues, SubValues, or NValues were used, and any  arguments of (h) did have the head Unevaluated. Then the head Unevaluated is  restored to that argument.  This is demonstrated in the next cell.

ClearAll["Global`*"] ;  a = 26 ;  h[a + 4, Unevaluated[a]]

h[30, Unevaluated[a]]


Unevaluated prevents sequences from splicing, and prevents attributes such as
Flat and Orderless from taking effect.  This is demonstrated in the next
cell.

ClearAll["Global`*"] ;  h[x + x, Unevaluated[Sequence[x, 2x], Plus[z, Plus[a, d], Plus[d, a]]]]

h[2 x, Unevaluated[Sequence[x, 2 x], z + (a + d) + (d + a)]]


However, in the next cell (h) has a downvalue that applies and we don't see
Unevaluated in the result.

ClearAll["Global`*"] ;  h[x_, y_, z_] := h[x, y]  h[4 + a, Unevaluated[a], 0]

h[4 + a, a]

Some Examples


From the discussion above it may be hard to understand the order that parts
of a complicated expression evaluate.  I provide two examples below to
demonstrate.  First evaluate the next cell which makes some definitions we
will use.

Clear["Global`*"] a1 = b1 ; a2 := {h[b2], b3} ; b2 = c2 ; b3 = b4 ;  h = g ; g[x_] := x + z ;

Consider evaluation of the example in the next cell.

{{h[a1], a2}, a1}

{{b1 + z, {c2 + z, b4}}, b1}


You could see the order of evaluation using Trace or a similar function, but
I find the output of these functions difficult to read. Instead I like to use
Print statements as I do below.

Clear["Global`*"] a1 := (Print["a1  b1"] ; b1) ; a2 ... 4; "<>ToString[x] <>"+z"] ; x + z) ;  {{h[a1], a2}, a1}

h  g

a1  b1

g[_]  b1+z

a2  {h[b2],b3}

h  g

b2  c2

g[_]  c2+z

b3  b4

a1  b1

{{b1 + z, {c2 + z, b4}}, b1}


Next consider how expressions evaluate when the head (h) in h[x] is a
non-trivial expression.  The next cell gives one such example.

Clear["Global`*"] ;  h = g ;  g[n_] := f[2 n] ;  f[n_][y_] := y^n  m = 3 ;  s = t ;   h[m][s]

t^6


The next cell shows how evaluation in this example progresses.

Clear["Global`*"] ;  h = (Print["h  g"] ; g) ;  g[ ... 4; 3"] ; 3) ;  s = (Print["s  t"] ; t) ;   h[m][s]

h  g

m  3

s  t

g[3]  f[6]

f[6][t]  t^6

t^6

Created by Mathematica  (May 17, 2004)