"Paradigms of AI Programming" Errata Sheet Peter Norvig The following bugs and typos have been discovered so far, and will be fixed in the next printing of the book. If you discover any additional errors, please send them to me, so that we can make the next printing as error-free as possible. Many thanks to all those who have contributed so far, and thanks in advance to those who will add to this list. Peter Norvig Tel: (508) 671-0508 Sun Microsystems Laboratories Fax: (508) 671-0624 Two Federal Street Email: Peter.Norvig@East.Sun.COM Billerica MA 01821 USA ============================================================================== Page 5: Line -2: Change "y = a * x + 3" ==> "y=a*x+3" that is, remove spaces. Page 9: Paragraph 3: "In evaluating an to" ==> "In evaluating an" Page 29: "forseen" ==> "foreseen" Page 39: Line -11: "grammers" ==> "grammars" Page 57: x++ ==> ++x Page 69: Change "T" to "t" two times: "(null nil) => T" ==> "(null nil) => t" "(listp x) => T" ==> "(listp x) => t" Page 70: In the diagram, change "(ONE TWO)" ==> "(ONE . TWO)" Page 87: (end pp 2) "cerrer" ==> "cerror" Page 90: A parenthesis is in the wrong place in test-ex: (assert (equal (ex 'x 0)) 0)) ==> (assert (equal (ex 'x 0) 0))) Page 96: (middle) "inobtrusive" -> "unobtrusive" Page 99: line 5: "signifigance" ==> "significance" Page 102: Could use more space after exercise 3.8 Page 106: (defun length-r ...) should be in typewriter font. Page 130: pp 1: line 11: change "eventualy" ==> "eventually" Page 166: (line -5) "remains" ==> "remains an" Page 159 and 182: change "(if (and (eq bindings no-bindings)) nil bindings)" ==> "(if (eq bindings no-bindings) nil bindings)" Page 169: Exercise 5.18 is actually the answer to exercise 5.17. Page 185: "succesful" ==> "successful" Page 186: middle: change "making the substitutions implied by the binding list into the code and then evaluating it" ==> "evaluating the code with the bindings implied by the binding list." [bug] Also replace definition of match-if with: (defun match-if (pattern input bindings) "Test an arbitrary expression involving variables. The pattern looks like ((?if code) . rest)." (and (progv (mapcar #'car bindings) (mapcar #'cdr bindings) (eval (second (first pattern)))) (pat-match (rest pattern) input bindings))) Page 197: (footnote) "any integration problem" ==> "the same class of integration problems" Page 198: Map needs route from K to I. Page 198/199: Sentence ends in the middle. Add "successors to a state. The cost for a state is the air distance to the destination city." Page 202: Missing text at bottom of page: (defun is (value &key (key #'identity) (test #'eql)) "Returns a predicate that tests for a given value." #'(lambda (path) (funcall test value (funcall key path)))) The {\tt path-saver} function returns a function that will take a path as an argument and generate successors paths. {\tt path-saver} takes as an argument a successor function that Page 204 (middle) "exitting" == "exiting" Page 206: should have an arrow from 2 -> 3. Page 207: Tree should have arrows, not undirected lines Page 209: (old) ==> (old nil) Page 212: Two arrows missing in diagram: A A C BC <-> BC and AB ^ | v C AB Page 215: Exercise 6.10[h] ==> Exercise 6.10[m] Exercise 6.13[m] ==> Exercise 6.13[d] Exercise 6.14[m] ==> Exercise 6.14[d] (line -1) remove the two commas after "answer" and "found" Page 219: Epigraph goes into roman font. Page 225: Line 2: change "exercise 7.5" ==> "exercise 7.3" Also Section 7.2 Line 2: change "it is good example" ==> "it is a good example" Page 234: Exercise 7.2[h] ==> Exercise 7.2[d] Page 228: Line 5,6: change "The datastructure op" ==> "The datastructure exp" change "like isolate, it assumes" ==> "unlike isolate, it assumes" and in the definition of in-exp change "(listp exp)" ==> "(exp-p exp)" Page 245: (end of pp 1) After "(an inexact number)." add "Another problem is that -2 is also a square root of 4, and in some contexts it is the correct one to use." Page 248: (pp 2) Change "and we could not use a single equality" to "and it would be wrong to arbitrarily choose one of these values." Page 257: change "for n/=1" ==> "for n /= -1 change "for n=1" ==> "for n = -1" and change "but it is log(u) for n = 1. ==> "but it is log(u) for n = -1." Page 274: "Exercise 9.8" ==> "Exercise 9.4" Change $n+1$ ==> n+1 (in math mode). Page 277: Change "compiler!versus ... versus compiler." ==> "compiler versus interpreter." Page 280: Change "field in undefined" ==> "field is undefined" Page 293: correct the indentation of profiled-fn, i.e. shift the "multiple-value-prog1" form 2 spaces to the left Page 295: correct the indentation of test-it, i.e. shift the "time" form 1 space to the left Page 299: Second text line: Change "exxpression" ==> "expression" Page 301: line 3: change "and a list of variable bindings." ==> "and a continuation for generating the code if the test passes. The list of current variable bindings is held in the special variable *bindings*." Page 309: Exercise 9.11[d] ==> Exercise 9.11[h] Page 310: (answer 9.4) Two uses of "100" should be subscripts: In LaTeX, change $T_100$ ==> $T_{100}$ and $F_100$ ==> $F_{100}$ Also, change "Knuth'sKnuth" ==> "Knuth" Also, in Answer 9.4: "(fib n)" ==> typewriter font Page 314: computaion ==> computation Page 329: 2nd pp: "parts of the answer" ==> "part of the answer" Page 367: end 1st pp: Change "which searches for solutions breadth-first." ==> "which must keep all solutions in memory at once." Page 391: "binsings" ==> "bindings" Page 401: Change: (IF (UNIFY! ?ARG1 ?ITEM) (IF (UNIFY! ?ARG2 (CONS ?ARG1 (?))) (FUNCALL CONT)))) instead of: (LET ((?ITEM (?))) (IF (UNIFY! ?ARG1 ?ITEM) (IF (UNIFY! ?ARG2 (CONS ?ITEM (?))) (FUNCALL CONT)))) ==change-to==> (LET ((?ITEM (?))) (IF (UNIFY! ?ARG1 ?ITEM) (IF (UNIFY! ?ARG2 (CONS ?ITEM (?))) (FUNCALL CONT)))) when it could compile to the more efficient: (IF (UNIFY! ?ARG2 (CONS ?ARG1 (?))) (FUNCALL CONT)) Page 417: [bug] change "(cons var (?))" ==> "(cons (deref var) (?))" Page 429: (defmacro with-compilation-unit (&body body) ==> (defmacro with-compilation-unit (options &body body) And 11 lines down, change: (with-compilation-unit ==> (with-compilation-unit () Also, add 429 to the index entry for with-compilation-unit Page 435: Delete "once and for all" from 1st pp, section 13.1 Page 443: box could be better Page 452: [bug] change to: (defmethod problem-combiner :around ((prob beam-problem) new old) (let ((combined (call-next-method))) (subseq combined 0 (min (problem-beam-width prob) (length combined))))) Page 461: 3rd pp, line 5: "paricular" ==> "particular" Page 463: line -1: change the double arrow "<=>" to a right arrow "=>" Page 464: under "Decidability" bullet: change "follows from the axioms" ==> "can be derived from the axioms" Page 482: 10 lines from the top, (?fn (subst-bindings #:bindings6369 `?fn))) should be indented 8 spaces further: (let ((?x (subst-bindings #:bindings6369 '?x)) (?fn (subst-bindings #:bindings6369 `?fn))) Page 529: [bug] The Lines beginning "(b " and "(c " in rat+rat should be: (b (rat-denominator x)) (c (rat-numerator y)) Page 533: The table does not fit on the page; the entries below "Previously Defined Functions" have been left out. Since this section is not crucial, I recommend just deleting the "Previously Defined Functions" line. Page 544: (temp patient> 98.6) ==> (temp patient > 98.6) That is, add a space before the >. Page 549: In fourth line of check-conditions, change conditions ==> kind That is, (warn "Rule ~a: Missing ~a" rule-num conditions) ==> (warn "Rule ~a: Missing ~a" rule-num kind) Page 558: "Pearl 1989/1978" ==> "Pearl 1989" Page 564: Change "ouput" ==> "output" Page 585/586: "After constraint propagation ... ZV=[-]" should be in monospace font. Page 596: Add epigraph: "In the beginner's mind there are endless possibilities; in the expert's there are few." -- Suzuki Roshi, Zen master Page 633: Change "In this, case..." ==> "In this case" Page 637: middle of page: Add more space after italic "mobility", i.e. "mobilityand" ==> "mobility and" Page 638: line -2: "depends is evaluated" ==> "is evaluated" Page 644: "lay" ==> "lie" Page 676: [bug] In the definition of "meaning", change (best-score (tree-score (first trees))) ==> (best-score (if trees (tree-score (first trees)) 0)) Page 680: line 1: "defintion" ==> "definition" Page 685: line 9: "that is noun phrase" ==> "that is a noun phrase" Page 700 and 932: change "Natassja Kinski" ==> "Nastassja Kinski" Page 748: line -3: "Svartik" ==> "Svartvik" Page 758: [bug] (interp (fourth x)) env ==> (interp (fourth x) env) Page 763: [bug] (interp (fourth x)) env ==> (interp (fourth x) env) [bug] also change to: (defun scheme-macro (symbol) (and (symbolp symbol) (get symbol 'scheme-macro))) Page 778: Part of answer to 22.6 appears in wrong place. Should be on page 781. Page 785: In table, add new line (at end): FN fn Create a closure from argument and current environment, and push it on the stack Also, add to description of CALL (on new line) the text: n is the number of arguments passed. Page 787: Change (gen 'call (length (rest x))))))))) ==> (gen 'CALL (length (rest x))))))))) Page 789: Change (let ((a 0.0) (b 0.1)) (let ((c 1.0) (d 1.1)) (let ((e 2.0) (f 2.1)) (+ a b c d e f)))) ==> (let ((a 2.0) (b 2.1)) (let ((c 1.0) (d 1.1)) (let ((e 0.0) (f 0.1)) (+ a b c d e f)))) Page 796: Change "CALL 1" ==> "CALLJ 1" Page 822: 1st line of text: "unforgable" ==> "unforgeable" Page 823: [bug] change to: (defparameter *primitive-fns* '((+ 2 + true nil) (- 2 - true nil) (* 2 * true nil) (/ 2 / true nil) (< 2 < nil nil) (> 2 > nil nil) (<= 2 <= nil nil) (>= 2 >= nil nil) (/= 2 /= nil nil) (= 2 = nil nil) (eq? 2 eq nil nil) (equal? 2 equal nil nil) (eqv? 2 eql nil nil) (not 1 not nil nil) (null? 1 not nil nil) (cons 2 cons true nil) (car 1 car nil nil) (cdr 1 cdr nil nil) (cadr 1 cadr nil nil) (list 1 list1 true nil) (list 2 list2 true nil) (list 3 list3 true nil) (read 0 read nil t) (write 1 write nil t) (display 1 display nil t) (newline 0 newline nil t) (compiler 1 compiler t nil) (name! 2 name! true t) (random 1 random true nil))) Page 838: line -1: change "transformaing" ==> "transforming" Page 839: change the two lines: > (div xyzzy 1) Error: XYZZY is not a bound variable ==> > (div 'xyzzy 1) Error: The value of NUMBER, XYZZY, should be a number Page 843: fill-loop-template has two extra )'s at end Page 862: [bug] In reduce-list, change the loop to: (loop repeat (- end (if init-p 1 2)) while seq do (setf result (funcall fn result (funcall-if key (pop seq))))) Page 881: defmacro binding-of ==> defun binding-of Page 890: top line "preferably" ==> "preferable" Page 893: insert "()" in (with-compilation-unit () (sys-action module system action)) Page 897,898: In "mget *", the space is too small Page 899/900: Add: Case-Based Reasoning cs.umd.edu /pub/schank/icbr Blackboard System Shell dime.cs.umass.edu /gbb/ Scheme ftp.cs.umb.edu /pub/scheme/umb-scheme-2.5.tar.Z Page 913: line 1: "Svartik" ==> "Svartvik" Page 918: In Winston and Horn, change "(1988)" ==> "(1989)" Page 921: delete the line "M, 60, 678" Page 929, 942: It would be nice (but not essential) if the following 2 lines could be added to the index: global variable, see special variable special variable, 51, 93, 888, 889 Page 930: put handler-case index entry on separate line Page Back cover: (University of California at Berkeley) ==> (Sun Microsystems Laboratories) Page In general: several people have complained about the "computer" font. Here are two of the comments: "The san-serif font that you use for computer printout does not mix well with the font for the body of the book. The spacing between normal text and computer text is comparable to the gaps between adjacent computer-text characters, and is confusing on first reading. The most telling example I've seen so far is the last line of p 53 where it seems there are words like explicitnil overwhen .." "There seems to be a problem with the spacing of in-text mono-space font (TeX's \tt), see the lists on page 220 for example." ============================================================================== The following have been reported, but have not been incorporated for one of two reasons. (1) Some I consider too unimportant to fix. I may change my mind if others have the same complaints. (2) Others are too expensive to fix. There is a cost for each page that is changed; it is not possible to just add new material without figuring how to change the surrounding pages. Certainly if there is a 2nd edition (as opposed to a 2nd printing), then some of these should be addressed. Page 13: "The last expression" ==> "The value of the last expression" Page 52: (if ...) "is the value." Also Page 53. Page 55: /* Pascal */ ==> { Pascal } or (* Pascal *) Page 68: dot notation used before explained. Page 74: gethash references get, which was not introduced. Page 92: incf, decf could be used in the definition of bank-account Page 114, 129: Change doc string for appropriate-p to: "An op is appropriate to a goal if the goal is in the op's add-list." Page 146: 2nd para in 4.20 is probably not what you want to say about NP. at least add "as the size of the problem grows LINEARLY." Page 182: change "of symbols like ?*" ==> "of symbols like ?is" Page 230: change "~%~a~{~% ~{ ~a~}~}~%" ==> "~%~a~{~% ~{ ~a~}~}~%" i.e. two blanks instead of one Page 234: line -3 n unknowns ==> $m \le n$ unknowns. Page 239: Para 4: survive ==> survived. Page 259: section 8.7 cite with name (..) consistently.. e.g. Moses (1975) ==> Moses 1975 There is a better book by Geddes Labahn and Czapor (1992) that covers this stuff. Page 285: in the definition of "sieve" change "(mod x (headpipe))" ==> "(mod x (head pipe))" Page 315: perhaps remove "the following" since you have another sentence next.. Page 437: Need some guard against depositing a negative amount. Page 465: 2nd pp, line 2: "was" ==> "is" Page 466: "1982" ==> "(1982)" Page 734: "present-plural" in the call to verb might be better named "3rd-person-sing" Page 811: line -11: "less" ==> "fewer" Page 826: Deutsch 1980 ==> Deutsch (1980). Page Chapter 1: Certain basic functions (listp, atom) are not presented. Page 919: I'd prefer for index entries like *state* to sort under S. Page 924: the entry for "Common Lisp" could be omitted. Page Bibliography: The editor tag is missing on various "Readings in" entries Whenever there's a label including an "et al." a backslash is missing after it in the source making TeX to produce an inter-sentence spacing. Probably this is just an error in the BibTeX-style. See pages 234, 382, and 383 for example. 3. In section 25.14 about "Problems with Macros" your example pop-end is probably better written as a function. It does not violate the usual evaluation rules, and this was just explained to be a mistake, so it's probably not a padagogically valuable example. 4. Its great to have some examples for setf methods included in section 25.14, but the transition from the pop-end macro to a setf method for last on page 883 is not very obvious. In addition, it would be nice to shed some more light on setf methods: they are called methods but actually they are macros. In ANSI Common Lisp the confusion is even greater: Now there are 4 ways to define setf "methods" (defsetf ...) (define-setf-method ...) (defmethod setf ...) (defun (setf ...) ...) Why not including an extra section on setf methods? 3. On page 272 your write: "The trick is that memoize takes this new function and makes it the symbol-function value of the function name. This means that all the references in the original function will now go to the new function ..." Essentially, this is the trick, but someone who is not that familiar with closures and the difference between symbols and local variables might wonder how the memoized version of fib does call the unmemoized version of fib. As you explained, the recursive call to fib in the definition of fib uses the symbol fib, so this compiles into a fetch of the symbol-function of fib (which results in the memoized version), but the call "(funcall fn x)" in the memoized version uses the function bound to the local (lexical) variable fn which is the original version. I think you should explicitly explain this, and maybe add a reference to section 3.16 (closures) and to the end of section 3.17 (special variables) which explains symbol-value which is analog to symbol-function. 4. Unfortunately, in the subsection about Queues (Page 341ff) you haven't given a concise and abstract definition of Queues, and your implementation of ``dequeue is a bit awkward in that it returns the queue instead of the dequeued element. I suggest changing this to be consistent with the operation ``pop'' for stacks which is nothing but a ``dequeue'' for LIFO-Queues (see the article from Norvig and Waters in LISP Pointers). In addition, at least give a hint that it might be more efficient to use vectors instead of lists for implementing queues -- after all it is a chapter about efficiency issues. A reference to your LISP Pointer article might be useful too.