perm filename COMPLR.NOT[CMP,LSP] blob sn#217936 filedate 1976-05-23 generic text, type C, neo UTF8
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
	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.

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


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

	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
been taken.

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

	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

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

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

	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
test conditions.

	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
of others.

	CLEAR1  runs  together the functions of CLRCCLST, SAVEACS and


	CLEARAC pushes the contents of an accumulator and marks it as
empty in the map.


	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

	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

	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

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

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


				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

















	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

			      (SETQ PRODUCT 1)

	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.

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

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