CSE 505 Lecture Notes - 30 Sept 1994 - Evaluation in Functional Languages

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


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).

Examples:

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



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.


==============================

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.