Lazy Evaluation

So far, we have not paid much attention to how Haskell programs are evaluated. Perhaps you have not seen anything out of the ordinary, but then we have really only scratched the surface. When we dig a little deeper, it turns out that Haskell’s evaluation strategy is quite different from that of other languages.

While other languages eagerly evaluate the program, Haskell has a much lazier attitude. Why should it do any work when it’s not clear that work is actually necessary? That’s why Haskell puts off evaluating any part of the program until it becomes clear that no result can be produced without doing that work.

This chapter gives a good idea of how evaluation works and why there is room for different strategies. It briefly covers the most popular evaluation strategy among programming languages, Call by Value, and its opposite, Call by Name. We will learn that neither is ideal and that Haskell’s lazy evaluation strategy combines the...

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

Call by Need

Haskell’s evaluation strategy is called Call by Need or lazy evaluation. It is quite similar to Call by Name in that it only evaluates work that is needed for the result of the computation. At the same time, it avoids the main problem of Call by Name: it does not duplicate any work.

Sharing

The way in which lazy evaluation avoids duplication is known as sharing, or sometimes also as memoization. Instead of duplicating work, the work is shared, and when the work is performed once, all who share it can use the work’s results without redoing them.

Conceptually, we model sharing the work by using let binding:

  (\x -> x + x) (sin 1.0)
↣ let w = sin 1.0
   in w + w

To evaluate the sum in the body of the let binding, we first have to evaluate its left operand. As this operand is a let bound variable w, we consult the binding. The binding shows that the variable is bound to a reducible expression. Hence, we reduce...

Programming with lazy evaluation

The key benefit of lazy evaluation is that it allows for a much more compositional style of programming. Instead of writing large blocks of code from scratch, we can frequently assemble functionality out of highly reusable functions. Many key use cases of that revolve around lists.

Streaming

Let us consider what happens in the following scenario:

*Main> [1..5]

Behind the scenes, GHCi calls show on [1..5] to display the resulting list. As a reminder, we show the definitions of the key functions involved. First, the enumeration [1..5] is generated by the enumFromTo method of the Enum class:

Prelude
enumFromTo :: Integer -> Integer -> Integer
enumFromTo l h
  | l <= h = l : enumFromTo (l+1) h
  | otherwise = []

Secondly, show l is defined as showList l "":

Prelude
showList :: [Integer] -> String -> String
showList []     s = "[]" ++ s
showList (x:xs)...

Lazy memory leaks

One of the main issues with laziness is that it becomes much harder to reason about the order in which different parts of the program are executed. That in itself is not necessarily a problem, but a side effect can be. When a program does not need the result of a computation immediately but may need it later, it holds onto that computation in the form of a thunk. Over time, a build-up of such thunks can arise, and the program may start using excessive amounts of memory for them. In that case, we speak of a memory leak.

The leaking accumulator

In Chapter 3, Recursion, we saw the accumulator-based approach to summing a list:

sumAcc :: [Integer] -> Integer
sumAcc l = go l 0 where
  go :: [Integer] -> Integer -> Integer
  go []     acc = acc
  go (x:xs) acc = go xs (acc + x)

This can also be written using the foldl recursion scheme from Chapter 4, Higher-Order Functions:

sumAcc' :: [Integer...

Summary

In this chapter, we have covered the basic evaluation mechanism of functional programs, beta reduction, and evaluation strategies that decide in which order reductions are performed. The common Call by Value strategy may perform unnecessary reductions. This is prevented by Call by Name but at the cost of sometimes duplicating work. Haskell’s Call by Need (or lazy evaluation) mechanism combines the best of both: it only performs necessary reductions and never duplicates work. We can exploit this strategy for the purpose of streaming, often aided by infinite datatypes and corecursive functions. At the same time, we need to be careful about the memory allocations that arise from deferred reductions.

The next chapter explains how Haskell programs interface with their environment: the user, the file system, the operating system, and any other party outside of the program. This is particularly challenging due to lazy evaluation. Yet, Haskell has found a unique solution...

Questions

1. What is beta reduction?
2. What is Call by Need/lazy evaluation?
3. What is streaming?
4. What are strictness annotations?

Answers

1. Beta reduction is the core mechanism of program evaluation in functional programs. It acts on a function application such as (\ x -> sin x) 1.0 and simplifies it to the body of that function sin x, in which it replaces the formal parameter x with the actual parameter 1.0.
2. Call by Need is an evaluation strategy. An evaluation strategy decides which functional application to reduce in the current expression. Call by Need only reduces the top-level expression, provided it is a function application. Unlike the commonly used Call by Value strategy, this defers evaluating the function parameters and may eventually not evaluate them at all when this is not needed. At the same time, it employs a sharing mechanism known as thunks to avoid duplicating subexpressions and performing the same reduction repeatedly. In this sense, it is an improvement upon Call by Name.
3. Streaming is an approach to data processing whereby a composite data structure (e.g., a list) is not first...