." franz.n -[Thu Jun 17 11:01:27 1982 by jkf]-
." this file will contain a description of the franz lisp system.
." sort of a systems manual.
\fBThe Franz Lisp System\fP
This document describes the
system written at The University of California
Included are descriptions of the memory management, interpreter
and compiler, the conventions used within the C coded kernel
and those within the compiled code.
This does not duplicate the information found in The Franz Lisp Manual.
.++ C '\s-2Draft\s+2'\fBThe\ Franz\ Lisp\ System\fP'%'
.+c Characteristics\ of\ \F\s-2RANZ\ \s0L\s-2ISP\s0
There is no formal standard for lisp systems, thus each lisp
system is almost guaranteed to be different from any other lisp system.
In this section we will examine the design decisions which most often
characterize a lisp system.
focus does not imply that all other parts of the language are generally
In fact, there is nothing sacred to lisp system designers.
For example, one usually identifies the symbol
and one usually thinks of lisp as a dynamically scoped language.
Both of these conventions are are not true in the lisp dialect
currently being written at MIT.
As another example, one imagines that a lisp system must
use garbage collection to reclaim storage.
that is running on Lisp Machines doesn't
normally use a garbage collector
because of the way in which it allocates its address space.
It is faster to reboot the machine than to do a garbage collection.
In most lisp dialects the lisp expressions are written in
(PSL) at the University of Utah, programs are written
Thus some of the discussion to follow indicates not so much
but instead, how decisions were made.
.sh 2 Scoping\ and\ Binding
that is, after A calls B, B can access all of the
variables that A allocated
as those that A can access, provided B doesn't allocate variables of the same
There are two popular ways of implementing dynamic scoping:
Note that we will use the terms variable allocation and lambda
binding interchangeably in this report.
The former term is less language-specific than the latter.
In a deep binding implementation, when a variable is allocated,
the name of the variable and a space for its value are pushed on the
When a program asks for the value of a variable,
the lisp system must search down the stack for the first occurrence of
This system offers great flexibility for the
programmer since the state of his program
can be described by the contents of the stack.
It is thus possible to save the context of a program by just saving
the stack or in some cases just a pointer to
The problem with deep binding is that it is time-consuming to search
down the stack for the value of a variable, and,
as a result, most systems
modify the deep binding model by giving variables a global value
cell and allowing programs to set and access the global cell.
Some implementations of Interlisp use deep binding.
In a shallow binding implementation, each variable has a global value cell
which contains the current value of the variable.
When a variable is allocated inside a program, its name
and old value are pushed on a stack called a
The variable is then given a new value.
Throughout the lifetime of the allocation, the current value of the
variable can be found in the global value cell associated with the variable.
When leaving the context of the variable's allocation, the old value
A shallow binding scheme makes it much cheaper to access
the values of variables, however it is much more difficult to
save the state and to restore it.
and most other lisps which are not derived from Interlisp
Some versions of Interlisp use shallow binding.
Dynamic scoping often is not necessary and it is never cheap, even
in a shallow binding implementation.
compiler prefers to do lexical scoping rather than dynamic
If the user does not specify otherwise, when a
function is compiled, all variables
put on a local stack and will
function that this function calls.
convention results in faster code being generated by
user is not careful, it can result in compiled and interpreted code
In some of the new lisp designs, such as
the semantics of compiled and interpreted code have been
transferring the compiler semantics (lexical scoping) to the interpreter.
This is a rather large step
longer an option, and it is not clear whether the resulting
language should be called 'lisp'.
A complete list of data types in
can be found in the first chapter of the
The most important ones are described below.
Lisp is a list processing language and the basic data type is the list
A list cell also goes by the name of cons cell, pair, or dotted pair (dtpr).
It contains pointers to two lisp objects, and these pointers can
Each pointer requires four (8-bit) bytes and thus the list cell is
The cdr pointer is stored first since this makes it easier
to 'cdr down a list' using the addressing modes of the VAX.
The symbol cell is used to implement variables. It contains a pointer
to a string that is the print name, a cell to store a value, a cell to
store the function definition, a cell to store a pointer to the property
list and one pointer that the list system uses if it stores
the symbol in the oblist.
.sh +0 Memory\ Management
A lisp system must be able to determine the type of an
The method used to determine the type influences the
way storage is managed and garbage collection is done.
Next, we will look at three possible places
to store the type information.
The type of the data object could be placed in the object itself, much
as Pascal stores the type of a variant record in the record itself.
This could result is a large amount of storage being used to store
No lisp system that we know of uses this method exclusively.
Every reference to a lisp object could contain the type of the object
This is a good idea in a machine like an IBM 370 where only
part of machine word is used by the addressing hardware.
Lisps that use typed pointers generally use a
memory management scheme and a
all memory is divided by a pointer (called the
heap pointer) separating lisp
When a new lisp object is needed, it is formed at the
the heap pointer is incremented
Garbage collection is done by maintaining two separate spaces for lisp
data, only one of which is used at any one time.
When one fills up, all active lisp objects are copied to the
other space, leaving the first space totally free.
Subsequent allocations are done from the second space, until it fills up,
all active data in the second space is copied to the first space.
The advantage of the copying garbage collector is that the data space
is compacted, which will improve virtual memory behavior.
half the data space is always unused.
PSL on a PDP-10 uses this scheme, as does Lisp 370 on
PSL and NIL on the VAX will also use this scheme.
uses the entire word for address
must mask off the type bits
of a pointer before using it to reference memory.
The final alternative is to allocate data objects by pages rather than
Each page contains only one type of object and there is a table that
keeps track of the type of data object in each page.
The address of an object tells which page the object is on and
the page number tells which type the object is.
Since a whole page of objects is allocated when only one
the rest of the objects in the page are put on a free list.
This method of allocation is sometimes referred to as
The garbage collector for bibop is usually
All active data objects are marked and
then each page is swept linearly with
the free cells being put on the free list and the used cells
The advantage of mark and sweep over a copying garbage collector is that
the mark phase is cheaper because data objects do not have to be copied.
Also, all of memory can be used since there is no requirement for two spaces.
The disadvantage is that a sweep phase is required in a mark and sweep
but one is not required in a copying garbage collector.
The sweep phase is expensive because it has to alter most data pages
while building a free list.
can be expensive in a virtual memory environment.
Alternatives to the sweep phase have been proposed in
[Foderaro+Fateman Characterization of Vax Macsyma].
uses a bibop memory allocator and a mark and sweep garbage collector,
as does Maclisp (on a PDP-10).
uses bibop is primarily due to the VAX architecture,
which makes typed pointers
Also, typed pointers would make it difficult to pass lisp values
to programs written in other languages, some of which may not have
the ability to extract the address of a lisp object from a typed pointer.
system is built by adding lisp code to a C-coded kernel.
The C-coded kernel is a working lisp interpreter, although it has few of
the functions a lisp system needs.
The lisp code provides most of the functions, the top level and error
The lisp compiler is also written in lisp,
run as a separate process.
can dynamically load and execute functions defined in the other languages
It uses two different dynamic loaders.
One is part of the lisp system and is used for lisp only, it is called
The other is the Unix loader, ld, which is used for loading in
C, Fortran or Pascal code.
is much faster than with ld
the simplicity of a lisp object file.
In this chapter we shall examine the data structures which are most
First, though we will see how the lisp system uses the address space.
As a Unix process, lisp has three address regions: text, data and stack.
Text begins at location 0 and continues up to 0x3b73c (0x means hex number).
The data segment begins on the next page boundary and continues
up to a limit set by the configuration parameters (currently 0x2fd000).
Lisp does not begin running with such a large data segment, rather it grows
The stack segment begins at address 0x7fffffff and grows downward to a
maximum size of one-half megabyte.
The text segment stores the instructions for the C kernel as well as read-only
The read-only data for lisp are
the symbol nil, the i/o ports, and the small integer
The symbol nil is stored at location 0 which makes it very easy to test
The problem with storing nil in read-only space is that a special case
must be made for nil's property list, which is the only thing in the
nil symbol that the user is permitted to alter.
The fixnums -1024 through 1023 are stored sequentially, with 0 being
doesn't have any 'immediate' lisp data, that is data whose value is
stored as part of the reference to the data.
But, by storing some of the fixnums in a known place, we can achieve
some of the benefits of immediate data:
as a test for a fixnum in the range -1024 to 1023.
In the majority of cases, when asked
to allocate a fixnum, the system can return a pointer into this table
and bypass the memory allocator.
uses the typed pages (or bibop)
method of type determination.
This table describes the type of all pages, from page 0 where nil is stored,
up to the end of data space.
Thus there are many entries that describe the types of the pages which
In order to reduce the wasted space in the typetable,
we could have made the typetable begin typing pages at the start of data
space and make a special case of the pages that contain nil and
effect of this change would be that type checks
(which are done in-line in compiled code) would
be longer and slower. Since type checking happens quite
frequently, we felt it was better to waste the space in the
typetable in order to save execution time and instruction space.
Each page on a VAX is 512 bytes, and thus to find the type of an
object given the address of it,
it is only necessary to shift the address right 9 bits
and index the typetable array offset by one.
The offset by one is required because the value -4, which is an illegal
address, is used as a sentinel value to indicate an illegal value.
Thus when we take the type of -4 we will be indexing the table by -1
and we want to retrieve the first byte in the table (which contains
The C macro which retrieves the type is this (from file h/global.h):
#define TYPE(a1) ((typetable+1)[(int)(a1) >> 9])
This is code generated by the lisp compiler to check if the type
code of an argument (stored at 0(r10)) is a symbol (which is type
The type codes which are stored in the typetable are these:
UNBO -1\tSTRNG 0\tATOM 1\tINT 2
DTPR 3\tDOUB 4\tBCD 5\tPORT 6
ARRAY 7\tOTHER 8\tSDOT 9\tVALUE 10
HUNK2 11\tHUNK4 12\tHUNK8 13\tHUNK16 14
HUNK32 15\tHUNK64 16\tHUNK128 17
The names given above are the C kernel internal names.
ATOM is symbol, INT is fixnum, DTPR is list cell,
DOUB is flonum, BCD is binary,
SDOT is bignum and all the HUNKn types are just known as hunk to
The C runtime stack is the stack part of the address space
and the other two stacks are stored in the data space.
The C-coded kernel uses this
stack in the same way as a typical C program
and non-lisp-object arguments to subroutines,
and storing local variables within a function.
on this stack as well (to be described later).
The lisp system assumes that there are no lisp data on the stack and
thus the use of this stack
by a program is unrestricted.
As will be discussed later on, the
instructions are used for most subroutine calls and returns.
These instructions expect the stack to look a certain way.
The namestack contains only lisp data.
It is used to pass arguments to functions and to hold
local (lexically scoped) data within lisp functions.
It is also used as a temporary storage spot for lisp data
which must be protected from garbage collection.
A slight digression on the garbage collector:
The person who writes code for the lisp system must always be aware of
his greatest enemy: the garbage collector.
Whenever a function is called that could possibly allocate more lisp
data, one must assume that it
when it attempts to allocate space, the garbage collector
will be invoked and that it will take away everything that isn't protected
The objects that are protected from garbage collection are: the
namestack, the bindstack, the oblist (table of interned symbols),
and the compiler literals. Objects that are only
referred to by values in registers or
the C runtime stack will not be seen by the mark phase of the
garbage collector and will be swept up during the sweep phase.
The first free element on the namestack is pointed to by the
This variable is always stored in the VAX register r6.
Another pointer into the namestack is the C variable
It is always stored in VAX register r7.
Its use will be described in the section on calling conventions.
The bindstack is a stack of lisp object pairs: symbol and
It is used to implement shallow binding.
When a symbol is lambda-bound, the symbol and its current value are put
Then the symbol can be given a new value.
When the context of the lambda binding is over, the symbol and value pair
are popped from the stack and the symbol is given its old value.
points to the first free entry on the bindstack.
In the C code, the following macros lambda-bind a symbol to a value
and restore the old value:
#define PUSHDOWN(atom,value)\e
bnp++->val=(atom)->a.clb;\e
if(bnp>bnplim) binderr();}
{--bnp; bnp->atm->a.clb=bnp->val;}
The bitmap is used in garbage collection to hold
the mark bits for the mark and sweep garbage collector.
As its names implies, it is viewed as a collection of bits.
The minimum size of a lisp data object is 4 bytes, thus
there are 128 of those on a VAX page of 512 bytes.
Since there are 8 bits in a byte, it takes 16 bytes to obtain 128 bits.
Therefore the size of the bitmap in bytes is 16
times the maximum number of
Like the typetable, the bitmap keeps track of marks from the
bottom of memory, not the bottom of data space.
The bitmap and the typetable are static structures.
It is their size, which is determined when the C kernel is built,
which determines the size to which the data segment can grow.
Transfer tables are used by compiled lisp code as a transfer vector to
A transfer table consists of pairs of entries: symbol and pointer to
When a compiled lisp function calls another (non-local) function, it
calls indirectly through an entry in the transfer table.
Depending on the setting of certain status variables, the call may
bring control into a function linkage routine or directly to
the function desired (if that function is a compiled lisp or C function).
Transfer tables serve a number of useful purposes.
They allow compiled code to call interpreted code
or compiled code using the same calling sequence.
They allow the selection of which function to call to be determined
at runtime based on the name of the function.
In most other languages, this selection process is done at either
They allow the user to run in a debugging mode where all calls
from compiled code go through the interpreter.
Once control reaches the interpreter, it is easier to debug.
They allow the user to run in a production mode, where all calls
from compiled to other compiled code are done without function
They allow the user to switch between debugging and production modes
at runtime with one function call.
Transfer tables will be described further in the section on
Lisp has a number of forms of non-local transfers.
If a program is willing to accept a non-local transfer, it puts a
on the stack which describes which type of transfer it
The catch frame describes the current state of the registers,
the variables np, lbot, and bnp, and also contains entries that describe
what kinds of non-local transfers the function will accept.
After creating a catch frame, the program goes on to evaluate forms.
Should the evaluation of one of those forms result in a non-local
transfer to the catch frame that this program has set up, the
system will restore the namestack and bindstack to the way
they were when the program put the catch frame on the stack (by using
np and bnp) and will return control to the program (setting
the variable retval to describe why it returned).
This is described further in the
section on interpreter conventions.
points to the most recent catch frame, and then each catch frame points
to the previous catch frame.
Normally when symbols are created they are
that is they are put in a hash table called an oblist (or obarray).
The purpose of the oblist is to insure that if you type a
symbol's name to the reader, you will always get the same symbol.
Also it protects the symbol from garbage collection.
The oblist is simply a hash table with buckets, with a hash link being
part of the symbol data structure.
Currently the hash table is not accessible to a lisp program, but with
a little work it could be.
The interpreter is composed of these parts:
The functions eval, apply and funcall.
.ip \fIstack\ management:\fP
The code to create catch frames and handle non-local transfers.
.ip \fImemory\ management:\fP
The code to allocate and garbage collect memory.
.ip \fIthe\ functions:\fP
The user callable functions that expect lisp arguments and return
In the above list, the first three are written mainly in C (with a little
assembler) and the last is written mainly in Lisp with a little
and a very small amount in assembler.
The core functions are the center of activity in the interpreter.
function given a lisp expression to evaluate.
It must determine if it is a simple expression such as a symbol or number
whose value eval can determine immediately, or if it is an function
If the form is a function call, eval must determine if the arguments should
be evaluated and if so eval must recursively call itself to evaluate the
arguments and then stack them.
If the function called is to be interpreted, eval must lambda-bind the
formal variables of the function to the arguments just stacked.
If the function being called is compiled, eval just calls the function and
lets the function do the lambda binding if it wants to.
function is passed two lisp objects:
a function to call (either a symbol or a functional object)
and a list of arguments already evaluated.
It will do lambda binding if the function to call is to
function is passed any number of lisp objects,
the first of which is the function to call, and the rest are the
arguments to the function
which have already been evaluated and stacked.
Funcall will do lambda binding if the function to call is
When compiled lisp code calls a function
which must be interpreted, it enters the interpreter through the
The interpreter may go to compiled code through either eval, apply or
funcall, though most often it goes through eval.
These are the conventions used in interpreted and compiled code.
Our conventions are extensions of the C calling conventions, so we
describe here the conventions for C.
Registers r12 through r15 are reserved
for use by the hardware because we use the
Registers r0-r5 can be used by a program without saving them first.
The result of a function call is returned in r0.
Registers r11-r6 are allocated (from high to low)
declaration is made in the C code.
saved upon entry and restored upon exit if they are used within a function.
On the VAX it is very easy to preserve registers
since it is done automatically
The first short word (two bytes) of a subroutine is a
tells which registers should be saved (on the C runtime stack) upon
entry and restored when a
Earlier we mentioned that the C variables np and lbot are
It is very difficult to globally assign a variable to a register
in the C language (no external register declarations
and thus we have to filter
the output of the C compiler and convert all occurrences of 'np' to 'r6'
and all occurrences of 'lbot' to 'r7'.
This is only half the job, though.
We also must modify the register save masks for those routines which
alter the value of np or lbot to insure that those registers get
saved and restored upon function entry and exit.
This is done in the C code by putting
at the beginning of a routine which will alter np or lbot and which
also allocates n register variables.
Also in that routine, before the function returns, we put
This is not really necessary in the VAX, but it is there for other
machine implementations which don't have a
function which restores registers.
The calls to Savestack are recognized by a filter which processes
of the C compiler and fixes up
The following text describes what the conventions are for
compiled lisp functions, whether they were written in lisp or C.
We look at it from the viewpoint of the called function.
lbot points to the first argument and np points to the
first free spot on the namestack.
If np equals lbot then there are no arguments.
Recall that np will be in r6 and lbot in r7.
The function is free to alter registers r0 through r5 and should return
The function may alter registers r6 through r11 as long as their
are restored when the function returns.
The value of np should always
point to the first free entry in the namestack.
This is all that is required.
The extra conventions followed by
in the code it generates are described in the next chapter.
A catch frame saves the state of execution that a program
might want to return to at some later time.
A catch frame is stored on the C runtime stack, with the most recent
frame pointed to by the C global variable errp.
- one or two optional arguments. The lisp compiler always
arguments since it must know exactly how large the frame is.
- the class describes what type of frame this is (described below).
- address to return to if returning from this frame
- pointer to next older catch frame on the stack
- value of bnp (bindstack pointer) when the frame was created
- value of np when the frame was created
- value of lbot when the frame was created.
.ip \fIsystem\ dependent\fP
- the rest of the information stacked depends on the particular machine.
In the case of the VAX, registers r13 through r8 are stacked. (r14 and
r15 are the stack pointer and program counter; they are not saved since
they can be calculated from the other information).
The information in a catch frame is put on the C runtime stack
in the precise order given above, and the variable errp points not
at the beginning of the entire frame, but to the lbot entry.
Thus errp\ +\ 4 points to np.
The classes of frames are described below.
Each class is defined as a constant in the C code (h/frame.h) whose value
- takes no arguments. This frame marks the beginning of a piece of
The interpreter uses this to implement
and for its primative break loop.
The lisp compiler does not use catch frames for progs since it only
and thus it can determine how to do the non-local transfer
- this takes one or two arguments and is used to implement both
the first argument is the tag which is being caught,
supplies a second argument which is non nil if the error message
- in the C kernel, the reset function
is implemented as a non local transfer to a F_RESET catchframe.
When the lisp system is built, the reset function is redefined to
Thus this type of catch frame is rarely used.
- this has one argument, the form being evaluated.
on every eval would be expensive,
this type of catch frame is only stacked if a \fI(*rset\ t)\fP
has been done and if the value of the symbol
The form being evaluated is stacked so that
the necessary information for the
function is available and so that
can return from the context of any pending evaluation.
- this is much like F_EVAL,
except the one argument it takes is the
name of the function to call.
It has the same restrictions on when it is stacked as F_EVAL
and for the same reasons.
In C, a frame is pushed on the stack with Pushframe, with a call
errp = Pushframe(class,arg1);
errp = Pushframe(class,arg1,arg2);
After the call the C variable
contains the value which describes why this function returned.
You must remember that it is possible for this one function call to
The reasons it can return are these (from h/frame.h):
This is the initial call to set up the frame.
This will only happen for F_PROG frames.
the C variable lispretval contains a lisp symbol which is the tag
to which control should be transferred.
If the tag cannot be found in this prog or do body, the
tag should be again thrown up the stack to a next higher prog or do.
This will only happen for F_PROG frames.
In this case, lispretval contains the value to return from this prog.
This will only happen for F_CATCH frames.
In this case lispretval contains the value to return from this catch.
This will only happen for F_RESET frames.
It simply means that a reset is being done.
This will only happen for F_EVAL and F_FRETURN frames.
The variable lispretval contains the value to return from this
The call to Pushframe is turned into a simple subroutine call (using
instruction instead of the
by the filters which alter the code coming out of the C compiler.
Thus it may be useful to see what stacking a catch frame really looks
Here is what the lisp compiler generates
to stack the frame for \fI(*catch\ 'tag\ x)\fP
movl 0(r8),r0 #move 'tag to r0
pushl $0 # dummy argument
pushl r0 # put tag argument on C runtime stack
jsb _qpushframe # call Pushframe
movl r0,_errp # move result into errp
Every function which does a Pushframe() must also do a Popframe()
before it returns to its caller.
This simply removes the frame from the stack.
.tl ''errp = Popframe()''
in the code generated by the lisp compiler it looks like:
movl _errp,r1 # put current errp in r1
movl 12(r1),_errp # put previous errp in errp
addl3 $32,r1,sp # pop frame from stack
Non-local transfers are done with the Inonlocalgo
function. This function always takes three arguments.
first is the return type (one of the types mentioned
above which begin with 'C_'). It will be assigned to retval.
The second argument is the value to be assigned to lispretval,
except in the case of a C_THROW, where the second argument
is the tag to throw to and the third argument is the value
This function never returns.
If it doesn't find a catch frame
which matches what it is looking for, it signals an error.
The function is called with
and the arguments are stacked on the C runtime stack, not the
.+c Liszt:\ The\ Lisp\ Compiler
The purpose of compiling a lisp function is to create a representation of
the function which can be evaluated in less time and perhaps take
There are two approaches to lisp compilers.
One is to convert the functions to a compact form, often called
which can be rapidly interpreted.
Each bytecode represents a primitive operation in the lisp system.
This approach is simple to implement but there is an time penalty
The other approach is to compiled to machine code.
In general, this is not as portable as the bytecode approach but the result
There are two ways of compiling to machine code.
One is to place arguments to functions in registers.
If there are more arguments than registers, the arguments are put on
a stack and a special type of call is made.
This method is used in Maclisp.
The other method is to assume a stack model, in which
arguments to a function are placed on a stack.
The stack model made it much easier to write parts of the lisp
system in the C langauge.
It also simplifies the garbage collector since the mark phase doesn't
have to locate and peruse all saved registers looking for lisp data.
When a file of lisp expressions is loaded,
function repeatedly reads and evaluates the forms in the
Some of these evaluations may result in functions being defined,
and others may use the functions just defined or previously defined.
The job of the lisp compiler is to create an object file, which,
in, except when a function is defined it is defined in machine
code, not as a lisp expression.
This is quite a bit different from what compilers do in other languages
and it is done this way to make it easier to
switch between compiled and
.sh +0 Differences\ between\ compiled\ and\ interpreted
There are some differences, though, between compiled and interpreted code.
Local variables in compiled code are lexically scoped (put on the
namestack and inaccessible to other functions) unless the variable
\fI(declare (special x y))\fP
declares both x and y to be special from this point in the file on.
\fI(declare (specials t))\fP
declares all variables to be special.
Lisp has a very powerful macro definition system.
The compiler will macro expand all it can, whereas the interpreter
expands macros when necessary but never replaces a macro call with
Thus if you redefine a macro, the compiled code that uses it will
still work the same way, but the interpreted code will use the
Also, when compiling a file, macro definitions must be
done before any call on the macro is encountered during compiling.
macros can be defined or redefined anytime up until
Thus the interpreter is far freer about macro definitions than
This could cause programs which work interpreted to
.sh +0 Top\ level\ algorithm
The top level algorithm of the compiler is simply this:
read a lisp expression from the input file
macro expand the top level of the form as much as possible
if the form is a function definition (a list beginning with
if the form is not a function definition then put it on a list of
forms that will be evaluated when the file is
if not at end of file, go to step 1.
In reality, step 3 is a bit more complex.
If the definition is of a macro, then the form will be evaluated
immediately, thus adding the macro definition to the compiler's
is t then the macro will also be compiled.
There are also some forms like \fI(progn\ 'compile\ ...)\fP
and \fI(eval-when\ ()\ )\fP which determine when the
forms get compiled and evaluated.
See the lisp manual for details.
.sh +0 Expression\ Compilation
Just as the interpreter is centered around the
function, the lisp compiler is centered around the function
whose job it is to compile the expression passed to it.
The lisp compiler is one pass.
Before a call to d-exp returns,
all the compiled code for a form has been computed and written
One reason that the lisp compiler can be a single pass compiler
is that the assembler which reads the compiler's output is
.sh +1 global\ state\ variables
There are a number of variables that maintain the state of
These variables are declared special and are thus dynamically scoped
and visible to any function within the compiler.
is called their meanings are:
- contains the expression to be compiled.
- tells where the result of evaluating this expression should be put.
If g-loc is nil, then the value returned is unimportant and shouldn't
- controls conditional branches.
If g-cc is non nil, then it is a list cell whose value has
either a non-null car or non-null cdr but not both.
If the car is non-nil then
if the value of the expression held in
v-form is non-nil, a branch should be done to the symbol
stored in \fI(car\ g-cc)\fP.
If the cdr is non-nil then if the value of v-form
is nil, a branch should be done to the symbol stored in
\fI(cdr\ g-cc)\fP. Since at
branch control should either jump or continue, the car and cdr will
- is non nil if the result of evaluating v-form will be returned as the
value of the function we are evaluating.
This is used to allow liszt to detect
when tail recursion removal is possible.
- maintains current information about the state of the stacks:
the bindstack (for specials), the namestack (for locals) and the
C runtime stack (for catch frames)
The form of g-locs is a stack of tokens stored as a list.
The meaning of each token is as follows:
\fInil\fP - this represents an unnamed object on the namestack. This happens
when calling functions, when the arguments are stacked prior
\fI<symbol>\fP - the given symbol is the name of a local variable on the namestack.
\fI(prog . <n>)\fP - prog statement which binds <n> special variables
\fI(do . <n>)\fP - head of a do statement which binds <n> special variables
\fI(catcherrset . 0)\fP - catch or errset frame on stack
\fI(lambda . <n>)\fP - lambda expression which binds <n> special variables
- this is a stack of labels.
There is one entry in g-labs for every entry which is a list
the forms of the entries are:
\fInil\fP - no labels in this form
\fI(endlab (real . gen) (real2 . gen2) ...)\fP - endlab is the label to go to
to get out of this body. After this label will be code
to unbind specials and pop off locals.
The 'real' labels are those found in the code. the gen
labels are those generated and put in the assembler code.
.sh +0 Function\ compilation
The action d-exp takes when compiling an expression depends on the
For atoms (symbols and numbers) the compilation is very simple, it
is just a matter of putting the value where g-loc specifies and
then jumping if specified by g-cc.
When the expression is a list, d-exp first macro
expands the form and then looks at the first element of
the list (if the list has not macro expanded to an atom).
If the first element is a symbol then the list is
If the function is one of the functions which liszt knows how to open compile
then liszt will call the particular routine designated to open
There are two classes of functions within liszt that
The first class, the fl-expr class, are distinguished by names which
These functions always generate
code which returns the result in r0.
They are not equipped to obey the contents of g-loc and g-cc.
Thus d-exp, after calling one of these functions, must do what
is necessary to obey g-loc and g-cc.
The other class of open compiling functions, the fl-exprcc class (whose
As a result these are usually much more complex and generate better code.
.sh -1 Register\ Conventions
The register conventions used by liszt are an extension of those
- return value placed here
these registers are used in a least-recently-used fashion to access down
The compiler keeps track of the values in these registers but must
assume that they are garbage after a function is called.
There a number of functions which work on fixnum's only and these
usually put their result in r5.
The assembler code function
which returns a pointer to a cell containing a fixnum value (after
checking if it is in the fixnum table), expects its argument to be
When calling a function, this register is set just before the function
call, and after the function call its value is used to reset the value
of np in order to pop the arguments off the namestack.
the literal table pointer.
The compiler generates a table of all the literal lisp data
which the compiled code might access.
Upon function entry a pointer to the base of this table is put in r8.
For example, if we compile \fI(setq\ x\ 'foo)\fP then we will
need a pointer to the lisp symbol
as been declared special we will also need a pointer to
- upon function entry the value of lbot (r7) is put in r10.
This allows us to reference the arguments to our function while
using lbot to call other function.
There are four types of addresses used internally in Franz:
symbolic, intermediate addresses (iadr), extended intermediate (eiadr)
and vax assembler format.
These are the names of lisp objects, such as `a', `foo', 34,
A name is either a local variable, a special variable or a
number. A number is either a small fixnum, large fixnum,
bignum or floating point number.
.sh +0 Intermediate\ address\ (IADR)
This type of address is generated from a symbolic address by
- the location or value of nil.
- the location or value of t.
- register r0, which is where the result of function calls
- the address pointed to by np with np incremented after
the value is stored. (i.e (r6)+)
- the address one word below np (np is decremented before
- this is just <symbol>. This allows strange forms to be
- The n'th value on the namestack for this function.
The first value 0(r10) is (stack 1).
- The cdr of the n'th value on the namestack.
That is, (stack 1) is *0(r10)
- The value of the n'th value in
this refers to a symbol, then this is the value
If this refers to a list then this
this is the cdr of the list (although this is a rare
use). (bind 1) corresponds to *0(r8).
- The n'th value in the literal table. If
object foo then this is the address of foo
- This is the address of small fixnum n in memory.
A small fixnum is in the range -1024 to 1023.
- The is the immediate constant n.
.sh +0 extended\ intermediate\ address\ (EIADR)
This address is generated from an IADR by e-cvt. It
symbolically represents a vax address.
- This corresponds to <atom>.
- This corresponds to n(<atom>)
(stack n+1) and (lbind n+1) are converted to these forms.
.ip \fI(n\ <atom1>\ <atom2>)\fP
- This corresponds to n(<atom1>)[<atom2>]
There is currently no IADR which generates this.
-This corresponds to *n(<atom>)
(vstack n+1) and (bind n+1) are converted to these forms.
- This corresponds to (<atom>)+.
stack is converted to this form.
- This corresponds to -(<atom>)
unstack is converted to this form.
- This corresponds to $<atom>
(immed <numb>) is converted to this form.
- This corresponds to $<loc> where <loc> equals
the base of the fixnums (0x1400) plus 4 * <numb>
(fixnum <numb>) is converted to this form
- This corresponds to $<numb>. It is generated
by d-rsimple occasionally when you ask for the
cdr of a number (which you do sometimes when you
are compiling fixnum operators).
.sh +0 Vax\ Unix\ assembler\ addresses
The addresses are printed from a EIADR by e-cvtas. The conversions
are shown in the above section.
.sh -1 Function\ calling\ convention
.sh +1 Function\ linkages
The function associated with a symbol is stored in the function
definition slot of the symbol. If the function slot contains a
list then the function is to be interpreted and its 'car' will
be lambda, nlambda, lexpr or macro. If the function is compiled then
the function definition slot will contain a binary object.
is composed of two independent parts: the discipline and the entry.
The discipline is one of:
- a function whose arguments should be evaluated.
- a function whose arguments should not be evaluated but
which should be passed as a list
- a function which should be passed the unevaluated form
being evaluated and whose result should be evaluated.
- a foreign function subroutine
.ip \fI\"integer-function\"\fP
- a foreign function returning an integer
.ip \fI\"real-function"\fP
- a foreign function returning a flonum.
A lexpr is not in the list as there is no difference to the caller
between compiled lambda's and compiled lexprs.
Most calls from compiled code to other lisp functions go through
transfer tables. A transfer table entry is a pair: symbol, address
When another lisp function is called it uses the
indirectly jump through the address in the transfer table. This
address may point to the desired function or it may point to the
interface routine. If a call ends up in the interface routine,
then that routine will trace back through the call stack and eventually
reach the tranfer table entry that it was 'called through'. Since the
transfer table entry contains a symbol which names the function
to be called, the interface routine can determine which routine
was to have been called. If that routine is compiled then the
interface routine can modify the transfer table so that a call
through that table entry will go directly to the desired function.
If the routine to be called is interpreted, or if the user has
requested that transfer linkages should be disabled, then the
interface routine will go through the 'funcall' function
in the interpreter to continue the call.
.sh +0 calling\ sequence\ in\ the\ compiler:
When transfer tables are used
\fBcompute\fP arg and stack result using (r6)+
for example: movl r0,(r6)+
movab -n(r6),r7 where n = 4*number of args to fcn
calls $0,*trantb+m where m is the index of the function
The compiler supports local functions, which are function accessible
Because they are not accessible from C code, we can use a very fast
call and return sequence when calling them.
\fBcompute\fP and stack using (r6)+
jsb LOCALNAME go directly to the function, it will
restore r6 before it returns.
The beginning of each function looks as follows.
First for a non-lexpr function called in the standard way
(topsim is the label jumped to when tail merging, it will be unique
for each function; the brackets indicate the optional code which
exists if the -p switch is given to liszt);
.word 0x5c0 # save r6, r7, r8, r10
[ movab mcounts,r0 # if profiling, mcounts replaced by fasl
movab linker,r8 # set up r8
movl r7,r10 # set up oldlbot
movab n(r10),r6 # n = 4*Number of args expected.
[ movab mcounts,r0 # if profiling. [mcounts replaced by fasl]
movab linker,r8 # set up r8
subl3 $4,r7,-(sp) # address one word below bottom of args
movl r6,r10 # first free addr to arg base
subl3 r7,r6,r0 # number of args * 4 into r0
movab 0x1400(r0),(r6)+ # stack boxed number of args
movl 0(r10),-(sp) # also store on stack so user can't clobber
And finally for local functions:
movl r10,-(sp) # save r10
movab -n(r6),r10 # set up arg base using arg top
.sh -1 Assembler\ file\ format
The liszt compiler generates a file which is in Unix assembler format.
The Unix assembler converts that file into an object file which fasl
Although the object file generated is a standard Unix object
file (as defined in /usr/include/a.out.h), it is not of a
format that the Unix ld loader can understand.
This is because the requirements of a lisp object file are different
from an object file of other languages.
run time semantics of lisp and the fact that lisp data must be protected
from garbage collection are the principal differences.
The unconventional object file created by the unix assembler
unconventional assembler input file.
Next we will look at what must be put in the assembler file and how
The assembler file must contain
- vax assembler code for the compiled functions.
If there aren't any functions compiled, this can be empty.
- lisp data which is referred to by compiled code
.ip \fItransfer\ table\fP
- the names of the functions which correspond to the calls through
The instructions simply say 'call indirect through the nth transfer
.ip \fIfunction\ names\fP
- the names of the functions which are being
.ip \fIload\ time\ forms\fP
function, fasl has to be able to evaluate lisp expressions at fasl
time, so we must be able to store lisp expressions in the assembler
file and indicate when they should be evaluated.
Based on the requirements above, the form of the assembler file
The assembler builds two segments: text and data.
We put all of our information in the text segment.
The compiler places some annotation strings in the data segment
so that the object file can be identified, however the data segment
.ip \fIcompiled\ instructions\fP
The instructions for each compiled (non-local) function begins with
The globl declaration and the fact that the symbol name begins
with a F will tell fasl that this is the beginning of a lisp
The symbols beginning with F must be unique within a file
but may be duplicated in other files.
The lisp name of the function will appear later.
Next the instructions for the function are given.
Only a small fixed set of external symbols may be referenced.
The list is found in the code for nfasl.c and the common
ones will be described below (soon).
Labels should be given a name beginning with L and should
be unique within the file.
somewhere in the file there should be a pair of 'set' assembler
pseudo ops which describe the sizes of the literal table and
where linker_size is the number of entries in the literal table
which will be required and trans_size is the number of entries
in the transfer table which will be required.
Those tables will be built by fasl.
- this table describes the order that the functions should be
defined and forms evaluated.
It is a table of longwords beginning at the symbol bind_org
and ending when a -1 entry is seen.
The meaning of the entries will be described below.
.ip \fIlisp\ expression\ table\fP
- this is a table of null terminated strings beginning at the
symbol lit_org and ending at the symbol lit_end.
Each string is read by the lisp read function (using the
The first linker_size expressions are put in the literal table.
The next trans_size expressions are the names of the
functions to put in the transfer table.
The remaining expressions correspond to the entries in the
The binder entries are processed, one by one.
Provided that the binder entry is not -1, an expression
is read from the lisp expression table.
Then if the binder table entry is 0, that expression is the name of
a lambda type lisp function.
A binary object is created, the discipline is set to lambda and
the function address is set to the lexically next function
If the binder entry is 1 then this is an nlambda function, and
if the entry is 2 then this is a macro function.
If the entry is 99 then the expression just read should be evaluated
by the lisp function eval.
The lisp compiler normally puts the assembler format output file in /tmp
and removes it when it is done.
The -S switch will tell liszt to write the
assembler file in the same place as
the source file, and with the same root name but a .s extension.
The -C file will tell the lisp compiler to comment the file as it
generates it, making it easier to understand what is going on.
Assume that the following is file foo.l:
(defun foo (x) (bar y) (baz k))
(def test (nlambda (l) (print 'hithere) (foo 3)))
we now compile it with -SC
.globl F00007 #(fcn lambda foo)
movl *0(r8),(r6)+ #(calling bar)
movl *4(r8),(r6)+ #(calling baz)
.globl F00009 #(fcn nlambda test)
movl 8(r8),(r6)+ #(calling print)
#(from 'hithere to stack)
movl $5132,(r6)+ #(calling foo)
#(from (fixnum 3) to stack)
.data # this is just for documentation
.asciz "@(#)Compiled by Lisp Compiler 7.1 on Sun Feb 21 17:51:54 1982"
.asciz "@(#)decl.l 1.5 2/10/82"
.asciz "@(#)array.l 1.1 9/25/81"
.asciz "@(#)datab.l 1.1 9/25/81"
.asciz "@(#)expr.l 1.1 9/25/81"
.asciz "@(#)io.l 1.1 9/25/81"
.asciz "@(#)funa.l 1.3 2/10/82"
.asciz "@(#)funb.l 1.2 2/10/82"
.asciz "@(#)func.l 1.2 2/10/82"
.asciz "@(#)tlev.l 1.4 10/24/81"
.asciz "@(#)fixnum.l 1.6 10/21/81"
.asciz "@(#)util.l 1.2 10/7/81"
.sh +0 functions\ callable\ from\ compiled\ lisp\ code
.sh +0 Object\ File\ Format
projects / unix-history / blob