>>37<<5552 >>37<>16<< >>37<<5552 44444 s>>37<<0 >>16<>12<< >>16<>16<< >>37<<242>>37<< >>37<<5552 >>17<<000>>17<< 11>>37<<11 >>37<>37<<55>>15<>60<< LISP is a source language for writing algorithms. Unlike most other languages, in which a source program consists of a sequence of instructions to be executed in a certain order, a LISP program usually (but not always) consists of a collection of function definitions. The basic object in LISP is a branching-tree type of structure called an S-expression. All function definitions, function arguments, function values, programs, instructions, variables, constants, and data are S-expressions. At each node of an S-expression there are two branches. The branches eventually terminate in atoms. An S-expression is thus defined recursively - it is either an atom or the concatena- tion of two S-expressions. o lambda o o o x nil nil o times o 2 o x o x nil fig. 1 - an S-expression In the S-expression of figure 1, lambda, x, nil, times, and 2 are atoms. The S-expression is the concatenation of the S-expression lambda, which is an atom, with another concatenation. There is a notation for transmission of S-expressions between LISP and the outside world. An atom is simply spelled out. A concatenation is written as a left parenthe- sis, the S-expression on the left side, a period, the S- expression on the right side, and a right parenthesis. The S-expression of figure 1 could be written (lambda.((x.nil).((times.(2.(x.(x.nil)))).nil))) j Almost all S-expressions that are commonly used have a chain of branches going off to the right, with the atom nil at the end. From each node an S-expression hangs on the left. Such an S-expression is called a list. o a o b o x o y o z nil fig. 2 - a list There is a special notation for lists, consisting of a left parenthesis, the items of the list with spaces separat- ing them, and a right parenthesis. Using list notation, the S-expression of figure 2 is written (a b x y z) and that of figure 1 is written (lambda (x) (times 2 x x)) Either format is permissible for input. In typing out S- expressions, LISP uses list notation wherever possible. There are two types of atoms. Numbers consist of one or more digits, with or without a minus sign. Atomic symbols contain at least one non-numeric character. f The three most basic functions in LISP are car, cdr, and cons. These three, along with over 60 others, exist as subroutines in the LISP program. Given a nonatomic S-expression as an argument car finds the left half. Cdr finds the right half. car of (a.b) = a cdr of (a.b) = b Cons takes two arguments and concatenates them. cons of a and b = (a.b) Note that the car of a list is its first element, and the cdr is the list of the remaining elements. The list of no elements is the atomic symbol nil. car of (a b c) = a cdr of (a b c) = (b c) cdr of (a) = nil The cons of an S-expression and a list is the list with the S-expression tacked onto the front. cons of a and (b c) = (a b c) 9 LISP does arithmetic with the following functions. All arguments must be numbers. Plus takes any number of arguments and calculates their sum. Minus takes any number of arguments and calculates their alternating sum, with the sign of the last argument negative. Hence minus of one argument is its negation, and minus of two arguments is their difference. Times takes any number of arguments and calculates their product. Logand returns the bitwise and of its arguments. Logor returns the bitwise inclusive or of its arguments. Logxor returns the bitwise exclusive or of its arguments. Add1 takes one argument and adds one to it. Sub1 takes one argument and subtracts one from it. Quotient takes two arguments and returns the quotient of the integer division of the first by the second. Remainder takes two arguments and calculates the remain- der of the integer division of the first by the second. >>17<< LISP uses the atomic symbols t and nil to represent truth and falsehood, respectively. Decisions are made by functions called predicates. A predicate applies a test to its argument and returns t or nil depending on the result. Atom returns t if its argument is an atom (number or atomic symbol) and nil if it a concatenation. Numberp returns t only if its argument is a number. It returns nil if it is an atomic symbol or a concatena- tion. Null returns t if its argument is nil, and returns nil otherwise. Equal takes two arguments and returns t if they have the same structure, i.e. if they would look alike if printed out. Eq takes two arguments and returns t if they are exactly the same. The difference between equal and eq is explained later. The argument of zerop must be a number. It returns t if that number is plus zero. The argument of minusp must be a number. It returns t if that number is negative. Minus zero is negative. Greaterp takes two numeric arguments and returns t if the first is algebraically strictly greater than the second. 4 Predicates are usually used with cond, the decision making function. Cond takes an indefinite number of argu- ments, called clauses, each of which is a list of one or more (typically two) items. The first item of each clause is the antecedent. The remaining items (if any) are conse- quents. The clauses are examined one at a time until an antecedent is found to be true (typically t, anything different from nil will suffice). The corresponding conse- quents are evaluated, and cond returns the value of the last one (or, if there are no consequents, cond returns the value of the antecedent). If the value of an antecedent is nil, cond goes on to the next clause. If it runs out of arguments, an error message is printed. In the examples which follow, conditionals will be written in the "pure" form with one consequent per clause. Programs may frequently be shortened by using a less rigid format. Logical quantities are manipulated with the functions and and or. Each takes an indefinite number of logical arguments and returns t if all of them or one of them, respectively, is true. There is no function named not, but null may be used to negate logical quantities. Remember that logand and logor are used with numerical quantities, and and or with logical ones. Atomic symbols have the property that they may "stand for" things. The thing for which an atomic symbol stands is called its value. It may be any S-expression, atomic or otherwise. The value of an atom may be the atom itself, as is the case with t and nil. When an atom has a value, it is said to be bound to that value. Not all atoms are bound. The predicate valp may be used to determine whether an atomic symbol has a value. The function setq is used to bind atomic symbols. The first argument is the symbol, the second is the value. Any previous value of the symbol is lost. Setq is an example of a pseudo-function. It is used for its effect rather than its value. Pseudo-functions, like all other functions, must return values, but the value is usually ignored. Setq returns its second argument. >>53<< In LISP function calls are written as S-expressions, using a variation of Polish notation. The S-expression used is a list containing the function as the first item and the arguments as the remaining items. Every function must therefore be able to be written as an S-expression. For this purpose, associated with each internal function in LISP is an atomic symbol with the same name. The value of the symbol is a number with an invisible flag giving the LISP program the information it needs to call the subroutine. Suppose, for example, that x stands for a and y stands for (b c), and one wishes to take the cons of x and y, obtaining (a b c). The atomic symbol cons is used, and the call is the S-expression (cons x y). Note that the car of a function call is the function, and the cdr is the argument list. The procedure by which the S-expression (cons x y) is transformed into (a b c) is called evaluation, and is the most important procedure in LISP. Evaluation of a number gets the number itself. Evaluation of an atomic symbol gets the symbol's value. Evaluation of a nonatomic S-expression (which must be a list) causes the arguments to be evaluated (in most cases), and their values sent to the function. Whether the arguments of a function are evaluated or not is a property of the function. Except where otherwise speci- fied, all functions have their arguments evaluated. Since the arguments of functions are evaluated, they may be other function calls, enabling functions to be nested within each other. For example, to take the car of the cdr of the car of whatever x is bound to, evaluate (car (cdr (car x))) If x evaluates to (1.3), then (plus (minus (car x)) 5 (cdr x)) evaluates to 7. Evaluation may be stopped with the function quote. Quote takes one argument and returns it without evaluation. To find the cons of a and (b c), obtaining (a b c), evaluate (cons (quote a) (quote (b c))) LISP will evaluate (quote a) to a and (quote (b c)) to (b c) before sending them to cons. Evaluating (cons a (b c)) would cause the value of c to be sent to the function b, and the value of a concatenated with the result. When writing LISP programs, great care must be taken to evaluate the right things and quote the right things. Following are some of the important exceptions to the rule that all functions evaluate all arguments. The function setq evaluates its second argument but not its first. To increase the numerical value of x by one, evaluate (setq x (add1 x)) The function setqq is similar to setq but evaluates neither argument. To bind x to (a b c), evaluate (setqq x (a b c)) Setqq is usually used for defining constants at the top level. For manipulating prog variables, setq is usually required. The function cond does not evaluate its arguments direct- ly but evaluates the antecedents and consequents separately. The antecedent of each argument is evaluated until one is found to be true. The consequents are then evaluated. The functions and and or evaluate only enough arguments to determine the result. As soon as or finds a true argument, or and finds a false one, all remaining arguments are left unevaluated. This is useful in some applications. Prog (see below) also has an unusual way of evaluating its arguments. An example of a conditional (cond ((atom x) (quote a)) (y (quote (a b))) (t (quote (a b c)))) evaluates to a if the value of x is atomic, or (a b) if the value of y is not nil, or (a b c) otherwise. The third case works because t is bound to itself. o In addition to functions written as subroutines, func- tions may be written by the programmer. These functions are interpreted by LISP when they are called. A programmed function is a list of three items, the first of which is usually the atomic symbol lambda. Lambda is not a subroutine but a special symbol which LISP recognizes. It has no value. Like subroutines, programmed functions are usually given names, and an atomic symbol of the same name is given a value of the function. Functions defined with lambda are called expr's and always have their arguments evaluated. Suppose the symbol foo has a value of (lambda (x) (times 2 x x)) Lambda identifies it as an expr, (x) is the dummy symbol list, indicating that it takes one argument called x, and (times 2 x x) is the actual definition. This function takes one argument, squares it, multiplies by 2, and returns the result. (foo (plus 1 2)) evaluates to 18 (foo (foo (foo 1))) evaluates to 128 A predicate symbp to detect whether an S-expression is an atomic symbol could be written as (lambda (x) (and (atom x) (null (numberp x)))), or as (lambda (y) (cond ((numberp y) nil) ((atom y) t) (t nil) )) This predicate, if defined, could be used exactly as one would use atom or numberp. Programmed functions may call any functions, including themselves. A function fact to find the factorial of a number could be written as (lambda (x) (cond ((zerop x) 1) (t (times x (fact (sub1 x)))))) (fact 4) evaluates to 24 (fact (fact 3)) evaluates to 720 y When LISP attempts to evaluate a function call, that is, a nonatomic S-expression, it evaluates the function as many times as necessary (usually once) until a subroutine or a list beginning with lambda, nlamda, or label is found. If lambda is found, the arguments are evaluated and paired with the symbols on the dummy symbol list. Any old values of these symbols are saved, and the symbols are bound to the evaluated arguments. The definition is then evaluated and, after restoring the previous bindings of the dummy symbols, the value of the definition is returned as the value of the call. Example - suppose that the second definition of symbp is used. Find out whether a is a symbol. symbp evaluates to (lambda (y) (cond ((numberp y) nil) ((atom y) t) (t nil))) y evaluates to (1 2 3). This is its previous value from some unrelated calculation. Evaluate (symbp (quote a)). The function symbp is evaluated to (lambda (y) (cond ((numberp y) nil) ((atom y) t) (t nil))) LISP recognizes this as an expr, so it evaluates each argument (quote a) is evaluated - its value is a The dummy symbol list is (y). The old value of y, (1 2 3), is saved. y is bound to the evaluated argument. y now evaluates to a. (cond ((numberp y) nil) ((atom y) t) (t nil)), the definition of the function, is evaluated. Cond, unlike most functions, does not evaluate its arguments immediately, so the arguments sent to cond are ((numberp y) nil), ((atom y) t), and (t nil). (numberp y), the first antecedent, is evaluated. Numberp evaluates its argument. y is evaluated, obtaining a, which is sent to numberp. a is not a number, so numberp returns nil. cond goes to the next antecedent. (atom y) is evaluated. y evaluates to a, which is an atom, so atom returns t. The second clause is true, so its consequent, t, is evaluated. t is bound to itself, so the value of the call to cond is t. y is restored to (1 2 3), its old value, and t is returned as the value of (symbp (quote a)). Hence a is a symbol. d Functions like symbp and fact, being values of atomic symbols, are relatively permanent and may be used repeat- edly. When one wishes to use a function only once, it is not necessary to give it a name and bind the atomic symbol of the same name to it. The function itself may be used. Hence ((lambda (y) (cond ((numberp y) nil) ((atom y) t) (t nil))) (quote a)) may be used to determine that a is a symbol. If a function is recursive, however, it must be given a name so that it may use that name in calling itself. An attempt to calculate 4 factorial by evaluating ((lambda (x) (cond ((zerop x) 1) (t (times x (fact (sub1 x)))))) 4) would not work because fact has no value. ((label fact (lambda (x) (cond ((zerop x) 1) (t (times x (fact (sub1 x))))))) 4) will work. Label is used to temporarily bind the atomic symbol fact to the definition of the factorial function. A list consisting of label, a symbol, and a function is equivalent to the function alone, except that the symbol is temporarily bound to the function. The function can there- fore call itself by referring to the symbol with which it is labelled. The previous value of the symbol is restored when the function is finished. Label should be used only with expr's. To write a function which does not have its arguments evaluated, use nlamda instead of lambda. Functions defined in this way are called fexpr's. In addition to not evaluat- ing their arguments, they also have a different way of binding arguments to the dummy symbol list. A fexpr may take any number of arguments. There must be exactly one symbol on the dummy symbol list. It will be bound to the list of all of the arguments. Functions which do not evaluate their arguments are usually used only on the top level for "utility" purposes. Other functions do not, as a rule, call them, and they are not usually recursive. Prindef, dex, fix, trace, and untrace are examples of built-in functions which do not evaluate their arguments. h Expr's may be conveniently defined by means of the function dex. Dex takes three arguments and does not evaluate them. The first is the name of the function to be defined, the second is the dummy symbol list, and the third is the definition. (dex symbp (y) (cond ((numberp y) nil) ((atom y) t) (t nil))) evaluates to symbp and defines symbp to be the expr described above. Programs in the usual sense may be written with the functions prog, return, and go. Prog takes an indefinite number of arguments and does not immediately evaluate them. The first argument is the temporary variables list. The value of each symbol on this list is saved, and each symbol is bound to nil. These symbols may be used for temporary storage by the program, and will have their original values restored upon exit. Of the remaining arguments, atomic symbols are interpreted as address tags and nonatomic expressions as instructions. The previous values of the tags are saved, and the tags are bound to pointers to the appropriate locations in the program. The instructions are then evaluated in sequence, and the values ignored. If the program runs out of instructions, nil is returned. If the function return is called, its evaluated argument is returned as the value of the program. In either case the temporary variables and address tags are restored. The function go, with an address tag as an argument, causes a transfer of control to the indicated address. Prog, like other functions, may be nested. Return and go always refer to the most recently entered prog. Program variables of nested progs are saved independently at each level. On the top level of a prog the rules for use of cond are relaxed. If cond runs out of clauses, rather than giving an error message it simply goes to the next statement of the program. A typical use of prog is in the function reverse, which reverses a list. Reverse could be defined by (dex reverse (x) (prog (y) z (cond ((null x) (return y))) (setq y (cons (car x) y)) (setq x (cdr x)) (go z) )) This takes advantage of the facts that the program variable is initially bound to nil and that a cond may run out of clauses in a prog. , LISP keeps a symbol table similar to those used by debuggers and assemblers, containing an entry for each symbol, whether it has a value or not. This table initially contains one entry for each subroutine, with a name the same as that of the subroutine and a value of a number with an invisible flag. t and nil, with values of themselves space, lpar, rpar, etc., with values of atomic symbols whose names are the indicated characters. lambda, nlamda, and label, with no values. These are flags used internally by the LISP program. Whenever an atomic symbol not appearing in the table is read in, it is placed in the table with no value. It may later be given a value. The value of an atomic symbol is stored on the car of that symbol. Taking the car of an atomic symbol gets its value. It is illegal to take the car of a symbol with no value, and it is very dangerous to take the car or cdr of a number. The cdr of a symbol is normally nil, but any S- expression may be stored there by the programmer. f S-expressions which look alike may occupy different locations of memory. Expressions may also be different but share common sub-expressions. Whenever an S-expression is read in, a fresh copy of it is created in memory, even if another copy already exists. Only atomic symbols are in unique locations. For example, reading and evaluating (setq x (quote ((a.b) (c.d)))) and (setq y (quote ((a.b) (c.d)))) leaves memory looking like this - x y o o o o o o a b o o nil c d fig. 3 - non-identical S-expressions x and y will both print out as ((a.b) (c.d)), and will satisfy the predicate equal, but they will not be identical. The predicate eq may be used to test for exact identity between two S-expressions. In the example above, (eq x y) would evaluate to nil. If x and y had been bound by (setq x (quote ((a.b) (c.d)))) and (setq y x) they would be identical and would satisfy eq. Equal could have been written in terms of eq as (dex equal (x y) (cond ((and (numberp x) (numberp y)) (zerop (logxor x y))) ((or (numberp x) (numberp y)) nil) ((and (atom x) (atom y)) (eq x y)) ((or (atom x) (atom y)) nil) (t (and (equal (car x) (car y)) (equal (cdr x) (cdr y)))) )) >>17<< There are two S-expression modifying functions, rplaca and rplacd, each taking two arguments and evaluating both. They replace the car and cdr, respectively, of the first argument with the second argument, and return the modified first argument. If x and y are bound as in figure 3, (rplacd (car x) (quote q)) removes the dotted line in the figure and replaces it with a pointer to the atomic symbol q. It returns (a.q), its modified first argument. The value of x is now ((a.q) (c.d)). The value of y is not changed. If y had been bound by (setq y x), so that its value was identical with that of x, it too would have been changed. Since the car of an atomic symbol is its value, rplaca may be used to bind symbols, and rplacd may be used to store S- expressions on the cdr of a symbol. h Other S-expression manipulating functions Caar, cadr, cdar, cddr, and caddr are compositions of car and cdr. They could have been defined by (dex caar (x) (car (car x))) (dex cadr (x) (car (cdr x))) (dex cdar (x) (cdr (car x))) (dex cddr (x) (cdr (cdr x))) (dex caddr (x) (car (cdr (cdr x)))) For example, the cadr of (a b c) is the car of the cdr of (a b c), or b. Caddr gets the third item from a list. List takes (and evaluates) an indefinite number of arguments and returns the list of them. List and cons are the two functions that are used to create complex S- expressions out of small ones. (list 1 (cons (quote a) (quote b)) (plus 1 2 3)) evaluates to (1 (a.b) 6) (list (quote (a b c)) (quote (d e f))) evaluates to ((a b c) (d e f)) Append takes two arguments, which must be lists, and appends them. (append (quote (a b c)) (quote (d e f))) evaluates to (a b c d e f) Append makes a copy of the first list in order to avoid modifying it. Append could have been defined by (dex append (x y) (cond ((null x) y) (t (cons (car x) (append (cdr x) y))) )) Note that append and list are very different. Nconc is the same as append except that it does not copy its first argument but merely changes the nil at the end of the first list to the second list. In doing so the first list is permanently modified. Nconc could have been defined by (dex nconc (x y) (cond ((null x) y) 4 (t (prog (z) (setq z x) a (cond ((null (null (cdr z))) (go b)) (rplacd z y) (return x) b (setq z (cdr z)) (go a) )))) Reverse takes one argument, which is a list, and reverses it. It could have been defined by (dex reverse (x) (prog (y) a (cond ((null x) (return y))) (setq y (cons (car x) y)) (setq x (cdr x)) (go a) )) Subst takes three arguments and substitutes the first for all appearances, on all levels, of the second in the third. The third argument is not actually modified. Subst could have been defined by (dex subst (x y z) (cond ((equal y z) x) ((atom z) z) (t (cons (subst x y (car z)) (subst x y (cdr z)))) )) Sassoc takes three arguments and looks up the first in the second, which is a special type of table called an association list. An association list is a list of dotted pairs of atomic symbols with the S-expressions associated with them. For example, to keep a table with the information x=1 y=2 z=3 and not bind x, y, and z to these values, one could bind tab to ((x.1) (y.2) (z.3)) Sassoc can look through a table in this format. It returns the first pair which has a car identically equal to the first argument. (sassoc (quote y) tab no) evaluates to (y.2) w The third argument is a function of no variables which is called if the item is not found. (sassoc (quote z) tab (quote (lambda nil (quote (not found))))) evaluates to (z.3). If z had not been found, (not found) would have been returned as the value of the call to sassoc. In order to save space in memory, a number may be used as the third argument. If the search fails the uaf error message will be printed along with the number. Sassoc could have been written as (dex sassoc (x y z) (cond ((null y) (z)) ((eq x (caar y)) (car y)) (t (sassoc x (cdr y) z)) )) Length takes one argument, which is a list, and returns its length, a number. It could have been defined by (dex length (x) (cond ((null x) 0) (t (add1 (length (cdr x)))) )) Nth takes two arguments, the first a number and the second a list. It returns the list with the first n items removed. Nth could have been defined by (dex nth (n x) (cond ((greaterp 1 n) x) (t (nth (sub1 n) (cdr x))) )) Other predicates Member takes two arguments, the second of which is a list, and returns t if the first argument is a member of that list. Equal is used for the comparison, so any S- expression may be tested. The second argument is searched on the top level only. Member could have been defined by (dex member (x y) (cond ((null y) nil) ((equal x (car y)) t) >>35<< (t (member x (cdr y))) )) I/O operations Read takes no arguments. It reads one S-expression from the typewriter or a text file and returns that S-expression. (read) evaluates to (a b c d) if the latter is typed in. Prin1 takes one argument, and prints it or writes it on a file with no extra punctuation. The value returned is the original argument. Print prints or writes its argument preceded by a carriage return and followed by a space. The argument is returned. (print (quote (a b c))) prints out " (a b c) " and returns (a b c) Terpri prints or writes a carriage return. It takes no arguments and returns nil. Miscellaneous functions Stop takes no arguments. It returns to the control program (see below) for a change of input source, output destination, etc. Gensym takes no arguments. Each call to gensym creates a new atomic symbol as if it had been read in and returns that symbol. The names of the symbols are g001, g002, etc. Eval takes one argument and returns its value. This means that the argument is actually evaluated twice. If x is bound to (cons 1 3), the value of (eval x) is (1.3), whereas the value of x alone is (cons 1 3). Apply takes two arguments, a function and an argument list for the function. The function is called with the given arguments. If the function is one which normally evaluates all its arguments, they will not be evaluated again, but simply taken from the second argument to apply, which was, of course, evaluated already. (apply (quote cons) (quote (a b))) sends a and b, without further evaluation, to cons, thereby returning (a.b). >>16<< Trace takes any number of arguments and does not evaluate them. Each argument should be the name of an expr or fexpr. Each function is traced, or modified so that it prints out its name and evaluated arguments on entry, and its name and returned value on exit. Nested or recursive functions cause the printouts to occur in proper order at each entry and exit. If fact initially had a value of (lambda (x) (cond ((zerop x) 1) (t (times x (fact (sub1 x)))))) (trace fact) would evaluate to nil and redefine fact as (lambda (x) (prog (99g) (print (quote (enter fact))) (print (list x)) (setq 99g (cond ((zerop x) 1) (t (times x (fact (sub1 x)))))) (print (quote (value fact))) (return (print 99g)) )) Evaluation of (fact 3) would return 6 after printing (enter fact) (3) (enter fact) (2) (enter fact) (1) (enter fact) (0) (value fact) 1 (value fact) 1 (value fact) 2 (value fact) 6 Untrace takes any number of arguments and does not evaluate them. Each argument should be the name of a traced function. Untrace restores each function to its original definition. Prindef is used to write the definitions of functions and constants. It takes any number of arguments and does not evaluate them. Each argument should be an atomic symbol with a value. Prindef prints the definition of each symbol as a ) call to rplaca, and then returns a call to stop, which is normally printed also. The resultant text, when read at a later time, defines the atoms and then returns to the control program. (prindef fact) prints (rplaca (quote fact) (quote (lambda (x) (cond ((zerop x) 1) (t (times x (fact (sub1 x)))))))) (stop) Prindef could have been defined by (setqq prindef (nlamda (x) (prog nil a (cond ((null x) (return (quote (stop))))) (print (list (quote rplaca) (list (quote quote) (car x)) (list (quote quote) (eval (car x))) )) (terpri) (setq x (cdr x)) (go a) ))) Fix is used to edit or modify functions. It takes three arguments and does not evaluate them. The third is the name of the function to be fixed. The first argument is substituted for the second in each appearance in the function, and the function is redefined to be the result. Fix could have been defined by (setqq fix (nlamda (x) (rplaca (caddr x) (subst (car x) (cadr x) (eval (caddr x)))) )) Prog2 is used to cause the evaluation of several func- tions with a single call to eval. It takes one or more arguments, evaluates all, and returns the last. Mapcar is used to send each item of a list to a function as the single argument of that function, and return the list of the values returned. Mapcar takes two arguments and evaluates both. The first is the list of arguments, the second is the function. To cons each item of the list (a b c d) with x, for example, evaluate (mapcar (quote (a b c d)) (quote (lambda (y) (cons y (quote x))))) m obtaining ((a.x) (b.x) (c.x) (d.x)) Mapcar could have been defined by (dex mapcar (x y) (cond ((null x) nil) (t (cons (apply y (list (car x))) (mapcar (cdr x) y))) )) p Output Output normally goes to the typewriter or a text file, depending on destination specified to the control program. Error messages are always printed on the typewriter. S-expressions which are nearly lists, such as (a.(b.(c.d))) are printed as (a b c.d) This format is also acceptable for input. Negative numbers are printed with a minus sign. The radix (octal or decimal) is determined by the control program. It is normally decimal. A carriage return is inserted after approximately every 65 characters of output not containing a carriage return. It is never inserted in the middle of an atom. To facilitate printing of characters that are not normal- ly permitted in atomic symbol names, the atoms space, lpar, rpar, red, black, period, tabul, backspace, and carret are provided. Each of these is bound to a symbol whose name is the indicated character. Hence, to type a left parenthesis, evaluate (prin1 lpar) >>37<< Input Input comes from the typewriter or text file, depending on the source specified to the control program. Parentheses, period, and space separate atoms. Extra spaces may be used anywhere except inside an atom. Spaces may be omitted except where needed to separate atoms. Tab is equivalent to space. () is equivalent to nil. When an S- expression consists of an atom only it must be followed by a separation character, usually space. This separator is saved and used on the next call to read. Carriage return and stop code are ignored. 0 to 7 in octal radix and 0 to 9 in decimal radix are digits. An atom containing only digits, with an optional minus sign, is a number. Plus signs are not permitted in numbers. The absolute value of a number must not exceed 131071 decimal or 377777 octal. Overbar causes the character immediately following to be considered a letter regardless of what it actually is. The overbar itself does not appear in the atom, and will not be printed out when the atom is printed. Other characters, including case shifts and all upper- case characters, are letters, and atoms containing one or more letters are atomic symbols. All atoms must begin and end in lower case. Atomic symbols may be of any reasonable length. Backspace may be used to correct errors in typing. After one or more characters of an atom have been typed, backspace deletes those characters and starts the atom over. The remainder of the S-expression is not affected. A backspace immediately after a separation character starts the entire S-expression over and prints out a carriage return. 1 Operation Load the program, start at zero, and type the number of core modules to be used. LISP stores itself on drum field 15, part of which it uses for pushdown stack and atom name storage. Free storage remains in core at all times. LISP sets an illegal memory reference return, which is removed when it dismisses to ID with "b". The control program The control program is entered when LISP is first started and whenever the function stop is called. When entered it types a red shift and minus sign, and waits for control characters to be typed. The first character specifies input source. t - from the typewriter s - from Expensive Typewriter's text buffer, starting on page 1 e - from Expensive Typewriter's text buffer, starting from where it last read. When LISP is first started, this is the same as "s". The next character specifies output destination. t - to the typewriter. s - to a text buffer on drum field 7, starting on page 1. e - to a text buffer on drum field 7, appending a new page. n - nowhere. After "s" and "e", stop must be called to finish output. If "o" is typed before the input source specification, numbers will be read and printed in octal radix. Numbers are decimal otherwise. If "b" is typed, LISP will dismiss to ID. e After leaving the control program, LISP reads S-expres- sions and prints out their values. The LISP program could be simulated by (prog nil a (print (eval (read))) (go a)) Some other LISP programs, notably the version used on the 7094, use a different algorithm, in which a function and its argument list are typed in as two separate S-expressions, and the arguments are not evaluated on the top level. This algorithm may be approximately simulated by (prog nil a (print (apply (read) (read))) (go a)) Turning on sense switch 1 when LISP is running or printing out will cause it to return to the top level read- eval-print loop immediately. Temporarily bound symbols will be restored to their original values. In very severe cases, it may be necessary to hit call and restart at location zero. In this case, temporary bindings will remain, and, if a garbage collection was in progress, free storage will be seriously damaged. Upon detection of an error, LISP prints a 3-letter error code on the typewriter, sometimes followed by the S- expression in error. Most of these errors return to the read-eval-print cycle as if sense switch one had been raised. The more serious ones return to the control program. When the latter happens, temporary bindings are not restored. uas (unbound atomic symbol) - The argument of a call to eval is an atomic symbol with no value. The symbol in error is printed. LISP restores old symbol bindings and returns to the read-eval-print cycle. uaf (unbound atomic function) - A symbol which is not bound or is bound to itself, or a number without the internal function flag, has been used as a function. The symbol or number is printed. Same recovery as uas. tfa (too few arguments) - A subr or expr has not been given enough arguments, or the symbol list after nlamda contains more than one symbol. The recovery is the same as that for uas. tma (too many arguments) - A subr or expr has been given too many arguments, or the symbol list after nlamda is empty. Same recovery as uas. cva (car of valueless atom) - an attempt has been made to calculate the car of an atomic symbol which has no value. The symbol in error is printed. Same recovery as uas. t icd (illegal conditional) - A call to cond has run out of clauses. Same recovery as uas. nna (non-numeric argument) - An argument to an arithmetic function is not a number. Same recovery as uas. dze (divide by zero) - The divisor for quotient or remainder is zero. Same recovery as uas. pce (pushdown capacity exceeded) - The length of the pushdown list is too great. LISP returns to the control program. Temporary bindings are not removed. sce (storage capacity exceeded) - The free storage list has been exhausted, and no space could be reclaimed by the garbage collector. Same recovery as pce. ace (atom capacity exceeded) - The atomic symbol object table is full. Same recovery as pce. nce (name capacity exceeded) - The atomic symbol name table is full. Same recovery as pce. imr (illegal memory reference) - An illegal memory reference trap has occured, usually because of taking the car or cdr of a number. Same recovery as pce. iif (illegal input format) - An object which is not an S- expression has been read. Same recovery as pce. b Appendix - built-in LISP functions name number of args description | evaluate or quote | | PF if pseudo-function | | | class car 1 e general cdr 1 e general caar 1 e general car_ car cadr 1 e general car_ cdr cdar 1 e general cdr_ car cddr 1 e general cdr_ cdr caddr 1 e general car_ cdr_ cdr cons 2 e general (x.y) list n e general (x y z ...) rplaca 2 e PF general y . (car x) rplacd 2 e PF general y . (cdr x) append 2 e general nconc 2 e PF general (append x y) . x reverse 1 e general subst 3 e general subst x for y in z sassoc 3 e general look up x in y, or call z length 1 e general length of a list nth 2 e general cdr of y x times and n e logical x and y and z ... or n e logical x or y or z ... null 1 e predicate x = nil atom 1 e predicate x is atom numberp 1 e predicate x is number valp 1 e predicate x is bound >>35<< zerop 1 e predicate x = 0 minusp 1 e predicate x < 0 greaterp 2 e predicate x > y eq 2 e predicate x is y exactly equal 2 e predicate x looks like y member 2 e predicate x is a member of y plus n e arith x + y + z ... minus n e arith ... - x + y - z times n e arith x x y x z ... logor n e arith x >>05<< y >>05<< z ... logand n e arith x ^ y ^ z ... logxor n e arith x ~ y ~ z ... quotient 2 e arith [x/y] remainder 2 e arith x - y x [x/y] add1 1 e arith x + 1 sub1 1 e arith x - 1 read 0 PF I/O prin1 1 e PF I/O print without punctuation print 1 e PF I/O print with punctuation terpri 0 PF I/O print carriage return stop 0 PF misc. return to control program gensym 0 PF misc. create symbol quote 1 q misc. setq 2 q,e PF misc. bind x to y setqq 2 q PF misc. bind x to y, y not evaluated cond n misc. eval 1 e misc. value of x apply 2 e misc. call x with y >>52<< trace n q PF misc. untrace n q PF misc. prindef n q PF misc. print definitions dex 3 q PF misc. define expr fix 3 q PF misc. fix x for y in z prog n misc. go 1 e PF misc. go to x return 1 e PF misc. return from program mapcar 2 e misc. send each element of x to y prog2 n e misc. last arg built-in constants name value t t nil nil space lpar ( rpar ) red black period . tabul backspace carret c 7