Essentials of Programming Languages Exercises
Preface
Usage
Usage  X
Exercise 0.1 [★]
We often use phrases like “some languages have property X.” For each such phrase, find one or more languages that have the property and one or more languages that do not have the property. Feel free to ferret out this information from any descriptive book on programming languages (say Scott (2005), Sebesta (2007), or Pratt & Zelkowitz (2001)).
Skipped.
1 Inductive Sets of Data
1.1 Recursively Specified Data
1.1.1 Inductive Specification
Exercise 1.1 [★]
Write inductive definitions of the following sets. Write each definition in all three styles (topdown, bottomup, and rules of inference). Using your rules, show the derivation of some sample elements of each set.
 {3n + 2  n ∈ N}
 {2n + 3m + 1  n, m ∈ N}
 {(n, 2n + 1)  n ∈ N}
 {(n, n^{2})  n ∈ N} Do not mention squaring in your rules. As a hint, remember the equation (n + 1)^{2} = n^{2} + 2n + 1.

{3n + 2  n ∈ N}

Topdown:
n ∈ S if
 n = 2, or
 n − 3 ∈ S

Bottomup:
S is the smallest set that satisfying the following two properties:
 2 ∈ S, and
 If n ∈ S, then n + 3 ∈ S

Rules of inference:
 \(\dfrac{}{2 ∈ S}\)
 \(\dfrac{n ∈ S}{n + 3 ∈ S}\)


{2n + 3m + 1  n, m ∈ N}

Topdown:
n ∈ S if
 n = 1, or
 n − 2 ∈ S, or
 n − 3 ∈ S

Bottomup:
S is the smallest set that satisfying the following two properties:
 1 ∈ S, and
 If n ∈ S, then n + 2 ∈ S, and
 If n ∈ S, then n + 3 ∈ S

Rules of inference:
 \(\dfrac{}{1 ∈ S}\)
 \(\dfrac{n ∈ S}{n + 2 ∈ S}\)
 \(\dfrac{n ∈ S}{n + 3 ∈ S}\)


{(n, 2n + 1)  n ∈ N}

Topdown:
(m, n) ∈ S if
 m = 0 and n = 1, or
 (m − 1, n − 2) ∈ S

Bottomup:
S is the smallest set that satisfying the following two properties:
 (0, 1) ∈ S, and
 If (m, n) ∈ S, then (m + 1, n + 2) ∈ S

Rules of inference:
 \(\dfrac{}{(0, 1) ∈ S}\)
 \(\dfrac{(m, n) ∈ S}{(m + 1, n + 2) ∈ S}\)


{(n, n^{2})  n ∈ N}

Topdown:
(m, n) ∈ S if
 m = 0 and n = 0, or
 (m − 1, n − 2m + 1) ∈ S

Bottomup:
S is the smallest set that satisfying the following two properties:
 (0, 0) ∈ S, and
 If (m, n) ∈ S, then (m + 1, n + 2m + 1) ∈ S

Rules of inference:
 \(\dfrac{}{(0, 0) ∈ S}\)
 \(\dfrac{(m, n) ∈ S}{(m + 1, n + 2m + 1) ∈ S}\)

Exercise 1.2 [★★]
What sets are defined by the following pairs of rules? Explain why.
 \((0, 1) ∈ S \quad \dfrac{(n, k) ∈ S}{(n + 1, k + 7) ∈ S}\)
 \((0, 1) ∈ S \quad \dfrac{(n, k) ∈ S}{(n + 1, 2k) ∈ S}\)
 \((0, 0, 1) ∈ S \quad \dfrac{(n, i, j) ∈ S}{(n + 1, j, i + j) ∈ S}\)
 [★★★] \((0, 1, 0) ∈ S \quad \dfrac{(n, i, j) ∈ S}{(n + 1, i + 2, i + j) ∈ S}\)

\((0, 1) ∈ S \quad \dfrac{(n, k) ∈ S}{(n + 1, k + 7) ∈ S}\)
{(n, 7n + 1)  n ∈ N}

\((0, 1) ∈ S \quad \dfrac{(n, k) ∈ S}{(n + 1, 2k) ∈ S}\)
{(n, 2^{n})  n ∈ N}

\((0, 0, 1) ∈ S \quad \dfrac{(n, i, j) ∈ S}{(n + 1, j, i + j) ∈ S}\)
{(n, f(n), f(n + 1))  n ∈ N, f(0) = 0, f(1) = 1, f(n + 2) = f(n) + f(n + 1)}

\((0, 1, 0) ∈ S \quad \dfrac{(n, i, j) ∈ S}{(n + 1, i + 2, i + j) ∈ S}\)
{(n, 2n + 1, n^{2})  n ∈ N}
Exercise 1.3 [★★★]
Find a set T of natural numbers such that 0 ∈ T, and whenever n ∈ T, then n + 3 ∈ T, but T ≠ S, where S is the set defined in definition 1.1.2.
Let T = N.
1.1.2 Defining Sets Using Grammars
Exercise 1.4 [★]
Write a derivation from ListofInt to
(7 . (3 . (14 . ())))
.
ListofInt
⇒ (
Int .
ListofInt)
⇒ (7 .
ListofInt)
⇒ (7 . (
Int .
ListofInt))
⇒ (7 . (3 .
ListofInt))
⇒ (7 . (3 . (
Int .
ListofInt)))
⇒ (7 . (3 . (14 .
ListofInt)))
⇒ (7 . (3 . (14 . ())))
1.1.3 Induction
Exercise 1.5 [★★]
Prove that if e ∈ LcExp, then there are the same number of left and right parentheses in e.
By induction on the structure of LcExp.
If e is of Identifier form, it has 0 left parenthesis and 0 right parenthesis, the hypothesis holds.
If e is of (lambda (
Identifier)
LcExp)
form, the Identifier has 0 parenthesis. By induction, LcExp has
the same number of left and right parentheses. Let the number be n, then e has n + 2 left parentheses and n + 2
right parentheses. The hypothesis holds.
If e is of (
LcExp LcExp)
form, let m be the number of left or right parentheses in the first LcExp, let
n be the number of left or right parentheses in the second LcExp, then e has m + n + 1 left parentheses and
m + n + 1 right parentheses. The hypothesis holds.
1.2 Deriving Recursive Programs
1.2.2 nthelement
Exercise 1.6 [★]
If we reversed the order of the tests in
nthelement
, what would go wrong?
car
may be applied to empty list.
Exercise 1.7 [★★]
The error message from
nthelement
is uninformative. Rewritenthelement
so that it produces a more informative error message, such as “(a b c)
does not have 8 elements.”
(define reportlisttooshort
(lambda (lst n)
(eopl:error 'nthelement
"~s does not have ~s elements.~%" lst (+ n 1))))
(define nthelementhelper
(lambda (lst n currentlist i)
(if (null? currentlist)
(reportlisttooshort lst n)
(if (zero? i)
(car currentlist)
(nthelementhelper lst n (cdr currentlist) ( i 1))))))
(define nthelement
(lambda (lst n)
(nthelementhelper lst n lst n)))
1.2.3 removefirst
Exercise 1.8 [★]
In the definition of removefirst, if the last line were replaced by
(removefirst s (cdr los))
, what function would the resulting procedure compute? Give the contract, including the usage statement, for the revised procedure.
removefirst : Sym × Listof(Sym) → Listof(Sym)
usage: (removefirst
s los)
returns a sub of list from los, starting from the symbol after the first
s. If los doesn’t contain s, an empty list is returned.
(define removefirst
(lambda (s los)
(if (null? los)
'()
(if (eqv? (car los) s)
(cdr los)
(removefirst s (cdr los))))))
Exercise 1.9 [★★]
Define
remove
, which is likeremovefirst
, except that it removes all occurrences of a given symbol from a list of symbols, not just the first.
(define remove
(lambda (s los)
(if (null? los)
'()
(if (eqv? (car los) s)
(remove s (cdr los))
(cons (car los) (remove s (cdr los)))))))
1.2.4 occursfree?
Exercise 1.10 [★]
We typically use “or” to mean “inclusive or”. What other meanings can “or” have?
Exclusive or.
1.2.5 subst
Exercise 1.11 [★]
In the last line of
substinsexp
, the recursion is on sexp and not a smaller substructure. Why is the recursion guaranteed to halt?
Because subst
recurs on smaller substructure. We can replace the call to substinsexp
with the body of
substinsexp
, then subst
becomes a normal recursive on a smaller substructure.
Exercise 1.12 [★]
Eliminate the one call to
substinsexp
insubst
by replacing it by its definition and simplifying the resulting procedure. The result will be a version ofsubst
that does not needsubstinsexp
. This technique is called inlining, and is used by optimizing compilers.
(define subst
(lambda (new old slist)
(if (null? slist)
'()
(cons (let ([sexp (car slist)])
(if (symbol? sexp)
(if (eqv? sexp old) new sexp)
(subst new old sexp)))
(subst new old (cdr slist))))))
Exercise 1.13 [★★]
In our example, we began by eliminating the Kleene star in the grammar for Slist. Write
subst
following the original grammar by usingmap
.
(define substinsexp
(lambda (new old sexp)
(if (symbol? sexp)
(if (eqv? sexp old) new sexp)
(subst new old sexp))))
(define subst
(lambda (new old slist)
(map (lambda (sexp) (substinsexp new old sexp))
slist)))
1.3 Auxiliary Procedures and Context Arguments
1.3.0
Exercise 1.14 [★★]
Given the assumption 0 ≤ n < length(v), prove that
partialvectorsum
is correct.
Since 0 ≤ n < length(v), we know that length(v) is at least 1, so that v contains at least one element. We
prove partialvectorsum
is correct by induction over n.
Base case: if n equals to 0, (partialvectorsum
v n)
equals to (vectorref
v 0)
, which equals to
\(\sum_{i = 0}^0 v_i\), the claim holds.
Inductive case: if n ≠ 0, n (partialvectorsum
v n)
equals to
(add (vectorref
v n) (partialvectorsum
v (
n 1)))
, which equals to
\(v_n + \sum_{i = 0}^{n  1} v_i\), which equals to \(\sum_{i = 0}^n v_i\), the claim holds.
1.4 Exercises
1.4.0
Exercise 1.15 [★]
(duple n x)
returns a list containingn
copies ofx
.> (duple 2 3) (3 3) > (duple 4 '(ha ha)) ((ha ha) (ha ha) (ha ha) (ha ha)) > (duple 0 '(blah)) ()
(define duplehelper
(lambda (lst n x)
(if (zero? n)
lst
(duplehelper (cons x lst) ( n 1) x))))
(define duple
(lambda (n x)
(duplehelper '() n x)))
Exercise 1.16 [★]
(invert lst)
, where lst is a list of 2lists (lists of length two), returns a list with each 2list reversed.> (invert '((a 1) (a 2) (1 b) (2 b))) ((1 a) (2 a) (b 1) (b 2))
(define invert
(lambda (lst)
(map (lambda (x) (list (cadr x) (car x)))
lst)))
Exercise 1.17 [★]
(down lst)
wraps parentheses around each toplevel element oflst
.> (down '(1 2 3)) ((1) (2) (3)) > (down '((a) (fine) (idea))) (((a)) ((fine)) ((idea))) > (down '(a (more (complicated)) object)) ((a) ((more (complicated))) (object))
(define down
(lambda (lst)
(map (lambda (x) (list x))
lst)))
Exercise 1.18 [★]
(swapper s1 s2 slist)
returns a list the same as slist, but with all occurrences ofs1
replaced bys2
and all occurrences ofs2
replaced bys1
.> (swapper 'a 'd '(a b c d)) (d b c a) > (swapper 'a 'd '(a d () c d)) (d a () c a) > (swapper 'x 'y '((x) y (z (x)))) ((y) x (z (y)))
(define swapper
(lambda (s1 s2 slist)
(map (lambda (sexp)
(if (symbol? sexp)
(if (eqv? sexp s1)
s2
(if (eqv? sexp s2)
s1
sexp))
(swapper s1 s2 sexp)))
slist)))
Exercise 1.19 [★]
(listset lst n x)
returns a list likelst
, except that then
th element, using zerobased indexing, isx
.> (listset '(a b c d) 2 '(1 2)) (a b (1 2) d) > (listref (listset '(a b c d) 3 '(1 5 10)) 3) (1 5 10)
(define listset
(lambda (lst n x)
(if (zero? n)
(cons x (cdr lst))
(cons (car lst) (listset (cdr lst) ( n 1) x)))))
Exercise 1.20 [★]
(countoccurrences s slist)
returns the number of occurrences ofs
inslist
.> (countoccurrences 'x '((f x) y (((x z) x)))) 3 > (countoccurrences 'x '((f x) y (((x z) () x)))) 3 > (countoccurrences 'w '((f x) y (((x z) x)))) 0
(define countoccurrencessexp
(lambda (s sexp)
(if (symbol? sexp)
(if (eqv? sexp s) 1 0)
(countoccurrences s sexp))))
(define countoccurrences
(lambda (s slist)
(if (null? slist)
0
(+ (countoccurrencessexp s (car slist))
(countoccurrences s (cdr slist))))))
Exercise 1.21 [★★]
(product sos1 sos2)
, wheresos1
andsos2
are each a list of symbols without repetitions, returns a list of 2lists that represents the Cartesian product ofsos1
andsos2
. The 2lists may appear in any order.> (product '(a b c) '(x y)) ((a x) (a y) (b x) (b y) (c x) (c y))
(define productsymbol
(lambda (tail s sos)
(if (null? sos)
tail
(productsymbol (cons (list s (car sos)) tail) s (cdr sos)))))
(define producthelper
(lambda (tail sos1 sos2)
(if (null? sos1)
tail
(producthelper (productsymbol tail (car sos1) sos2)
(cdr sos1)
sos2))))
(define product
(lambda (sos1 sos2)
(producthelper '() sos1 sos2)))
Exercise 1.22 [★★]
(filterin pred lst)
returns the list of those elements inlst
that satisfy the predicatepred
.> (filterin number? '(a 2 (1 3) b 7)) (2 7) > (filterin symbol? '(a (b c) 17 foo)) (a foo)
(define filterin
(lambda (pred lst)
(if (null? lst)
'()
(let ([element (car lst)]
[tail (filterin pred (cdr lst))])
(if (pred element)
(cons element tail)
tail)))))
Exercise 1.23 [★★]
(listindex pred lst)
returns the 0based position of the first element oflst
that satisfies the predicatepred
. If no element oflst
satisfies the predicate, thenlistindex
returns#f
.> (listindex number? '(a 2 (1 3) b 7)) 1 > (listindex symbol? '(a (b c) 17 foo)) 0 > (listindex symbol? '(1 2 (a b) 3)) #f
(define listindexhelper
(lambda (n pred lst)
(if (null? lst)
#f
(if (pred (car lst))
n
(listindexhelper (+ n 1) pred (cdr lst))))))
(define listindex
(lambda (pred lst)
(listindexhelper 0 pred lst)))
Exercise 1.24 [★★]
(every? pred lst)
returns#f
if any element oflst
fails to satisfypred
, and returns#t
otherwise.> (every? number? '(a b c 3 e)) #f > (every? number? '(1 2 3 5 4)) #t
(define every?
(lambda (pred lst)
(if (null? lst)
#t
(and (pred (car lst))
(every? pred (cdr lst))))))
Exercise 1.25 [★★]
(exists? pred lst)
returns#t
if any element oflst
satisfiespred
, and returns#f
otherwise.> (exists? number? '(a b c 3 e)) #t > (exists? number? '(a b c d e)) #f
(define exists?
(lambda (pred lst)
(if (null? lst)
#f
(or (pred (car lst))
(exists? pred (cdr lst))))))
Exercise 1.26 [★★]
(up lst)
removes a pair of parentheses from each toplevel element oflst
. If a toplevel element is not a list, it is included in the result, as is. The value of(up (down lst))
is equivalent to lst, but(down (up lst))
is not necessarilylst
. (See exercise 1.17.)> (up '((1 2) (3 4))) (1 2 3 4) > (up '((x (y)) z)) (x (y) z)
(define extendhead
(lambda (tail head)
(if (null? head)
tail
(cons (car head) (extendhead tail (cdr head))))))
(define upelement
(lambda (tail element)
(if (list? element)
(extendhead tail element)
(cons element tail))))
(define up
(lambda (lst)
(if (null? lst)
'()
(upelement (up (cdr lst)) (car lst)))))
Exercise 1.27 [★★]
(flatten slist)
returns a list of the symbols contained inslist
in the order in which they occur whenslist
is printed. Intuitively,flatten
removes all the inner parentheses from its argument.> (flatten '(a b c)) (a b c) > (flatten '((a) () (b ()) () (c))) (a b c) > (flatten '((a b) c (((d)) e))) (a b c d e) > (flatten '(a b (() (c)))) (a b c)
(define flattenelement
(lambda (tail element)
(if (list? element)
(flattenhelper tail element)
(cons element tail))))
(define flattenhelper
(lambda (tail slist)
(if (null? slist)
tail
(flattenelement (flattenhelper tail (cdr slist))
(car slist)))))
(define flatten
(lambda (slist)
(flattenhelper '() slist)))
Exercise 1.28 [★★]
(merge loi1 loi2)
, whereloi1
andloi2
are lists of integers that are sorted in ascending order, returns a sorted list of all the integers inloi1
andloi2
.> (merge '(1 4) '(1 2 8)) (1 1 2 4 8) > (merge '(35 62 81 90 91) '(3 83 85 90)) (3 35 62 81 83 85 90 90 91)
(define mergehelper
(lambda (loi1 loi2)
(if (null? loi1)
loi2
(let ([i1 (car loi1)]
[i2 (car loi2)])
(if (< i1 i2)
(cons i1 (mergehelper (cdr loi1) loi2))
(cons i2 (mergehelper (cdr loi2) loi1)))))))
(define merge
(lambda (loi1 loi2)
(if (null? loi1)
loi2
(mergehelper loi2 loi1))))
Exercise 1.29 [★★]
(sort loi)
returns a list of the elements ofloi
in ascending order.> (sort '(8 2 5 2 3)) (2 2 3 5 8)
(define getrun
(lambda (loi)
(let ([head1 (car loi)]
[tail1 (cdr loi)])
(if (null? tail1)
(cons loi '())
(let ([head2 (car tail1)])
(if (<= head1 head2)
(let ([tailrun (getrun tail1)])
(cons (cons head1 (car tailrun)) (cdr tailrun)))
(cons (list head1) tail1)))))))
(define merge
(lambda (run1 run2)
(let ([head1 (car run1)]
[head2 (car run2)])
(if (<= head1 head2)
(let ([tail1 (cdr run1)])
(if (null? tail1)
(cons head1 run2)
(cons head1 (merge tail1 run2))))
(let ([tail2 (cdr run2)])
(if (null? tail2)
(cons head2 run1)
(cons head2 (merge run1 tail2))))))))
(define collapseall
(lambda (stack run)
(if (null? stack)
run
(collapseall (cdr stack) (merge (cdar stack) run)))))
(define collapse
(lambda (stack level run)
(if (null? stack)
(list (cons level run))
(let ([top (car stack)])
(if (= (car top) level)
(collapse (cdr stack) (+ level 1) (merge (cdr top) run))
(cons (cons level run) stack))))))
(define sorthelper
(lambda (stack loi)
(let* ([runandtail (getrun loi)]
[run (car runandtail)]
[tail (cdr runandtail)])
(if (null? tail)
(collapseall stack run)
(sorthelper (collapse stack 0 run) tail)))))
(define sort
(lambda (loi)
(if (null? loi)
'()
(sorthelper '() loi))))
Exercise 1.30 [★★]
(sort/predicate pred loi)
returns a list of elements sorted by the predicate.> (sort/predicate < '(8 2 5 2 3)) (2 2 3 5 8) > (sort/predicate > '(8 2 5 2 3)) (8 5 3 2 2)
(define getrun
(lambda (pred loi)
(let ([head1 (car loi)]
[tail1 (cdr loi)])
(if (null? tail1)
(cons loi '())
(let ([head2 (car tail1)])
(if (pred head2 head1)
(cons (list head1) tail1)
(let ([tailrun (getrun pred tail1)])
(cons (cons head1 (car tailrun)) (cdr tailrun)))))))))
(define merge
(lambda (pred run1 run2)
(let ([head1 (car run1)]
[head2 (car run2)])
(if (pred head2 head1)
(let ([tail2 (cdr run2)])
(if (null? tail2)
(cons head2 run1)
(cons head2 (merge pred run1 tail2))))
(let ([tail1 (cdr run1)])
(if (null? tail1)
(cons head1 run2)
(cons head1 (merge pred tail1 run2))))))))
(define collapseall
(lambda (pred stack run)
(if (null? stack)
run
(collapseall pred (cdr stack) (merge pred (cdar stack) run)))))
(define collapse
(lambda (pred stack level run)
(if (null? stack)
(list (cons level run))
(let ([top (car stack)])
(if (= (car top) level)
(collapse pred (cdr stack) (+ level 1) (merge pred (cdr top) run))
(cons (cons level run) stack))))))
(define sorthelper
(lambda (pred stack loi)
(let* ([runandtail (getrun pred loi)]
[run (car runandtail)]
[tail (cdr runandtail)])
(if (null? tail)
(collapseall pred stack run)
(sorthelper pred (collapse pred stack 0 run) tail)))))
(define sort/predicate
(lambda (pred loi)
(if (null? loi)
'()
(sorthelper pred '() loi))))
Exercise 1.31 [★]
Write the following procedures for calculating on a bintree (definition 1.1.7):
leaf
andinteriornode
, which build bintrees,leaf?
, which tests whether a bintree is a leaf, andlson
,rson
, andcontentsof
, which extract the components of a node.contentsof
should work on both leaves and interior nodes.
(define leaf
(lambda (num)
num))
(define interiornode
(lambda (symbol leftchild rightchild)
(cons symbol (cons leftchild rightchild))))
(define leaf? integer?)
(define lson cadr)
(define rson cddr)
(define contentsof
(lambda (bintree)
(if (leaf? bintree)
bintree
(car bintree))))
Exercise 1.32 [★]
Write a procedure
doubletree
that takes a bintree, as represented in definition 1.1.7, and produces another bintree like the original, but with all the integers in the leaves doubled.
(define doubletree
(lambda (bintree)
(if (leaf? bintree)
(leaf (* (contentsof bintree) 2))
(interiornode (contentsof bintree)
(doubletree (lson bintree))
(doubletree (rson bintree))))))
Exercise 1.33 [★★]
Write a procedure
markleaveswithreddepth
that takes a bintree (definition 1.1.7), and produces a bintree of the same shape as the original, except that in the new tree, each leaf contains the number of nodes between it and the root that contain the symbolred
. For example, the expression(markleaveswithreddepth (interiornode 'red (interiornode 'bar (leaf 26) (leaf 12)) (interiornode 'red (leaf 11) (interiornode 'quux (leaf 117) (leaf 14)))))
which is written using the procedures defined in exercise 1.31, should return the bintree
(red (bar 1 1) (red 2 (quux 2 2)))
(define markleaveswithreddepthhelper
(lambda (bintree rednum)
(if (leaf? bintree)
(leaf rednum)
(let* ([content (contentsof bintree)]
[newrednum (if (eqv? content 'red) (+ rednum 1) rednum)])
(interiornode content
(markleaveswithreddepthhelper (lson bintree) newrednum)
(markleaveswithreddepthhelper (rson bintree) newrednum))))))
(define markleaveswithreddepth
(lambda (bintree)
(markleaveswithreddepthhelper bintree 0)))
Exercise 1.34 [★★★]
Write a procedure
path
that takes an integern
and a binary search treebst
(page 10) that contains the integern
, and returns a list ofleft
s andright
s showing how to find the node containingn
. Ifn
is found at the root, it returns the empty list.> (path 17 '(14 (7 () (12 () ())) (26 (20 (17 () ()) ()) (31 () ())))) (right left left)
(define path
(lambda (n bst)
(let ([head (car bst)])
(if (< n head)
(cons 'left (path n (cadr bst)))
(if (= n head)
'()
(cons 'right (path n (caddr bst))))))))
Exercise 1.35 [★★★]
Write a procedure
numberleaves
that takes a bintree, and produces a bintree like the original, except the contents of the leaves are numbered starting from 0. For example,(numberleaves (interiornode 'foo (interiornode 'bar (leaf 26) (leaf 12)) (interiornode 'baz (leaf 11) (interiornode 'quux (leaf 117) (leaf 14)))))
should return
(foo (bar 0 1) (baz 2 (quux 3 4)))
(define numberleaveshelper
(lambda (bintree n)
(if (leaf? bintree)
(cons (leaf n) (+ n 1))
(let* ([leftresult (numberleaveshelper (lson bintree) n)]
[rightresult (numberleaveshelper (rson bintree) (cdr leftresult))])
(cons (interiornode (contentsof bintree)
(car leftresult)
(car rightresult))
(cdr rightresult))))))
(define numberleaves
(lambda (bintree)
(car (numberleaveshelper bintree 0))))
Exercise 1.36 [★★★]
Write a procedure
g
such thatnumberelements
from page 23 could be defined as(define numberelements (lambda (lst) (if (null? lst) '() (g (list 0 (car lst)) (numberelements (cdr lst))))))
(define g
(lambda (head tail)
(cons head
(map (lambda (item)
(list (+ (car item) 1) (cadr item)))
tail))))
2 Data Abstraction
2.1 Specifying Data via Interfaces
2.1.0
Exercise 2.1 [★]
Implement the four required operations for bigits. Then use your implementation to calculate the factorial of 10. How does the execution time vary as this argument changes? How does the execution time vary as the base changes? Explain why.
(define *base* 10)
(define *basesub1* ( *base* 1))
(define zero
(lambda ()
'()))
(define iszero? null?)
(define successor
(lambda (n)
(if (null? n)
'(1)
(let ([lowestdigit (car n)])
(if (= lowestdigit *basesub1*)
(cons 0 (successor (cdr n)))
(cons (+ lowestdigit 1) (cdr n)))))))
(define predecessor
(lambda (n)
(let ([lowestdigit (car n)]
[restdigits (cdr n)])
(if (= lowestdigit 0)
(cons *basesub1* (predecessor restdigits))
(if (and (= lowestdigit 1) (null? restdigits))
'()
(cons ( lowestdigit 1) (cdr n)))))))
(define plus
(lambda (m n)
(if (iszero? n)
m
(plus (successor m) (predecessor n)))))
(define multiplyhelper
(lambda (base m n)
(if (iszero? n)
base
(multiplyhelper (plus base m) m (predecessor n)))))
(define multiply
(lambda (m n)
(multiplyhelper (zero) m n)))
(define factorialhelper
(lambda (base n)
(if (iszero? n)
base
(factorialhelper (multiply base n) (predecessor n)))))
(define factorial
(lambda (n)
(factorialhelper (successor (zero)) n)))
When the argument of factorial
becomes larger, the execution time becomes longer. Obviously.
The execution time becomes shorter when the base becomes larger. I think that’s because fewer allocations are needed when the base becomes larger.
Exercise 2.2 [★★]
Analyze each of these proposed representations critically. To what extent do they succeed or fail in satisfying the specification of the data type?
 Unary representation. Too much space consumed.
 Scheme number representation. Not every language has native big integer support.
 Bignum representation. Not easy to implement.
Exercise 2.3 [★★]
Define a representation of all the integers (negative and nonnegative) as difftrees, where a difftree is a list defined by the grammar
Difftree ::=
(one)
(diff
Difftree Difftree)
The list
(one)
represents 1. If t_{1} represents n_{1} and t_{2} represents n_{2}, then(diff t1 t2)
is a representation of n_{1} − n_{2}.So both
(one)
and(diff (one) (diff (one) (one)))
are representations of 1;(diff (diff (one) (one)) (one))
is a representation of 1.
 Show that every number has infinitely many representations in this system.
 Turn this representation of the integers into an implementation by writing
zero
,iszero?
,successor
, andpredecessor
, as specified on page 32, except that now the negative integers are also represented. Your procedures should take as input any of the multiple legal representations of an integer in this scheme. For example, if yoursuccessor
procedure is given any of the infinitely many legal representations of 1, it should produce one of the legal representations of 2. It is permissible for different legal representations of 1 to yield different legal representations of 2. Write a procedure
difftreeplus
that does addition in this representation. Your procedure should be optimized for the difftree representation, and should do its work in a constant amount of time (independent of the size of its inputs). In particular, it should not be recursive.
 0 has infinitely many representations:
(diff (one) (one))
,(diff (diff (one) (one)) (diff (one) (one)))
, and so on. n can be represented as(diff
n 0)
, since 0 has infinitely many representations, n has infinitely many representations. 
(define zero (lambda () '(diff (one) (one)))) (define interpret (lambda (n) (if (eqv? (car n) 'one) 1 ( (interpret (cadr n)) (interpret (caddr n)))))) (define iszero? (lambda (n) (zero? (interpret n)))) (define successor (lambda (n) (list 'diff n '(diff (diff (one) (one)) (one))))) (define predecessor (lambda (n) (list 'diff n '(one))))

(define difftreeplus (lambda (m n) (list 'diff m (list 'diff '(diff (one) (one)) n))))
2.2 Representation Strategies for Data Types
2.2.1 The Environment Interface
Exercise 2.4 [★★]
Consider the data type of stacks of values, with an interface consisting of the procedures
emptystack
,push
,pop
,top
, andemptystack?
. Write a specification for these operations in the style of the example above. Which operations are constructors and which are observers?
(emptystack)
= ⌈∅⌉(push
⌈f⌉ v)
= ⌈g⌉, where g(0) = v, and g(n + 1) = f(n)(pop
⌈f⌉)
= g, where g(n) = f(n + 1)(top
⌈f⌉)
= ⌈f(0)⌉(emptystack?
⌈f⌉)
=#t
if f = ∅,#f
otherwise
Constructors: emptystack
, push
and pop
.
Observers: top
and emptystack?
.
2.2.2 Data Structure Representation
Exercise 2.5 [★]
We can use any data structure for representing environments, if we can distinguish empty environments from nonempty ones, and in which one can extract the pieces of a nonempty environment. Implement environments using a representation in which the empty environment is represented as the empty list, and in which
extendenv
builds an environment that looks like┌───┬───┐ │ ╷ │ ╶─┼─► savedenv └─┼─┴───┘ ▼ ┌───┬───┐ │ ╷ │ ╷ │ └─┼─┴─┼─┘ ┌───┘ └───┐ ▼ ▼ savedvar savedval
This is called an alist or associationlist representation.
(define emptyenv
(lambda ()
'()))
(define applyenv
(lambda (env searchvar)
(let ([head (car env)])
(if (eqv? (car head) searchvar)
(cdr head)
(applyenv (cdr env) searchvar)))))
(define extendenv
(lambda (var val env)
(cons (cons var val) env)))
Exercise 2.6 [★]
Invent at least three different representations of the environment interface and implement them.
Deferred.
Exercise 2.7 [★]
Rewrite
applyenv
in figure 2.1 to give a more informative error message.
(define emptyenv
(lambda ()
'(emptyenv)))
(define extendenv
(lambda (var val env)
(list 'extendenv var val env)))
(define applyenv
(lambda (env searchvar)
(let loop ([env1 env])
(cond
[(eqv? (car env1) 'emptyenv) (reportnobindingfound searchvar env)]
[(eqv? (car env1) 'extendenv) (let ([savedvar (cadr env1)]
[savedval (caddr env1)]
[savedenv (cadddr env1)])
(if (eqv? searchvar savedvar)
savedval
(loop savedenv)))]
[else (reportinvalidenv env1)]))))
(define collectbindings
(lambda (env)
(let loop ([base '()]
[env env])
(let ([tag (car env)])
(cond [(eqv? tag 'emptyenv) base]
[(eqv? tag 'extendenv) (let ([savedvar (cadr env)]
[savedval (caddr env)]
[savedenv (cadddr env)])
(loop (if (assv savedvar base)
base
(cons (cons savedvar savedval) base))
savedenv))])))))
(define reportnobindingfound
(lambda (searchvar env)
(eopl:error 'applyenv "No binding for ~s. All bindings: ~s" searchvar (collectbindings env))))
(define reportinvalidenv
(lambda (env)
(eopl:error 'applyenv "Bad environment: ~s" env)))
Exercise 2.8 [★]
Add to the environment interface an observer called
emptyenv?
and implement it using the alist representation.
(emptyenv?
⌈f⌉)
= #t
if f = ∅, #f
otherwise.
(define emptyenv? null?)
Exercise 2.9 [★]
Add to the environment interface an observer called
hasbinding?
that takes an environment env and a variable s and tests to see if s has an associated value in env. Implement it using the alist representation.
(hasbinding?
⌈f⌉)
= #t
if f(var) = val for some var and val, #f
otherwise.
(define hasbinding?
(lambda (env searchvar)
(cond [(null? env) #f]
[(eqv? (caar env) searchvar) #t]
[else (hasbinding? (cdr env) searchvar)])))
Exercise 2.10 [★]
Add to the environment interface a constructor
extendenv*
, and implement it using the alist representation. This constructor takes a list of variables, a list of values of the same length, and an environment, and is specified by
(extendenv* (
var_{1} … var_{k}) (
val_{1} … val_{k})
⌈f⌉)
= ⌈g⌉, where g(var) = val_{i} if var = var_{i} for some i such that 1 ≤ i ≤ k, f(var) otherwise.
(define extendenv*
(lambda (vars vals env)
(if (null? vars)
env
(extendenv* (cdr vars)
(cdr vals)
(cons (cons (car vars) (car vals)) env)))))
Exercise 2.11 [★★]
A naïve implementation of
extendenv*
from the preceding exercise requires time proportional to k to run. It is possible to represent environments so thatextendenv*
requires only constant time: represent the empty environment by the empty list, and represent a nonempty environment by the data structure┌───┬───┐ │ ╷ │ ╶─┼─► savedenv └─┼─┴───┘ ▼ ┌───┬───┐ │ ╷ │ ╷ │ └─┼─┴─┼─┘ ┌───┘ └───┐ ▼ ▼ savedvars savedvals
Such an environment might look like
backbone │ ┌───┬───┐ ▼ ┌───┬───┐ ┌───┬───┐ │ ╷ │ ╶─┼──────────►│ ╷ │ ╶─┼──────────►│ ╷ │ ╶─┼──────────► rest of environment └─┼─┴───┘ └─┼─┴───┘ └─┼─┴───┘ ▼ ▼ ▼ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ │ ╷ │ ╷ │ │ ╷ │ ╷ │ │ ╷ │ ╷ │ └─┼─┴─┼─┘ └─┼─┴─┼─┘ └─┼─┴─┼─┘ ┌──┘ └──┐ ┌──┘ └──┐ ┌──┘ └──┐ ▼ ▼ ▼ ▼ ▼ ▼ (a b c) (11 12 13) (x z) (66 77) (x y) (88 99)
This is called the ribcage representation. The environment is represented as a list of pairs called ribs; each left rib is a list of variables and each right rib is the corresponding list of values.
Implement the environment interface, including
extendenv*
, in this representation.
(define emptyenv
(lambda ()
'()))
(define applyenv
(lambda (env searchvar)
(let loop ([env env])
(let ([rib (car env)])
(let applyrib ([vars (car rib)]
[vals (cdr rib)])
(cond [(null? vars) (loop (cdr env))]
[(eqv? (car vars) searchvar) (car vals)]
[else (applyrib (cdr vars) (cdr vals))]))))))
(define extendenv*
(lambda (vars vals env)
(cons (cons vars vals) env)))
(define extendenv
(lambda (var val env)
(extendenv* (list var) (list val) env)))
2.2.3 Procedural Representation
Exercise 2.12 [★]
Implement the stack data type of exercise 2.4 using a procedural representation.
(define emptystack
(lambda ()
(lambda (command)
(cond [(eqv? command 'empty?) #t]))))
(define push
(lambda (stack val)
(lambda (command)
(cond [(eqv? command 'empty?) #f]
[(eqv? command 'pop) stack]
[(eqv? command 'top) val]))))
(define pop
(lambda (stack)
(stack 'pop)))
(define top
(lambda (stack)
(stack 'top)))
(define emptystack?
(lambda (stack)
(stack 'empty?)))
Exercise 2.13 [★★]
Extend the procedural representation to implement
emptyenv?
by representing the environment by a list of two procedures: one that returns the value associated with a variable, as before, and one that returns whether or not the environment is empty.
(define reportnobindingfound
(lambda (searchvar)
(eopl:error 'applyenv "No binding for ~s" searchvar)))
(define emptyenv
(lambda ()
(list (lambda (searchvar)
(reportnobindingfound searchvar))
(lambda ()
#t))))
(define emptyenv?
(lambda (env)
((cadr env))))
(define extendenv
(lambda (savedvar savedval savedenv)
(list (lambda (searchvar)
(if (eqv? searchvar savedvar)
savedval
(applyenv savedenv searchvar)))
(lambda ()
#f))))
(define applyenv
(lambda (env searchvar)
((car env) searchvar)))
Exercise 2.14 [★★]
Extend the representation of the preceding exercise to include a third procedure that implements
hasbinding?
(see exercise 2.9).
(define reportnobindingfound
(lambda (searchvar)
(eopl:error 'applyenv "No binding for ~s" searchvar)))
(define emptyenv
(lambda ()
(list (lambda (searchvar)
(reportnobindingfound searchvar))
(lambda ()
#t)
(lambda (searchvar)
#f))))
(define emptyenv?
(lambda (env)
((cadr env))))
(define extendenv
(lambda (savedvar savedval savedenv)
(list (lambda (searchvar)
(if (eqv? searchvar savedvar)
savedval
(applyenv savedenv searchvar)))
(lambda ()
#f)
(lambda (searchvar)
(or (eqv? savedvar searchvar)
(hasbinding? savedenv searchvar))))))
(define applyenv
(lambda (env searchvar)
((car env) searchvar)))
(define hasbinding?
(lambda (env searchvar)
((caddr env) searchvar)))
2.3 Interfaces for Recursive Data Types
2.3.0
Exercise 2.15 [★]
Implement the lambdacalculus expression interface for the representation specified by the grammar above.
(define varexp
(lambda (var)
var))
(define lambdaexp
(lambda (boundvar body)
`(lambda (,boundvar)
,body)))
(define appexp
(lambda (operator operand)
`(,operator ,operand)))
(define varexp? symbol?)
(define lambdaexp?
(lambda (exp)
(and (pair? exp)
(eqv? (car exp) 'lambda))))
(define appexp?
(lambda (exp)
(and (pair? exp)
(not (eqv? (car exp) 'lambda)))))
(define varexp>var
(lambda (exp)
exp))
(define lambdaexp>boundvar caadr)
(define lambdaexp>body caddr)
(define appexp>rator car)
(define appexp>rand cadr)
Exercise 2.16 [★]
Modify the implementation to use a representation in which there are no parentheses around the bound variable in a
lambda
expression.
(define lambdaexp
(lambda (boundvar body)
`(lambda ,boundvar ,body)))
(define lambdaexp>boundvar cadr)
Remaining implementations are the same as the ones in exercise 2.15.
Exercise 2.17 [★]
Invent at least two other representations of the data type of lambdacalculus expressions and implement them.
Skipped.
Exercise 2.18 [★]
We usually represent a sequence of values as a list. In this representation, it is easy to move from one element in a sequence to the next, but it is hard to move from one element to the preceding one without the help of context arguments. Implement nonempty bidirectional sequences of integers, as suggested by the grammar
NodeInSequence ::=
(
Int Listof(
Int)
Listof(
Int))
The first list of numbers is the elements of the sequence preceding the current one, in reverse order, and the second list is the elements of the sequence after the current one. For example,
(6 (5 4 3 2 1) (7 8 9))
represents the list(1 2 3 4 5 6 7 8 9)
, with the focus on the element 6.In this representation, implement the procedure
number>sequence
, which takes a number and produces a sequence consisting of exactly that number. Also implementcurrentelement
,movetoleft
,movetoright
,inserttoleft
,inserttoright
,atleftend?
, andatrightend?
.For example:
> (number>sequence 7) (7 () ()) > (currentelement '(6 (5 4 3 2 1) (7 8 9))) 6 > (movetoleft '(6 (5 4 3 2 1) (7 8 9))) (5 (4 3 2 1) (6 7 8 9)) > (movetoright '(6 (5 4 3 2 1) (7 8 9))) (7 (6 5 4 3 2 1) (8 9)) > (inserttoleft 13 '(6 (5 4 3 2 1) (7 8 9))) (6 (13 5 4 3 2 1) (7 8 9)) > (inserttoright 13 '(6 (5 4 3 2 1) (7 8 9))) (6 (5 4 3 2 1) (13 7 8 9))
The procedure
movetoright
should fail if its argument is at the right end of the sequence, and the proceduremovetoleft
should fail if its argument is at the left end of the sequence.
(define number>sequence
(lambda (num)
(list num '() '())))
(define currentelement car)
(define movetoleft
(lambda (node)
(let ([before (cadr node)])
(if (null? before)
(eopl:error 'movetoleft "Cannot move to left when at left end.")
(let ([num (car node)]
[after (caddr node)])
(list (car before) (cdr before) (cons num after)))))))
(define movetoright
(lambda (node)
(let ([after (caddr node)])
(if (null? after)
(eopl:error 'movetoright "Cannot move to right when at right end.")
(let ([num (car node)]
[before (cadr node)])
(list (car after) (cons num before) (cdr after)))))))
(define inserttoleft
(lambda (num node)
(let ([current (car node)]
[before (cadr node)]
[after (caddr node)])
(list current (cons num before) after))))
(define inserttoright
(lambda (num node)
(let ([current (car node)]
[before (cadr node)]
[after (caddr node)])
(list current before (cons num after)))))
(define atleftend?
(lambda (node)
(null? (cadr node))))
(define atrightend?
(lambda (node)
(null? (caddr node))))
Exercise 2.19 [★]
A binary tree with empty leaves and with interior nodes labeled with integers could be represented using the grammar
Bintree ::=
()
(
Int Bintree Bintree)
In this representation, implement the procedure
number>bintree
, which takes a number and produces a binary tree consisting of a single node containing that number. Also implementcurrentelement
,movetoleftson
,movetorightson
,atleaf?
,inserttoleft
, andinserttoright
. For example,> (number>bintree 13) (13 () ()) > (define t1 (inserttoright 14 (inserttoleft 12 (number>bintree 13)))) > t1 (13 (12 () ()) (14 () ())) > (movetoleftson t1) (12 () ()) > (currentelement (movetoleftson t1)) 12 > (atleaf? (movetorightson (movetoleftson t1))) #t > (inserttoleft 15 t1) (13 (15 (12 () ()) ()) (14 () ()))
(define number>bintree
(lambda (num)
`(,num () ())))
(define currentelement car)
(define movetoleftson cadr)
(define movetorightson caddr)
(define atleaf? null?)
(define inserttoleft
(lambda (num bintree)
(let ([rootvalue (car bintree)]
[leftchild (cadr bintree)]
[rightchild (caddr bintree)])
`(,rootvalue (,num ,leftchild ()) ,rightchild))))
(define inserttoright
(lambda (num bintree)
(let ([rootvalue (car bintree)]
[leftchild (cadr bintree)]
[rightchild (caddr bintree)])
`(,rootvalue ,leftchild (,num () ,rightchild)))))
Exercise 2.20 [★★★]
In the representation of binary trees in exercise 2.19 it is easy to move from a parent node to one of its sons, but it is impossible to move from a son to its parent without the help of context arguments. Extend the representation of lists in exercise 2.18 to represent nodes in a binary tree. As a hint, consider representing the portion of the tree above the current node by a reversed list, as in exercise 2.18.
In this representation, implement the procedures from exercise 2.19. Also implement
moveup
andatroot?
.
(define number>bintree
(lambda (num)
(cons `(,num () ()) '())))
(define currentelement caar)
(define movetoleftson
(lambda (bintree)
(let* ([current (car bintree)]
[value (car current)]
[leftson (cadr current)]
[rightson (caddr current)]
[parents (cdr bintree)])
(cons leftson
(cons (list value 'right rightson)
parents)))))
(define movetorightson
(lambda (bintree)
(let* ([current (car bintree)]
[value (car current)]
[leftson (cadr current)]
[rightson (caddr current)]
[parents (cdr bintree)])
(cons rightson
(cons (list value 'left leftson)
parents)))))
(define atleaf?
(lambda (bintree)
(null? (car bintree))))
(define inserttoleft
(lambda (num bintree)
(let* ([current (car bintree)]
[value (car current)]
[leftson (cadr current)]
[rightson (caddr current)]
[parents (cdr bintree)])
(cons `(,value (,num ,leftson ()) ,rightson)
parents))))
(define inserttoright
(lambda (num bintree)
(let* ([current (car bintree)]
[value (car current)]
[leftson (cadr current)]
[rightson (caddr current)]
[parents (cdr bintree)])
(cons `(,value ,leftson (,num () ,rightson))
parents))))
(define moveup
(lambda (bintree)
(let* ([current (car bintree)]
[parents (cdr bintree)]
[parent (car parents)]
[parentvalue (car parent)]
[parentotherbranch (cadr parent)]
[parentotherson (caddr parent)]
[restparents (cdr parents)])
(if (eqv? parentotherbranch 'left)
(cons (list parentvalue parentotherson current)
restparents)
(cons (list parentvalue current parentotherson)
restparents)))))
(define atroot?
(lambda (bintree)
(null? (cdr bintree))))
2.4 A Tool for Defining Recursive Data Types
2.4.0
Exercise 2.21 [★]
Implement the data type of environments, as in section 2.2.2, using
definedatatype
. Then includehasbinding?
of exercise 2.9.
(definedatatype envtype env?
(emptyenv)
(extendenv [var symbol?]
[val always?]
[env env?]))
(define applyenv
(lambda (env searchvar)
(cases envtype env
[emptyenv () (eopl:error 'applyenv "No binding for ~s" searchvar)]
[extendenv (var val env) (if (eqv? var searchvar)
val
(applyenv env searchvar))])))
(define hasbinding?
(lambda (env searchvar)
(cases envtype env
[emptyenv () #f]
[extendenv (var val env) (or (eqv? var searchvar)
(hasbinding? env searchvar))])))
Exercise 2.22 [★]
Using
definedatatype
, implement the stack data type of exercise 2.4.
(definedatatype stacktype stack?
(emptystack)
(push [savedstack stack?]
[val always?]))
(define pop
(lambda (stack)
(cases stacktype stack
[emptystack () (eopl:error 'pop "Can not pop an empty stack.")]
[push (savedstack val) savedstack])))
(define top
(lambda (stack)
(cases stacktype stack
[emptystack () (eopl:error 'pop "Can not top an empty stack.")]
[push (savedstack val) val])))
(define emptystack?
(lambda (stack)
(cases stacktype stack
[emptystack () #t]
[push (savedstack val) #f])))
Exercise 2.23 [★]
The definition of
lcexp
ignores the condition in definition 1.1.8 that says “Identifier is any symbol other thanlambda
.” Modify the definition of identifier? to capture this condition. As a hint, remember that any predicate can be used indefinedatatype
, even ones you define.
(define identifier?
(lambda (value)
(and (symbol? value)
(not (eqv? value 'lambda)))))
Exercise 2.24 [★]
Here is a definition of binary trees using
definedatatype
.(definedatatype bintree bintree? (leafnode (num integer?)) (interiornode (key symbol?) (left bintree?) (right bintree?)))
Implement a
bintreetolist
procedure for binary trees, so that(bintreetolist (interiornode 'a (leafnode 3) (leafnode 4)))
returns the list(interiornode a (leafnode 3) (leafnode 4))
(define bintreetolist
(lambda (tree)
(cases bintree tree
[leafnode (num) `(leafnode ,num)]
[interiornode (key left right) (list 'interiornode
key
(bintreetolist left)
(bintreetolist right))])))
Exercise 2.25 [★★]
Use
cases
to writemaxinterior
, which takes a binary tree of integers (as in the preceding exercise) with at least one interior node and returns the symbol associated with an interior node with a maximal leaf sum.> (define tree1 (interiornode 'foo (leafnode 2) (leafnode 3))) > (define tree2 (interiornode 'bar (leafnode 1) tree1)) > (define tree3 (interiornode 'baz tree2 (leafnode 1))) > (maxinterior tree2) foo > (maxinterior tree3) baz
The last invocation of
maxinterior
might also have returnedfoo
, since both thefoo
andbaz
nodes have a leaf sum of 5.
(definedatatype bintreeinfo bintreeinfo?
[leafinfo [num integer?]]
[interiorinfo [sum integer?]
[maxsum integer?]
[maxkey symbol?]])
(define maxinteriorhelper
(lambda (tree)
(cases bintree tree
[leafnode (num)
(leafinfo num)]
[interiornode (key left right)
(let ([leftinfo (maxinteriorhelper left)]
[rightinfo (maxinteriorhelper right)])
(cases bintreeinfo leftinfo
[leafinfo (leftnum)
(cases bintreeinfo rightinfo
[leafinfo (rightnum)
(let ([sum (+ leftnum rightnum)])
(interiorinfo sum
sum
key))]
[interiorinfo (rightsum rightmaxsum rightmaxkey)
(let ([sum (+ leftnum rightsum)])
(if (< sum rightmaxsum)
(interiorinfo sum
rightmaxsum
rightmaxkey)
(interiorinfo sum
sum
key)))])]
[interiorinfo (leftsum leftmaxsum leftmaxkey)
(cases bintreeinfo rightinfo
[leafinfo (rightnum)
(let ([sum (+ leftsum rightnum)])
(if (< sum leftmaxsum)
(interiorinfo sum
leftmaxsum
leftmaxkey)
(interiorinfo sum
sum
key)))]
[interiorinfo (rightsum rightmaxsum rightmaxkey)
(let* ([sum (+ leftsum rightsum)]
[maxsumandkey (if (< leftmaxsum rightmaxsum)
(cons rightmaxsum rightmaxkey)
(cons leftmaxsum leftmaxkey))]
[maxsum (car maxsumandkey)]
[maxkey (cdr maxsumandkey)])
(if (< sum maxsum)
(interiorinfo sum
maxsum
maxkey)
(interiorinfo sum
sum
key)))])]))])))
(define maxinterior
(lambda (tree)
(cases bintreeinfo (maxinteriorhelper tree)
[leafinfo (num) (eopl:error 'maxinterior "~s is not an interior node" tree)]
[interiorinfo (sum maxsum maxkey) maxkey])))
Exercise 2.26 [★★]
Here is another version of exercise 1.33. Consider a set of trees given by the following grammar:
Redbluetree ::= Redbluesubtree
Redbluesubtree ::=
(rednode
Redbluesubtree Redbluesubtree)
::=(bluenode
{Redbluesubtree}^{∗})
::=(leafnode Int)
Write an equivalent definition using
definedatatype
, and use the resulting interface to write a procedure that takes a tree and builds a tree of the same shape, except that each leaf node is replaced by a leaf node that contains the number of red nodes on the path between it and the root.
(definedatatype redbluetree redbluetree?
[rednode [lson redbluetree?]
[rson redbluetree?]]
[bluenode [sons (listof redbluetree?)]]
[leafnode [num integer?]])
(define markleaveswithreddepthhelper
(lambda (tree rednum)
(cases redbluetree tree
[rednode (lson rson) (let ([newrednum (+ rednum 1)])
(rednode (markleaveswithreddepthhelper lson newrednum)
(markleaveswithreddepthhelper rson newrednum)))]
[bluenode (sons) (bluenode (map (lambda (son)
(markleaveswithreddepthhelper son rednum))
sons))]
[leafnode (_) (leafnode rednum)])))
(define markleaveswithreddepth
(lambda (tree)
(markleaveswithreddepthhelper tree 0)))
2.5 Abstract Syntax and Its Representation
2.5.0
Exercise 2.27 [★]
Draw the abstract syntax tree for the lambda calculus expressions
((lambda (a) (a b)) c) (lambda (x) (lambda (y) ((lambda (x) (x y)) x)))
((lambda (a) (a b)) c)
┌─────────┐
│ appexp │
└────┬────┘
┌──────┴───────┐
rator rand
┌─────┴──────┐ ┌────┴────┐
│ lambdaexp │ │ varexp │
└─────┬──────┘ └────┬────┘
┌────┴────┐ │
boundvar body var
┌─┴─┐ ┌────┴────┐ ┌─┴─┐
│ a │ │ appexp │ │ c │
└───┘ └────┬────┘ └───┘
┌─────┴──────┐
rator rand
┌────┴────┐ ┌────┴────┐
│ varexp │ │ varexp │
└────┬────┘ └────┬────┘
│ │
var var
┌─┴─┐ ┌─┴─┐
│ a │ │ b │
└───┘ └───┘
(lambda (x)
(lambda (y)
((lambda (x)
(x y))
x)))
┌────────────┐
│ lambdaexp │
└─────┬──────┘
┌────┴─────┐
boundvar body
┌─┴─┐ ┌─────┴──────┐
│ x │ │ lambdaexp │
└───┘ └─────┬──────┘
┌────┴────┐
boundvar body
┌─┴─┐ ┌────┴────┐
│ y │ │ appexp │
└───┘ └────┬────┘
┌──────┴───────┐
rator rand
┌─────┴──────┐ ┌────┴────┐
│ lambdaexp │ │ varexp │
└─────┬──────┘ └────┬────┘
┌────┴────┐ │
boundvar body var
┌─┴─┐ ┌────┴────┐ ┌─┴─┐
│ x │ │ appexp │ │ x │
└───┘ └────┬────┘ └───┘
┌─────┴──────┐
rator rand
┌────┴────┐ ┌────┴────┐
│ varexp │ │ varexp │
└────┬────┘ └────┬────┘
│ │
var var
┌─┴─┐ ┌─┴─┐
│ x │ │ y │
└───┘ └───┘
Exercise 2.28 [★]
Write an unparser that converts the abstract syntax of an lcexp into a string that matches the second grammar in this section (page 52).
(define identifier? symbol?)
(definedatatype lcexp lcexp?
[varexp [var identifier?]]
[lambdaexp [boundvar identifier?]
[body lcexp?]]
[appexp [rator lcexp?]
[rand lcexp?]])
(define unparselcexp
(lambda (exp)
(cases lcexp exp
[varexp (var) (symbol>string var)]
[lambdaexp (boundvar body)
(stringappend "(lambda ("
(symbol>string boundvar)
") "
(unparselcexp body)
")")]
[appexp (rator rand)
(stringappend "("
(unparselcexp rator)
" "
(unparselcexp rand)
")")])))
Exercise 2.29 [★]
Where a Kleene star or plus (page 7) is used in concrete syntax, it is most convenient to use a list of associated subtrees when constructing an abstract syntax tree. For example, if the grammar for lambdacalculus expressions had been
Lcexp ::= Identifier
varexp (var)
::=(lambda (
{Identifier}^{∗})
Lcexp)
lambdaexp (boundvars body)
::=(
Lcexp {Lcexp}^{∗})
appexp (rator rands)
then the predicate for the
boundvars
field could be(listof identifier?)
, and the predicate for therands
field could be(listof lcexp?)
. Write adefinedatatype
and a parser for this grammar that works in this way.
(define identifier?
(lambda (x)
(and (symbol? x)
(not (eqv? x 'lambda)))))
(definedatatype lcexp lcexp?
[varexp [var identifier?]]
[lambdaexp [boundvars (listof identifier?)]
[body lcexp?]]
[appexp [rator lcexp?]
[rands (listof lcexp?)]])
(define parseexpression
(lambda (datum)
(cond [(identifier? datum) (varexp datum)]
[(pair? datum) (if (eqv? (car datum) 'lambda)
(lambdaexp (cadr datum)
(parseexpression (caddr datum)))
(appexp (parseexpression (car datum))
(map parseexpression (cdr datum))))]
[else (eopl:error 'parseexpression "Invalid expression: ~s" datum)])))
Exercise 2.30 [★★]
The procedure
parseexpression
as defined above is fragile: it does not detect several possible syntactic errors, such as(a b c)
, and aborts with inappropriate error messages for other expressions, such as(lambda)
. Modify it so that it is robust, accepting any sexp and issuing an appropriate error message if the sexp does not represent a lambdacalculus expression.
(define identifier?
(lambda (x)
(and (symbol? x)
(not (eqv? x 'lambda)))))
(definedatatype lcexp lcexp?
[varexp (var identifier?)]
[lambdaexp [boundvar identifier?]
[body lcexp?]]
[appexp [rator lcexp?]
[rand lcexp?]])
(define reporterror
(lambda (expected datum)
(eopl:error 'parseexpression "Expect ~a, but got ~s." expected datum)))
(define parselambdaexpression
(lambda (datum)
(let ([afterlambda (cdr datum)])
(if (pair? afterlambda)
(let ([boundvarlist (car afterlambda)]
[afterboundvarlist (cdr afterlambda)])
(if (pair? boundvarlist)
(let ([boundvar (car boundvarlist)]
[afterboundvar (cdr boundvarlist)])
(if (identifier? boundvar)
(if (null? afterboundvar)
(if (pair? afterboundvarlist)
(let ([body (car afterboundvarlist)]
[afterbody (cdr afterboundvarlist)])
(if (null? afterbody)
(lambdaexp boundvar (parseexpression body))
(reporterror "null after body" afterbody)))
(reporterror "a pair after bound var list" afterboundvarlist))
(reporterror "null after bound var" afterboundvar))
(reporterror "an identifier" boundvar)))
(reporterror "a pair" boundvarlist)))
(reporterror "a pair after lambda" afterlambda)))))
(define parseapplicationexpression
(lambda (datum)
(let ([rator (car datum)]
[afterrator (cdr datum)])
(if (pair? afterrator)
(let ([rand (car afterrator)]
[afterrand (cdr afterrator)])
(if (null? afterrand)
(appexp (parseexpression rator) (parseexpression rand))
(reporterror "null after rand" afterrand)))
(reporterror "a pair after rator" afterrator)))))
(define parseexpression
(lambda (datum)
(cond [(symbol? datum) (if (eqv? datum 'lambda)
(reporterror "an identifier" datum)
(varexp datum))]
[(pair? datum) (if (eqv? (car datum) 'lambda)
(parselambdaexpression datum)
(parseapplicationexpression datum))]
[else (reporterror "a symbol or pair" datum)])))
Exercise 2.31 [★★]
Sometimes it is useful to specify a concrete syntax as a sequence of symbols and integers, surrounded by parentheses. For example, one might define the set of prefix lists by
Prefixlist ::=
(
Prefixexp)
Prefixexp ::= Int
::=
Prefixexp Prefixexpso that
(  3 2  4  12 7)
is a legal prefix list. This is sometimes called Polish prefix notation, after its inventor, Jan Łukasiewicz. Write a parser to convert a prefixlist to the abstract syntax(definedatatype prefixexp prefixexp? (constexp (num integer?)) (diffexp (operand1 prefixexp?) (operand2 prefixexp?)))
so that the example above produces the same abstract syntax tree as the sequence of constructors
(diffexp (diffexp (constexp 3) (constexp 2)) (diffexp (constexp 4) (diffexp (constexp 12) (constexp 7))))
As a hint, consider writing a procedure that takes a list and produces a
prefixexp
and the list of leftover list elements.
(definedatatype prefixexp prefixexp?
[constexp [num integer?]]
[diffexp [operand1 prefixexp?]
[operand2 prefixexp?]])
(define parseprefixexp
(lambda (prefixlist)
(let ([head (car prefixlist)]
[tail (cdr prefixlist)])
(cond [(integer? head) (cons (constexp head) tail)]
[(eqv? head ') (let* ([operand1andrest1 (parseprefixexp tail)]
[operand1 (car operand1andrest1)]
[rest1 (cdr operand1andrest1)]
[operand2andrest2 (parseprefixexp rest1)]
[operand2 (car operand2andrest2)]
[rest2 (cdr operand2andrest2)])
(cons (diffexp operand1 operand2) rest2))]
[else (eopl:error 'parseprefixexp "Bad syntax: ~s." prefixlist)]))))
(define parseprefixlist
(lambda (prefixlist)
(let* ([expandrest (parseprefixexp prefixlist)]
[exp (car expandrest)]
[rest (cdr expandrest)])
(if (null? rest)
exp
(eopl:error 'parseprefixlist "Expect null after prefixexp, but got: ~s." rest)))))
3 Expressions
3.2 LET: A Simple Language
3.2.4 Specifying the Behavior of Expressions
Exercise 3.1 [★]
In figure 3.3, list all the places where we used the fact that ⌊⌈n⌉⌋ = n.
Skipped.
Exercise 3.2 [★★]
Give an expressed value val ∈ ExpVal for which ⌈⌊val⌋⌉ ≠ val.
Not sure, but maybe when val is constructed using a Bool?
3.2.8 Implementing the Specification of LET
Exercise 3.3 [★]
Why is subtraction a better choice than addition for our single arithmetic operation?
One reason I can think of, is that subtraction is not commutative, that is \(a  b\) may not equal to \(b  a\). If our implementation of subtraction is incorrect, we can discover the error quickly.
Exercise 3.4 [★]
Write out the derivation of figure 3.4 as a derivation tree in the style of the one on page 5.
\[ \dfrac{\dfrac{\dfrac{\dfrac{\texttt{(valueof «x» $ρ$)} = 33} {\texttt{(valueof «(x, 11)» $ρ$)} = 22}} {\texttt{(valueof «zero?((x, 11))» $ρ$)} = \texttt{(boolval #f)}}} {\texttt{(valueof «if zero?((x, 11)) then (y, 2) else (y, 4)» $ρ$)} = \texttt{(valueof «(y, 4)» $ρ$)}} \quad \dfrac{\texttt{(valueof «y» $ρ$)} = 22} {\texttt{(valueof «(y, 4)» $ρ$)} = 18}} {\texttt{(valueof «if zero?((x, 11)) then (y, 2) else (y, 4)» $ρ$)} = 18} \]
Exercise 3.5 [★]
Write out the derivation of figure 3.5 as a derivation tree in the style of the one on page 5.
Skipped.
Exercise 3.6 [★]
Extend the language by adding a new operator minus that takes one argument, n, and returns −n. For example, the value of
minus((minus(5), 9))
should be 14.
Solution is implemented here.
Exercise 3.7 [★]
Extend the language by adding operators for addition, multiplication, and integer quotient.
Solution is implemented here.
Exercise 3.8 [★]
Add a numeric equality predicate
equal?
and numeric order predicatesgreater?
andless?
to the set of operations in the defined language.
Solution is implemented here.
Exercise 3.9 [★★]
Add list processing operations to the language, including
cons
,car
,cdr
,null?
andemptylist
. A list should be able to contain any expressed value, including another list. Give the definitions of the expressed and denoted values of the language, as in section 3.2.2. For example,let x = 4 in cons(x, cons(cons((x,1), emptylist), emptylist))
should return an expressed value that represents the list
(4 (3))
.
Solution is implemented here.
Exercise 3.10 [★★]
Add an operation
list
to the language. This operation should take any number of arguments, and return an expressed value containing the list of their values. For example,let x = 4 in list(x, (x,1), (x,3))
should return an expressed value that represents the list
(4 3 1)
.
Solution is implemented here.
Exercise 3.11 [★]
In a real language, one might have many operators such as those in the preceding exercises. Rearrange the code in the interpreter so that it is easy to add new operators.
Solution is implemented here.
Exercise 3.12 [★]
Add to the defined language a facility that adds a
cond
expression. Use the grammarExpression ::=
cond
{Expression==>
Expression}^{∗}end
In this expression, the expressions on the lefthand sides of the
==>
’s are evaluated in order until one of them returns a true value. Then the value of the entire expression is the value of the corresponding righthand expression. If none of the tests succeeds, the expression should report an error.
Solution is implemented here.
Exercise 3.13 [★]
Change the values of the language so that integers are the only expressed values. Modify
if
so that the value 0 is treated as false and all other values are treated as true. Modify the predicates accordingly.
Solution is implemented here.
Exercise 3.14 [★★]
As an alternative to the preceding exercise, add a new nonterminal Boolexp of boolean expressions to the language. Change the production for conditional expressions to say
Expression ::=
if
Boolexpthen
Expressionelse
ExpressionWrite suitable productions for Boolexp and implement
valueofboolexp
. Where do the predicates of exercise 3.8 wind up in this organization?
I’ll deal with this one later.
Exercise 3.15 [★]
Extend the language by adding a new operation
Solution is implemented here.
Because print
cause a side effect while our specification framework does not have something to do this.
Exercise 3.16 [★★]
Extend the language so that a
let
declaration can declare an arbitrary number of variables, using the grammarExpression ::=
let
{Identifier=
Expression}^{∗}in
ExpressionAs in Scheme’s
let
, each of the righthand sides is evaluated in the current environment, and the body is evaluated with each new variable bound to the value of its associated righthand side. For example,let x = 30 in let x = (x,1) y = (x,2) in (x,y)
should evaluate to 1.
Solution is implemented here.
Exercise 3.17 [★★]
Extend the language with a
let*
expression that works like Scheme’slet*
, so thatlet x = 30 in let* x = (x,1) y = (x,2) in (x,y)
should evaluate to 2.
Solution is implemented here.
Exercise 3.18 [★★]
Add an expression to the defined language:
Expression ::=
unpack
{Identifier}^{∗}=
Expressionin
Expressionso that
unpack x y z = lst in ...
bindsx
,y
, andz
to the elements oflst
iflst
is a list of exactly three elements, and reports an error otherwise. For example, the value oflet u = 7 in unpack x y = cons(u,cons(3,emptylist)) in (x,y)
should be 4.
Solution is implemented here.
3.3 PROC: A Language with Procedures
3.3.2 Representing Procedures
Exercise 3.19 [★]
In many languages, procedures must be created and named at the same time. Modify the language of this section to have this property by replacing the
proc
expression with aletproc
expression.
Skipped.
Exercise 3.20 [★]
In PROC, procedures have only one argument, but one can get the effect of multiple argument procedures by using procedures that return other procedures. For example, one might write code like
let f = proc (x) proc (y) ... in ((f 3) 4)
This trick is called Currying, and the procedure is said to be Curried. Write a Curried procedure that takes two arguments and returns their sum. You can write x + y in our language by writing
(
x, (0,
y))
.
proc (x)
proc (y)
(x, (0, y))
Exercise 3.21 [★★]
Extend the language of this section to include procedures with multiple arguments and calls with multiple operands, as suggested by the grammar
Expression ::=
proc (
{Identifier}^{∗(,)})
Expression
Expression ::=(
Expression {Expression}^{∗})
Solution is implemented here.
Exercise 3.22 [★★★]
The concrete syntax of this section uses different syntax for a builtin operation, such as difference, from a procedure call. Modify the concrete syntax so that the user of this language need not know which operations are builtin and which are defined procedures. This exercise may range from very easy to hard, depending on the parsing technology being used.
Solution is implemented here.
Exercise 3.23 [★★]
What is the value of the following PROC program?
let makemult = proc (maker) proc (x) if zero?(x) then 0 else (((maker maker) (x,1)), 4) in let times4 = proc (x) ((makemult makemult) x) in (times4 3)
Use the tricks of this program to write a procedure for factorial in PROC. As a hint, remember that you can use Currying (exercise 3.20) to define a twoargument procedure
times
.
Value of given program is 12.
The procedure of factorial:
let maketimes = proc (maker)
proc (x)
proc (y)
if zero?(x)
then 0
else ((((maker maker) (x, 1)) y), (0, y))
in let times = (maketimes maketimes)
in let makefact = proc (maker)
proc (x)
if zero?(x)
then 1
else ((times x) ((maker maker) (x, 1)))
in (makefact makefact)
Exercise 3.24 [★★]
Use the tricks of the program above to write the pair of mutually recursive procedures,
odd
andeven
, as in exercise 3.32.
odd
:
let false = zero?(1)
in let true = zero?(0)
in let makeeven = proc (makeeven)
proc (makeodd)
proc (x)
if zero?(x)
then true
else (((makeodd makeeven) makeodd) (x, 1))
in let makeodd = proc (makeeven)
proc (makeodd)
proc (x)
if zero?(x)
then false
else (((makeeven makeeven) makeodd) (x, 1))
in ((makeodd makeeven) makeodd)
even
:
let false = zero?(1)
in let true = zero?(0)
in let makeeven = proc (makeeven)
proc (makeodd)
proc (x)
if zero?(x)
then true
else (((makeodd makeeven) makeodd) (x, 1))
in let makeodd = proc (makeeven)
proc (makeodd)
proc (x)
if zero?(x)
then false
else (((makeeven makeeven) makeodd) (x, 1))
in ((makeeven makeeven) makeodd)
Exercise 3.25 [★]
The tricks of the previous exercises can be generalized to show that we can define any recursive procedure in PROC. Consider the following bit of code:
let makerec = proc (f) let d = proc (x) proc (z) ((f (x x)) z) in proc (n) ((f (d d)) n) in let maketimes4 = proc (f) proc (x) if zero?(x) then 0 else ((f (x,1)), 4) in let times4 = (makerec maketimes4) in (times4 3)
Show that it returns 12.
maketimes4
is a procedure that takes a times4
procedure and returns a times4
procedure. First we convert
maketimes4
to a procedure maker
that takes a maker
and returns a times4
procedure (assume we use f
to
represent maketimes4
):
proc (f)
let maker = proc (maker)
let recursiveproc = (maker maker)
in (f recursiveproc)
in ...
But the code would not work because once we call (maker maker)
, it will first call (maker maker)
which will cause
infinite recursion. We will fix this by wrapping (maker maker)
inside another procedure:
proc (f)
let maker = proc (maker)
proc (x)
let recursiveproc = (maker maker)
in ((f recursiveproc) x)
in ...
Now we get a maker
, we call the maker
with maker
, we will get a recursive version of f
:
proc (f)
let maker = proc (maker)
proc (x)
let recursiveproc = (maker maker)
in ((f recursiveproc) x)
in (maker maker)
Let’s run the program:
let makerec = proc (f)
let maker = proc (maker)
proc (x)
let recursiveproc = (maker maker)
in ((f recursiveproc) x)
in (maker maker)
in let maketimes4 = proc (f)
proc (x)
if zero?(x)
then 0
else ((f (x, 1)), 4)
in let times4 = (makerec maketimes4)
in (times4 3)
Yep, the result is also 12. Although it is a little different than the original one.
Exercise 3.26 [★★]
In our datastructure representation of procedures, we have kept the entire environment in the closure. But of course all we need are the bindings for the free variables. Modify the representation of procedures to retain only the free variables.
Here is a function that filters free variables in the environment:
(define (filterenv env boundvars exp)
(let loop ([result (emptyenv)]
[boundvars boundvars]
[exp exp])
(cases expression exp
[constexp (num) result]
[varexp (var) (if (memv var boundvars)
result
(extendenv var (applyenv env var) result))]
[diffexp (exp1 exp2) (loop (loop result boundvars exp1) boundvars exp2)]
[zero?exp (exp1) (loop result boundvars exp1)]
[ifexp (exp1 exp2 exp3) (loop (loop (loop result
boundvars
exp1)
boundvars
exp2)
boundvars
exp3)]
[letexp (var exp1 body) (loop (loop result boundvars exp1)
(cons var boundvars)
body)]
[procexp (vars body) (loop result (append vars boundvars) body)]
[callexp (rator rands) (let loop2 ([result (loop result boundvars rator)]
[rands rands])
(if (null? rands)
result
(loop2 (loop result boundvars (car rands))
(cdr rands))))])))
Exercise 3.27 [★]
Add a new kind of procedure called a
traceproc
to the language. Atraceproc
works exactly like aproc
, except that it prints a trace message on entry and on exit.
Solution is implemented here.
Exercise 3.28 [★★]
Dynamic binding (or dynamic scoping) is an alternative design for procedures, in which the procedure body is evaluated in an environment obtained by extending the environment at the point of call. For example in
let a = 3 in let p = proc (x) (x,a) a = 5 in (a,(p 2))
the
a
in the procedure body would be bound to 5, not 3. Modify the language to use dynamic binding. Do this twice, once using a procedural representation for procedures, and once using a datastructure representation.
Solution is implemented here.
Only datastructure representation is implemented.
Exercise 3.29 [★★]
Unfortunately, programs that use dynamic binding may be exceptionally difficult to understand. For example, under lexical binding, consistently renaming the bound variables of a procedure can never change the behavior of a program: we can even remove all variables and replace them by their lexical addresses, as in section 3.6. But under dynamic binding, this transformation is unsafe.
For example, under dynamic binding, the procedure
proc (z) a
returns the value of the variablea
in its caller’s environment. Thus, the programlet a = 3 in let p = proc (z) a in let f = proc (x) (p 0) in let a = 5 in (f 2)
returns 5, since
a
’s value at the call site is 5. What iff
’s formal parameter werea
?
The result should be 2.
3.4 LETREC: A Language with Recursive Procedures
3.4.0
Exercise 3.30 [★]
What is the purpose of the call to
procval
on the nexttolast line ofapplyenv
?
When we are creating the desired recursive closure, we need an environment containing the closure, but we can not create
the environment directly because we need the closure in order to create the environment. So we delay the creation of
the closure in the environment so that we can create the environment without a closure. Then, when we need to use the
closure, we create it by calling procval
.
Exercise 3.31 [★]
Extend the language above to allow the declaration of a recursive procedure of possibly many arguments, as in exercise 3.21.
Solution is implemented here.
Exercise 3.32 [★★]
Extend the language above to allow the declaration of any number of mutually recursive unary procedures, for example:
letrec even(x) = if zero?(x) then 1 else (odd (x,1)) odd(x) = if zero?(x) then 0 else (even (x,1)) in (odd 13)
Solution is implemented here.
Exercise 3.33 [★★]
Extend the language above to allow the declaration of any number of mutually recursive procedures, each of possibly many arguments, as in exercise 3.21.
Solution is implemented here.
Exercise 3.34 [★★★]
Implement
extendenvrec
in the procedural representation of environments from section 2.2.3.
Skipped.
Exercise 3.35 [★]
The representations we have seen so far are inefficient, because they build a new closure every time the procedure is retrieved. But the closure is the same every time. We can build the closures only once, by putting the value in a vector of length 1 and building an explicit circular structure, like
TODO: Add this figure later.
Here’s the code to build this data structure.
(define extendenvrec (lambda (pname bvar body savedenv) (let ((vec (makevector 1))) (let ((newenv (extendenv pname vec savedenv))) (vectorset! vec 0 (procval (procedure bvar body newenv))) newenv))))
Complete the implementation of this representation by modifying the definitions of the environment data type and
applyenv
accordingly. Be sure thatapplyenv
always returns an expressed value.
Solution is implemented here.
Exercise 3.36 [★★]
Extend this implementation to handle the language from exercise 3.32.
Solution is implemented here.
Exercise 3.37 [★]
With dynamic binding (exercise 3.28), recursive procedures may be bound by
let
; no special mechanism is necessary for recursion. This is of historical interest; in the early years of programming language design other approaches to recursion, such as those discussed in section 3.4, were not widely understood. To demonstrate recursion via dynamic binding, test the programlet fact = proc (n) add1(n) in let fact = proc (n) if zero?(n) then 1 else *(n,(fact (n,1))) in (fact 5)
using both lexical and dynamic binding. Write the mutually recursive procedures
even
andodd
as in section 3.4 in the defined language with dynamic binding.
Skipped.
3.7 Implementing Lexical Addressing
3.7.2 The Nameless Interpreter
Exercise 3.38 [★]
Extend the lexical address translator and interpreter to handle
cond
from exercise 3.12.
Solution is implemented here.
Exercise 3.39 [★]
Extend the lexical address translator and interpreter to handle
pack
andunpack
from exercise 3.18.
Solution is implemented here.
Exercise 3.40 [★★]
Extend the lexical address translator and interpreter to handle
letrec
. Do this by modifying the context argument totranslationof
so that it keeps track of not only the name of each bound variable, but also whether it was bound byletrec
or not. For a reference to a variable that was bound by aletrec
, generate a new kind of reference, called anamelessletrecvarexp
. You can then continue to use the nameless environment representation above, and the interpreter can do the right thing with anamelessletrecvarexp
.
Solution is implemented here.
Exercise 3.41 [★★]
Modify the lexical address translator and interpreter to handle
let
expressions, procedures, and procedure calls with multiple arguments, as in exercise 3.21. Do this using a nameless version of the ribcage representation of environments (exercise 2.11). For this representation, the lexical address will consist of two nonnegative integers: the lexical depth, to indicate the number of contours crossed, as before; and a position, to indicate the position of the variable in the declaration.
Solution is implemented here.
Exercise 3.42 [★★★]
Modify the lexical address translator and interpreter to use the trimmed representation of procedures from exercise 3.26. For this, you will need to translate the body of the procedure not
(extendsenv
var senv)
, but in a new static environment that tells exactly where each variable will be kept in the trimmed representation.
Solution is implemented here.
Exercise 3.43 [★★★]
The translator can do more than just keep track of the names of variables. For example, consider the program
let x = 3 in let f = proc (y) (y,x) in (f 13)
Here we can tell statically that at the procedure call,
f
will be bound to a procedure whose body is(y,x)
, wherex
has the same value that it had at the procedurecreation site. Therefore we could avoid looking upf
in the environment entirely. Extend the translator to keep track of “known procedures” and generate code that avoids an environment lookup at the call of such a procedure.
Solution is implemented here.
Exercise 3.44 [★★★]
In the preceding example, the only use of
f
is as a known procedure. Therefore the procedure built by the expression proc(y) (y,x)
is never used. Modify the translator so that such a procedure is never constructed.
Solution is implemented here.
4 State
4.2 EXPLICITREFS: A Language with Explicit References
4.2.0
Exercise 4.1 [★]
What would have happened had the program been instead
let g = proc (dummy) let counter = newref(0) in begin setref(counter, (deref(counter), 1)); deref(counter) end in let a = (g 11) in let b = (g 11) in (a,b)
The result would been 0. Because counter
rebinds to a new location that has the value 0 every time g is called, the
final value that referenced by counter
will be the same.
4.2.1 StorePassing Specifications
Exercise 4.2 [★]
Write down the specification for a
zero?exp
.
\[ \dfrac{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} = (val_1, σ_1)} {\texttt{(valueof (zero?exp $exp_1$) $ρ$ $σ_0$)} = \cases{(\texttt{(boolval #t)}, σ_1) &if $\texttt{(expval>num $val_1$)} = 0$ \\ (\texttt{(boolval #f)}, σ_1) &if $\texttt{(expval>num $val_1$)} ≠ 0$}} \]
Exercise 4.3 [★]
Write down the specification for a
callexp
.
\[ \dfrac{\eqalign{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} &= (val_1, σ_1) \\ \texttt{(valueof $exp_2$ $ρ$ $σ_1$)} &= (val_2, σ_2)}} {\texttt{(valueof (callexp $exp_1$ $exp_2$) $ρ$ $σ_0$)} = \texttt{(applyprocedure $val_1$ $val_2$ $σ_2$)}} \]
Exercise 4.4 [★★]
Write down the specification for a
begin
expression.Expression ::=
begin
Expression {;
Expression}^{∗}end
A
begin
expression may contain one or more subexpressions separated by semicolons. These are evaluated in order and the value of the last is returned.
\[ \dfrac{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} = (val_1, σ_1)} {\eqalign{\texttt{(valueof (beginexp $exp_1$ '()) $ρ$ $σ_0$)} &= (val_1, σ_1) \\ \texttt{(valueof (beginexp $exp_1$ (cons $exp_2$ $exps$)) $ρ$ $σ_0$)} &= \texttt{(valueof (beginexp $exp_2$ $exps$) $ρ$ $σ_1$)}}} \]
Exercise 4.5 [★★]
Write down the specification for
list
(exercise 3.10).
\[ \texttt{(valueof (listexp '()))} = \texttt{(emptylist)} \]
\[ \dfrac{\eqalign{ \texttt{(valueof $exp_1$ $ρ$ $σ_0$)} &= (val_1, σ_1) \\ \texttt{(valueof (listexp $exps$) $ρ$ $σ_1$)} &= (val_2, σ_2)}} {\texttt{(valueof (listexp (cons $exp_1$ $exps$)))} = (\texttt{(pairval $val_1$ $val_2$)}, σ_2)} \]
4.2.2 Specifying Operations on Explicit References
Exercise 4.6 [★]
Modify the rule given above so that a
setrefexp
returns the value of the righthand side.
\[ \dfrac{\eqalign{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} &= (l, σ_1) \\ \texttt{(valueof $exp_2$ $ρ$ $σ_1$)} &= (val, σ_2)}} {\texttt{(valueof (setrefexp $exp_1$ $exp_2$ $ρ$ $σ_0$))} = (val, [l=val]σ_2)} \]
Exercise 4.7 [★]
Modify the rule given above so that a
setrefexp
returns the old contents of the location.
\[ \dfrac{\eqalign{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} &= (l, σ_1) \\ \texttt{(valueof $exp_2$ $ρ$ $σ_1$)} &= (val, σ_2)}} {\texttt{(valueof (setrefexp $exp_1$ $exp_2$ $ρ$ $σ_0$))} = (σ_0(l), [l=val]σ_2)} \]
4.2.3 Implementation
Exercise 4.8 [★]
Show exactly where in our implementation of the store these operations take linear time rather than constant time.
In newref
, length
and append
take linear time, so newref
takes linear time.
In deref
, listref
take linear time, so deref
takes linear time.
In setref!
, setrefinner
loops through the store, which takes linear time, so setref!
takes linear time.
Exercise 4.9 [★]
Implement the store in constant time by representing it as a Scheme vector. What is lost by using this representation?
(define (emptystore)
(vector))
(define thestore 'uninitialized)
(define (getstore)
thestore)
(define (initializestore!)
(set! thestore (emptystore)))
(define (reference? v)
(and (integer? v)
(not (negative? v))))
(define (extendstore store val)
(let* ([storesize (vectorlength store)]
[newstore (makevector (+ storesize 1))])
(let loop ([i 0])
(if (< i storesize)
(let ([val (vectorref store i)])
(vectorset! newstore i val)
(loop (+ i 1)))
(vectorset! newstore i val)))
(cons newstore storesize)))
(define (newref val)
(let* ([newstoreinfo (extendstore thestore val)]
[newstore (car newstoreinfo)]
[newref (cdr newstoreinfo)])
(set! thestore newstore)
newref))
(define (deref ref)
(vectorref thestore ref))
(define (reportinvalidreference ref store)
(eopl:error 'setref
"illegal reference ~s in store ~s"
ref
store))
(define (setref! ref val)
(if (and (reference? ref)
(< ref (vectorlength thestore)))
(vectorset! thestore ref val)
(reportinvalidreference ref thestore)))
Note that newref
still takes linear time. It is possible to implement the store that allocates locations in constant
time on average by preallocating more locations in advance, but it is a little complicated, so I’ll just choose the easy
way to implement the store.
As for the disadvantages of using a Scheme vector to implement the store, may be sharing values between stores becomes more difficult.
Exercise 4.10 [★]
Implement the
begin
expression as specified in exercise 4.4.
The reference implementation already implemented the begin
expression, so I’ll just skip this one.
Exercise 4.11 [★]
Implement
list
from exercise 4.5.
Solution is implemented here.
Exercise 4.12 [★★★]
Our understanding of the store, as expressed in this interpreter, depends on the meaning of effects in Scheme. In particular, it depends on us knowing when these effects take place in a Scheme program. We can avoid this dependency by writing an interpreter that more closely mimics the specification. In this interpreter,
valueof
would return both a value and a store, just as in the specification. A fragment of this interpreter appears in figure 4.6. We call this a storepassing interpreter. Extend this interpreter to cover all of the language EXPLICITREFS.Every procedure that might modify the store returns not just its usual value but also a new store. These are packaged in a data type called
answer
. Complete this definition ofvalueof
.
Solution is implemented here.
Also, what is applystore
in the reference implementation?
Exercise 4.13 [★★★]
Extend the interpreter of the preceding exercise to have procedures of multiple arguments.
Solution is implemented here.
4.3 IMPLICITREFS: A Language with Implicit References
4.3.1 Specification
Exercise 4.14 [★]
Write the rule for
let
.
\[ \dfrac{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} = (val_1, σ_1)} {\texttt{(valueof (letexp $var$ $exp_1$ $body$) $ρ$ $σ_0$)} = \texttt{(valueof $body$ $[var = l]ρ$ $[l = val_1]σ_1$)}} \]
4.3.2 The Implementation
Exercise 4.15 [★]
In figure 4.8, why are variables in the environment bound to plain integers rather than expressed values, as in figure 4.5?
Because we know for sure that the denoted values will all be references, so plain integers are sufficient to represent the location info we need.
Exercise 4.16 [★]
Now that variables are mutable, we can build recursive procedures by assignment. For example
letrec times4(x) = if zero?(x) then 0 else ((times4 (x,1)), 4) in (times4 3)
can be replaced by
let times4 = 0 in begin set times4 = proc (x) if zero?(x) then 0 else ((times4 (x,1)), 4); (times4 3) end
Trace this by hand and verify that this translation works.
First we allocate a new location for the number 0, then we bind times4
to the location. After we setting times4
to
the procedure, the location pointed by times4
contains the procedure closure. In the enclosed environment of the
procedure, times4
also points to the procedure so the procedure can call itself recursively.
Exercise 4.17 [★★]
Write the rules for and implement multiargument procedures and
let
expressions.
\[ \eqalign{ &\texttt{(applyprocedure (procedure (list $var_1$ $var_2$ $…$ $var_n$) $body$ $ρ$) (list $val_1$ $val_2$ $…$ $val_n$) $σ$)} \\ = &\texttt{(valueof $body$ $[var_n = l_n]…[var_2 = l_2][var_1 = l_1]ρ$ $[l_n = val_n]…[l_2 = val_2][l_1 = val_1]σ$)}} \]
\[ \dfrac{\eqalign{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} &= (val_1, σ_1) \\ \texttt{(valueof $exp_2$ $ρ$ $σ_1$)} &= (val_2, σ_2) \\ &… \\ \texttt{(valueof $exp_n$ $ρ$ $σ_{n  1}$)} &= (val_n, σ_n)}} {\eqalign{ &\texttt{(valueof (letexp (list $var_1$ $var_2$ $…$ $var_n$) (list $exp_1$ $exp_2$ $…$ $exp_n$) $body$) $ρ$ $σ_0$)} \\ = &\texttt{(valueof $body$ $[var_n = l_n]…[var_2 = l_2][var_1 = l_1]ρ$ $[l_n = val_n]…[l_2 = val_2][l_1 = val_1]σ_n$)}}} \]
Exercise 4.18 [★★]
Write the rule for and implement multiprocedure
letrec
expressions.
\[ \eqalign{ &\texttt{(valueof (letrecexp (list $var_1$ $var_2$ $…$ $var_n$) (list $bvars_1$ $bvars_2$ $…$ $bvars_n$) (list $pbody_1$ $pbody_2$ $…$ $pbody_n$) $letrecbody$) $ρ$ $σ$)} \\ = &\texttt{(let ([letrecenv $[var_n=l_n]…[var_2=l_2][var_1=l_1]ρ$])} \\ &\quad \texttt{(valueof $letrecbody$ letrecenv $[l_n = \texttt{(procedure $bvars_n$ $pbody_n$ letrecenv)}] … [l_2 = \texttt{(procedure $bvars_2$ $pbody_2$ letrecenv)}] [l_1 = \texttt{(procedure $bvars_1$ $pbody_1$ letrecenv)}]σ$))}} \]
Exercise 4.19 [★★]
Modify the implementation of multiprocedure
letrec
so that each closure is built only once, and only one location is allocated for it. This is like exercise 3.35.
Solution is implemented here.
Exercise 4.20 [★★]
In the language of this section, all variables are mutable, as they are in Scheme. Another alternative is to allow both mutable and immutable variable bindings:
 ExpVal = Int + Bool + Proc
 DenVal = Ref(ExpVal) + ExpVal
Variable assignment should work only when the variable to be assigned to has a mutable binding. Dereferencing occurs implicitly when the denoted value is a reference.
Modify the language of this section so that
let
introduces immutable variables, as before, but mutable variables are introduced by aletmutable
expression, with syntax given byExpression ::=
letmutable
Identifier=
Expressionin
Expression
Solution is implemented here.
Exercise 4.21 [★★]
We suggested earlier the use of assignment to make a program more modular by allowing one procedure to communicate information to a distant procedure without requiring intermediate procedures to be aware of it. Very often such an assignment should only be temporary, lasting for the execution of a procedure call. Add to the language a facility for dynamic assignment (also called fluid binding) to accomplish this. Use the production
Expression ::=
setdynamic
Identifier=
Expressionduring
Expression
setdynamicexp (
var exp_{1} body)
The effect of the
setdynamic
expression is to assign temporarily the value of exp_{1} to var, evaluate body, reassign var to its original value, and return the value of body. The variable var must already be bound. For example, inlet x = 11 in let p = proc (y) (y,x) in (setdynamic x = 17 during (p 22), (p 13))
the value of
x
, which is free in procedurep
, is 17 in the call(p 22)
, but is reset to 11 in the call(p 13)
, so the value of the expression is 5 − 2 = 3.
Solution is implemented here.
Exercise 4.22 [★★]
So far our languages have been expressionoriented: the primary syntactic category of interest has been expressions and we have primarily been interested in their values. Extend the language to model the simple statementoriented language whose specification is sketched below. Be sure to Follow the Grammar by writing separate procedures to handle programs, statements, and expressions.
Values As in IMPLICITREFS.
Syntax Use the following syntax:
Program ::= Statement
Statement ::= Identifier
=
Expression
::=
::={
{Statement}^{∗(;)}}
::=if
Expression Statement Statement
::=while
Expression Statement
::=var
{Identifier}^{∗(,)};
StatementThe nonterminal Expression refers to the language of expressions of IMPLICITREFS, perhaps with some extensions.
Semantics A program is a statement. A statement does not return a value, but acts by modifying the store and by printing.
Assignment statements work in the usual way. A print statement evaluates its actual parameter and prints the result. The
if
statement works in the usual way. A block statement, defined in the last production for Statement, binds each of the declared variables to an uninitialized reference and then executes the body of the block. The scope of these bindings is the body.Write the specification for statements using assertions like
\[ \texttt{(resultof $stmt$ $ρ$ $σ_0$)} = σ_1 \]
Examples Here are some examples.
(run "var x,y; {x = 3; y = 4; print +(x,y)} % Example 1") 7 (run "var x,y,z; {x = 3; % Example 2 y = 4; z = 0; while not(zero?(x)) {z = +(z,y); x = (x,1)}; print z}") 12 (run "var x; {x = 3; % Example 3 print x; var x; {x = 4; print x}; print x}") 3 4 3 (run "var f,x; {f = proc(x,y) *(x,y); % Example 4 x = 3; print (f 4 x)}") 12
Example 3 illustrates the scoping of the block statement.
Example 4 illustrates the interaction between statements and expressions. A procedure value is created and stored in the variable
f
. In the last line, this procedure is applied to the actual parameters 4 andx
; sincex
is bound to a reference, it is dereferenced to obtain 3.
Solution is implemented here.
Specification for statements:
\[ \dfrac{\texttt{(valueof $exp$ $ρ$ $σ_0$)} = (val, σ_1)} {\texttt{(resultof (assignstatement $var$ $exp$) $ρ$ $σ_0$)} = [ρ(var) = val]σ_1} \]
\[ \dfrac{\texttt{(valueof $exp$ $ρ$ $σ_0$)} = (val, σ_1)} {\texttt{(resultof (printstatement $exp$) $ρ$ $σ_0$)} = σ_1} \]
\[ \dfrac{\eqalign{ \texttt{(resultof $stmt_1$ $ρ$ $σ_0$)} &= σ_1 \\ \texttt{(resultof $stmt_2$ $ρ$ $σ_1$)} &= σ_2 \\ &… \\ \texttt{(resultof $stmt_n$ $ρ$ $σ_{n  1}$)} &= σ_n}} {\texttt{(resultof (bracestatement (list $stmt_1$ $stmt_1$ $…$ $stmt_n$)) $ρ$ $σ_0$)} = σ_n} \]
\[ \dfrac{\texttt{(valueof $exp$ $ρ$ $σ_0$)} = (val, σ_1)} {\texttt{(resultof (ifstatement $exp$ $stmt_1$ $stmt_2$) $ρ$ $σ_0$)} = \cases{\texttt{(resultof $stmt_1$ $ρ$ $σ_1$)} &if $\texttt{(expval>bool $val$)} = \texttt{#t}$ \\ \texttt{(resultof $stmt_2$ $ρ$ $σ_1$)} &if $\texttt{(expval>bool $val$)} = \texttt{#f}$}} \]
\[ \dfrac{\eqalign{ \texttt{(valueof $exp$ $ρ$ $σ_0$)} &= (val, σ_1) \\ \texttt{(resultof $stmt$ $ρ$ $σ_1$)} &= σ_2}} {\eqalign{ &\texttt{(resultof (whilestatement $exp$ $stmt$) $ρ$ $σ_2$)} \\ = &\cases{\texttt{(resultof (whilestatement $exp$ $stmt$) $ρ$ $σ_2$)} &if $\texttt{(expval>bool $val$)} = \texttt{#t}$ \\ σ_1 &if $\texttt{(expval>bool $val$)} = \texttt{#f}$}}} \]
\[ \eqalign{ &\texttt{(resultof (blockstatement (list $var_1$ $var_2$ $…$ $var_n$) $stmt$) $ρ$ $σ_0$)} \\ = &\texttt{(resultof $stmt$ $[var_n = l_n]…[var_2 = l_2][var_1 = l_1]ρ$ $[l_n = undefined]…[l_2 = undefined][l_1 = undefined]σ_0$)}} \]
Exercise 4.23 [★]
Add to the language of exercise 4.22
read
statements of the formread
var. This statement reads a nonnegative integer from the input and stores it in the given variable.
Solution is implemented here.
Exercise 4.24 [★]
A
dowhile
statement is like awhile
statement, except that the test is performed after the execution of the body. Adddowhile
statements to the language of exercise 4.22.
Solution is implemented here.
Exercise 4.25 [★]
Extend the block statement of the language of exercise 4.22 to allow variables to be initialized. In your solution, does the scope of a variable include the initializer for variables declared later in the same block statement?
Solution is implemented here.
No, the scope of a variable does not include the initializer for variables declared later in the same block statement.
Exercise 4.26 [★★★]
Extend the solution to the preceding exercise so that procedures declared in a single block are mutually recursive. Consider restricting the language so that the variable declarations in a block are followed by the procedure declarations.
Solution is implemented here.
Exercise 4.27 [★★]
Extend the language of the preceding exercise to include subroutines. In our usage a subroutine is like a procedure, except that it does not return a value and its body is a statement, rather than an expression. Also, add subroutine calls as a new kind of statement and extend the syntax of blocks so that they may be used to declare both procedures and subroutines. How does this affect the denoted and expressed values? What happens if a procedure is referenced in a subroutine call, or vice versa?
Solution is implemented here.
Denoted values does not change, expressed values now contains a subval
variant.
Error will happen if procedure is referenced in a subroutine call, or vice versa.
4.4 MUTABLEPAIRS: A Language with Mutable Pairs
4.4.2 Another Representation ofMutable Pairs
Exercise 4.28 [★★]
Write down the specification rules for the five mutablepair operations.
\[ \dfrac{\eqalign{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} &= (val_1, σ_1) \\ \texttt{(valueof $exp_2$ $ρ$ $σ_1$)} &= (val_2, σ_2)}} {\texttt{(valueof (newpairexp $exp_1$ $exp_2$) $ρ$ $σ_0$)} = (\texttt{(mutpairval (apair $l_1$ $l_2$))}, [l_2 = val_2][l_1 = val_1]σ_2)} \]
\[ \dfrac{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} = (\texttt{(mutpairval (apair $l_1$ $l_2$))}, σ_1)} {\texttt{(valueof (leftexp $exp_1$) $ρ$ $σ_0$)} = (σ_1(l_1), σ_1)} \]
\[ \dfrac{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} = (\texttt{(mutpairval (apair $l_1$ $l_2$))}, σ_1)} {\texttt{(valueof (rightexp $exp_1$) $ρ$ $σ_0$)} = (σ_1(l_2), σ_1)} \]
\[ \dfrac{\eqalign{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} &= (\texttt{(mutpairval (apair $l_1$ $l_2$))}, σ_1) \\ \texttt{(valueof $exp_2$ $ρ$ $σ_1$)} &= (val_2, σ_2)}} {\texttt{(valueof (setleftexp $exp_1$ $exp_2$) $ρ$ $σ_0$)} = (\texttt{(numval 82)}, [l_1 = val_2]σ_2)} \]
\[ \dfrac{\eqalign{\texttt{(valueof $exp_1$ $ρ$ $σ_0$)} &= (\texttt{(mutpairval (apair $l_1$ $l_2$))}, σ_1) \\ \texttt{(valueof $exp_2$ $ρ$ $σ_1$)} &= (val_2, σ_2)}} {\texttt{(valueof (setrightexp $exp_1$ $exp_2$) $ρ$ $σ_0$)} = (\texttt{(numval 83)}, [l_2 = val_2]σ_2)} \]
Exercise 4.29 [★★]
Add arrays to this language. Introduce new operators
newarray
,arrayref
, andarrayset
that create, dereference, and update arrays. This leads to
 ArrVal = (Ref(ExpVal))^{∗}
 ExpVal = Int + Bool + Proc + ArrVal
 DenVal = Ref(ExpVal)
Since the locations in an array are consecutive, use a representation like the second representation above. What should be the result of the following program?
let a = newarray(2,99) p = proc (x) let v = arrayref(x,1) in arrayset(x,1,(v,1)) in begin arrayset(a,1,0); (p a); (p a); arrayref(a,1) end
Here
newarray(2,99)
is intended to build an array of size 2, with each location in the array containing 99.begin
expressions are defined in exercise 4.4. Make the array indices zerobased, so an array of size 2 has indices 0 and 1.
Solution is implemented here.
The result of that program should be 2.
Exercise 4.30 [★★]
Add to the language of exercise 4.29 a procedure
arraylength
, which returns the size of an array. Your procedure should work in constant time. Make sure thatarrayref
andarrayset
check to make sure that their indices are within the length of the array.
Solution is implemented here.
4.5 ParameterPassing Variations
4.5.1 CALLBYREFERENCE
Exercise 4.31 [★]
Write out the specification rules for CALLBYREFERENCE.
Skipped.
Exercise 4.32 [★]
Extend the language CALLBYREFERENCE to have procedures of multiple arguments.
Solution is implemented here.
Exercise 4.33 [★★]
Extend the language CALLBYREFERENCE to support callbyvalue procedures as well.
Solution is implemented here.
Exercise 4.34 [★]
Add a callbyreference version of
let
, calledletref
, to the language. Write the specification and implement it.
Solution is implemented here.
Exercise 4.35 [★★]
We can get some of the benefits of callbyreference without leaving the callbyvalue framework. Extend the language IMPLICITREFS by adding a new expression
Expression ::=
ref
Identifier
refexp (var)
This differs from the language EXPLICITREFS, since references are only of variables. This allows us to write familiar programs such as
swap
within our callbyvalue language. What should be the value of this expression?let a = 3 in let b = 4 in let swap = proc (x) proc (y) let temp = deref(x) in begin setref(x,deref(y)); setref(y,temp) end in begin ((swap ref a) ref b); (a,b) end
Here we have used a version of
let
with multiple declarations (exercise 3.16). What are the expressed and denoted values of this language?
Solution is implemented here.
Here we have used a version of
let
with multiple declarations (exercise 3.16).
No, you have not.
The value of the given expression should be 1.
Expressed values now contains reference values, and denoted values still only contains references.
Exercise 4.36 [★]
Most languages support arrays, in which case array references are generally treated like variable references under callbyreference. If an operand is an array reference, then the location referred to, rather than its contents, is passed to the called procedure. This allows, for example, a swap procedure to be used in commonly occurring situations in which the values in two array elements are to be exchanged. Add array operators like those of exercise 4.29 to the callbyreference language of this section, and extend
valueofoperand
to handle this case, so that, for example, a procedure application like((swap arrayref(a, i)) arrayref(a, j))
will work as expected. What should happen in the case of
((swap arrayref(a, arrayref(a, i))) arrayref(a, j))
?
Solution is implemented here.
((swap arrayref(a, arrayref(a, i))) arrayref(a, j))
will swap the element indexed by the value of arrayref(a, i)
with the element indexed by j
.
Exercise 4.37 [★★]
Callbyvalueresult is a variation on callbyreference. In callbyvalueresult, the actual parameter must be a variable. When a parameter is passed, the formal parameter is bound to a new reference initialized to the value of the actual parameter, just as in callbyvalue. The procedure body is then executed normally. When the procedure body returns, however, the value in the new reference is copied back into the reference denoted by the actual parameter. This may be more efficient than callbyreference because it can improve memory locality. Implement callbyvalueresult and write a program that produces different answers using callbyvalueresult and callbyreference.
Solution is implemented here.
This program produces 4 using callbyvalueresult while it produces 3 using callbyreference.
let f = proc (x)
begin set x = 3;
4
end
in let x = 5
in begin (f x);
x
end
4.5.2 Lazy Evaluation: CALLBYNAME and CALLBYNEED
Exercise 4.38 [★]
The example below shows a variation of exercise 3.25 that works under callbyneed. Does the original program in exercise 3.25 work under callbyneed? What happens if the program below is run under callbyvalue? Why?
let makerec = proc (f) let d = proc (x) (f (x x)) in (f (d d)) in let maketimes4 = proc (f) proc (x) if zero?(x) then 0 else ((f (x,1)), 4) in let times4 = (makerec maketimes4) in (times4 3)
Yes, the original program in exercise 3.25 works under callbyneed.
And the program above will loop infinitely under callbyvalue, because in line 3, (d d)
calls d
with itself, and
when d
is called, it calls its argument x
with x
, where x
is d
itself. So (d d)
leads to another call to
(d d)
which leads to infinite loop.
Exercise 4.39 [★]
In the absence of effects, callbyname and callbyneed always give the same answer. Construct an example in which callbyname and callbyneed give different answers.
let x = 0
in let f = proc (y)
begin y;
y
end
in (f begin set x = (x, 1);
x
end)
The program above should produce 1 in callbyneed and 2 in callbyname.
Exercise 4.40 [★]
Modify
valueofoperand
so that it avoids making thunks for constants and procedures.
Solution is implemented here.
Exercise 4.41 [★★]
Write out the specification rules for callbyname and callbyneed.
Skipped.
Exercise 4.42 [★★]
Add a lazy
let
to the callbyneed interpreter.
Solution is implemented here.
5 ContinuationPassing Interpreters
5.1 A ContinuationPassing Interpreter
5.1.0
Exercise 5.1 [★]
Implement this data type of continuations using the procedural representation.
Solution is implemented here.
Exercise 5.2 [★]
Implement this data type of continuations using a datastructure representation.
Solution is implemented here.
Exercise 5.3 [★]
Add
let2
to this interpreter. Alet2
expression is like alet
expression, except that it defines exactly two variables.
Solution is implemented here.
Exercise 5.4 [★]
Add
let3
to this interpreter. Alet3
expression is like alet
expression, except that it defines exactly three variables.
Solution is implemented here.
Exercise 5.5 [★]
Add lists to the language, as in exercise 3.9.
Solution is implemented here.
Exercise 5.6 [★★]
Add a
list
expression to the language, as in exercise 3.10. As a hint, consider adding two new continuationbuilders, one for evaluating the first element of the list and one for evaluating the rest of the list.
Solution is implemented here.
Exercise 5.7 [★★]
Add multideclaration
let
(exercise 3.16) to this interpreter.
Solution is implemented here.
Exercise 5.8 [★★]
Add multiargument procedures (exercise 3.21) to this interpreter.
Solution is implemented here.
Exercise 5.9 [★★]
Modify this interpreter to implement the IMPLICITREFS language. As a hint, consider including a new continuationbuilder
(setrhscont env var cont)
.
Solution is implemented here.
Exercise 5.10 [★★]
Modify the solution to the previous exercise so that the environment is not kept in the continuation.
Not all environments can be removed from continuations. For example, I cannot think of a way to remove the environment in the continuation of the bound expression.
Solution is implemented here.
Exercise 5.11 [★★]
Add the
begin
expression of exercise 4.4 to the continuationpassing interpreter. Be sure that no call tovalueof
orvalueofrands
occurs in a position that would build control context.
Solution is implemented here.
Exercise 5.12 [★]
Instrument the interpreter of figures 5.4–5.6 to produce output similar to that of the calculation on page 150.
Skipped.
Exercise 5.13 [★]
Translate the definitions of
fact
andfactiter
into the LETREC language. You may add a multiplication operator to the language. Then, using the instrumented interpreter of the previous exercise, compute(fact 4)
and(factiter 4)
. Compare them to the calculations at the beginning of this chapter. Find(* 4 (* 3 (* 2 (fact 1))))
in the trace of(fact 4)
. What is the continuation ofapplyprocedure/k
for this call of(fact 1)
?
The implementation of fact
is:
letrec fact(n) = if zero?(n)
then 1
else *(n, (fact (n, 1)))
in fact
The implementation of factiter
is:
letrec factiteracc(n) = proc (a)
if zero?(n)
then a
else ((factiteracc (n, 1)) *(n, a))
in proc (n)
((factiteracc n) 1)
The continuation of applyprocedure/k
for call of (fact 1)
is:
(multiply2cont (numval 2)
(multiply2cont (numval 3)
(multiply2cont (numval 4)
(endcont))))
Exercise 5.14 [★]
The instrumentation of the preceding exercise produces voluminous output. Modify the instrumentation to track instead only the size of the largest continuation used during the calculation. We measure the size of a continuation by the number of continuationbuilders employed in its construction, so the size of the largest continuation in the calculation on page 150 is 3. Then calculate the values of
fact
andfactiter
applied to several operands. Confirm that the size of the largest continuation used byfact
grows linearly with its argument, but the size of the largest continuation used byfactiter
is a constant.
Skipped.
Exercise 5.15 [★]
Our continuation data type contains just the single constant,
endcont
, and all the other continuationbuilders have a single continuation argument. Implement continuations by representing them as lists, where(endcont)
is represented by the empty list, and each other continuation is represented by a nonempty list whose car contains a distinctive data structure (called frame or activation record) and whose cdr contains the embedded continuation. Observe that the interpreter treats these lists like a stack (of frames).
Solution is implemented here.
Exercise 5.16 [★★]
Extend the continuationpassing interpreter to the language of exercise 4.22. Pass a continuation argument to
resultof
, and make sure that no call toresultof
occurs in a position that grows a control context. Since a statement does not return a value, distinguish between ordinary continuations and continuations for statements; the latter are usually called command continuations. The interface should include a procedureapplycommandcont
that takes a command continuation and invokes it. Implement command continuations both as data structures and as zeroargument procedures.
Solution is implemented here.
5.2 A Trampolined Interpreter
5.2.0
Exercise 5.17 [★]
Modify the trampolined interpreter to wrap
(lambda () ...)
around each call (there’s only one) toapplyprocedure/k
. Does this modification require changing the contracts?
Solution is implemented here.
No, this modification does not require changing the contracts.
Exercise 5.18 [★]
The trampoline systemin figure 5.7 uses a procedural representation of a Bounce. Replace this by a data structure representation.
Solution is implemented here.
Exercise 5.19 [★]
Instead of placing the
(lambda () ...)
around the body ofapplyprocedure/k
, place it around the body ofapplycont
. Modify the contracts to match this change. Does the definition of Bounce need to change? Then replace the procedural representation of Bounce with a datastructure representation, as in exercise 5.18.
Solution is implemented here.
The definition of Bounce need not to change.
Exercise 5.20 [★]
In exercise 5.19, the last bounce before
trampoline
returns a FinalAnswer is always something like(applycont (endcont)
val)
, whereval
is someExpVal
. Optimize your representation of bounces in exercise 5.19 to take advantage of this fact.
Skipped.
Exercise 5.21 [★★]
Implement a trampolining interpreter in an ordinary procedural language. Use a data structure representation of the snapshots as in exercise 5.18, and replace the recursive call to
trampoline
in its own body by an ordinarywhile
or other looping construct.
Skipped.
Exercise 5.22 [★★★]
One could also attempt to transcribe the environmentpassing interpreters of chapter 3 in an ordinary procedural language. Such a transcription would fail in all but the simplest cases, for the same reasons as suggested above. Can the technique of trampolining be used in this situation as well?
I don’t think trampolining can be used in that situation. In the case of continuationpassing interpreters, every call
to valueof
is a tail call, so we can simulate the process using a loop. But in the case of environmentpassing
interpreters, not every call to valueof
is a tail call, so we cannot convert the process using a loop. The
trampolining method will fail in such case.
5.3 An Imperative Interpreter
5.3.0
Exercise 5.23 [★]
What happens if you remove the “goto” line in one of the branches of this interpreter? Exactly how does the interpreter fail?
The interpreter will stop running at the position where the “goto” line should be.
Exercise 5.24 [★]
Devise examples to illustrate each of the complications mentioned above.
Skipped.
Exercise 5.25 [★★]
Registerize the interpreter for multiargument procedures (exercise 3.21).
Solution is implemented here.
Exercise 5.26 [★]
Convert this interpreter to a trampoline by replacing each call to
applyprocedure/k
with(set! pc applyprocedure/k)
and using a driver that looks like(define trampoline (lambda (pc) (if pc (trampoline (pc)) val)))
Solution is implemented here.
Exercise 5.27 [★]
Invent a language feature for which setting the
cont
variable last requires a temporary variable.
Skipped.
Exercise 5.28 [★]
Instrument this interpreter as in exercise 5.12. Since continuations are represented the same way, reuse that code. Verify that the imperative interpreter of this section generates exactly the same traces as the interpreter in exercise 5.12.
Skipped.
Exercise 5.29 [★]
Apply the transformation of this section to
factiter
(page 139).
(define n1 'uninitialized)
(define a 'uninitialized)
(define (factiteracc)
(if (zero? n1)
a
(begin (set! a (* n1 a))
(set! n1 ( n1 1))
(factiteracc))))
(define (factiter n)
(set! n1 n)
(set! a 1)
(factiteracc))
Exercise 5.30 [★★]
Modify the interpreter of this section so that procedures rely on dynamic binding, as in exercise 3.28. As a hint, consider transforming the interpreter of exercise 3.28 as we did in this chapter; it will differ from the interpreter of this section only for those portions of the original interpreter that are different. Instrument the interpreter as in exercise 5.28. Observe that just as there is only one continuation in the state, there is only one environment that is pushed and popped, and furthermore, it is pushed and popped in parallel with the continuation. We can conclude that dynamic bindings have dynamic extent: that is, a binding to a formal parameter lasts exactly until that procedure returns. This is different from lexical bindings, which can persist indefinitely if they wind up in a closure.
Skipped.
Exercise 5.31 [★]
Eliminate the remaining
let
expressions in this code by using additional global registers.
Skipped.
Exercise 5.32 [★★]
Improve your solution to the preceding exercise by minimizing the number of global registers used. You can get away with fewer than 5. You may use no data structures other than those already used by the interpreter.
Skipped.
Exercise 5.33 [★★]
Translate the interpreter of this section into an imperative language. Do this twice: once using zeroargument procedure calls in the host language, and once replacing each zeroargument procedure call by a
goto
. How do these alternatives perform as the computation gets longer?
Skipped.
Exercise 5.34 [★★]
As noted on page 157, most imperative languages make it difficult to do this translation, because they use the stack for all procedure calls, even tail calls. Furthermore, for large interpreters, the pieces of code linked by
goto
’s may be too large for some compilers to handle. Translate the interpreter of this section into an imperative language, circumventing this difficulty by using the technique of trampolining, as in exercise 5.26.
Skipped.
5.4 Exceptions
5.4.0
Exercise 5.35 [★★]
This implementation is inefficient, because when an exception is raised,
applyhandler
must search linearly through the continuation to find a handler. Avoid this search by making thetrycont
continuation available directly in each continuation.
Solution is implemented here.
Exercise 5.36 [★]
An alternative design that also avoids the linear search in
applyhandler
is to use two continuations, a normal continuation and an exception continuation. Achieve this goal by modifying the interpreter of this section to take two continuations instead of one.
Solution is implemented here.
Exercise 5.37 [★]
Modify the defined language to raise an exception when a procedure is called with the wrong number of arguments.
Solution is implemented here.
Exercise 5.38 [★]
Modify the defined language to add a division expression. Raise an exception on division by zero.
Solution is implemented here.
Exercise 5.39 [★★]
So far, an exception handler can propagate the exception by reraising it, or it can return a value that becomes the value of the
try
expression. One might instead design the language to allow the computation to resume from the point at which the exception was raised. Modify the interpreter of this section to accomplish this by running the body of the handler with the continuation from the point at which theraise
was invoked.
Solution is implemented here.
Exercise 5.40 [★★★]
Give the exception handlers in the defined language the ability to either return or resume. Do this by passing the continuation from the
raise
exception as a second argument. This may require adding continuations as a new kind of expressed value. Devise suitable syntax for invoking a continuation on a value.
Solution is implemented here.
Exercise 5.41 [★★★]
We have shown how to implement exceptions using a datastructure representation of continuations. We can’t immediately apply the recipe of section 2.2.3 to get a procedural representation, because we now have two observers:
applyhandler
andapplycont
. Implement the continuations of this section as a pair of procedures: a oneargument procedure representing the action of the continuation underapplycont
, and a zeroargument procedure representing its action underapplyhandler
.
Solution is implemented here.
I had to use a oneargument procedure to represent the action under applyhandler
instead of a zeroargument
procedure.
Exercise 5.42 [★★]
The preceding exercise captures the continuation only when an exception is raised. Add to the language the ability to capture a continuation anywhere by adding the form
letcc
Identifierin
Expression with the specification
(valueof/k (letcc
var body)
ρ cont)
= (valueof/k
body(extendenv
var cont ρ)
cont)
Such a captured continuation may be invoked with
throw
: the expressionthrow
Expressionto
Expression evaluates the two subexpressions. The second expression should return a continuation, which is applied to the value of the first expression. The current continuation of the throw expression is ignored.
Solution is implemented here.
Exercise 5.43 [★★]
Modify
letcc
as defined in the preceding exercise so that the captured continuation becomes a new kind of procedure, so instead of writingthrow
exp_{1}to
exp_{2}, one would write(
exp_{2} exp_{1})
.
Solution is implemented here.
Exercise 5.44 [★★]
An alternative to
letcc
andthrow
of the preceding exercises is to add a single procedure to the language. This procedure, which in Scheme is calledcallwithcurrentcontinuation
, takes a oneargument procedure,p
, and passes top
a procedure that when invoked with one argument, passes that argument to the current continuation,cont
. We could definecallwithcurrentcontinuation
in terms ofletcc
andthrow
as follows:let callwithcurrentcontinuation = proc (p) letcc cont in (p proc (v) throw v to cont) in ...
Add
callwithcurrentcontinuation
to the language. Then write a translator that takes the language withletcc
andthrow
and translates it into the language withoutletcc
andthrow
, but withcallwithcurrentcontinuation
.
Solution is implemented here.
To translate a language with letcc
and throw
into the language without letcc
and throw
, just do the following:
 Translate
letcc
varin
body intocallcc(proc (
var)
body)
;  Translate
throw
exp_{1}to
exp_{2} into(
exp_{2} exp_{1})
.
5.5 Threads
5.5.0
Exercise 5.45 [★]
Add to the language of this section a construct called
yield
. Whenever a thread executes ayield
, it is placed on the ready queue, and the thread at the head of the ready queue is run. When the thread is resumed, it should appear as if the call to yield had returned the number 99.
Solution is implemented here. It is copied from the reference implementation.
Exercise 5.46 [★★]
In the system of exercise 5.45, a thread may be placed on the ready queue either because its time slot has been exhausted or because it chose to yield. In the latter case, it will be restarted with a full time slice. Modify the system so that the ready queue keeps track of the remaining time slice (if any) of each thread, and restarts the thread only with the time it has remaining.
Solution is implemented here.
Exercise 5.47 [★]
What happens if we are left with two subthreads, each waiting for a mutex held by the other subthread?
The two subthreads will deadlock and never be executed.
Exercise 5.48 [★]
We have used a procedural representation of threads. Replace this by a datastructure representation.
Solution is implemented here.
Exercise 5.49 [★]
Do exercise 5.15 (continuations as a stack of frames) for THREADS.
Solution is implemented here.
Exercise 5.50 [★★]
Registerize the interpreter of this section. What is the set of mutually tailrecursive procedures that must be registerized?
Solution is implemented here.
Procedures that must be registerized are applycont
, applyprocedure
, applyunop
, signalmutex
, valueof/k
and
waitformutex
.
Exercise 5.51 [★★★]
We would like to be able to organize our program so that the consumer in figure 5.17 doesn’t have to busywait. Instead, it should be able to put itself to sleep and be awakened when the producer has put a value in the buffer. Either write a program with mutexes to do this, or implement a synchronization operator that makes this possible.
let buffer = 0
in let mut = mutex()
in let producer = proc (n)
letrec wait1(k) = if zero?(k)
then begin set buffer = n;
signal(mut)
end
else begin print((k, 200));
(wait1 (k, 1))
end
in (wait1 5)
in let consumer = proc (d)
begin wait(mut);
buffer
end
in begin wait(mut);
spawn(proc (d)
(producer 44));
print(300);
(consumer 86)
end
Exercise 5.52 [★★★]
Write a program using mutexes that will be like the program in figure 5.21, except that the main thread waits for all three of the subthreads to terminate, and then returns the value of
x
.
let x = 0
in let mut = mutex()
in let incr_x = proc (id)
let mut1 = mutex()
in begin wait(mut1);
spawn(proc (dummy)
begin wait(mut);
set x = (x, 1);
signal(mut);
signal(mut1)
end);
mut1
end
in let mut1 = (incr_x 100)
in let mut2 = (incr_x 200)
in let mut3 = (incr_x 300)
in begin wait(mut1);
wait(mut2);
wait(mut3);
x
end
Exercise 5.53 [★★★]
Modify the thread package to include thread identifiers. Each new thread is associated with a fresh thread identifier. When the child thread is spawned, it is passed its thread identifier as a value, rather than the arbitrary value 28 used in this section. The child’s number is also returned to the parent as the value of the
spawn
expression. Instrument the interpreter to trace the creation of thread identifiers. Check to see that the ready queue contains at most one thread for each thread identifier. How can a child thread know its parent’s identifier? What should be done about the thread identifier of the original program?
Solution is implemented here.
We can pass both the parent’s thread number and the child’s thread number to the child.
Exercise 5.54 [★★]
Add to the interpreter of exercise 5.53 a
kill
facility. Thekill
construct, when given a thread number, finds the corresponding thread on the ready queue or any of the waiting queues and removes it. In addition,kill
should return a true value if the target thread is found and false if the thread number is not found on any queue.
Solution is implemented here.
Exercise 5.55 [★★]
Add to the interpreter of exercise 5.53 an interthread communication facility, in which each thread can send a value to another thread using its thread identifier. A thread can receive messages when it chooses, blocking if no message has been sent to it.
Solution is implemented here.
Exercise 5.56 [★★]
Modify the interpreter of exercise 5.55 so that rather than sharing a store, each thread has its own store. In such a language, mutexes can almost always be avoided. Rewrite the example of this section in this language, without using mutexes.
Skipped.
Exercise 5.57 [★★★]
There are lots of different synchronization mechanisms in your favorite OS book. Pick three and implement them in this framework.
Skipped.
Exercise 5.58 [definitely
★] Go off with your friends and have some pizza, but make sure only one person at a time grabs a piece!
Skipped.
6 ContinuationPassing Style
6.1 Writing Programs in ContinuationPassing Style
6.1.0
Exercise 6.1 [★]
Consider figure 6.2 without
(set! pc fact/k)
in the definition offact/k
and without(set! pc applycont)
in the definition ofapplycont
. Why does the program still work?
Because when fact/k
is called, the value of pc
must be fact/k
, so we don’t need to set pc
to fact/k
in order
to continue computation. Same for applycont
.
Exercise 6.2 [★]
Prove by induction on n that for any g,
(fib/k
n g)
=(
g(fib
n))
.
Base case: if n < 2, (fib/k
n g)
= (
g 1)
= (
g (fib
n))
.
Inductive case: if n ≥ 2,
(fib/k
n g)
= (fib/k (
n 1) (lambda (val1) (fib/k (
n 2) (lambda (val2) (
g (+ val1 val2))))))
= ((lambda (val1) (fib/k (
n 2) (lambda (val2) (
g (+ val1 val2))))) (fib (
n 1)))
(by induction)
= (fib/k (
n 2) (lambda (val2) (
g (+ (fib (
n 1)) val2))))
= ((lambda (val2) (
g (+ (fib (
n 1)) val2))) (fib (
n 2)))
(by induction)
= (
g (+ (fib (
n 1)) (fib (
n 2))))
= (
g (fib
n))
Exercise 6.3 [★]
Rewrite each of the following Scheme expressions in continuationpassing style. Assume that any unknown functions have also been rewritten in CPS.
(lambda (x y) (p (+ 8 x) (q y)))
(lambda (x y u v) (+ 1 (f (g x y) (+ u v))))
(+ 1 (f (g x y) (+ u (h v))))
(zero? (if a (p x) (p y)))
(zero? (if (f a) (p x) (p y)))
(let ((x (let ((y 8)) (p y)))) x)
(let ((x (if a (p x) (p y)))) x)

(lambda (x y cont) (q y (lambda (val) (p (+ 8 x) val cont))))

(lambda (x y u v cont) (g x y (lambda (val1) (f val1 (+ u v) (lambda (val2) (cont (+ 1 val2)))))))

(g x y (lambda (val1) (h v (lambda (val2) (f val1 (+ u val2) (lambda (val3) (+ 1 val3)))))))

(if a (p x zero?) (p y zero?))

(f a (lambda (val) (if val (p x zero?) (p y zero?))))

(let ([y 8]) (p y (lambda (val) (let ([x val]) x))))

(let ([cont (lambda (val) (let ([x val]) x))]) (if a (p x cont) (p y cont)))
Exercise 6.4 [★★]
Rewrite each of the following procedures in continuationpassing style. For each procedure, do this first using a datastructure representation of continuations, then with a procedural representation, and then with the inlined procedural representation. Last, write the registerized version. For each of these four versions, test to see that your implementation is tailrecursive by defining
endcont
by(applycont (endcont) val) = (begin (eopl:printf "End of computation.~%") (eopl:printf "This sentence should appear only once.~%") val)
as we did in chapter 5.
removefirst
(section 1.2.3).listsum
(section 1.3).occursfree?
(section 1.2.4).subst
(section 1.2.5).
Solution is implemented here.
Exercise 6.5 [★]
When we rewrite an expression in CPS, we choose an evaluation order for the procedure calls in the expression. Rewrite each of the preceding examples in CPS so that all the procedure calls are evaluated from right to left.
Skipped.
Exercise 6.6 [★]
How many different evaluation orders are possible for the procedure calls in
(lambda (x y) (+ (f (g x)) (h (j y))))
? For each evaluation order, write a CPS expression that calls the procedures in that order.
There are six different evaluation orders.
(lambda (x y cont)
(g x
(lambda (val1)
(f val1
(lambda (val2)
(j y
(lambda (val3)
(h val3
(lambda (val4)
(cont (+ val2 val4)))))))))))
(lambda (x y cont)
(g x
(lambda (val1)
(j y
(lambda (val2)
(f val1
(lambda (val3)
(h val2
(lambda (val4)
(cont (+ val3 val4)))))))))))
(lambda (x y cont)
(g x
(lambda (val1)
(j y
(lambda (val2)
(h val2
(lambda (val3)
(f val1
(lambda (val4)
(cont (+ val4 val3)))))))))))
(lambda (x y cont)
(j y
(lambda (val1)
(g x
(lambda (val2)
(f val2
(lambda (val3)
(h val1
(lambda (val4)
(cont (+ val3 val4)))))))))))
(lambda (x y cont)
(j y
(lambda (val1)
(g x
(lambda (val2)
(h val1
(lambda (val3)
(f val2
(lambda (val4)
(cont (+ val4 val3)))))))))))
(lambda (x y cont)
(j y
(lambda (val1)
(h val1
(lambda (val2)
(g x
(lambda (val3)
(f val3
(lambda (val4)
(cont (+ val4 val2)))))))))))
Exercise 6.7 [★★]
Write out the procedural and the inlined representations for the interpreter in figures 5.4, 5.5, and 5.6.
Solution is implemented here and here.
Exercise 6.8 [★★★]
Rewrite the interpreter of section 5.4 using a procedural and inlined representation. This is challenging because we effectively have two observers,
applycont
andapplyhandler
. As a hint, consider modifying the recipe on page 6.1 so that we add to each procedure two extra arguments, one representing the behavior of the continuation underapplycont
and one representing its behavior underapplyhandler
.
Solution is implemented here and here.
Exercise 6.9 [★]
What property of multiplication makes this program optimization possible?
The associative property.
Exercise 6.10 [★]
For
listsum
, formulate a succinct representation of the continuations, like the one forfact/k
above.
(define listsum/k
(lambda (loi cont)
(if (null? loi)
cont
(listsum/k (cdr loi)
(+ cont (car loi))))))
6.2 Tail Form
6.2.0
Exercise 6.11 [★]
Complete the interpreter of figure 6.6 by writing
valueofsimpleexp
.
Solution is implemented here. This is copied from the reference implementation.
Exercise 6.12 [★]
Determine whether each of the following expressions is simple.
((f (x,1)),1)
(f ((x,y),1))
if zero?(x) then (x,y) else ((x,y),1)
let x = proc (y) (y x) in (x,3)
let f = proc (x) x in (f 3)
((f (x,1)),1)
is not simple because(f (x,1))
is a procedure call.(f ((x,y),1))
is not simple because(f ((x,y),1))
is a procedure call.if zero?(x) then (x,y) else ((x,y),1)
is simple.let x = proc (y) (y x) in (x,3)
is simple. although(y x)
is procedural call, but it is in a procedure body so that’s OK.let f = proc (x) x in (f 3)
is not simple because(f 3)
is a procedure call.
Exercise 6.13 [★]
Translate each of these expressions in CPSIN into continuationpassing style using the CPS recipe on page 200 above. Test your transformed programs by running them using the interpreter of figure 6.6. Be sure that the original and transformed versions give the same answer on each input.
removeall
.letrec removeall(n,s) = if null?(s) then emptylist else if number?(car(s)) then if equal?(n,car(s)) then (removeall n cdr(s)) else cons(car(s), (removeall n cdr(s))) else cons((removeall n car(s)), (removeall n cdr(s)))
occursin?
.letrec occursin?(n,s) = if null?(s) then 0 else if number?(car(s)) then if equal?(n,car(s)) then 1 else (occursin? n cdr(s)) else if (occursin? n car(s)) then 1 else (occursin? n cdr(s))
remfirst
. This usesoccursin?
from the preceding example.letrec remfirst(n,s) = letrec loop(s) = if null?(s) then emptylist else if number?(car(s)) then if equal?(n,car(s)) then cdr(s) else cons(car(s),(loop cdr(s))) else if (occursin? n car(s)) then cons((remfirst n car(s)), cdr(s)) else cons(car(s), (remfirst n cdr(s))) in (loop s)
depth
.letrec depth(s) = if null?(s) then 1 else if number?(car(s)) then (depth cdr(s)) else if less?(add1((depth car(s))), (depth cdr(s))) then (depth cdr(s)) else add1((depth car(s)))
depthwithlet
.letrec depth(s) = if null?(s) then 1 else if number?(car(s)) then (depth cdr(s)) else let dfirst = add1((depth car(s))) drest = (depth cdr(s)) in if less?(dfirst,drest) then drest else dfirst
map
.letrec map(f, l) = if null?(l) then emptylist else cons((f car(l)), (map f cdr(l))) square(n) = *(n,n) in (map square list(1,2,3,4,5))
fnlrgtn
. This procedure takes an nlist, like an slist (page 9), but with numbers instead of symbols, and a numbern
and returns the first number in the list (in lefttoright order) that is greater thann
. Once the result is found, no further elements in the list are examined. For example,finds 7.(fnlrgtn list(1,list(3,list(2),7,list(9))) 6)
every
. This procedure takes a predicate and a list and returns a true value if and only if the predicate holds for each list element.letrec every(pred, l) = if null?(l) then 1 else if (pred car(l)) then (every pred cdr(l)) else 0 in (every proc(n) greater?(n,5) list(6,7,8,9))
Skipped.
Exercise 6.14 [★]
Complete the interpreter of figure 6.6 by supplying definitions for
valueofprogram
andapplycont
.
Solution is implemented here. This is copied from the reference implementation.
Exercise 6.15 [★]
Observe that in the interpreter of the preceding exercise, there is only one possible value for
cont
. Use this observation to remove thecont
argument entirely.
Solution is implemented here.
Exercise 6.16 [★]
Registerize the interpreter of figure 6.6.
Solution is implemented here.
Exercise 6.17 [★]
Trampoline the interpreter of figure 6.6.
Solution is implemented here.
Exercise 6.18 [★★]
Modify the grammar of CPSOUT so that a simple
diffexp
orzero?exp
can have only a constant or variable as an argument. Thus in the resulting languagevalueofsimpleexp
can be made nonrecursive.
Solution is implemented here.
Exercise 6.19 [★★]
Write a Scheme procedure
tailform?
that takes the syntax tree of a program in CPSIN, expressed in the grammar of figure 6.3, and determines whether the same string would be in tail form according to the grammar of figure 6.5.
Solution is implemented here.
(define all
(lambda (pred items)
(let loop ([items items])
(or (null? items)
(and (pred (car items))
(loop (cdr items)))))))
(define simpleexp?
(lambda (exp)
(cases expression exp
[constexp (num) #t]
[diffexp (exp1 exp2) (and (simpleexp? exp1)
(simpleexp? exp2))]
[zero?exp (exp1) (simpleexp? exp1)]
[varexp (var) #t]
[procexp (vars body) (tailformexp? body)]
[else #f])))
(define tailformexp?
(lambda (exp)
(cases expression exp
[constexp (num) #t]
[diffexp (exp1 exp2) (and (simpleexp? exp1)
(simpleexp? exp2))]
[zero?exp (exp1) (simpleexp? exp1)]
[ifexp (exp1 exp2 exp3) (and (simpleexp? exp1)
(tailformexp? exp2)
(tailformexp? exp3))]
[varexp (var) #t]
[letexp (var exp1 body) (and (simpleexp? exp1)
(tailformexp? body))]
[letrecexp (pnames bvarss pbodies letrecbody) (and (all tailformexp? pbodies)
(tailformexp? letrecbody))]
[procexp (vars body) (tailformexp? body)]
[callexp (rator rands) (and (simpleexp? rator) (all simpleexp? rands))])))
(define tailform?
(lambda (pgm)
(cases program pgm
[aprogram (exp) (tailformexp? exp)])))
6.3 Converting to ContinuationPassing Style
6.3.0
Exercise 6.20 [★]
Our procedure
cpsofexps
causes subexpressions to be evaluated from left to right. Modifycpsofexps
so that subexpressions are evaluated from right to left.
Solution is implemented here.
Exercise 6.21 [★]
Modify
cpsofcallexp
so that the operands are evaluated from left to right, followed by the operator.
Solution is implemented here.
Exercise 6.22 [★]
Sometimes, when we generate
(
K simp)
, K is already aprocexp
. So instead of generating(proc (var1) ... simp)
we could generate
let var1 = simp in ...
This leads to CPS code with the property that it never contains a subexpression of the form
(proc (var) exp1 simp)
unless that subexpression was in the original expression.
Modify
makesendtocont
to generate this better code. When does the new rule apply?
Solution is implemented here.
The new rule applies when transform a expression on a operand position.
Exercise 6.23 [★★]
Observe that our rule for
if
makes two copies of the continuation K, so in a nestedif
the size of the transformed program can grow exponentially. Run an example to confirm this observation. Then show how this may be avoided by changing the transformation to bind a fresh variable toK
.
Solution is implemented here.
Exercise 6.24 [★★]
Add lists to the language (exercise 3.10). Remember that the arguments to a list are not in tail position.
Solution is implemented here.
Exercise 6.25 [★★]
Extend CPSIN so that a
let
expression can declare an arbitrary number of variables (exercise 3.16).
Solution is implemented here.
Exercise 6.26 [★★]
A continuation variable introduced by
cpsofexps
will only occur once in the continuation. Modifymakesendtocont
so that instead of generatinglet var1 = simp1 in T
as in exercise 6.22, it generates T[simp_{1}/var_{1}], where the notation E_{1}[E_{2}/var] means expression E_{1} with every free occurrence of the variable var replaced by E_{2}.
Solution is implemented here.
Exercise 6.27 [★★]
As it stands,
cpsofletexp
will generate a uselesslet
expression. (Why?) Modify this procedure so that the continuation variable is the same as the let variable. Then if exp_{1} is nonsimple,
(cpsofexp <<let
var_{1}=
exp_{1}in
exp_{2}>>
K)
= (cpsofexp
exp_{1}<<proc (
var_{1}) (cpsofexp
exp_{2} K)>>
Solution is implemented here.
Exercise 6.28 [★]
Food for thought: imagine a CPS transformer for Scheme programs, and imagine that you apply it to the first interpreter from chapter 3. What would the result look like?
It would look like a continuationpassing interpreter.
Exercise 6.29 [★★]
Consider this variant of
cpsofexps
.(define cpsofexps (lambda (exps builder) (let cpsofrest ((exps exps) (acc '())) cpsofrest : Listof(InpExp) × Listof(SimpleExp) → TfExp (cond ((null? exps) (builder (reverse acc))) ((inpexpsimple? (car exps)) (cpsofrest (cdr exps) (cons (cpsofsimpleexp (car exps)) acc))) (else (let ((var (freshidentifier 'var))) (cpsofexp (car exps) (cpsprocexp (list var) (cpsofrest (cdr exps) (cons (cpsofsimpleexp (varexp var)) acc))))))))))
Why is this variant of cpsofexp more efficient than the one in figure 6.8?
Because this variant only scan exps
once without looking back, the original one will scan exps
multiple times if
there are multiple nonsimple expressions in exps
.
Exercise 6.30 [★★]
A call to
cpsofexps
with a list of expressions of length one can be simplified as follows:
(cpsofexps (list
exp)
builder)
=(cpsofexp/ctx
exp(lambda (simp) (
builder(list simp))))
where
cpsofexp/ctx : InpExp × (SimpleExp → TfExp) → TfExp
(define cpsofexp/ctx (lambda (exp context) (if (inpexpsimple? exp) (context (cpsofsimpleexp exp)) (let ((var (freshidentifier 'var))) (cpsofexp exp (cpsprocexp (list var) (context (cpsvarexp var))))))))
Thus, we can simplify occurrences of
(cpsofexps (list ...))
, since the number of arguments to list is known. Therefore the definition of, for example,cpsofdiffexp
could be defined withcpsofexp/ctx
instead of withcpsofexps
.(define cpsofdiffexp (lambda (exp1 exp2 kexp) (cpsofexp/ctx exp1 (lambda (simp1) (cpsofexp/ctx exp2 (lambda (simp2) (makesendtocont kexp (cpsdiffexp simp1 simp2))))))))
For the use of
cpsofexps
incpsofcallexp
, we can usecpsofexp/ctx
on therator
, but we still needcpsofexps
for the rands. Remove all other occurrences ofcpsofexps
from the translator.
Solution is implemented here.
Exercise 6.31 [★★★]
Write a translator that takes the output of
cpsofprogram
and produces an equivalent program in which all the continuations are represented by data structures, as in chapter 5. Represent data structures like those constructed usingdefinedatatype
as lists. Since our language does not have symbols, you can use an integer tag in the car position to distinguish the variants of a data type.
Skipped.
Exercise 6.32 [★★★]
Write a translator like the one in exercise 6.31, except that it represents all procedures by data structures.
Skipped.
Exercise 6.33 [★★★]
Write a translator that takes the output from exercise 6.32 and converts it to a register program like the one in figure 6.1.
Skipped.
Exercise 6.34 [★★]
When we convert a program to CPS, we do more than produce a program in which the control contexts become explicit. We also choose the exact order in which the operations are done, and choose names for each intermediate result. The latter is called sequentialization. If we don’t care about obtaining iterative behavior, we can sequentialize a program by converting it to Anormal form or ANF. Here’s an example of a program in ANF.
(define fib/anf (lambda (n) (if (< n 2) 1 (let ((val1 (fib/anf ( n 1)))) (let ((val2 (fib/anf ( n 2)))) (+ val1 val2))))))
Whereas a program in CPS sequentializes computation by passing continuations that name intermediate results, a program in ANF sequentializes computation by using
let
expressions that name all of the intermediate results.Retarget
cpsofexp
so that it generates programs in ANF instead of CPS. (For conditional expressions occurring in nontail position, use the ideas in exercise 6.23.) Then, show that applying the revisedcpsofexp
to, e.g., the definition offib
yields the definition offib/anf
. Finally, show that given an input program which is already in ANF, your translator produces the same program except for the names of bound variables.
Solution is implemented here.
Exercise 6.35 [★]
Verify on a few examples that if the optimization of exercise 6.27 is installed, CPStransforming the output of your ANF transformer (exercise 6.34) on a program yields the same result as CPStransforming the program.
Skipped.
6.4 Modeling Computational Effects
6.4.0
Exercise 6.36 [★★]
Add a
begin
expression (exercise 4.4) to CPSIN. You should not need to add anything to CPSOUT.
Solution is implemented here.
Exercise 6.37 [★★★]
Add implicit references (section 4.3) to CPSIN. Use the same version of CPSOUT, with explicit references, and make sure your translator inserts allocation and dereference where necessary. As a hint, recall that in the presence of implicit references, a
varexp
is no longer simple, since it reads from the store.
Solution is implemented here.
Exercise 6.38 [★★★]
If a variable never appears on the lefthand side of a
set
expression, then it is immutable, and could be treated as simple. Extend your solution to the preceding exercise so that all such variables are treated as simple.
Solution is implemented here.
Exercise 6.39 [★]
Implement
letcc
andthrow
in the CPS translator.
Solution is implemented here.
Exercise 6.40 [★★]
Implement
try/catch
andthrow
from section 5.4 by adding them to the CPS translator. You should not need to add anything to CPSOUT. Instead, modifycpsofexp
to take two continuations: a success continuation and an error continuation.
Solution is implemented here.
7 Types
7.1 Values and Their Types
7.1.0
Exercise 7.1 [★]
Below is a list of closed expressions. Consider the value of each expression. For each value, what type or types does it have? Some of the values may have no type that is describable in our type language.
proc (x) (x,3)
proc (f) proc (x) ((f x), 1)
proc (x) x
proc (x) proc (y) (x y)
proc (x) (x 3)
proc (x) (x x)
proc (x) if x then 88 else 99
proc (x) proc (y) if x then y else 99
(proc (p) if p then 88 else 99 33)
(proc (p) if p then 88 else 99 proc (z) z)
proc (f) proc (g) proc (p) proc (x) if (p (f x)) then (g 1) else ((f x),1)
proc (x) proc(p) proc (f) if (p x) then (x,1) else (f p)
proc (f) let d = proc (x) proc (z) ((f (x x)) z) in proc (n) ((f (d d)) n)

proc (x) (x,3)
int > int

proc (f) proc (x) ((f x), 1)
(
t> int) > (
t> int)

proc (x) x
t
>
t 
proc (x) proc (y) (x y)
(
t_{1}>
t_{2}) > (
t_{1}>
t_{2})

proc (x) (x 3)
(int >
t) >
t 
proc (x) (x x)
Not describable

proc (x) if x then 88 else 99
bool > int

proc (x) proc (y) if x then y else 99
bool > (int > int)

(proc (p) if p then 88 else 99 33)
Type error

(proc (p) if p then 88 else 99 proc (z) z)
Type error

proc (f) proc (g) proc (p) proc (x) if (p (f x)) then (g 1) else ((f x),1)
(
t> int) > ((int > int) > ((int > bool) > (
t> int)))

proc (x) proc(p) proc (f) if (p x) then (x,1) else (f p)
int > ((int > bool) > (((int > bool) > int) > int))

proc (f) let d = proc (x) proc (z) ((f (x x)) z) in proc (n) ((f (d d)) n)
((
t_{1}>
t_{2}) > (
t_{1}>
t_{2})) > (
t_{1}>
t_{2})
(Not sure about this one)
Exercise 7.2 [★★]
Are there any expressed values that have exactly two types according to definition 7.1.1?
No, I don’t think so.
Exercise 7.3 [★★]
For the language LETREC, is it decidable whether an expressed value val is of type t?
Not sure about this one.
7.2 Assigning a Type to an Expression
7.2.0
Exercise 7.4 [★]
Using the rules of this section, write derivations, like the one on page 5, that assign types for
proc (x) x
andproc (x) proc (y) (x y)
. Use the rules to assign at least two types for each of these terms. Do the values of these expressions have the same types?
\[ \dfrac{\texttt{(typeof «x» $[\texttt{x}=t]tenv$)} = t} {\texttt{(typeof «proc (x) x» $tenv$)} = \texttt{($t$ > $t$)}} \]
\[ \dfrac{\dfrac{\dfrac{\eqalign{\texttt{(typeof «x» $[\texttt{y}=t_1][\texttt{x}=\texttt{($t_1$ > $t_2$)}]tenv$)} &= \texttt{($t_1$ > $t_2$)} \\ \texttt{(typeof «y» $[\texttt{y}=t_1][\texttt{x}=\texttt{($t_1$ > $t_2$)}]tenv$)} &= t_1}} {\texttt{(typeof «(x y)» $[\texttt{y}=t_1][\texttt{x}=\texttt{($t_1$ > $t_2$)}]tenv$)} = t_2}} {\texttt{(typeof «proc (y) (x y)» $[\texttt{x}=\texttt{($t_1$ > $t_2$)}]tenv$)} = \texttt{($t_1$ > $t_2$)}}} {\texttt{(typeof «proc (x) proc (y) (x y)» $tenv$)} = \texttt{($t_1$ > $t_2$) > ($t_1$ > $t_2$)}} \]
The values of these expressions do not necessarily have the same types. According to the actual type of t, the result type may be different.
CHECKED: A TypeChecked Language
7.3.1 The Checker
Exercise 7.5 [★★]
Extend the checker to handle multiple
let
declarations, multiargument procedures, and multipleletrec
declarations. You will need to add types of the form(
t_{1}*
t_{2}* ... *
t_{n}>
t)
to handle multiargument procedures.
Solution is implemented here.
Exercise 7.6 [★]
Extend the checker to handle assignments (section 4.3).
Solution is implemented here.
Exercise 7.7 [★]
Change the code for checking an
ifexp
so that if the test expression is not a boolean, the other expressions are not checked. Give an expression for which the new version of the checker behaves differently from the old version.
Solution is implemented here.
This expression behaves differently in the new version of checker:
if 1 then (zero?(1), 4) else 2
Exercise 7.8 [★★]
Add
pairof
types to the language. Say that a value is of typepairof
t_{1}*
t_{2} if and only if it is a pair consisting of a value of type t_{1} and a value of type t_{2}. Add to the language the following productions:Type ::=
pairof
Type*
Type
pairtype (ty1 ty2)
Expression ::=
newpair (
Expression,
Expression)
pairexp (exp1 exp2)
Expression ::=
unpair
Identifier Identifier=
Expression
in
Expression
unpairexp (var1 var2 exp body)
A
pair
expression creates a pair; anunpair
expression (like exercise 3.18) binds its two variables to the two parts of the expression; the scope of these variables isbody
. The typing rules forpair
andunpair
are:\[ \dfrac{\eqalign{\texttt{(typeof $e_1$ $tenv$)} &= t_1 \\ \texttt{(typeof $e_1$ $tenv$)} &= t_2}} {\texttt{(typeof (pairexp $e_1$ $e_2$) $tenv$)} = \texttt{pairof $t_1$ * $t_2$}} \]
\[ \dfrac{\eqalign{ \texttt{(typeof $e_{pair}$ $tenv$)} &= \texttt{pairof $t_1$ $t_2$} \\ \texttt{(typeof $e_{body}$ $[var_1=t_1][var_2=t_2]tenv$)} &= t_{body}}} {\texttt{(typeof (unpairexp $var_1$ $var_2$ $e_1$ $e_{body}$) $tenv$)} = t_{body}} \]
Extend CHECKED to implement these rules. In
typetoexternalform
, produce the list(pairof
t_{1} t_{2})
for a pair type.
Solution is implemented here.
Exercise 7.9 [★★]
Add
listof
types to the language, with operations similar to those of exercise 3.9. A value is of typelistof
t if and only if it is a list and all of its elements are of type t. Extend the language with the productionsType ::=
listof
Type
listtype (ty)
Expression ::=
list (
Expression {,
Expression}^{∗})
listexp (exp1 exps)
Expression ::=
cons (
Expression,
Expression)
consexp (exp1 exp2)
Expression ::=
null? (
Expression)
nullexp (exp1)
Expression ::=
emptylist [
Type]
emptylistexp (ty)
with types given by the following four rules:
\[ \dfrac{\eqalign{\texttt{(typeof $e_1$ $tenv$)} &= t \\ \texttt{(typeof $e_2$ $tenv$)} &= t \\ &⋮ \\ \texttt{(typeof $e_n$ $tenv$)} &= t}} {\texttt{(typeof (listexp $e_1$ ($e_2$ $…$ $e_n$)) $tenv$)} = \texttt{listof $t$}} \]
\[ \dfrac{\eqalign{\texttt{(typeof $e_1$ $tenv$)} &= t \\ \texttt{(typeof $e_2$ $tenv$)} &= \texttt{listof $t$}}} {\texttt{(typeof «cons($e_1$, $e_2$)» $tenv$)} = \texttt{listof $t$}} \]
\[ \dfrac{\texttt{(typeof $e_1$ $tenv$)} = \texttt{listof $t$}} {\texttt{(typeof «null?($e_1$)» $tenv$)} = \texttt{bool}} \]
\[ \texttt{(typeof «emptylist[$t$]» $tenv$)} = \texttt{listof $t$} \]
Although
cons
is similar topair
, it has a very different typing rule.Write similar rules for
car
andcdr
, and extend the checker to handle these as well as the other expressions. Use a trick similar to the one in exercise 7.8 to avoid conflict withproctypeexp
. These rules should guarantee thatcar
andcdr
are applied to lists, but they should not guarantee that the lists be nonempty. Why would it be unreasonable for the rules to guarantee that the lists be nonempty? Why is the type parameter inemptylist
necessary?
Solution is implemented here.
Because a list may be dynamic generated, we have no way to know the length of the list statically, so we can not guarantee a list is nonempty.
Because our implementation must know the exact type of every expression. If we omit the type parameter, we couldn’t
determine the type the expression emptylist
.
Exercise 7.10 [★★]
Extend the checker to handle EXPLICITREFS. You will need to do the following:
 Add to the type system the types
refto
t, where t is any type. This is the type of references to locations containing a value of type t. Thus, if e is of type t,(newref
e)
is of typerefto
t. Add to the type system the type
void
. This is the type of the value returned bysetref
. You can’t apply any operation to a value of typevoid
, so it doesn’t matter what valuesetref
returns. This is an example of types serving as an informationhiding mechanism. Write down typing rules for
newref
,deref
, andsetref
. Implement these rules in the checker.
Solution is implemented here.
Exercise 7.11 [★★]
Extend the checker to handle MUTABLEPAIRS.
Solution is implemented here.
7.4 INFERRED: A Language with Type Inference
7.4.0
Exercise 7.12 [★]
Using the methods in this section, derive types for each of the expressions in exercise 7.1, or determine that no such type exists. As in the other examples of this section, assume there is a
?
attached to each bound variable.
Turns out most of my solutions are correct, except for the last one. I think the last one
proc (f)
let d = proc (x)
proc (z) ((f (x x)) z)
in proc (n) ((f (d d)) n)
is a fixedpoint combinator, and should have the type
((
t_{1} >
t_{2}) > (
t_{1} >
t_{2})) > (
t_{1} >
t_{2})
.
But due to our limited type system, we couldn’t assign a concrete type to d
or x
, so we failed to infer the who
program.
In fact, the following program in Typed Racket type checks.
#lang typed/racket/base
(: fix (∀ (𝑡₁ 𝑡₂) ((𝑡₁ → 𝑡₂) → (𝑡₁ → 𝑡₂)) → (𝑡₁ → 𝑡₂)))
(define fix
(λ (f)
(let ([d : ((Rec r (r → (𝑡₁ → 𝑡₂))) → (𝑡₁ → 𝑡₂))
(λ (x)
(λ (z)
((f (x x)) z)))])
(λ (n)
((f (d d)) n)))))
Exercise 7.13 [★]
Write down a rule for doing type inference for
let
expressions. Using your rule, derive types for each of the following expressions, or determine that no such type exists.
let x = 4 in (x 3)
let f = proc (z) z in proc (x) ((f x), 1)
let p = zero?(1) in if p then 88 else 99
let p = proc (z) z in if p then 88 else 99
\[ \begin{alignat}{2} \texttt{(letexp $var$ $e_1$ $body$)} &: & t_{var} &= t_{e_1} \\ & & t_{body} &= t_\texttt{(letexp $var$ $e_1$ $body$)} \end{alignat} \]

let x = 4 in (x 3)
Type error.

let f = proc (z) z in proc (x) ((f x), 1)
int > int

let p = zero?(1) in if p then 88 else 99
int

let p = proc (z) z in if p then 88 else 99
Type error.
Exercise 7.14 [★]
What is wrong with this expression?
letrec ? even(odd : ?) = proc (x : ?) if zero?(x) then 1 else (odd (x,1)) in letrec ? odd(x : bool) = if zero?(x) then 0 else ((even odd) (x,1)) in (odd 13)
The parameter x
of odd
should be of type int
.
Exercise 7.15 [★★]
Write down a rule for doing type inference for a
letrec
expression. Your rule should handle multiple declarations in aletrec
. Using your rule, derive types for each of the following expressions, or determine that no such type exists:
letrec ? f (x : ?) = if zero?(x) then 0 else ((f (x,1)), 2) in f
letrec ? even (x : ?) = if zero?(x) then 1 else (odd (x,1)) ? odd (x : ?) = if zero?(x) then 0 else (even (x,1)) in (odd 13)
letrec ? even (odd : ?) = proc (x) if zero?(x) then 1 else (odd (x,1)) in letrec ? odd (x : ?) = if zero?(x) then 0 else ((even odd) (x,1)) in (odd 13)
\[ \begin{alignat}{2} \texttt{(letrecexp $pnames$ $bvars$ $pbodies$ $letrecbody$)} &: & t_{pname_1} &= \texttt{($t_{bvar_1}$ > $t_{pbody_1}$)} \\ & & t_{pname_2} &= \texttt{($t_{bvar_2}$ > $t_{pbody_2}$)} \\ & & &⋮ \\ & & t_{pname_n} &= \texttt{($t_{bvar_n}$ > $t_{pbody_n}$)} \\ & & t_{letrecbody} &= t_\texttt{(letrecexp $pnames$ $bvars$ $pbodies$ $letrecbody$)} \end{alignat} \]

letrec ? f (x : ?) = if zero?(x) then 0 else ((f (x,1)), 2) in f
(int > int)

letrec ? even (x : ?) = if zero?(x) then 1 else (odd (x,1)) ? odd (x : ?) = if zero?(x) then 0 else (even (x,1)) in (odd 13)
int

letrec ? even (odd : ?) = proc (x : ?) if zero?(x) then 1 else (odd (x,1)) in letrec ? odd (x : ?) = if zero?(x) then 0 else ((even odd) (x,1)) in (odd 13)
int
Exercise 7.16 [★★★]
Modify the grammar of INFERRED so that missing types are simply omitted, rather than marked with
?
.
Solution is implemented here.
7.4.1 Substitutions
Exercise 7.17 [★★]
In our representation,
extendsubst
may do a lot of work if σ is large. Implement an alternate representation in whichextendsubst
is implemented as(define extendsubst (lambda (subst tvar ty) (cons (cons tvar ty) subst)))
and the extra work is shifted to
applysubsttotype
, so that the property t(σ[tv = t′]) = (tσ)[tv = t′] is still satisfied. For this definition ofextendsubst
, is the nooccurrence invariant needed?
Solution is implemented here.
The nooccurrence invariant is not needed for this definition of extendsubst
.
Exercise 7.18 [★★]
Modify the implementation in the preceding exercise so that
applysubsttotype
computes the substitution for any type variable at most once.
Solution is implemented here.
7.4.2 The Unifier
Exercise 7.19 [★]
We wrote: “If
ty1
is an unknown type, then the nooccurrence invariant tells us that it is not bound in the substitution.” Explain in detail why this is so.
Because ty1
is the result type after applying the substitution, if it is an unknown type, either it is not bound in
the substitution, or it is on the right hand side of the substitution. Since the nooccurrence invariant forbids bounded
variable occurs on the right hand side of the substitution, ty1
is not bound in the substitution.
Exercise 7.20 [★★]
Modify the unifier so that it calls
applysubsttotype
only on type variables, rather than on its arguments.
Solution is implemented here.
Exercise 7.21 [★★]
We said the substitution is like a store. Implement the unifier, using the representation of substitutions from exercise 7.17, and keeping the substitution in a global Scheme variable, as we did in figures 4.1 and 4.2.
Solution is implemented here.
Exercise 7.22 [★★]
Refine the implementation of the preceding exercise so that the binding of each type variable can be obtained in constant time.
The best I can do is linear time look up, I think I’ll need hash table to implement constant time look up. Still, in my implementation, faster look up time is at the cost of slower extension.
Solution is implemented here.
7.4.3 Finding the Type of an Expression
Exercise 7.23 [★★]
Extend the inferencer to handle pair types, as in exercise 7.8.
Solution is implemented here.
Exercise 7.24 [★★]
Extend the inferencer to handle multiple
let
declarations, multiargument procedures, and multipleletrec
declarations.
Solution is implemented here.
Exercise 7.25 [★★]
Extend the inferencer to handle list types, as in exercise 7.9. Modify the language to use the production
Expression ::=
emptylist
instead of
Expression ::=
emptylist_
TypeAs a hint, consider creating a type variable in place of the missing
_
t.
Solution is implemented here.
Exercise 7.26 [★★]
Extend the inferencer to handle EXPLICITREFS, as in exercise 7.10.
Solution is implemented here.
Exercise 7.27 [★★]
Rewrite the inferencer so that it works in two phases. In the first phase it should generate a set of equations, and in the second phase, it should repeatedly call
unify
to solve them.
Solution is implemented here.
Exercise 7.28 [★★]
Our inferencer is very useful, but it is not powerful enough to allow the programmer to define procedures that are polymorphic, like the polymorphic primitives
pair
orcons
, which can be used at many types. For example, our inferencer would reject the programlet f = proc (x : ?) x in if (f zero?(0)) then (f 11) else (f 22)
even though its execution is safe, because
f
is used both at type(bool > bool)
and at type(int > int)
. Since the inferencer of this section is allowed to find at most one type forf
, it will reject this program.For a more realistic example, one would like to write programs like
letrec ? map (f : ?) = letrec ? foo (x : ?) = if null?(x) then emptylist else cons((f car(x)), ((map f) cdr(x))) in foo in letrec ? even (y : ?) = if zero?(y) then zero?(0) else if zero?((y,1)) then zero?(1) else (even (y,2)) in pair(((map proc(x : int)(x,1)) cons(3,cons(5,emptylist))), ((map even) cons(3,cons(5,emptylist))))
This expression uses
map
twice, once producing a list ofint
s and once producing a list ofbool
s. Therefore it needs two different types for the two uses. Since the inferencer of this section will find at most one type formap
, it will detect the clash betweenint
andbool
and reject the program.One way to avoid this problem is to allow polymorphic values to be introduced only by
let
, and then to treat(letexp
var e_{1} e_{2})
differently from(callexp (procexp
var e_{2})
e_{1})
for typechecking purposes.Add polymorphic bindings to the inferencer by treating
(letexp var
e_{1} e_{2})
like the expression obtained by substituting e_{1} for each free occurrence ofvar
in e_{2}. Then, from the point of view of the inferencer, there are many different copies of e_{1} in the body of thelet
, so they can have different types, and the programs above will be accepted.
Solution is implemented here.
Exercise 7.29 [★★★]
The type inference algorithm suggested in the preceding exercise will analyze e_{1} many times, once for each of its occurrences in e_{2}. Implement Milner’s Algorithm W, which analyzes e_{1} only once.
Skipped.
Exercise 7.30 [★★★]
The interaction between polymorphism and effects is subtle. Consider a program starting
let p = newref(proc (x : ?) x) in ...
 Finish this program to produce a program that passes the polymorphic inferencer, but whose evaluation is not safe according to the definition at the beginning of the chapter.
 Avoid this difficulty by restricting the righthand side of a let to have no effect on the store. This is called the value restriction.
Skipped.