6.7. STANDARDIZING TERMINOLOGY
55
;; interp : FAE DefrdSub → FAE-Value
(define (interp expr ds)
(type-case FAE expr
[num (n) (numV n)]
[add (l r) (num+ (interp l ds) (interp r ds))]
[id (v) (lookup v ds)]
[fun (bound-id bound-body)
(closureV bound-id bound-body ds)]
[app (fun-expr arg-expr)
(local ([define fun-val (interp fun-expr ds)])
(interp (closureV-body fun-val)
(aSub (closureV-param fun-val)
(interp arg-expr ds)
(closureV-ds fun-val))))]))
Figure 6.2: First-Class Functions with Deferred Substitutions: Interpreter
56
CHAPTER 6. FIRST-CLASS FUNCTIONS
Part III
Laziness
57
Chapter 7
Programming with Laziness
We have seen several teasers about the difference between eager and lazy evaluation. As you may have
guessed, once the language becomes sufficiently rich, this seemingly small difference does have a large
impact on the language’s behavior. We will now study these differences in two different contexts.
7.1
Haskell
The paradigmatic modern lazy programming language is called Haskell, in honor of Haskell Curry, who laid
the foundation for a great deal of modern programming language theory. We will study the experience of
programming in Haskell (using its own syntax) to get a feel for the benefits of laziness.
What follows is a partisan sample of Haskell’s many wonders. It is colored by the fact that this text uses
Haskell primarily to illustrate specific linguistic features, as opposed to providing a general introduction to
Haskell. The Haskell language Web site1 has references to several texts and tutorials that describe far more of the language and do so from several perspectives.
7.1.1
Expressions and Definitions
Like Scheme, simple Haskell programs do not need to be wreathed in scaffolding; and like most Scheme
implementations, most Haskell implementations provide an interactive environment. These notes use one
called Helium; others have a similar interface.
Prelude> 3
3
Prelude> True
True
(Prelude> is a Haskell prompt whose significance will soon become clear.) Haskell employs a traditional
algebraic syntax for operations (with the corresponding order of precedence), with parentheses representing
only grouping:
1http://www.haskell.org/
59
60
CHAPTER 7. PROGRAMMING WITH LAZINESS
Prelude> 2*3+5
11
Prelude> 2+3*5
17
Prelude> mod 7 4
3
Prelude> mod (mod 7 4) 2
1
As in most programming languages other than Scheme, some built-in operators are written in infix notation
while most others, including user-defined ones, are written in prefix. A prefix operator can always be used
in an infix position, however, using a special syntactic convention (note that these are backquotes):
Prelude> 7 ‘mod‘ 4
3
Prelude> (7 ‘mod‘ 4) ‘mod‘ 2
1
and infix operators can, similarly, be treated as a procedural value, even used in a prefix position:
Prelude> ((<) 4 ((+) 2 3))
True
The latter is syntactically unwieldy; why would one need it?2
We have seen integers (Int) and booleans (Bool). Haskell also has characters (of type Char) that are
written inside single-quotes: ’c’ (the character ‘c’), ’3’ (the character ‘3’), ’\n’ (the newline character),
and so on.
Based on what we’ve seen so far, we can begin to write Haskell functions. This one proposes a grading
scale for a course:
scoreToLetter :: Int -> Char
scoreToLetter n
| n > 90 = ’A’
| n > 80 = ’B’
| n > 70 = ’C’
| otherwise = ’F’
The first line of this excerpt tells Haskell the type to expect for the corresponding definition (read :: as
“has the type”). The rest of the excerpt defines the actual function using a series of rules, akin to a Scheme
conditional. Loading this definition into the Haskell evaluator makes it available to execute.3 To test the
function, we use it in the evaluator:
2Answer: Because we may want to use a traditionally infix operator, such as +, as an argument to another function. Think about
what would happen without such a notation.
3In Helium, this definition must be saved in a file whose name begins with a capital letter. Helium’s file functions can be
accessed from the menus or, as in most other Haskell implementations, from the Haskell command-line: :l followed by a filename
loads the definitions in the named file, :r reloads the file loaded most recently, and so on. The implementation manual will describe
other short-cuts.
7.1. HASKELL
61
CS173> scoreToLetter 83
’B’
CS173> scoreToLetter 51
’F’
CS173> scoreToLetter 99
’A’
Note that in typical Haskell implementations, upon loading a file, the prompt changes from Prelude to
the name of the file, indicating in which context the expression will be evaluated. The Prelude is the set of
definitions built into Haskell.
7.1.2
Lists
Haskell naturally has more sophisticated types as well. As in Scheme, lists are inductively (or recursively)
defined data-structures; the empty list is written [] and non-empty list constructor is written :. Haskell also
offers a convenient abbreviation for lists. Thus:
Prelude> []
[]
Prelude> 1:[]
[1]
Prelude> 1:2:[]
[1,2]
Prelude> 1:[2,3,2+2]
[1,2,3,4]
Note, however, that lists must be homogenous: that is, all values in a list must be of the same type.
Prelude> [1,’a’]
Type error in element of list
expression
: [1, ’a’]
term
: ’a’
type
: Char
does not match : Int
(The exact syntax of the type error will depend on the specific Haskell implementation, but the gist should
be the same. Here, Helium tells us that the second element of the list has type Char, whereas Helium was
expecting a value of type Int based on the first list element.)
Haskell’s Prelude has many useful functions already built in, including standard list manipulatives:
CS173> filter odd [1, 2, 3, 4, 5]
[1,3,5]
CS173> sum [1, 2, 3, 4, 5]
15
CS173> product [1, 2, 3, 4, 5]
120
62
CHAPTER 7. PROGRAMMING WITH LAZINESS
We can, of course, use these in the context of our new definition:
CS173> map scoreToLetter [83, 51, 99]
"BFA"
CS173> length (map scoreToLetter [83, 51, 99])
3
It takes a little practice to know when one can safely leave out the parentheses around an expression. Eliding
them in the last interaction above leads to this error:
CS173> length map scoreToLetter [83, 51, 99]
Type error in application
expression
: length map scoreToLetter [83, 51, 99]
term
: length
type
: [a]
-> Int
does not match : ((b -> c) -> [b] -> [c]) -> (Int -> Char) -> [Int] -> d
probable fix
: remove first and second argument
What?!? With practice (and patience), we realize that Haskell is effectively saying that length takes
only one argument, while the use has three: map, scoreToLetter and [83, 51, 99]. In this case,
Helium’s suggestion is misleading: the fix is not to remove the arguments but rather to inform Haskell of
our intent (first map the function, the determine the length of the result) with parentheses.
Suppose Haskell didn’t have length built in. We could build it easily, using Haskell’s pattern-matching
notation:
len [] = 0
len (x:s) = 1 + len s
Here, the argument (x:s) automatically deconstructs the list, though Haskell also provides the operators
head and tail for explicit manipulation. Notice, however, that we haven’t written a type declaration for
length. This brings us to two interesting aspects of Haskell.
7.1.3
Polymorphic Type Inference
We can ask Haskell for the type of any expression using the :type or :t directive. For instance:
CS173> :t 3
3 :: Int
CS173> :t True
True :: Bool
CS173> :t 3 + 4
3 + 4 :: Int
What should we expect when we ask Haskell for the type of len? Haskell responds with
CS173> :t len
len :: [a] -> Int
7.1. HASKELL
63
What does this type mean? It says that len consumes a list and returns an Int, but it says a little more.
Specifically, it says that the list consumed by len must have elements (recall that lists are homogenous) of
type. . . a. But a is not a concrete type like Int or Bool; rather, it is a type variable. Mathematically, we
would write this as
∀α . len : [α] → Int
That is, α is bound to a concrete type, and remains bound to that type for a particular use of len; but
different uses of len can bind α to different concrete types. We call such types polymorphic, and will study
them in great detail in Section 29.
We can see the type parameter at work more clearly using the following (trivial) function:
listCopy [] = []
listCopy (x:s) = x : listCopy s
Haskell reports this type as
CS173> :t listCopy
listCopy :: [a] -> [a]
which is Haskell’s notation for
∀α . listCopy : [α] → [α]
When we apply listCopy to different argument list types, we see that it produces lists of the same type
as the input each time:
CS173> :t listCopy [1,2,3]
listCopy [1,2,3] :: [Int]
CS173> :t listCopy [’a’,’b’,’c’]
listCopy [’a’,’b’,’c’] :: [Char]
CS173> :t listCopy [[1], [1, 2], []]
listCopy [[1], [1, 2], []] :: [[Int]]
In the last instance, notice that we are applying listCopy to—and obtaining as a result—a list of type list
of Int (i.e., a nested list of integers).
Why does Haskell assign the type parameter a name (a)? When there is only one parameter the name
isn’t necessary, but some functions are parameterized over multiple types. For instance, map is of this form:
CS173> :t map
map :: (a -> b) -> [a] -> [b]
which we might write with explicit quantifiers as
∀α, β . map : (α → β ) → [α] → [β ]
Just from reading the type we can guess map’s behavior: it consumes a function that transforms each α into
a corresponding β , so given a list of α’s it generates the corresponding list of β ’s.
In the process of studying polymorphism, we may have overlooked something quite remarkable: that
Haskell was able to generate types without our ever specifying them! This process is known as type in-
ference. Indeed, not only is Haskell able to infer a type, it infers the most general type it can for each
expression. We will study the machinery behind this remarkable power, too, in Section 29.
64
CHAPTER 7. PROGRAMMING WITH LAZINESS
Exercise 7.1.1 What would you expect is the type of the empty list? Check your guess using a Haskell
implementation.
Exercise 7.1.2 Why does Haskell print the type of multi-argument functions with arrows between each
adjacent pair of arguments? Experiment with Haskell by providing what appears to be a two-argument
function (such as map) with only one argument.
7.1.4
Laziness
Is Haskell eager or lazy? We can test this using a simple interaction:
CS173> head []
exception: Prelude.head: empty list.
This tells us that attempting to ask for the first element of the empty list will result in a run-time exception.
Therefore, if Haskell used eager evaluation, the following expression should also result in an error:
CS173> (\ x -> 3) (head [])
3
The expression (\ x -> 3) uses Haskell’s notation for defining an anonymous procedure: it is the syn-
tactic analog of Scheme’s (lambda (x) 3). Thus, the whole expression is equivalent to writing
((lambda (x) 3) (first empty))
which in Scheme would indeed result in an error. Instead, Haskell evaluates it to 3. From this, we can posit
that Haskell does not evaluate the argument until it is used, and therefore follows a lazy evaluation regime.
Why is laziness useful? Clearly, we rarely write a function that entirely ignores its argument. On
the other hand, functions do frequently use different subsets of their arguments in different circumstances,
based on some dynamic condition. Most programming languages offer a form of short-circuited evaluation
for the branches of conditional (based on the value of the test expression, only one or the other branch
evaluates) and for Boolean connectives (if the first branch of a disjunction yields true the second branch
need not evaluate, and dually for conjunction). Haskell simply asks why this capability should not be lifted
to function arguments also, and demonstrates what we get when we do.
In particular, since Haskell treats all function applications lazily, this also encompasses the use of most
built-in constructors, such as the list constructor. As a result, when confronted with a definition such as
ones = 1 : ones
Haskell does not evaluate the second argument to : until necessary. When it does evaluate it, there is a
definition available for ones: namely, a 1 followed by . . . . The result is therefore an infinite list, but only
the act of examining the list actually constructs any prefix of it.
How do we examine an infinite list? Consider a function such as this:
front :: Int -> [a] -> [a]
front _ [] = []
front 0 (x:s) = []
front n (x:s) = x : front (n-1) s
7.1. HASKELL
65
When used, front causes as many list constructions of ones as necessary until the recursion terminates—
CS173> front 5 ones
[1,1,1,1,1]
CS173> front 10 ones
[1,1,1,1,1,1,1,1,1,1]
—but no more. Because the language does not force front to evaluate its arguments until necessary,
Haskell does not construct any more of ones than is needed for front to terminate. That is, it is the act
of pattern-matching that forces ones to grow, since the pattern-matcher must determine the form of the list
to determine which branch of the function to evaluate.
Obtaining the prefix of a list of ones may not seem especially impressive, but there are many good uses
for front. Suppose, for instance, we have a function that generates the eigenvalues of a matrix. Natural
algorithms for this problem generate the values in decreasing order of magnitude, and in most applications,
only the first few are meaningful. In a lazy language, we can pretend we have the entire sequence of
eigenvalues, and use front to obtain just as many as the actual application needs; this in turn causes only
that many to be computed. Indeed, any application can freely generate an infinite list of values, safe in the
knowledge that a consumer can use operators such as front to inspect the prefix it cares about.
The function front is so useful when programming in Haskell that it is actually built into the Pre-
lude, under the name take. Performing the same computation in an eager language is considerably more
complex, because the computation that generates values and the one that consumes them must explicitly
coordinate with each other: in particular, the generator must be programmed to explicitly expect requests
from the consumer. This complicates the construction of the generator, which may already have complex
domain-specific code; worse, if the generator was not written with such a use in mind, it is not easy to adapt
it to behave accordingly.
Where else are infinite lists useful? Consider the process of generating a table of data whose rows cycle
between a fixed set of colors. Haskell provides a function cycle that consumes a list and generates the
corresponding cyclic list:
CS173> take 5 (cycle ["blue", "rondo"])
["blue","rondo","blue","rondo","blue"]
The procedure for displaying the data can consume the cyclic list and simply extract as many elements from
it as necessary. The generator of the cyclic list doesn’t need to know how many rows there will be in the
table; laziness ensures that the entire infinite list does not get generated unless necessary. In other words,
programmers often find it convenient to create cyclic data structure not so much to build a truly infinite data
structure, but rather to produce one that is large enough for all possible consumers (none of which will ever
examine more than a finite prefix, but each of which may want a different number of prefix elements).
Consider one more example. At the end of some stages of the Tour de France, the top finishers receive a
“time bonus”, which we can think of as a certain number of bonus points. Let us suppose that the top three
finishers receive 20-, 12- and 8-second bonuses, respectively, while the others receive none. Given a list
reflecting the order in which contestants completed a stage, we would like a list that pairs each name with
the number of points that person received. That is, we would like a function timeBonuses such that
66
CHAPTER 7. PROGRAMMING WITH LAZINESS
CS173> timeBonuses ["Lance", "Jan", "Tyler", "Roberto", "Iban"]
[("Lance",20),("Jan",12),("Tyler",8),("Roberto",0),("Iban",0)]
where ("Lance",20) is an anonymous tuple of two elements, the first projection a string and the second
a number. Note that the result is therefore a list of two-tuples (or pairs), where the heterogeneity of lists
forces each tuple to be of the same type (a string in the first projection and a number in the second).
We can write timeBonuses by employing the following strategy. Observe that every position gets a
fixed bonus (20, 12, and 8, followed by zero for everyone else), but we don’t know how many finishers there
will be. In fact, it isn’t even clear there will be three finishers if the organizers run a particularly brutal stage!
First let’s create a list of all the bonuses:
[20, 12, 8] ++ cycle [0]
where ++ appends lists. We can check that this list’s content matches our intuition:
Prelude> take 10 ([20, 12, 8] ++ cycle [0])
[20,12,8,0,0,0,0,0,0,0]
Now we need a helper function that will match up the list of finishers with the list of scores. Let’s define
this function in parts:
tB :: [String] -> [Int] -> [(String,Int)]
tB [] _ = []
Clearly, if there are no more finishers, the result must also be the empty list; we can ignore the second
argument. In contrast, if there is a finisher, we want to assign him the next available time bonus:
tB (f:fs) (b:bs) = (f,b) : tB fs bs
The right-hand side of this definition says that we create an anonymous pair out of the first elements of each
list ((f,b)), and construct a list (:) out of this pair and the natural recursion (tB fs bs).
At this point our helper function definition is complete. A Haskell implementation ought to complain
that we haven’t specified what should happen if the second argument is empty but the first is not:
(26,1): Warning: Missing pattern in function bindings:
tBb (_ : _) [] = ...
This message says that the case where the first list is not empty (indicated by (_ : _)) and the second one
is ([]) hasn’t been covered. Since we know the second list is infinitely long, we can ignore this warning.
Given this definition of tB, it is now straightforward to define timeBonuses:
timeBonuses finishers =
tB finishers ([20, 12, 8] ++ cycle [0])
This definition matches the test case above. We should also be sure to test it with fewer than three finishers:
CS173> timeBonuses ["Lance", "Jan"]
[("Lance",20),("Jan",12)]
7.1. HASKELL
67
The helper function tB is so helpful, it too (in a slightly different form) is built into the Haskell Prelude.
This more general function, which terminates the recursion when the second list is empty, too, is called zip:
zip [] _ = []
zip _ [] = []
zip (a:as) (b:bs) = (a,b) : zip as bs
Notice that the type of zip is entirely polymorphic:
CS173> :type zip
zip :: [a] -> [b] -> [(a, b)]
Its name is suggestive of its behavior: think of the two lists as the two rows of teeth, and the function as the
zipper that pairs them.
Haskell can equally comfortably accommodate non-cyclic infinite lists. To demonstrate this, let’s first
define the function zipOp. It generalizes zip by consuming an operator to apply to the pair of first
elements:
zipOp :: (a -> b -> c) -> [a] -> [b] -> [c]
zipOp f [] _ = []
zipOp f _ [] = []
zipOp f (a:as) (b:bs) = (f a b) : zipOp f as bs
We can recover the zip operation from zipOp easily:4
myZip = zipOp (\ a b -> (a,b))
But we can also pass zipOp other operators, such as (+):5
CS173> zipOp (+) [1, 1, 2, 3, 5] [1, 2, 3, 5, 8]
[2,3,5,8,13]
In fact, zipOp is also built into the Haskell Prelude, under the name zipWith.
In the sample interaction above, we are clearly beginning to build up the sequence of Fibonacci numbers.
But there is an infinite number of these and, indeed, there is no reason the arguments to zipOp must be
finite lists. Let us therefore generate the entire sequence. The code above is suggestive: clearly the first and
second argument are the same list (the list of all Fibonacci numbers), but the second is the first list “shifted”
by one, i.e., the tail of that list. We might therefore try to seed the process with the initial values, then use
that seed to construct the remainder of the list:
seed = [1, 1]
output = zipOp (+) seed (tail seed)
4Recall that (\ ···) is Haskell’s equivalent of (lambda ···).
5We have to enclose + to avoid parsing errors, since + is an infix operator. Without the parentheses, Haskell would try to add
the value of zipOp to the list passed as the first argument.
68
CHAPTER 7. PROGRAMMING WITH LAZINESS
But this produces only one more Fiboanacci number before running out of input values, i.e., output is
bound to [2]. So we have made progress, but need to find a way to keep seed from exhausing itself. It
appears that we want a way to make seed and output be the same, so that each new value computed
triggers one more computation! Indeed,
fibs = 1 : 1 : zipOp (+) fibs (tail fibs)
We can test this in Haskell:
CS173> take 12 fibs
[1,1,2,3,5,8,13,21,34,55,89,144]
Sure enough fibs represents the entire infinite list of Fibonacci numbers, ready for further use.
Exercise 7.1.3 Earlier, we saw the following interaction:
Prelude> take 10 ([20, 12, 8] ++ cycle [0])
[20,12,8,0,0,0,0,0,0,0]
What happens if you instead write take 10 [20, 12, 8] ++ cycle [0]? Does it result in a type
error? If not, do you get the expected answer? If so, is it for the right reasons? Try this by hand before
entering it into Haskell.
Exercise 7.1.4 The definition of the Fibonacci sequence raises the question of which “algorithm” Haskell is
employing. Is it computing the nth Fibonacci number in time linear in n (assuming constant-time arithmetic)
or exponential in n?
1. First, try to determine this experimentally by asking for the nthterm for large values of n (though you
may have trouble with arithmetic overflow).
2. Of course, even if you observe linear behavior, this is not proof; it may simply be that you didn’t use
a large enough value of n to observe the exponential. Therefore, try to reason about this deductively.
What about Haskell will determine the computation time of the nth Fibonacci?
7.1.5
An Interpreter
Finally, we demonstrate an interpreter for WAE written in Haskell. First we define some type aliases,
type Identifier = String
type Value = Int
followed by the two important type definitions:
type Env = [(Identifier, Value)]
data WAE = Num Int
| Add WAE WAE
|