perm filename COMPLR.NOT[CMP,LSP] blob sn#217936
filedate 1976-05-23 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00026 PAGES
C REC PAGE DESCRIPTION
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
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
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.
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 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
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.
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
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
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
PROPNAM takes a property as an argument and returns the name
of the property.
PROPTABLE takes an identifier as argument and returns the
PROPVAL takes a property and returns the value part of the
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
SETPROP takes an identifier, a property name and a value and
sets that property to the value.
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
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
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
FLUSHLAP prints out LAP definitions in files being compiled.
MAKDEF produces a DEFPROP expression from its arguments to hand to
MAPPUT puts a property onto a list of atoms.
PRINTMSG prints a message on the listing device for error messages
READLOOP reads and applies a functional argument to each
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
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.
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
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
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
PASS1FSUBR expands a call to an FSUBR. It simply returns the
PASS1FUNVAR expands both the function part and the arguments.
PASS1LSUBR expands each of the arguments without checking on
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
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.
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.
ACEFFECTS Takes a function name as argument and returns a
mask indicating which accumulators are damaged by the a call to the
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
BOOLAND carries out the compilatin of an AND, by calling
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
BOOLOR compiles OR by setting up an appropriate call to
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
CLEAR1 runs together the functions of CLRCCLST, SAVEACS and
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
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
CLRPVARS initializes the PROG variables by pushing NILs on
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
COMPEXPR compiles a form in expression context, ie. for
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
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
FREEAC1 does the work for freeac. Its arguments is the
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
ILOC1 locates a item if possible, computing it if necessary.
LISTNILS generates a list of NILs to intitialize the ACS
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.
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
ALLFUNS is a list of all the fuctions defined in the compilation of a
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
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
EXITN is the exit from a prog which returns NIL and is used similarly
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
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
LINCNT is the number of lines which have been printed on the current
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
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
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
VGO is the tag which marks the begining of the despatch code for
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.
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.
These are errors in the compiler itself. It halts and goes into
a read eval print loop without unbinding the variables to facilitate
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
Concider the following definition of factorial, represented by a
modified S-expression in which the arrows represent the circularity in the list
(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)
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))
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))
G0010 (MOVE 2 -1 P)