Can we do better? Of course: once we have computed the value of an identifier, instead of only using it,
we can also cache it for future use. Where should we store it? The expression closure is a natural container:
the next time we attempt to evaluate that closure, if we find a value in the cache, we can simply use that
value instead.
To implement caching, we modify the interpreter as follows. First, we have to create a field for the
value of the expression closure. What’s the value of this field? Initially it needs to hold a dummy value, to
eventually be replaced by the actual one. “Replaced” means its value needs to change; therefore, it needs to
be a box. Concretely, we’ll use the boolean value false as the initial value.
(define-type CFAE/L-Value
[numV (n number?)]
[closureV (param symbol?)
(body CFAE/L?)
(env Env?)]
[exprV (expr CFAE/L?)
(env Env?)
(cache boxed-boolean/CFAE/L-Value?)])
We define the cache’s field predicate as follows:
(define (boxed-boolean/CFAL-Value? v)
(and (box? v)
(or (boolean? (unbox v))
(numV? (unbox v))
(closureV? (unbox v)))))
Notice that we carefully exclude exprV values from residing in the box. The box is meant to cache the result
of strictness, which by definition and construction cannot result in a exprV. Therefore, this exclusion should
never result in an error (and an indication to the contrary should be investigated).
Having changed the number of fields, we must modify all uses of the constructor. There’s only one: in
function application.
[app (fun-expr arg-expr)
(local ([define fun-val (strict (interp fun-expr env))]
[define arg-val (exprV arg-expr env (box false) )])
(interp (closureV-body fun-val)
(aSub (closureV-param fun-val)
8.3. CACHING COMPUTATIONS SAFELY
79
arg-val
(closureV-env fun-val))))]
That leaves only the definition of strict. This is where we actually use the cache:
(define (strict e)
(type-case CFAE/L-Value e
[exprV (expr env cache)
(if (boolean? (unbox cache))
(local [(define the-value (strict (interp expr env)))]
(begin
(printf ”Forcing exprV ˜a to ˜a˜n” expr the-value)
(set-box! cache the-value)
the-value))
(begin
(printf ”Using cached value˜n”)
(unbox cache)))]
[else e]))
With these changes, we see that interpreting the running example needs to force an expression closure
fewer times (how many?). The other instances reuse the value of a prior reduction. Figure 8.3 and Figure 8.4
present the heart of the interpreter. Haskell uses the value cache we have just studied, so it combines the
benefit of laziness (not evaluating unnecessary arguments) with reasonable performance (evaluating the
necessary ones only once).
Exercise 8.2.1 An expression closure is extremely similar to a regular (function) closure. Indeed, if should
be possible to replace the former with the latter. When doing so, however, we don’t really need all the pieces
of function closures: there are no arguments, so only the body and environment matter. Such a closure is
called a thunk, a name borrowed from a reminiscent technique used in Algol 60. Implement laziness entirely
using thunks, getting rid of expression closures.
Exercise 8.2.2 We could have achieved the same effect as using thunks (see Exercise 8.2.1) by simply using
one-argument procedures with a dummy argument value. Why didn’t we propose this? Put otherwise, what
benefit do we derive by keeping expression closures as a different kind of value?
Exercise 8.2.3 Extend this language with recursion and list primitives so you can run the equivalent of the
programs we saw in Section 7.1. In this extended language, implement Fibonacci, run it with and without
value caching, and arrive at a conclusion about the time complexity of the two versions.
8.3
Caching Computations Safely
Any language that caches computation (whether in an eager or lazy regime) is making a very strong tacit
assumption: that an expression computes the same value every time it evaluates. If an expression can yield a
different value in a later evaluation, then the value in the cache is corrupt, and using it in place of the correct
value can cause the computation to go awry. So we must examine this evaluation decision of Haskell.
80
CHAPTER 8. IMPLEMENTING LAZINESS
This assumption cannot be applied to most programs written in traditional languages, because of the use
of side-effects. A method invocation in Java can, for instance, depend on the values of fields (directly, or
indirectly via method accesses) in numerous other objects, any one of which may later change, which will
almost certainly invalidate a cache of the method invocation’s computed value. To avoid having to track
this complex web of dependencies, languages like Java avoid caching values altogether in the general case
(though an optimizing compiler may introduce a cache under certain circumstances, when it can ensure the
cache’s consistency).
Haskell implementations can cache values because Haskell does not provide explicit mutation opera-
tions. Haskell instead forces programmers to perform all computations by composing functions. While this
may seem an onerous style to those unaccustomed to it, the resulting programs are in fact extremely elegant,
and Haskell provides a powerful collection of primitives to enable their construction; we caught a glimpse
of both the style and the primitives in Section 7.1. Furthermore, the lack of side-effects makes it possible for Haskell compilers to perform some very powerful optimizations not available to traditional language compilers, so what seems like an inefficient style on the surface (such as the creation of numerous intermediate
tuples, lists and other data structures) often has little run-time impact.
Of course, no useful Haskell program is an island; programs must eventually interact with the world,
which itself has true side-effects (at least in practice). Haskell therefore provides a set of “unsafe” operators
that conduct input-output and other operations. Computations that depend on the results of unsafe operations
cannot be cached. Haskell does, however, have a sophisticated type system (featuring quite a bit more,
in fact, than we saw in Section 7.1) that makes it possible to distinguish between the unsafe and “safe”
operations, thereby restoring the benefits of caching to at least portions of a program’s computation. In
practice, Haskell programmers exploit this by limiting unsafe computations to a small portion of a program,
leaving the remainder in the pure style espoused by the language.
The absence of side-effects benefits not only the compiler but, for related reasons, the programmer
also. It greatly simplifies reasoning about programs, because to understand what a particular function is
doing a programmer doesn’t need to be aware of the global flow of control of the program. In particular,
programmers can study a program through equational reasoning, using the process of reduction we have
studied in high-school algebra. The extent to which we can apply equational reasoning depends on the
number of expressions we can reasonably substitute with other, equivalent expressions (including answers).
We have argued that caching computation is safe in the absence of side-effects. But the eager version of
our interpreted language doesn’t have side-effects either! We didn’t need to cache computation in the same
way we have just studied, because by definition an eager language associates identifiers with values in the
environment, eliminating the possibility of re-computation on use. There is, however, a slightly different
notion of caching that applies in an eager language called memoization.
Of course, to use memoization safely, the programmer or implementation would have to establish that
the function’s body does not depend on side-effects—or invalidate the cache when a relevant effect happens.
Memoization is sometimes introduced automatically as a compiler optimization.
Exercise 8.3.1 There are no lazy languages that permit mutation. Why not? Is there a deeper reason beyond
the invaldation of several compiler optimizations?
Exercise 8.3.2 Why do you think there are no lazy languages without type systems?
Hint: This is related to Exercise 8.3.1.
8.3. CACHING COMPUTATIONS SAFELY
81
Referential Transparency
People sometimes refer to the lack of mutation as “referential transparency”, as in, “Haskell is
referentially transparent” (and, by implicit contrast, languages like Java, C++, Scheme and ML are
not). What do they really mean?
Referential transparency is commonly translated as the ability to “replace equals with equals”. For
example, we can always replace 1 + 2 with 3. Now think about that (very loose) definition for
a moment: when can you not replace something with something else that the original thing is
equal to? Never, of course—you always can. So by that definition, every language is “referentially
transparent”, and the term becomes meaningless.
Referential transparency really describes a relation: it relates pairs of terms exactly when they can
be considered equivalent in all contexts. Thus, in most languages, 1 + 2 is referentially transparent
√
to 3 (assuming no overflow), and
4 (written in the appropriate notation) is referentially transparent
to 2 (assuming the square root function returns only the positive root).
Given this understanding, we can now ask the following question: what is the size of the referential
transparency relation for a program in a given language? While even a language like C subscribes a
referential transparency relation, and some C programs have larger relations (because they minimize
side-effects), the size of this relation is inherently larger for programs written in a language without
mutation. This larger relation enables a much greater use of equational reasoning.
As a programmer, you should strive to make this relation as large as possible, no matter what lan-
guage you program in: this has a positive impact on long-term program maintenance (for instance,
when other programmers need to modify your code). As a student of programming languages,
however, please use this term with care; in particular, always remember that it describes a relation
between phrases in a program, and is rarely meaningful when applied to languages as a whole.
Memoization
Memoization associates a cache with each function. The cache tracks actual argument tuples and
their corresponding return values. When the program invokes a “memoized” function, the evaluator
first tries to find the function’s value in the cache, and only invokes the function proper if that
argument tuple hadn’t been cached before. If the function is recursive, the recursive calls might also
go through the memoized version. Memoization in this instance reduces the exponential number
of calls in computing Fibonacci numbers to a linear number, without altering the natural recursive
definition.
It’s important to note that what we have implemented for lazy languages is not memoization. While
we do cache the value of each expression closure, this is different from caching the value of all
expression closures that contain the same expression closed over the same environment. In our
implementation, if a program contains the same source expression (such as a function invocation)
twice, each use of that expression results in a separate evaluation.
82
CHAPTER 8. IMPLEMENTING LAZINESS
8.4
Scope and Evaluation Regimes
Students of programming languages often confuse the notions of scope (static versus dynamic) and evalua-
tion regimes (eager versus lazy). In particular, readers often engage in the following fallacious reasoning:
Because lazy evaluation substitutes expressions, not values, and because substituting expres-
sions (naively) results in variables getting their values from the point of use rather than the
point of definition, therefore lazy evaluation must result in dynamic scope.
It is very important to not be trapped by this line of thought. The scoping rules of a language are determined
a priori by the language designer. (For the reasons we have discussed in Section 6.5, this should almost
always be static scope.) It is up to the language implementor to faithfully enforce them. Likewise, the
language designer determines the reduction regime, perhaps based on some domain constraints. Again, the
implementor must determine how to correctly implement the chosen regime. We have seen how the use of
appropriate closure values can properly enforce static scope in both eager and lazy evaluation regimes.
8.4. SCOPE AND EVALUATION REGIMES
83
(define-type CFAE/L
[num (n number?)]
[add (lhs CFAE/L?) (rhs CFAE/L?)]
[id (name symbol?)]
[fun (param symbol?) (body CFAE/L?)]
[app (fun-expr CFAE/L?) (arg-expr CFAE/L?)])
(define-type CFAE/L-Value
[numV (n number?)]
[closureV (param symbol?)
(body CFAE/L?)
(env Env?)]
[exprV (expr CFAE/L?)
(env Env?)])
(define-type Env
[mtSub]
[aSub (name symbol?) (value CFAE/L-Value?) (env Env?)])
;; num+ : CFAE/L-Value CFAE/L-Value −→ numV
(define (num+ n1 n2)
(numV (+ (numV-n (strict n1)) (numV-n (strict n2)))))
;; num-zero? : CFAE/L-Value → boolean
(define (num-zero? n)
(zero? (numV-n (strict n))))
;; strict : CFAE/L-Value → CFAE/L-Value [excluding exprV]
(define (strict e)
(type-case CFAE/L-Value e
[exprV (expr env)
(local ([define the-value (strict (interp expr env))])
(begin
(printf ”Forcing exprV to ˜a˜n” the-value)
the-value))]
[else e]))
Figure 8.1: Implementation of Laziness: Support Code
84
CHAPTER 8. IMPLEMENTING LAZINESS
;; interp : CFAE/L Env → CFAE/L-Value
(define (interp expr env)
(type-case CFAE/L expr
[num (n) (numV n)]
[add (l r) (num+ (interp l env) (interp r env))]
[id (v) (lookup v env)]
[fun (bound-id bound-body)
(closureV bound-id bound-body env)]
[app (fun-expr arg-expr)
(local ([define fun-val (strict (interp fun-expr env))]
[define arg-val (exprV arg-expr env)])
(interp (closureV-body fun-val)
(aSub (closureV-param fun-val)
arg-val
(closureV-env fun-val))))]))
Figure 8.2: Implementation of Laziness: Interpreter
8.4. SCOPE AND EVALUATION REGIMES
85
(define-type CFAE/L-Value
[numV (n number?)]
[closureV (param symbol?)
(body CFAE/L?)
(env Env?)]
[exprV (expr CFAE/L?)
(env Env?)
(cache boxed-boolean/CFAE/L-Value?)])
(define (boxed-boolean/CFAE/L-Value? v)
(and (box? v)
(or (boolean? (unbox v))
(numV? (unbox v))
(closureV? (unbox v)))))
;; strict : CFAE/L-Value → CFAE/L-Value [excluding exprV]
(define (strict e)
(type-case CFAE/L-Value e
[exprV (expr env cache)
(if (boolean? (unbox cache))
(local [(define the-value (strict (interp expr env)))]
(begin
(printf ”Forcing exprV ˜a to ˜a˜n” expr the-value)
(set-box! cache the-value)
the-value))
(begin
(printf ”Using cached value˜n”)
(unbox cache)))]
[else e]))
Figure 8.3: Implementation of Laziness with Caching: Support Code
86
CHAPTER 8. IMPLEMENTING LAZINESS
;; interp : CFAE/L Env → CFAE/L-Value
(define (interp expr env)
(type-case CFAE/L expr
[num (n) (numV n)]
[add (l r) (num+ (interp l env) (interp r env))]
[id (v) (lookup v env)]
[fun (bound-id bound-body)
(closureV bound-id bound-body env)]
[app (fun-expr arg-expr)
(local ([define fun-val (strict (interp fun-expr env))]
[define arg-val (exprV arg-expr env (box false))])
(interp (closureV-body fun-val)
(aSub (closureV-param fun-val)
arg-val
(closureV-env fun-val))))]))
Figure 8.4: Implementation of Laziness with Caching: Interpreter
Part IV
Recursion
87
Chapter 9
Understanding Recursion
Can we write the factorial function in FAE? We currently don’t have subtraction or multiplication, or a way
of making choices in our FAE code. But those two are easy to address. At this point adding subtraction and
multiplication is trivial, while to make choices, we can add a simple conditional construct, leading to this
language:
<CFAE> ::= <num>
| {+ <CFAE> <CFAE>}
| {* <CFAE> <CFAE>}
| <id>
| {fun {<id>} <CFAE>}
| {<CFAE> <CFAE>}
| {if0 <CFAE> <CFAE> <CFAE>}
An if0 evaluates its first sub-expression. If this yields the value 0 it evaluates the second, otherwise it
evaluates the third. For example,
{if0 {+ 5 -5}
1
2}
evaluates to 1.
Given CFAE, we’re ready to write factorial (recall from Section 6.3 that with can be handled by a
pre-processor or by the parser):
{with {fac {fun {n}
{if0 n
1
{* n {fac {+ n -1}}}}}}
{fac 5}}
What does this evaluate to? 120? No. Consider the following simpler expression, which you were asked to
contemplate when we studied substitution:
89
90
CHAPTER 9. UNDERSTANDING RECURSION
{with {x x} x}
In this program, the x in the named expression position of the with has no binding. Similarly, the environ-
ment in the closure bound to fac binds no identifiers. Therefore, only the environment of the first invocation
(the body of the with) has a binding for fac. When fac is applied to 5, the interpreter evaluates the body
of fac in the closure environment, which has no bound identifiers, so interpretation stops on the intended
recursive call to fac with an unbound identifier error. (As an aside, notice that this problem disappears with
dynamic scope! This is why dynamic scope persisted for as long as it did.)
Before you continue reading, please pause for a moment, study the program carefully, write down the
environments at each stage, step by hand through the interpreter, even run the program if you wish, to
convince yourself that this error will occur. Understanding the error thoroughly will be essential to following
the remainder of theis section.
9.1
A Recursion Construct
It’s clear that the problem arises from the scope rules of with: it makes the new binding available only in its
body. In contrast, we need a construct that will make the new binding available to the named expression also.
Different intents, so different names: Rather than change with, let’s add a new construct to our language,
rec.
<RCFAE> ::= <num>
| {+ <RCFAE> <RCFAE>}
| {* <RCFAE> <RCFAE>}
| <id>
| {fun {<id>} <RCFAE>}
| {<RCFAE> <RCFAE>}
| {if0 <RCFAE> <RCFAE> <RCFAE>}
| {rec {<id> <RCFAE>} <RCFAE>}
RCFAE is CFAE extended with a construct for recursive binding. We can use rec to write a description of
factorial as follows:
{rec {fac {fun {n}
{if0 n
1
{* n {fac {+ n -1}}}}}}
{fac 5}}
Simply defining a new syntactic construct isn’t enough; we must also describe what it means. Indeed,
notice that syntactically, there is nothing but the keyword distinguishing with from rec. The interesting
work lies in the interpreter. But before we get there, we’ll first need to think hard about the semantics at a
more abstract level.
9.2. ENVIRONMENTS FOR RECURSION
91
9.2
Environments for Recursion
It’s clear from the analysis of our failed attempt at writing fac using with that the problem has something
to do with environments. Let’s try to make this intuition more precise.
One way to think about constructs such as with is as environment transformers. That is, they are
functions that consume an environment and transform it into one for each of their sub-expressions. We will
call the environment they consume—which is the one active outside the use of the construct—the ambient
environment.
There are two transformers associated with with: one for its named expression, and the other for its
body. Let’s write them both explicitly.
ρwith,named(e) = e
In other words, whatever the ambient environment for a with, that’s the environment used for the named
expression. In contrast,
ρwith,body(e) = (aSub bound-id
bound-value
e)
where bound-id and bound-value have to be replaced with the corresponding identifier name and value,
respectively.
Now let’s try to construct the intended transformers for rec in the factorial definition above. Since rec
has two sub-expressions, just like with, we will need to describe two transformers. The body seems easier
to tackle, so let’s try it first. At first blush, we might assume that the body transformer is the same as it was
for with, so:
ρrec,body(e) = (aSub ’fac
(closureV · · ·)
e)
Actually, we should be a bit more specific than that: we must specify the environment contained in the clo-
sure. Once again, if we had a with instead of a rec, the closure would close over the ambient environment:
ρrec,body(e) = (aSub ’fac
(closureV ’n
;; bound id
(if0 · · ·)
;; body
e)
e)
But this is no good! When the fac procedure is invoked, the interpreter is going to evaluate its body in the
environment bound to e, which doesn’t have a binding for fac. So this environment is only good for the
first invocation of fac; it leads to an error on subsequent invocations.
Let’s understand how this closure came to have that environment. The closure simply closes over what-
ever environment was active at the point of the procedure’s definition. Therefore, the real problem is making
sure we have the right environment for the named-expression portion of the rec. If we can do that, then
the procedure in that position would close over the right environment, and everything would be set up right
when we get to the body.
92
CHAPTER 9. UNDERSTANDING RECURSION
We must therefore shift our attention to the environment transformer for the named expression. If we
evaluate an invocation of fac in the ambient environment, it fails immediately because fac isn’t bound. If
we evaluate it in (aSub ’fac (closureV · · · e) e), we can perform one function application before we halt with
an error. What if we wanted to be able to perform two function calls (i.e., one to initiate the computation,
and one recursive call)? Then the following environment would suffice:
ρrec,named(e) =
(aSub ’fac
(closureV ’n
(if0 · · ·) ;; body
(aSub ’fac
(closureV ’n
(if0 · · ·) ;; body
e)
e))
e)
That is, when the body of fac begins to evaluate, it does so in the environment
(aSub ’fac
(closureV ’n
(if0 · · ·) ;; body
e)
e)
which contains the “seed” for one more invocation of fac. That second invocation, however, evaluates its
body in the environment bound to e, which has no bindings for fac, so any further invocations would halt
with an error.
Let’s try this one more time: the following environment will suffice for one initial and two recursive
invocations of fac:
ρrec,named(e) =
(aSub ’fac
(closureV ’n
(if0 · · ·)