COMMENT ⊗ VALID 00026 PAGES C REC PAGE DESCRIPTION C00001 00001 C00004 00002 A Brief Description of the Stanford Lisp Compiler C00007 00003 Fundamental Table Dispatch Mechanism C00011 00004 Top Level C00015 00005 Pass One C00019 00006 Pass Two C00021 00007 Glossary of Lisp Compiler Functions C00025 00008 TOP LEVEL C00030 00009 PASS1 C00041 00010 PASS2 C00043 00011 BOOLNULL compiles the function NULL, by simply reversing the C00046 00012 CALLSUBR This is the fundamental function call operation. C00049 00013 CLRCCLST computes the values of items waiting to be loaded C00051 00014 COMPFORM is the central routine of the compiler. It is in C00054 00015 DOP2VAL manages the compilation of functions which primarily C00056 00016 GETSLOT takes as argument an number indicating a storage C00058 00017 OUT1 C00064 00018 EXITN is the exit from a prog which returns NIL and is used similarly C00067 00019 NACS is the number of acs which may be used for function arguments. C00071 00020 PRSSL is a copy of the stack just after all of the prog variables C00073 00021 User Errors C00075 00022 User Warnings C00076 00023 Other Compiler Messages C00078 00024 Compiler Errors C00079 00025 In considering the correctness of a LISP compiler, the question arises C00082 00026 The compiler's attempts at optimization have added to the primary C00084 ENDMK C⊗; A Brief Description of the Stanford Lisp Compiler This document will attempt to give a brief explanation of the fundamental structure and behavior of the Stanford Lisp compiler. Throughout the operation of the Lisp compiler, as described in the Lisp 1.6 manual will be assumed known. In all explicit descriptions below, the compiler will be taken to be operation on a disk file to produce another disk file, as this is the fundamental mode of operation. Organisation The compiler is divided into three major parts. Toplevel, the first of these is concerned with processing user commands, handling files and in general providing the framework within which actual compiling takes place. The remaining two parts are concerned with compilation itself. The first, Pass1, preprocesses the expression, putting certain things in normal forms, expanding macros and recording information in tables. The second, Pass2, operating on the output of Pass1, preforms the final code generation. In addition, there are verious subsidiary pieces dealing with IO, debugging and general subroutine support. The three major pieces will be discussed after a brief digression to consider a basic mechanism which is used at several places in the compiler. Fundamental Table Dispatch Mechanism It is a common process in Lisp programs to process a S-expression with an atomic car by checking for certain set atoms or certain classes of atoms and calling routines corresponding to these various cases. For example, a routine to evaluate arithmetic expressions might, after first check for an atomic expression, test to see if car of the expression were one of plus, times etc. and calling routines to add or multiply as appropriate. In a slightly more complicated arithmetic interpreter, there might also be certain classes. Sin, Cosine and Tangent might all lead to the invocation of the same routine for processing trigonometric functions. The disadvantages of this technique are twofold. First, it is inflexible, and second, it is, in certain ways, inefficient. The latter is a problem of growth. Though the tests are not time consuming, the total time increases with their number. Much more important, is the fact that when adding or modifying the behavior of a process written in this way, the original code must be altered even for a pure addtion. This may necessitate recompiling or other time consuming processes. The technique which will now be described attempts to systematize the process of dispatching on the car of an expression in such a way as to remove these disadvantages. Given a non-atomic expression with an atomic car to be processed, our basic intention is to search the property list of the car for some property of interest. Rather than having a list of the properties which are of interest, however, the emphasis on flexibility can be pushed still furtther by distinguishing interesting properties by examining their own property lists. Thus given an atom which is car of an expression, each indicator on its property list is examined to see if it in turn has a special property. This last property is not a seat of flexibility but occurs explicitly in the code. The routine in the compler which accomplishes this is called GETGET. In the following sections, three explicit cases of its use will be discussed. Top Level When the COMPL command is given, causing the compilation of a file, the compiler must process each expression in the file appropriately. The file may contain functions defined by S-expressions, functions defined by Lap, declarations affecting the compiler, expressions to be evaluated at load time, comments etc. Each of these things must be processed differently. The function definitions must be compiled into Lap, the Lap must be examined to note the types of the functions it defines, the declarations must be processed for their intended effects, the runtime S-expressions must be printed out unchanged, and the comments must be absorbed and ignored. Further, all of these things must be done in such a way that changes and additions may be easily made. After all of the overhead of deciphering the user's command and preparing for a file processing operation has been put by, the compiler settles down to considering each expression in the input file to decide on appropriate action. The routine which does this is called COMPEFFECT. If the expression is atomic, it is simply printed and no further action is taken. If it is not atomic, but has an atomic car, the function GETGET is called with the property COMPEFFECT in mind. If the car of the expression has a property, which in turn has the COMPEFFECT property then the entire S-expression is handed over to the function which is the value of this COMPEFFECT property. At present, in the case of the top level there are only two atoms which have the COMPEFFECT property. The first of these is the atom MACRO. Thus if car of an expression is a macro, then control will be given to the function ACTONMACRO which will be found as the CCOMPEFFECT property of the atom MACRO. The function ACTONMACRO will then make use of the macro definition to expand the macro and then apply the function ACTONEXPR to the result. The other distinguished property which will be uncovered by ACTONEXPR is COMPACTION. This property indicates that the atom in question is to be dealt with specially. The value of the COMPEFFECT property of the atom COMPACTION is a simple function which finds the COMPACTION property of the original atom and hands it control. Pass One Pass one is the first part of compiling proper. As noted above, it will put the expression in normal form by such acts as expanding macros and recording information for the use of the second pass. As with the top level, control is passed around among functions which occur as properties of various atoms and are discovered by the operation of GETGET. The property given to GETGET in this case is PASS1. Several atoms have the PASS1 property including SUBR, FSUBR, MACRO and their relatives. As with the COMPEFFECTs of the top level, there is a property which indicates that an expression is to receive special treatment. This property is P1. The information kept by pass one is primarily about the variables occurring in the expression. Variables are divided into two classes, SPECIAL and LOCAL. Into the former go all variables whether bound or not which are know to the compiler as special variables from either declarations or prior free occurrence. The local variables are kept on a separate list and certain information is kept about them. During the process of compilation, it is often necessary to refer to quantities which are old values of variables. Rather than assigning to each such quantity a separate name and treating is as a peculiar sort of variable, the compiler keeps a count during compilation which is used to record the progress of events. This count which is set to zero at the beginning of each pass is incremented each time that any variable is referenced in any way, and at certain other places. It is desired to guarantee that if a variable takes on two different values, it may not do so at one value of the count. The count thus serves the function of a sort of "time" within the compilation. The first pass, in addition to maintaining the count, will record for each local variable the last value of the count at which it was seen. Thus if the count during the second pass should ever become larger that that associated with some variable, then the variable will never be used again. This allows the space it occupied to be used for something else. Pass Two The fundamental processes of the compiler take place in pass two. Most of the complexity of this section is due to a desire to exploit the architecture of the PDP-10 by placing function arguments in the accumulators. In order to avoid the orgy of pushing and popping the most frequent action in which the compiler must engage is that of compiling the arguments to a function, then applying the function to the arguments. If this were done in the straight forward way in which it would be done if arguments were placed on the stack, the need to maintain transparancy would result in an orgy of pushing and popping which would paralyse the computation. Instead the compiler follows a more sophisticated and vastly more confusing plan. It compiles in turn each argument without loading it into any particualar place. This amounts to guaranteeing that the desired result exists somewhere in the machine and making note that it may be moved but not damaged. Finally, after all of a functions arguments have been compiled, they are loaded into the first few accumulators and the funtion is called. Glossary of Lisp Compiler Functions MACROS DFUNC defines an EXPR. FLUSHDEF prints a definition. GETPROP behaves like GET. IFIF is the logical "if and only if". INCR is used to increment the compiler's count. MAPDEF does lots of defprops in one compact expression. MCONS is cons of several things. OUTINST outputs an instruction by calling OUTSTAT. OUTPSOP outputs a pseudo-op by calling OUTSTAT. OUTTAG outpust a tag by calling OUTSTAT. PDLDEPTH gives the current number of items on the push down list. Q is short for quote. TAGP asks if an expression is a tag. USERWARN prints a message warning the user of a potentally dangerous condition in his code. The property list manipulating functions operate primarly on tails of the property lists of atoms. The functions which fetch a property return the tail of the property list, beginning with the property name. The word property below will refer to such a tail. FIRSTPROP gets the first property from the property list of an identifier, ie. the whole property list. LASTPROP asks if a property is the last on the property list of an atom. NEXTPROP gets the next property after the one it is givenas an argument. PROPNAM takes a property as an argument and returns the name of the property. PROPTABLE takes an identifier as argument and returns the property list. PROPVAL takes a property and returns the value part of the property. DELETEPROP takes an identifier and a property name and removes the property with that name from the identifier. HASPROP is a predicate which asks is an atom has a property. INITPROP plases a property on a property list, whether or not there is one there. SEEKPROP looks for a property name on the property list of an atom. SETPROP takes an identifier, a property name and a value and sets that property to the value. TOP LEVEL ACTONEXPR decides the action to be taken on each expression in a file being compiled. ACTONMACRO expands macros at the top level in a file being compiled. CMP is for debugging. It takes as argument either a single function name or a function definition in the same format as DFUNC. COMPDEF handles the compilation of a DEFPROP. COMPFILE compiles a file. COMPFUNC manages the compilation of a function definition. COMPILE takes a list of function names and compiles their definitions. COMPILEFUN does most of the work for COMPILE and CMP. COMPL compiles a list of files, by calling COMPFILE on each. COMPREADS is a read and compile loop. CURFILE gives the name of the file currently being compiled for use in error messages. CURFUN gives the name of the function currently being compiled for use in error messages. DECLARE is a function know to the compiler, which if encountered at the top level of a file during compilation evaluates each of its arguments. DEFEXPR manages the compilation of a DEFPROP of an EXPR. DEFFEXPR manages the compilation of a DEFPROP of an FEXPR. DEFMACRO manages the compilation of a DEFPROP of a MACRO DO*EXPR operates on a DEFPROP of a *EXPR. DO*FEXPR operates on a DEFPROP of a *FEXPR. DOACT dispatches the compilation of a function found at the top level in a file which has a COMPACTION property indicating it is to get special treatment. DODE operates on a DE to compile the defined function. DODF operates on a DF to compile the defined function. DODM operates on a DM to define the macro. DOFILE applies a functional argument to each expression in a file. FLUSHEXPR prints out an expression on which no other action has been taken. FLUSHLAP prints out LAP definitions in files being compiled. MAKDEF produces a DEFPROP expression from its arguments to hand to COMPDEF. MAPPUT puts a property onto a list of atoms. PRINTMSG prints a message on the listing device for error messages and warnings. READLOOP reads and applies a functional argument to each expression read. SPECIAL is known to the compiler, and when seen at the top level of a file being compiled declares each of its arguments to be a special variable. TELLTALE plows through data left after the compilation of a file and reports various information. TYPEFN types out a function name on the listing defivice to show that the compilation of a function has been completed. UNSPECIAL behaves in a way complementary to SPECIAL and removes the special declarations from its arguments. CINIT initializes the compiler. It does an excise and sets the INITFN to CSTART. CSTART attemts to read initializatin files from the disk and then prints a message saying that the compiler has started. PASS1 The process of the first pass of the compiler will be referred to expansion. It is a process of putting expressions into normal form, and recording information in tables for the use of the second pass. Expressions are usually expanded by first expanding the arguments then massageing the whole. Each expressin must be expanded in accordance with the context in which it appears. An expression which appers as an argument to a CONS must be expanded in light of the fact that it is to be evaluated. If on the other hand, it appears as an argument to a QUOTE, it must be left alone. The first case will be called expansion in evaluated contest or expansion for evaluation. The latter will be called expansion in quoted context. In one or two contexts, ie. PROGs, things are more complicated and atoms must be treated differently from all other expressions. Tables are kept for both the local and the special variables. When a variable is either bound or referenced, it is added to the appropriate table. Throughout the first pass a count(P1CNT) is kept of all references to all variables. For each local variable a note is made of the count, each time it is seen. This noted counts will be referred to as the last appearance of the variable. In addition to the usual function properties of atoms, the compiler adds some for its own use. The properties *SUBR, *FUSBR, and *LSUBR indicate functions know to be of the times SUBR, FSUBR, and LSUBR by the compler, but whose definitions are not present. The property *UNDEF indicates a function believed to be a SUBR but as yet undefined. The property FUNVAR indicates a functional variable which must not be mistaken for an ordinary function name. DOP1 applies specfic routines to expressions whose CARs have the P1 property, which indicates that they get special treatment. GENFUN takes a piece of code, wraps it up as a function of no arguments, gives it a generated name, and compiles it. MAPP1 applies the first pass expansion process to each element of a list. P1 is the central function of the first pass of the compiler. It examines the property lists of the CARs of the expressions it processes, and acts accordingly in giving their expansion to suitable more specialized functions. P1ANDOR expands ANDs and ORs. Aside from expanding the arguments, It uses P1BUG to raise the last appearance number of each variable to the highest count seen during the AND or OR. P1BIND operates on a list of variables to be bound by a lambda or prog. After checking for various errors, it adds information about them to various lists. P1BUG raises the "last count at which seen" of variables seen after a certain point to some larger value. This occurs in circomstances, like PROG, where order of evaluation of expressions is varible. P1COND expands COND expressions. This is in many ways similar to the process for ANDs and ORs but expansion must be mapped over each of the tuples. P1CONS expands CONSes. This function will try to turn a CONS to an NCONS. P1ELSE handles all functions not already known to the compiler, by supposing that they are as yet undefined EXPRs. The *UNDEF property is put on their property lists and they are added to the list of undefined functons. P1ERRSET compiles the argument of the ERRSET using GENFUN and changes the expression to refer to a call on this new function. P1EVAL expands an EVAL, attempting to make it a *EVAL. P1FUNCTION compiles the argument of a FUNCTION statement using GENFUN, and modifies the call to refer to this new function. P1*FUNCTION behaves about the same as P1FUNCTION. P1GO checks to see that the GO is really in a PROG, then if the argument is not atomic it expands it in the usual way. P1LABEL turns the label statement into a PROG in which the function is bound as a prog variable. P1PROG first binds the PROG variables, then prepares a list of generated tags to be used in the LAP code. Finally it goes through exppanding each expression according to whether it is an atom or not. Atoms are left alone, while other expressions are processed in evaluation context. P1RETURN expands the argument of the return for evaluation, after checking to be sure the return is inside a PROG. P1SETQ expands its arguments differently. The second argument of the SETQ is expanded for evaluation while the first, being a variable, is simply checked against the tables. P1STORE is expanded specially. Its arguments are expanded for evaluation in reverse order. P1SUBRARGS expands each element in a list, checking that there not too many for the argument accumulors. PASS1 sets up all of the various tables which are used for the first pass to record its results, binds the variables, calls P1 etc. PASS1FSUBR expands a call to an FSUBR. It simply returns the expression unchanged. PASS1FUNVAR expands both the function part and the arguments. PASS1LSUBR expands each of the arguments without checking on their number. PASS1LAMDA expands the arguments, binds the variables and finally expands the body of an internal LAMBDA, after checking that the lambda expression has been given the correct number of arguments. PASS1MACRO expands an appeal to a macro by applying the macro definition to the entire expression and then expanding the result. PASS1SUBR expands each of the arguments, checking that there are no more arguments than available argument accumulators. PASS1UNDEF expands the expression like PASS1SUBR and adds it to the list of undefined functions. SPECIALP is a predicate asking if an identifier is a special variable. VARB processes a variable, asking whether it has been seen before and in what context. VARIABLEP asks if an expression is a legitimate variable, ie. an identifier and not a resurved constant. INTERNAL MACROS Several functions are logically treated as macros, though for reasons of speed it is desirable to have their macro definitions compiled, an option not offered in the basic Lisp system. The compiler therefore makes use of its own extensibility to add the new function type INMACRO. The several INMACRO definitions which follow are therefor compiled. It should be emphasized that in so doing the compiler is only mmaking use of compiler facilities of which any user program might have availed itself. The INMACROs are APPEND, LIST, NOT and ZEROP. Their definitions are precisely those which would be used to define ordinary macros to preform those functions. PASS1INMACRO is the function which expands INMACROS rather as PASS1MACRO expands macros. PASS2 ACEFFECTS Takes a function name as argument and returns a mask indicating which accumulators are damaged by the a call to the functon. ACNUMP is a predicate which indicates if a number is used to represent an accumualtor. BINDARGS takes a list of arguments to a function and makes entries in the ACS list to show which arguments are in which accumulators. BOOLAND carries out the compilatin of an AND, by calling BOOLARGS. BOOLARGS is the principal function used to compile booleans. It takes as agruments a list of expressions to be anded or ored and compiles them interspersed with appropriate jumps and tags. BOOLEQ compiles an EQ for value or boolean test, by compiling the arguments for value and generating a compare instruction. Several cases arise, depending on whether the arguments are already available as variables or are compiled to give temporary results. At least one of the arguments must be in an accumulator, and, before the comparte instruction is generated the stack must be restored in preparation for any jump which follows. BOOLEXPR finds and employs the appropriate function for compileing a given boolean. BOOLNULL compiles the function NULL, by simply reversing the test conditions. BOOLOR compiles OR by setting up an appropriate call to BOOLARGS. BOOLVALUE generates a T or NIL in a given accumualtor from a jump to a tag, by making the fall through give a nil and arrival at the tag give a T. The process of compiling a function call, with little regard for the function's type, can be divided into four parts. First the arguments must be compiled. Second, they must be loaded into the correct places. Third, any valuable data which are in vulnerable places must be moved to safe loacations. Last, the calling instruction can be output and the results marked in the storage map. CALLFSUBR generates a call to an FSUBR by placing the appropriatly quoted argument string in accumulator one, cleaning valuable items out of the accumulators, generating a call to the function and marking accumulator one as containing the result. CALLFUNARGS generates a call to a calculated function. First the function is calculated, then the arguments are compiled and loaded into the accumulators. Once this has been done, the function, which has been preserved through these events, is called in the usual way. CALLLSUBR This process differs slightly from the others, in that, as the arguments go on the stack, each argument is loaded right after it is compiled. All valuable data in the accunulators must therefore be saved before this process is begun. Once this is completed, the calling and marking are done as usual. CALLSUBR This is the fundamental function call operation. First, the arguments are compiled, without being loaded into specific locations. These results are marked as valuable by being placed on the LDLST, and the values of earlier arguments are preserved through the compilation of later ones. This is designed to save pushing and popping where possible. After the arguments have been compiled, they are loaded, in inverse order, into the appropriate accumulators. Next, a cleanup is done, in which valuable data remaining in the accumulators are pushed along with the values of any special variables whose current values will be needed later. The various functions whose names begin with CLEAR or CLR all are concerned with setting things to rigths in prepation for possible hazards. In general this means that partial results will be computed and saved in preparation for the destruction of the data on which they depend. Some of these functions are simply ad hoc combinations of others. CLEAR1 runs together the functions of CLRCCLST, SAVEACS and CLRPVARS. CLEARBOTH runs together CLRCCLST and CLRSPECS. CLEARAC pushes the contents of an accumulator and marks it as empty in the map. CLEARITALL runs together CLEARBOTH and CLEARACS. CLEARACS pushes all valuable items in the accumuators and marks them as empty in the map. CLRCCLST computes the values of items waiting to be loaded which are known to be cars or cdrs of other things. This may be necessary as a distinct operation to making copies of the original items since RPLACA and RPLACD operations may destroy the objects pointed to. CLRLOCS pushes copies of any local variables waiting to be loaded as function arguments. This is done prior to branching, since different assignments might be made to the variable on different branches. CLRPVARS initializes the PROG variables by pushing NILs on the stack. CLRSPECS pushes copies of any special variables waiting to be loaded as function arguments. This is necessary whenever a function is call whose effects on special variables are not known. CLRSPVAR pushes a copy of one special variable, if a copy is not already in the accumuulators or on the stack. COMPARGS compiles a list of function arguments without loading them. COMPEXPR compiles a form in expression context, ie. for value. COMPPRED compiles a form in predicate context, ie. to be tested for effect on the flow of control. COMPFORM is the central routine of the compiler. It is in charge of the compilation of all forms to be evaluated. COMPSTAT compiles a form in statement context, ie. for neither value nor effect on the flow of control, but only for side effects on variables or list structure. COPT attempts to optimize the computation of a car or cdr by looking to see if the result is already known. CPUSH guarantees that a copy of a valuable item is on the stack. It first checks to see if the item is valuable, if not it is ignored. Next, a check is made to see if the item is already on the stack. Third, CPUSH will look for a suitable place on the stack into which to move the item. As a last resort, it will push a copy onto the end of the stack. CSFUN is called by CLRCCLST to compile those cars and cars and cdrs whose values are not already available. CSTEP expands a car-cdr chain, using COPT at each step to determin if the sub-results are already present. DOP2BOOL manages the computation of a boolean expression in any context, first compiling it as a boolean for effects on control and then generating code to produce a value, if necessary. DOP2ELSE manages the compilation of those functions which may do one thing in predicate context and another in value context. DOP2VAL manages the compilation of functions which primarily produce values. DVP is a predicate which decides if an item is valuable. EQUIVTAG gives the lap tag corresponding to a prog tag. EXITBUM generates the code for a functin exit, trying to end with a jump instead of a call if possible. FREEAC finds a free accumulator when one is needed for a partial result. This function will forcefully clear an accumulator if it must. FREEAC1 does the work for freeac. Its arguments is the preferred accumulator. FINDFREEAC will find a free accumulator if there is one, but will not forcefully clear one. FREEZE removes from the storage map any references to the current value of a variable , and replaces them with reverences to the value at the time of the freeze. FREEZE1 is a subsidiary to freeze which acts on an individual piece of the storage map. GENCONST generates the Lap notation of a constant or literal word to be used in the address field of an instruction. GETSLOT takes as argument an number indicating a storage loaction in the accumulators or on the stack, and returns the appropriate piece of the map. ILOC is a functions which returns the location of an item if it is present in memory, or returns a NIL is the item must be computed. ILOC1 locates a item if possible, computing it if necessary. LISTNILS generates a list of NILs to intitialize the ACS list. LOADARG loads an item into an accumulator. LOADCARCDR generates code to calculate a car or cdr. LOADCOMP compiles a form and loads the result. LOADSUBRARGS loads a list of items into the appropriate accumulators to be arguments of a subr. LOC uses ILOC1 to locate an item. MARKVAL generates an item name, for a computed result and enters it in the storage map in the appropriate place. This item name is also entered on the LDLST, if necessary, to protect it. NONSPECVARS extracts from a list of variables the ones which are not special. OUT1 OUTCALL OUTCALLF OUTCJMP OUTENDTAG OUTFUNCALL OUTGOTAB OUTJCALL OUTJMP OUTJRST OUTMOVE OUTMOVEM OUTPOP OUTPUSH OUTPUTSTAT OUTSTAT P2*EVAL P2ARG P2CARCDR P2COND P2COND1 P2GO P2PROG P2PROG2 P2PROGN P2QUOTE P2RETURN P2RPLAC P2SETARG P2SETQ P2STORE PASS2 PASS2LAMBDA PROGTAG PROTECTACS PUTINAC REMOVE RESTORE RSLSET RST SAVEACS SETSLOT SHRINKPDL SIDEEFFECTS SLOTCONT SLOTLIST SLOTPOP SLOTPUSH SPECBIND SPECVARP TESTJUMP TRANSOUT USEDTAGP CMPBREAK COMPERR EVALREAD LAPNOTES USERERR ATMARGIN CARRETN CURCOL FORMF LINEF PRINL PRINS PRINTEXPR PRINTN PRINTSTAT TABTO ADDTOLIST ASSOCR CONSTANTP COPY DEINITSYM FSUBRP GETGET LSUBRP MAKESPECIAL MAKESYM MAKEUNSPECIAL NEXTSYM NTHCDR PROGN STARTSYM STOPSYM SUBRP TOPCOPY Brief Description of Compiler Global Variables ACS is a map of the contents of the accumualtors during the compilation. An entry in this may be NIL, or a doted pair. If it is NIL it indicates that nothing is known about the contents of the accumualtor If it is a dotted pair with null cdr then it is the current value of a variable. If its cdr is numeric, it represents the value of a variable at some previous "time". If its cdr is "DUP", it is a duplicate of the current value of a variable. If its cdr is "QT" then it is a quoted expression. If its cdr is "TAKEN" then it is an ad hoc value which cannot normally be moved, damaged or even seen. ALLACS is a default map with ones set in every position. It indicates that every argument accumulator is affected by a function call. ALLFUNS is a list of all the fuctions defined in the compilation of a file. ARRAYAC is the accumualtor which is used for the computation of the argument to the special array access routine. CCLST is a list of partial results which are cars or cdrs of variables. Each entry contains a name for a partial result, followed by a function name CAR, CDR, CADR etc. followed by the item to which this fucntion must be applied. CODESIZE is simply a count of how many words of code have been generated. CONSTSIZE is a count of how many constants have been generated. CTAG is a tag which is the exit to an n-tuple in a COND. In many cases such a tag will only be jumped to from one place, and cannot be dropped in to. In such cases CTAG helps to expedite this jump, avoiding the usual loss of knowledge or the acs which usually accompanies a jump. CURBIND is a list of the variables a a point in the computation which are currently bound by local lambdas or progs, along with the name by which they are being called. Variables are normally called by their own names, unless the same variable is bound twice in the function, in which case the second occurrence is sytematically renamed and the old and new names entered as a dotted pair on this list. EXIT is the tag which is the exit from a PROG. It is passed around free and used in the compilation of a cond to expedite the case of a conditional return. EXITN is the exit from a prog which returns NIL and is used similarly to EXIT. FARGAC is the ac used for the argument of an FSUBR or FEXPR. FOUNDFREE is a list of all variables found free in the expression being compiled. These are a subset of the special variables. FUNNAME is the name of the function being compiled. GENFUNS is a list of the names of the functions which have been generated from explicit lambda expressions used as arguments to the functions FUNCTION or *FUNCTION. GOLIST is a list associated with a prog of all tags and the equivalent tags to be used in the Lap output code. GOTABAC is the ac to be used for the arguments of computed GOs. INDEV is the default device from which the compilers input is to be taken. INPROG is a flag saying whether the expression currently being compiled is inside a prog. If this flag is not set a GO or RETURN will cause an error. LASTOUT is a one instruction output buffer. Instructions in this buffer are occasionally deleted or modified. LDLST is the list of items waiting to be loaded as arguments to functions. LINCNT is the number of lines which have been printed on the current page. LISTING is the name of a device to be used for the messages which would normally be sent to the console. LOCVARS is a list of all the local variables encountered in pass on, together with a notation of the count at which they were last seen. MINDEPTH is the shortest that the stack may be allowed to get in order that it may be restored to the length requred to jump to some tag. MSGCHAN is the channel used for the messages output by the compiler. NACS is the number of acs which may be used for function arguments. It is the length of ACS. OUTDEV is the device to which the compiler's output is directed. OUTEXT is the extension which will be added to the name of the input fill to get the name of the output file. P1CNT is the count kept in pass one. This count begins at one and is incremented each time any variable occurs. It is also incremented at selected places in functions which branch, though this may not be necessary. Since no two occurences of a variable may have the same count, the count may be used to refer to old values of variables. P2CNT is the count kept in pass two. It should at all points in the computation parallel the corresponding values of P1CNT. P1SCNT is a count saved in pass one at the beginning of functions, such as PROG, which destroy the partially ordered flow of control. After the funtion has been processed, the counts of all variables seen after P1SCNT are raised to the value of P1CNT at the end of the fucntion. PAGEHEIGHT is the height of pages on the current output device. PAGEWIDTH is the width of pages on the current output device. PDL is a map of the contents of the push down list. The possible entries in this list are described under ACS. PDLDEPTH is the current length of the PDL. PRGSPFLG is a flag indicating that a PROG binds special variables. PROGSW is a switch indicating that the variables of a PROG have yet to be put on the stack. This is part of a mechanism which attempts to optomise the code at the beginning of a PROG by not pushing NILS on the stack for variables which are set before they are referenced and before any branching occurs. PROGVARS is a list of those local variables of a prog which have not yet been given slots on the stack. This is part of the same optimizatin cited under PROGSW. PRSSL is a copy of the stack just after all of the prog variables have been pushed. PVR stands for the prog value register. This is the place in which the value of the current PROG will be returned. It is passed down free to the function which compiles return. RSL is a copy of the slotlist at the time a jump to CTAG was output. SHOWNAMES is a switch indicating that the name of each function the compiler processes should be typed on the message device. SPECVARS is a list of all special variables encountered in the fuction definition during pass one. TRACELIST is a list of expressions which will be evaluated each time an instruction is output and printed on the output listing. UNDFUNS is a list of all functions call before they are defined. VALUEAC is the ac in which the value of a function is returned. VARLIST is a list of partial results which have been found to be equal to others by being car and cdrs of the same things. This list is used to protect items which would normally have passed their usefulness. VGO is the tag which marks the begining of the despatch code for computed GOs. User Errors These are errors in source code which cause the compiler to halt. ARGNO-P1CONS CONS has the wrong number of arguments. ARGNOERR-BOOLEQ1 Wrong number of agruments to EQ. ARGNOERR-COMPDEF "DEFPROP" has the wrong number of arguments. ARGNOERR-INTERNALLAMBDA Differing numbers of variables and arguments. ARGNOERR-P2CARCDR Wrong number of arguments to CAR, CDR, CADR etc. ATOMICVARLIST-P1BIND An atom where a variable list was expected. CONSTFUN-P1 Attempt to call a constant(number, T or NIL) as a function. EXTRAARGS-P1SUBRARGS EXPR or SUBR called with too many arguments. EXTRAARGS-PASS1 Attempt to define a SUBR or EXPR with too many arguments. NOTINPROG-P1GO GO occurring outside of PROG. NOTINPROG-P1RETURN RETURN occurring outside of PROG. NOTVARIABLE-P1BIND A constant or non-atom in variable context. NOTVARIABLE-P1SETQ Attempt to SETQ a constant or non-atom. PROGTOOSHORT-P1PROG PROG must at least have a variable list. READERR-FLUSHLAP Read error while reading LAP in source file. TOFEWARGS-P2PROG2 User Warnings These messages indicate that the compiler thinks there might have been an error. They do not interrupt compilation, but indicate conditions which can be expected to produce errors in object code. REPEATED VARIABLE Variable name repeated in a variable list. MULTIPLY DEFINED TAG Two PROG tags with same name. UNUSED PROG VARIABLE Some PROG variable not referenced. UNDECLARED FREE VARIABLES Variables found free in source code. UNDEFINED TAG Undefined PROG tag. Other Compiler Messages FSUBR USED AS SUBR A function previously called and presumed to be a SUBR has been defined to be an FSUBR. LSUBR USED AS SUBR A function previously called and presumed to be a SUBR has been defined to be an LSUBR. MACRO USED AS SUBR A function previously called and presumed to be a SUBR has been defined to be an MACRO. (name . flag) USED AS SUBR Same as above, except that the function has been defined by LAP in source file. var LOCAL AND SPECIAL A variable compiled as local in an earlier function is found free or declared special. The compiler is worried that they might be the same variable. Compiler Errors These are errors in the compiler itself. It halts and goes into a read eval print loop without unbinding the variables to facilitate debugging. ATOM-NTHCDR COUNTSDISAGREE-COMPFUNC FUNNYVAR-BINDVARS LDLSTLEFT-PASS2 LOSTVAR-ILOC1 NEGNUM-NTHCDR NIL-RST NOAC-RESTORE NOTAC-GETSLOT NOTLAMBDA-GENFUN NOTONPDL-GETSLOT NOTSLOT-GETSLOT NULLLOC-MARKVAL PDLSHORT-RESTORE PDLTOOLONG-LSUBRCALL SOMETHINGELSE-P2ELSE In considering the correctness of a LISP compiler, the question arises of whether its domain of operation is appropriate peices of list structure or the corresponding S-expressions which represent them. The latter point of view is by far the more common, but if the language is viewed as being defined by its interpreter, then the former view is preferable. This, however, gives rise to certain difficulties. Concider the following definition of factorial, represented by a modified S-expression in which the arrows represent the circularity in the list structure. (LAMBDA (NUMBER) (PROG (PRODUCT) (SETQ PRODUCT 1) →→→(COND ((ZEROP NUMBER) (RETURN PRODUCT))) ^ (SETQ PRODUCT (TIMES NUMBER PRODUCT)) ^ (SETQ NUMBER (SUB1 NUMBER)) ^←←←)) This definition is correctly interpreted and gives `NUMBER!' as value. Naturally a two pass compiler when presented with this structure never completes its first pass. A one pass compiler, however, gives more interesting results. It produces the following infinite sequence of machine instructions which are in a natural sense a compilation of the input. (LAP FACTORIAL SUBR) (PUSH P 1) (PUSH P (C 0 0 (QUOTE 1) 0)) (CALL 1 (E ZEROP)) (JUMPE 1 G0005) (MOVE 1 0 P) (JRST 0 G0001) G0005 (MOVE 2 -1 P) (MOVE 1 0 P) (CALL 2 (E *TIMES)) (MOVEM 1 0 P) (MOVE 1 -1 P) (CALL 1 (E SUB1)) (MOVEM 1 -1 P) (CALL 1 (E ZEROP)) (JUMPE 1 G0010) (MOVE 1 0 P) (JRST 0 G0001) G0010 (MOVE 2 -1 P) ...ETC... The compiler's attempts at optimization have added to the primary inconvenience that the code is infinite a second form of infinity problem. The program has a point at infinity represented by the tag `G0001' which would better have been called `Omega.' This, however, can be remedied by a small adjustment to the compiler, which then produces the following code. (LAP FACTORIAL SUBR) (PUSH P 1) (PUSH P (C 0 0 (QUOTE 1) 0)) (CALL 1 (E ZEROP)) (JUMPE 1 G0005) (MOVE 1 0 P) (SUB P (C 0 0 2 2)) (POPJ P) G0005 (MOVE 2 -1 P) (MOVE 1 0 P) (CALL 2 (E *TIMES)) (MOVEM 1 0 P) (MOVE 1 -1 P) (CALL 1 (E SUB1)) (MOVEM 1 -1 P) (CALL 1 (E ZEROP)) (JUMPE 1 G0010) (MOVE 1 0 P) (SUB P (C 0 0 2 2)) (POPJ P) G0010 (MOVE 2 -1 P) ...ETC...