Paradigms of Artificial Intelligence Programming

Case Studies in Common Lisp

Peter Norvig

• Publisher: Morgan Kaufmann
• Year: 2014
• Print ISBN: 9781558601918
• eBook ISBN: 9780080571157
• Topic: Informatique
• Subtopic: Intelligence artificielle (IA) et sémantique

Paradigms of AI Programming is the first text to teach advanced Common Lisp techniques in the context of building major AI systems. By reconstructing authentic, complex AI programs using state-of-the-art Common Lisp, the book teaches students and professionals how to build and debug robust practical programs, while demonstrating superior programming style and important AI concepts. The author strongly emphasizes the practical performance issues involved in writing real working programs of significant size. Chapters on troubleshooting and efficiency are included, along with a discussion of the fundamentals of object-oriented programming and a description of the main CLOS functions. This volume is an excellent text for a course on AI programming, a useful supplement for general AI courses and an indispensable reference for the professional programmer.

Part I

Introduction to Common Lisp

Chapter 1

Introduction to Lisp

You think you know when you learn, are more sure when you can write, even more when you can teach, but certain when you can program.

—Alan Perlis

Yale University computer scientist

This chapter is for people with little or no experience in Lisp. Readers who feel confident in their Lisp programming ability can quickly skim the chapter or skip it entirely. This chapter necessarily moves quickly, so those with little programming experience, or any reader who finds this chapter tough going, should seek out a supplementary introductory text. My recommendations are in the preface.

Computers allow one to carry out computations. A word processing program deals with words while a calculator deals with numbers, but the principles are the same. In both cases, you provide the input (words or numbers) and specify the operations (such as deleting a word or adding two numbers) to yield a result (a completed document or calculation).

We will refer to anything that can be represented in the memory of a computer as a computational object, or just an object. So, words, paragraphs, and numbers can be objects. And because the operations (deleting and adding) must be represented somewhere in the computer’s memory, they are objects, too.

Normally, the distinction between a computer “user” and a computer “programmer” is that the user provides new input, or data (words or numbers), while the programmer defines new operations, or programs, as well as new types of data. Every new object, be it datum or operation, must be defined in terms of previously defined objects. The bad news is that it can be quite tedious to get these definitions right. The good news is that each new object can in turn be used in the definition of future objects. Thus, even complex programs can be built out of smaller, simpler objects. This book covers a number of typical AI problems, showing how each problem can be broken down into manageable pieces, and also how each piece can be described in the programming language Common Lisp. Ideally, readers will learn enough through studying these examples to attack new AI problems with style, grace, and success.

Let’s consider a simple example of a computation: finding the sum of two numbers, let’s say 2 and 2. If we had a calculator handy, we would type “2 + 2 =” and see the answer displayed. On a calculator using reverse Polish notation, we would have to type “22+” to see the same answer. In Lisp, as with the calculator, the user carries out an interactive dialog with the computer by typing in an expression and seeing the computer print the value of that expression. This interactive mode is different from many other programming languages that only offer a batch mode, wherein an entire program is compiled and run before any output can be seen.

We start up a pocket calculator by flipping the on/off switch. The Lisp program must also be started, but the details vary from one computer to another, so I can’t explain how your Lisp will work. Assuming we have managed to start up Lisp, we are likely to see a prompt of some kind. On my computer, Lisp types “>” to indicate it is ready to accept the next computation. So we are faced with a screen that looks like this:

>

We may now type in our computation and see the result displayed. It turns out that the Lisp convention for arithmetic expressions is slightly different: a computation consists of a parenthesized list with the operation name first, followed by any number of operands, or arguments. This is called prefix notation.

>(+ 2 2)

4

>

We see that Lisp has printed the answer, 4, and then another prompt, >, to indicate it is ready for the next computation. Throughout this book, all Lisp expressions will be displayed in typewriter font. Text on the same line as the “>” prompt is input typed by the user, and text followin...

Table of contents

• Cover image
• Title page
• Table of Contents
• Copyright page
• Dedication
• Preface
• Part I: Introduction to Common Lisp
• Part II: Early AI Programs
• Part III: Tools and Techniques
• Part IV: Advanced AI Programs
• Part V: The Rest of Lisp
• Appendix: Obtaining the Code in this Book
• Bibliography
• Index