Among the chief distinctions among programming languages is whether function calls are evaluated using a strict or lazy approach. Most commonly used languages employ strict evaluation where all parameters to a function are evaluated before the function is called. This approach is also called call-by-value and is used by Scheme, ML, Java, and C among others.
Haskell uses a lazy evaluation mechanism where parameters are evaluated only when their values are needed. This approach is also called call-by-name and frequently implemented using a call-by-need algorithm.
Before proceeding, let’s determine whether our interpreters implement
a strict or lazy approach. Look at the code for evaluating App from
the interpreter for FBAE:
evalM env (App f a) = do { (Lambda i b) <- (evalM env f) ;
a' <- (evalM env a) ;
evalM ((i,a'):env) b
The first argument to App is evaluated to get back a Lambda. The
second argument is evaluated and assigned to a'. eval then
evaluates the lambda body by adding (i,a') to the environment and
evaluating. What is stored in the environment is the result of
evaluating the lambda’s actual parameter implying that it is
evaluated before the function gets called. It should be clear that
our evaluator implements call-by-value or strict evaluation.
How hard is it to change to call-by-name? Turns out rather simple.
If we don’t want to evaluate a just store a in the environment
without evaluating it first:
evalM env (App f a) = do { (Lambda i b) <- (evalM env f) ;
evalM ((i,a):env) b
All we did was delete the evaluation of a and that’s it. In this
case, the argument is passed to the lambda without evaluation and we
have implemented call-by-name or lazy evaluation. The only additional
change is to the type Env that must store FBAE abstract syntax
rather than values:
type Env = [(String,FBAE)]
There you go. Now we have a lazy interpreter to go with our strict interpreter.
Most languages are strict, but a few like Haskell are lazy. Why choose one over the other? As with most decisions, there is good and bad to both.
First let’s look at the biggest problem with lazy evaluation semantics. Look at this function:
bind silly = lambda x in x + x + x + x + x + x + x + x + x + x in
(silly (silly (silly 1 + 3 - 7 + (f 5) + 21)))
This really silly function uses x over and over again. Using strict
semantics, the actual parameter to silly is evaluated only once.
Using lazy semantics, the actual parameter to silly is evaluated every
silly place you see x. That’s pretty huge. Call-by-need evaluation
semantics eliminates this problem by replacing every instance of x
with a kind of pointer to one common x. Whenever x is evaluated,
that one x is evaluated once and all copies are immediately replaced
with the same value.
On the other hand, this if expression does not evaluate silly at all:
bind silly = lambda x in x + x + x + x + x + x + x + x + x + x in
if 0 then (silly 5) else 5
It’s never used in the if and thus not evaluated. Using strict
semantics it would be. if itself shows the distinction between lazy
and strict. If we wrote if as a function, strict semantics causes
problems. Look at this psuedocode:
if x y z = lambda x in lambda y in ...
Using strict semantics, x, y, and z are all evaluated before
if is evaluated. This is a problem because we only want to evaluate
one of y or z. Using lazy semantics, if can be implemented by a
simple data type:
data Boolean where
true :: Boolean
false :: Boolean
if x y z = case x of
true -> y
false -> z
Pretty groovy. if is not special, but is just an ordinary function.
The final pro-lazy argument has to do with infinit structures. One can define a list in Haskell like this:
alt10 = 1:0:alt10
If this were done in a strict language, it would be infinite. In
Haskell as long as you don’t evaluate alt10 directly. In strict
languages, pointers are used to accomplish a similar behavior. The
pointer value is evaluated without evaluating what it points to.
App, - AppS and AppL. Do not worry
about a concrete syntax. Simply replace App in the abstract
syntax and define a new eval function.