Artificial Intelligence Programming

Eugene Charniak, Christopher K. Riesbeck, Drew V. McDermott, James R. Meehan

• Publisher: Psychology Press
• Year: 2014
• eBook ISBN: 9781317767985
• Topic: Psychology
• Subtopic: Cognitive Psychology & Cognition
• Index: Psychology

Artificial intelligence research has thrived in the years since this best-selling AI classic was first published. The revision encompasses these advances by adapting its coding to Common Lisp, the well-documented language standard, and by bringing together even more useful programming tools. Today's programmers in AI will find this volume's superior coverage of programming techniques and easily applicable style anything but common.

1

Lisp Programming

1

Lisp Review

LISP has jokingly been called “the most intelligent way to misuse a computer.” I think that description is a great compliment because it transmits the full flavor of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts.

— Edsger Dijkstra

LISP was the world’s first elegant language, in the sense that it provided a parsimonious base with rich possibilities for extension. LISP has been applied mainly to problems of symbolic manipulation and artificial intelligence, partly because manipulating symbols is so easy in LISP, and partly because AI programmers tend to be lazy and undisciplined, like pilots who refuse to file a flight plan before taking off, and LISP’S interactive structure allows them to get away with this.

1.1 Data Structures

LISP data structures are called “S-expressions.” The S stands for “symbolic.” In this text, the terms “S-expression” and “expression” are used interchangeably. An S-expression is

1. a number, e.g., 15, written as an optional plus or minus sign, followed by one or more digits.
2. a symbol, e.g., F00, written as a letter followed by zero or more letters or digits.
3. a string, e.g., “This is a string”, written as a double quote, followed by zero or more characters, followed by another double quote.
4. a character, e.g., #\q, written as a sharp sign, followed by a backslash, followed by a character. (Numbers, symbols, strings, and characters are called atoms. There are other kinds of atoms. We will see them in later chapters.)
5. a list of S-expressions, e.g., (A B) or (IS TALL (FATHER BILL)), written as a left parenthesis, followed by zero or more S-expressions, followed by a right parenthesis.

Parentheses are more significant in LISP than they are in most other programming languages. Parentheses are virtually the only punctuation marks available in LISP programs. They are used to indicate the structure of S-expressions. For example, (A) is a list of one element, the symbol A. ((A)) is also a list of one element, which is in turn a list of one element, which is the symbol A. Notice also that the left and right parentheses must balance. That is, a well-formed S-expression has a right parenthesis to close off each left parenthesis.

1.2 Program Structures

Syntax: The syntax of a LISP program is simple: Every S-expression is a syntactically legal program! That is, any given data structure could be executed as a program. Most of them, however, fail on semantic grounds.

Semantics: The function that executes S-expressions (and hence defines the semantics of LISP) is called EVAL. EVAL takes one S-expression and returns another S-expression. The second expression is called the value of the first expression. We notate this as expression => value.

The rules for evaluation are fairly simple.

Rule 1: If the expression is a number, a string, a character, the symbol T, or the symbol NIL, then its value is itself. So 5 => 5.

Rule 2: If the expression is a list of the form

(function arg₁ . . . arg_k)

then the value is found by first evaluating each argument (arg₁ to arg_k), and then calling function with these values. For the moment, all our functions are named by symbols. For example, the symbols + (for addition) and * (for multiplication) name functions that are defined in LISP for doing arithmetic.

(+ 15 2)	=> 17
(* 3 5)	=> 15
(+ (* 3 5) 2)	=> 17

Note that in order to evaluate the last expression, each argument has to be evaluated first. Since the first argument is itself a list, (* 3 5), Rule 2 is applied again, and the arguments, 3 and 5, are evaluated. By Rule 1, they evaluate to themselves. They are passed to the multiplication procedure, *, which returns 15. Similarly, 2 evaluates to itself, and 15 and 2 are passed to +, which returns the number 17.

Rule 3: If the expression is a list of the form

(reserved-word arg₁ . . . arg_k)

then the value depends completely on the definition of reserved-word. The arguments may or may not be evaluated. Reserved words are named by symbols, just as functions are.

One such reserved word is SETQ. SETQ is used for assigning values to symbols. (SETQ symbol expression) cau...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• Preface
• Part I: Lisp Programming
• Part II: Al Programming Techniques
• Appendix 1: A Glossary of Common Lisp Functions
• Answers to Selected Exercises
• Bibliography
• Author Index
• Index of Defined Lisp Items
• Subject Index