Introduction to Mathematical Software

21-126, Spring 2000
Dr. David Handron

Lesson 4

Evaluation Rules (Programing the kenel)

Delaying Evaluation

Suppose we want the function f[x] to return true if x was prime or divisible by 4. Using the tools we've just learned it is natural to try:

Clear[f] 
f[x_] = PrimeQ[x] || MatchQ[x/4,_Integer] 
?f

Remember that Mathematica always fully recursively evaluates each expression. In the above, PrimeQ[] and MatchQ[] and Or[] were called with the symbolic constant x which is neither prime nor divisible by four.

PrimeQ[x] 
MatchQ[x/4, _Integer] 
% || %%

This is an instance where we don't want Mathematica to fully evaluate the expression, we want it to  wait until f[x_] is matched. This is accomplished using the SetDelayed[] command which has the short form := (colon equals, without any gaps in between).

Clear[f] 
f[x_] := PrimeQ[x] || MatchQ[x/4,_Integer] 
?f

Now Mathematica will wait until f[x_] is evaluated, so that we can use f[] as intended.

f[16]

The evaluation of this process went something like: 
1)	f[16] matches f[x_] with x = 16 
2)	This is evaluated to (PrimeQ[16] || MatchQ[16/4, _Integer] ) 
3)	This is then evaluated to (PrimeQ[16] || MatchQ[4, _Integer]) 
4)	PrimeQ[] and MatchQ[] are evaluated to give (False || True) 
5)	Finally Or[] is evaluated to give (True)  
 
Mapping f[] onto a list gives a Boolean list.

Map[f, Range[20]]Select[Range[20], f]

Conditional Evaluation

The following two of rules can be used to compute n factorial.
 
	1) If n = 0 then n factorial = 1 
	2) If n > 0, (and n is an integer) then n factorial is the product of n and (n-1) factorial 
	 
The idea is to compute n! as n (n-1)!, and to continue on until we have

	n! = n (n-1)! = n (n-1) (n-1)! = n (n-1)(n-2) ..... 2 . 1

These two evaluation rules are specified as:

Clear[f] 
f[n_Integer] := 1 		 /; n == 0 
f[n_Integer] := n f[n-1] /; n > 0 
?f

Before explaining this new syntax, let's try a few examples.

f[3] 
f[10]

As a check:

3! 
10!

f[x] 
f[1.0]

The /; is an abbreviation for the Condition[] command.

FullForm[Hold[ a /; b ]]

This command is used to control evaluation when using := (SetDelayed[]), and like /. (ReplaceAll[]) and -> (Rule[]) we will almost never use the long form of /;. The expression appearing after the /; must evaluate to a true or false, and can use the Boolean operations &&, ||, == (and, or, equals) etc. to form very specific conditions for particular rules. 
 
Let's step through the evaluation process for f[3] 
 
	    f[3] 	= 3 f[2]		by rule 2 
		= 3 (2 f[1]) = 6 f[1]	by rule 2 
		= 6 (1 f[0]) = 6 f[0]	by rule 2 
		= 6 1			by rule 1 
		= 6 
 
Notice that Mathematica is using full recursive evaluation. Every time it applies a rule and gets something different (eg. f[3] evaluated to 3 f[2]) it applies all the rules afresh to the new result(s). Note too that the intermediate result 3 (2 f[1]) was simplified according to 
 
     3 (2 f[1]) = Times[3, Times[2,f[1]] ] = Times[3, 2, f[1]] = Times[6, f[1]] = 6 f[1] 
      
  so Mathematica was quite busy after we entered f[3] for evaluation. 
     
(The first step of converting Times[3, Times[2, f[1]] ] to Times[3,2,f[1]] is automatically done by the kernel, and the Times[] function then simplified this to Times[6,f[1]], but we postpone the discussion of these finer points.)