lisp book - Gary D. Knott.pdf - Lisp - musli_com

This is ¯le: lispbook.tex

L A T E X'ed: June 22, 2006

Feb. 18, 1997

Interpreting LISP by Gary D. Knott

Preface

I wrote this book to help teach LISP to students in a course on data structures. Consequently it

contains a careful description of the data structures manipulated by LISP functions. These data

structures and others, notably hash tables, are also used in constructing a LISP interpreter. I wish

to acknowledge the help of my students in shaping and debugging this material.

The study of LISP, coupled with the study of a LISP interpreter intended for exhibition, is of

special interest to students in the areas of programming languages and computer architecture as

well as data structures. Indeed, I hope this book will be useful to students in all areas of computer

science, and I also hope it will be useful to autodidacts, professional programmers, and computer

enthusiasts in a wide variety of ¯elds.

This book is intended to be accessible to a wide range of interested readers from high school

students through professional programmers. I would very much like to see students use this book

to help them understand LISP interpreters, and thus understand the concepts involved in building

an interpreter for any language. The best way to proceed is to compile and run the C LISP

interpreter, and then experiment by modifying it in various ways. Finally, I hope this book can

help all who use it develop an aesthetic appreciation of this elegant programming language.

Copies of this little book in PDF format, together with the LISP interpreter source code and

ancillary ¯les, can be found at www.civilized.com .

Gary Knott

Civilized Software, Inc.

12109 Heritage Park Circle

Silver Spring, Maryland 20906

phone:1-(301)-962-3711

email:knott@civilized.com

URL:http://www.civilized.com

CONTENTS

Contents

1 LISP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2

2 The Atom Table and the Number Table : : : : : : : : : : : : : : : : : : : : : : : : : 2

3 Evaluation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7

4 Some Functions and Special Forms : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8

5 S-Expressions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11

6 Typed-Pointers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12

7 Pictorial Notation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14

8 More Functions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17

9 Arguments and Results are Typed-Pointers : : : : : : : : : : : : : : : : : : : : : : : 19

10 List Notation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20

11 More Special Forms : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23

12 De¯ning Functions: ¸-Expressions : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25

13 More Functions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 27

14 De¯ning Special Forms : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30

15 The Label Special Form : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 32

16 The Quote Macro : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33

17 More Functions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34

18 More About Typed-Pointers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34

19 Binding Actual Values to Formal Arguments : : : : : : : : : : : : : : : : : : : : : : 36

20 Minimal LISP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42

21 More Functions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 43

22 Input and Output : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 45

23 Property Lists : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 46

24 What is LISP Good For? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 49

25 Symbolic Di®erentiation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 51

26 Game-Playing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 57

27 The LISP Interpreter Program : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64

28 Garbage Collection : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 78

29 LISP in C : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 81

30 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 101

2 THE ATOM TABLE AND THE NUMBER TABLE

1 LISP

LISP is an interesting programming language and the ideas involved in building a LISP interpreter

are equally interesting. This book contains an introduction to LISP and it also contains the data

structure details and the explicit code for a working LISP interpreter.

LISP is a programming language with unique features. It is conceptually interactive. Input com-

mands are given one by one and the associated result values are typed-out. LISP is an applicative

language,meaningthatitconsistsmainlyoffunctionalapplicationcommands. Besidesfunctionap-

plication, thereareformsofassignmentcommandsandconditionalcommandswritteninfunctional

form. In general, iteration is replaced by recursion.

The data values on which a LISP function may operate includes real numbers. Thus, an expression

like \1:5+2" is a LISP statement which means: type-out the result of applying + to the argu-

ments 1:5 and 2. In LISP, function application statements are always written in pre¯x form, e.g.

+ ( 1:5;2 ) . Moreover, rather than writing f(x;y) to indicate the result of the function f applied

to the arguments x and y, we write ( f x y ) in LISP, so (+ 1:5 2 ) is the LISP form for \1:5+2".

Finally, functions in LISP are usually speci¯ed by identi¯er names rather than special symbols.

Thus the correct way to compute 1:5+2 in LISP is to enter the expression (PLUS 1:5 2 ) , which will,

indeed, cause \3:5" to be typed out. An expression such as (PLUS 1.5 2) is called a function call

expression. LISP functions can also operate on lists of objects; indeed the name \LISP" is derived

from the phrase \LISt Processing".

LISP is commonly implemented with an interpreter program called the LISP interpreter. This

program reads LISP expressions which are entered as input and evaluates them and types out

the results. Some expressions specify that state-changing side-e®ects also occur. We shall describe

belowhowaparticularLISPinterpreterisconstructedatthesametimethatLISPitselfisdescribed.

There are a variety of dialects of LISP, including extended forms which have enriched collections

of functions and additional datatypes. We shall focus on the common core of LISP, but some

de¯nitions given here are not universal, and in a few cases they are unique to the version of LISP

presented herein (GOVOL). The GOVOL dialect of LISP presented here is similar to the original

LISP 1.5 [MIT62]; it is not as complex as the most frequently used varieties of LISP found these

days, but it contains all the essential features of these more complex varieties, so that what you

learn here will be immediately applicable for virtually every LISP dialect.

2 The Atom Table and the Number Table

Our LISP interpreter program maintains several general data structures. The ¯rst data structure

is a symbol table with an entry for every named data object. These named data objects are called

ordinary atoms, andthesymboltableofordinaryatomsiscalledthe atom table. (Theterm\atom"

ishistorical; thatisthetermJohnMcCarthyused.) Theatomtableisconceptuallyofthefollowing

form.

name type value plist bindlist

. . .

n¡1

The atom table has n entries where n is some reasonably large value which is unspeci¯ed for now.

Each entry in the atom table has a name ¯eld, which holds the atom name, for example: \ PLUS " or

\ AXY ". Each entry also has a value ¯eld for holding the current value of the atom, and an associated

type ¯eld which is an integer code that speci¯es the type of the value of the atom. For example,

the value of the atom \ PLUS " is a builtin function, which is classi¯ed by the integer typecode 10.

Each atom table entry also has a plist ¯eld and a bindlist ¯eld to be discussed later.

The second data structure isasimple table calledthe number table in which °oating-point numbers

are stored. Every input number and every computed number is stored in the number table, at least

for the period of time it is required to be there. The number table is conceptually of the following

form:

number

. . .

n¡1

Since the °oating-point numbers include a large complement of integers, there is no reason, except,

perhaps, for speed, to have integers provided in LISP as a separate datatype.

Exercise 2.1: Precisely specify the set of integers which are expressible in °oating point

format on some computer with which you are familiar.

Exercise 2.2: Is there a good reason that the atom table and the number table have the same

number of entries?

Solution 2.2: No, there is no good reason for this. It can be easily changed if desired.

The datatype codes are:

2 THE ATOM TABLE AND THE NUMBER TABLE

1 unde¯ned

8 variable (ordinary atom)

9 number (number atom)

0 dotted-pair (non-atomic S-expression)

10 builtin function

11 builtin special form

12 user-de¯ned function

13 user-de¯ned special form

14 unnamed function

15 unnamed special form

These datatypes are exactly the datatypes available in the version of LISP discussed here. The

reason for the seemingly peculiar typecodes will be apparent later; they are chosen so that the

individual binary digits have useful meanings.

There are two kinds of atoms in LISP. All atoms occur in either the atom table or the number

table; ordinary atoms are entries in the atom table, and number atoms are entries in the number

table. An ordinary atom is like a variable in FORTRAN. It has a name and a value. The name is a

character string which is kept for printing and input matching purposes. The value of an ordinary

atom is a value of one of the types listed above. A number atom which represents a real constant

also has a value; this value is the °oating-point bitstring representing the number. The value of a

number atom cannot be changed; a number atom is thus a constant.

An ordinary atom whose value is unde¯ned is created in the atom table whenever a previously-

unknown name occurs in a LISP input statement. An ordinary atom whose value is unde¯ned has

an arbitrary bit pattern in its value-¯eld and the typecode 1 in its type-¯eld.

An ordinary-atom-valued ordinary atom in entry i of the atom table holds an index j of an atom

table entry in its value-¯eld; the value of the entry i atom is then the entry j atom. The typecode

in the type ¯eld of such an ordinary-atom-valued ordinary atom is 8.

A number-valued ordinary atom A in entry i of the atom table holds an index j of a number table

entry in its value ¯eld. Entry j in the number table is where the number atom representing the

number-value of the ordinary atom A is stored. The type ¯eld of entry i in the atom table holds

the typecode 9.

A number atom is created in the number table whenever a number which is not already present in

the number table occurs in the input, or is computed. Each distinct number in the number table

occursinoneandonlyoneentry. Similarly, anordinaryatomiscreatedintheatomtablewhenever

an ordinary atom occurs in the input, or is otherwise generated, which is not already present in

the atom table. Each distinct ordinary atom in the atom table is stored uniquely in one and only

one entry.

An atom may be its own value. In particular, this is always the case for a number atom which

is always made to appear to have itself as its value in the sense that the result of evaluating the

number atom named n is the corresponding °oating-point bitstring which is represented lexically

and typed-out as the identical name n or a synonym thereof. Since number atoms are constants,

lisp book - Gary D. Knott.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: