# Full text of "LISP 1.5"

## See other formats

ji i i LISP 1.5 GEORGE G. ROBERTSON VANDERBILT UNIVERSITY COMPUTER CENTER AUGUST, 1969 VANDERBILT UNIVERSITY NASHVILLE, TENNESSEE Report No. 1004 George G. Robertson Vanderbilt University- Computer Center Nashville, Tennessee TABLE OF CONTENTS Page TABLE OF CONTENTS. i I. INTRODUCTION. I - 1 II. THE LISP LANGUAGE. II - 1 2.1 Symbolic Expressions. II - 2 2.2 Elementary Functions. II - 2 2.3 List Notation. II - 4 2.4 Meta-Language Expressions. II - 4 2.5 Syntax. II - 7 III. ADAPTING LISP AS A PROGRAMMING SYSTEM.1.. Ill - 1 3.1 The Universal Function. Ill - 1 3.2 Variables, Constants, Functions, and Special Forms. Ill - 2 3.3 Extentions. Ill - 4 3.4 Arithmetic. HI - 5 3.5 Program Feature. IU - 6 IV. IMPLEMENTATION OF LISP ON THE SDS SIGMA 7. IV - 1 4.1 Internal Structures. IV - 2 4.2 Functions. IV - 8 V. USER OPERATING PROCEDURES. V- 1 5.1 The LISP Program. V - 1 5.2 Tape Operations... V - 1 5.3 System Messages. V - 1 5.4 Control Card Options. V - 6 VI. CONCLUSIONS AND FUTURE CONSIDERATION. VI - 1 APPENDIX I: LISP 1.5 FUNCTIONS 1. INTRODUCTION This publication is intended as a reference manual in the use of Vanderbilt SDS SIGMA 7 LISP 1.5, based on MIT 7090 LISP 1.5 (see LISP 1.5 Programmer's Manual , MIT Press, January 1966). The manual is divided into five sections. The first three sections offer an introduction to the LISP language. The final two offer a description of the SIGMA 7 implementation and user operating procedures. LISP is a mathematical language designed primarily for meaningful manipulation of list structures. When certain important features are added to the mathematical language, it can be extended to a programming language suitable for list processing. The mathematical language is complete without these extensions, but without them, it is not very useful as a programming language. With the extensions added, the language is referred to as the programming language LISP 1.5. Once the mathematical language has been extended to a programming language, the task becomes one of developing a programming system capable of translating the programming language into meaningful computer operations. With some languages, this task is best accomplished with a compiler. A compiler is a program which translates the source language into machine language. With LISP 1.5, however, this task is best accomplished with an interpretive system. An interpretive system is a programming system which executes a source language program by examining the source language and performing specified algorithms. These algorithms may be specified by the user in the LISP language, or they may be one of many primitive routines included in the system. A primitive is a machine language routine designed to perform one specific algorithm. These primitives along with the inter¬ preter make up the interpretive system. The task of translating the programming language LISP 1.5 is accomplished with such an interpretive system. Thus, the problem of implementing the mathematical language LISP on the SDS SIGMA 7 is reduced to a two step process. First, extend the mathematical language to a programming language. Second, develop an interpretive system capable of translating the programming language. These processes, as well as a mathematical description of the language, are discussed in this manual. II. THE LISP LANGUAGE LISP is a formal system and, as such, has the elements of any formal system. The elements of LISP include a set of symbols which are called symbolic expressions, abbreviated S-expressions. Also included is a functional notation over the set of symbols. These functions are referred to as Meta-language expressions, abbreviated M-expressions. A formal mapping of M-expressions into S-expressions is developed as a part of the system. Finally, a universal function, written as an M-exprossion, is defined. This function is used for interpreting the S-expression images of the M-expressions. This interpretation is actually the application of any function to its arguments. These elements form a complete mathematical system. As a mathematical system, LISP can be thought of as a mathematical language. A language is a set of sentences over an alphabet. The alphabet, which is a finite set of symbols, is the set of upper and lower case Latin letters, the arabic numerals, and a few special characters such as left and right parentheses, the comma, the blank, and the period. A sentence over an alphabet is any string of finite length composed of symbols from the alphabet which satisfies the rules of some grammar. The sentences in LISP are the atomic symbols which make up S-expressions. The mathematical system gives the language its meaning. Given the elements of the mathematical system, the mathematical language can be recognized and translated. 2.1 Symbolic Expressions The smallest whole element of the LISP language is the atomic symbol. An atomic symbol is a string of numerals and capital letters with the first character of the string being a letter. Examples : ATOM A BL1234567890 ALONGSTRINGOFLETTERS All S-expressions are composed of atomic symbols plus appropriate delimiters. An S-expression is either an atomic symbol or a left parenthesis, followed by an S-expression, followed by a period, followed by an S-expression, followed by a right parenthesis. An S-expression of the second type is sometimes referred to as a dotted pair. Examples: ATOM (A1 . A2) (A . (B . C)) ((A . B) . C) ((A . B) . (C . D)) 2.2 Elementary Functions The elementary functions operate on S-expressions. To dif¬ ferentiate functions from S-expressions, the functions will be in small letters. Arguments to functions will be separated by a semi¬ colon. The five elementary functions are cons , head , tail, eq , and atom . The function cons is used to construct new S-expressions from smaller S-expressions. There are two arguments to cons and its value is an S-expression with the arguments to the function being the elements of the dotted pair. Examples : cons (A ; B) = (A . B) cons ((A . B) ; C) = ((A . B) . C) cons (A ; (B . C)) = (A . (B . C)) cons (cons (A ; B) ; C) = ((A . B) . C) The functions head and tail are selectors. The function head selects the first S-expression of the dotted pair which is the functional argument, while tail selects the second S-expres- sion of the dotted pair. Either function applied to an atomic symbol yields an undefined result. Examples: head ((A . B)) = A tail ((A . B)) = B head (((A . B) . C)) = (A . B) tail (((A . B) . C)) = C tail (head (((A . B) . C))) = B head (A) is undefined head (cons (A ; B)) = A tail (cons (A ; B)) = B cons (head ((A . B)) ; tail ((A . B))) = (A . B) The functions ec^ and atom are predicates, that is, they are functions whose value is either true or false. In LISP, the values true and false are represented by the atomic symbols T and F, respectively. The predicate ec[ tests for equality of atomic symbols. It is undefined for non-atomic arguments. The predicate atom is true if its argument is an atomic symbol and false it its argument is a dotted pair. , Examples : eq (A ; A) = T eq (A ; B) = F eq (A ; (B . C)) is undefined atom (ATOM) = T atom ((A . B)) = F atom (head ((A . B))) = T II - 4 2.3 List Notation All non-atomic S-expressions used up to this point have been written as dotted pairs. Any non-atomic S-expression may be written in this form, but, for convenience, LISP allows an alternative form for this type of S-expression. The alternative form, called list notation, consists of a left parenthesis, followed by an arbitrary number of S-expressions, each separated from the following by either a blank or a comma, followed by a right parenthesis. The list (a^ a 2 ...a^) is equivalent to the list . (a 2 . (...(a n .NIL)...))), where NIL is the atomic symbol used to terminate lists. Dotted pairs and list notation may be used in the same S-expression. Examples ; (A B C) = (A . (B . (C . NIL))) ((A B) C) = ((A . (B . NIL)) . (C . NIL)) (A) = (A . NIL) ((A)) = ((A . NIL) . NIL) (A (B . C)) = (A . ((B . C) . NIL)) 2.4 Meta-language Expressions The five elementary functions already discussed are examples of M-expressions. The M-expressions were distinguished from S-expres- sions by the use of lower case letters and the use of the semicolon as a seperator for arguments. Lower case letters are also used to represent variables in LISP. A variable is a symbol used to repre¬ sent an arbitrary S-expression. There are three other M-expressions which will be discussed before defining the mapping of M-expressions into S-expressions. These are the conditional expression, the lambda notation, and the label notation. In order to facilitate the definition of recursive functions, the conditional expression is included in the LISP language. A conditional expression is of the form (p, -* e, ; p~ e 0 ;...; p -*■ e ) s. L & £. nil where each p^ is an expression whose value is either true or false, and each e^ is any expression. The p^ are searched from left to right until the first true one is found. The value of the corre¬ sponding e^ becomes the value of the conditional expression. If none of the p^ are true, then the value of the entire expression is undefined. Each p^ or e^ can be either an S-expression, a function, a composition of functions, or another conditional function. Example : (eq (head (x) ; A) cons (B ; tail (x)) ; T ->■ x) In this example, x is a variable. If the head of x is A, then the value of the expression is the list x with A replaced by B. If the head of x is not A, then the value is x unchanged. The lambda notation is included in the language to allow the distinction between functions and forms. The lambda notation of Alonzo Church (See The Calculi of Lambda-Conversion by A. Church) is used. A form is an expression of more than one variable where the correspondence between variable and argument is not specified. If the correspondence is specified, then the expression is a function. The lambda notation allows a form to be converted to a function by specifying the correspondence. If e is a form in the variables x^^;...;x n , then the expression A((Xj;...jx^); e) represents the function of n variables obtained by substituting the n arguments in order for the variables Xjj...;x , respectively. II - 6 Examples : MO ; y) ; y 2 + x) (3;4) = 4 2 + 3 = 19 H(y X) ; y 2 + x) (3; 4) = 3 2 + 4 = 13 In order to use a function recursively, the function name must be bound. The lambda notation is not sufficient for this, so the label notation is included in the language. If e is a expres¬ sion, and a is its name, we write label (a ; e) . Example : label (ff ; A((x) ; (atom (x) ->■ x ; T -»• ff (head (x))))) In this expression, x is a bound variable, and ff is a bound function name. The mapping of M-expressions into S-expressions can now be defined. If the function is represented by its name, it is translated by changing all of the letters to upper case, making it an atomic symbol. If the function uses the lambda notation, then the expres¬ sion X((x 1 ;...;x n ); e) is translated into (LAMBDA (XI ... XN) e*), where e* is the translation of e. If the function begins with label, then the translation of label (a ; e) is (LABEL a* e*). A variable, like a function name, is translated by using upper case letters. The translation of a constant X is (QUOTE X). This avoids ambiguity from the translation of x, which is X. The form fnfargjj...;arg n ) is translated into (fn* arg^*...arg n *). Finally, the conditional expression (p^ -+• e 1 ;...;p n e R ) is translated into (COND (pj* e^*) • ••(p n * e n *». Examples : M-expressions S-expressions x X head HEAD head (x) (HEAD X) II - 7 M-expressions T ff(head(x)) (atom(x)->-x; T+ff(head(x))) label (ff; X ((x); (atom(x)-*x; T-*-f f (head (x) ) ) ) ) S-expressions (QUOTH T) (FF (HEAD X)) (COND ((ATOM X) X) ((QUOTE T) (FF (HEAD X)))) (LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (HEAD X)))))) 2.5 Syntax The discussion of the formal system is now complete with the exception of a discussion of the universal function. Discussion of that function will be deferred to the section on the extension of the mathematical language to a programming language. The purpose of the universal function is to allow interpretation of the appli¬ cation of a function to its arguments. The interpretive nature of this function makes the programming language easily translatable. It is for that reason that discussion of it is found in the next section. For completeness, the syntax of the LISP language, described in Backus notation (see J. W. Backus, The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM- Gamm Conference. ICIP Paris, June 1959), is included. The Data Language <letter>::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z <digit>::= 0|l|2|3|4|5|6|7|8|9 <atomic-symbol>::= <LETTER>|<atomic-symbol><LETTER>|<atomic-symbol><digit> <S-expression>::= <atomic-symbol>| (<S- expression>.<S-expression>)| (<S-exp part>) <S-exp part>::= <empty>|<S-expression>|<S-exp part><S-expression> The Meta-Language <l$tter>::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z <identifier>::= <letter>|<identifier><letter>|<identi£ier><digit> <form>::= <constant>| <variable>| <function>(<argument list>)| <constant>: := <S-expression <variable>::= <identifier> <argument>:: = <form> <argument list>::= <empty>|<argument>|<qrgument list>;<argument> <conditional list>::= <empty> | <form>-*<form> | <form>-*-<form>; conditional list> <function>::= <identi£ier>| A(<var list>;<£orm>)| label (<identifier>;<£unction>) <var list>::= (<variable list>) <variable list>::= <empty>|<variable>|<variable list>;<variable> III. ADAPTING LISP AS A PROGRAMMING SYSTEM To make the mathematical language LISP useful in a programming environment, it must be extended to a programming language. First, in a programming system it is difficult to differentiate a data language and a meta-language. The solution to this problem is that the LISP formal system provides a universal function which can make that distinction, and which can interpret the meta-language expressed in the data language. Next, in a programming environment, there must be means of allowing the programmer to define his own functions and initialize his own variables to constants. Also, there should be provisions for logical operations on certain types of data and arithmetic operations on other types. To make the system useful, a large number of functions should be available to the programmer to accom¬ plish these types of tasks. Finally, there should be some method of controlled looping available to the programmer. With all of these extensions, the mathematical language becomes very useful in a programming environment, and the extended language can rightfully be called a programming language. 3.1 The Universal Function An interpreter or universal function is one that can compute the value of any given function applied to its arguments when given a description of that function. The LISP universal function is evalquote (fn, args). All LISP functions have S-expressions as arguments, and therefore, the argument fn of evalquote must be an S-expression. In particular, fn is the S-expression image of some M-expression function. The universal function obeys the following identity. Let f be a function written as an M-expression, and let fn be its translation, an S-expression. Let f be a function of n arguments and let args=(argj...arg n ), a list of n S-expressions being used as arguments. Then evalquote (fn, args)=f(argp...;arg n ) if either side of the equation is defined at all. Example ; f: A((x;y) ; cons( head (x) ; y)) fn: (LAMBDA (X Y) (CONS (HEAD X) Y)) argp (A B) arg 2 : (C D) args: ((A B) (C D)) evalquote ((LAMBDA (X Y) (CONS (HEAD X) Y)j ; ((A B) (C D)))= X ((x;y) ; cons(head (x) ; y)) ((A B) ; (C D))= (A C D) During the execution of evalquote , an association list is maintained. This list has the current values of bound variables and function names. Two main functions are used by evalquote . They are eval and apply . The function apply handies a function and its arguments, while eval handles forms. Both auxiliary functions have the current association list as an argument. The maintenance of an association list in this manner allows dynamic binding of both variables and function names. 3.2 Variables, Constants, Functions, and Special Forms A variable is a symbol used to represent an argument of a function. A variable becomes bound to a value in one of two ways. It may become bound by the lambda notation. The part of the interpreter that binds variables is called apply . When apply encounters a function beginning with LAMBDA, the association list is altered by adding the paired list of variables and arguments. During evaluation of the functions, when variables are encountered, they are evaluated by looking them up on the association list. If a variable has several bindings, the most recent is used. The part of the interpreter that finds the value of a variable is called eval . A variable remains bound within the scope of the lambda that binds it. The second way a variable may become bound is for the programmer to set the variable to a constant. A constant is simply a variable bound on the highest level. In other words, a constant is a variable which has the same value regardless of the current association list. This is accomplished by means of the property list, abbreviated p-list (see section 4.1 for detailed discussion of p-lists), associated with the variable symbol. Every atomic symbol has a p-list. If the p-list contains the indicator APVAL, then the next item on the p-list is the constant value of the variable. P-lists are searched by eval before the association list is searched, thus making it possible to set variables to constant values. This task is accomplished with the cset function. cset(X ; (ABC D)) makes the variable X always stand for (A B C D). Similarly, there are two ways to bind function names. One way is to use the label notation to alter the current association list by adding the function name bound to its function definition. A more desirable method involves the changing of the p-list of the atomic symbol representing the function name. The indicator EXPR on a p-list informs apply that the function is bound on the highest level of the S-expression which follows on the p-list. The function apply searches the p-list before searching the current association list, so that this method will override the label notation. The alteration of the p-list is accomplished by the function define . There is another class of functions in the LISP system. These are bound on their respective p-lists by the indicator SUBR followed by linkage to a machine language subroutine. All of the functions which are a part of the LISP system are of this type. A special form is a type of function with an indefinite number of arguments. The arguments of a special form are not evaluated before the special form receives them, unlike all other functional arguments. Special forms have indicators on their p-lists called FEXPR and FSUBR for LISP- defined forms and machine language forms, respectively. Special forms are included in the language to give it flexibility. 3.3 Extensions There are several extensions to the language which are very useful in a programming environment. A full complement of input and output functions should be added, as well as functions which are designed for character manipulation. These functions are referred to as pseudo-functions because it is their side effects, not their values, which are important. For example, the print function has a side effect the physical printing of its S-expression argument on the line printer. The value of the print function is trivial and may be ignored. In addition to this type of pseudo-function, it would be useful to introduce functionals, that is, functions which have functions as arguments. Finally, it would be useful to include propositional connectives. These extensions extend the scope and usefulness of the language. The syntax of the meta-language does not allow functions as arguments. It expects an argument to be a form. To allow functionals, we must modify the syntatic definition of an argument to include functional arguments: <argument>::= form>|<function> Also, a rule for translating functional arguments must be set forth. If fn is a function used as an argument, then it is translated into (FUNCTION fn*). Now, functionals will be considered a part of the programming language. To allow logical connectives, three predicates are introduced. These are and , or , and not , The predicate not has only one argument, and its value is true if the argument has a value of false, false otherwise. The predicates and and or have an indefinite number of arguments, and are, therefore, special forms. If any of the arguments to and are false, then the value of and is false. Otherwise, its value is true. If any of the arguments to or~ are true, then the value of or is true. Otherwise, its value is false. With these predicates, any Boolean operations may be performed. 3.4 Arithmetic Any useful programming language must have means of performing arithmetic and logical operations and making basic tests. For this reason, the programming language LISP 1.5 has provisions for handling fixed-point and floating-point numbers and logical words. In discussing arithmetic in LISP, two things must be considered; the form of numbers for reading and printing, and the arithmetic functions and predicates. Numbers are stored internally as a special type of atomic symbol. They may occur in S-expressions as though they were atomic symbols. Numbers are constants that evaluate to themselves. They do not need to be quoted. Numbers should not be used as variables or function names. A floating-point number must include a decimal point, but not as the first or last character. An optional plus or minus sign may precede the number. An optional exponent may be written directly after the number with the letter E, followed by an optional sign, followed by one or two digits of exponent. A fixed-point number _».s written as an integer with an optional sign. A logical word is written as a hexadecimal constant. It begins with the letter X, followed by the character ', followed by up to eight hex¬ adecimal digits, that is, the digits and the letters A, B, C, D, E, F, followed by the character ’. The arithmetic functions and predicates will be described in detail in section 4.2. These functions must be given numbers as arguments; otherwise an error condition will result. Types of numbers may be mixed in a list of numeric arguments. If all arguments are fixed-point numbers, then the value of the function will be fixed-point number. If at least one argument is a floating-point number, then the value of the function will be a floating-point number. These arithmetic functions may be used recursively, just as other functions available to the interpreter. 3.5 Program Feature The addition of the program feature to LISP 1.5 allows the programmer to write an Algol-like program containing LISP statements to be executed. This allows the programmer to use controlled looping in his LISP program. The program form has the structure (PROG, list of program variables, sequence of statements and atomic symbols...). An atomic symbol in the list is the location marker for the statement beginning immediately after that symbol. The first list after the symbol PROG is a list of program variables. If there are none, then this should be written NIL or (). Program variables are treated much like bound variables, but they are not bound by LAMBDA. The value of each program variable is NIL until it has been set to something else by either a SET form or a SETQ form. These forms are used only to set program variables. Ill - 7 Program statements, which are often executed for their effect rather than their value, are normally executed in sequence. That is, the statements are evaluated with the current association list, and then the value is ignored. The sequence of statements executed may be altered by the form GO. (GO A) causes a transfer to the statement with the location marker A. The form GO can be used only as a statement on the top level of a PROG or immediately inside a COND which is on the top level of a PROG. If a conditional statement on the top level of a PROG has none of its propositions true, then, unlike elsewhere, the program continues with the next statement. The normal end of a program is the form RETURN. The argument of RETURN is evaluated, and this is the value of the program. If a program runs out of statements, it returns with the value NIL. The program feature, like other LISP functions, can be used recursively. Example : rev (x) ::prog ( (y; z) ; A (nul 1 (x)-*return (y); z:=head(x); atom(z)->-go(B)); z:=rev(z); B y:=cons(z;y); x:=tail(x); go(A)) The predicate null is true if its argument is NIL. It is useful in determining when the end of a list is reached. The function rev will reverse a list on all levels so that rev((A ((B C) I)))) = ((D (C B)) A). IV. IMPLEMENTATION OF LISP ON THE SDf> SIGMA 7 'Oils section contains the specifications for an implementation of the programming language LISP 1.5 on the SD5 SIGMA 7 at Vanderbilt University. This implementation is based on the M. I. T. 7090 LISP system. The major difference between the two systems is the omission of the compiler and assembler from the SIGMA 7 system. In other words, this system is an interpretive-only system; all routines associated with the compiler, assembler, and loader arc not present in this implementation. Hie SDS SIGMA 7 is a binary computer with a 32-bit word length and 65,536 words of storage, expandable to 131-072 words. There are 16 general registers, 7 of which can be used for indexing. One level of indirect addressing, with or without post-indexing, is allowed. All of memory is addressable and alterable by byte (8-bit), halfword (2-byte), word (4-byte), and doubleword (8-byte). The halfword addressability makes the elementary functions extremely simple if free storage is limited to 2*'* or 32,768 words, so that a pointer to a word in free storage may be contained in a halfword. When the SDS Batch Processing Monitor is in use, it resides in the lower 19,000 words of memory. The programming system used to translate the programming language LISP 1.5 is an interpretive system. The interpretive system is composed of three major components. First, there is a translator which translates the source language into internal list structures. This routine places the paired arguments, called doublets, for evalquote, onto a list called the input list, abbreviated I-list. A LISP program is simply a series of these doublets. Second, there is the interpreter or universal function evalquote. A control routine passes the pairs from the I-list to the interpreter for execution. The interpreter interprets the application of its first argument, which is an S-expression image of some M-expression, to its second argument, which is the S-expression argument to the function. The interpreter uses an association list, now abbreviated A-list, to keep track of which variables are bound and which functions names are bound. The interpreter, on its lowest level, links the source arguments to appropriate primitives or source language functions. The third component of the interpre¬ tive system is the set of primitives. In discussing the implementation of this programming system, three things must be included. There must be a complete description of the system's internal structures, the functions available to the user, and the running procedures for the system. This section gives these descriptions. 4.1 Internal Structures Five major areas of discussion evolve from a discussion of the internal structures in the LISP system. First, we must specify the run-time storage layout. That is, we must specify exactly where the major components of the system will be when the system is in use. Second, we must consider the internal representation of list structures. Third, we should consider the make up of property lists, for both atomic symbols and for numeric constants. Fourth, we should consider each of the special structures necessary to make the system complete. Finally, we should consider the method of garbage collection and the structures that the garbage collection routine uses. The primary purpose of discussing these internal structures is to give the reader an idea of what the real make up of this programming system is, rather than simply present a functional description of the system. The run-time storage layout is best representated by the following diagram. 0000 Lists are structural forms built out of computer words as parts of trees. In representating list structure, a computer word will be divided as follows: Bit Purpose 0 Reserved for garbage collection 1-15 head(x) - contains a displacement from the beginning of the Free storage area 16 0 - normal 1 - indicates head of numeric p-list 17-31 tail(x) - contains a displacement from the beginning of the Free storage area To represent a word, a rectangle is used. Bits 0 and 16 are ignored, if zero, and the word is represented by a rectangle divided into two sections. The presence of a name in a section indicates a pointer to that atomic symbol's property list. The pointer to NIL is represented by Every atomic symbol has a property list. When an atomic symbol is read, a p-list is created for it. A p-list is characterized by having a -1, or hexadecimal 7FFF, as the first element of the list. The rest of the list contains various indicators followed by pertinant properties of the symbol, and/or flags. A flag is not followed by a property, but rather indicates a property itself. The indicators and flags are: ATOM - flag - the -1 which characterizes p-lists TRACE - flag - indicates that this function should be traced EXf'R - indicator - followed by a pointer to an S-expression which represents some function FEXPR - indicator - followed by a pointer to an S-expression which represents a special form SUBR - indicator - followed by linkage to machine language subroutine, a function FSUBR - indicator - followed by linkage to machine language subroutine, a special form APVAL - indicator - followed by permanent value of the symbol PNAM - indicator - followed by a pointer to a list of full words containing the symbols print name PROP. Full word storage is reserved for storage of elements of the system which require a full word of significance. The primary use is for the storing of print names, numbers, and linkages of subroutines. Example : The print name for the atomic symbol EXAMPLE is: Numbers have a special p-list. The type of number indicated by TYP, where logical words have TYP equal to numbers have TYP equal to 1, and floating-point numbers Example: •~*-l TYP lJ 1 number represented is 0 , fixed-point have a TYP of 2. One of the most important special structures is the object list. The object list is a list of all atomic symbols in existence. The read function uses this list to assure no duplications of p-lists. The structure is actually 28 lists. The first 26 correspond to the letters of the alphabet, and any atomic symbol beginning with the i th letter will have its p-list on the i th U.-L list in the object list. The 27 list consists of all special symbols while the 28^ list consists of all numbers. Example : heads of lists Two other special lists have already been discussed. They are the association list and the input list. Both of these lists, along with the object list, are used during garbage collection to trace all active list structures. There arc several other special structures that should be mentioned. Certain functions available to the user work with characters rather than pointers to lists. These characters are called character objects. The functions expecting character objects will consider the head of a list to be an EBCDIC character rather than a displacement address. There are also several buffers in the system. The character manipulation buffer, called 60FF0, is 120 bytes long. All functions designed to do character manipulations use this buffer. There are three input buffers, each 80 bytes long. Input is actually done with the middle (2 nc *) buffer. The other two buffers are used for indication of errors by the errorl function. There is also a 120 byte output buffer. Finally, a large section of the run¬ time storage layout is reserved for a push-down stack. When arguments are passed to any subroutine, the push-down stack is used for passing arguments. Whenever a. recursive routine is entered, the push-down stack is used to save pertinent information. All of these special structures are necessary to make the system complete. When a word of Free or Full word storage is requested and none is available, the garbage collector is called. A user may explicitly call the garbage collector if he so desires. The user function is called reclaim . The garbage collector traces all active lists through the object list, the input list, and the current association list, setting bit 0 of every free storage word it encounters to 1. For full words, the garbage collector sets a corresponding bit in a bit table. When all lists have been exhausted, the garbage collector makes a linear pass over free storage, creating a new free storage list from words with bit 0 set to 0, and resetting bit 0 if it, is set to 1. Then the garbage collector does the same for full word storage using the bit table. The function reclaim has no arguments and its value is NIL. 4.2 Functions and Constants in the LISP System This section contains all functions available in the LISP System as of August 1969. Each entry contains the name of the object, the property under which it is available (e.g., EXPR, FEXPR, SUBR, FS1JBR, or APVAL), whether it. is a pseudo-function, functional (function having functions as arguments), or predicate, and in some cases a definition of the function as an M-expression. In the case of APVAL's, the value is given. Elementary Functions car [x] : SUBR head [x] : SUBR cdr [x] : SUBR tail [x] : SUBR The elementary functions car and cdr always have some sort of value rather than giving an error diagnostic. A chain of cdr's applied to an atomic symbol will allow one to search its property list. Indiscriminate use of these functions past the atomic level will result in non-list structure and may appear as lengthy or even infinite garbage expressions if printed. The functions head and tail are identical to the functions car and cdr respectively. cons [x;y] : SUBR com; obtains a new word from the free storage list and places its two arguments in the head and tail of this word, respectively. It does not check to see if the arguments are valid list structure. The value of con s IV - 9 is a pointer to the word that was just created. If the free storage list has been exhausted, cons calls the garbage collector to make a new free storage list and then performs the cons operation. atom [x] : SUBR predicate The first word on the property list of an atomic symbol contains -1 or 7FFFj£ in the head. The atom subroutine depends upon this, and on the fact that NIL is located at 0. ec^[x;y] : SUBR predicate eq is true if its two arguments are identical list structure. equal [x;y] : SUBR predicate equal is true if its arguments are the same S-expression, although they do not have to be identical list structures in the computer. It uses eq on the atomic level and is recursive. Floating point numbers in S-expressions are compared for numerical equality with a floating point tolerance of 3 x 10Fixed point numbers are compared for numerical equality. list [x 1 ;...;x n ] : FSUBR The value of list is a list of its arguments. null [x] : SUBR predicate The value of null is true if its argument is NIL which is located at 0 in the computer. SUBR pseudo-function SUBR pseudo-function SUBR pseudo-function pseudo-function SUBR The operator rpla c.a[x;y] replaces the head of x with y. Its value is x, but x is something different from what it was before. In terms of value, rplaca can be described by the equation. rplac a[x;y] = cons [y;cdr[x]]. But the effect is quite different: there is no cons involved and a new word is not created. rplacd [x;y] replaces the tail of x with y. These operators must be used with caution. They can permanently alter existing definitions and other basic memory. They can be used to create circular lists, which can cause infinite printing, and look infinite to functions that search, such as e qual and subst . ! The functions replhd and repltl are identical to the functions rplaca and rplacd respectively. Logical Connectives and[x 1 ;x 2 ...,x r ] : FSUBR predicate The arguments of and are evaluated in sequence, from left to right, until one is found that is false, or until the end of the list is reached. The value of and is false or true repectively. or[Xj;x 2 ...,x n ] : FSUBR predicate The arguments of or are evaluated in sequence from left to right, until one is found that is true, or until the end of the list is reached. The value of or is true or false respectively. not[x] : SUBR predicate The value of not is true if its argument is false, and false otherwise. IV - 11 I nter pret er and Pr og_Feature evalquote ifn;args ] : S!JBR evalquoto [ fn; args ] = [get [ fn; FEXPR] get[fn; FSUBR]-* eval[cons[fn;args];NIL] T-*apply[fn; args; NIL]] This definition shows that evalquote is capable of handling special forms as a sort of exception. Apply cannot handle special forms and will give an error if given one as its first argument. apply [fn;args;a] : SUBR In this description, spread can be regarded as a pseudo-function of one argument. This argument is a list, s pread puts the individual items of this list into the push-down stack. These M-expressions should not be taken too literally. In many cases, the actual program is a store and transfer where a recursion is suggested by these definitions. apply [fn;args;a]-[ null[fn]-*NIL; atom[fn]-*[get[fn;EXPR]-*app.ly[expr; ^argsja]; f spread[args] get [fn;SUBR]-* ^ $ALIST:=a; j" j [ TSX subr 1 ^ J T-*apply[cdr[sassoc[fn;a;X[ [ ];error[A2] ] ] ];args;a]; eq[car[fn];LABEL]-*apply[caddr[fn];args;const cons[cadr[fn];caddr[fn]];a]]; eq[car[fn];FUNARG]-*apply[cadr[fn];args;caddr[fn]]; eq[car[fn];LAMBDA]-*eval[caddr[fn];nconc[pair[cadr[fn];args];a]] T-*apply [eval[fn;a];args;a] ] 1. The value of get is set aside. This is the meaning of the apparent free or undefined variable. eval[form;a] SUBR eval[form;a]=[ null [ form ]-*-NIL; numberp [ f orm]-»-f orm; atom [ f orra ]-*■[ get [ f orm; APVAL ]^-car [ apval 1 ]; T-*cdr [sassoc [ form; a; X [ [ ]; error [ A8 ] ] ] ] ]; eq [ car [ f orm ]; QUOTE ]-»-cadr [ f orm]; eq[car[form];FUNCTION]-*list[FUNARG;cadr[form];a]; eq[car[form] ;COND]-*-evcon[cdr[form] ;a]; eq[car[form] ;PROG]-*-prog[cdr[form] ;a]; atom[ car [form] ]-*[get [ car [ form]; EXPR]->-apply [ expr; ^evlis [ cdr [ form]; a]; a]; get[car[form]jFEXPRl^-applytfexprj^listtcdrtform];a];a]; /spread[evlis[cdr[form];a]]; get[car[form];SUBR]-^j$ALIST:=a; [TSX subr,^4 ^AC:=cdr[form]; | get[car[form] ;FSUBR]-*-jMQ:=$ALIST:=a; p 5 |TSX fsubr, 1 4 J . T-*eval[cons[cdr[sassoc[car[form] ;a;X[ [] ;error[A9] ] ] ]; cdr[form]];a]]; T->-apply[ car [form]; evils [cdr [form] ;a] ;a] ] evcon (c; a] = [null [ c]-»-error [ A3 ]; eval[caar[c] ;a]-»-eval[cadar[c] ;a]; T-*evcon[cdr[c]; a] ] evlislmjaJ^maplisttn^Xt [j ] ;eval[car[j] ;a] ] ] The PROG Feature The PROG feature is an FSUBR coded into the system. It can best be explained in English, although it is possible to define it by using M-expressions. 1. As soon as the PROG feature is entered, the list of program variables is used to make a new list in which each one is paired with NIL. This is then appended to the current a-list. Thus each program variable is set to NIL at the entrance to the program. 1. The value of get is set aside. This is the meaning of the apparent free or undefined variable. IV - 13 2. 'Che remainder of the program is searched for atomic symbols that are understood to bo location symbols. A go-list is formed in which each location symbol is paired with a pointer into the remainder of the program. 3. When a set or a setq is encountered, the name of the variable is located on the a-list. The value of the variable (or edr of the pair) is actually replaced with the new value. If the variable is bound several times on the a-list, only the first or most recent occurrence is changed. J.f the current binding of the variable is at a higher level then the entrance to the prog , then the change will remain in effect throughout the scope of that binding, and the old f value will be lost. If the variable does not occur on the a-list, then an error diagnostic will occur. 4. When a re turn is encountered at any point, its argument is evaluated and returned as the value of the most recent prog that has been entered. 5. The form £0 may be used only in two ways. a. (GO X) may occur on the top level of the prog , x must be a location symbol of this pro g and not another one on a higher or lower level. b. This form may also occur as one of the value parts of a conditional expression, if this conditional expression occurs on the top level of the prog . If a go is used incorrectly or refers to a nonexistent location, an error diagnostic will occur. IV - 14 0 6. When the form cond occurs on the top level of a prog , it differs from other conds in the following ways. a. It is the only instance in which a go can occur inside a cond. b. If the cpnd runs out of clauses, an error diagnostic will no occur. Instead, the pro g will continue with the next statement. 7. When a statement is executed, this has the following meaning, with the exception of the special foras cond , go, retu rn, setq and the pseudo- function set , all of which are peculiar to prog . The statement £ is executed by performing eval[s;a], where a is the current a-list, and then ignoring the value. 8. If a prog runs out of statements, its value is NIL. Defining Functions and Functions Useful for Property Lists d efine [x] : SUBR pseudo-function The argument of define , x, is a list of pairs ((u lV - Vn” where each u is a name and each v is a A-expression for a function. For each pair, define puts an EXPR on the property list for u pointing to v. The function of define puts things on at the front of the property list. The value of define is the list of u's. define[x] = deflist[x;EXPR] deflist[x;ind] : SUBR pseudo-function The function deflist is a more general defining function. Its first argument is a list of pairs as for define . Its second argument is the indicator that is to be used. After deflist has been executed with (u^v^) amoung its first argument, the property list of u i will begin: u. X V. 1 If deflist or define is used twice on the same object with the same indicator, the old value will be replaced by the new one. attrib [x;e] : SUBR pseudo-function The function attrib concatenates its two arguments by changing the last element of its first argument to point to the second argument. Thus it is commonly used to tack something onto the end of a property, list. The value of attrib is the second argument. For example attrib [FF; (EXPR (LAMBDA (X) (COND ((ATOM.X) X) (T (FF (CAR X))))))] would put EXPR followed by the LAMDBA expression for FF onto the end of the property list for FF. prop [x;y;u] : SUBR functional The function prop searches the list x for an item that is e^ to y. If such an element is found, the value of prop is the rest of the list beginning immediately after the element. Otherwise the value is u[], where u is a function of no arguments. prop[x;y;u] = [null[x] -*■ u[];eq[car[x];y]+cdr[x]; T -»-prop[cdr[x];y;u]] I£t[x;y] : SUBR get is somewhat like prop ; however its value is car of the rest of the list if the indicator is found, and NIL otherwise. get[x;y[ = [mill[x] -> NII,;eq[car[x] ;y] -> cadr[x]; T •> get[cdr[x];y]] cset [ob;val] : SUBR pseudo-function This pseudo-function is used to create a constant by putting the indicator APVAL and a value on the property list of an atomic symbol. The first argument should be an atomic symbol; the second argument is the value to be placed on that atomic symbol’s p-list. The value of cset is the value of cons[val,NIL]. csetq [ob;val] : FSUBR pseudo-function csetq is like cset except that it quotes its first argument instead of evaluating it. remprop [x;ind] : SUBR pseudo-function The pseudo-function re mprop searches the list, x, looking for all occurrences of the indicator ind. When such an indicator is found, its name and the succeeding property are removed from the list. The two "ends" of the list are tied together as indicated by the dashed line below. PROPERTY The value of remprop is NIL. When an indicator appears on a property list without a property following it, then it is called a flag. An example of a flag is the indicator TRACE which informs the interpreter that the function on whose property list it appears is to be traced. There are two pseudo-functions for creating and removing flags respectively. flag[£;ind] : SUBR . pseudo-function The pseudo-function flag puts the flag ind on the property list of every atomic symbol in the list Z. Note that Z cannot be an atomic symbol, and must be a list of atomic symbols. The flag is always placed immediately following the first word of the property list, and the rest of the property list then follows. The value of flag is NIL. No property list ever receives a duplicated flag. remflag [l;ind] : SUBR pseudo-function remflag removes all occurrences of the indicator ind from the property list of etch atomic symbol in the list Z. It does this by patching around the indicator with a rplacd in a manner similar to the way remprop works. Table Building and Table Reference Functions pair [x;y] : SUBR The function pair has as value the list of pairs of corresponding elements of the lists x and y. The arguments x and y must be lists of the same number of elements. They should not be atomic symbols. The value is a dotted pair list, i.e. ((a ^ (« 2 • B 2 ) pairfxjy] = [prog[u;v;m] u:= x; v:= y; A [null[u] -* [null[v] ■+ return[m];T -* error[F2]]]; [null[v] error[F3]]; m:= cons[cons[car[u];car[v]];m ]; u:= cdr[u]; v:= cdr[v]; go[A]] IV - 18 sassoc[x;y;u] : SUM functional The function sassoc searches y, which is a list of dotted pairs, for a pair whose first element that is x. If such a pair is found, the value of sassoc is this pair. Otherwise the function u of no arguments is taken as the value of sassoc . sassoc[x;y;u] = [null[y] u[];eq[caarfy];x] -*■ car[y]; T sassocfx;cdr[y];u]] subst [x;y;z] : SUBR The function suhst has as value the result of substituting x for all occurrences of the S-expression y in the S-cxpression z. subst.[x;y;z] = [equal[y;z] -> x; atom[z] -*• z; T -»• cons[subst[x;y;car[z]];subst[x;y;cdr[z]]]] sublis [x;y] : SUBR Here x is a list of pairs. C( u l • vp (u 2 (u. n v )) n J J The value of sublis [x;y] is the result of substituting each v for the corresponding u in y. sublis[x;y] = [null[x] -»■ y; null[y] y; T ■+ search [x; Mf. j ]; equal [y; caar[ j] ] ]; A[[j];cdar[j]]; *[[j]l[atom[y] -► y; T cons [sublis[x;car[y] ];sublis[x;cdr[y] ]]]]]] List Handling Functions append [x;y] : SUBR The function append combines its two arguments into one new list. The value of append is the resultant list. For example, append [(A B) (C) ] = (A B C) append[((A)) (C D)] = ((A) C D) append[x;y] = [null[x] y; T -*■ cons[car[x];append[cdr[x];y]]] Note that append copies the top level of the first list; append is like nconc except that nconc does not copy its first argument. cone t x 2 >X-n>». ■ >x^1 : FSUBR pseudo-function c°nc concatenates its arguments by stringing them all together on the top level. For example, cone [ (A (B • C) D); (F); (G H) ] = (A (B • C) D F G H). cone concatenates its arguments without copying them. Thus it changes existing list structure and is a pseudo-function. The value of cone is the resulting concatenated list. nconc [x;y] : SUBR pseudo-function The function nconc concatenates its arguments without copying the first one. The operation is identical to that of attrjb except that the value is the entire result, (i.e. the modified first argument, x). The program for nconc[x;y] has the program variable m and is as follows: nconc[x;y] = prog[[m]; £null[x] -*■ return[y]]; A [null[cdr[m]] •+• go[B]]; m:=cdr[m]; go[A]; B rplacd[m;y]; return[x]] copy [x] : SUBR This function makes a copy of the list x. The value of copy is the location of the copied list. copy[x] = [null[x] ■+• NIL;atom[x] x;T -*■ cons[copy[car[x]]; copy[cdr[x]]]] reverse [-2] : SUBR This is a function to reverse the top level of a list. Thus reverse[(A B (C • D))] = ((C • D) B A)) reverse[£] = prog[[v]; u:=£; A [null[u] -* return[v]]; v:=cons[car[u];v]; u:=cdr[u]; to [A]] member [x;£] : SUBR predicate If the S-expression x is a member of the list £, then the value of member is *T*. Otherwise, the value is NIL. member[x;£.] = [null[£] -»■ F;equal[x;car[£]] ■** T; T member [x; cdr [-t]]] length [x] : SUBR The value of length is the number of items in the list x. The list ( ) or NIL has length 0. IV - 21 efface[x;£] : SUBR pseudo-function The function efface deletes the first appearance of the item x from the list £. efface[x;£] = [null[£] -*■ NIL; equal [x;car[£]] -*• cdr[£]; T -*■ rplacd[£;efface[x;cdr[£]]]] These four functionals apply a function, f, to x, then to cdr[x], then to cddr[x], etc. Functionals or Functions with Functions as Arguments maplist [x;f] : SUBR functional The function maplist is a mapping of the list x onto a new list f[x]. maplist[x;f] = [null[x] NIL;T cons [f [x] ;maplist[cdr[x] ;f]] ] mapcon [x;f] : SUBR pseudo-functional The function mapcon is like the function maplist except that the resultant list is a concatenated one instead of having been created by cons- ing. mapcon[x;f] = [null[x] NIL;T -*■ nconc[f [x] ;mapcon[cdr[x] ;f]] ] ma£[x;f] : SUBR functional The function ma£ is like the function maplist except that the value °f ma£ is NIL, and ma£ does not do a cons of the evaluated functions. map is used only when the action of doing f[x] is important. The program for map[x;f] has the program variable m and is the following: map[x;f] = prog[[m]; m: = x; LOOP [null [m] -*■ return[NIL] ]; f[m]; m:= cdr[m]; go[LOOP]] search [x;p;f;u] : SUBR functional The function search looks through a list x for an element that has the property p, and if such an element is found the function f of that element is the value of search . If there is no such element, the function u of one argument x is taken as the value of search (in this case x is, of course, NIL). search[x;p;f;u] = [null[x] -*• u[x];p[x] -*■ f[x];T -*■ search[cdr[x];p;f;u]] Arithmetic Functions We shall now list all of the arithmetic functions in the System. They must be given numbers as arguments; otherwise an error condition will result The arguments may be any type of number. A function may be given some fixed-point arguments and some floating-poing arguments at the same time. If all of the arguments for a function are fixed-point numbers, then the value will be a fixed-point number. If at least one argument is a floating-point number, then the value of the function will be a floating¬ point number. plus [x^;...;x^j is a function of any number of arguments whose value is the algebraic sum of the arguments. difference [x;yj has for its value the algebraic difference of its arguments. minus[x] has for its value -x. IV - 23 times [x.^;... ;x^] is a function of any number of arguments, whose value is the product (with correct sign) of its arguments. addl[x] has x+1 for its value. The value is fixed-point or floating¬ point, depending on the argument. subl [x] has x-1 for its value. The value is fixed-point or floating¬ point, depending on the argument. max i^;... ;x n ] chooses the largest of its arguments of its value. Note that max[3;2.0]= 3.0. min tx^...;x^] chooses the smallest of its arguments for its value. recip [x] computes 1/x. The reciprocal of any fixed point number is defined as zero. quotient [x;y] computes the quotient of its arguments. For fixed- point arguments, the value is the number theoretic quotient. A divide check or floating-point trap will result in a LISP error. remainder [x;y] computes the number theoretic remainder for fixed- point numbers, and the floating-point residue for floating-point arguments. divide [x;y] = cons[quotient[x;y]; cons [remainder[x;y];NIL]] expt [x;y] = x^. If both x and y are fixed-point numbers, this is computed by iterative multiplication. Otherwise the power is computed by using logarithms. The first argument cannot be negative. We shall now list all of the arithmetic predicates in the System. They may have fixed-point and floating-point arguments mixed freely. The value of a predicate is *T* or NIL. lessp [x;y] is true if x <y, and false otherwise. greaterp [x;y] is true if x > y. zerop [x] is true if x=0, or if |x| < 3 x 10 onep [x] is true if j x-11 < 3 x 10 minusp [x] is true if x is negative. numbergi [x] is true if x is a number (fixed-point or floating-point). fixp [x] is true only if x is a fixed-point number. If x is not a number at all, an error will result. floatp [x] is similar to fixp[x] but for floating-point numbers. equal [x;y] works on any arguments including S-expressions incorporating numbers inside them. Its value is true if the arguments are identical. Floating-point numbers must satisfy |x-y| < 3 x 10 . The logical functions operate on 32 bit words. The only acceptable arguments are fixed-point numbers. These may be read in as hexadecimal or decimal integers, or they may be the result of a previous computation. logor[x^;...;x n J performs a logical OR on its arguments. logand [x^;. ..;x r ] performs a logical AND on its arguments. logxortXjj...; x r ] performs an exclusive OR (0 v 0 = 0 , 1 v 0 = 0 v 1 = 1, 1 v. 1 = 0). leftshift [x;n] = x X 2 n . The first argument is shifted left by the number of bits specified by the second argument. If the second argument is negative, the first argument will be shifted right. , If the first argument is logical, a logical shift is done and the result is logical. If the first argument is fixed-point, an arithmetic shift is done and the result is fixed-point. If the first argument is floating¬ point, a floating shift is done and the result is floating-point, array [arg] • SUBR pseudo-function Provision is made in LISP 1.5 for allocating blocks or storage for data. The data may consist of numbers, atomic symbols or other S-expressions. The pseudo-function array reserves space for arrays, and turns the name of an array into a function that can be used to fill the array or locate any element of it. IV - 25 Arrays may have up to three indices. Each element (uniquely specified by its co-ordinates) contains a pointer to an S-expression. array is a function of one argument which is a list of arrays to be declared. Each item is a list containing the name of an array, its dimensions, and the word LIST. (Non-list arrays are reserved for future developments of the LISP system.) For example, to make an array called alpha of size 7 x 10, and one called beta of size 3x4x5 one should execute: array[((ALPHA (7 10) LIST) (BETA (3 4 5) LIST))] After this has been executed, both arrays exist and their elements are all set to NIL. Indices range from 0 to n-1. alpha and beta are now functions that can be used to set or locate elements of these respective arrays. To set alpha . . to x, execute - alpha[SET;x;i;j] To set alpha 3 4 to (A B C) execute - alpha[SET;(A B C);3;4] Inside a function or program X might be bound to (A B C), I bound to 3, and J bound to 4, in which case the setting can be done by evaluating - (ALPHA (QUOTE SET) X I J) To locate an element of an array, use the array name as a function with the coordinates as axis. Thus any time after executing the previous example - alpha[3;4] = (ABC) IV - 26 Arrays are stored as lists originating in the property list of the array name. Indexing is accomplished by a linear search for the n** 1 element of the array list. Input and Output rea< * [ ] : SUBR pseudo-function The execution of read causes one list to be read from the SI device. The list that is read is the value of read . print [x] : SUBR pseudo-function The execution of print causes the S-expression x to be printed on the LO device. The value of print is its argument. punch [x] : SUBR pseudo-function The execution of punch causes S-expression x to be punched in BCD card images on the PO device. The value of punch is its argument. prinl [x] : SUBR pseudo-function prinl prints an atomic symbol without terminating the print line. The argument of prinl must be an atomic symbol. terpri [ ] : SUBR pseudo-function terpri terminates the print line. mprint [x i] : SUBR pseudo-function The execution of mprint causes the S-expression x to be written in 80 character records on device F:i. The F: device must be assigned to a physical device by an !ASSIGN control card preceeding the I LISP control card. The value of mprint is the list printed. 1 < i < 5 inread [i] SUBR pseudo-function The execution of mread causes one S-expression to be read from the F:i device. The value of mread is the S-expression read. 1 <_ i <_ 5 . rewind[i] : SUBR pseudo-function rewind [i] rewinds the F:i device. The value of rewind is NIL. 1 <_ i <_ 5 backspace [i] : SUBR pseudo-function The execution of backspace causes the F:i device to be backspaced one record. Caution in the use of this function is recommended, for if an S-expression to be read from an F: device is more than 80 characters, then it will occupy more than one record on the F: device, and a single backspace will not move the device all the way back to the beginning of the S-expression. The value of backspace is NIL, 1 i i £ 5 . Packing and Unpacking Characters When a sequence of characters is to be made into either a print name or a numerical object, the characters must be put one by one into a buffer called BOFFO. BOFFO is. used to store the characters until they are to be combined. It is not available explicitly to the LISP programmer, but the character-packing functions are described in terms of theip effects on BOFFO. At any point, BOFFO contains a sequence of characters. Each operation on BOFFO either adds another character at the end of the sequence or clears BOFFO, i.e., sets BOFFO to the null sequence. The maximum length of the sequence is 120 characters; an attempt to add more characters will cause an error. The character-packing- functions arc: pack [c] : SUBR pseudo-function The argument of pack must be a character object, pack adds the character c at the end of the sequence of characters in BOFFO. The value of pack is NIL. clearbuff [ ] : SUBR pseudo-function clearbuff is a function of no arguments. It clears BOFFO and has value NIL. The contents of BUFFO are undefined until a clearbuff has been performed. mknam [ ] : SUBR pseudo-function mknam is a function of no arguments. Its value is a list of full words containing the characters in BOFFO in packed BCD form. The last word is filled out with blanks if necessary. After mknam is performed, BOFFO ; is automatically cleared. Note that intern [mknam[ ]] yields the object whose print name is in BOFFO. numob [ ] : SUBR pseudo-function numob is a function of no arguments. Its value is the numerical object represented by the sequence of characters in BOFFO. (Positive decimal integers from 0 to 9 are converted so as to point to the corresponding character object.) unpack [x]: : SUBR pseudo-function This function has as argument a pointer to a full word, unpack considers the full word to be a set of 4 BCD characters, and has as value a list of these characters ignoring all characters including and following the first blank. intern [pname] : SUBR pseud-function This function has as argument a pointer to a PNAME type structure such as Its value is the atomic symbol having this print name. If it does not already exist, then a new atomic symbol will be created. The Character-Classifying Predicates liter[c]: : SUBR predicate liter has as argument a character object. Its value is T if the character is a letter of the alphabet, and F otherwise. digit [c]: : SUBR predicate digit has as argument a character object. Its value is T if the character is a digit between 0 and 9, and F otherwise. opchar fc]: : SUBR predicate opchar has as argument a character object. Its value is T if the character is +, -,•■/, *, or =, and F otherwise. dash [c]: : SUBR predicate dash has as argument a character object. Its value is T if the character is an 11-punch minus, and F otherwise. The Character-Reading Functions The character-reading functions make it possible to read characters one by one from input. There is an object CURCHAR whose value is the character most recently read (as an object). There is also an object CHARCOUNT whose value is an integer object given the column just read on the card, i.e., the column number of the character given by CURCHAR. There are three functions which affect the value of CURCHAR: startread [ ]: : SUBR pseudo-function startread is a function of no arguments which causes a new card to be read. The value of startread is the first character on that card, or more precisely, the object corresponding to the first character on the card. If and end-of-file condition exists, the value of startread is $EOF$. The value of CURCHAR becomes the same as the output of startread , and the value of CHARCOUNT becomes 1. Both CURCHAR and CHARCOUNT are undefined until a startread is performed. A startread may be performed before the current card has been completely read. advance[ ]: : SUBR pseudo-function advance is a function of no arguments which causes the next character to be read. The value of advance is that character. After the 72 n< * character on the card has been read, the next advance will have value $EOR$. After reading $EOR$, the next advance will act like a startread , i.e., will read the first character of the next card unless an end-of-file condition exists. Hie new value of CURCHAR is the same as the output of advance ; executing advance also increases the value of CHARCOUNT by 1. However, CHARCOUNT is undefined when CURCHAR is either $EOR$ or $EOF$. endread[ ]: SUBR pseudo-function endread is a function of no arguments which causes the remainder of the card to be read and ignored, endread sets CURCHAR to $EOR$ and leaves CHARCOUNT undefined; the value of endread is always $EOR$. An advance following endread acts like a startread . If CURCHAR already has value $EOR$ and endread is performed, CURCHAR will remain the same and endread will, as usual, have value $EOR$. Diagnostic Function errorl [ ]: : SUBR pseudo-function error1 is a function of no arguments and has value NIL. It should be executed only while reading characters from a card (or tape]). Its effect is to mark the character just read, i.e., CURCHAR, so that when the end of the card is reached, either by successive advances or by an endread , the entire card is printed out along with a visual pointer to the defective character. For a line consisting of ABCDEFG followed by blanks, a pointer to C would look like this: V ABCDEFG A If errorl is performed an even number of times on the same character, the A will not appear. If errorl is performed before the first startread or while CURCHAR has value $EOR$ or $EOF$, it will have no effect. Executing a startread before the current card has been completed will cause the errorl printout to be lost. The card is considered to have been completed when CURCHAR has been set to $EOR$. Successive endreads will cause the errorl printout to be reprinted. Any number of characters in a given line may be marked by errorl . Miscellaneous Functions trace [x] : SUBR pseudo-function The argument of trace is a list of functions. After trace has been executed, the arguments and values of these functions are printed each time the function is entered recursively. The value of trace is NIL. Special forms cannot be traced. untrace [x] : SUBR pseudo-function This removes the tracing from all functions in the list x. The value of untrace is NIL. obkeep [s] : SUBR pseudo-function The argument of obkeep is a list of atom names which the programmer wishes to keep. All other atomic symbols are removed from the system. The value of obkeep is NIL. reserved [ ] : SUBR pseudo-function The execution of reserved causes the printing of all atoms on the object list. The value of reserved is NIL. space [x] : SUBR pseudo-function space[*T*] causes all output to be double-spaced, space [NIL] restores the spacing to its original status. The value of space is NIL. eject [ ] : SUBR pseudo-function eject [ ] causes a skip to the top of the next page of output. Its value is NIL. verbos [x] : SUBR pseudo-function verbos [NIL] causes reclaim not to print its message whenever it is called, verbos[*T*] restores reclaim's message. Its value is NIL. count [n] SUBR pseudo-function count [n] turns the cons counter on and resets, the .counter. After n conses have been executed, a cons counter trap occurs, count [NIL] turns the counter on so as to continue counting from the state it was in when last turned off. The value of count is NIL. uncount [NIL] : SUBR pseudo-function uncount [NIL] turns off the cons counter. Its value is NIL. speak [NIL] : SUBR pseudo-function The value of speak [NIL] is the number of conses counted since the counter was last reset. error [x] : SUBR pseudo-function error causes an error diagnostic to be printed along with the S-expression x. The value of error is x. prog2 [x;y] : SUBR the value of prog2 is its second argument. It is used mainly to perform two pseudo-functions. prog2[x;y] = y cpl[x] : SUBR cpl copies its argument which must be a list of a very special type. FULL WORD FULL WORD The copied list is the value of cpl . IV - 34 gensym [ ] : SUBR The function gensym has no arguments. Its value is a new, distinct, and freshly created atomic symbol with a print name of the form G001, G002, ..., G999. This function is useful for creating atomic symbol when one is needed; each one is guaranteed unique, gensym names are not permanent and will not be recognized if read back in. ££lect[q;(q 1 e 1 );(q 2 e 2 );...;(q n e n );e] : FSUBR The q^'s in select are evaluated in sequence from left to right until one is found that <\ ± = q> and the value of select is the value of the corresponding e.. If no such ... i q^ is found the value of select is that of e. tempus [ ] : SUBR pseudo-function Executing this will cause a time statement to appear in the output. The value is NIL. reclaim [ ] : SUBR pseudo-function Executing this will cause a garbage collection to occur. The value is NIL. pause [ ] : SUBR pseudo-function pause [ ] is a no operation function. Its value is NIL. dump [low;high;title] : SUBR pseudo-function The first two arguments must be absolute hexadecimal addresses. . dump causes memory to be dumped in hexadecimal from location low to location high . The value of dump is NIL. intern[x] : SUBR pseudo-function The argument of intern must be a PNAME type of structure, that is, a list of full words forming a print name. If this print name belongs to an already existing atomic symbol, this is found, otherwise a new one is created. The value of intern in either case is an atomic symbol having the specified print name. remob [x] : SUBR This removes the atom x from the object list. It causes the symbol and all its properties to be lost unless the symbol is referred t° by active list structure. When an atomic symbol has been removed, subsequent reading of its name from input will create a different atomic symbol. Its value is NIL. traceset[x] : EXPR pseudo-function traceset is a debugging aid. The argument x should be a list of functions names. Each of these functions must be an EXPR which has a PROG on the top level, traceset modifies the definition of the function so that every SETQ on the first level inside the PROG is traced. For example, suppose a PROG has the statement (SETQ A X). At run time, if this statement is executed while X has the value (U V), then in addition to setting the variable A, the function will print out. (A =) (U V) untraceset [x] is part of the traceset package. Its argument is a list of functions whose definitions are to be restored to their original condition. IV - 36 printprop [x] : EXPR pseudo-function If x is an atomic symbol, all of its properties will be printed in the output. Nothing is changed by printprop . punchdef [x] : EXPR pseudo-function If x is a list of atomic symbols, each one having an EXPR or FEXPR will have its definition punched out. Nothing is changed. APVAL's APVAL value BLANK CHARCOUNT COMMA CURCHAR DOLLAR EOF EOR EQSI6N F LPAR NIL PERIOD PLUSS RPAR SLASH STAR T (BCD blank) (character count during reading of characters) (current character during reading of characters) $ $EOF$ $EOR$ NIL ( NIL ) / * ★•j 1 * V. USER OPERATING PROCEDURES 5.1 The LISP Program A program for execution in LISP consists of a sequence of doublets. . The first list or atomic symbol of each doublet is in¬ terpreted as a function. Hie second is a list of arguments for the function. They are evaluated by evalquote , and the value is printed. The program should be terminated by the atomic symbol STOP. There is no particular card format for writing LISP. Card boundaries are ignored. ' , * s » ' ‘ If ! tfie liser? requires input data for his LISP <program, this d'ata . i ' ’ should begi^on the next cqjrd. immediately j^ftei^ the 9 ard witty the ° ■ * * . • ■ 1 I j STOP atomic ^s^inbol. The end of data,should*be indicated by ( eit!hei“ a i : i ; . i 1 j | 1 ’ \ ! j \ ! , !EOp or a !I*IN carijl. ! 1 ’’ 5.2 Tape Operations r The functions rewind , mprint , mread, 'and backspace are designed to allow the user access to tape and other physical devices. Specifically, they use the user DCB's F:l, F:2, F:3, F:4, and F:5. If used, the F: devices must be assigned by IASSIGN control cards preceeding the !LISP < control card. * 5.3 System Messages ' Translation Phase When the translation phase is initiated, the following message appears as the heading. * LISP 1.5 * AVAILABLE MEMORY * FREE STORAGE = XXXXX (WORDS) * FULL WORD STORAGE = XXXX (WORDS) * PUSH-DOWN STACK = XXXX(WORDS) Following this message is the source listing. Errors encountered during the translation phase are discussed under Input/Output error messages. Normally, an error in the translation phase will cause the interpreter to be bypassed. In this case, the following message would be found. ERROR IN TRANSLATION PHASE INTERPRETER ABORTED Interpreter Phase The interpreter phase is begun by: LISP 1.5 SYSTEM INITIATED 10:22 JUL 4,'69 When the interpreter is entered, it prints: FUNCTION EVALQUOTE HAS BEEN ENTERED, ARGUMENTS., followed by the two arguments to evalquote . At completion of the interpretation of a doublet, evalquote prints: END OF EVALQUOTE, VALUE IS., followed by the value. When the interpreter phase is. completed: LISP 1.5 SYSTEM TERMINATED 10:25 JUL 4,'69 Garbage Collector When the garbage collector is called, it prints the following; RECLAIM m FREE n FULL where m is the number of free words collected, and n is the number of full words collected. Error Diagnostics When an error occurs, a diagnostic giving the nature of the error is printed out. The diagnostic gives the type of error and in some cases additional information about the error. If the DB option was specified, then a backtrace is also printed. This is a list of functions that were entered recursively but not completed at the time of the error. In most cases, the program continues with the next doublet if in debug mode. If not in debug mode, control is returned to the monitor. Certain errors are fatal, and control is always passed to the monitor. Interpreter Errors: FUNCTION NOT DEFINED - APPLY This occurs when an atomic symbol, given as the first argument to apply , does not have a definition either on its property list or on the a-list of apply . The atomic symbol immediately following the diagnostic is the undefined symbol. FUNCTION NOT DEFINED - EVAL Eval expects the first object on a list to be evaluated to be an atomic symbol. This frequently occurs when a parenthesis miscount causes the wrong phase to be evaluated. The undefined symbol is printed. WRONG NUMBER OF ARGUMENTS A function expecting a fixed number of arguments was passed the wrong number of arguments. UNBOUND VARIABLE - EVAL The atomic symbol in question is not bound on the a-list for eval nor does it have an APVAL. The undefined symbol is printed. CONDITIONAL UNSATISFIED - EVCON None of the propositions following COND are true. INVALID GO ARGUMENT Go refers to a point not labelled. VARIABLE UNBOUND - SET Either set or setq is attempted on a nonexistent program variable. The undefined symbol is printed. Character-Handling Errors: BUFFER OVERFLOW - PACK FLOATING POINT NUMBER OUT OF RANGE - NUMOB NUMERIC CONSTANT MISFORMED - NUMOB Miscellaneous Errors: CONS COUNTER TRAP ARGUMENT LISTS NOT SAME LENGTH PAIR Pair is used by the interpreter to bind variables to arguments. If a function is given the wrong number of arguments, this error may occur. ARITHMETIC OVERFLOW SYSTEM STACK OVERFLOW The push-down stack is the memory device that keeps track of the level of recursion. When recursion becomes very deep, this error may occur. Non-terminating recursion will cause this error. INVALID DUMP ARGUMENT INVALID TRACESET ARGUMENT Garbage Collector Errors: FATAL ERROR - RECLAIM This error occurs only when the system is so choked that it cannot be restored. Control goes to the monitor. Arithmetic Errors: ILLEGAL NUMBER OF DIMENSIONS WRONG NUMBER OF SUBSCRIPTS SUBSCRIPT NOT NUMERIC SUBSCRIPT OUT OF RANGE INVALID ARGUMENT - EXPT First argument cannot be negative. INTEGER OVERFLOW - EXPT REAL OVERFLOW - EXPT ARITH FUNCTION GIVEN NON-NUMERIC ARGUMENT Input - Output Errors: PRIN1 ARG IS NON-ATOMIC FIRST OBJECT ON INPUT LIST ILLEGAL - READ This error occurs when the read program encounters a character such as a ")" or out of context. This occurs frequently when there is a parenthesis miscount. CONTEXT ERROR - READ The dot-notation was not used properly. INVALID CHARACTER - READ HEX CONSTANT MISFORMED ILLEGAL $$ FORMAT END OF FILE - READ INVALID TAPE FUNCTION ARGUMENT 5.4 Control Card Options The options listed below may be specified on the !LISP control card. DB - debug - After any error, a backtrace is given. Then execution is continued with the next doublet. NODB - no debug, default - After an error, the execution is terminated and control is returned to the monitor. LS - list source, default NOLS - no list source GO - Begin execution of the first doublet even if translation phase errors occur. NOGO - No execution phase. If neither GO nor NOGO is specified, then the execution phase will begin if no translation phase errors occur. VI. CONCLUSIONS AND FUTURE CONSIDERATIONS An interpretive system capable of translating the prograpning language LISP 1.5 has been successfully implemented on the SDS SIGMA 7. There are no restrictions to the language in this implementation. The mathematical language LISP, with sufficient extensions to make it useful in a programming environment, is now accessible to SIGMA 7 users. The language's primary use has been in the field of artificial intelligence research. It has been used for symbolic calculations in calculus, mathematical logic, game playing, and other fields of artificial intelli¬ gence. It has also been useful in further understanding of information structures in general. It is hoped that the implementation of LISP on the SIGMA 7 might allow more people access to the language, so that its study and use might prove more profitable. In the future, the present implementation will be expanded to include a compiler, assembler, and loader. The compiler may be called by the user to translate any function from LISP into machine language. When this is done, the function should be much faster in execution speed, for the interpreter will link the source arguments to the compiled function rather than execute it interpretively. The assembler and loader will allow the LISP user to include assembly language subroutines which he himself has written. These additions should improve the speed of the LISP system as well as add to its flexibility. APPENDIX I LISP 1.5 FUNCTIONS The functions that are marked by an asterisk are new functions or functions that are different from the functions with ■ the : same name in M.I.T. 7090 LISP 1, .5. See Section 4.2 for details on all functions. ADD1 ♦GENSYM PROG2 ADVANCE GET PROP AND GO PUNCH APPEND GREATERP PUNCHDEF APPLY ♦HEAD QUOTE ♦ARRAY INTERN QUOTIENT ATOM ' LABEL READ ATTRIB ♦LEFTSHIFT RECIP ♦BACKSPACE LENGTH RECLAIM CAR LESSP REMAINDER CDR LIST REMFLAG CLEARBUFF LITER REMOB CONC LOGAND REMPROP CONS LOGOR ♦REPLHD COPY LOGXOR ♦REPLTL COUNT MAP ♦RESERVED CPI MAPCON RETURN CSET MAPLIST REVERSE CSETQ MAX REWIND DASH MEMBER RPLACA DEFINE MIN RPLACD DEFLIST MINUS SASSOC DIFFERENCE MINUSP SEARCH DIGIT MKNAM SELECT DIVIDE ♦MPRING SET DUMP ♦MREAD SETQ EFFACE NCONC SPACE EJECT NOT SPEAK ENREAD NULL STARTREAD EQ NUMBERP SUB1 EQUAL NUMOB SUBLIS ERROR ♦OBKEEP SUBST ERROR1 ONEP ♦TAIL EVAL OPCHAR ♦TEMPUS ♦EVALQUOTE OR TERPRI EVLIS PACK TIMES EXPT PAIR TRACE ♦FIX ♦PAUSE TRACESET FIXP PLUS UNCOUNT FLAG PRIN1 UNPACK ♦FLOAT PRINT UNTRACE ♦FLOATP PRINTPROP UNTRACESET FUNCTION PROG VERBOS ZEROP ‘