Substitution Model

Applicative Order Reduction

Explanation

• This is what most programming languages use
• Evaluate expressions as soon as possible (“Simplify” as soon as possible)

Item	How to Handle
Primitive Expressions	Take the value
Operator Combinations	Evaluate operands, apply operator
Constant declaration	Evaluate the value expression, and replace the name by the value
Function application (function call)	Evaluate component expressions. If the function is primitive, then apply the primitive function, If the function is compound, then substitute the function with bodies of function declarations

Example

function sq(x) { return x * x; }
function sum_of_sqs(x, y) { return sq(x) + sq(y); }
function f(a) { return sum_of_sqs(a+1, a*2); }
 
f(5)
/*
-> sum_of_sqs(5+1, 5*2)
-> sum_of_sqs(6, 10)
-> sq(6) + sq(10)
-> (6*6) + (10*10)
...
-> 136
*/

Normal Order Reduction

• Expand all functions, only evaluate operators at the end

Example

function sq(x) { return x * x; }
function sum_of_sqs(x, y) { return sq(x) + sq(y); }
function f(a) { return sum_of_sqs(a+1, a*2); }
 
f(5)
/*
-> sum_of_sqs(5+1, 5*2)
-> sq(5+1) + sq(5*2)
-> ((5+1) * (5+1)) + ((5*2) * (5*2))
...
-> 136
*/