CSE 505 Lecture Notes:

Evaluation in Functional Languages

Sept. 30, 1994

Introduction

The evaluation of an expression in a functional language can be described as a rewriting of the expression into a canonical form. The function definitions are the rewrite rules. Rewrite a function application by replacing it with the body of the function, substituting actual arguments for formals.

Example:

given the definition double x = x+x evaluate double 4 double 4 => 4+4 => 8

Normal Order vs. Applicative Order Evaluation

In general there are many possible rewriting orders. Two important ones are "normal order" and "applicative order". In normal order, you rewrite the leftmost occurrence of a function application. In applicative order, you rewrite the innermost occurrence of a function application first. To specify this completely, pick the leftmost one, although it doesn't actually matter which you pick. (Why?)

Normal order always gives the same results as lazy evaluation, although it may end up evaluating expressions more times. It corresponds to call-by-name, which we'll discuss when we come to Algol 60.

Applicative order corresponds to call-by-value (again we'll talk about this more when we come to Algol-60).

Example 1:

consider double x = x+x average x y = (x+y)/2 to avoid confusion about infix notation, let's re-express this as double x = plus x x average x y = divide (plus x y) 2 evaluate double (average 2 4) using normal order evaluation: double (average 2 4) => plus (average 2 4) (average 2 4) => plus (divide (plus 2 4) 2) (average 2 4) => plus (divide 6 2) (average 2 4) => plus 3 (average 2 4) => plus 3 (divide (plus 2 4) 2) => plus 3 (divide 6 2) => plus 3 3 => 6 Notice that (average 2 4) was evaluated twice ... lazy evaluation would cache the results of the first evaluation. using applicative order evaluation: double (average 2 4) => double (divide (plus 2 4) 2) => double (divide 6 2) => double 3 => plus 3 3 => 6

Example 2:

Now consider: my_if True x y = x my_if False x y = y evaluate my_if (less 3 4) (plus 5 5) (divide 1 0) normal order evaluation: my_if (less 3 4) (plus 5 5) (divide 1 0) => my_if True (plus 5 5) (divide 1 0) => (plus 5 5) => 10 applicative order evaluation: my_if (less 3 4) (plus 5 5) (divide 1 0) => my_if True (plus 5 5) (divide 1 0) => my_if True 10 (divide 1 0) => DIVIDE BY ZERO ERROR Important properties:

If there is any evaluation order that will terminate and that will not generate an error, normal order evaluation will terminate and will not generate an error.

ANY evaluation order that terminates without error will give the same result as any other evaluation order that terminates without error.

The Dreaded Twice Twice Twice Example

Now let's tackle a simpler version of the twice twice twice example ... twice f x = f (f x) s n = plus n 1 twice twice s 0 => twice (twice s) 0 => (twice s) ((twice s) 0) ... or dropping the extra parens: twice s (twice s 0) => s (s (twice s 0)) => s (s (s (s 0))) => s (s (s 1)) => s (s 2) => s (3) => 4 Actually, this is cheating a bit -- I happen to know that both twice and s are *strict* in both of their arguments, so I switched to applicative order evaluation. The correct order of evaluation is really: twice twice s 0 => twice (twice s) 0 => (twice s) ((twice s) 0) ... or dropping the extra parens: twice s (twice s 0) => s (s (twice s 0)) => plus (s (twice s 0)) 1 => plus (plus (twice s 0) 1) 1 => plus (plus (twice s 0) 1) 1 => plus (plus (s (s 0)) 1) 1 => plus (plus (plus (s 0) 1) 1) 1 => plus (plus (plus (plus 0 1) 1) 1) 1 => plus (plus (plus 1 1) 1) 1 => plus (plus 2 1) 1 => plus 3 1 => 4 Definition:

A function is *strict* in an argument if that argument is always evaluated whenever an application of f is evaluated. If a function is strict in an argument, we can safely evaluate the argument first if we need the value of applying the function.