Errata as of June 18, 2003

New text is shown in italics. Where the original is in italics both before and after are shown.

Introduction

pxv Nick Pippenger, George Tsiknis, and the other

Chapter 1

p9 ``thermometer to measure the current"

p19 (+ 2 3) -> 6 should be 5 (at least as of this date).

p33 In Ex. 1-21, the answer is incorrect. See Appendix A errata.

p35 Second last paragraph: ``we could evaluate the above form''. The form actually appears in Program 1-6 on the next page.

p36 After Program 1-8: Interchange ``former'' and ``latter''.

p38 Last paragraph: the phrase ``Universal Robots'' should not appear.

p41 Septimius should be Septimus.

p44 Definition rule: ``the binding between the name and value is added to the environment."

p44 The answer to Ex. 1-34 is confusing. See Appendix A errata for p691.

p47 There should be a Boolean rule: ``The values #t and #f are the results of Boolean operations and predicates, and can be input as #t and #f.

p47 In the If rule: #f should be #f, the value.

p49 The Scheme code for the hour hand is correct, but the text should read: ``30 degrees per hour, and thus 0.5 degrees per minute, or 1 degree each 120 seconds.''

Chapter 2

p65 The code derived from the analysis of addition assumes that b is nonnegative. The first case in the algebra at the bottom of the page applies even if b is negative, but the recursive restatement will not terminate if b is negative.

p70 In the sidebar on Numbers, ``some extremely limited ones may only support integers in the range from -32768 to 32767.'' As it is, the numbers require 17 bits, which is quite unusual; most machines support 16 bit numbers.

p75 (collect-evens 0123450) -> 0240, but the first 0 is not printed. The problem should be rephrased as (collect-evens 123450) so that the answer wouldn't require the leading 0.

p78 We must assume that the jars are completely filled when used.

p82 Both mult%1 and mult%2 assume b>=1.

p83 The version of mult%1 we wrote in Ex. 2-4 is modeled on power, not on the recursive identity that appears at the top of the page. We used a * b = 0, for b=0 in Ex. 2-4. The identity as it appears on p.83 is odd. Its last should be a * b = 0, where b=0.

p84 Figure 2-13 contains some errors. The trace should be:

> (mult%2 17 13)
call mult%2: 17 13
| call mult%2: 34 6
| | call mult%2: 68 3
| | | call mult%2: 136 1
| | | return from mult%2: 136
| | return from mult%2: 204
| return from mult%2: 204
return from mult%2: 221
221

p85 The lg of 16 is 4. We shouldn't have used ``log''.

p89 ``The class of problems that have polynomial algorithms is called P."

p89 Second last paragraph: ``as much good-quality wood as possible.''

p98 There are extra closing parentheses in the last two expressions involving interest.

p104 boolean should be boolean? in the Scheme Summary.

p104 Problem 1: reverse-digits cannot be expected to work on numbers that end with 0, since the printed representation of the reverse of such a number does not begin with 0, even though the arithmetic might be correct in coming up with the answer.

p105 Problem 11: (digit-0 1) should return -1 always!.

p107 Programming problem 2: r should be 10% to get the answer given. There is a confusion between rate and percentage.

Chapter 3

p111 Fourth paragraph: \#5 should be #\5.

p115 The test >= in the string programs could easily be replaced with = the procedure starts at 0 and increases the value of pos at each step.

p115 In the second last paragraph of Section 3.1.2, the last sentence should read "... and then calls the helper (Program 3-2)."

p120 Program 3-10: ``first character differs from last character---remove is.

p122 (log x) is used without introduction in the answer to Ex. 3-8, and does not appear in the Scheme Summary.

p123 ``position pos is the one at position pos+k''

p124 Remove the question mark in the first sentence of paragraph three.

p127 The --- should not appear in the result of display.

p129 Should the quote be ``Friends, Romans, countrymen, lend me your ears''?

p134 ``generalized procedure" is used without definition or glossarizing.

p135 ``anonymous procedure" is used without definition or glossarizing.

p136 The second argument to with-output-to-file should be a thunk:

(with-output-to-file "myfile.dat"
  (lambda () (display "Hello, world!")))

p140 The let syntax definition shows only (let ((name value) body) while p142 (the correct version) shows multiple definitions.

p142 The let example:

  (let ((name 1 value1))
       ((name 2 value2))
       . . .
       ((namen valuen))
    body)
Should be:
  (let ((name1 value1)
        (name2 value2)
        . . .
        (namen valuen))
    body)

Chapter 4

p181 The hello, world! output should not have an exclamation point.

p181 Next line: "can still cannot" should be "still cannot"

p187 Second paragraph: ``This looks like a Scheme form, so we must quote...''

p193 The program for list-tail% should be:

(define list-tail%
  (lambda (x n)
    (if (= n 0)
      x
      (list-tail% (cdr x) (sub1 n)))))

p195 equal?% assumes its arguments are either pairs, numbers, strings, symbols, or null. It returns #f if its arguments are different types only because (and (null? a) (null? b)) only returns #t if both a and b are null. Thus the text is misleading, if not incorrect.

p196 After definition of member%, the line ``which uses eqv? instead.'' is out of place, as a result of an autofilled comment!

p219 There should only be one argument to add-em:

(define add-em
  (lambda (nums)

p226 The list of Scheme primitives introduced should include list and list?.

Chapter 5

p235 (define x (make-box 30)) should be (define b (make-box 30)).

p243 append!% is never defined---it should be append! (which is not indexed).

p248 equal?% is not consistent with earlier implementation.

p250 In Ex. 5-12, the answer is incorrect. See Appendix A errata.

p256 In Ex. 5-16, the answer:

  (let ((temp a))
    (set! a b)
    (set! b c)
    (set! c temp))
should be
  (let ((temp a))
    (set! a c)
    (set! c b)
    (set! b temp))

p262 line 2: ``does not exist" should be ``is not seen".

p270 Ex. 5-18: the static link for alphonce_0 should point to user-env and the dynamic link to gaston_0.

p275 Oops: n^2 = (n-1)^2 + (2n-1).

p281 fl on lambda in Figure 5-26.

p283 fl on lambda in Figure 5-27.

p284 fact-helper should point to the procedure whose parameters are count and acc.

p284 The static and dynamic link of frame let1 should both point to the let0 frame.

p287 Figure 5-30. The parameters should be (*g0*) in the first anonymous procedure at top. The binding of fact-helper in the let_1 frame should point to the procedure with parameters (n acc).

p294 keywords: ``identity'' is missing

p294 Scheme features: list-set! is missing

p296 Self-Assessment Question 3: the answer should be (5 2), not ((5 2) 4), which is the value of b.

p297 Self-assessment Question 7 should ask: ``What are the values of the last two forms.

p297 Self-assessment Question 6, the code for romulus should be:

(define romulus 
  (lambda (n) 
    (letrec 
      ((helper 
         (lambda (m x)
           (if (< m n)
             (helper (add1 m)
               (if (> (remainder m 5) 3)
                 (+ x m)
                 x))
             x))))
      (helper 1 0))))

Chapter 6

p318 In the answers: the figure showing the snapshot of the two separate frames for the two invocations of make-dispenser, the title of the frames should be make-dispenser_0 and make-dispenser_1 instead of any-list_0 and any-list_1.

p318 line last-2: A look at any standard keyboard

p321 2nd last paragraph: ``the key can be a symbol, a number, or a character''. Strings do not work as keys in the case form.

p325 In Section 6.3,the snapshot has two errors: first, there is a stray arrow from nowhere pointing into the box let_0; second, the parent arrow from the procedure that is the value of account should point to the frame let_0.
The snapshot is the result of (account 'make 'lucien 100).

p333 Program 6-11: The withdraw method should actually reduce the amount! (set! balance (- balance amount))

p340 keywords: ``method'' is missing

p340 special forms: class should be define-class.

p341 Problem 4: the last line should be:
(a-box 'address)->4321

p342 In Self-Assessment Question 2, the code uses the wrong case syntax in bar.

p342 The answer to Self-Assessment Question 2, on p725, is the snapshot ``while evaluating the last form'', not ``after evaluating the following forms''.

Chapter 7

p356 command in the EBNF for test should be dream-command

p357 Program 7-4: Every occurrence of expr should be n-expr.

p359 In its definition of tree, the glossary uses descendant and ancestor without definition. The edges (lines connecting nodes) in a tree have a direction, going from a node to its subtree. A direct descendant of a node is a node directly connected to the node at the end of an edge. A direct ancestor is the node at the beginning of an edge. The President is the direct ancestor of the VP Sales, who is the President's direct ancestor. A node is a descendant of another if it lies in one of the node's subtrees. Likewise a node A is an ancestor of a node B if B is in A's subtrees.

p361 In Ex. 7-9, the answer should be:

("President"
  ("VP Sales"
    ("Sales Dir East")
    ("Sales Dir West")
    ("Sales Dir International"))
  ("VP Development"
    ("Dir, Software Division")
    ("Dir, Hardware Division")))

p361 The variable operation "accessing a variable's value" should say ``returning its value'' instead of mutating its value.

p374 the argument~form should be the parameter~form in the macro section

p382ff In the EBNF for Scheme, form should be simple-form.

p384 self-eval just mentioned in passing, in the section on Procedures.

p386 The ADT uses set-binding!, def-binding! while the code uses set-binding and def-binding.

p406 In the keywords, subtree and compiler are missing. The ``Scheme Features Introduced in This Chapter'' is missing. It should contain the special forms, cond and define-macro.

p408 fls in Figure 7-12: Trees.scmfl, Dream.scmfl

Chapter 8

p415 At the first use of columns: ``the columns in this example are the sets of names, addresses, and balances, respectively.''

p432 table-find is not in the ADT for table.

p443 The code for insertion sort does not conform to the trace shown above. The following code does.

 (define insertion-sort
   (lambda (lst compare)
     (insertion-sort-h lst compare '()))))
 (define insertion-sort-h 
   (lambda (lst compare res)
     (if (null? lst)
       res
       (insertion-sort-h
         (cdr lst)
         (insert-in-order
           (car lst)
           res
           compare)))))
  (define insert-in-order
    (lambda (item lst compare)
      (if (null? lst)
        (cons item '())
        (if (eqv? (compare item (car lst)) 'greater-than)
          (cons (car lst) 
            (insert-in-order item (cdr lst) compare))
          (cons item lst)))))

Chapter 9

p476 bst-insert! should alter the key:

 (bst-node-value t)
should be
 (set-bst-node-value! t v)

p477 Exercise 9--8 is unclear. ``Balanced'' means not only that each node has two subtrees, but also path lengths differ by only 1.

p480 In Figure 9-5 mytree should have value of a tree as on p478. The static links are reversed; they should point to channel to the user frame. Also, the frames are in the old format: the name of frame should not be in a box on top, the resume point is not in gray, and there should be no continuation point.

p491 Figure 9-10 should include the name smaller pointing to the same cell as info, in the After portion, reflecting the operation of quicksort! when the value of the data in info is less than the value of the data in the first element in smaller.

p492 The first line under the box labeled ``Accessors" should be:
(vector-refany-list k)
(the ``k" was omitted). list->vector has the wrong arguments. It should be:
(list->vectorany-list). Its description is wrong also, and should be replaced with: ``Make a vector containing the elements of any-list.

p492 vector should be: (vector item1 item2 ... itemn) Make a vector containing the evaluated arguments in the given order.

p492 vector-set!: its action should be
Set the kth element of vector to obj.

p497 Procedure binary-search has a few errors. It should be:

(define binary-search
  (lambda (v low up item compare)
    (if (> (- up low) 1)
      (let ((half (ceiling (/ (+ low up) 2))))
        (case (compare (vector-ref v half) item)
          ((less-than) (binary-search v half up item compare))
          ((equal-to) 'success)
          ((greater-than) (binary-search v low half item compare))))
      (if (or (eqv? (compare (vector-ref v low) item) 'equal-to)
              (eqv? (compare (vector-ref v (add1 low)) item) 'equal-to))
        'success
        'failure))))

p519 keywords: ``pivot'' is in there twice. ``queue'' is not at all. not clear why ``insert'' is, and not ``remove''.

Chapter 10

p535 No (?? right turn ?? red) does not match (I want to make a right turn on a red light).

> (match? '(?? right turn ?? red) 
    '(I want to make a right turn on a red light))
#f

p553 In Figure 10-7 there is an fl on philosopher.

p556 The foo-corp rules are wrong.

  ((indirectly-supervises ?x ?y) 
   (indirectly-supervises ?x ?z) (supervises ?z ?y))
should be:
  ((indirectly-supervises ?x ?y) 
   (supervises ?z ?y)(indirectly-supervises ?x ?z))

p558 extract in forward should be:

(define extract 
  (lambda (qry answers)
    (filter
      (lambda (answer)
        (or 
         (match? qry answer)
         (match? answer qry)))
      answers)))

p560 forward1 should use rule-lhs instead of car and rule-rhs instead of cdr:

  (use-rule
    (lambda (single-rule)
      (for-each 
        (lambda (fact)
          (ground fact (car (rule-rhs single-rule))
            (cdr (rule-rhs single-rule)) (rule-lhs single-rule) '()))
        old))))

p572 The problem about evaluate-logical is the same as evaluate just above.

Chapter 11

p583 #xA is not #b01000001, (char->integer #
A)
is.

p585 The definition of read-digit should be as follows, reversing the order of the last two lines:

(define read-digit
  (lambda ()
    (let ((ch (read-char)))
      (if (char-numeric? ch)
        (- (char->integer ch) (char->integer #\0))
	-1))))

p600 fls on source in Figure 11-8.

p603 sym1 should be sym_1 in the description of define-symbols.

p605 ``effective address'' is used before its definition.

p606 The comment: put #t in r3 in Program 11-8 should say put true in r3.

p607 Sec 11.3.4, first paragraph: ``the cell at location #x1002 will be used'', not 105.

p607 In Program 11-9, the label on the last line is called "loadinst", but referred to [in the 2nd instruction] as "loadinstr".

p612 first line: ``The gap code for the tail-calling version of xfoo'' should be ``The gap code for xfoo'' since xfoo is tail-calling.

p615 Figs 11-10 and 11-11 contains fls. The value of 108 in location 1002 should be 1008.

p615 There are fls in Figure 11-15.

p627 There is no reason for a black box to appear in the Destination bitmap on the right side of Figure 11-15.

Chapter 12

None, yet.

Appendix A

p690 In Ex. 1-21, the answer should be:
(discr 7 2 0)->4, which looks correct. On the other hand, (discr 7 2 1)->32, which is wrong; the correct answer is~-24. This example demonstrates that a single test case might happen to ``luck out''. Therefore, you should always test a procedure with more than one set of data.

p691 The answer to Ex. 1-34 should probably be:

(define postage
  (lambda (weight)
    (if (< weight 30) 15
      (if (and (>= weight 30) (<= weight 49)) 17
        (if (and (>= weight 50) (<= weight 99)) 22
          (/ weight 4))))))
This interprets x to y grams as including y grams. But the issue about fractions still matters: 49.5 grams still results in a postage of 12.375 cents. The Post Office probably intended something between 17 and 22 (not 15!).

p693 Ex. 2-3. The fourth droid is actually evaluating (power 7 0).

p693 Ex. 2-4. The analysis and therefore the code only applies when b is nonnegative.

p695 In Ex. 2-12, the answer should be:

(define sum-digits
  (lambda (x)
    (if (= x 0) 
      0
      (+ (remainder x 10) 
         (sum-digits (quotient x 10))))))

p697 In the table answering Ex. 2-25, the entry 12 0 should show undefined since the procedure will loop forever!

p699 The procedure arithmetic for Ex. 3-11 should not have (newline) in its last line, otherwise the result would be the void value.

p706 In Figure A-6, the Scheme code above (b) should be (a (b . c) d) and above (c) it should be ((a . b) . (c . d)).

p707 population-find contains error-testing code even though the specification in Exc. 4-22 states that the named city can be assumed to be in the list.

p714 In Ex. 5-12, the answer is incorrect, and dates from the time when assoc returned the null list when it couldn't find the key. assoc returns #f when it fails. The argument holds if we replace ``null'' with ``the value #f''.

p715 In Ex. 5-16, the answer:

  (let ((temp a))
    (set! a b)
    (set! b c)
    (Set! c temp))
should be
  (let ((temp a))
    (set! a c)
    (set! c b)
    (set! b temp))

p716 Ex. 5-18: the static link for alphonce_0 should point to user-env and the dynamic link to gaston_0.

p722 In the answers: the figure showing the snapshot of the two separate frames for the two invocations of make-dispenser, the title of the frames should be make-dispenser_0 and 1 instead of any-list_0 and 1.

p722 In Ex. 6-13, the answer should be:
(joel-symbol-equal? 'symb2 'symb2) correctly returns #t.
(joel-symbol-equal? 'symb1 'symb2) correctly returns #f.
(joel-symbol-equal? 'symb2 'symb1) incorrectly returns #t.

p725 Self Assessment for Chapter 6, number 2. The answer in Figure A-17 is the snapshot ``while evaluating the last form'', not ``after evaluating the following forms''. To answer the question as given, the frame for foo_0 should not be there, and the dynamic link for bar_0 should be null (ground).

p727 In Ex. 7-9, the answer should be:

("President"
  ("VP Sales"
    ("Sales Dir East")
    ("Sales Dir West")
    ("Sales Dir International"))
  ("VP Development"
    ("Dir, Software Division")
    ("Dir, Hardware Division")))

p727 In Ex. 7-13, the answer should be:

call dream-expr-eval: (times 2 (times 3 5))
| call dream-expr-eval: 2
| return from dream-expr-eval: 2
| call dream-expr-eval: (times 3 5)
| | call dream-expr-eval: 3
| | return from dream-expr-eval: 3
| | call dream-expr-eval: 5
| | return from dream-expr-eval: 5
| return from dream-expr-eval: 15
return from dream-expr-eval: 30
The answer given in the text was produced by a Scheme evaluator that evaluated the RIGHT side of the expression first! The above answer correctly evaluates LEFT to RIGHT as we agreed would be the convention.

p737 In the answer to Ex. 9-2, scan-lst should use eqv? instead of eq?.

p737 In the answer to Ex. 9-6, the Scheme list representation of the tree should be

(13 () ; key value
    (10 () ; key value
        () ; no left
        (12 () () ())) ; right node, leaf
    (22 () ; key value
        (16 () () ()) ; leaf
        ()) ; no right
)
Ignoring values:
(13 ; key
    (10 ; key
        () ; no left
        (12 () ())) ; right node, leaf
    (22 ; key
        (16 () ()) ; leaf
        ()) ; no right
)

p746 The last two digits of the MRI instructions are in error.

0040000B
0050000C
8E600405
02600006
00400009
04000007
0040000A
9F400000
A0000000
0000002E
0000004D
0000000A
0000000C

Appendix B

p756 ``A Scheme programmwer'' should be ``A Scheme programmer''

p763 eq?, eqv?, and equal? use the wrong font for their arguments.

p763 last-pair is only in the appendix.

p763 In the last line, the space between ``list'' and ``k'' was omitted.

p764 Several Scheme procedures are presented incorrectly:
(list-set! listk v) instead of (list-set! list k v);
the same error occurs in list-ref and first-tail.
Also, it is equivalent to (set-car! (list-tail list k))---the last ) is missing.

p764 The presentation of first is flawed. It is equivalent to
(list-ref (list-tail list 0))---the last ) is missing.

p767 (string obj) should be (string? obj).

p769 We have two identical lines
(input-port? obj) primitive
One of the lines should be output-port?.

p772 In the last entry, (trace proc ...) should be (untrace proc ...).

Index

append! should be indexed on p243.

hexadecimal is not indexed in Chapter 11.

The first two sentences in the description of member and its related procedures should be replaced by:

These procedures return #f if obj is not a member of list; otherwise, the return result is the tail (as with list-tail of list whose car is equal to obj.

subst should not be indexed as a primitive.

Chapter 7 introduces cond but it does not appear in the Scheme summary.