norvig / paip-lisp

Lisp code for the textbook "Paradigms of Artificial Intelligence Programming"

This is an open-source repository for the book Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig (1992), and the code contained therein. The copyright has reverted to the author, who has shared it here under MIT license. On the list of most influential books for programmers. As seen on TV. See also: errata, comments, retrospective.

The book is available in these formats:

• we're generating ebooks - epub and pdf - from the markdown files, see Releases
• scanned pdfs
  • 4th edition, 1998: higher resolution, better OCR, smaller file thanks to better compression
  • 6th edition, 2001: newer printing
• text: PAIP.txt (from OCR'ing the scanned pdf, containing many errors)
• a source epub: see releases for a cleaned up version downloaded from Safari (much cleaner than the scanned versions)
• and chapter?.md markdown files:

Table of Contents

• Paradigms of Artificial Intelligence Programming
  • Front matter
  • Preface
• Part I: Introduction to Common Lisp
  • 1 Introduction to Lisp
  • 2 A Simple Lisp Program
  • 3 Overview of Lisp
• Part II: Early AI Programs
  • 4 GPS: The General problem Solver
  • 5 Eliza: Dialog with a Machine
  • 6 Building Software Tools
  • 7 Student: Solving Algebra Word Problems
  • 8 Symbolic Mathematics: A Simplification Program
• Part III: Tools and Techniques
  • 9 Efficiency Issues
  • 10 Low-Level Efficiency Issues
  • 11 Logic Programming
  • 12 Compiling Logic programs
  • 13 Object-Oriented Programming
  • 14 Knowledge Representation and Reasoning
• Part IV: Advanced AI Programs
  • 15 Symbolic Mathematics with Canonical Forms
  • 16 Expert Systems
  • 17 Line-Diagram Labeling by Constraint Satisfaction
  • 18 Search and the Game of Othello
  • 19 Introduction to Natural Language
  • 20 Unification Grammars
  • 21 A Grammar of English
• Part V: The Rest of Lisp
  • 22 Scheme: An Uncommon Lisp
  • 23 Compiling Lisp
  • 24 ANSI Common Lisp
  • 25 Troubleshooting

The Lisp Files

The Lisp code files are listed here:

CH	Filename	Description
-	examples.lisp	A list of example inputs taken from the book
-	tutor.lisp	An interpreter for running the examples
-	auxfns.lisp	Auxiliary functions; load this before anything else
1	intro.lisp	A few simple definitions
2	simple.lisp	Random sentence generator (two versions)
3	overview.lisp	14 versions of LENGTH and other examples
4	gps1.lisp	Simple version of General Problem Solver
4	gps.lisp	Final version of General Problem Solver
5	eliza1.lisp	Basic version of Eliza program
5	eliza.lisp	Eliza with more rules; different reader
6	patmatch.lisp	Pattern Matching Utility
6	eliza-pm.lisp	Version of Eliza using utilities
6	search.lisp	Search Utility
6	gps-srch.lisp	Version of GPS using the search utility
7	student.lisp	The Student Program
8	macsyma.lisp	The Macsyma Program
8	macsymar.lisp	Simplification and integration rules for Macsyma
9-10	auxfns.lisp	Auxiliary functions
11	unify.lisp	Unification functions
11	prolog1.lisp	First version of Prolog interpreter
11	prolog.lisp	Final version of Prolog interpreter
12	prologc1.lisp	First version of Prolog compiler
12	prologc2.lisp	Second version of Prolog compiler
12	prologc.lisp	Final version of Prolog compiler
12	prologcp.lisp	Primitives for Prolog compiler
13	clos.lisp	Some object-oriented and CLOS code
14	krep1.lisp	Knowledge Representation code: first version
14	krep2.lisp	Knowledge Representation code with conjunctions
14	krep.lisp	Final KR code: worlds and attached functions
15	cmacsyma.lisp	Efficient Macsyma with canonical form
16	mycin.lisp	The Emycin expert system shell
16	mycin-r.lisp	Some rules for a medical application of emycin
17	waltz.lisp	A Line-Labeling program using the Waltz algorithm
18	othello.lisp	The Othello playing program and some strategies
18	othello2.lisp	Additional strategies for Othello
18	edge-tab.lisp	Edge table for Iago strategy
19	syntax1.lisp	Syntactic Parser
19	syntax2.lisp	Syntactic Parser with semantics
19	syntax3.lisp	Syntactic Parser with semantics and preferences
20	unifgram.lisp	Unification Parser
21	grammar.lisp	Comprehensive grammar of English
21	lexicon.lisp	Sample Lexicon of English
22	interp1.lisp	Scheme interpreter, including version with macros
22	interp2.lisp	A tail recursive Scheme interpreter
22	interp3.lisp	A Scheme interpreter that handles call/cc
23	compile1.lisp	Simple Scheme compiler
23	compile2.lisp	Compiler with tail recursion and primitives
23	compile3.lisp	Compiler with peephole optimizer
23	compopt.lisp	Peephole optimizers for compile3.lisp

Running the Code

There is no single "application" to run. Rather, there is a collection of source code files, duplicating the code in the book. You can read and/or run whatever you like. Lisp is an interactive language, and you will need to interact with the code to get benefit from it. Some hints:

• You will need a Common Lisp interpreter/compiler/environment. Here's a discussion of the options.
• You will always need (load "auxfns.lisp").
• You will need (requires "file"), for the various instances of file that you want to use. (If requires does not work properly on your system you may have to alter its definition, in auxfns.lisp.
• The function do-examples, which takes as an argument either :all or a chapter number or a list of chapter numbers, can be used to see examples of the use of various functions. For example, (do-examples 1) shows the examples from chapter 1. Access this by doing (requires "examples").

Other resources

• I wrote a retrospective on the book in 2002.
• There is a nice Python version of the code, by Daniel Connelly at Georgia Tech, supervised by Ashok Goel.

paip-lisp's Issues

use common-lisp instead of lisp in code blocks

This way the syntax highlighting would be better in GitHub.

What do you think?

Errata in chapter 4

in the function

(defun achieve (state goal goal-stack) "A goal is achieved if it already holds, or if there is an appropriate op for it that is applicable." (dbg-indent :gps (length goal-stack) "Goal: "a" goal) (cond ((member-equal goal state) state) ((member-equal goal goal-stack) nil) (t (some #'(lambda (op) (apply-op state goal op goal-stack)) (find-all goal *ops* :test #'appropriate-p)))))

(dbg-indent :gps (length goal-stack) "Goal: "a" goal)
should be:
(dbg-indent :gps (length goal-stack) "Goal: ~a" goal)

Fix up Exercise and Answer lines

tags: scripts, grep, prettier markdown

Normalize e.g. from **Exercise 6**.**6** [**m**] to **Exercise 6.6 [m]**

error in code of chapter one in github pages book

(mappend #'(lambda (l) (list l (reverse l)))
((1 2 3) (a b c)))

should be

(mappend #'(lambda (l) (list l (reverse l)))
'((1 2 3) (a b c)))

Exercise character

In the print version each exercise starts with a monitor with a question mark. What would be the best replacement for this in the text file?

Here are some propositions:

1. ■
2. ▣
3. ▶
4. ◈
5. ◉
6. •
7. anything else?

(debug :search) wrong display of results

Dear Mr Norvig,

When running some examples with the debug feature, it seems to be a bug in the code, or I am doing something wrong.

The last result of the first "search" which is (12 13 7) is displayed only when executing another command, like shown below.

I am using CMUCL, but I dont think this is related to the Cl distribution.

Could You please have a look and to advice the solution.

CL-USER>
950(depth-first-search 1 (is 12) (finite-binary-tree 15))
951
952;; Search: (13 7)
953;; Search: (1)
954;; Search: (2 3)
955;; Search: (4 5 3)
956;; Search: (8 9 5 3)
957;; Search: (9 5 3)
958;; Search: (5 3)
959;; Search: (10 11 3)
960;; Search: (11 3)
961;; Search: (3)
962;; Search: (6 7)
963
964 12
965CL-USER> (show-city-path (trip (city 'san-francisco) (city 'boston) 1))
966
967;; Search: (12 13 7)
968;; Search: (#<Path to (SAN-FRANCISCO 122.26 37.47) cost 0.0>)
969;; Search: (#<Path to (RENO 119.49 39.3) cost 4355.0>)
970;; Search: (#<Path to (GRAND-JCT 108.37 39.05) cost 4427.3>)
971;; Search: (#<Path to (DENVER 105.0 39.45) cost 4428.3>)
972;; Search: (#<Path to (KANSAS-CITY 94.35 39.06) cost 4492.0>)
973;; Search: (#<Path to (INDIANAPOLIS 86.1 39.46) cost 4507.1>)
974;; Search: (#<Path to (PITTSBURGH 79.57 40.27) cost 4514.8>)
975#<Path 4514.8 km: San-Francisco - Reno - Grand-Jct - Denver - Kansas-City - Indianapolis - Pittsburgh - Boston>
976CL-USER>

(depth-first-search 1 (is 12) (finite-binary-tree 15))
977
978;; Search: (#<Path to (BOSTON 71.05 42.21) cost 4514.8>)
979;; Search: (1)
980;; Search: (2 3)
981;; Search: (4 5 3)
982;; Search: (8 9 5 3)
983;; Search: (9 5 3)
984;; Search: (5 3)
985;; Search: (10 11 3)
986;; Search: (11 3)
987;; Search: (3)
988;; Search: (6 7)
989
99012

Kind Regards,
Adrian W. Pasieka

Table of contents for PDF

Hello,

I'm adding a table of contents to my private copy of the PDF, for convenience's sake.

I'd be happy to share that copy if there is interest in including it in this repo.

Errata for chapter 3

(let ((numbers '(1234 5)))
(format t "&{r^ plus ~} is ~@r"
numbers (apply #'+ numbers)))

should be:

(let ((numbers '(1 2 3 4 5)))
(format t "&{r^ plus ~} is ~@r"
numbers (apply #'+ numbers)))

to get the output -> one plus two plus three plus four plus five is XV

*PACKAGES-FOR-WARN-ON-REDEFINITION*

in auxfns.lisp

*PACKAGES-FOR-WARN-ON-REDEFINITION* should be HCL:*PACKAGES-FOR-WARN-ON-REDEFINITION*

Note the package HCL.

suggestion: add an info page to ebook?

Rough drafts of the ebooks are nearing; I've saved drafts of releases. Those ebooks could spread outside GitHub. Adding an info page early in the book might be a good idea, which could include, as examples:

• "There's a collaborative effort at our GitHub repo. We're working on this in public, together - see https://github.com/norvig/paip-lisp . Corrections are welcome as PRs or Issues. For updates / newer versions, check Releases."
• Plz don't charge for this / if you paid for this ebook, [fill in blank - email? File an issue? Ask for a refund?]
• "This is a snapshot of the text in the repo as of, say, 2022-04-09"; the date's also in the book title and file names right now
• an email address, like, "plz email corrections to ___, attn: PAIP corrections", though a PR or Issue on the repo's probably preferable by far
• this book's open source, under the MIT license, not public domain
• a 2022 copyright

(I haven't yet posted those ebook releases because I'm not sure if it would be overstepping or if the situation is more "I trust you, go nuts".)

Thoughts?

Convert PAIP.txt to PAIP.md

If you convert the PAIP.txt to PAIP.md (I think it effectively is markdown), then it can be used as page references to the book, because it has page markers <a id="page-..."></a>.

This becomes useful for such things as the PAIP Retrospective Lessons that include page numbers.

I created an example https://github.com/ianchanning/paip-lessons that uses the lessons with links to a PAIP.md

Markdown - target version? Hard line breaks?

I thought we were targeting GitHub Flavored Markdown, but hard line breaks aren't rendering well. Compare the quote at the start of chapter 2 over on the repo (good!) to the online version of the book (not good).

I think the online version uses docsify, which uses marked, which seems to have an optional parameter to enable gfm. I set up a local server and experimented with the $docsify portion in docs/index.html, but I was unable to get it working. Help, or suggestions?

so old....

Published in 1992, all the examples with setf result in errors because an undefined variable is being "set." The language is now so appalling and ornate that the only thing that works is (defparameter x 10). The committees have taken over and made the language a bastion of hideous rules that enshrine the committee members' esoteric knowledge.

Run Common Lisp in Browser?

Is it possible that each code fragment could be runnable and editable, right in the browser?

One way to get there is to create a docker container with the book, the code, a Common Lisp compiler, and an IDE.

Another way is to run code on a server and embed links to it. Some tools for this:

• rextester Gnu clisp
• tutorialspoint Gnu clisp

More attractive is to run right in the browser. But I couldn't find any tool that translates a big enough subset of Common Lisp to javascript; they were all too limited. It would be great if someone finds one that works. Here are some that will not work for various reasons:

• Slip: missing &key etc.
• Parenscript: statement/expression issues.

Is PDF file recently generated?

The PDF file at https://github.com/norvig/paip-lisp/blob/master/PAIP-part1.pdf is about 2 years old. Is there a newer version somewhere? Thanks!

use Github releases for large file distribution.

https://help.github.com/articles/about-releases/

We don't limit the total size of your binary release files, nor the bandwidth used to deliver them. However, each individual file must be under 2 GB in size.

It seems enough for current PDF.

paip.asd works around ANSI CL compatibility problems, doesn't document it and creates new problems

paip.asd introduces a package PAIP which helps to deal with ANSI CL incompatibilities.

Unfortunately the file does not document why it is doing that and which issues it fixes how.

• it is undefined to define a function for an external symbol of the package CL. This is the case for PAIP functions SYMBOL, DEBUG, IGNORE and OPTIMIZE. Thus the new package PAIP shadows these symbols. This then makes it impossible to use (declare (ignore ...)). One has to use (declare (cl:ignore ...). Similar for (declare (optimize ...)).

• the shadowing definition of DEFCONSTANT has been provided because in ANSI CL it is only allowed to call DEFCONSTANT again with the same value. The same here means EQL. Thus (defconstant foo "foo") can't be called twice, while (defconstant bar 1) can. The paip code uses DEFCONSTANT with strings and lists - those are not necessarily EQL.

Unfortunately the paip.asd

creates new problems:

• unfortunately the paip lisp source files have no package in the modeline and no in-package.
  Which can make editing a pain, since the editor might not know that all the code is in the PAIP package.

• functions which use FIND-SYMBOL, INTERN and READ-FROM-STRING might need to be updated to look in the correct package. If there is no package parameter, they will look into whatever package is the runtime value of *PACKAGE*

• the paip.asd file does not include modules for most of the source files - thus compiling/loading is done with a different mechanism

Markdown tables

I am working through converting the table screenshots into Markdown tables. I have converted the Chapter 7 table [1]. The remaining chapters are Chapters 11, 12, 15, 16, 17, 18, 21, and 23.

I do not know how to handle the table caption. MarkedJS has table captions as an open feature request [2]. Let me know how table captions for PAIP should be done, and I will update my edits before submitting a pull request.

[1] HM0880@51bf6b1
[2] markedjs/marked#980 (comment)

encode parentheses

tags: script, prettier markdown

Switch to (regex) from (regex).

If that's hard to read:

good: `(exp)`
 bad: (`exp`)

the file loop.lisp has a package USER in the modeline

USER is now COMMON-LISP-USER

{docsify-ignore}

I don't understand the issue with the {docsify-ignore} but I know it is not pretty.

Rights Reversion

Elsevier has reverted the copyright on the book to the author (me, Peter Norvig), so we are now free to do with it what we want. Robert Smith, @tarballs-are-good, is interested in putting in some work towards this end.

code and tables

There are places where tables are used to roughly format code. We should use code blocks instead.

I used Sublime Text and option+mouse drag to make a rectangular selection. I think chapters 9 and 23 still have some of these. I used the scan as a reference for column alignment.

whitespace cleanup

tags: grep

We should try to avoid trailing spaces. I think a double trailing space was used for a linebreak; a trailing \ is probably better for that - less cryptic, more visible in markdown in the editor.

Similarly, converting tabs to spaces is good. The number of spaces to tabs can vary and can confuse; if in doubt, check the scan.

Pseudocode block formatting

We want to describe some pseudocode, with placeholders, like, toward the end of chapter 1.6:

previously

At times, we've had:

• italics in a code block, which doesn't work *well* - that's a problem in many places, honestly
• non-breaking spaces -  
• nested block quotes and new lines

I think these are ugly and/or error-prone to use.

other symbols

We could use other symbols to delineate placeholder text here, like [square brackets] or {curly brackets}.

using html pre tag

A possible solution: drop back to the <pre> html tag. Here's how that looks:

function first-name(name):
    if the first element of name is a title
        then return the first-name of the rest of the name
        else return the first element of the name

That was made with:

<pre>
function first-name(name):
    if <i>the first element of name is a title</i>
        then <i>return the</i> first-name <i>of the rest of the name</i>
        else <i>return the first element of the name</i>
</pre>

Any thoughts or suggestions?

Chapter 2 Code: combine-all

Hi,

I'm not great with GitHub so I'm not sure if I'm using it right. Basically if you look at the full text of chapter 2 you'll see there's a definition there for combined-all, repeated below:

(defun combine-all (xlist ylist)
"Return a list of lists formed by appending a y to an x.
E.g., (combine-all '((a) (b)) '((1) (2)))
-> ((A 1) (B 1) (A 2) (B 2))."
(mappend #'(lambda (y)
(mapcar #'(lambda (x) (append . y)) xlist))
ylist))

Note that the append does not refer to x as it should. This error does not appear in the .lisp file collation of the code from this chapter.

fix chapter links

tags: scripts, links

The chapter links mostly use the filenames from the source epub, like B9780080571157500017.xhtml, rather than the more clear chapter1.md. We should fix these. A couple of possible methods:

• look for chapter (num) or [chapter (num)](old link.xhtml)
• look at PAIP-safari.md and the TOC / preface for chapter filenames

Don't worry about sections or subchapters yet; those will require additional markup, which is a source of incompatibility between markdown parsers.

Is there a Julia version under development?

Hi @norvig,

Just saw the Python version is available for sometime now. Is there a Julia version under development under your guidance?

regards,

Sambit

Question about markdown syntax

Is there any reason to use quoting syntax for code evaluations and use <code> tags instead of backticks for inline code marking? Besides these, I see HTML tables in source files.

For example:

> \> 'John ⇒ JOHN 

> \> '(John Q Public) ⇒ (JOHN Q PUBLIC) 

> \> '2 ⇒ 2 

> \> 2 ⇒ 2 

> \> '(+ 2 2) ⇒ (+ 2 2) 

> \> (+ 2 2) ⇒ 4 

> \> John ⇒ Error: JOHN is not a bound variable 

> \> (John Q Public) ⇒ Error: JOHN is not a function 

and

Note that <code>'2</code> evaluates to <code>2</code> because it is a quoted expression, and <code>2</code> evaluates to <code>2</code> because numbers valuate to themselves. Same result, different reason. In contrast, <code>'John</code> evaluates to <code>John</code> because it is a quoted expression, but evaluating <code>John</code> leads to an error, because evaluating a symbol means getting the value of the symbol, and no value has been assigned to <code>John</code>. 

and

<table>
  <tr>
    <td>defun</td>
    <td>define function</td>
  </tr>
  <tr>
    <td>defparameter</td>
    <td>define special variable</td>
  </tr>
  <tr>
    <td>setf</td>
    <td>set variable or field to new value</td>
  </tr>
  <tr>
    <td>let</td>
    <td>bind local variable(s)</td>
  </tr>
  <tr>
    <td>case</td>
    <td>choose one of several alternatives</td>
  </tr>
  <tr>
    <td>if</td>
    <td>do one thing or another, depending on a test</td>
  </tr>
  <tr>
    <td>function (#')</td>
    <td>refer to a function</td>
  </tr>
  <tr>
    <td>quote (')</td>
    <td>introduce constant data</td>
  </tr>
</table>

Errata for queues in chapter 10

Back in the 1990s I remember finding a bug in the queues code. Since I've lost the email and forgotten the problem, I'll try to reconstruct it now.

The code in chapter10.md appears to be unchanged from pp. 342-343 of the scanned pdf of the book.

queue-nconc looks wrong on the case when q is empty and list is null: after running (queue-nconc (make-queue) nil), the queue structure will be (nil . nil), which is not a valid queue representation (the car should point back to the queue structure itself).

I think the other 3 cases for queue-nconc are OK (q is nonempty or list is nonnull), but I haven't checked carefully.

The other functions look right -- I sketched box-and-pointer graphs before and after for the cases where q is empty or nonempty.

Errata for chapter 8

I noticed a couple of mistakes in the definition of integrate (page 256) that probably slipped by testing. In the sketch below, I've indicated the mistakes with comments describing corrections:

(cond
  ((free-of exp x) `(* ,exp x))   ;; This should instead unquote x as in `(* ,exp ,x).
  ...
  ((starts-with exp '-)
   (ecase ...
     (1 (integrate (exp-lhs exp) x))  ;; This should instead build a unary minus operation to account for negation, as in `(- ,(integrate (exp-lhs exp) x)).
     ...

Code indentation

Using the cleaner source is nice, but the code it emits is error-prone. The source basically has <code> around each line in a code block.

1. I built a script that tries to recognize code blocks in the converted markdown, at least, but it's error-prone around indentation, especially with multiple levels. Perhaps I need to take a closer look at the conversion to markdown.
2. There are lisp files in the repo, which we can copy into the text piecemeal. There are trailing spaces though, and I think there's code in the text which doesn't appear in those files.
3. Is there a pretty printer / indentation tool that matches your preferred style? This might be best.

Clean up .txt version; port to md or some other format

The .txt version has a lot of errors; I got it from the default Save as other / ...Text menu item in Acrobat. An automated tool could rejoin the lines that end in hyphens, and perhaps find missing spaces, as in programmingpractices and anunfortunate. Other errors would require significant human labor to clean up.

asdf definition for paip in paip.asd : serial option should move to the module definition

the :serial t option should be in the module definition:

(asdf:defsystem "paip"
  :default-component-class paip-source-file
  :version "0.1"
  :author "Peter Norvig"
  :license "MIT"
  :components ((:module "lisp"
                :serial t
                :components
                ((:file "auxfns")
                 (:file "tutor")
                 (:file "examples"))))
  :description "Lisp code for the textbook \"Paradigms of Artificial Intelligence Programming\"")

compiled file pathname type

ANSI CL has the function compile-file-pathname

could be used for *paip-binary* in lisp/auxfns.lisp

Convert cleaner version to markdown

There's a much cleaner version of the book available on O'Reilly Safari that's text instead of scanned bitmaps.

Getting that version: Unpaid trial accounts are available, and you can use safaribooks to download and generate an epub file, or grab my copy. I'd love to compare against another download.

Much formatting, like italics, are missing on rendering, but present in the source html. Note, @hourann also archived the Safari book as a forest of html files in a zip file; I found the epub easier to work with, as each chapter is only one file.

Converting it to markdown: The epub is a zip file with a mix of HTML / XML / XHTML. I found a tool for converting epub to markdown, and worked on it a bit: epub2markdown The markdown generated is still hairy - and only one file! - and needs manual cleanup, but I hope it signals where cleanup is needed. The generated markdown file is in another branch.

I'm interested in what other people think of this.

REQUIRES does not compile a file

The COMPILE-ALL-PAIP-FILES function is not that great, this compiles different files with various versions of the functions.

The REQUIRES function only loads files. To have it load compiled files, one needs to call COMPILE-ALL-PAIP-FILES or similar - which is not great.

Probably a good idea to have REQUIRES compile the files if they are not already compiled.

Updating images

See #136 (comment) and #136 (comment) for initial discussion on updating the images.

This issue is to discuss the @pronoiac's bookmarks and thoughts about diagrams.

Lock on package COMMON-LISP violated on SBCL when trying to run auxfns.lisp

The error message:

Unhandled SYMBOL-PACKAGE-LOCKED-ERROR in thread #<SB-THREAD:THREAD "main thread" RUNNING {10005605B3}>:
  Lock on package COMMON-LISP violated when proclaiming SYMBOL as a function
  while in package COMMON-LISP-USER.

Environment:
Compiler: SBCL 1.4.5
Operating System: OS X 10.11.6

Current workaround:

#+sbcl
(dolist (pkg '(common-lisp common-lisp-user))
    (sb-ext:unlock-package pkg))

Add above code to the eval-when at the beginning of the file.

Inconsistent rewrite rules in chapter 2's rule-based grammar

In 2.3 A Rule-Based Solution, I notice that those parentheses around the right hand side of the the first 3 rules are unnecessary and wonder if they are intentionally put there.

(defparameter *simple-grammar*
  '((sentence -> (noun-phrase verb-phrase))
    (noun-phrase -> (Article Noun))
    (verb-phrase -> (Verb noun-phrase))
    (Article -> the a)
    (Noun -> man ball woman table)
    (Verb -> hit took saw liked))
  "A grammar for a trivial subset of English.")

It is unlikely that they are purely for decoration like the right arrow symbol (->) since the purpose of this representation is to make the rules consistent as written below.

The complication is that there can be two kinds of right-hand sides: a concatenated list of symbols, as in "Noun-Phrase => Article+Noun," or a list of alternate words, as in "Noun => man, ball, ..." We can account for these possibilities by deciding that every rule will have a list of possibilities on the right-hand side, ...

Upcoming: a better scan?

I'm thinking about getting or making a better scan.

It feels like the ebook copies I've seen come from an earlier draft than what made it into print, and that the print copy benefited from more proofreading. We've fixed mistakes that were present in ebooks, not artifacts of the ebook to markdown conversion, and not present in the print copy. A better scan could result in better OCR, and fixing a bunch of mistakes. (Though it might not! OCR is hard.)

For scanning:

• I tried the book scanner at Noisebridge, but the book's wide enough that reflections were an issue on the margins
• I'm building the TIFLIC scanner from the DIY Book Scanner forum; it uses a camera to digitize. (I have other things I want to scan anyway.)
• I mail a copy for a destructive scan; 1DollarScan looks decent

For OCR, I have thoughts and notes, but it feels like a different discussion / issue, and I don't want to get too far ahead of myself.

Any thoughts or suggestions?

PDF version contains mangled glyphs

Both in code snippets (e.g. page 433) and in the text itself (e.g. page 105).

The version available here is better in that regard:
http://gen.lib.rus.ec/book/index.php?md5=E64BEAAE4866C4F055A051D40C76BD5A

epub issues

the epub version had issues. The cover was not set correctly and there were many issues parsing the html. I used calibre to fix errors and add the cover.

I also generated a mobi version using Calibre. The ebook files are available at
https://unglue.it/download_ebook/55795/ (pdf)
https://unglue.it/download_ebook/55796/ (epub)
https://unglue.it/download_ebook/55797/ (mobi)

All of these at https://unglue.it/work/314675/
It's best to put ebook downloads in releases. (See #15 )

Chapter 4 Typos and other

Hi, I found more typos As I'm sure you can tell by now, I've decided to read the book online. I'll just make the actual typo bold, it should be obvious what the replacement should be. It's very hard to label exact locations so I'm included surrounding text to make it easier to find. At some point I stopped logging the things I was finding, this chapter is a mess.

Below there is a typo from Chapter 4, towards the top of the chapter. It should be "all" instead of "ail". I've actually noted this issue in a few places, please search for "ail" and see what you get.

Although GPS never lived up to these exaggerated claims, it was still an important program for historical reasons. It was the first program to separate its problem solving strategy from its knowledge of particular problems, and it spurred much further research in problem solving. For ail these reasons, it is a fitting object of study.

Also chapter 4, "confusing"

In fact, the conf using nature of IPL was probably an important reason for the grand claims about GPS. If the program was that complicated, it must do something important.

I think I may be seeing a general problem with the markup, maybe that's my browser. You could find most of these by searching for "!!!". In case it isn't a markup issue in my browser, here's an example (one more directly after):

_We follow all five stages in the development of our versions of GPS, with the hope that the reader will understand GPS better and will also come to understand better how to write a program of his or her own. To summarize, the five stages of an AI programming project are:

Describe the problem in vague terms !!!(p) {:.numlist}

Specify the problem in algorithmic terms !!!(p) {:.numlist}

Implement the problem in a programming language !!!(p) {:.numlist}

Test the program on representative examples !!!(p) {:.numlist}

Debug and analyze the resulting program, and repeat the process !!!(p) {:.numlist}_

there are several of these issues:
4.2 Stage 2: Specification
{:#s0015} {:.h1hd}

Similar problem to the one with "confusing":

The function a chieve is given as an argument a single goal. The function succeeds if that goal is already true in the current state (in which case we don't have to do anything) or if we can apply an appropriate operator. This is accomplished by first building the list of appropriate operators and then testing each in turn until one can be applied. achieve calls find-all, which we defined on page 101. In this use, find-all returns a list of operators that match the current goal, according to the predicate appropriate-p.

error in the code below, that should be "tell", ":action", ":action":

_With this operator as a model, we can define other operators corresponding to Newell and Simon's quote on page 109. There will be an operator for installing a battery, telling the repair shop the problem, and telephoning the shop. We can fill in the "and so on" by adding operators for looking up the shop's phone number and for giving the shop money:

(defparameter school-ops
(list
(make-op :action 'drive-son-to-school
:preconds '(son-at-home car-works)
:add-list '(son-at-school)
:del-list '(son-at-home))
(make-op :action 'shop-installs-battery
:preconds '(car-needs-battery shop-knows-problem shop-has-money)
:add-list '(car-works))
(make-op :action 'tel 1-shop-problem
:preconds '(in-communication-with-shop)
:add-list '(shop-knows-problem))
(make-op raction 'telephone-shop
:preconds '(know-phone-number)
:add-list '(in-communication-with-shop))
(make-op .-action 'look-up-number
:preconds '(have-phone-book)
:add-list '(know-phone-number))
(make-op :action 'give-shop-money
:preconds '(have-money)
:add-list '(shop-has-money)
:del-list '(have-money))))_

Similar problems in section 4.9, that should be add-list:

_In our simulated nursery school world there is only one way to find out a phone number: to look it up in the phone book. Suppose we want to add an operator for finding out a phone number by asking someone. Of course, in order to ask someone something, you need to be in communication with him or her. The asking-for-aphone-number operator could be implemented as follows:

(push (make-op :action 'ask-phone-number
:preconds '(in-communication-with-shop)
:add-1 i st '(know-phone-number))
school-ops)_

Change "master" to "main"

Can we change "master" to "main"? What would break?

Hi. I try to upload an 3 kb file using https://github.com/account/project/upload and I get error:

Hi. I try to upload an 3 kb file using https://github.com/account/project/upload and I get error:
Yowza, that’s a big file. Try again with a file smaller than 25MB.
My file is a .xcdatamodeld (CoreData Model) - 3 kb size
Do you know how can I avoid this bug ?

Originally posted by @tygruletz in #15 (comment)

CMU Python

paip-lisp/docs/chapter9.md

Line 97 in f589ad5

Recent compilers such as CMU's Python provide feedback that eases this learning process.

Shouldn't it be CMU Lisp instead of CMU's Python?

Handling formulae

Use case

We could use a way to handle formulae within Github markdown; I'm punting on the epub/pdf side. For embedding, a quick test of SVG seems to work. LaTeX is probably the best-supported way to specify formulae, but it's not directly supported in Github markdown.

Proposal

We replace the .gifs with a .tex source and a rendered .svg file.
The .tex files would make it easier to regenerate with different fonts, re-optimize, switch to png, etc.

My rough draft workflow

Original gif file, from chapter 9.9:

I never really learned LaTeX, so I'm slowly working in the codecogs editor.
This is with svg output, default font. I'm including the LaTeX source in the link description, in case the browser doesn't like the svg.

The tex file:

T_{100} \approx \phi^{100}\frac{1.1 \text{sec}}{\phi^{25}} \approx 5 \times 10^{15} \text{sec}

The markdown:

![T_{100} \approx \phi^{100}\frac{1.1 \text{sec}}{\phi^{25}} \approx 5 \times 10^{15} \text{sec}](https://latex.codecogs.com/svg.latex?T_%7B100%7D%20%5Capprox%20%5Cphi%5E%7B100%7D%5Cfrac%7B1.1%20%5Ctext%7Bsec%7D%7D%7B%5Cphi%5E%7B25%7D%7D%20%5Capprox%205%20%5Ctimes%2010%5E%7B15%7D%5Ctext%20%7Bsec%7D) 

yields:

This looks much nicer when zoomed in than the original gif.

As a png, it looks like:

There are options for other fonts - Computer Modern looks like a nice sans serif font - and inline text, when it's within a paragraph.

Open Questions

Verify that inline SVG works as well as I think it does, in the major three/four browsers, and possibly in a pandoc pdf / epub in Bluefire.

As alternative markup, we could use something like readme2tex instead, with inline formatting like It is well known that if $ax^2 + bx + c = 0$ and

$$
\frac{n!}{k!(n-k)!} = {n \choose k}
$$

I'm not keen on readme2tex because:

• it looks like it generates png not svg by default
• I prefer markdown not html img tags
• it would introduce dependencies

Thoughts?

Chapter 8 - recursive expansion of abbreviated patterns

Description

8.3 Associativity and Commutativity
The following pattern matching abbreviations are defined in such a way that causes a recursive expansion:

;; Define n and m as numbers; s as a non-number:
(pat-match-abbrev 'n '(?is n numberp))
(pat-match-abbrev 'm '(?is m numberp))
(pat-match-abbrev 's '(?is s not-numberp))

For example, we can see here that the 2nd n got recursively expanded (its binding is the first item in the resulting list).

> (pat-match '(n n) '(5 5))
(((?IS (?IS N NUMBERP) NUMBERP) . 5) ((?IS N NUMBERP) . 5))

This happens because the first thing pat-match does is expand the received pattern. At the same time it might be called recursively (e.g., by single-matcher), thus expanding the rest of an already expanded pattern...
In the above example (n n) will be first expanded to ((?is n numberp) (?is n numberp)), the car of which will get processed by single-matcher, while the rest will be recursively processed by pat-match, which will expand (?is n numberp) into (?is (?is n numberp) numberp).

Improvement

I've managed to avoid this by eliminating the recursive relationship and using ?n instead:

(pat-match-abbrev '?n '(?is n numberp))

Consequently, affected simplification rules had to be modified to use ?n on the left-hand side but just n on the right hand-side. For example:

(?s * ?n = n * s)
(?n * (?m * x) = (n * m) * x)

ignoring ignore and other non-referenced variables

variables named ignore and other non-referenced variables should be declared to be ignored.

Use for example this declaration:

(declare (ignore ignore))