![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to franz.n CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / lisp / doc|
Return to franz.n CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / lisp / doc |
1.1 root 1: .\" Copyright (c) 1980 Regents of the University of California.
2: .\" All rights reserved. The Berkeley software License Agreement
3: .\" specifies the terms and conditions for redistribution.
4: .\"
5: .\" @(#)franz.n 6.1 (Berkeley) 4/29/86
6: .\"
7: ." franz.n -[Thu Jun 17 11:01:27 1982 by jkf]-
8: ." this file will contain a description of the franz lisp system.
9: ." sort of a systems manual.
10: .de Fr
11: F\s-2RANZ\s0 L\s-2ISP\s0
12: ..
13: .tp
14: .(l C
15: .sz +2
16: \fBThe Franz Lisp System\fP
17: .sz -2
18: .sp 2v
19: \fIby
20: \fIJohn K. Foderaro\fP
21: .)l
22: .sp 3v
23: .tl ''Abstract''
24: .br
25: This document describes the
26: .Fr
27: system written at The University of California
28: at Berkeley.
29: Included are descriptions of the memory management, interpreter
30: and compiler, the conventions used within the C coded kernel
31: and those within the compiled code.
32: This does not duplicate the information found in The Franz Lisp Manual.
33: .++ C '\s-2Draft\s+2'\fBThe\ Franz\ Lisp\ System\fP'%'
34: .+c Characteristics\ of\ \F\s-2RANZ\ \s0L\s-2ISP\s0
35: .ls 1
36: .pp
37: There is no formal standard for lisp systems, thus each lisp
38: system is almost guaranteed to be different from any other lisp system.
39: In this section we will examine the design decisions which most often
40: characterize a lisp system.
41: This
42: focus does not imply that all other parts of the language are generally
43: agreed upon.
44: In fact, there is nothing sacred to lisp system designers.
45: For example, one usually identifies the symbol
46: .i nil
47: with the empty list,
48: and one usually thinks of lisp as a dynamically scoped language.
49: Both of these conventions are are not true in the lisp dialect
50: .i NIL
51: currently being written at MIT.
52: As another example, one imagines that a lisp system must
53: use garbage collection to reclaim storage.
54: The lisp dialect
55: .i ZetaLisp
56: that is running on Lisp Machines doesn't
57: normally use a garbage collector
58: because of the way in which it allocates its address space.
59: It is faster to reboot the machine than to do a garbage collection.
60: In most lisp dialects the lisp expressions are written in
61: parenthesised form. In
62: .i Portable
63: .i Standard
64: .i Lisp
65: (PSL) at the University of Utah, programs are written
66: primarily
67: in an Algol-like
68: syntax.
69: .pp
70: Thus some of the discussion to follow indicates not so much
71: .i unique
72: charateristics of
73: .Fr
74: but instead, how decisions were made.
75: .sh 2 Scoping\ and\ Binding
76: .pp
77: The
78: .Fr
79: interpreter
80: uses
81: .i dynamic
82: .i scoping ,
83: that is, after A calls B, B can access all of the
84: variables that A allocated
85: as well
86: as those that A can access, provided B doesn't allocate variables of the same
87: names.
88: There are two popular ways of implementing dynamic scoping:
89: .i deep
90: .i binding
91: and
92: .i shallow
93: .i binding .
94: Note that we will use the terms variable allocation and lambda
95: binding interchangeably in this report.
96: The former term is less language-specific than the latter.
97: .sh +1 Deep\ Binding
98: .pp
99: In a deep binding implementation, when a variable is allocated,
100: the name of the variable and a space for its value are pushed on the
101: top of a stack.
102: When a program asks for the value of a variable,
103: the lisp system must search down the stack for the first occurrence of
104: the variable.
105: This system offers great flexibility for the
106: programmer since the state of his program
107: can be described by the contents of the stack.
108: It is thus possible to save the context of a program by just saving
109: the stack or in some cases just a pointer to
110: a place in the stack.
111: The problem with deep binding is that it is time-consuming to search
112: down the stack for the value of a variable, and,
113: as a result, most systems
114: modify the deep binding model by giving variables a global value
115: cell and allowing programs to set and access the global cell.
116: Some implementations of Interlisp use deep binding.
117: .sh +0 Shallow\ Binding
118: .pp
119: In a shallow binding implementation, each variable has a global value cell
120: which contains the current value of the variable.
121: When a variable is allocated inside a program, its name
122: and old value are pushed on a stack called a
123: .i bindstack .
124: The variable is then given a new value.
125: Throughout the lifetime of the allocation, the current value of the
126: variable can be found in the global value cell associated with the variable.
127: When leaving the context of the variable's allocation, the old value
128: is restored from the
129: .i bindstack .
130: A shallow binding scheme makes it much cheaper to access
131: the values of variables, however it is much more difficult to
132: save the state and to restore it.
133: .pp
134: .Fr
135: and most other lisps which are not derived from Interlisp
136: use shallow binding.
137: Some versions of Interlisp use shallow binding.
138: .sh -1 Lisp\ Compiler
139: .pp
140: Dynamic scoping often is not necessary and it is never cheap, even
141: in a shallow binding implementation.
142: Thus the
143: .Fr
144: compiler prefers to do lexical scoping rather than dynamic
145: scoping.
146: If the user does not specify otherwise, when a
147: function is compiled, all variables
148: allocated will be
149: put on a local stack and will
150: .i not
151: be accessible by any
152: function that this function calls.
153: This
154: convention results in faster code being generated by
155: the compiler, but if the
156: user is not careful, it can result in compiled and interpreted code
157: working differently.
158: In some of the new lisp designs, such as
159: .i NIL
160: and
161: .i Common
162: .i Lisp
163: the semantics of compiled and interpreted code have been
164: unified by
165: transferring the compiler semantics (lexical scoping) to the interpreter.
166: This is a rather large step
167: if dynamic scoping is no
168: longer an option, and it is not clear whether the resulting
169: language should be called 'lisp'.
170: .sh +0 Data\ Types
171: .pp
172: A complete list of data types in
173: .Fr
174: can be found in the first chapter of the
175: .Fr
176: Manual.
177: The most important ones are described below.
178: .pp
179: Lisp is a list processing language and the basic data type is the list
180: cell.
181: A list cell also goes by the name of cons cell, pair, or dotted pair (dtpr).
182: It contains pointers to two lisp objects, and these pointers can
183: be accessed via the
184: .i car
185: and
186: .i cdr
187: functions.
188: Each pointer requires four (8-bit) bytes and thus the list cell is
189: eight bytes large.
190: The cdr pointer is stored first since this makes it easier
191: to 'cdr down a list' using the addressing modes of the VAX.
192: .pp
193: The symbol cell is used to implement variables. It contains a pointer
194: to a string that is the print name, a cell to store a value, a cell to
195: store the function definition, a cell to store a pointer to the property
196: list and one pointer that the list system uses if it stores
197: the symbol in the oblist.
198: .sh +0 Memory\ Management
199: .pp
200: A lisp system must be able to determine the type of an
201: object at run time.
202: The method used to determine the type influences the
203: way storage is managed and garbage collection is done.
204: Next, we will look at three possible places
205: to store the type information.
206: .sh +1 Typed\ data
207: .pp
208: The type of the data object could be placed in the object itself, much
209: as Pascal stores the type of a variant record in the record itself.
210: This could result is a large amount of storage being used to store
211: type information.
212: No lisp system that we know of uses this method exclusively.
213: .sh +0 Typed\ pointers
214: .pp
215: Every reference to a lisp object could contain the type of the object
216: referenced.
217: This is a good idea in a machine like an IBM 370 where only
218: part of machine word is used by the addressing hardware.
219: Lisps that use typed pointers generally use a
220: .i heap
221: memory management scheme and a
222: .i copying
223: garbage collector.
224: In a heap scheme,
225: all memory is divided by a pointer (called the
226: heap pointer) separating lisp
227: data and free space.
228: When a new lisp object is needed, it is formed at the
229: dividing line and then
230: the heap pointer is incremented
231: past the new object.
232: Garbage collection is done by maintaining two separate spaces for lisp
233: data, only one of which is used at any one time.
234: When one fills up, all active lisp objects are copied to the
235: other space, leaving the first space totally free.
236: Subsequent allocations are done from the second space, until it fills up,
237: at which point
238: all active data in the second space is copied to the first space.
239: The advantage of the copying garbage collector is that the data space
240: is compacted, which will improve virtual memory behavior.
241: The disadvantage is that
242: half the data space is always unused.
243: .pp
244: PSL on a PDP-10 uses this scheme, as does Lisp 370 on
245: an IBM 370.
246: PSL and NIL on the VAX will also use this scheme.
247: Since the VAX hardware
248: uses the entire word for address
249: calculation,
250: PSL and NIL
251: must mask off the type bits
252: of a pointer before using it to reference memory.
253: .sh +0 Typed\ pages
254: .pp
255: The final alternative is to allocate data objects by pages rather than
256: individually.
257: Each page contains only one type of object and there is a table that
258: keeps track of the type of data object in each page.
259: The address of an object tells which page the object is on and
260: the page number tells which type the object is.
261: Since a whole page of objects is allocated when only one
262: object is necessary,
263: the rest of the objects in the page are put on a free list.
264: This method of allocation is sometimes referred to as
265: .i bibop
266: for BIg Bag Of Pages.
267: The garbage collector for bibop is usually
268: a traditional
269: .i mark
270: and
271: .i sweep
272: algorithm.
273: All active data objects are marked and
274: then each page is swept linearly with
275: the free cells being put on the free list and the used cells
276: left alone.
277: The advantage of mark and sweep over a copying garbage collector is that
278: the mark phase is cheaper because data objects do not have to be copied.
279: Also, all of memory can be used since there is no requirement for two spaces.
280: The disadvantage is that a sweep phase is required in a mark and sweep
281: but one is not required in a copying garbage collector.
282: The sweep phase is expensive because it has to alter most data pages
283: while building a free list.
284: This operation
285: can be expensive in a virtual memory environment.
286: Alternatives to the sweep phase have been proposed in
287: [Foderaro+Fateman Characterization of Vax Macsyma].
288: .pp
289: .Fr
290: uses a bibop memory allocator and a mark and sweep garbage collector,
291: as does Maclisp (on a PDP-10).
292: The reason that
293: .Fr
294: uses bibop is primarily due to the VAX architecture,
295: which makes typed pointers
296: expensive to implement.
297: Also, typed pointers would make it difficult to pass lisp values
298: to programs written in other languages, some of which may not have
299: the ability to extract the address of a lisp object from a typed pointer.
300: .sh -1 Construction
301: .pp
302: The
303: .Fr
304: system is built by adding lisp code to a C-coded kernel.
305: The C-coded kernel is a working lisp interpreter, although it has few of
306: the functions a lisp system needs.
307: The lisp code provides most of the functions, the top level and error
308: handlers.
309: The lisp compiler is also written in lisp,
310: but is usually
311: run as a separate process.
312: .sh +0 Unique\ features
313: .pp
314: .Fr
315: can dynamically load and execute functions defined in the other languages
316: which run on the VAX.
317: It uses two different dynamic loaders.
318: One is part of the lisp system and is used for lisp only, it is called
319: .i fasl
320: (for fast loader).
321: The other is the Unix loader, ld, which is used for loading in
322: C, Fortran or Pascal code.
323: Loading code with fasl
324: is much faster than with ld
325: since fasl benefits from
326: the simplicity of a lisp object file.
327: .+c Data\ Structures
328: .sh 0 _
329: .nr $1 \n(ch
330: .pp
331: In this chapter we shall examine the data structures which are most
332: important to the
333: .Fr
334: system.
335: First, though we will see how the lisp system uses the address space.
336: .sh 2 Physical\ layout
337: .pp
338: As a Unix process, lisp has three address regions: text, data and stack.
339: Text begins at location 0 and continues up to 0x3b73c (0x means hex number).
340: The data segment begins on the next page boundary and continues
341: up to a limit set by the configuration parameters (currently 0x2fd000).
342: Lisp does not begin running with such a large data segment, rather it grows
343: when necessary.
344: The stack segment begins at address 0x7fffffff and grows downward to a
345: maximum size of one-half megabyte.
346: .pp
347: The text segment stores the instructions for the C kernel as well as read-only
348: data.
349: The read-only data for lisp are
350: the symbol nil, the i/o ports, and the small integer
351: table.
352: The symbol nil is stored at location 0 which makes it very easy to test
353: whether a value is nil.
354: The problem with storing nil in read-only space is that a special case
355: must be made for nil's property list, which is the only thing in the
356: nil symbol that the user is permitted to alter.
357: .pp
358: The fixnums -1024 through 1023 are stored sequentially, with 0 being
359: stored at 0x1400.
360: .Fr
361: doesn't have any 'immediate' lisp data, that is data whose value is
362: stored as part of the reference to the data.
363: But, by storing some of the fixnums in a known place, we can achieve
364: some of the benefits of immediate data:
365: A program can use
366: .i eq
367: as a test for a fixnum in the range -1024 to 1023.
368: In the majority of cases, when asked
369: to allocate a fixnum, the system can return a pointer into this table
370: and bypass the memory allocator.
371: .sh +0 Typetable
372: .pp
373: .Fr
374: uses the typed pages (or bibop)
375: method of type determination.
376: The
377: .i typetable
378: is an array of bytes (
379: .i chars
380: in C lingo).
381: This table describes the type of all pages, from page 0 where nil is stored,
382: up to the end of data space.
383: Thus there are many entries that describe the types of the pages which
384: make up the C kernel.
385: In order to reduce the wasted space in the typetable,
386: we could have made the typetable begin typing pages at the start of data
387: space and make a special case of the pages that contain nil and
388: the small integer table.
389: However, the
390: effect of this change would be that type checks
391: (which are done in-line in compiled code) would
392: be longer and slower. Since type checking happens quite
393: frequently, we felt it was better to waste the space in the
394: typetable in order to save execution time and instruction space.
395: .pp
396: Each page on a VAX is 512 bytes, and thus to find the type of an
397: object given the address of it,
398: it is only necessary to shift the address right 9 bits
399: and index the typetable array offset by one.
400: The offset by one is required because the value -4, which is an illegal
401: address, is used as a sentinel value to indicate an illegal value.
402: Thus when we take the type of -4 we will be indexing the table by -1
403: and we want to retrieve the first byte in the table (which contains
404: the value UNBOUND).
405: The C macro which retrieves the type is this (from file h/global.h):
406: .(b I
407:
408: #define TYPE(a1) ((typetable+1)[(int)(a1) >> 9])
409:
410: .)b
411: This is code generated by the lisp compiler to check if the type
412: code of an argument (stored at 0(r10)) is a symbol (which is type
413: code 1):
414: .(b I
415:
416: ashl $-9,0(r10),r0
417: cmpb _typetable+1[r0],$1
418:
419: .)b
420: .pp
421: The type codes which are stored in the typetable are these:
422: .ts 2i 4i 6i
423: .(b I
424: UNBO -1\tSTRNG 0\tATOM 1\tINT 2
425: DTPR 3\tDOUB 4\tBCD 5\tPORT 6
426: ARRAY 7\tOTHER 8\tSDOT 9\tVALUE 10
427: HUNK2 11\tHUNK4 12\tHUNK8 13\tHUNK16 14
428: HUNK32 15\tHUNK64 16\tHUNK128 17
429: .)b
430: The names given above are the C kernel internal names.
431: ATOM is symbol, INT is fixnum, DTPR is list cell,
432: DOUB is flonum, BCD is binary,
433: SDOT is bignum and all the HUNKn types are just known as hunk to
434: the user.
435: .sh +0 Stacks
436: .pp
437: .Fr
438: uses three stacks: the
439: .i C
440: .i runtime
441: stack, the
442: .i namestack
443: and the
444: .i bindstack .
445: The C runtime stack is the stack part of the address space
446: and the other two stacks are stored in the data space.
447: .sh +1 C\ runtime\ stack
448: The C-coded kernel uses this
449: stack in the same way as a typical C program
450: use the stack:
451: storing return addresses
452: and non-lisp-object arguments to subroutines,
453: saving registers,
454: and storing local variables within a function.
455: The lisp system stores
456: .i catch
457: .i frames
458: on this stack as well (to be described later).
459: .pp
460: The lisp system assumes that there are no lisp data on the stack and
461: thus the use of this stack
462: by a program is unrestricted.
463: As will be discussed later on, the
464: .b calls
465: and
466: .b ret
467: instructions are used for most subroutine calls and returns.
468: These instructions expect the stack to look a certain way.
469: .sh +0 Namestack
470: .pp
471: The namestack contains only lisp data.
472: It is used to pass arguments to functions and to hold
473: local (lexically scoped) data within lisp functions.
474: It is also used as a temporary storage spot for lisp data
475: which must be protected from garbage collection.
476: .pp
477: A slight digression on the garbage collector:
478: The person who writes code for the lisp system must always be aware of
479: his greatest enemy: the garbage collector.
480: Whenever a function is called that could possibly allocate more lisp
481: data, one must assume that it
482: when it attempts to allocate space, the garbage collector
483: will be invoked and that it will take away everything that isn't protected
484: from garbage collection.
485: The objects that are protected from garbage collection are: the
486: namestack, the bindstack, the oblist (table of interned symbols),
487: and the compiler literals. Objects that are only
488: referred to by values in registers or
489: the C runtime stack will not be seen by the mark phase of the
490: garbage collector and will be swept up during the sweep phase.
491: .pp
492: Back to the namestack:
493: The first free element on the namestack is pointed to by the
494: C variable
495: .i np .
496: This variable is always stored in the VAX register r6.
497: Another pointer into the namestack is the C variable
498: .i lbot .
499: It is always stored in VAX register r7.
500: Its use will be described in the section on calling conventions.
501: .sh +0 Bindstack
502: .pp
503: The bindstack is a stack of lisp object pairs: symbol and
504: value.
505: It is used to implement shallow binding.
506: When a symbol is lambda-bound, the symbol and its current value are put
507: on this stack.
508: Then the symbol can be given a new value.
509: When the context of the lambda binding is over, the symbol and value pair
510: are popped from the stack and the symbol is given its old value.
511: The C variable
512: .i bnp
513: points to the first free entry on the bindstack.
514: In the C code, the following macros lambda-bind a symbol to a value
515: and restore the old value:
516: .(b
517: #define PUSHDOWN(atom,value)\e
518: {bnp->atm=(atom);\e
519: bnp++->val=(atom)->a.clb;\e
520: (atom)->a.clb=value;\e
521: if(bnp>bnplim) binderr();}
522:
523: #define POP\e
524: {--bnp; bnp->atm->a.clb=bnp->val;}
525: .)b
526: .sh -1 Bitmap
527: .pp
528: The bitmap is used in garbage collection to hold
529: the mark bits for the mark and sweep garbage collector.
530: As its names implies, it is viewed as a collection of bits.
531: The minimum size of a lisp data object is 4 bytes, thus
532: there are 128 of those on a VAX page of 512 bytes.
533: Since there are 8 bits in a byte, it takes 16 bytes to obtain 128 bits.
534: Therefore the size of the bitmap in bytes is 16
535: times the maximum number of
536: pages.
537: Like the typetable, the bitmap keeps track of marks from the
538: bottom of memory, not the bottom of data space.
539: The bitmap and the typetable are static structures.
540: It is their size, which is determined when the C kernel is built,
541: which determines the size to which the data segment can grow.
542: .sh +0 Transfer\ Tables
543: .pp
544: Transfer tables are used by compiled lisp code as a transfer vector to
545: other functions.
546: A transfer table consists of pairs of entries: symbol and pointer to
547: function.
548: When a compiled lisp function calls another (non-local) function, it
549: calls indirectly through an entry in the transfer table.
550: Depending on the setting of certain status variables, the call may
551: bring control into a function linkage routine or directly to
552: the function desired (if that function is a compiled lisp or C function).
553: .pp
554: Transfer tables serve a number of useful purposes.
555: .np
556: They allow compiled code to call interpreted code
557: or compiled code using the same calling sequence.
558: .np
559: They allow the selection of which function to call to be determined
560: at runtime based on the name of the function.
561: In most other languages, this selection process is done at either
562: compile or load time.
563: .np
564: They allow the user to run in a debugging mode where all calls
565: from compiled code go through the interpreter.
566: Once control reaches the interpreter, it is easier to debug.
567: .np
568: They allow the user to run in a production mode, where all calls
569: from compiled to other compiled code are done without function
570: lookup overhead.
571: .np
572: They allow the user to switch between debugging and production modes
573: at runtime with one function call.
574: .pp
575: Transfer tables will be described further in the section on
576: the lisp compiler.
577: .sh +0 Catch\ frames
578: .pp
579: Lisp has a number of forms of non-local transfers.
580: Among them are
581: .i throw ,
582: .i error ,
583: .i return
584: and
585: .i go .
586: If a program is willing to accept a non-local transfer, it puts a
587: .i catch
588: .i frame
589: on the stack which describes which type of transfer it
590: accepts.
591: The catch frame describes the current state of the registers,
592: the variables np, lbot, and bnp, and also contains entries that describe
593: what kinds of non-local transfers the function will accept.
594: After creating a catch frame, the program goes on to evaluate forms.
595: Should the evaluation of one of those forms result in a non-local
596: transfer to the catch frame that this program has set up, the
597: system will restore the namestack and bindstack to the way
598: they were when the program put the catch frame on the stack (by using
599: np and bnp) and will return control to the program (setting
600: the variable retval to describe why it returned).
601: This is described further in the
602: section on interpreter conventions.
603: .pp
604: The C variable
605: .i errp
606: points to the most recent catch frame, and then each catch frame points
607: to the previous catch frame.
608: .sh +0 oblist
609: .pp
610: Normally when symbols are created they are
611: .i interned ,
612: that is they are put in a hash table called an oblist (or obarray).
613: The purpose of the oblist is to insure that if you type a
614: symbol's name to the reader, you will always get the same symbol.
615: Also it protects the symbol from garbage collection.
616: The oblist is simply a hash table with buckets, with a hash link being
617: part of the symbol data structure.
618: Currently the hash table is not accessible to a lisp program, but with
619: a little work it could be.
620: .+c Interpreter
621: .sh 0 _
622: .nr $1 \n(ch
623: .pp
624: The interpreter is composed of these parts:
625: .ip \fIcore:\fP
626: The functions eval, apply and funcall.
627: .ip \fIstack\ management:\fP
628: The code to create catch frames and handle non-local transfers.
629: .ip \fImemory\ management:\fP
630: The code to allocate and garbage collect memory.
631: .ip \fIthe\ functions:\fP
632: The user callable functions that expect lisp arguments and return
633: lisp values.
634: .pp
635: In the above list, the first three are written mainly in C (with a little
636: assembler) and the last is written mainly in Lisp with a little
637: bit in C
638: and a very small amount in assembler.
639: .pp
640: The core functions are the center of activity in the interpreter.
641: The
642: .i eval
643: function given a lisp expression to evaluate.
644: It must determine if it is a simple expression such as a symbol or number
645: whose value eval can determine immediately, or if it is an function
646: calling expression.
647: If the form is a function call, eval must determine if the arguments should
648: be evaluated and if so eval must recursively call itself to evaluate the
649: arguments and then stack them.
650: If the function called is to be interpreted, eval must lambda-bind the
651: formal variables of the function to the arguments just stacked.
652: If the function being called is compiled, eval just calls the function and
653: lets the function do the lambda binding if it wants to.
654: .pp
655: The
656: .i apply
657: function is passed two lisp objects:
658: a function to call (either a symbol or a functional object)
659: and a list of arguments already evaluated.
660: It will do lambda binding if the function to call is to
661: be interpreted.
662: .pp
663: The
664: .i funcall
665: function is passed any number of lisp objects,
666: the first of which is the function to call, and the rest are the
667: arguments to the function
668: which have already been evaluated and stacked.
669: Funcall will do lambda binding if the function to call is
670: to be interpreted.
671: .pp
672: When compiled lisp code calls a function
673: which must be interpreted, it enters the interpreter through the
674: funcall function.
675: The interpreter may go to compiled code through either eval, apply or
676: funcall, though most often it goes through eval.
677: .sh 2 Conventions
678: .pp
679: These are the conventions used in interpreted and compiled code.
680: .sh +1 C\ conventions
681: .pp
682: Our conventions are extensions of the C calling conventions, so we
683: describe here the conventions for C.
684: The VAX has 16 general
685: purpose registers.
686: Registers r12 through r15 are reserved
687: for use by the hardware because we use the
688: .i calls
689: subroutine call.
690: Registers r0-r5 can be used by a program without saving them first.
691: The result of a function call is returned in r0.
692: Registers r11-r6 are allocated (from high to low)
693: by the C compiler when a
694: .i register
695: declaration is made in the C code.
696: Registers r11-r6 must be
697: saved upon entry and restored upon exit if they are used within a function.
698: On the VAX it is very easy to preserve registers
699: since it is done automatically
700: by the hardware if the
701: .i calls
702: (or
703: .i callg )
704: instruction is used.
705: The first short word (two bytes) of a subroutine is a
706: register save mask which
707: tells which registers should be saved (on the C runtime stack) upon
708: entry and restored when a
709: .i ret
710: instruction is done.
711: .sh +0 np\ and\ lbot
712: .pp
713: Earlier we mentioned that the C variables np and lbot are
714: always stored in
715: registers r6 and r7.
716: It is very difficult to globally assign a variable to a register
717: in the C language (no external register declarations
718: are permitted)
719: and thus we have to filter
720: the output of the C compiler and convert all occurrences of 'np' to 'r6'
721: and all occurrences of 'lbot' to 'r7'.
722: This is only half the job, though.
723: We also must modify the register save masks for those routines which
724: alter the value of np or lbot to insure that those registers get
725: saved and restored upon function entry and exit.
726: This is done in the C code by putting
727: .(b C
728: Savestack(n)
729: .)b
730: at the beginning of a routine which will alter np or lbot and which
731: also allocates n register variables.
732: Also in that routine, before the function returns, we put
733: .(b C
734: Restorestack()
735: .)b
736: This is not really necessary in the VAX, but it is there for other
737: machine implementations which don't have a
738: .i ret
739: function which restores registers.
740: The calls to Savestack are recognized by a filter which processes
741: the output
742: of the C compiler and fixes up
743: the save masks.
744: .sh +0 Function\ calling
745: .pp
746: The following text describes what the conventions are for
747: calling
748: compiled lisp functions, whether they were written in lisp or C.
749: We look at it from the viewpoint of the called function.
750: .pp
751: Upon entry
752: to the compiled functon,
753: lbot points to the first argument and np points to the
754: first free spot on the namestack.
755: If np equals lbot then there are no arguments.
756: Recall that np will be in r6 and lbot in r7.
757: The function is free to alter registers r0 through r5 and should return
758: the result in r0.
759: The function may alter registers r6 through r11 as long as their
760: original values
761: are restored when the function returns.
762: The value of np should always
763: point to the first free entry in the namestack.
764: This is all that is required.
765: The extra conventions followed by
766: the lisp compiler
767: in the code it generates are described in the next chapter.
768: .sh +0 Catch\ frames
769: .pp
770: A catch frame saves the state of execution that a program
771: might want to return to at some later time.
772: A catch frame is stored on the C runtime stack, with the most recent
773: frame pointed to by the C global variable errp.
774: The information saved is
775: .ip \fIargs\fP
776: - one or two optional arguments. The lisp compiler always
777: stacks two
778: arguments since it must know exactly how large the frame is.
779: .ip \fIclass\fP
780: - the class describes what type of frame this is (described below).
781: .ip \fIretaddr\fP
782: - address to return to if returning from this frame
783: .ip \fIolderrp\fP
784: - pointer to next older catch frame on the stack
785: .ip \fIbnp\fP
786: - value of bnp (bindstack pointer) when the frame was created
787: .ip \fInp\fP
788: - value of np when the frame was created
789: .ip \fIlbot\fP
790: - value of lbot when the frame was created.
791: .ip \fIsystem\ dependent\fP
792: - the rest of the information stacked depends on the particular machine.
793: In the case of the VAX, registers r13 through r8 are stacked. (r14 and
794: r15 are the stack pointer and program counter; they are not saved since
795: they can be calculated from the other information).
796: .pp
797: The information in a catch frame is put on the C runtime stack
798: in the precise order given above, and the variable errp points not
799: at the beginning of the entire frame, but to the lbot entry.
800: Thus errp\ +\ 4 points to np.
801: The classes of frames are described below.
802: Each class is defined as a constant in the C code (h/frame.h) whose value
803: is a small integer.
804: .ip F_PROG\ [1]
805: - takes no arguments. This frame marks the beginning of a piece of
806: code which can accept a
807: .i return
808: or a
809: .i go .
810: The interpreter uses this to implement
811: .i prog
812: and
813: .i do
814: and for its primative break loop.
815: The lisp compiler does not use catch frames for progs since it only
816: permits
817: .i returns
818: and
819: .i gos
820: to occur within
821: .i progs
822: or
823: .i dos
824: and thus it can determine how to do the non-local transfer
825: at compile time.
826: .ip F_CATCH\ [2]
827: - this takes one or two arguments and is used to implement both
828: .i catch
829: and
830: .i errset .
831: In both cases
832: the first argument is the tag which is being caught,
833: which in the case of an
834: .i errset
835: is symbol ER%all.
836: An
837: .i errset
838: also
839: supplies a second argument which is non nil if the error message
840: should be printed.
841: .ip F_RESET\ [3]
842: - in the C kernel, the reset function
843: is implemented as a non local transfer to a F_RESET catchframe.
844: When the lisp system is built, the reset function is redefined to
845: do a
846: .i throw.
847: Thus this type of catch frame is rarely used.
848: .ip F_EVAL\ [4]
849: - this has one argument, the form being evaluated.
850: Since stacking this
851: on every eval would be expensive,
852: this type of catch frame is only stacked if a \fI(*rset\ t)\fP
853: has been done and if the value of the symbol
854: .i *rset
855: is non nil.
856: The form being evaluated is stacked so that
857: the necessary information for the
858: .i evalframe
859: function is available and so that
860: .i freturn
861: can return from the context of any pending evaluation.
862: .ip F_FUNCALL\ [5]
863: - this is much like F_EVAL,
864: except the one argument it takes is the
865: name of the function to call.
866: It has the same restrictions on when it is stacked as F_EVAL
867: and for the same reasons.
868: .pp
869: In C, a frame is pushed on the stack with Pushframe, with a call
870: of one of these forms:
871: .(b
872: errp = Pushframe(class);
873: errp = Pushframe(class,arg1);
874: errp = Pushframe(class,arg1,arg2);
875: .)b
876: After the call the C variable
877: .i retval
878: contains the value which describes why this function returned.
879: You must remember that it is possible for this one function call to
880: return more than once!
881: The reasons it can return are these (from h/frame.h):
882: .ip C_INITIAL\ [0]
883: This is the initial call to set up the frame.
884: .ip C_GO\ [1]
885: This will only happen for F_PROG frames.
886: In this case,
887: the C variable lispretval contains a lisp symbol which is the tag
888: to which control should be transferred.
889: If the tag cannot be found in this prog or do body, the
890: tag should be again thrown up the stack to a next higher prog or do.
891: .ip C_RET\ [2]
892: This will only happen for F_PROG frames.
893: In this case, lispretval contains the value to return from this prog.
894: .ip C_THROW\ [3]
895: This will only happen for F_CATCH frames.
896: In this case lispretval contains the value to return from this catch.
897: .ip C_RESET\ [4]
898: This will only happen for F_RESET frames.
899: It simply means that a reset is being done.
900: .ip C_FRETURN\ [5]
901: This will only happen for F_EVAL and F_FRETURN frames.
902: The variable lispretval contains the value to return from this
903: call to
904: .i eval
905: or
906: .i funcall .
907: .pp
908: The call to Pushframe is turned into a simple subroutine call (using
909: the
910: .i jsb
911: instruction instead of the
912: .i calls )
913: by the filters which alter the code coming out of the C compiler.
914: Thus it may be useful to see what stacking a catch frame really looks
915: like.
916: Here is what the lisp compiler generates
917: to stack the frame for \fI(*catch\ 'tag\ x)\fP
918: .(b
919: movl 0(r8),r0 #move 'tag to r0
920: pushl $0 # dummy argument
921: pushl r0 # put tag argument on C runtime stack
922: pushl $2 # push F_CATCH
923: jsb _qpushframe # call Pushframe
924: movl r0,_errp # move result into errp
925: .)b
926: .pp
927: Every function which does a Pushframe() must also do a Popframe()
928: before it returns to its caller.
929: This simply removes the frame from the stack.
930: In C it is written:
931: .br
932: .tl ''errp = Popframe()''
933: in the code generated by the lisp compiler it looks like:
934: .(b
935: movl _errp,r1 # put current errp in r1
936: movl 12(r1),_errp # put previous errp in errp
937: addl3 $32,r1,sp # pop frame from stack
938: .)b
939: .pp
940: Non-local transfers are done with the Inonlocalgo
941: function. This function always takes three arguments.
942: The
943: first is the return type (one of the types mentioned
944: above which begin with 'C_'). It will be assigned to retval.
945: The second argument is the value to be assigned to lispretval,
946: except in the case of a C_THROW, where the second argument
947: is the tag to throw to and the third argument is the value
948: to assign to lispretval.
949: This function never returns.
950: If it doesn't find a catch frame
951: which matches what it is looking for, it signals an error.
952: The function is called with
953: .i calls
954: and the arguments are stacked on the C runtime stack, not the
955: namestack.
956: .+c Liszt:\ The\ Lisp\ Compiler
957: .sh 0 _
958: .nr $1 \n(ch
959: .pp
960: The purpose of compiling a lisp function is to create a representation of
961: the function which can be evaluated in less time and perhaps take
962: up less space.
963: There are two approaches to lisp compilers.
964: One is to convert the functions to a compact form, often called
965: .i bytecodes
966: which can be rapidly interpreted.
967: Each bytecode represents a primitive operation in the lisp system.
968: This approach is simple to implement but there is an time penalty
969: in using an interpreter.
970: The other approach is to compiled to machine code.
971: In general, this is not as portable as the bytecode approach but the result
972: generally runs faster.
973: There are two ways of compiling to machine code.
974: One is to place arguments to functions in registers.
975: If there are more arguments than registers, the arguments are put on
976: a stack and a special type of call is made.
977: This method is used in Maclisp.
978: The other method is to assume a stack model, in which
979: arguments to a function are placed on a stack.
980: This is what the
981: .Fr
982: compiler Liszt does.
983: The stack model made it much easier to write parts of the lisp
984: system in the C langauge.
985: It also simplifies the garbage collector since the mark phase doesn't
986: have to locate and peruse all saved registers looking for lisp data.
987: .sh 2 File\ Compiler
988: .pp
989: When a file of lisp expressions is loaded,
990: the
991: .i load
992: function repeatedly reads and evaluates the forms in the
993: file.
994: Some of these evaluations may result in functions being defined,
995: and others may use the functions just defined or previously defined.
996: The job of the lisp compiler is to create an object file, which,
997: when read in
998: by
999: .i fasl,
1000: acts just like it was
1001: .i load ed
1002: in, except when a function is defined it is defined in machine
1003: code, not as a lisp expression.
1004: This is quite a bit different from what compilers do in other languages
1005: and it is done this way to make it easier to
1006: switch between compiled and
1007: interpreted code.
1008: .sh +0 Differences\ between\ compiled\ and\ interpreted
1009: .pp
1010: There are some differences, though, between compiled and interpreted code.
1011: Local variables in compiled code are lexically scoped (put on the
1012: namestack and inaccessible to other functions) unless the variable
1013: has been declared
1014: .i special.
1015: The declaration:
1016: .(b
1017: \fI(declare (special x y))\fP
1018: .)b
1019: declares both x and y to be special from this point in the file on.
1020: The declaration
1021: .(b
1022: \fI(declare (specials t))\fP
1023: .)b
1024: declares all variables to be special.
1025: .pp
1026: Lisp has a very powerful macro definition system.
1027: The compiler will macro expand all it can, whereas the interpreter
1028: expands macros when necessary but never replaces a macro call with
1029: its expansion.
1030: Thus if you redefine a macro, the compiled code that uses it will
1031: still work the same way, but the interpreted code will use the
1032: new definition.
1033: Also, when compiling a file, macro definitions must be
1034: done before any call on the macro is encountered during compiling.
1035: In the interpreter,
1036: macros can be defined or redefined anytime up until
1037: they are used.
1038: Thus the interpreter is far freer about macro definitions than
1039: the compiler.
1040: This could cause programs which work interpreted to
1041: fail compiled.
1042: .sh +0 Top\ level\ algorithm
1043: .pp
1044: The top level algorithm of the compiler is simply this:
1045: .np
1046: read a lisp expression from the input file
1047: .np
1048: macro expand the top level of the form as much as possible
1049: .np
1050: if the form is a function definition (a list beginning with
1051: the symbol 'def')
1052: then compile it.
1053: .np
1054: if the form is not a function definition then put it on a list of
1055: forms that will be evaluated when the file is
1056: .i fasl ed
1057: in.
1058: .np
1059: if not at end of file, go to step 1.
1060: .pp
1061: In reality, step 3 is a bit more complex.
1062: If the definition is of a macro, then the form will be evaluated
1063: immediately, thus adding the macro definition to the compiler's
1064: environment.
1065: If the lisp variable
1066: .i macros
1067: is t then the macro will also be compiled.
1068: There are also some forms like \fI(progn\ 'compile\ ...)\fP
1069: and \fI(eval-when\ ()\ )\fP which determine when the
1070: forms get compiled and evaluated.
1071: See the lisp manual for details.
1072: .sh +0 Expression\ Compilation
1073: .pp
1074: Just as the interpreter is centered around the
1075: .i eval
1076: function, the lisp compiler is centered around the function
1077: .i d-exp
1078: whose job it is to compile the expression passed to it.
1079: The lisp compiler is one pass.
1080: Before a call to d-exp returns,
1081: all the compiled code for a form has been computed and written
1082: to a file.
1083: One reason that the lisp compiler can be a single pass compiler
1084: is that the assembler which reads the compiler's output is
1085: a two pass assembler.
1086: .sh +1 global\ state\ variables
1087: .pp
1088: There are a number of variables that maintain the state of
1089: the compilation process.
1090: These variables are declared special and are thus dynamically scoped
1091: and visible to any function within the compiler.
1092: When d-exp
1093: is called their meanings are:
1094: .ip \fIv-form\fP
1095: - contains the expression to be compiled.
1096: .ip \fIg-loc\fP
1097: - tells where the result of evaluating this expression should be put.
1098: If g-loc is nil, then the value returned is unimportant and shouldn't
1099: be put anywhere.
1100: .ip \fIg-cc\fP
1101: - controls conditional branches.
1102: If g-cc is non nil, then it is a list cell whose value has
1103: either a non-null car or non-null cdr but not both.
1104: If the car is non-nil then
1105: if the value of the expression held in
1106: v-form is non-nil, a branch should be done to the symbol
1107: stored in \fI(car\ g-cc)\fP.
1108: If the cdr is non-nil then if the value of v-form
1109: is nil, a branch should be done to the symbol stored in
1110: \fI(cdr\ g-cc)\fP. Since at
1111: every conditional
1112: branch control should either jump or continue, the car and cdr will
1113: never both be specified.
1114: .ip \fIg-ret\fP
1115: - is non nil if the result of evaluating v-form will be returned as the
1116: value of the function we are evaluating.
1117: This is used to allow liszt to detect
1118: when tail recursion removal is possible.
1119: .ip \fIg-locs\fP
1120: - maintains current information about the state of the stacks:
1121: the bindstack (for specials), the namestack (for locals) and the
1122: C runtime stack (for catch frames)
1123: The form of g-locs is a stack of tokens stored as a list.
1124: The meaning of each token is as follows:
1125: .br
1126: \fInil\fP - this represents an unnamed object on the namestack. This happens
1127: when calling functions, when the arguments are stacked prior
1128: to a function call.
1129: .br
1130: \fI<symbol>\fP - the given symbol is the name of a local variable on the namestack.
1131: .br
1132: \fI(prog . <n>)\fP - prog statement which binds <n> special variables
1133: .br
1134: \fI(do . <n>)\fP - head of a do statement which binds <n> special variables
1135: .br
1136: \fI(catcherrset . 0)\fP - catch or errset frame on stack
1137: .br
1138: \fI(lambda . <n>)\fP - lambda expression which binds <n> special variables
1139: .ip \fIg-labs\fP
1140: - this is a stack of labels.
1141: There is one entry in g-labs for every entry which is a list
1142: in g-locs.
1143: the forms of the entries are:
1144: .br
1145: \fInil\fP - no labels in this form
1146: .br
1147: \fI(endlab (real . gen) (real2 . gen2) ...)\fP - endlab is the label to go to
1148: to get out of this body. After this label will be code
1149: to unbind specials and pop off locals.
1150: The 'real' labels are those found in the code. the gen
1151: labels are those generated and put in the assembler code.
1152: .sh +0 Function\ compilation
1153: .pp
1154: The action d-exp takes when compiling an expression depends on the
1155: type of expression.
1156: For atoms (symbols and numbers) the compilation is very simple, it
1157: is just a matter of putting the value where g-loc specifies and
1158: then jumping if specified by g-cc.
1159: When the expression is a list, d-exp first macro
1160: expands the form and then looks at the first element of
1161: the list (if the list has not macro expanded to an atom).
1162: If the first element is a symbol then the list is
1163: is a function call.
1164: If the function is one of the functions which liszt knows how to open compile
1165: then liszt will call the particular routine designated to open
1166: compile this function.
1167: There are two classes of functions within liszt that
1168: do open compiling.
1169: The first class, the fl-expr class, are distinguished by names which
1170: begin with c-.
1171: These functions always generate
1172: code which returns the result in r0.
1173: They are not equipped to obey the contents of g-loc and g-cc.
1174: Thus d-exp, after calling one of these functions, must do what
1175: is necessary to obey g-loc and g-cc.
1176: The other class of open compiling functions, the fl-exprcc class (whose
1177: names begin with cc-),
1178: handle g-loc and g-cc.
1179: As a result these are usually much more complex and generate better code.
1180: .sh -1 Register\ Conventions
1181: .pp
1182: The register conventions used by liszt are an extension of those
1183: used by the C code.
1184: .ip \fIr0\fP
1185: - return value placed here
1186: .ip \fIr1,r2,r3,r4\fP
1187: - scratch registers.
1188: When long strings of
1189: .i car's
1190: or
1191: .i cdr's
1192: are done (such as
1193: .i caddadr )
1194: these registers are used in a least-recently-used fashion to access down
1195: the list.
1196: The compiler keeps track of the values in these registers but must
1197: assume that they are garbage after a function is called.
1198: .ip \fIr5\fP
1199: - fixnum accumulator.
1200: There a number of functions which work on fixnum's only and these
1201: usually put their result in r5.
1202: The assembler code function
1203: .i qnewint
1204: which returns a pointer to a cell containing a fixnum value (after
1205: checking if it is in the fixnum table), expects its argument to be
1206: in r5.
1207: .ip \fIr6\fP
1208: np
1209: .ip \fIr7\fP
1210: lbot.
1211: When calling a function, this register is set just before the function
1212: call, and after the function call its value is used to reset the value
1213: of np in order to pop the arguments off the namestack.
1214: .ip \fIr8\fP
1215: the literal table pointer.
1216: The compiler generates a table of all the literal lisp data
1217: which the compiled code might access.
1218: Upon function entry a pointer to the base of this table is put in r8.
1219: For example, if we compile \fI(setq\ x\ 'foo)\fP then we will
1220: need a pointer to the lisp symbol
1221: .i foo
1222: and if the symbol
1223: .i x
1224: as been declared special we will also need a pointer to
1225: .i x .
1226: .ip \fIr10\fP
1227: - upon function entry the value of lbot (r7) is put in r10.
1228: This allows us to reference the arguments to our function while
1229: using lbot to call other function.
1230: .sh +0 Addresses
1231: There are four types of addresses used internally in Franz:
1232: symbolic, intermediate addresses (iadr), extended intermediate (eiadr)
1233: and vax assembler format.
1234: .sh +1 Symbolic
1235: .pp
1236: These are the names of lisp objects, such as `a', `foo', 34,
1237: or 3.234234.
1238: A name is either a local variable, a special variable or a
1239: number. A number is either a small fixnum, large fixnum,
1240: bignum or floating point number.
1241: .sh +0 Intermediate\ address\ (IADR)
1242: .pp
1243: This type of address is generated from a symbolic address by
1244: .i d-loc,
1245: .i d-loclit
1246: and the routines
1247: .i d-simple
1248: and
1249: .i d-rsimple
1250: which
1251: call them. The forms are
1252: .ip \fINil\fP
1253: - the location or value of nil.
1254: .ip \fIT\fP
1255: - the location or value of t.
1256: .ip \fIreg\fP
1257: - register r0, which is where the result of function calls
1258: are stored.
1259: .ip \fIstack\fP
1260: - the address pointed to by np with np incremented after
1261: the value is stored. (i.e (r6)+)
1262: .ip \fIunstack\fP
1263: - the address one word below np (np is decremented before
1264: accessing. (i.e. -(r6))
1265: .ip \fI<symbol>\fP
1266: - this is just <symbol>. This allows strange forms to be
1267: represented directly.
1268: .ip \fI(stack\ n)\fP
1269: - The n'th value on the namestack for this function.
1270: The first value 0(r10) is (stack 1).
1271: .ip \fI(vstack\ n)\fP
1272: - The cdr of the n'th value on the namestack.
1273: That is, (stack 1) is *0(r10)
1274: .ip \fI(bind\ n)\fP
1275: - The value of the n'th value in
1276: the literal table. If
1277: this refers to a symbol, then this is the value
1278: of the symbol.
1279: If this refers to a list then this
1280: this is the cdr of the list (although this is a rare
1281: use). (bind 1) corresponds to *0(r8).
1282: .ip \fI(lbind\ n)\fP
1283: - The n'th value in the literal table. If
1284: this refers to
1285: object foo then this is the address of foo
1286: in memory.
1287: .ip \fI(fixnum\ n)\fP
1288: - This is the address of small fixnum n in memory.
1289: A small fixnum is in the range -1024 to 1023.
1290: .ip \fI(immed\ n)\fP
1291: - The is the immediate constant n.
1292: .sh +0 extended\ intermediate\ address\ (EIADR)
1293: .pp
1294: This address is generated from an IADR by e-cvt. It
1295: symbolically represents a vax address.
1296: .ip \fI<atom>\fP
1297: - This corresponds to <atom>.
1298: .ip \fI(n\ <atom>)\fP
1299: - This corresponds to n(<atom>)
1300: (stack n+1) and (lbind n+1) are converted to these forms.
1301: .ip \fI(n\ <atom1>\ <atom2>)\fP
1302: - This corresponds to n(<atom1>)[<atom2>]
1303: There is currently no IADR which generates this.
1304: .ip \fI(*\ n\ <atom>)\fP
1305: -This corresponds to *n(<atom>)
1306: (vstack n+1) and (bind n+1) are converted to these forms.
1307: .ip \fI(+\ <atom>)\fP
1308: - This corresponds to (<atom>)+.
1309: stack is converted to this form.
1310: .ip \fI(-\ <atom>)\fP
1311: - This corresponds to -(<atom>)
1312: unstack is converted to this form.
1313: .ip \fI($\ <numb>)\fP
1314: - This corresponds to $<atom>
1315: (immed <numb>) is converted to this form.
1316: .ip \fI(#\ <numb>)\fP
1317: - This corresponds to $<loc> where <loc> equals
1318: the base of the fixnums (0x1400) plus 4 * <numb>
1319: (fixnum <numb>) is converted to this form
1320: .ip \fI(*\ #\ <numb>)\fP
1321: - This corresponds to $<numb>. It is generated
1322: by d-rsimple occasionally when you ask for the
1323: cdr of a number (which you do sometimes when you
1324: are compiling fixnum operators).
1325: .sh +0 Vax\ Unix\ assembler\ addresses
1326: .pp
1327: The addresses are printed from a EIADR by e-cvtas. The conversions
1328: are shown in the above section.
1329: .sh -1 Function\ calling\ convention
1330: .sh +1 Function\ linkages
1331: .pp
1332: The function associated with a symbol is stored in the function
1333: definition slot of the symbol. If the function slot contains a
1334: list then the function is to be interpreted and its 'car' will
1335: be lambda, nlambda, lexpr or macro. If the function is compiled then
1336: the function definition slot will contain a binary object.
1337: A binary object
1338: is composed of two independent parts: the discipline and the entry.
1339: The discipline is one of:
1340: .ip \fIlambda\fP
1341: - a function whose arguments should be evaluated.
1342: .ip \fInlambda\fP
1343: - a function whose arguments should not be evaluated but
1344: which should be passed as a list
1345: .ip \fImacro\fP
1346: - a function which should be passed the unevaluated form
1347: being evaluated and whose result should be evaluated.
1348: .ip \fI\"subroutine\"\fP
1349: - a foreign function subroutine
1350: .ip \fI\"integer-function\"\fP
1351: - a foreign function returning an integer
1352: .ip \fI\"real-function"\fP
1353: - a foreign function returning a flonum.
1354: .pp
1355: A lexpr is not in the list as there is no difference to the caller
1356: between compiled lambda's and compiled lexprs.
1357: .sh +0 Transfer\ tables
1358: Most calls from compiled code to other lisp functions go through
1359: transfer tables. A transfer table entry is a pair: symbol, address
1360: of routine.
1361: When another lisp function is called it uses the
1362: .i calls
1363: instruction which will
1364: indirectly jump through the address in the transfer table. This
1365: address may point to the desired function or it may point to the
1366: interface routine. If a call ends up in the interface routine,
1367: then that routine will trace back through the call stack and eventually
1368: reach the tranfer table entry that it was 'called through'. Since the
1369: transfer table entry contains a symbol which names the function
1370: to be called, the interface routine can determine which routine
1371: was to have been called. If that routine is compiled then the
1372: interface routine can modify the transfer table so that a call
1373: through that table entry will go directly to the desired function.
1374: If the routine to be called is interpreted, or if the user has
1375: requested that transfer linkages should be disabled, then the
1376: interface routine will go through the 'funcall' function
1377: in the interpreter to continue the call.
1378: .sh +0 calling\ sequence\ in\ the\ compiler:
1379: .pp
1380: When transfer tables are used
1381: .(b
1382: \fBforeach\fP arg
1383: \fBcompute\fP arg and stack result using (r6)+
1384: for example: movl r0,(r6)+
1385: movab -n(r6),r7 where n = 4*number of args to fcn
1386: calls $0,*trantb+m where m is the index of the function
1387: in the transfer table.
1388: movl r7,r6 restore r6
1389: .)b
1390: .pp
1391: The compiler supports local functions, which are function accessible
1392: only within one file.
1393: Because they are not accessible from C code, we can use a very fast
1394: call and return sequence when calling them.
1395: To call a local function
1396: .(b
1397: \fBforeach\fP arg
1398: \fBcompute\fP and stack using (r6)+
1399: jsb LOCALNAME go directly to the function, it will
1400: restore r6 before it returns.
1401: .)b
1402: .pp
1403: The beginning of each function looks as follows.
1404: First for a non-lexpr function called in the standard way
1405: (topsim is the label jumped to when tail merging, it will be unique
1406: for each function; the brackets indicate the optional code which
1407: exists if the -p switch is given to liszt);
1408: .(b
1409: .word 0x5c0 # save r6, r7, r8, r10
1410: [ movab mcounts,r0 # if profiling, mcounts replaced by fasl
1411: jsb mcount ]
1412: movab linker,r8 # set up r8
1413: movl r7,r10 # set up oldlbot
1414: movab n(r10),r6 # n = 4*Number of args expected.
1415: topsim:
1416: .)b
1417: .pp
1418: Now for lexprs:
1419: .(b
1420: .word 0x5c0
1421: [ movab mcounts,r0 # if profiling. [mcounts replaced by fasl]
1422: jsb mcount ]
1423: movab linker,r8 # set up r8
1424: subl3 $4,r7,-(sp) # address one word below bottom of args
1425: topsim:
1426: movl r6,r10 # first free addr to arg base
1427: subl3 r7,r6,r0 # number of args * 4 into r0
1428: movab 0x1400(r0),(r6)+ # stack boxed number of args
1429: movl 0(r10),-(sp) # also store on stack so user can't clobber
1430: .)b
1431: .pp
1432: And finally for local functions:
1433: .(b
1434: movl r10,-(sp) # save r10
1435: movab -n(r6),r10 # set up arg base using arg top
1436: topsim:
1437: .)b
1438: .sh -1 Assembler\ file\ format
1439: .pp
1440: The liszt compiler generates a file which is in Unix assembler format.
1441: The Unix assembler converts that file into an object file which fasl
1442: then reads.
1443: Although the object file generated is a standard Unix object
1444: file (as defined in /usr/include/a.out.h), it is not of a
1445: format that the Unix ld loader can understand.
1446: This is because the requirements of a lisp object file are different
1447: from an object file of other languages.
1448: The
1449: run time semantics of lisp and the fact that lisp data must be protected
1450: from garbage collection are the principal differences.
1451: The unconventional object file created by the unix assembler
1452: is a result of the
1453: unconventional assembler input file.
1454: Next we will look at what must be put in the assembler file and how
1455: it is put there.
1456: .pp
1457: The assembler file must contain
1458: .ip \fIinstructions\fP
1459: - vax assembler code for the compiled functions.
1460: If there aren't any functions compiled, this can be empty.
1461: .ip \fIliterals\fP
1462: - lisp data which is referred to by compiled code
1463: .ip \fItransfer\ table\fP
1464: - the names of the functions which correspond to the calls through
1465: the transfer table.
1466: The instructions simply say 'call indirect through the nth transfer
1467: table entry'.
1468: .ip \fIfunction\ names\fP
1469: - the names of the functions which are being
1470: defined.
1471: .ip \fIload\ time\ forms\fP
1472: - in order to mimic the
1473: .i load
1474: function, fasl has to be able to evaluate lisp expressions at fasl
1475: time, so we must be able to store lisp expressions in the assembler
1476: file and indicate when they should be evaluated.
1477: .pp
1478: Based on the requirements above, the form of the assembler file
1479: is as described below.
1480: The assembler builds two segments: text and data.
1481: We put all of our information in the text segment.
1482: The compiler places some annotation strings in the data segment
1483: so that the object file can be identified, however the data segment
1484: is ignored by fasl.
1485: The format is
1486: .ip \fIcompiled\ instructions\fP
1487: The instructions for each compiled (non-local) function begins with
1488: .(b
1489: .globl F00003
1490: F00003:
1491: .word 0x5c0
1492: .)b
1493: The globl declaration and the fact that the symbol name begins
1494: with a F will tell fasl that this is the beginning of a lisp
1495: function.
1496: The symbols beginning with F must be unique within a file
1497: but may be duplicated in other files.
1498: The lisp name of the function will appear later.
1499: Next the instructions for the function are given.
1500: Only a small fixed set of external symbols may be referenced.
1501: The list is found in the code for nfasl.c and the common
1502: ones will be described below (soon).
1503: Labels should be given a name beginning with L and should
1504: be unique within the file.
1505: .ip \fItable\ sizes\fP
1506: somewhere in the file there should be a pair of 'set' assembler
1507: pseudo ops which describe the sizes of the literal table and
1508: transfer table.
1509: The form is this
1510: .(b
1511: .set linker_size 4
1512: .set trans_size 3
1513: .)b
1514: where linker_size is the number of entries in the literal table
1515: which will be required and trans_size is the number of entries
1516: in the transfer table which will be required.
1517: Those tables will be built by fasl.
1518: .ip \fIbinder\ table\fP
1519: - this table describes the order that the functions should be
1520: defined and forms evaluated.
1521: It is a table of longwords beginning at the symbol bind_org
1522: and ending when a -1 entry is seen.
1523: The meaning of the entries will be described below.
1524: .ip \fIlisp\ expression\ table\fP
1525: - this is a table of null terminated strings beginning at the
1526: symbol lit_org and ending at the symbol lit_end.
1527: Each string is read by the lisp read function (using the
1528: raw readtable).
1529: The first linker_size expressions are put in the literal table.
1530: The next trans_size expressions are the names of the
1531: functions to put in the transfer table.
1532: The remaining expressions correspond to the entries in the
1533: binder table.
1534: The binder entries are processed, one by one.
1535: Provided that the binder entry is not -1, an expression
1536: is read from the lisp expression table.
1537: Then if the binder table entry is 0, that expression is the name of
1538: a lambda type lisp function.
1539: A binary object is created, the discipline is set to lambda and
1540: the function address is set to the lexically next function
1541: defined in the
1542: file.
1543: If the binder entry is 1 then this is an nlambda function, and
1544: if the entry is 2 then this is a macro function.
1545: If the entry is 99 then the expression just read should be evaluated
1546: by the lisp function eval.
1547: .pp
1548: The lisp compiler normally puts the assembler format output file in /tmp
1549: and removes it when it is done.
1550: The -S switch will tell liszt to write the
1551: assembler file in the same place as
1552: the source file, and with the same root name but a .s extension.
1553: The -C file will tell the lisp compiler to comment the file as it
1554: generates it, making it easier to understand what is going on.
1555: Assume that the following is file foo.l:
1556: .(b
1557: (defun foo (x) (bar y) (baz k))
1558: (print (foo 3))
1559: (def test (nlambda (l) (print 'hithere) (foo 3)))
1560: .)b
1561: we now compile it with -SC
1562: .(b
1563: .globl F00007 #(fcn lambda foo)
1564: F00007:
1565: .word 0x5c0
1566: movab linker,r8
1567: movl r7,r10
1568: movab 4(r10),r6
1569: L00008:
1570: movl *0(r8),(r6)+ #(calling bar)
1571: #(from y to stack)
1572: movab -4(r6),r7
1573: calls $0,*trantb+0
1574: movl r7,r6
1575: movl *4(r8),(r6)+ #(calling baz)
1576: #(from k to stack)
1577: movab -4(r6),r7
1578: calls $0,*trantb+8
1579: movl r7,r6
1580: ret
1581: .globl F00009 #(fcn nlambda test)
1582: F00009:
1583: .word 0x5c0
1584: movab linker,r8
1585: movl r7,r10
1586: movab 4(r10),r6
1587: L00010:
1588: movl 8(r8),(r6)+ #(calling print)
1589: #(from 'hithere to stack)
1590: movab -4(r6),r7
1591: calls $0,*trantb+16
1592: movl r7,r6
1593: movl $5132,(r6)+ #(calling foo)
1594: #(from (fixnum 3) to stack)
1595: movab -4(r6),r7
1596: calls $0,*trantb+24
1597: movl r7,r6
1598: ret
1599: bind_org:
1600: .set linker_size, 3
1601: .set trans_size, 4
1602: .long 0
1603: .long 99
1604: .long 1
1605: .long -1
1606: lit_org:
1607: .asciz "y"
1608: .asciz "k"
1609: .asciz "hithere"
1610: .asciz "bar"
1611: .asciz "baz"
1612: .asciz "print"
1613: .asciz "foo"
1614: .asciz "foo"
1615: .asciz "(print (foo 3))"
1616: .asciz "test"
1617: lit_end:
1618: .data # this is just for documentation
1619: .asciz "@(#)Compiled by Lisp Compiler 7.1 on Sun Feb 21 17:51:54 1982"
1620: .asciz "@(#)decl.l 1.5 2/10/82"
1621: .asciz "@(#)array.l 1.1 9/25/81"
1622: .asciz "@(#)datab.l 1.1 9/25/81"
1623: .asciz "@(#)expr.l 1.1 9/25/81"
1624: .asciz "@(#)io.l 1.1 9/25/81"
1625: .asciz "@(#)funa.l 1.3 2/10/82"
1626: .asciz "@(#)funb.l 1.2 2/10/82"
1627: .asciz "@(#)func.l 1.2 2/10/82"
1628: .asciz "@(#)tlev.l 1.4 10/24/81"
1629: .asciz "@(#)fixnum.l 1.6 10/21/81"
1630: .asciz "@(#)util.l 1.2 10/7/81"
1631: .)b
1632: .sh +0 functions\ callable\ from\ compiled\ lisp\ code
1633: .sh +0 Object\ File\ Format
1634: .sh +0 Fasl
1635:
1636:
1637:
1638:
1639:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.