by Eric Norman

Once this primer has been read and LISP practiced for a while, the reader should be, if he wishes, ready for a full treatment presented in the 1100 LISP Reference Manual.

Although this primer describes LISP in general, there are many places where specifics are given for a particular version, namely the LISP system for the Univac 1100 series of computers as implemented at the Madison Academic Computing Center.

1.0 Introduction to LISP . . . . . . . . . . . . . 1-1 2.0 The Universe of Discourse . . . . . . . . . . 2-1 2.1 Atomic Objects . . . . . . . . . . . . . . 2-1 2.1.1 Numbers . . . . . . . . . . . . . . 2-1 2.1.2 Atomic Symbols . . . . . . . . . . . 2-2 2.1.3 Functions . . . . . . . . . . . . . 2-2 2.2 Lists . . . . . . . . . . . . . . . . . . 2-3 3.0 The Functions . . . . . . . . . . . . . . . . 3-1 3.1 Quotation . . . . . . . . . . . . . . . . 3-1 3.2 Some Primitive Functions . . . . . . . . . 3-2 3.2.1 Construction . . . . . . . . . . . . 3-2 3.2.2 Selection . . . . . . . . . . . . . 3-2 3.3 Example . . . . . . . . . . . . . . . . . 3-4 3.4 More Primitive Functions . . . . . . . . . 3-6 4.0 The Language . . . . . . . . . . . . . . . . . 4-1 4.1 Evaluation . . . . . . . . . . . . . . . . 4-1 4.1.1 Evaluation of Atoms . . . . . . . . 4-1 4.1.2 Evaluation of Lists . . . . . . . . 4-2 4.2 COND . . . . . . . . . . . . . . . . . . . 4-2 4.3 AND, OR . . . . . . . . . . . . . . . . . 4-3 4.4 LAMBDA . . . . . . . . . . . . . . . . . . 4-3 4.5 Naming Functions . . . . . . . . . . . . . 4-4 5.0 Using the 1100 LISP System . . . . . . . . . . 5-1 5.1 Useful Information . . . . . . . . . . . . 5-1 5.2 Example . . . . . . . . . . . . . . . . . 5-2 5.3 Diagnostics . . . . . . . . . . . . . . . 5-5 5.3.1 Help Mode . . . . . . . . . . . . . 5-7 5.3.2 The Backtrace . . . . . . . . . . . 5-7 5.3.3 Example . . . . . . . . . . . . . . 5-7 5.4 LISP Control Statements . . . . . . . . . 5-9 5.5 Tracing . . . . . . . . . . . . . . . . . 5-1 6.0 Additional Features . . . . . . . . . . . . . 6-1 6.1 The PROG Feature . . . . . . . . . . . . . 6-1 6.2 Input - Output . . . . . . . . . . . . . . 6-3 6.3 Functions as Arguments . . . . . . . . . . 6-5 6.4 Other System Defined Functions . . . . . . 6-6 6.5 One More Example . . . . . . . . . . . . . 6-7 6.6 Reserved Atomic Symbols . . . . . . . . . 6-10 6.7 Practice . . . . . . . . . . . . . . . . . 6-10

It has been found that once people get used to LISP, it becomes an extremely useful and powerful tool. This is because LISP assumes most of the "dirty work" of programming; namely, allocation of memory, saving temporary results, and the like. However, it does take a while before one can feel at ease with LISP. This is caused mostly by the syntax which, although very simple and consistent, is somewhat difficult to read at first.

Furthermore, LISP requires that one think in a manner different from other programming languages; specifically, LISP emphasizes the expression instead of the statement. By expression we mean something that specifies a value to be computed; a statement indicates something to be done. The justification for this approach is that the value computed by an expression is what we are really interested in. For example, when we write an ALGOL statement such as V:=A+B, the important thing is the sum of A and B; the fact that we assign their sum to V is only a means to an end; i.e., we do the assignment because we are going to need the sum of A and B later, either because it is the answer we want or because is is going to be used in another expression. In LISP such behavior is discouraged. Instead of computing the sum of A and B beforehand, we compute it when we want it; that is, we write an expression that computes A+B as a subexpression of some other expression that needs this sum. Or if A+B is the answer that we desire, then we need do nothing more than write it; the LISP system assumes that we are interested in knowing what the sum is and therefore prints it.

The impact of the LISP approach is that in order to understand LISP we must forget that we ever knew about such things as assignment statements or sequences of instructions and begin thinking of ways to build up expressions that describe the result we want. Another way of saying all this is that in LISP we describe the answer that we want and not the steps that the machine is to perform in order to compute it.

This manual is intended to be used as a primer only. There has been no attempt to explain everything that there is in LISP. An attempt has been made to introduce only those concepts that will enable one to get a start in LISP and to be able to write a few LISP programs and try them out. This primer should be usable by anyone who has had a little experience with other programming languages but has never seen LISP. Once you have practiced a while with the basics introduced here, you should be ready for a more complete coverage and can go on to the 1100 LISP Reference Manual, which is also available from MACC.

In this chapter we shall concentrate on the objects that LISP is capable of manipulating and also give the rules for writing them. That is, what you have to punch on a card or type into a terminal to specify one of these objects.

Our first concern will be with those objects that are atomic. We say that an object is atomic because we do not consider it to be built out of smaller objects. The general rule for writing atomic objects is that they must be delimited on both sides by either a card boundary or a LISP punctuation mark, which in 1100 LISP are space, comma, period, left and right parentheses, left and right square brackets, left and right broken brackets, apostrophe, and question mark; e.g.

blank , . ( ) [ ] < > ` ?

As with other languages, LISP includes numbers in its universe of discourse and, as usual, there are two kinds: integers and reals.

Integers are written as any sequence of decimal digits optionally preceded by a sign and optionally followed by the letter "E" and a decimal scale factor. Examples of integers are

Integers may also be written in octal. This is indicated by a sequence of octal digits with optional sign and followed by the letter "Q" and an optional octal scale factor. Legal octal numbers are

Real numbers must contain a decimal point, which may not be the first character; they may optionally be followed by the letter "E" and a decimal exponent. Examples of real numbers are

One of the features of LISP that distinguishes it from other languages is the inclusion of atomic symbols in its universe of discourse. It`s kind of hard to describe what an atomic symbol is, so let`s just say that it`s an object just like an integer or a real number and that manipulations can be performed with or on them. Maybe the best way to get a feeling of what they are is with an example. Suppose we were writing a program to play chess. In LISP we would probably chose to represent Black`s King`s Bishop`s pawn by the atomic symbol

Please notice that atomic symbols and atomic objects are not the same things. The set of atomic objects so far includes as (disjoint) subsets the sets of atomic symbols, integers, and reals. We shall henceforth use "atom" when we mean any atomic object and only use the term

LISP also allows us to do computations with functions. We mean "functions" here in essentially the mathematical sense, i.e. those things that we can apply to arguments and calculate results. Examples of well known functions are the binary addition function and the unary factorial function. LISP allows us to manipulate functions with as much freedom as any other object and is somewhat unique in this respect.

So far our universe of discourse contains atoms; now we will expand it by including lists. A list is any sequence of other objects. A list is surrounded by left and right parentheses (or left and right square brackets, or left and right crooked brackets) and contains a sequence of objects separated by spaces or commas. The following are examples of lists

(A B (SUBLIST)), and ((A) <1234> BCD)

The existence of lists along with atomic symbols is what gives LISP its tremendous power for symbolic computation. Lists can grow to any size and there is no need to reserve space or anticipate their maximum size in advance as one has to do in other languages, e.g. declare array dimensions. As a simple example of how lists and atomic symbools can be used, suppose we were writing a program to prove theorems in the propositional calculus. We can represent axioms or assertions in the propositional calculus in a fairly natural manner. For instance, the following LISP objects can be used to represent their obvious counterparts in the propositional calculus:

Now that we have a glimpse of the types of data that we can manipulate with LISP, we need to know what kind of manipulations that we can do. However, in order to do so, we are going to have to find out a little of what the LISP language looks like.

The fundamental notion in LISP is that of applying a function to arguments, and we write this like so:

to the more familiar

You may have noticed that LISP programs look like LISP data objects. In fact they are. However, this fact does tend to cause problems. For instance, consider the LISP expression

The mechanism for achieving this "quotation" in 1100 LISP is to precede the object by an apostrophe. The apostrophe in essence means that the next object you write is the actual object you want (i.e. a literal) and not an identifier or subexpression that represents the value desired. For instance, if instead of the above we wrote

As you may have surmised above, LISP does have a supply of built in arithmetic functions for manipulating numerical data. But what we are really interested in here are some primitive functions for manipulating structured data, i.e. lists.

The first thing that we need to do is build lists. The fundamental function in LISP that allows us to do this is called construction, is symbolized by the atomic symbol

Another important point. Doing the above in no way altered the arguments supplied to

As further examples of the use of

(CONS `A `()) = (A) (CONS `A NIL) = (A) (CONS NIL NIL) = (NIL) (CONS `A (CONS `B (CONS `C NIL))) = (A B C) (CONS`A `(CONS B NIL)) = (A CONS B NIL) (CONS (PLUS 1 2)(CONS (TIMES 3 4) NIL)) = (3 12)

Now that we can build lists, the next thing we want to do is to be able to take them back apart. There are two functions in LISP that do this. The first is symbolized by the atomic symbol

The other selection function is symbolized by

The admonition that was given about

Another way of looking at

The examples below show more clearly the uses of

Here`s a handy little abbreviation you will want to know about. Instead of writing(CAR `(A B))=A(CDR `(A B))=(B)(CAR (CDR `(A B)))=B(CDR (CDR `(A B)))=()=NIL(CAR (CONS anythinglist))= anything(CDR (CONS anythinglist))=list(CONS (CAR (CDR `(A B)))(CONS (CAR `(A B)) NIL))=(B A)

And just to satisfy your curiosity, the names

Now we know just a little about what kinds of operations that we can do with LISP. What we really would like to know now is how to write a program to do something useful. Unfortunately, we can`t tell you yet, but we`ll do the next best thing. We will look at an example of how to write a program. Be warned that there is a lot in this example that we haven`t told you about yet, but with a little narrative you should be able to induce a little of what is going on. The example is this: suppose we want to define a function that will compute the length of a list, e.g.

Essentially what the above says is that we want to define a function symbolized (named) by the atomic symbol(CSETQ LENGTH (LAMBDA (L) (COND ((NULL L) 0) (T (PLUS 1 (LENGTH (CDR L)))) )))

Now after we have defined this function, we can test it out by simply writing

One of the important things to notice about the above example is what we didn't have to do. We did not have to invent an extra variable in which to accumulate the length of the list as we ran down it and we did not have to remember to set this variable to(LENGTH `(A B C))=(PLUS 1 (LENGTH (CDR `(A B C))))=(PLUS 1 (LENGTH `(B C)))=(PLUS 1 (PLUS 1 (LENGTH `(C))))=(PLUS 1 (PLUS 1 (PLUS 1 (LENGTH NIL))))=(PLUS 1 (PLUS 1 (PLUS 1 0)))=(PLUS 1 (PLUS 1 1))=(PLUS 1 2)=3

What we did above that allowed us to define the length function so easily was to define

One other thing to notice about the example above is that it gives us a hint of how we "talk" to the LISP system. Essentially, all the LISP system does is evaluate expressions. We submit a LISP expression to the system and it computes and prints out the result and then waits for another expression to evaluate. This mode of operation is very nice, especially when running from a timesharing terminal. As shown above, you can try out the function just defined on a few test cases immediately after defining it to make sure you got it right. Also notice that even what we wrote to define to the

Here are some more of the primitive functions in LISP that are supplied by the system. Here, and throughout the rest of this manual, we will use lower case letters to represent arguments to functions with the understanding that they represent the value of whatever subexpression is written in their place.

Truth in LISP is represented by the atomic symbol

(EQ `A `A)=T(EQ `A `B)=NIL(EQ `A `(A))=NIL(EQ 1 `A)=NIL(EQ 1 1)= undefined

(

In the last chapter we learned some of the primitive functions that are already included in the LISP system. There are many more, of course, and they are listed elsewhere or in the Reference Manual. But what we need to learn now is how to build up more complex LISP expressions, and specifically, how to form functions of our own definition from these complex functions.

An important notion in LISP is that of

The rules for evaluating a LISP expression are going to be given in this chapter. There are very few of them, they are quite simple, and they generally agree with obvious notions that you have learned in other programming languages. They are also very powerful since there are almost no special cases or restrictions.

When an atom (i.e. an atomic symbol or a number) is used in a LISP expression, it has the value that you would expect it to have. If it is a number, then its value is itself. If it is an atomic symbol, then it is a variable and stands for some other value. There are two different kinds of variables in LISP and the distinction between them depends on how their values are assigned or changed. The first kind is called a constant in LISP. (This is somewhat unfortunate since the word "constant" means something else in other languages, i.e. numbers). LISP constants aren`t really constant since their values can change.

Constant variables change their values only when you explicitly assign a new value to them. For example, the LISP expression

The other kind of variable in LISP is called a

As we saw in the last chapter, a list, when used as a LISP expression means that we want to apply a function to arguments. The precise rule is this: the value of an expression such as

The only exception to the above rule is when the first element of a list is a special atomic symbol that means special actions are to be taken. These special atomic symbols are essentially equivalent to "reserved words" in other languages.

We have already seen a couple of them but they weren`t very recognizable. When we wrote things like

If

Another one of these special atomic symbols is

We will now learn a few more of these special atomic symbols, which are called

The special-form

(COND(P1 E1) (P2 E2) ...)

The rule for evaluating this special-form is this: the

If no

The expression(CSETQ LENGTH (LAMBDA(L) (COND ((NULL L) 0) (T (PLUS 1 (LENGTH (CDR L)))))

If

As another example of the use of COND, suppose that we have two variables

I.e. it evaluates to(COND ((GREATERP M N) M)(T N))

Special forms of the form

What we have so far, i.e. the ability to nest subexpressions and to write conditional expressions, allows us to write quite complex expressions. What we require now is the ability to use these expressions in definitions of functions of our own choosing.

For example, we don`t want to have to write

There is a very useful special-form in LISP that allows us to turn expressions into functions. The special-form

Each

For instance, the expression

We could apply this function to some arguments by writing the expression

and the value of this expression would be((LAMBDA(X Y)(PLUS X (TIMES X Y))) 4 5)

Notice that the expression

The special-form

In order to give a function a name, we do exactly the same thing that we would do if we wanted to give anything else a name. For instance, when we write

and then we assign this function to a variable by writing(LAMBDA(X Y)(COND ((GREATERP X Y) X)(T Y)))

The value of the above expression happens to be the function, but that`s really not what we care about. In this case we care about the side effect of(CSETQ MAX(LAMBDA(X Y)(COND ((GREATERP X Y) X)(T Y))))

Expressions of the form

There are some other useful things about the 1100 LISP system that will make it easier to use. The first is its capability for automatic parentheses balancing. As we mentioned above, either round,

E.g.

Similarly,

A more useful "tool" for balancing parnetheses is to develop some sort of arrangement and indentation structure so that similar expressions are grouped similarly or beneath each other.

The only time you are required to have a space in LISP is between two consecutive atomic symbols, all others are optional. So you should use these extra spaces to lay out LISP programs in some manner that is consistent and makes sense to you. By so doing, you will find that there are places where you have to fill in a bunch of closing brackets and when you get there you can automatically fill in the right number. For instance, you will have certain places where you always need three right parentheses so you can fill them in automatically without counting.

The example below uses the part of the indentation system that I have developed for myself over the years.

The 1100 LISP system will not print an object beyond certain limits. This means that as soon as a certain depth of nesting is reached in an object then any list will be printed as only

The depth and length limits are 10 and 50 when the 1100 LISP system is printing the value of an expression. This should be more than adequate. For certain other printouts (see examples of the backtrace and tracing below) these limits are lessened so not "too much" detail appears.

The example below shows what a typical LISP session would look like from a timesharing terminal.

This example uses LISP to define some functions to do manipulations on sets. In LISP, we would choose to represent a set

The functions below will discover if an element is a member of a set, compute the union of two sets, compute the intersection of two sets, and compute the power set (set of all subsets) of a set.

@LISP 1100 LISP 7.72 EVAL: (CSETQ MEMBER (LAMBDA (E S) (COND ((NULL S)NIL) ((EQUAL (CAR S) E) T) (T (MEMBER E (CDR S))) ))) VALUE: [MEMBER] EVAL: (MEMBER `C `(A B C D E)) VALUE: T EVAL: (MEMBER `X `(A B C D E)) VALUE: NIL EVAL: (CSETQ UNION (LAMBDA (SA SB) (COND ((NULL SA) SB) ((MEMBER (CAR SA) SB)(UNION (CDR SA) SB)) (T(CONS (CAR SA) (UNION (CDR SA) SB))))) ))) VALUE: [UNION] EVAL: (UNION `(A B C DE) `(G E D B A)) VALUE: (C DE G E D B A) EVAL: (CSETQ INTERSECTION (LAMBDA (SA SB) (COND ((NULL SA) NIL) ((MEMBER (CAR SA) SB) (CONS (CAR SA) (INTERSECTION (CDR SA) SB))) (T (INTERSECTION (CDR SA) SB> VALUE: [INTERSECTION] EVAL: (INTERSECTION `(A B C D E) `(G E B S A)) VALUE: (A B E) EVAL: (CSETQ POWER (LAMBDA (S) (COND ((NULL S) `(NIL)) (T (SPREAD (CAR S) (POWER (CDR S)))) ))) VALUE: [POWER] EVAL: (CSETQ SPREAD (LAMBDA (E PS) (COND [(NULL PS) NIL] [T (CONS (CONS E (CAR PS)) (CONS (CAR PS) (SPREAD E (CDR PS] > VALUE: [SPREAD] EVAL: (POWER `(A B C)) VALUE: ((A B C) (B C) (A C) (C) (A B) (B) (A) NIL) EVAL: (POWER (INTERSECTION `(A B C D) `(B D E F> VALUE: ((B D) (D) (B) NIL)

Some notes about the above example:

The lines starting with

A narrative of the membership function goes something like this:

We ask if the set is empty

The value of the expression that we used to define the membership function is that function itself. The 1100 LISP system indicated this by printing

This does not mean a list when the 1100 LISP system prints something using square brackets in this case it means that value which has been assigned to the atomic symbol

You should expect such a value whenever you define a function with

Note that after we define each function, we try it out on a few test cases to verify that it works.

Note that when we got to the end of defining the function named

Furthermore, note the use of square brackets in the conditional expression in the definition of the function named

The definitions of the set union and intersection are fairly straightforward. You should study them until you see how they work. The reason for the second part of the conditional expression,

(UNION `(A B C) `(C B E))=(CONS `A (UNION `(B C) `(C B E)))=(CONS `A (UNION `(C) `(C B E)))=(CONS `A (UNION NIL `(C B E)))=(CONS `A `(C B E))=`(A C B E)

The definition of the power set deserves careful study, since it illustrates a "trick" that we often have to resort to when programming in LISP. The first thing we do is obvious; we ask if our set is the empty set. If it is, then the answer is the set containing the empty set,

After that, things aren`t so obvious. The key to the problem is to ask what we can compute and what we could do with that. Well, we can compute the power set of the rest of the set with

Having the set of all subsets of the rest of the set, then what we have to do is to take each element (subset) from that set and include it in the power set once without the first element and once again as another set with this element added to it.

In order to do this we invent another function called

A sample of how this process works is as follows:

(POWER `(A B)=(SPREAD `A (POWER (CDR `(A B))))=(SPREAD `A (POWER `(B)))=(SPREAD `A (SPREAD `B (POWER (CDR `(B)))))=(SPREAD `A (SPREAD `B (POWER NIL)))=(SPREAD `A (SPREAD `B `(NIL)))=(SPREAD `A (CONS (CONS `B NIL) (CONS NIL (SPREAD `B NIL))))=(SPREAD `A (CONS (CONS `B NIL)(CONS NIL NIL)))=(SPREAD `A (CONS (CONS `B NIL) `(NIL)))=(SPREAD `A (CONS `(B) `(NIL)))=(SPREAD `A `((B) NIL))=(CONS (CONS `A `(B)) (CONS `(B) (SPREAD `A `(NIL)))))=(CONS (CONS `A `(B)) (CONS `(B) (CONS (CONS `A NIL) (CONS NIL (SPREAD 'A NIL))))))=(CONS (CONS `A `(B)) (CONS `(B) (CONS (CONS `A NIL) (CONS NIL NIL)))))=(CONS (CONS `A `(B)) (CONS `(B) (CONS (CONS `A NIL) `(NIL)))))=(CONS (CONS `A `(B)) (CONS `(B) (CONS`(A) `(NIL)))))=(CONS (CONS `A `(B)) (CONS `(B) `((A) NIL))))=(CONS (CONS `A `(B)) `((B)(A) NIL)))=(CONS `(A B) `((B)(A) NIL)))=`((A B)(B)(A) NIL)

As we stated above, all the LISP supervisor does is to evaluate an expression, print out its value, and then proceed on to the next expression.

When one makes a mistake, he will either get gibberish as an answer or the LISP system will eventually catch him attempting some illegal operation and complain.

The most common messages appear below along with the most common mistakes that cause them. For a complete list of LISP diagnostics, consult the Reference Manual.

The internal push-down stack used by LISP during evaluation of expressions has exceeded its bounds. This is invariably caused by "infinite" recursion, i.e, writing a function that keeps calling itself without ever stopping for some terminal condition. Either you forgot to check for the terminal condition, or you didn`t check for it in the right place. This is the LISP equivalent of putting your program in an infinite loop.

Will occur when you have not parenthesised a conditional expression correctly or mispelled

Invariably means that you have written a FORTRAN like expression instead of LISP. That is, you wanted to apply a function to some arguments and you wrote

You have typed in an expression and anxiously await its value and nothing happens. You probably haven`t parenthesised it correctly and there are more left than right parentheses so as far as LISP knows, you haven`t typed in the whole expression yet. Type in a bunch of right parentheses and see what happens.

or

You have probably applied a system defined function to an illegal argument. E.g, you might have asked for the length of a number instead of a list or something similar.

You have used the variable

After the

In other cases, when help probably wouldn`t enable evaluation to proceed, then the LISP system merely returns to the supervisor to evaluate the next expression. But on the way back, it prints out a backtrace, which is a listing of the expressions that were in the process of being evaluated.

By studying the example below, you should be able to get an idea of what is in a backtrace and how to use it.

Here`s another example of a session with the 1100 LISP system that illustrates some of the diagnostics, a backtrace, and one of the control statements (see next section).

In this example we define a function to compute the number of elements in a list but use the atomic symbol

@LISP 1100 LISP 7.72 EVAL: (CSETQ LENGTH (LAMBDA (L) (COND ((NULL L) ZERO) (T (PLUS 1 (LENGTH (CDR L> VALUE: [LENGTH] (LENGTH `(A B C D)) UNBOUND ZEROC HELP: 0 VALUE: 4 EVAL: (LENGTH `(A B> UNBOUND ZERO HELP: :BACK ... (COND ((NULL L) ZERO) (T (PLUS 1 &))) ... (LENGTH (CDR L)) ... (PLUS 1 (LENGTH (CDR L))) ... (COND ((NULL L) ZERO) (T (PLUS 1 &))) ... (LENGTH (CDR L)) ... (PLUS 1 (LENGTH (CDR L))) ... (COND ((NULL L) ZERO) (T (PLUS 1 &))) ... (LENGTH (QUOTE (A B))) EVAL: (CSETQ ZERO 0) VALUE: 0 EVAL: (LENGTH `(A B C D E F G H I J)) VALUE: 10

Note how we simply filled in the value we wanted for

If we wished, we could have fixed this problem by merely rewriting the length function using

There are certain control statements that the 1100 LISP system will respond to whenever it is reading input. These all start with a colon in column 1.

The most useful ones are listed below. Again, for a complete list, consult the

Causes the LISP system to immediately return to the supervisor and request the next expression to evaluate.

Causes the LISP system to return to the supervisor just like

Causes a backtrace to be printed just like

Is a transparent control statement that instructs the LISP system to list input lines as they are read. Input lines are normally listed in batch mode and normally are not listed in timesharing mode.

Is a transparent control statement that turns off the listing of input lines as they are read.

May be inserted in front of images that are to be read by the LISP pseudo-function named

Is used in front of function defining expressions that are kept in a symbolic element and loaded into LISP via

Turns off

There is a useful feature in 1100 LISP that allows you to monitor the evaluation of expressions and application of functions in order to find out what is going on.

This facility was written in LISP by

This library is (of course) called

somewhere within a LISP run.@ADD LISP*LIB.DEBUG

The main pseudo-function of the tracing package is named

As usual, full details will not be given here but will be reserved for the Reference Manual.

The pseudo-function named

Each of these functions will have the values of their arguments printed when they are applied to arguments and will have their result printed after they have computed it.

The pseudo-function named

The best way to illustrate how tracing works is with an example. The sample session below continues from the example in section 5.2 assuming that the set-theoretic functions have already been defined.

EVAL: @ADD LISP*LIB.DEBUG VALUE: DEBUG PACKAGE LOADED EVAL: ($TRACE `(INTERSECTION POWER)) VALUE: T EVAL: (INTERSECTION `(A B C D) `(E C F A)) >ENTERING INTERSECTION [0] SA: (A B C D) SB: (E C F A) >ENTERING INTERSECTION [1] SA: (B C D) SB: (E C F A) >ENTERING INTERSECTION [2] SA: (C D) SB: (E C F A) >ENTERING INTERSECTION [3] SA: (D) SB: (E C F A) >ENTERING INTERSECTION [4] SA: NIL SB: (E C F A) <LEAVING INTERSECTION [4] $VAL: NIL <LEAVING INTERSECTION [3] $VAL: NIL <LEAVING INTERSECTION [2] $VAL: (C) <LEAVING INTERSECTION [1] $VAL: (C) <LEAVING INTERSECTION [0] $VAL: (A C) VALUE: (A C) EVAL: (POWER `(A B C)) >ENTERING POWER [0] S: (A B C) >ENTERING POWER [1] S: (B C) >ENTERING POWER [2] S: (C) >ENTERING POWER [3] S: NIL <LEAVING POWER [3] $VAL: (NIL) <LEAVING POWER [2] $VAL: ((C) NIL) <LEAVING POWER [1] $VAL: ((B C) (C) (B) NIL) <LEAVING POWER [0] $VAL: ((A B C) (B C) (A C) (C) (A B) --) VALUE: ((A B C) (B C) (A C) (C) (A B) (B) (A) NIL) EVAL: ($TRACE`(SPREAD)) VALUE: T EVAL: ($UNBUG`(INTERSECTION)) VALUE: T EVAL: (POWER(INTERSECTION `(A B C D) `(E C F A))) >ENTERING POWER [0] S: (A C) >ENTERING POWER [1] S: (C) >ENTERING POWER [2] S: NIL <LEAVING POWER [2] $VAL: (NIL) >ENTERING SPREAD [2] E: C PS: (NIL) >ENTERING SPREAD [3] E: C PS: NIL <LEAVING SPREAD [3] $VAL: NIL <LEAVING SPREAD [2] $VAL: ((C) NIL) <LEAVING POWER [1] $VAL: ((C) NIL) >ENTERING SPREAD [1] E: A PS: ((C) NIL) >ENTERING SPREAD [2} E: A PS: (NIL) >ENTERING SPREAD [3] by E: A PS: NIL <LEAVING SPREAD [3] $VAL: NIL <LEAVING SPREAD [2] $VAL: ((A) NIL) <LEAVING SPREAD [1] $VAL: ((A C) (C) (A) NIL) <LEAVING POWER [0] $VAL: ((A C) (C) (A) NIL) VALUE: ((A C) (C) (A) NIL)

As we noticed above, the primary tool for building "programs" in LISP is to define recursive functions. There has been nothing that resembles the sequences of statements, for-loops, and goto`s of other languages.

There are times when writing things as sequences of statements is more convenient, than writing them as recursive functions.

There is a feature in LISP that allows us to do this. You may be surprised that it hasn`t been mentioned before. The reason for this is that the real power of LISP lies in its ability to handle recursive functions. To emphasize this point, you should know, although you may not believe, that anything that can be computed using the

Anyway,

Each(PROG (V1 V2...) S1 S2...)

The rule for evaluating a

The

The expression

The special form

As an example of the use of

(CSETQ LENGTH (LAMBDA (L) (PROG (N) (SETQ N 0) LOOP (COND ((NULL L) (RETURN N))) (SETQ N (PLUS N 1)) (SETQ L (CDR L))) (GO LOOP) )))

Notice that the conditional expression (really statement here) used above has an undefined value whenever

Also notice that

As another example of the use of

(CSETQ SUPERREVERSE (LAMBDA (L) (PROG (SRL) LOOP (COND ((NULL L) (RETURN SRL)) ((ATOM (CAR L)) (SETQ SRL (CONS (CAR L) SRL))) (T (SETQ SRL (CONS (SUPERREVERSE (CAR L)) SRL)))) (SETQ L (CDR L)) (GO LOOP) )))

Note that there are still no restrictions about functions calling themselves recursively. Even though the

Compare this with the definition of

(CSETQ SUPERREVERSE (LAMBDA (L) (COND ((NULL L) NIL) ((ATOM L) L)) (T (STICKATENDOF (SUPERREVERSE (CDR L))(SUPERREVERSE (CAR L)))) ))) (CSETQ STICKATENDOF (LAMBDA (L E) (COND ((NULL L) (LIST E)) (T (CONS (CAR L) (STICKATENDOF (CDR L) E))) )))

In this case, defining

I know that once you`ve learned about the

It is also the case that by using the

As we saw above, the normal method of "inputting data" to a LISP program is to write it as arguments to a function and the "output" of the program is the result computed by that function. For most LISP applications, this serves quite nicely; however, there are times when we want to read LISP objects off of cards and print our answers ourselves.

The pseudo-functions below are some of the basic input-output facilities in 1100 LISP; the Reference Manual contains a complete list.

The value of the expression

The value of the expression

The effect of the expression

The effect is to set the input routine to begin the next read in column

The effect is to edit the object

The effect is to edit the object

The next

The effect is to edit the object

Prints the internal print buffer. The value is

The value of the expression

The effect is to cause

As an example of the use of these Input-output pseudo-functions, the definition below creates a LISP supervisor that goes through essentially the same read-eval-print loop that the real LISP supervisor does.

(CSETQ LISP (LAMBDA() (PROG (EXP VAL) LOOP (CLEARBUFF) (PRINT 'EVAL!:) (SETQ EXP (READ)) (SETQ VAL (EVAL EXP)) (PRIN1 'VALUE!:! ) (PRINT VAL) (GO LOOP) )))

One of the things that it is much easier to do in LISP than in other languages is to supply functions as arguments to other functions. The reason for this is that functions in LISP are data objects just like anything else. We noticed this above when we merely assigned a function to a variable in order to give it a name.

As an example, suppose that we wanted to define a function that would take a list and another function as arguments and whose result would be a new list consisting of the result of applying that function to each element.

E.g, assuming that we have defined a function named

We define this function exactly like we would expect to; the only thing that is so surprising is that the definition is so natural and easy.

(CSETQ INTO (LAMBDA(L FN) (COND ((NULL L) NIL) (T (CONS (FN (CAR L)) (INTO (CDR L) FN))) )))

Note that we now could also write something like

As another example, we could define a function to find out if each element of a list has a certain property like so:

(CSETQ IFALL (LAMBDA (L P) (COND ((NULL L) T) ((P (CAR L)) (IFALL (CDR L) P)) (T NIL) )))

So

Along with the functions and special-forms that we have learned already, there are a few others that you might find useful. These are listed below.

A complete list of all functions available in 1100 LISP appears in the reference manual.

In some cases, the functions below will be defined in LISP by means of the primitive functions you know already just to give you more examples of LISP definitions.

(CSETQ APPEND (LAMBDA (L1 L2) (COND ((NULL L1) L2) (T (CONS (CAR L1) (APPEND (CDR L1) L2))) )))

E.g,

(CSETQ MAP (LAMBDA (L FN) (PROG() AGAIN (COND ((NULL L)(RETURN NIL)) (FN (CAR L)) (SETQ L (CDR L)) (GO AGAIN) )))

See definition above in 6.3.

Here is a final example of a LISP session from a terminal. In this example we use LISP to develop a system to do algebraic simplification. The problem of algebraic simplification is quite complex and the example here is far from anything resembling a full treatment, but it does give an example of the kinds of things that LISP is good at.

This example only handles a part of the simplification that we would want to do with addition and multiplication. It assumes that the expressions are written in LISP. We also include a pseudo-function to define "constants".

In this case, we use the editor to create a symbolic element and @ADD it into LISP. This is so that we can save and modify the LISP program that we are developing. This gets kind of messy since it means that we have to leave LISP, use the editor to make changes, and come back to LISP whenever we need to redefine a function and have the definition remembered. Or we have to remember to change our symbolic element later and redefine the function within LISP.

There are facilities in LISP that allow us to do text editing and filing of function definitions, but they require a familiarity with LISP that we felt was beyond the scope of this primer. They are detailed in the Reference Manual.

@ASG,A MYFILE @EDIT,I MYFILE.SIMPLIFY EDIT 1.33-1/16-2:33 INPUT :LOAD <CSETQ SIMPLIFY (LAMBDA [EXP] (COND [(ATOM EXP) (VALUEOF EXP VALUELIST)] [T (REDUCE (CAR EXP) (INTO (CDR EXP) SIMPLIFY))] )) <CSETQ VALUEOF (LAMBDA [VAR VL] (COND [(NULL VL) VAR] [(EQ (CAAR VL) VAR)(CADAR VL)] [T (VALUEOF VAR (CDR VL))] ))> <CSETQ REDUCE (LAMBDA [OP ARGS] (COND [(EQ OP 'PLUS) (DOPLUS (CAR ARGS) (CADR ARGS))] [(EQ OP'TIMES) (DOTIMES (CAR ARGS) (CADR ARGS))] [T (CONS OP ARGS)] ))> <CSETQ DOPLUS (LAMBDA [A1 A2] (COND [(NUMBERP A2) (COND [(ZEROP A2) A1] [(NUMBERP A1) (PLUS A1 A2)] [(ATOM A1) (LIST 'PLUS A1 A2)] [(AND (EQ (CAR A1) 'PLUS)(NUMBERP (CADDR A1))) (DOPLUS (CADR A1)(PLUS (CADDR A1) A2))] [T (LIST 'PLUS A1 A2)] )] [(NUMBERP A1) (DOPLUS A2 A1)] [(EQUAL A1 A2) (DOTIMES A1 2)] [T (LIST 'PLUS A1 A2)] ))> <CSETQ DOTIMES (LAMBDA [A1 A2] (COND [(NUMBERP A2) (COND [(ZEROP A2) 0] [(EQUAL A2 1) A1] [(NUMBERP A1)(TIMES A1 A2)] [(ATOM A1) (LIST 'TIMES A1 A2)] [(AND (EQ (CAR A1)'TIMES) (NUMBERP (CADDR A1))) (DOTIMES (CADR A1) (TIMES (CADDR A1) A2))] [T (LIST 'TIMES A1 A2)] )] [(NUMBERP A1) (DOTIMES A2 A1)] [T (LIST 'TIMES A1 A2)] ))> <CSETQ VALUELIST NIL> <CSETQ DEFINE (LAMBDA [VAR VAL] (PROG[] <UNDEFINE VAR> <CSETQ VALUELIST (CONS (LIST VAR VAL) VALUELIST)> (RETURN (LIST VAR 'DEFINED 'AS VAL)) ))> <CSETQ UNDEFINE (LAMBDA[VAR] (PROG[L] <SETQ L VALUELIST> <CSETQ VALUELIST NIL> LOOP <COND[(NULL L) (RETURN (LIST VAR 'UNDEFINED))] [(NOT (EQ (CAAR L) VAR))<CSETQ VALUELIST (CONS (CAR L) VALUELIST)>]> <SETQ L (CDR L)> <GO LOOP> ))> :END 'SIMPLIFY! LOADED @LISP LINES FILED: 67 1110 LISP 7.72 EVAL: @ADD MYFILE.SIMPLIFYVAR VALUE: SIMPLIFY LOADED EVAL: (SIMPLIFY '(PLUS 0 A> VALUE: A EVAL: (SIMPLIFY '(TIMES 3 (PLUS (TIMES B 1)B> VALUE: (TIMES B 6) EVAL: (DEFINE 'K 6) VALUE: (K DEFINED AS 6) EVAL: (SIMPLIFY '(PLUS 3 (PLUS A K> VALUE: (PLUS A 9) EVAL: (SIMPLIFY '(PLUS A (DIFFERENCE K A> VALUE: (PLUS A (DIFFERENCE 6 A)) EVAL: (DEFINE 'C 7) VALUE: (C DEFINED AS 7) EVAL: (SIMPLIFY '(TIMES C (TIMES A K> VALUE: (TIMES A 42) EVAL: (UNDEFINE 'K> VALUE: (K UNDEFINED) EVAL: (SIMPLIFY '(TIMES C (TIMES A K> VALUE: (TIMES (TIMES A K) 7) EVAL: (SIMPLIFY '(PLUS A (PLUS C (PLUS A -7> VALUE: (TIMES A 2)

The following is a list of atomic symbols that have constant values when LISP is loaded.

These atomic symbols, and any others that you use as names of functions, cannot be used as names for variables. It is not necessary that you memorize this list. Just look it over and see if there are any that you would be likely to use (like

The ones that are underlined are the ones that have been described in this primer; the others are described in the Reference Manual.

ADD1 | ALIST | AMB | AND | APPEND | ASSOC | ATOM |
---|---|---|---|---|---|---|

ATSYMB | ATTEMPT | BACKSP | BACKTR | BREAK | CAR | CDR |

CADR | CADDR | CDDR | CLEARBUFF | COMPRESS | COND | CONS |

CSETQ | CSET | CURRCOL | DATE | DEFINE | DEFMAC | DEFSPEC |

DELIM | DIFFERENCE | DO | DTIME | DUMP | ENTIER | EQ |

EQUAL | ERASE | ERROR | EVAL | EXPLODE | EXPLODE2 | F |

FIXP | FLAG | FLOATP | FUNCTION | GCTIME | GENSYM | GET |

GO | GREATERP | GROW | IFFLAG | IFTYPE | INDEX | INTO |

LAMDA | LAMBDA | LEFTSHIFT | LENGTH | LESSP | LIST | LISP |

LOAD | LOGAND | LOGXOR | LOGOR | MANIFEST | MAP | MAPCAR |

MAPLIST | MAPC | MEMBER | MEMORY | MINUS | MINUSP | NCONC |

NIL | NOT | NTH | NULL | NUMBERP | OBLIST | ONDEX |

ONTO | OR | PLENGTH2 | PLENGTH | PLIMIT | PLUS | PRIN2 |

PRIN1 | PRINT | PROP | PROG | PUT | QUOTIENT | QUOTE |

READMAC | READCH | READ | REMPROP | REMAINDER | REQUEST | RETURN |

REVERSE | RPLACD | RPLACA | SET | SETCOL | SETQ | SPACE |

STACK | STRING | SUB1 | SUBST | T | TERPRI | TIME |

TIMES | TOKEN | UNBREAK | UNFLAG | ZEROP | *BEGIN | *CAR |

*CDR | *CHAIN | *DEF | *DEPOSIT | *EMIT | *EPT | *EXAM |

*MACRO | *ORG | *PACKIT | *SPEC |

Learning LISP is just like learning to play the piano. You can read all you want about chords, scales and what not, but you still won`t know how to play the piano. The only way that you learn is to sit down and practice it. The same is true of LISP, you can read this as many times as you like, but you won`t be able to write LISP programs until you practice writing a few. So sit yourself down at a terminal and try writing something in LISP.

If you don`t have any ideas about things to try, the suggestions below are some simple exercises. Try defining the functions to do what is required and try them out on a few test cases.

These exercises are listed in approximately their order of difficulty.