The LISP Compiler is a program written in LISP that translates S-expression definitions of functions into machine language subroutines. It is an optional feature that makes programs run many times faster than they would if they were to be interpreted at run time by the interpreter.
When the compiler is called upon to compile a function, it looks for an EXPR or FEXPR on the property list of the function name. The compiler then translates this S-expression into an S-expression that represents a subroutine in the LISP Assembly Language (LAP). LAP then proceeds to assemble this program into binary program space. Thus an EXPR, or an FEXPR, has been changed to a SUBR or an FSUBR, respectively.
Experience has shown that compiled programs run anywhere from 10 to 100 times as fast as interpreted programs, the time depending upon the nature of the program. Compiled programs are also more economical with memory than their corresponding S-expressions, taking only from 50 per cent to 80 per cent as much space.(1)
The major part of the compiler is a translator or function from the S-expression function notation into the assembly language, LAP. The only reasons why the compiler is regarded as a pseudo-function are that it calls LAP, and it removes EXPR's and FEXPR's when it has finished compiling.
The compiler has an interesting and perhaps unique history. It was developed in the following steps:
1. The compiler was written and debugged as a LISP program consisting of a set of S-expression definitions of functions. Any future change or correction to the compiler must start with these definitions; therefore they are included in the LISP Library.
2. The compiler was commanded to compile itself. This operation is called bootstrapping. It takes more than 5 minutes on the IBM 7090 computer to do this, since most parts of the compiler are being interpreted during most of this time.
3. To avoid having to repeat the slow bootstrapping operation each time a system tape is created, the entire compiler was punched out in assembly language by using punchlap.
4. When a system tape is to be made, the compiler in assembly language is read in by using readlap.
The compiler is called by using the pseudo-function compile. The argument of compile is a list of the names of functions to be compiled. Each atomic symbol on this list should have either an EXPR or an FEXPR on its property list before being compiled.
The processing of each function occurs in three steps. First, the S-expression for the function is translated into assembly language. If no S-expression is found, then the compiler will print this fact and proceed with the next function. Second, the assembly
________________________________________
1. Since the compiled program is placed in binary program space,
which is normally not otherwise accessible, one gains as free
storage the total space formerly occupied by the S-expression
definition.
language program is assembled by LAP. Finally, if no error has occurred, then the EXPR or FEXPR is removed from the property list. When certain errors caused by undeclared free variables occur, the compiler will print a diagnostic and continue. This diagnostic will be spuriously produced when programs leaning on APVALs are compiled.
When writing a large LISP program, it is better to debug the individual function defi nitions by using the interpreter, and compile them only when they are known to work.
Persons planning to use the compiler should note the following points:
1. It is not necessary to compile all of the functions that are used in a particular run. The interpreter is designed to link with compiled functions. Compiled functions that use interpreted functions will call the interpreter to evaluate these at run time.
2. The order in which functions are compiled is of no significance. It is not even necessary to have all of the functions defined until they are actually used at run time. (Special forms are an exception to this rule. They must be defined before any function that calls them is compiled.)
3. If the form LABEL is used dynamically, the resulting function will not compile properly.
4. Free variables in compiled functions must be declared before the function is compiled. This is discussed at length in this appendix.
Excise
The compiler and the assembler LAP can be removed from the system by using the pseudo-function excise. If excise [NIL] is executed, then the compiler will be removed. If excise [*T*] is executed, then the compiler and LAP will both be excised. One may execute excise [NIL] and then excise [*T*] at a later time. When a portion of the system is excised, the region of memory that it occupied is converted into additional free-storage space.
Free Variables
A variable is bound in a particular function when it occurs in a list of bound variables following the word LAMBDA or PROG. Any variable that is not bound is free.
Example
(LAMBDA (A) (PROG (B)
S (SETQ B A)
(COND ((NULL B) (RETURN C)))
(SETQ C (CONS (CAR A) C))
(GO S) ))
A and B are bound variables, C is a free variable.
When a variable is used free, it must have been bound by a higher level function. If a program is being run interpretively, and a free variable is used without having bee bound on a higher level, error diagnostic *A 8* will occur.
If the program is being run complied, the diagnostic may not occur, and the variable may have value NIL.
There are three types of variables in compiled functions: ordinary variables, SPECIAL variables, and COMMON variables. SPECIAL and COMMON variables must be declared before compiling. Any variable that is not declared will be considered an ordinary variable.
When functions are translated into subroutines, the concept of a variable is translated into a location where an argument is stored. If the variable is an ordinary one, then a storage location for it is set up on the push-down list. Other functions cannot find this private cell, making it impossible to use it as a free variable.
SPECIAL variables have the indicator SPECIAL on their property lists. Following the indicator there is a pointer to a fixed cell. When this variable is bound, the old value is saved on the push-down list, and the current value is stored in the SPECIAL cell. When it is no longer bound, the old value must be restored. When a function uses this variable free, then the quantity in the SPECIAL cell is picked up.
SPECIAL variables are declared by using the pseudo-function special[a], where a is a list of variable names. This sets up the SPECIAL indicator and creates a SPECIAL cell. Both the indicator and the cell can be removed by the pseudo-function unspecial[a], where a is a list of variable names. It is important that the declaration be in effect at compile time. It may be removed at run time.
The compiler refers to SPECIAL cells, using the LAP field (SPECIAL X) whose value is the address of the SPECIAL cell. When a variable has been declared, removed, and then declared again, a new cell is created and is actually a different variable.
SPECIAL variables are inexpensive and will allow free communication among compiled functions. They do not increase run time significantly. SPECIAL variables cannot be communicated between the interpreter and compiled functions.
COMMON variables have the flag COMMON on their property lists; however, this is only used to inform the compiler that they are COMMON, and is not needed at run time. COMMON variables are bound on an a-list by the compiled functions. When they are to be evaluated, eval is given this a-list. This happens at run time.
The use of COMMON variables will slow down any compiled function using them. However, they do provide complete communication between interpreted and compiled functions.
COMMON variables are declared by common[a], where a is a list of variable names. The declaration can be removed by uncommon[a], where a is a list of variable names.
Functional Constants
Consider the following definition of a function ydot by using an S-expression:
(YDOT (LAMBDA (X Y) (MAPLIST X (FUNCTION
(LAMBDA (J) (CONS (CAR J) Y)) ))))
ydot[(A B C D);X]=[((A . X) (B . X) (C . X) (D . X))]
Following the word FUNCTION is a functional constant. If we consider it as a separate function, it is evident that it contains a bound variable "J", and a free variable "Y". This free variable must be declared SPECIAL or COMMON, even though it is bound in YDOT.
Functional Arguments
MAPLIST can be defined in S-expressions as follows
(MAPLIST (LAMBDA (L FN) (COND
((NULL L) NIL)
(T (CONS (FN L) (MAPLIST (CDR L) FN))) )))
The variable FN is used to bind a functional argument. That is, the value of FN is a function definition. This type of variable must be declared COMMON.
Link
Link is the routine that creates all linkage of compiled functions at run time. The normal procedure for calling a compiled function is to place the arguments in the AC, MQ, $ARG3, ...and then to TSX FN,4. However, the first time any call is executed, there will be an STR in place of the TSX. The address and the decrement of the STR specify the name of the function that is being called, and the number of arguments that are being transmitted, respectively. The tag contains a 7. If there is no SUBR or FSUBR for the function that is being called, then link will call the interpreter that may find an EXPR or FEXPR. If there is a subroutine available, then link will form the instruction TSX and plant this on top of the STR.
Tracing Compiled Functions
trace will work for complied functions, subject to the following restrictions.
1. The trace must be declared after the function has been complied.
2. Once a direct TSX link is made, this particular calling point will not be traced. (Link will not make a TSX as long as the called function is being traced.)