LISP PRIMER
by Eric Norman


This primer gives an introduction to LISP, a high-level language for symbolic computations. Only the fundamentals of the language are presented in a manner that should allow one who has had a little experience with other programming languages to become familiar with LISP.

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.


TABLE OF CONTENTS 

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


Chapter 1
INTRODUCTION to LISP

LISP is another programming language that belongs in the category of list processing languages; that is, it deals with (manipulates, performs computations on) objects that have a certain amount of structure. Although there is essentially only one type of structured object in LISP, it is a very general one and can serve to represent any type of structured object desired (although sometimes not too efficiently). LISP is at its best when dealing with objects that have unpredictable sizes, like representations of theorems in the propositional calculus, possible moves to be made in a game such as chess, complex molecules in organic chemistry, or electrical circuits; LISP has been used to solve problems in all these areas.

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.



Chapter 2
THE UNIVERSE OF DISCOURSE

In order to gain an understanding of any programming language, we must eventually be able to answer three questions. First, what objects are available to manipulate, i.e. what types of data are allowed? Second, what are the manipulations or computations that we are allowed to perform on these data? And finally, how do we indicate the computations that we desire? We are not going to answer these questions in their entirety at the beginning. We shall answer them only partially and, hopefully, simply enough that we can grasp the fundamentals of LISP. A more complete treatment will be held off until later.

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.


2.1 ATOMIC 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  ,  .  (  )  [  ]  <  >  `  ?


2.1.1 NUMBERS

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 0, +3, 10, -256, 1E6 (same as 1000000), and -0. Examples of non integers are +, A, 3AB, -10EE.0.

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 0Q, 77Q3 (same as 77000Q), and -77Q2. A minus sign indicates one`s complement and scaling is performed by doing a circular left shift, so the last is the same as 777777770077Q.

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 0.0, 3.14159, 4.3E10, and -2.061E-22.


2.1.2 ATOMIC SYMBOLS

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 BKBP; if we didn`t have atomic symbols, we would have to represent this piece by some number such as 113. Atomic symbols are written in LISP as a sequence of letters or digits that begins with a letter of the alphabet. The following are all legitimate atomic symbols A, ALONGERONE, NIL, P1, and TRINITROTOLUENE. If we need to include a LISP punctuation mark in an atomic symbol, then we must precede it with an "!" so the LISP system will not think that it is the end of one atomic symbol and the beginning of the next, for instance, THIS!IS!ONE!ATOMIC!SYMBOL!,!NOT!SEVEN.

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 "atomic symbol" when we mean exactly that.


2.1.3 FUNCTIONS

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.


2.2 LISTS

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,C), [D E F], (A123 . 456BCD), (ONE), and (). The next to last is a list of one element, which is not the same as a single atomic symbol. The last is the empty list which happens to be equivalent to the atomic symbol NIL, and they can be used interchangably. Lists can contain other lists as elements, or sublists, so the following are also perfectly good 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: (P IMPLIES Q), or ((A AND B)IMPLIES A).



Chapter 3

THE FUNCTIONS


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: (FN ARG1 ARG2). This means that the function symbolized by FN is to be applied to the two arguments symbolized by ARG1 and ARG2. In most other languages, this would be written as FN(ARG1, ARG2). We know that the LISP notation is unusual and is going to cause confusion in the beginning, but you are just going to have to live with it. Some of the features available in LISP are so powerful that this syntax is necessary in order to avoid ambiguities. Anyway, examples of things that we might write in LISP programs are:

(PLUS A 3), or (TIMES N (PLUS N M)), which are equivalent

to the more familiar A+3 and N*(N+M).


3.1 QUOTATION

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 (TIMES N (PLUS N M)). As we saw above, the LISP object (PLUS N M) is a subexpression of the larger expression; the above does not mean to multiply whatever N is by the LISP object that is a list containing the atomic symbols PLUS, N, and M. The distinction here is very important; this same problem arises in other languages when you have to put some sort of quote marks around a character string (alias Hollerith constant) in order that the compiler doesn`t think that you are meaning the value of some identifier. In LISP the problem is a little more acute since LISP programs also happen to be LISP data objects.

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 (TIMES N `(PLUS N M)), then we mean the product of whatever N is and the actual LISP object that is the list consisting of the atomic symbols PLUS, N, and M, which of course is nonsense since multiplication by a list is not a legal operation, so writing the above would result in garbage, but it does illustrate the point.


3.2 SOME PRIMITIVE FUNCTIONS

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.


3.2.1 CONSTRUCTION

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 CONS, and essentially results in prefixing an element to the front of a list. For instance, the result of the LISP expression (CONS `A `(B C D)) is the list (A B C D). Note the use of the apostrophies; we really meant the atomic symbol A, not what it meant when interpreted as an identifier. The result of (CONS `(A B) `((C D) E)) is the list and sublists ((A B)(C D)E). Note that the result of CONS is always a list of length one greater than its second argument; i.e. the result is as shown above, which is not the same as the list (A B (C D) E).

Another important point. Doing the above in no way altered the arguments supplied to CONS; i.e. CONS is a function, not an operation. Consider that when in other languages you write something like A+3, you get as a result the sum of whatever A is and 3; what you have not done is to change the value of whatever A is to three more than that. Exactly the same is true of CONS, if we wrote (CONS `A L) we would get a list that starts with the atomic symbol A and then would follow the elements of the list represented by L (note lack of apostrophe before L). If we use L elsewhere it still means exactly the same list as it meant before, not the new list that has A as its first element.

As further examples of the use of CONS, the result of each of the expressions below is as shown:


(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)


3.2.2 SELECTION

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 CAR, and is a function of one argument which when applied to a list selects its first element. E.g. (CAR `(A B C)) results in the atomic symbol A, and (CAR `((A B)(C D)) = (A B).

The other selection function is symbolized by CDR and when applied to a list results in the list that remains after the first element is removed. For example, (CDR `(A B C)) = (B C) and (CDR `((A B)(C D))) = ((C D)).

The admonition that was given about CONS above also applies to CAR and CDR. They are functions, not operations; they compute something rather than do something. E.g. applying CDR to a list gives you a list that is one element shorter than its argument, just like writing N-1 in other languages gives you a new number without changing N to one less than it used to be.

Another way of looking at CAR and CDR is that CAR selects the first (element) of a list and CDR selects the rest of the list. CAR and CDR can be applied to lists only. Attempting to apply one to an atom is an error and will result in severe chastisement by the LISP system.

The examples below show more clearly the uses of CAR and CDR and how they relate to CONS:


(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)
Here`s a handy little abbreviation you will want to know about. Instead of writing (CAR (CDR x)), we can write (CADR x), and (CADADR x) can be written instead of (CAR (CDR (CAR (CDR x)))), and so forth. The limit happens to be 35 A`s and D`S, but nobody has come close to that with anything useful yet. Anyway, the ones that you especially want to remember are CAR, CADR, CADDR, CADDDR, etc., which select the first, second, third, fourth, etc. elements of a list, and CDR, CDDR, CDDDR, etc., which "chop off" the first, the first two, the first three, etc. elements of a list.

And just to satisfy your curiosity, the names CAR and CDR are historical, traditional, and downright silly. They arose because LISP was originally implemented on a 7090 where CAR and CDR mean contents of address register and contents of decrement register, respectively, which is directly related to the method of representing lists in memory. The names CAR and CDR are so traditional that nobody has had the courage to change them into something reasonable like HEAD and TAIL, or FIRST and REST. Furthermore, just so you can sound like you know what you are talking about when you talk to your friends about LISP, CAR is pronounced in the obvious manner and CDR is pronounced could-er.


3.3 EXAMPLE

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. (LENGTH `(A B C)) = 3. We would write the following:


(CSETQ LENGTH (LAMBDA (L)
  (COND
    ((NULL L) 0)
    (T (PLUS 1 (LENGTH (CDR L))))
  )))
Essentially what the above says is that we want to define a function symbolized (named) by the atomic symbol LENGTH and that it is a function of one argument that we will call L. The result of this a function is to be computed as follows: if its argument, L, is the empty list, then its length is 0; otherwise, its length is one more than the length of a list that is one element shorter than L.

Now after we have defined this function, we can test it out by simply writing (LENGTH `(A B C)) and the system will respond with the value of this expression, 3. The way that the above function computes the length of a list is mildly interesting; it essentially goes thru the steps below during the evaluation of the expression (LENGTH `(A B C)).


(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
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 0 before starting. This is an example of some "dirty work" that LISP saves you from doing.

What we did above that allowed us to define the length function so easily was to define LENGTH in terms of itself; i.e. in order to compute the length of a list, we used the length function that we were defining to compute the length of another (shorter) list. Of course the above technique won`t work unless we finally get to a place where we no longer need the length function; i.e. we finally arrive at the empty list, NIL, and we know its length. But any reasonable amount of intuition will tell you that you have to eventually get there and the above definition therefore has to work. Anyway, this technique of defining a function in terms of itself is called recursion. As you will find out, the use of recursion just seems to fit naturally with LISP and after a little practice it should become second nature. Furthermore, this is the last time I am going to mention it since to dwell on it tends to give it some aura of magic that it doesn`t really deserve. Recursion, or "thinking recursively", or whatever else it`s called is nothing more than simply applying functions to arguments.

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 LENGTH function above was an expression. It just happens that the value of that expression was not very interesting, what we were really interested in in that case was its effect, i.e. defining a function. There are some "functions" in LISP that are usually applied for their side-effects rather than for their result. These are called pseudo-functions in LISP. The pseudo-function CSETQ above is an example; its main purpose is to affect the LISP system so that it "remembers" that a function has been defined.


3.4 MORE PRIMITIVE FUNCTIONS

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.

(EQ x y) is true if x and y are the same atomic symbols. It is false if either is an atomic symbol and the other is not the same atomic symbol. It is undefined if neither is an atomic symbol.

Truth in LISP is represented by the atomic symbol T and falsehood is represented by the atomic symbol NIL.


(EQ `A `A) = T 

(EQ `A `B) = NIL

(EQ `A `(A)) = NIL

(EQ 1 `A) = NIL

(EQ 1 1) = undefined
(ATOM x)is true if x is an atom and false otherwise. E.g. (ATOM `ATOM) = T, (ATOM 1) = T, and (ATOM `(LIST)) = NIL.

(NULL x)is true if x is the empty list and false otherwise. (NULL x) is equivalent to (EQ x NIL) E.g. (NULL `A) = NIL, (NULL NIL) = T, (NULL (CDDR `(AB))) = T.

(PLUS x y z...) = x+y+z+... (Any number of arguments allowed.)

(TIMES x y z...) = x*y*z*... (Any number of arguments allowed.

(DIFFERENCE x y) = x-y.

(QUOTIENT x y) = the quotient when x is divided by y.

(REMAINDER x y) = the remainder when x is divided by y.

(EQUAL x y) = true if and only if x and y are the same LISP object; i.e, would look the same if printed. EQUAL must be used to compare numbers for equality, not EQ.

(GREATERP x y) = true if and only if x is greater than y.

(LESSP x y) = true if and only if x is less than y.

(ZEROP x) = true if x is the integer 0, false otherwise.

(LIST x y z...) = the list consisting of the objects x, y, z, etc. i.e, the object (x y z...). Hey! Wait a minute, you say. If I want to get the object (x y z...), why can`t I just write the list (x y z...)? The reason is that when you write (x y z...) as an expression you mean the function x applied to the arguments y, z, etc. Make sure you understand the difference. As I mentioned above, LISP programs (expressions) are also LISP objects and it is vital that you know when you are writing programs (expressions) and when you are writing data (literal LISP objects). Observe the following: (LIST `PLUS 1 2) evaluates to the LISP object (PLUS 1 2), whereas the expression (PLUS 1 2) evaluates to 3. Also notice that (LIST `A `(BC)) = (A (BC)) while (CONS `A `(BC)) = (A BC).



Chapter 4.

THE LANGUAGE


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.


4.1 EVALUATION

An important notion in LISP is that of evaluation. As stated above, all LISP programs are just expressions and evaluation is the process by which we find the value of such expressions.

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.


4.1.1 EVALUATION OF ATOMS

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 (CSETQ PI 3.14159265) assigns the real number 3.14159265 to the variable PI. CSETQ in LISP corresponds most to the assignment statement in other languages. The variable PI will retain this value until it is changed by another CSETQ.

The other kind of variable in LISP is called a fluid variable and is used to establish a correspondence between the dummy variables used in the definition of a function and the actual arguments to which that function is applied. That is, it corresponds to parameters, or formal parameters, or local variables, or whatever you call them in other languages. Their values change whenever we apply functions to arguments. They can also be changed explicitly in some cases but we really don`t need to know about that yet.


4.1.2 EVALUATION OF LISTS

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 (FN ARG1 ARG2...) is computed by first evaluating FN, ARG1, ARG2, etc. and then applying the function that is the value of FN to the arguments that are the values of the ARG`s. The value of whatever FN is must be a function; if it isn`t, we have made a mistake and the LISP system will complain.

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 `(A B) above, what we were really doing was writing an abbreviation for the expression (QUOTE (A B)). QUOTE is one of those special atomic symbols and the rule is that whatever appears after it is the actual value of the expression and is not to be evaluated.

If QUOTE were treated as the name of a function, then the above would mean that function applied to the value of the expression (A B), which in turn means function named by A applied to whatever B is, and that is not what we want.

Another one of these special atomic symbols is CSETQ which we used above. This is special because the variable that we assign a value to is the variable itself and is not evaluated (if it were, we would be assigning to whatever the variable represented, which isn`t what we want and would usually be an error).

We will now learn a few more of these special atomic symbols, which are called special-forms in LISP.


4.2 COND

The special-form COND is used to get the "if-then-else" idea. It is written like this:

    

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

The rule for evaluating this special-form is this: the Pi`s are evaluated from the left until one is found that evaluates to the atomic symbol T (truth). As soon as one is found, the corresponding Ei is evaluated and its value is the value of the entire conditional expression; everything after that is ignored.

If no Pi`s are true, the value of the conditional expression is undefined. Consider again the example program above: 


(CSETQ LENGTH (LAMBDA(L)
  (COND
    ((NULL L) 0)
    (T (PLUS 1 (LENGTH (CDR L)))))
The expression (NULL L) is the first P, (note carefully the placement of parentheses), 0 is the first E, T is the second P, and (PLUS 1...) is the second E.

If (NULL L) is true, then the value of the entire conditinal expression is 0. If not, then we evaluate the atomic symbol T, which is a constant provided by the system that always evaluates to itself, so if we ever get to the second P-E pair, the second P is guaranteed to be true. Writing this T in the final pair of a conditional expression is equivalent to using "else" or "otherwise" in other languages and should always be done to guarantee that the conditional expression has a value.

As another example of the use of COND, suppose that we have two variables M and N and we want the maximum of the two. The following conditional expression will evaluate to what we want:



     (COND ((GREATERP M N) M)(T N))
I.e. it evaluates to M if M is greater than N and N otherwise.


4.3 AND, OR

Special forms of the form (AND E1 E2...) or (OR E1 E2...) have their obvious meanings. The only reason that they are special-forms is that all of the "arguments" to AND or OR are not necessarily evaluated. Evaluation stops as soon as one is found whose value guarantees the value of the entire expression. E.g. the first Ei found from the left in the expression (OR E1 E2...) that is true will cause evaluation to cease with the value of the entire expression being true.


4.4 LAMBDA

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 (COND ((GREATERP M N) M)(T N)) every time that we want the larger of M and N. What we want to do is use this expression to define a function of our own called MAX and then write (MAX M N) whenever we want the larger of the two.

There is a very useful special-form in LISP that allows us to turn expressions into functions. The special-form (LAMBDA (V1 V2...) exp) means (evaluates to) the function of the variables V1, V2, etc. that is computed by exp.

Each Vi is an atomic symbol and exp is a LISP expression that tells how to compute the result of the function from the arguments symbolized by the Vi.

For instance, the expression (LAMBDA (X Y)(PLUS X (TIMES X Y))) has as its value that function of X and Y that is computed by X+X*Y.

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



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

Notice that the expression (PLUS X (TIMES X Y)) is not a function. If it were, then we could apply it to some arguments by writing ((PLUS X (TIMES X Y)) 4 5), which is nonsense since what it says is to take the value of (PLUS X (TIMES X Y)), which would have to be a number, and apply it to the numbers 4 and 5. Applying numbers to other numbers doesn`t make sense since numbers aren`t functions.

The special-form LAMBDA does two things. First, it specifies that we want to create a function, and second, it specifies the correspondence between the arguments for that function and the fluid variables that are used to describe how that function computes its result. What LAMBDA does not do is to give a name to the function that was created thereby.


4.5 NAMING FUNCTIONS

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 (CSETQ PI 3.14159265) we are giving a name to a real number so that we don`t have to write the number everytime we want it. And we do exactly the same thing when we want to give a name to a function, we assign the function to a variable. So, to get back to the original problem, when we want to create a function called MAX that computes the larger of its two arguments, we first create the function that we want with the expression



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


     (CSETQ MAX(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, which is to establish MAX as a constant whose value is the function above. Once this side effect has been done, then we can write (MAX x y) whenever we want the larger of x and y.

Expressions of the form (CSETQ FN (LAMBDA (V1 V2)...)) are the 1100 LISP equivalent of the procedure or function definitions in other languages. They will invariably appear at the beginning of a LISP run in order to define the functions desired.



Chapter 5.

USING THE 1100 LISP SYSTEM

One gains access to the 1100 LISP system by simply typing in @LISP. It is not necessary to give a file or element name since the 1100 LISP system is completely self contained. Once you are signed on with LISP, the LISP supervisor is in a loop that reads expressions, computes and prints their values, and then returns to read the next expression.


5.1 USEFUL INFORMATION

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, (), square, [], or crooked, <>, brackets may be used to delineate lists. The rule for automatic balancing is this: any closing bracket ), ], or >, will close all opening brackets to its left back to and including its corresponding opening bracket, (, [, or <.

E.g. (A [B C D) is a valid 1100 LISP list and is equivalent to (A [B C D]) or (A (B C D)).

Similarly, <A(B (C [D E] F [G) H > is the same as (A (B (C (D E) F(G)) H)).

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 "&". Furthermore, after a certain number of elements of a list or sublist are printed the 1100 LISP system simply prints "--" followed by the ")" closing the list. The main reason for this is that an infinite or circular list will not print forever.

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.


5.2 EXAMPLE

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 {A,B,C} by the list (A B C).

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 "EVAL:" and "VALUE:" were typed by the computer; everything else we typed in ourselves.

A narrative of the membership function goes something like this:

We ask if the set is empty (NULL S); if it is the answer is false and we are done. Otherwise we ask if the first element of the set (CAR S) is equal to the element we are looking for. If neither of the above happens, then we simply ask whether the element is a member of the rest of the set.

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 MEMBER in square brackets.

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 MEMBER.

You should expect such a value whenever you define a function with CSETQ and you can interpretet it to mean "you have just defined a function named [xxxx]".

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 INTERSECTION, we merely wrote an ">" instead of all the required right parentheses. This essentially generated the proper number of right parentheses so that the LISP system saw the end of the expression. Before it goes on to another expression, it skips to the beginning of the next line and the unmatched ">" never bothers anybody.

Furthermore, note the use of square brackets in the conditional expression in the definition of the function named SPREAD to balance the brackets in these subexpressions.

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, (MEMBER (CAR SA) SB), in the union function is to prevent an element from appearing twice in the union if it appears in both sets. For instance, the way that the union of two sets, say (A B C) and (C B E) is computed is for the union function to essentially go through the steps below:


(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, (NIL), not just the empty set, NIL.

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 (POWER (CDR S)).

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 SPREAD to do it.

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)


5.3 DIAGNOSTICS

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.


CANNOT TAKE CAR OR CDR OF x

x is some atom that you have attempted to apply CAR or CDR to. You probably forgot to check if a list was empty when you needed to.


WARNING, x CANNOT BE BOUND BECAUSE OF A MISSING ARGUMENT

x is a fluid variable in a LAMBDA-expression defining a function. You have applied this function to too few arguments.


WARNING, x IS AN ILLEGAL VARIABLE

x is a variable in a LAMBDA-expression defining a function. You shouldn`t use x as such a variable since it has already been established as a constant (via CSETQ or is the name of a system defined function). The constant value would always take precedence so using it as a fluid variable doesn`t make sense. The most common atomic symbols that are used this way are LIST, which is the name of a system function, T, which is a constant always bound to itself and used to represent truth, and F, which is a constant whose value is NIL and can be used to represent falsehood.


STACK OVERFLOW

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.


T IS NOT A FUNCTION


NIL IS NOT A FUNCTION

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


x IS NOT A FUNCTION

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 FN (ARG, ARG), FN (ARG ARG), or (FN (ARG, ARG)) instead of (FN ARG ARG).


nothing happens

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.


ILLEGAL INSTRUCTION: nnnnn

or

GUARD MODE: nnnnn

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.


UNBOUND x

HELP:

You have used the variable x in an expression and it has no meaning, i.e, it is neither a constant nor a current fluid variable. This is usually caused by either simply mispelling the variable somewhere or attempting to apply a function that you haven`t defined yet.


5.3.1 HELP MODE

After the UNBOUND x diagnostic, the 1100 LISP system will type out "HELP:". This means that the evaluation has been interrupted in the middle and you can help it out if you wish. What the LISP system expects is an expression. This expression will be evaluated and its value will be used as the value for the unbound variable. This is most useful when the reason for the unbound variable is that you merely mispelled it. In this case you can simply type in the correct variable after the "HELP:" and its value will be used to continue evaluation. If this is not what you wish, then all you have to do is type in ":LISP" (see control statements below) and return to the next expression to evaluate.


5.3.2 THE BACKTRACE

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.


5.3.3 EXAMPLE

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 ZERO instead of the number 0. The examples shows a couple of ways to solve this problem.



@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 ZEROwhen asked for help the first time and how evaluation proceeded on from there. But just because we supplied a value for ZERO once, it is not permanent until we make it so (via CSETQ).

If we wished, we could have fixed this problem by merely rewriting the length function using 0 instead of ZERO and reassigning it to LENGTH. The new function would replace the old one.


5.4 LISP CONTROL STATEMENTS

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 LISP Reference Manual.

:LISP

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


:BACK x

Causes the LISP system to return to the supervisor just like :LISP does but prints a backtrace on the way back. The type and length of the backtrace is controlled by the mode (batch or timesharing) and x. If x is blank, then just the expressions being evaluated will be printed in timesharing mode. In batch mode both expressions and association lists will be printed. Association lists are used by the LISP interpreter to associate the variables used in LAMBDA-expressions with the arguments to which they are bound. If x is "T", then association lists are printed even in timesharing mode. If x is a number from 1 thru 9, then only that many of the most recent expressions being evaluated will be printed.


:PEEK x

Causes a backtrace to be printed just like :BACK but is transparent; i.e, after the backtrace, the LISP system returns to continue reading just as if a :PEEK had not been done. :PEEK is used after a "HELP:" to look at the backtrace before supplying a value for help.


:LIST

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.


:UNLIST

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


:DATA

May be inserted in front of images that are to be read by the LISP pseudo-function named READ. In batch mode, this will prevent the LISP system from attempting to evaluate these data as expressions if the program reading these data should error out before all of them are read. All data images will be skipped until a :LISP or :END control statement is read.


:LOAD

Is used in front of function defining expressions that are kept in a symbolic element and loaded into LISP via @ADD. :LOAD will put LISP in the :UNLIST mode and will furthermore suppress printing of the EVAL: and VALUE: messages. :LOAD mode remains in effect until an :END control statement is read at which time the listing mode is restored to what it was before the :LOAD control statement was read.


:END

Turns off :LOAD or :DATA mode.


5.5 TRACING

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 Rick LeFaivre and is included in a LISP library on a catalogued file.

This library is (of course) called LISP*LIB. To include the tracing package, merely type in



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

The main pseudo-function of the tracing package is named $TRACE.

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

The pseudo-function named $TRACE can take one argument which is a list of names of functions to be traced.

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 $UNBUG will remove tracing from a list of atomic symbols that name functions.

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)



Chapter 6.

ADDITIONAL FEATURES



6.1 PROG FEATURE

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 PROG feature that we are about to describe can also be computed without it using only recursive functions. It just happens that the PROG feature is, in some cases, more convenient.

Anyway, PROG is a special form and it looks like this:



     (PROG (V1 V2...) S1 S2...)
Each Vi is an atomic symbol and becomes a local variable in the PROG. Each Si is any LISP expression.

The rule for evaluating a PROG is this: First all the Vi`s are initialized as local variables with the value NIL. Then the non-atomic Si`s are evaluated in sequence. The value of each Si is discarded, so each one must be a pseudo-function that somehow affects the state of affairs.

The Si`s are evaluated in sequence until you either fall off the end, in which case the value of the entire PROG-expression is NIL, or until a transfer of control is specified by evaluating an expression of the form (GO x). xis a label and a label is specified by writing an atomic symbol as an Si.

The expression (RETURN exp) also terminates execution of a PROG and the value of the PROG expression is the value of exp written after the RETURN.

The special form SETQ is used within a PROG to change the value of a variable. The effect of the expression (SETQ v exp) is to take the value of the expression exp and assign it to the variable v, replacing the old value.

SETQ can be used on either the local variables of a PROG or on the fluid variables appearing after a LAMBDA that surrounds a PROG.

SETQ acts just like an assignment statement and is very similar to CSETQ. The difference between the two is that CSETQ is used for global constants while SETQ is used on local variables.

As an example of the use of PROG, let's rewrite the LENGTH function that we defined above using the PROG feature.



(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 L is not empty, but we don`t care about that since the value is going to be discarded anyway, what we are interested in is the side effect of the statement.

Also notice that GO`s, SETQ`s or RETURN`s can be written either as one of the "statements" of a PROG, or they can be written as one of the branches in a conditional in a PROG.

As another example of the use of PROG, lets write a function to reverse a list and all its sublists so that (REVERSE `(A (B C D) E F)) = (F E (D C B) A).


(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 SUPERREVERSE function was defined as a PROG, it still uses itself to reverse any sublists that it finds.

Compare this with the definition of SUPERREVERSE written below as a recursive function that requires an auxiliary function.


(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 SUPERREVERSE as a PROG was slightly more convenient that defining it as a recursive function. It also turns out that the PROG definition is in this case more efficient in its usage of both time and space, but don`t assume that this is always the case.

I know that once you`ve learned about the PROG feature, you will find it so similar to FORTRAN or ALGOL or whatever language that you are already familiar with that there will be a great temptation to write LISP programs by writing the corresponding FORTRAN or ALGOL program and then translating it using the PROG feature. I strongly urge you to resist this temptation. It will certainly work but you will end up doing a lot of things the hard way.

It is also the case that by using the PROG feature you are likely to make a lot more mistakes. This is because the PROG feature requires to you to apply pseudo-functions for their side effects, and side-effects by their very nature effect other things elsewhere that you always seem to forget about.


6.2 INPUT - OUTPUT

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.

(READ)

The value of the expression (READ) is the next LISP object that appears in the input stream. The effect is to advance over this object so that successive READ`s read successive LISP objects.


(READCH)

The value of the expression (READCH) is an atomic symbol that is the next character in the input stream. The effect is to advance over this character.


(CLEARBUFF)

The effect of the expression (CLEARBUFF) is to skip to the beginning of the next image; the value is NIL.


(SETCOL c)

The effect is to set the input routine to begin the next read in column c of the current image. The value is NIL.


(PRINT x)

The effect is to edit the object x into LISP`s internal print buffer and print it. The value is x.


(PRIN1 x)

The effect is to edit the object x into the internal print buffer, but the buffer is not printed unless it overflows during editing.

The next PRIN1 or PRINT will begin in the next column of the internal buffer. The value is x.


(PRIN1 x c)

The effect is to edit the object x into the internal print buffer beginning in column c. The value is x.


(TERPRI)

Prints the internal print buffer. The value is NIL.


(CURRCOL)

The value of the expression (CURRCOL) is the next column of the internal print buffer that is due to receive characters.


(SPACE n)

The effect is to cause n blank lines to precede the next line of output. The value is NIL.


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)
  )))


6.3 FUNCTIONS AS ARGUMENTS

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 FACTORIAL then we want to define a function named INTO such that the value of (INTO `(1 2 3 4 5) FACTORIAL) is (1 2 6 24 120).

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 (INTO `(1 2 3 4 5) (LAMBDA (X)(PLUS X 3))) and its value would be the list (4 5 6 7 8).

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 (IFALL `(AB4 CX XX) ATOM) is true while (IFALL `(AB4 (C) X) ATOM) would be false.


6.4 OTHER SYSTEM DEFINED FUNCTIONS

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.

(NOT x)is true if and only if x is false. (NOT x) is equivalent to (NULL x)


(ADD1 x) = x + 1.


(SUB1 x) = x - 1.


(NUMBERP x)is true if x is an integer or a real number and false otherwise.


(MEMBER x m)is true if and only if x is one of the elements of the list m. EQUAL is used for the comparison, not EQ.


(APPEND m1 m2)is the list consisting of the elements of m1 followed by the elements of m2. E.g, (APPEND `(A B C) `(E F G H)) = (A B C E F G H). Note the difference between APPEND and CONS.



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


(SUBST x y z) = a copy of z with every subpart that is the same as y (via EQUAL) changed to x.

E.g, (SUBST `(A) `B `(C B (B) D)) = (C (A)((A))D).


(LENGTH m) = the number of elements in the list m. (LENGTH NIL) = 0; (LENGTH `(A B (C D)E)) = 4.


(REVERSE m) = the list m with its top-level elements written backwards. (REVERSE `(A B (C D) E)) = (E (C D) B A).


(MAP m fn) The pseudo-function fn is applied to each element of the list m. The value is NIL.


(CSETQ MAP (LAMBDA (L FN)
  (PROG()
    AGAIN
    (COND ((NULL L)(RETURN NIL))
          (FN (CAR L))
    (SETQ L (CDR L))
    (GO AGAIN)
  )))
(INTO m fn) = a list each of whose elements is the result of applying fn to an element of the list m.

See definition above in 6.3.


6.5 ONE MORE EXAMPLE

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)


6.6 RESERVED ATOMIC SYMBOLS

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 LIST) and remember not to use those.

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

ADD1ALISTAMBANDAPPENDASSOCATOM
ATSYMBATTEMPTBACKSPBACKTRBREAKCARCDR
CADRCADDRCDDRCLEARBUFFCOMPRESSCONDCONS
CSETQCSETCURRCOLDATEDEFINEDEFMACDEFSPEC
DELIMDIFFERENCEDODTIMEDUMPENTIEREQ
EQUALERASEERROREVALEXPLODEEXPLODE2F
FIXPFLAGFLOATPFUNCTIONGCTIMEGENSYMGET
GOGREATERPGROWIFFLAGIFTYPEINDEXINTO
LAMDALAMBDALEFTSHIFTLENGTHLESSPLISTLISP
LOADLOGANDLOGXORLOGORMANIFESTMAPMAPCAR
MAPLISTMAPCMEMBERMEMORYMINUSMINUSPNCONC
NILNOTNTHNULLNUMBERPOBLISTONDEX
ONTOORPLENGTH2PLENGTHPLIMITPLUSPRIN2
PRIN1PRINTPROPPROGPUTQUOTIENTQUOTE
READMACREADCHREADREMPROPREMAINDERREQUESTRETURN
REVERSERPLACDRPLACASETSETCOLSETQSPACE
STACKSTRINGSUB1SUBSTTTERPRITIME
TIMESTOKENUNBREAKUNFLAGZEROP*BEGIN*CAR
*CDR*CHAIN*DEF*DEPOSIT*EMIT*EPT*EXAM
*MACRO*ORG*PACKIT*SPEC


6.7 PRACTICE

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.

(ABS n) = the absolute value of the number n.

(COUNT m) = the number of atoms in the list m. E.g, (COUNT `(A B1 (C) DEF)) = 4.

(SUM m) = the sum of the elements of the list m. E.g, (SUM `(1 2 3 4)) = 10.

(ALTSUM m) = the sum of the elements of the list m written with alternating signs. E.g. (ALTSUM `(1 -2 3 4 5) = 7. (Hint, if you find yourself multiplying by -1 or any similar contortion, then you`re doing it the hard way!)

(SIGMA lo hi fn) = fn(lo) + fn(lo+1) +... + fn(hi-1) + fn(hi).

(FACT n) = the factorial of n.

(POWER x n) = x ** n. (n is an integer).

(LAST m) = the last element of the list m. (LAST `(A B C)) = C. (LAST NIL) can be NIL or an error, your choice.

(TAKEOUT x m) = the list m with the first occurence of x, if any,eq removed. (TAKEOUT `A `(A B C A D)) = (B C A D).

(TAKEAWAY x m) = the list m with all occurences of x removed.

(GCD m n) = the greatest common denominator of m and n. (GCD 12 15) = 3. (GCD 12 17) = 1. (Hint, use the Euclidian Algorithm. Never heard of the Euclidian Algorithm, you say? Then forget this exercise.

(MAX m) = the largest number in the list m. (Hint, will require an auxiliary function.)

(SORT m) = the list m with its elements in ascending numerical order. (SORT `(1 3 5 2 7 0)) = (0 1 2 3 5 7).

(SUBST x y z) as described above in 6.4, but write it yourself in LISP.

(SUBSET s1 s2) = true if s1 is a subset of s2. This continues from the set-theoretic definitions above. After this, define any other useful functions for set theory that you might think of. For example, find out if two sets are the same (EQUAL won`t work).

(PERMUTE m) = a list containing all the permutations of the list m. (Hint, this isn`t so easy, but I wanted to end with a challenge; Good Luck!)