Evaluation strategies

Before we delve into Haskell’s evaluation strategy, let us first consider what an evaluation strategy is. This is an aspect of a programming language that is usually not questioned or mentioned because most languages adopt the same strategy and act alike. This section shows that there is room for variation and that there are good reasons for deviating from the mainstream strategy.

Beta reduction

The mechanism at the core of program evaluation in function programming is called beta reduction. It defines how a function call should be evaluated. Let us take a small example of a function call (also called a function application):

(\ x -> sin x) 1.0

Here the (anonymous) (\ x -> sin x) function maps its formal parameter x to the function body sin x. This function is applied to the actual parameter 1.0.

Conceptually, the function call is evaluated, or reduced, by replacing it with a simpler expression. That simpler expression is the function body in which the formal parameter is replaced by the actual parameter. In our example, the x in sin x is replaced with 1.0 that yields the following:

sin 1.0

We will use a special arrow ↣ to denote such a reduction step:

(\ x -> sin x) 1.0  ↣  sin 1.0

Evaluation

In general, reducing one function call may reveal another. Program evaluation strings together beta reductions as long as there is a function call to reduce. Take this, for instance:

((\ f -> f) (\ x -> sin x)) 1.0

There are two functions called here:

• The function (\ f -> f) is called on (\ x -> sin x)
• The function ((\ f -> f) (\ x -> sin x)) is called on 1.0

However, only the first call can be reduced. The reason for that is that its function (\ f -> f) is directly given, whereas the function in the second call is a complex expression that first has to be reduced to reveal what its definition is. Hence, the only call that can at first be reduced is the first one. We have the following:

(\ f -> f) (\ x -> sin x) ↣ (\ x -> sin x)

Reduction is compositional; if we can reduce a part of a larger expression, the whole expression reduces accordingly. Hence, we have this:

((\ f -> f) (\ x -> sin x)) 1.0 ↣ (\ x -> sin x) 1.0

Here, we have underlined the function call that we have reduced. This is a useful convention when there is more than one function call in the expression.

If we combine this with the next reduction step, we get this:

  ((\ f -> f) (\ x -> sin x)) 1.0
↣ (\ x -> sin x) 1.0
↣ sin 1.0
↣ 0.8414709848078965

The third step is special because sin is a built-in function not defined in Haskell itself. Hence, we (pretend to) immediately step to its result. The last expression does not contain any further function calls and is thus the overall result of the program.

Evaluation strategies

It may be the case that an expression contains multiple function calls that can be reduced. Take this, for instance:

(\x -> x) ((\y -> sin y) 1.0)

This contains calls to two functions, (\x -> x) and (\y -> sin y), that can both be reduced. Hence, there is room to choose which call to reduce first. If we choose the first call, we get this:

  (\x -> x) ((\y -> sin y) 1.0)
↣ (\y -> sin y) 1.0
↣ sin 1.0
↣ 0.8414709848078965

Alternatively, we reduce the second call first:

  (\x -> x) ((\y -> sin y) 1.0)
↣ (\x -> x) (sin 1.0)

At this point, we can again choose which call to reduce first:

  (\x -> x) (sin 1.0)              (\x -> x) (sin 1.0)
↣ sin 1.0                       ↣ (\x -> x) 0.8414709848078965
↣ 0.8414709848078965            ↣ 0.8414709848078965

As we can see, there are already three ways to evaluate this small example expression. For larger programs, the number of possibilities can be huge. Of course, in practice, a compiler or interpreter wants to use a systematic approach to choose among the possibilities. Such a systematic approach is called an evaluation strategy. Does it matter what evaluation strategy is used? Yes and no:

• No, it does not matter, because all choices eventually yield the same result. We can see this clearly in the example; all three evaluation approaches yield the result 0.8414709848078965.
• Yes, it does, because the strategy affects the efficiency of evaluation. Some approaches require more reduction steps than others for particular programs. In an extreme case, some approaches may fail to terminate with a result, while others don’t.

Let us investigate what the impact of the evaluation strategy is by comparing two extreme choices before appreciating the middle ground that Haskell chooses.

Call by Value

The Call by Value evaluation strategy is the one most commonly found in programming languages. Hence, you are most likely already familiar with this strategy and may have expected that Haskell would behave accordingly (but it does not).

The idea of Call by Value is that a function call should only be reduced when its parameter is already fully reduced—a fully reduced expression is called a value. A practical consequence of this choice is that the innermost function call is reduced first.

This is the call-by-value reduction of our example expression:

   (\x -> x) ((\y -> sin y) 1.0)
↣ (\x -> x) (sin 1.0)
↣ (\x -> x) 0.8414709848078965
↣ 0.8414709848078965

What is good about Call by Value is that it is a steady and predictable strategy, which is easy to replicate in one’s mind. It can also be implemented efficiently.

A downside of Call by Value is that it may do unnecessary work. The following variation on the earlier example illustrates this:

   (\x -> 5) ((\y -> sin y) 1.0)
↣ (\x -> 5) (sin 1.0)
↣ (\x -> 5) 0.8414709848078965
↣ 5

Here, we reduce the inner function call and compute the sine that follows from it. Yet, the outer function is not interested in the result; it discards the sine’s value and simply returns 5. Hence, we have performed two unnecessary reduction steps.

We can easily make the redundant work arbitrarily large. In the extreme case, the redundant work runs forever and causes overall non-termination. Consider this looping example:

   (\x -> 5) (loop 1.0)
↣ (\x -> 5) (loop 1.0)
↣ (\x -> 5) (loop 1.0)
↣ …
where
loop :: a -> a
loop x = loop x

Another issue may be that the redundant work causes a runtime error:

  (\x -> 5) (div 1 0)
↣ *** Exception: divide by zero

A smarter evaluation strategy can avoid doing redundant work and thus be more efficient for some programs.

Call by Name

The opposite extreme of Call by Value is Call by Name. Call by Name reduces the outermost function call first. This avoids the redundant work that Call by Value takes on:

  (\x -> 5) ((\y -> sin y) 1.0)
↣ 5

As the outer function is not using its parameter, Call by Name yields the result in a single reduction step. Likewise, in the cases where the parameter is looping or raising a runtime error, Call by Name simply sidesteps those issues. Hence, it can be arbitrarily more efficient than Call by Value. Unfortunately, the opposite is also true. A big flaw of Call by Name is that it may duplicate work. Consider the following:

  (\x -> x + x) (sin 1.0)
↣ sin 1.0 + sin 1.0
↣ 0.8414709848078965 + sin 1.0
↣ 0.8414709848078965 + 0.8414709848078965
↣ 1.682941969615793

Because the outer function mentions its formal parameter x twice in the body, Call by Name creates two copies of the actual parameter sin 1.0. These two copies both need to be reduced to produce the overall result. That is of course a pointless duplication of work. Moreover, it can get arbitrarily worse if the function references its formal parameter an arbitrary number of times.

Further downsides of Call by Name are that its reduction steps are more expensive to implement and that it is harder for programmers to reason about its order of evaluation. Overall, this makes Call by Name simply not useful enough to be used in practice. Nevertheless, Call by Name is a useful reference for Haskell’s evaluation strategy, which adopts the main advantage of Call by Name but not its main weakness. We will see next how this is achieved.