Structure and Interpretation of Computer Programs by Harold Abelson and
Gerald Jay Sussman is licensed under a Creative Commons
Attribution-ShareAlike 3.0 Unported License.
Based on a work at mitpress.mit.edu.
;;------------------------------[ Oppgaver ]------------------------------;;
Kap. 1: 4 5 6 9 30 31 32 34 41 42 43 44
Kap. 2: 2 3 17 18 20 21 22 23 24 25 26 27 28 29 30 31 32 33 36 37 41 42 43
53 54 55 59 60 61 62 63 64 65 66 67 68 69 70 71 72
Kap. 3: 1 2 3 4 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 23 24 25 26 27 38
50 51 52 53 54 55 56 57 66 67 68 69
Kap. 4: 1 2 3 4 5 6 7 8 9 10 11 12 25 26 27 28 29
;;------------------------------------------------------------------------;;
;;----------------------------[ Exercise 1.4 ]----------------------------;;
Observe that our model of evaluation allows for combinations whose operators
are compound expressions. Use this observation to describe the behavior of
the following procedure:
(define (a-plus-abs-b a b) ((if (> b 0) + -) a b))
;;----------------------------[ Exercise 1.5 ]----------------------------;;
Ben Bitdiddle has invented a test to determine whether the interpreter he is
faced with is using applicative-order evaluation or normal-order
evaluation. He defines the following two procedures:
(define (p) (p))
(define (test x y) (if (= x 0) 0 y))
Then he evaluates the expression
(test 0 (p))
What behavior will Ben observe with an interpreter that uses
applicative-order evaluation? What behavior will he observe with an
interpreter that uses normal-order evaluation? Explain your answer. (Assume
that the evaluation rule for the special form if is the same whether the
interpreter is using normal or applicative order: The predicate expression
is evaluated first, and the result determines whether to evaluate the
consequent or the alternative expression.)
;;----------------------------[ Exercise 1.6 ]----------------------------;;
Alyssa P. Hacker doesn't see why if needs to be provided as a special
form. ``Why can't I just define it as an ordinary procedure in terms of
cond?'' she asks. Alyssa's friend Eva Lu Ator claims this can indeed be
done, and she defines a new version of if:
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
Eva demonstrates the program for Alyssa:
(new-if (= 2 3) 0 5)
5
(new-if (= 1 1) 0 5)
0
Delighted, Alyssa uses new-if to rewrite the square-root program:
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
What happens when Alyssa attempts to use this to compute square roots?
Explain.
;;----------------------------[ Exercise 1.9 ]----------------------------;;
Each of the following two procedures defines a method for adding two
positive integers in terms of the procedures inc, which increments its
argument by 1, and dec, which decrements its argument by 1.
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
Using the substitution model, illustrate the process generated by each
procedure in evaluating (+ 4 5). Are these processes iterative or recursive?
;;----------------------------[ Exercise 1.30 ]---------------------------;;
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
The sum procedure above generates a linear recursion. The procedure can be
rewritten so that the sum is performed iteratively. Show how to do this by
filling in the missing expressions in the following definition:
(define (sum term a next b)
(define (iter a result)
(if
(iter )))
(iter ))
;;----------------------------[ Exercise 1.31 ]---------------------------;;
a. The sum procedure is only the simplest of a vast number of similar
abstractions that can be captured as higher-order procedures.51 Write an
analogous procedure called product that returns the product of the values of
a function at points over a given range. Show how to define factorial in
terms of product. Also use product to compute approximations to using the
formula52
b. If your product procedure generates a recursive process, write one that
generates an iterative process. If it generates an iterative process, write
one that generates a recursive process.
;;----------------------------[ Exercise 1.32 ]---------------------------;;
a. Show that sum and product (exercise 1.31) are both special cases of a
still more general notion called accumulate that combines a collection of
terms, using some general accumulation function:
(accumulate combiner null-value term a next b)
Accumulate takes as arguments the same term and range specifications as sum
and product, together with a combiner procedure (of two arguments) that
specifies how the current term is to be combined with the accumulation of
the preceding terms and a null-value that specifies what base value to use
when the terms run out. Write accumulate and show how sum and product can
both be defined as simple calls to accumulate.
b. If your accumulate procedure generates a recursive process, write one
that generates an iterative process. If it generates an iterative process,
write one that generates a rec?rsive process.
;;----------------------------[ Exercise 1.34 ]---------------------------;;
Suppose we define the procedure
(define (f g)
(g 2))
Then we have
(f square)
4
(f (lambda (z) (* z (+ z 1))))
6
What happens if we (perversely) ask the interpreter to evaluate the
combination (f f)? Explain.
;;----------------------------[ Exercise 1.41 ]---------------------------;;
Define a procedure double that takes a procedure of one argument as argument
and returns a procedure that applies the original procedure twice. For
example, if inc is a procedure that adds 1 to its argument, then (double
inc) should be a procedure that adds 2. What value is returned by
(((double (double double)) inc) 5)
;;----------------------------[ Exercise 1.42 ]---------------------------;;
Let f and g be two one-argument functions. The composition f after g is
defined to be the function x f(g(x)). Define a procedure compose that
implements composition. For example, if inc is a procedure that adds 1 to
its argument,
((compose square inc) 6)
49
;;----------------------------[ Exercise 1.43 ]---------------------------;;
If f is a numerical function and n is a positive integer, then we can form
the nth repeated application of f, which is defined to be the function whose
value at x is f(f(...(f(x))...)). For example, if f is the function x x + 1,
then the nth repeated application of f is the function x x + n. If f is the
operation of squaring a number, then the nth repeated application of f is
the function that raises its argument to the 2nth power. Write a procedure
that takes as inputs a procedure that computes f and a positive integer n
and returns the procedure that computes the nth repeated application of
f. Your procedure should be able to be used as follows:
((repeated square 2) 5)
625
Hint: You may find it convenient to use compose from exercise 1.42.
;;----------------------------[ Exercise 1.44 ]---------------------------;;
The idea of smoothing a function is an important concept in signal
processing. If f is a function and dx is some small number, then the
smoothed version of f is the function whose value at a point x is the
average of f(x - dx), f(x), and f(x + dx). Write a procedure smooth that
takes as input a procedure that computes f and returns a procedure that
computes the smoothed f. It is sometimes valuable to repeatedly smooth a
function (that is, smooth the smoothed function, and so on) to obtained the
n-fold smoothed function. Show how to generate the n-fold smoothed function
of any given function using smooth and repeated from exercise 1.43.
;;----------------------------[ Exercise 2.2 ]----------------------------;;
Consider the problem of representing line segments in a plane. Each segment
is represented as a pair of points: a starting point and an ending
point. Define a constructor make-segment and selectors start-segment and
end-segment that define the representation of segments in terms of
points. Furthermore, a point can be represented as a pair of numbers: the x
coordinate and the y coordinate. Accordingly, specify a constructor
make-point and selectors x-point and y-point that define this
representation. Finally, using your selectors and constructors, define a
procedure midpoint-segment that takes a line segment as argument and returns
its midpoint (the point whose coordinates are the average of the coordinates
of the endpoints). To try your procedures, you'll need a way to print
points:
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
;;----------------------------[ Exercise 2.3 ]----------------------------;;
Implement a representation for rectangles in a plane. (Hint: You may want to
make use of exercise 2.2.) In terms of your constructors and selectors,
create procedures that compute the perimeter and the area of a given
rectangle. Now implement a different representation for rectangles. Can you
design your system with suitable abstraction barriers, so that the same
perimeter and area procedures will work using either representation?
;;----------------------------[ Exercise 2.17 ]---------------------------;;
Define a procedure last-pair that returns the list that contains only the
last element of a given (nonempty) list:
(last-pair (list 23 72 149 34))
(34)
;;----------------------------[ Exercise 2.18 ]---------------------------;;
Define a procedure reverse that takes a list as argument and returns a list
of the same elements in reverse order:
(reverse (list 1 4 9 16 25))
(25 16 9 4 1)
;;----------------------------[ Exercise 2.20 ]---------------------------;;
The procedures +, *, and list take arbitrary numbers of arguments. One way
to define such procedures is to use define with dotted-tail notation. In a
procedure definition, a parameter list that has a dot before the last
parameter name indicates that, when the procedure is called, the initial
parameters (if any) will have as values the initial arguments, as usual, but
the final parameter's value will be a list of any remaining arguments. For
instance, given the definition
(define (f x y . z) )
the procedure f can be called with two or more arguments. If we evaluate
(f 1 2 3 4 5 6)
then in the body of f, x will be 1, y will be 2, and z will be the list (3 4
5 6). Given the definition
(define (g . w) )
the procedure g can be called with zero or more arguments. If we evaluate
(g 1 2 3 4 5 6)
then in the body of g, w will be the list (1 2 3 4 5 6).11
Use this notation to write a procedure same-parity that takes one or more
integers and returns a list of all the arguments that have the same even-odd
parity as the first argument. For example,
(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
(same-parity 2 3 4 5 6 7)
(2 4 6)
;;----------------------------[ Exercise 2.21 ]---------------------------;;
The procedure square-list takes a list of numbers as argument and returns a
list of the squares of those numbers.
(square-list (list 1 2 3 4))
(1 4 9 16)
Here are two different definitions of square-list. Complete both of them by
filling in the missing expressions:
(define (square-list items)
(if (null? items)
nil
(cons )))
(define (square-list items)
(map ))
;;----------------------------[ Exercise 2.22 ]---------------------------;;
Louis Reasoner tries to rewrite the first square-list procedure of exercise
2.21 so that it evolves an iterative process:
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons (square (car things))
answer))))
(iter items nil))
Unfortunately, defining square-list this way produces the answer list in the
reverse order of the one desired. Why?
Louis then tries to fix his bug by interchanging the arguments to cons:
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons answer
(square (car things))))))
(iter items nil))
This doesn't work either. Explain.
;;----------------------------[ Exercise 2.23 ]---------------------------;;
The procedure for-each is similar to map. It takes as arguments a procedure
and a list of elements. However, rather than forming a list of the results,
for-each just applies the procedure to each of the elements in turn, from
left to right. The values returned by applying the procedure to the elements
are not used at all -- for-each is used with procedures that perform an
action, such as printing. For example,
(for-each (lambda (x) (newline) (display x))
(list 57 321 88))
57
321
88
The value returned by the call to for-each (not illustrated above) can be
something arbitrary, such as true. Give an implementation of for-each.
;;----------------------------[ Exercise 2.24 ]---------------------------;;
Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the
result printed by the interpreter, the corresponding box-and-pointer
structure, and the interpretation of this as a tree (as in figure 2.6).
;;----------------------------[ Exercise 2.25 ]---------------------------;;
Give combinations of cars and cdrs that will pick 7 from each of the
following lists:
(1 3 (5 7) 9)
((7))
(1 (2 (3 (4 (5 (6 7))))))
;;----------------------------[ Exercise 2.26 ]---------------------------;;
Suppose we define x and y to be two lists:
(define x (list 1 2 3))
(define y (list 4 5 6))
What result is printed by the interpreter in response to evaluating each of
the following expressions:
(append x y)
(cons x y)
(list x y)
;;----------------------------[ Exercise 2.27 ]---------------------------;;
Modify your reverse procedure of exercise 2.18 to produce a deep-reverse
procedure that takes a list as argument and returns as its value the list
with its elements reversed and with all sublists deep-reversed as well. For
example,
(define x (list (list 1 2) (list 3 4)))
x
((1 2) (3 4))
(reverse x)
((3 4) (1 2))
(deep-reverse x)
((4 3) (2 1))
;;----------------------------[ Exercise 2.28 ]---------------------------;;
Write a procedure fringe that takes as argument a tree (represented as a
list) and returns a list whose elements are all the leaves of the tree
arranged in left-to-right order. For example,
(define x (list (list 1 2) (list 3 4)))
(fringe x)
(1 2 3 4)
(fringe (list x x))
(1 2 3 4 1 2 3 4)
;;----------------------------[ Exercise 2.29 ]---------------------------;;
A binary mobile consists of two branches, a left branch and a right
branch. Each branch is a rod of a certain length, from which hangs either a
weight or another binary mobile. We can represent a binary mobile using
compound data by constructing it from two branches (for example, using
list):
(define (make-mobile left right)
(list left right))
A branch is constructed from a length (which must be a number) together with
a structure, which may be either a number (representing a simple weight) or
another mobile:
(define (make-branch length structure)
(list length structure))
a. Write the corresponding selectors left-branch and right-branch, which
return the branches of a mobile, and branch-length and branch-structure,
which return the components of a branch.
b. Using your selectors, define a procedure total-weight that returns the
total weight of a mobile.
c. A mobile is said to be balanced if the torque applied by its top-left
branch is equal to that applied by its top-right branch (that is, if the
length of the left rod multiplied by the weight hanging from that rod is
equal to the corresponding product for the right side) and if each of the
submobiles hanging off its branches is balanced. Design a predicate that
tests whether a binary mobile is balanced.
d. Suppose we change the representation of mobiles so that the constructors
are
(define (make-mobile left right)
(cons left right))
(define (make-branch length structure)
(cons length structure))
How much do you need to change your programs to convert to the new
representation?
;;----------------------------[ Exercise 2.30 ]---------------------------;;
Define a procedure square-tree analogous to the square-list procedure of
exercise 2.21. That is, square-list should behave as follows:
(square-tree
(list 1
(list 2 (list 3 4) 5)
(list 6 7)))
(1 (4 (9 16) 25) (36 49))
Define square-tree both directly (i.e., without using any higher-order
procedures) and also by using map and recursion.
;;----------------------------[ Exercise 2.31 ]---------------------------;;
Abstract your answer to exercise 2.30 to produce a procedure tree-map with
the property that square-tree could be defined as
(define (square-tree tree) (tree-map square tree))
;;----------------------------[ Exercise 2.32 ]---------------------------;;
We can represent a set as a list of distinct elements, and we can represent
the set of all subsets of the set as a list of lists. For example, if the
set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3)
(1 2) (1 2 3)). Complete the following definition of a procedure that
generates the set of subsets of a set and give a clear explanation of why it
works:
(define (subsets s)
(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map rest)))))
;;----------------------------[ Exercise 2.33 ]---------------------------;;
Fill in the missing expressions to complete the following definitions of
some basic list-manipulation operations as accumulations:
(define (map p sequence)
(accumulate (lambda (x y) ) nil sequence))
(define (append seq1 seq2)
(accumulate cons ))
(define (length sequence)
(accumulate 0 sequence))
;;----------------------------[ Exercise 2.36 ]---------------------------;;
The procedure accumulate-n is similar to accumulate except that it takes as
its third argument a sequence of sequences, which are all assumed to have
the same number of elements. It applies the designated accumulation
procedure to combine all the first elements of the sequences, all the second
elements of the sequences, and so on, and returns a sequence of the
results. For instance, if s is a sequence containing four sequences, ((1 2
3) (4 5 6) (7 8 9) (10 11 12)), then the value of (accumulate-n + 0 s)
should be the sequence (22 26 30). Fill in the missing expressions in the
following definition of accumulate-n:
(define (accumulate-n op init seqs)
(if (null? (car seqs))
nil
(cons (accumulate op init )
(accumulate-n op init ))))
;;----------------------------[ Exercise 2.37 ]---------------------------;;
Suppose we represent vectors v = (vi) as sequences of numbers, and matrices
m = (mij) as sequences of vectors (the rows of the matrix). For example, the
matrix
is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this
representation, we can use sequence operations to concisely express the
basic matrix and vector operations. These operations (which are described in
any book on matrix algebra) are the following:
We can define the dot product as17
(define (dot-product v w)
(accumulate + 0 (map * v w)))
Fill in the missing expressions in the following procedures for computing
the other matrix operations. (The procedure accumulate-n is defined in
exercise 2.36.)
(define (matrix-*-vector m v)
(map m))
(define (transpose mat)
(accumulate-n mat))
(define (matrix-*-matrix m n)
(let ((cols (transpose n)))
(map m)))
;;----------------------------[ Exercise 2.41 ]---------------------------;;
Write a procedure to find all ordered triples of distinct positive integers
i, j, and k less than or equal to a given integer n that sum to a given
integer s.
;;----------------------------[ Exercise 2.42 ]---------------------------;;
|---+---+---+---+---+---+---+---|
| | | | | | M | | |
|---+---+---+---+---+---+---+---|
| | | M | | | | | |
|---+---+---+---+---+---+---+---|
| M | | | | | | | |
|---+---+---+---+---+---+---+---|
| | | | | | | M | |
|---+---+---+---+---+---+---+---|
| | | | | M | | | |
|---+---+---+---+---+---+---+---|
| | | | | | | | M |
|---+---+---+---+---+---+---+---|
| | M | | | | | | |
|---+---+---+---+---+---+---+---|
| | | | M | | | | |
|---+---+---+---+---+---+---+---|
Figure 2.8: A solution to the eight-queens puzzle. The ``eight-queens
puzzle'' asks how to place eight queens on a chessboard so that no queen is
in check from any other (i.e., no two queens are in the same row, column, or
diagonal). One possible solution is shown in figure 2.8. One way to solve
the puzzle is to work across the board, placing a queen in each column. Once
we have placed k - 1 queens, we must place the kth queen in a position where
it does not check any of the queens already on the board. We can formulate
this approach recursively: Assume that we have already generated the
sequence of all possible ways to place k - 1 queens in the first k - 1
columns of the board. For each of these ways, generate an extended set of
positions by placing a queen in each row of the kth column. Now filter
these, keeping only the positions for which the queen in the kth column is
safe with respect to the other queens. This produces the sequence of all
ways to place k queens in the first k columns. By continuing this process,
we will produce not only one solution, but all solutions to the puzzle.
We implement this solution as a procedure queens, which returns a sequence
of all solutions to the problem of placing n queens on an n× n
chessboard. Queens has an internal procedure queen-cols that returns the
sequence of all ways to place queens in the first k columns of the board.
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
In this procedure rest-of-queens is a way to place k - 1 queens in the first
k - 1 columns, and new-row is a proposed row in which to place the queen for
the kth column. Complete the program by implementing the representation for
sets of board positions, including the procedure adjoin-position, which
adjoins a new row-column position to a set of positions, and empty-board,
which represents an empty set of positions. You must also write the
procedure safe?, which determines for a set of positions, whether the queen
in the kth column is safe with respect to the others. (Note that we need
only check whether the new queen is safe -- the other queens are already
guaranteed safe with respect to each other.)
;;----------------------------[ Exercise 2.43 ]---------------------------;;
Louis Reasoner is having a terrible time doing exercise 2.42. His queens
procedure seems to work, but it runs extremely slowly. (Louis never does
manage to wait long enough for it to solve even the 6× 6 case.) When Louis
asks Eva Lu Ator for help, she points out that he has interchanged the order
of the nested mappings in the flatmap, writing it as
(flatmap
(lambda (new-row)
(map (lambda (rest-of-queens)
(adjoin-position new-row k rest-of-queens))
(queen-cols (- k 1))))
(enumerate-interval 1 board-size))
Explain why this interchange makes the program run slowly. Estimate how long
it will take Louis's program to solve the eight-queens puzzle, assuming that
the program in exercise 2.42 solves the puzzle in time T.
;;----------------------------[ Exercise 2.53 ]---------------------------;;
What would the interpreter print in response to evaluating each of the
following expressions?
(list 'a 'b 'c)
(list (list 'george))
(cdr '((x1 x2) (y1 y2)))
(cadr '((x1 x2) (y1 y2)))
(pair? (car '(a short list)))
(memq 'red '((red shoes) (blue socks)))
(memq 'red '(red shoes blue socks))
;;----------------------------[ Exercise 2.54 ]---------------------------;;
Two lists are said to be equal? if they contain equal elements arranged in
the same order. For example,
(equal? '(this is a list) '(this is a list))
is true, but
(equal? '(this is a list) '(this (is a) list))
is false. To be more precise, we can define equal? recursively in terms of
the basic eq? equality of symbols by saying that a and b are equal? if they
are both symbols and the symbols are eq?, or if they are both lists such
that (car a) is equal? to (car b) and (cdr a) is equal? to (cdr b). Using
this idea, implement equal? as a procedure.36
;;----------------------------[ Exercise 2.55 ]---------------------------;;
Eva Lu Ator types to the interpreter the expression
(car ''abracadabra)
To her surprise, the interpreter prints back quote. Explain.
;;----------------------------[ Exercise 2.59 ]---------------------------;;
Implement the union-set operation for the unordered-list representation of
sets.
;;----------------------------[ Exercise 2.60 ]---------------------------;;
We specified that a set would be represented as a list with no
duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3}
could be represented as the list (2 3 2 1 3 2 2). Design procedures
element-of-set?, adjoin-set, union-set, and intersection-set that operate on
this representation. How does the efficiency of each compare with the
corresponding procedure for the non-duplicate representation? Are there
applications for which you would use this representation in preference to
the non-duplicate one?
;;----------------------------[ Exercise 2.61 ]---------------------------;;
Give an implementation of adjoin-set using the ordered representation. By
analogy with element-of-set? show how to take advantage of the ordering to
produce a procedure that requires on the average about half as many steps as
with the unordered representation.
;;----------------------------[ Exercise 2.62 ]---------------------------;;
Give a (n) implementation of union-set for sets represented as ordered
lists.
;;----------------------------[ Exercise 2.63 ]---------------------------;;
Each of the following two procedures converts a binary tree to a list.
(define (tree->list-1 tree)
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))
a. Do the two procedures produce the same result for every tree? If not, how
do the results differ? What lists do the two procedures produce for the
trees in figure 2.16?
b. Do the two procedures have the same order of growth in the number of
steps required to convert a balanced tree with n elements to a list? If not,
which one grows more slowly?
;;----------------------------[ Exercise 2.64 ]---------------------------;;
The following procedure list->tree converts an ordered list to a balanced
binary tree. The helper procedure partial-tree takes as arguments an integer
n and list of at least n elements and constructs a balanced tree containing
the first n elements of the list. The result returned by partial-tree is a
pair (formed with cons) whose car is the constructed tree and whose cdr is
the list of elements not included in the tree.
(define (list->tree elements)
(car (partial-tree elements (length elements))))
(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
(let ((left-size (quotient (- n 1) 2)))
(let ((left-result (partial-tree elts left-size)))
(let ((left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1))))
(let ((this-entry (car non-left-elts))
(right-result (partial-tree (cdr non-left-elts)
right-size)))
(let ((right-tree (car right-result))
(remaining-elts (cdr right-result)))
(cons (make-tree this-entry left-tree right-tree)
remaining-elts))))))))
a. Write a short paragraph explaining as clearly as you can how partial-tree
works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).
b. What is the order of growth in the number of steps required by list->tree
to convert a list of n elements?
;;----------------------------[ Exercise 2.65 ]---------------------------;;
Use the results of exercises 2.63 and 2.64 to give (n) implementations of
union-set and intersection-set for sets implemented as (balanced) binary
trees.41
;;----------------------------[ Exercise 2.66 ]---------------------------;;
Implement the lookup procedure for the case where the set of records is
structured as a binary tree, ordered by the numerical values of the keys.
;;----------------------------[ Exercise 2.67 ]---------------------------;;
Define an encoding tree and a sample message:
(define sample-tree
(make-code-tree (make-leaf 'A 4)
(make-code-tree
(make-leaf 'B 2)
(make-code-tree (make-leaf 'D 1)
(make-leaf 'C 1)))))
(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
Use the decode procedure to decode the message, and give the result.
;;----------------------------[ Exercise 2.68 ]---------------------------;;
The encode procedure takes as arguments a message and a tree and produces
the list of bits that gives the encoded message.
(define (encode message tree)
(if (null? message)
'()
(append (encode-symbol (car message) tree)
(encode (cdr message) tree))))
Encode-symbol is a procedure, which you must write, that returns the list of
bits that encodes a given symbol according to a given tree. You should
design encode-symbol so that it signals an error if the symbol is not in the
tree at all. Test your procedure by encoding the result you obtained in
exercise 2.67 with the sample tree and seeing whether it is the same as the
original sample message.
;;----------------------------[ Exercise 2.69 ]---------------------------;;
The following procedure takes as its argument a list of symbol-frequency
pairs (where no symbol appears in more than one pair) and generates a
Huffman encoding tree according to the Huffman algorithm.
(define (generate-huffman-tree pairs)
(successive-merge (make-leaf-set pairs)))
Make-leaf-set is the procedure given above that transforms the list of pairs
into an ordered set of leaves. Successive-merge is the procedure you must
write, using make-code-tree to successively merge the smallest-weight
elements of the set until there is only one element left, which is the
desired Huffman tree. (This procedure is slightly tricky, but not really
complicated. If you find yourself designing a complex procedure, then you
are almost certainly doing something wrong. You can take significant
advantage of the fact that we are using an ordered set representation.)
;;----------------------------[ Exercise 2.70 ]---------------------------;;
The following eight-symbol alphabet with associated relative frequencies was
designed to efficiently encode the lyrics of 1950s rock songs. (Note that
the ``symbols'' of an ``alphabet'' need not be individual letters.)
A 2 NA 16
BOOM 1 SHA 3
GET 2 YIP 9
JOB 2 WAH 1
Use generate-huffman-tree (exercise 2.69) to generate a corresponding
Huffman tree, and use encode (exercise 2.68) to encode the following
message:
Get a job
Sha na na na na na na na na
Get a job
Sha na na na na na na na na
Wah yip yip yip yip yip yip yip yip yip
Sha boom
How many bits are required for the encoding? What is the smallest number of
bits that would be needed to encode this song if we used a fixed-length code
for the eight-symbol alphabet?
;;----------------------------[ Exercise 2.71 ]---------------------------;;
Suppose we have a Huffman tree for an alphabet of n symbols, and that the
relative frequencies of the symbols are 1, 2, 4, ..., 2n-1. Sketch the tree
for n=5; for n=10. In such a tree (for general n) how many bits are required
to encode the most frequent symbol? the least frequent symbol?
;;----------------------------[ Exercise 2.72 ]---------------------------;;
Consider the encoding procedure that you designed in exercise 2.68. What is
the order of growth in the number of steps needed to encode a symbol? Be
sure to include the number of steps needed to search the symbol list at each
node encountered. To answer this question in general is difficult. Consider
the special case where the relative frequencies of the n symbols are as
described in exercise 2.71, and give the order of growth (as a function of
n) of the number of steps needed to encode the most frequent and least
frequent symbols in the alphabet.
;;----------------------------[ Exercise 3.1 ]----------------------------;;
An accumulator is a procedure that is called repeatedly with a single
numeric argument and accumulates its arguments into a sum. Each time it is
called, it returns the currently accumulated sum. Write a procedure
make-accumulator that generates accumulators, each maintaining an
independent sum. The input to make-accumulator should specify the initial
value of the sum; for example
(define A (make-accumulator 5))
(A 10)
15
(A 10)
25
;;----------------------------[ Exercise 3.2 ]----------------------------;;
In software-testing applications, it is useful to be able to count the
number of times a given procedure is called during the course of a
computation. Write a procedure make-monitored that takes as input a
procedure, f, that itself takes one input. The result returned by
make-monitored is a third procedure, say mf, that keeps track of the number
of times it has been called by maintaining an internal counter. If the input
to mf is the special symbol how-many-calls?, then mf returns the value of
the counter. If the input is the special symbol reset-count, then mf resets
the counter to zero. For any other input, mf returns the result of calling f
on that input and increments the counter. For instance, we could make a
monitored version of the sqrt procedure:
(define s (make-monitored sqrt))
(s 100)
10
(s 'how-many-calls?)
1
;;----------------------------[ Exercise 3.3 ]----------------------------;;
Modify the make-account procedure so that it creates password-protected
accounts. That is, make-account should take a symbol as an additional
argument, as in
(define acc (make-account 100 'secret-password))
The resulting account object should process a request only if it is
accompanied by the password with which the account was created, and should
otherwise return a complaint:
((acc 'secret-password 'withdraw) 40)
60
((acc 'some-other-password 'deposit) 50)
"Incorrect password"
;;----------------------------[ Exercise 3.4 ]----------------------------;;
Modify the make-account procedure of exercise 3.3 by adding another local
state variable so that, if an account is accessed more than seven
consecutive times with an incorrect password, it invokes the procedure
call-the-cops.
;;----------------------------[ Exercise 3.7 ]----------------------------;;
Consider the bank account objects created by make-account, with the password
modification described in exercise 3.3. Suppose that our banking system
requires the ability to make joint accounts. Define a procedure make-joint
that accomplishes this. Make-joint should take three arguments. The first is
a password-protected account. The second argument must match the password
with which the account was defined in order for the make-joint operation to
proceed. The third argument is a new password. Make-joint is to create an
additional access to the original account using the new password. For
example, if peter-acc is a bank account with password open-sesame, then
(define paul-acc
(make-joint peter-acc 'open-sesame 'rosebud))
will allow one to make transactions on peter-acc using the name paul-acc and
the password rosebud. You may wish to modify your solution to exercise 3.3
to accommodate this new feature.
;;----------------------------[ Exercise 3.8 ]----------------------------;;
When we defined the evaluation model in section 1.1.3, we said that the
first step in evaluating an expression is to evaluate its
subexpressions. But we never specified the order in which the subexpressions
should be evaluated (e.g., left to right or right to left). When we
introduce assignment, the order in which the arguments to a procedure are
evaluated can make a difference to the result. Define a simple procedure f
such that evaluating (+ (f 0) (f 1)) will return 0 if the arguments to + are
evaluated from left to right but will return 1 if the arguments are
evaluated from right to left.
;;----------------------------[ Exercise 3.9 ]----------------------------;;
In section 1.2.1 we used the substitution model to analyze two procedures
for computing factorials, a recursive version
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
and an iterative version
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
Show the environment structures created by evaluating (factorial 6) using
each version of the factorial procedure.14
;;----------------------------[ Exercise 3.10 ]---------------------------;;
In the make-withdraw procedure, the local variable balance is created as a
parameter of make-withdraw. We could also create the local state variable
explicitly, using let, as follows:
(define (make-withdraw initial-amount)
(let ((balance initial-amount))
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))))
Recall from section 1.3.2 that let is simply syntactic sugar for a procedure
call:
(let ((` )) )
is interpreted as an alternate syntax for
((lambda (``) ) )
Use the environment model to analyze this alternate version of
make-withdraw, drawing figures like the ones above to illustrate the
interactions
(define W1 (make-withdraw 100))
(W1 50)
(define W2 (make-withdraw 100))
Show that the two versions of make-withdraw create objects with the same
behavior. How do the environment structures differ for the two versions?
;;----------------------------[ Exercise 3.11 ]---------------------------;;
In section 3.2.3 we saw how the environment model described the behavior of
procedures with local state. Now we have seen how internal definitions
work. A typical message-passing procedure contains both of these
aspects. Consider the bank account procedure of section 3.1.1:
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch)
Show the environment structure generated by the sequence of interactions
(define acc (make-account 50))
((acc 'deposit) 40)
90
((acc 'withdraw) 60)
30
Where is the local state for acc kept? Suppose we define another account
(define acc2 (make-account 100))
How are the local states for the two accounts kept distinct? Which parts of
the environment structure are shared between acc and acc2?
;;----------------------------[ Exercise 3.12 ]---------------------------;;
The following procedure for appending lists was introduced in section 2.2.1:
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))
Append forms a new list by successively consing the elements of x onto
y. The procedure append! is similar to append, but it is a mutator rather
than a constructor. It appends the lists by splicing them together,
modifying the final pair of x so that its cdr is now y. (It is an error to
call append! with an empty x.)
(define (append! x y)
(set-cdr! (last-pair x) y)
x)
Here last-pair is a procedure that returns the last pair in its argument:
(define (last-pair x)
(if (null? (cdr x))
x
(last-pair (cdr x))))
Consider the interaction
(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))
z
(a b c d)
(cdr x)
(define w (append! x y))
w
(a b c d)
(cdr x)
What are the missing s? Draw box-and-pointer diagrams to explain
your answer.
;;----------------------------[ Exercise 3.13 ]---------------------------;;
Consider the following make-cycle procedure, which uses the last-pair
procedure defined in exercise 3.12:
(define (make-cycle x)
(set-cdr! (last-pair x) x)
x)
Draw a box-and-pointer diagram that shows the structure z created by
(define z (make-cycle (list 'a 'b 'c)))
What happens if we try to compute (last-pair z)?
;;----------------------------[ Exercise 3.14 ]---------------------------;;
The following procedure is quite useful, although obscure:
(define (mystery x)
(define (loop x y)
(if (null? x)
y
(let ((temp (cdr x)))
(set-cdr! x y)
(loop temp x))))
(loop x '()))
Loop uses the ``temporary'' variable temp to hold the old value of the cdr
of x, since the set-cdr! on the next line destroys the cdr. Explain what
mystery does in general. Suppose v is defined by (define v (list 'a 'b 'c
'd)). Draw the box-and-pointer diagram that represents the list to which v
is bound. Suppose that we now evaluate (define w (mystery v)). Draw
box-and-pointer diagrams that show the structures v and w after evaluating
this expression. What would be printed as the values of v and w ?
;;----------------------------[ Exercise 3.15 ]---------------------------;;
Draw box-and-pointer diagrams to explain the effect of set-to-wow! on the
structures z1 and z2 above.
;;----------------------------[ Exercise 3.16 ]---------------------------;;
Ben Bitdiddle decides to write a procedure to count the number of pairs in
any list structure. ``It's easy,'' he reasons. ``The number of pairs in any
structure is the number in the car plus the number in the cdr plus one more
to count the current pair.'' So Ben writes the following procedure:
(define (count-pairs x)
(if (not (pair? x))
0
(+ (count-pairs (car x))
(count-pairs (cdr x))
1)))
Show that this procedure is not correct. In particular, draw box-and-pointer
diagrams representing list structures made up of exactly three pairs for
which Ben's procedure would return 3; return 4; return 7; never return at
all.
;;----------------------------[ Exercise 3.17 ]---------------------------;;
Devise a correct version of the count-pairs procedure of exercise 3.16 that
returns the number of distinct pairs in any structure. (Hint: Traverse the
structure, maintaining an auxiliary data structure that is used to keep
track of which pairs have already been counted.)
;;----------------------------[ Exercise 3.18 ]---------------------------;;
Write a procedure that examines a list and determines whether it contains a
cycle, that is, whether a program that tried to find the end of the list by
taking successive cdrs would go into an infinite loop. Exercise 3.13
constructed such lists
;;----------------------------[ Exercise 3.20 ]---------------------------;;
Draw environment diagrams to illustrate the evaluation of the sequence of
expressions
(define x (cons 1 2))
(define z (cons x x))
(set-car! (cdr z) 17)
(car x)
17
using the procedural implementation of pairs given above. (Compare exercise
3.11.)
;;----------------------------[ Exercise 3.21 ]---------------------------;;
Ben Bitdiddle decides to test the queue implementation described above. He
types in the procedures to the Lisp interpreter and proceeds to try them
out:
(define q1 (make-queue))
(insert-queue! q1 'a)
((a) a)
(insert-queue! q1 'b)
((a b) b)
(delete-queue! q1)
((b) b)
(delete-queue! q1)
(() b)
``It's all wrong!'' he complains. ``The interpreter's response shows that
the last item is inserted into the queue twice. And when I delete both
items, the second b is still there, so the queue isn't empty, even though
it's supposed to be.'' Eva Lu Ator suggests that Ben has misunderstood what
is happening. ``It's not that the items are going into the queue twice,''
she explains. ``It's just that the standard Lisp printer doesn't know how to
make sense of the queue representation. If you want to see the queue printed
correctly, you'll have to define your own print procedure for queues.''
Explain what Eva Lu is talking about. In particular, show why Ben's examples
produce the printed results that they do. Define a procedure print-queue
that takes a queue as input and prints the sequence of items in the queue.
;;----------------------------[ Exercise 3.22 ]---------------------------;;
Instead of representing a queue as a pair of pointers, we can build a queue
as a procedure with local state. The local state will consist of pointers to
the beginning and the end of an ordinary list. Thus, the make-queue
procedure will have the form
(define (make-queue)
(let ((front-ptr ...)
(rear-ptr ...))
(define (dispatch m) ...)
dispatch))
Complete the definition of make-queue and provide implementations of the
queue operations using this representation.
;;----------------------------[ Exercise 3.23 ]---------------------------;;
A deque (``double-ended queue'') is a sequence in which items can be
inserted and deleted at either the front or the rear. Operations on deques
are the constructor make-deque, the predicate empty-deque?, selectors
front-deque and rear-deque, and mutators front-insert-deque!,
rear-insert-deque!, front-delete-deque!, and rear-delete-deque!. Show how to
represent deques using pairs, and give implementations of the operations.23
All operations should be accomplished in θ(1) steps.
;;----------------------------[ Exercise 3.24 ]---------------------------;;
In the table implementations above, the keys are tested for equality using
equal? (called by assoc). This is not always the appropriate test. For
instance, we might have a table with numeric keys in which we don't need an
exact match to the number we're looking up, but only a number within some
tolerance of it. Design a table constructor make-table that takes as an
argument a same-key? procedure that will be used to test ``equality'' of
keys. Make-table should return a dispatch procedure that can be used to
access appropriate lookup and insert! procedures for a local table.
;;----------------------------[ Exercise 3.25 ]---------------------------;;
Generalizing one- and two-dimensional tables, show how to implement a table
in which values are stored under an arbitrary number of keys and different
values may be stored under different numbers of keys. The lookup and insert!
procedures should take as input a list of keys used to access the table.
;;----------------------------[ Exercise 3.26 ]---------------------------;;
To search a table as implemented above, one needs to scan through the list
of records. This is basically the unordered list representation of section
2.3.3. For large tables, it may be more efficient to structure the table in
a different manner. Describe a table implementation where the (key, value)
records are organized using a binary tree, assuming that keys can be ordered
in some way (e.g., numerically or alphabetically). (Compare exercise 2.66 of
chapter 2.)
;;----------------------------[ Exercise 3.27 ]---------------------------;;
Memoization (also called tabulation) is a technique that enables a procedure
to record, in a local table, values that have previously been computed. This
technique can make a vast difference in the performance of a program. A
memoized procedure maintains a table in which values of previous calls are
stored using as keys the arguments that produced the values. When the
memoized procedure is asked to compute a value, it first checks the table to
see if the value is already there and, if so, just returns that
value. Otherwise, it computes the new value in the ordinary way and stores
this in the table. As an example of memoization, recall from section 1.2.2
the exponential process for computing Fibonacci numbers:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
The memoized version of the same procedure is
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
where the memoizer is defined as
(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))
Draw an environment diagram to analyze the computation of (memo-fib
3). Explain why memo-fib computes the nth Fibonacci number in a number of
steps proportional to n. Would the scheme still work if we had simply
defined memo-fib to be (memoize fib)?
;;----------------------------[ Exercise 3.38 ]---------------------------;;
Suppose that Peter, Paul, and Mary share a joint bank account that initially
contains $100. Concurrently, Peter deposits $10, Paul withdraws $20, and
Mary withdraws half the money in the account, by executing the following
commands: Peter: (set! balance (+ balance 10)) Paul: (set! balance (-
balance 20)) Mary: (set! balance (- balance (/ balance 2)))
a. List all the different possible values for balance after these three
transactions have been completed, assuming that the banking system forces
the three processes to run sequentially in some order.
b. What are some other values that could be produced if the system allows
the processes to be interleaved? Draw timing diagrams like the one in figure
3.29 to explain how these values can occur.
;;----------------------------[ Exercise 3.50 ]---------------------------;;
Complete the following definition, which generalizes stream-map to allow
procedures that take multiple arguments, analogous to map in section 2.2.3,
footnote 12.
(define (stream-map proc . argstreams)
(if ( (car argstreams))
the-empty-stream
(
(apply proc (map argstreams))
(apply stream-map
(cons proc (map argstreams))))))
;;----------------------------[ Exercise 3.51 ]---------------------------;;
In order to take a closer look at delayed evaluation, we will use the
following procedure, which simply returns its argument after printing it:
(define (show x)
(display-line x)
x)
What does the interpreter print in response to evaluating each expression in
the following sequence?59
(define x (stream-map show (stream-enumerate-interval 0 10)))
(stream-ref x 5)
(stream-ref x 7)
;;----------------------------[ Exercise 3.52 ]---------------------------;;
Consider the sequence of expressions
(define sum 0)
(define (accum x)
(set! sum (+ x sum))
sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(define y (stream-filter even? seq))
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
seq))
(stream-ref y 7)
(display-stream z)
What is the value of sum after each of the above expressions is evaluated?
What is the printed response to evaluating the stream-ref and display-stream
expressions? Would these responses differ if we had implemented (delay
) simply as (lambda () ) without using the optimization provided
by memo-proc ? Explain.
;;----------------------------[ Exercise 3.53 ]---------------------------;;
Without running the program, describe the elements of the stream defined by
(define s (cons-stream 1 (add-streams s s)))
;;----------------------------[ Exercise 3.54 ]---------------------------;;
Define a procedure mul-streams, analogous to add-streams, that produces the
elementwise product of its two input streams. Use this together with the
stream of integers to complete the following definition of the stream whose
nth element (counting from 0) is n + 1 factorial:
(define factorials (cons-stream 1 (mul-streams )))
;;----------------------------[ Exercise 3.55 ]---------------------------;;
Define a procedure partial-sums that takes as argument a stream S and
returns the stream whose elements are S0, S0 + S1, S0 + S1 + S2, .... For
example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15, ....
;;----------------------------[ Exercise 3.56 ]---------------------------;;
A famous problem, first raised by R. Hamming, is to enumerate, in ascending
order with no repetitions, all positive integers with no prime factors other
than 2, 3, or 5. One obvious way to do this is to simply test each integer
in turn to see whether it has any factors other than 2, 3, and 5. But this
is very inefficient, since, as the integers get larger, fewer and fewer of
them fit the requirement. As an alternative, let us call the required stream
of numbers S and notice the following facts about it.
S begins with 1. The elements of (scale-stream S 2) are also elements of S.
The same is true for (scale-stream S 3) and (scale-stream 5 S). These are
all the elements of S. Now all we have to do is combine elements from these
sources. For this we define a procedure merge that combines two ordered
streams into one ordered result stream, eliminating repetitions:
(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< s1car s2car)
(cons-stream s1car (merge (stream-cdr s1) s2)))
((> s1car s2car)
(cons-stream s2car (merge s1 (stream-cdr s2))))
(else
(cons-stream s1car
(merge (stream-cdr s1)
(stream-cdr s2)))))))))
Then the required stream may be constructed with merge, as follows:
(define S (cons-stream 1 (merge )))
Fill in the missing expressions in the places marked above.
;;----------------------------[ Exercise 3.57 ]---------------------------;;
How many additions are performed when we compute the nth Fibonacci number
using the definition of fibs based on the add-streams procedure? Show that
the number of additions would be exponentially greater if we had implemented
(delay ) simply as (lambda () ), without using the optimization
provided by the memo-proc procedure described in section 3.5.1.64
;;----------------------------[ Exercise 3.66 ]---------------------------;;
Examine the stream (pairs integers integers). Can you make any general
comments about the order in which the pairs are placed into the stream? For
example, about how many pairs precede the pair (1,100)? the pair (99,100)?
the pair (100,100)? (If you can make precise mathematical statements here,
all the better. But feel free to give more qualitative answers if you find
yourself getting bogged down.)
;;----------------------------[ Exercise 3.67 ]---------------------------;;
Modify the pairs procedure so that (pairs integers integers) will produce
the stream of all pairs of integers (i,j) (without the condition i ⪬
j). Hint: You will need to mix in an additional stream.
;;----------------------------[ Exercise 3.68 ]---------------------------;;
Louis Reasoner thinks that building a stream of pairs from three parts is
unnecessarily complicated. Instead of separating the pair (S0,T0) from the
rest of the pairs in the first row, he proposes to work with the whole first
row, as follows:
(define (pairs s t)
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
t)
(pairs (stream-cdr s) (stream-cdr t))))
Does this work? Consider what happens if we evaluate (pairs integers
integers) using Louis's definition of pairs.
;;----------------------------[ Exercise 3.69 ]---------------------------;;
Write a procedure triples that takes three infinite streams, S, T, and U,
and produces the stream of triples (Si,Tj,Uk) such that i ⪬ j ⪬ k. Use
triples to generate the stream of all Pythagorean triples of positive
integers, i.e., the triples (i,j,k) such that i ⪬ j and i2 + j2 = k2.
;;----------------------------[ Exercise 4.1 ]----------------------------;;
Notice that we cannot tell whether the metacircular evaluator evaluates
operands from left to right or from right to left. Its evaluation order is
inherited from the underlying Lisp: If the arguments to cons in
list-of-values are evaluated from left to right, then list-of-values will
evaluate operands from left to right; and if the arguments to cons are
evaluated from right to left, then list-of-values will evaluate operands
from right to left.
Write a version of list-of-values that evaluates operands from left to right
regardless of the order of evaluation in the underlying Lisp. Also write a
version of list-of-values that evaluates operands from right to left.
;;----------------------------[ Exercise 4.2 ]----------------------------;;
Louis Reasoner plans to reorder the cond clauses in eval so that the clause
for procedure applications appears before the clause for assignments. He
argues that this will make the interpreter more efficient: Since programs
usually contain more applications than assignments, definitions, and so on,
his modified eval will usually check fewer clauses than the original eval
before identifying the type of an expression.
a. What is wrong with Louis's plan? (Hint: What will Louis's evaluator do
with the expression (define x 3)?)
b. Louis is upset that his plan didn't work. He is willing to go to any
lengths to make his evaluator recognize procedure applications before it
checks for most other kinds of expressions. Help him by changing the syntax
of the evaluated language so that procedure applications start with
call. For example, instead of (factorial 3) we will now have to write (call
factorial 3) and instead of (+ 1 2) we will have to write (call + 1 2).
;;----------------------------[ Exercise 4.3 ]----------------------------;;
Rewrite eval so that the dispatch is done in data-directed style. Compare
this with the data-directed differentiation procedure of exercise 2.73. (You
may use the car of a compound expression as the type of the expression, as
is appropriate for the syntax implemented in this section.) .
;;----------------------------[ Exercise 4.4 ]----------------------------;;
Recall the definitions of the special forms and and or from chapter 1:
and: The expressions are evaluated from left to right. If any expression
evaluates to false, false is returned; any remaining expressions are not
evaluated. If all the expressions evaluate to true values, the value of the
last expression is returned. If there are no expressions then true is
returned. or: The expressions are evaluated from left to right. If any
expression evaluates to a true value, that value is returned; any remaining
expressions are not evaluated. If all expressions evaluate to false, or if
there are no expressions, then false is returned. Install and and or as new
special forms for the evaluator by defining appropriate syntax procedures
and evaluation procedures eval-and and eval-or. Alternatively, show how to
implement and and or as derived expressions.
;;----------------------------[ Exercise 4.5 ]----------------------------;;
Scheme allows an additional syntax for cond clauses, ( =>
). If evaluates to a true value, then is
evaluated. Its value must be a procedure of one argument; this procedure is
then invoked on the value of the , and the result is returned as the
value of the cond expression. For example
(cond ((assoc 'b '((a 1) (b 2))) => cadr)
(else false))
returns 2. Modify the handling of cond so that it supports this extended
syntax.
;;----------------------------[ Exercise 4.6 ]----------------------------;;
Let expressions are derived expressions, because
(let (( ) ... ( ))
)
is equivalent to
((lambda ( ... )
)
)
Implement a syntactic transformation let->combination that reduces
evaluating let expressions to evaluating combinations of the type shown
above, and add the appropriate clause to eval to handle let expressions.
;;----------------------------[ Exercise 4.7 ]----------------------------;;
Let* is similar to let, except that the bindings of the let variables are
performed sequentially from left to right, and each binding is made in an
environment in which all of the preceding bindings are visible. For example
(let* ((x 3)
(y (+ x 2))
(z (+ x y 5)))
(* x z))
returns 39. Explain how a let* expression can be rewritten as a set of
nested let expressions, and write a procedure let*->nested-lets that
performs this transformation. If we have already implemented let (exercise
4.6) and we want to extend the evaluator to handle let*, is it sufficient to
add a clause to eval whose action is
(eval (let*->nested-lets exp) env)
or must we explicitly expand let* in terms of non-derived expressions?
;;----------------------------[ Exercise 4.8 ]----------------------------;;
``Named let'' is a variant of let that has the form
(let `` )
The and are just as in ordinary let, except that `` is
bound within to a procedure whose body is and whose parameters
are the variables in the . Thus, one can repeatedly execute the
by invoking the procedure named ``. For example, the iterative
Fibonacci procedure (section 1.2.2) can be rewritten using named let as
follows:
(define (fib n)
(let fib-iter ((a 1)
(b 0)
(count n))
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))))
Modify let->combination of exercise 4.6 to also support named let.
;;----------------------------[ Exercise 4.9 ]----------------------------;;
Many languages support a variety of iteration constructs, such as do, for,
while, and until. In Scheme, iterative processes can be expressed in terms
of ordinary procedure calls, so special iteration constructs provide no
essential gain in computational power. On the other hand, such constructs
are often convenient. Design some iteration constructs, give examples of
their use, and show how to implement them as derived expressions.
;;----------------------------[ Exercise 4.10 ]---------------------------;;
By using data abstraction, we were able to write an eval procedure that is
independent of the particular syntax of the language to be evaluated. To
illustrate this, design and implement a new syntax for Scheme by modifying
the procedures in this section, without changing eval or apply.
;;----------------------------[ Exercise 4.11 ]---------------------------;;
Instead of representing a frame as a pair of lists, we can represent a frame
as a list of bindings, where each binding is a name-value pair. Rewrite the
environment operations to use this alternative representation.
;;----------------------------[ Exercise 4.12 ]---------------------------;;
The procedures set-variable-value!, define-variable!, and
lookup-variable-value can be expressed in terms of more abstract procedures
for traversing the environment structure. Define abstractions that capture
the common patterns and redefine the three procedures in terms of these
abstractions.
;;----------------------------[ Exercise 4.25 ]---------------------------;;
Suppose that (in ordinary applicative-order Scheme) we define unless as
shown above and then define factorial in terms of unless as
(define (factorial n)
(unless (= n 1)
(* n (factorial (- n 1)))
1))
What happens if we attempt to evaluate (factorial 5)? Will our definitions
work in a normal-order language?
;;----------------------------[ Exercise 4.26 ]---------------------------;;
Ben Bitdiddle and Alyssa P. Hacker disagree over the importance of lazy
evaluation for implementing things such as unless. Ben points out that it's
possible to implement unless in applicative order as a special form. Alyssa
counters that, if one did that, unless would be merely syntax, not a
procedure that could be used in conjunction with higher-order
procedures. Fill in the details on both sides of the argument. Show how to
implement unless as a derived expression (like cond or let), and give an
example of a situation where it might be useful to have unless available as
a procedure, rather than as a special form.
;;----------------------------[ Exercise 4.27 ]---------------------------;;
Suppose we type in the following definitions to the lazy evaluator:
(define count 0)
(define (id x)
(set! count (+ count 1))
x)
Give the missing values in the following sequence of interactions, and
explain your answers.38
(define w (id (id 10)))
;;; L-Eval input:
count
;;; L-Eval value:
;;; L-Eval input:
w
;;; L-Eval value:
;;; L-Eval input:
count
;;; L-Eval value:
;;----------------------------[ Exercise 4.28 ]---------------------------;;
Eval uses actual-value rather than eval to evaluate the operator before
passing it to apply, in order to force the value of the operator. Give an
example that demonstrates the need for this forcing.
;;----------------------------[ Exercise 4.29 ]---------------------------;;
Exhibit a program that you would expect to run much more slowly without
memoization than with memoization. Also, consider the following interaction,
where the id procedure is defined as in exercise 4.27 and count starts at 0:
(define (square x)
(* x x))
;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
;;; L-Eval input:
count
;;; L-Eval value:
Give the responses both when the evaluator memoizes and when it does not.
;;------------------------------------------------------------------------;;
`