"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 Email: Peter.Norvig@East.Sun.COM Sun Microsystems Laboratories Tel: (508) 442-0508 Two Elizabeth Drive Fax: (508) 250-5067 Chelmsford MA 01824-4195 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 141: Line 6: change: (sort (find-all goal *ops* :test #'appropriate-p) #'< to: (sort (copy-list (find-all goal *ops* :test #'appropriate-p)) #'< 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 187: In the definition of pat-match-abbrev: change (setf (get symbol 'expand-pat-match-abbrev) expansion) ==> (setf (get symbol 'expand-pat-match-abbrev) (expand-pat-match-abbrev expansion)) 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 249: Line -1: change: (d (u / v) / d x = (u * (d v / d x) - v * (d u / d x)) to (d (u / v) / d x = (v * (d u / d x) - u * (d v / d x)) Page 250: line 7: change: (d (exp u) / d x = (exp u) * (d u / d x)) to: (d (e ^ u) / d x = (e ^ u) * (d u / d x)) 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 475: (the first bulleted item): Line 7: change "1, 2, and 3" ==> " 1, 2, 3 and 6." Line 8: change "4" ==> "4 and 5" Line 9: change "five" -> "six". 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 607: In the definition of legal-moves: [bug] change (remove-if #'(lambda (move) (not (legal-p move player board))) all-squares)) ==> (loop for move in all-squares when (legal-p move player board) collect move)) Page 614 Line -14: (counting figure etc) change "advanatage" ==> "advantage" 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 702: Line -7: "accumlator" -> "accumulator". Page 721: Line 1 of 21.4: change "The simplest is the determiner" ==> "The simplest is the article" 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 775: In the definition of interp-begin: [bug] change (if (null (rest body)) val (interp-begin (rest body) env cc))))) ==> (if (null (rest body)) (funcall cc val) (interp-begin (rest body) env cc))))) Page 778: Part of answer to 22.6 appears in wrong place. Should be on page 781. Page 784: line -9: "of the stack" ==> "off the stack" 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 815: Line -11: change "(READ NEWLINE)" ==> "(SCHEME-READ NEWLINE)" Page 816: Line 18: [bug] 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 829: In definition of convert-numbers: [bug] add "x" in two places: (cons (setf (car x) (convert-numbers (car x))) (setf (cdr x) (convert-numbers (cdr x)))) (symbol (or (convert-number x) x)) (vector (dotimes (i (length x)) (setf (aref x i) (convert-numbers (aref x i))))) ==> (cons (setf (car x) (convert-numbers (car x))) (setf (cdr x) (convert-numbers (cdr x))) x) (symbol (or (convert-number x) x)) (vector (dotimes (i (length x)) (setf (aref x i) (convert-numbers (aref x i)))) x) Page 837: Line 5: change "veriables" ==> "variables" 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 868: Line -13: change "effect" ==> "affect" 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: Add following 2 lines 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 sans-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."