Innermost evaluation :

Under the innermost-evaluation rule, the evaluation of a function application

<name><actual-parameter>

proceeds as follows :

-- Evaluate the expression represented by <actual-parameter>.

-- Substitute the result for the formal in the function body.

-- Evaluate the body.

-- Return its value as the answer.

Each evaluation of a function body is called an activation of the function.

The approach of evaluating arguments before the function body is also referred to as call-by-value evaluation. Call-by-value can be implemented efficiently, so it is widely used.

Under call-by-value, all arguments are evaluated, whether their values are needed or not.

Outermost evaluation :

Under the outermost-evaluation rule, the evaluation of a function application

<name><actual-parameter>

proceeds as follows :

-- substitute the actual (without evaluating it) for the formal in the function body.

-- Evaluating the body.

-- Return its value as the answer.

Innermost and outermost evaluation produce the same result if both terminate with a result.

The distinguishing difference between the evaluation methods is that actual parameters are evaluated as they are needed in outermost evaluation; they are not evaluated before substitution.

Standard ML uses call-by-value or innermost evaluation.

Short-circuit evaluation :

The operation andalso and orelse in ML perform short-circuit evaluation of boolean expressions, in which the right operand is evaluated only if it has to be.

E andalso F is false if E is false; it is true if both E and F are true. The evaluation of E andalso F proceeds from left to right, with F being evaluated only if E is true.

So, E andalso F may terminate even if F does not.

The evaluation of E orelse F is true if E evaluates to be true. F is skipped if E is true.

The 91-function :

fun f(x) =

if x > 100 then x - 10 else f(f(x+11)) ;

f(100) = if 100 > 100 then 100 - 10 else f(f(100+11))

= f(f(100+11)

= f(f(111))

= f( if 111 > 100 then 111 -10 else f(f(111+11))

= f(101)

= if 101 > 100 then 101 - 10 else f(f(101+11))

= 101 - 10

= 91

Outermost evaluation :

f(100) = if 100 > 100 then 100 - 10 else f(f(100+11))

= f(f(100+11))

= if f(100+11) > 100 then f(100+11) - 10 else f(f(f(100+11)))

.......

Outermost vs innermost evaluation :

Outermost appears to do more work than innermost.

Outermost can terminate where innermost fails .

fun or(x,y) =

if x then true else y ;

-- under innermost-evaluation , both subexpression E and F are evaluated before they are substituted into the function body. So, or(true,F) results in a nonterminating computation if the evaluation of F does not terminate.

-- Under outermost -evaluation,

or(true,F) = if true then true else F ;

so the computation terminates regardless of the evaluation of F terminates or not.

Since ML uses innermost evaluation, the operator orelse has to be provided by the language. It cannot be user-defined as part of a program.

VAL BINDINGS :

The occurrence of x to the right of the keyword val in

let val x = E₁ in E₂ end

is called a binding occurrence or simply binding of x.

All occurrences of x in E₂ are said to be within the scope of this binding.

The occurrences of x within the scope of a binding are said to be bound.

A binding of a name is said to be visible to all occurrences of the name in the scope of the binding.

Eg.

let val x = 2 in let val x = x + 1 in x * x end end

The value of an expression is left undisturbed if we replace all occurrences of a variable x within the scope of a binding of x by a fresh variable :

let val x = 2 in

let val y = x + 1 in y * y end end

let fun f(x) = E₁ in E₂ end

The occurrences of f and x to the right of keyword fun are bindings of f and x.

let x = 2 in

let fun f(x) = x + 1 in f(x) end end