UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The interlisp virtual machine : study of its design and its implementation as multilisp Koomen, Johannes A.G.M. 1980

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1980_A6_7 K66.pdf [ 4.4MB ]
Metadata
JSON: 831-1.0051801.json
JSON-LD: 831-1.0051801-ld.json
RDF/XML (Pretty): 831-1.0051801-rdf.xml
RDF/JSON: 831-1.0051801-rdf.json
Turtle: 831-1.0051801-turtle.txt
N-Triples: 831-1.0051801-rdf-ntriples.txt
Original Record: 831-1.0051801-source.json
Full Text
831-1.0051801-fulltext.txt
Citation
831-1.0051801.ris

Full Text

C.I THE INTERLISP VIRTUAL MACHINE: A STUDY OF ITS DESIGN AND ITS IMPLEMENTATION AS MULTILISP by OHANNES A.G.M. KOOMEN B.Sc. THE UNIVERSITY OF BRITISH COLUMBIA 1978 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept this thesis as conforming to the required standard. THE UNIVERSITY OF BRITISH COLUMBIA July, 1980 (c) Johannes A.G.M. Koomen, 1980 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I ag ree that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . It i s u n d e r s t o o d that c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i thout my w r i t t e n p e r m i s s i o n . Department o f C o m p u t e r S c i e n c e The U n i v e r s i t y o f B r i t i s h Co lumbia 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 Date J u l y 2 2 , 1980 ABSTRACT A b s t r a c t machine d e f i n i t i o n s have been r e c o g n i z e d as c o n v e n i e n t and p o w e r f u l t o o l s f o r enhancing s o f t w a r e p o r t a b i l i t y . One such machine, the I n t e r l i s p V i r t u a l Machine, i s examined i n t h i s t h e s i s . We p r e s e n t the M u l t i l i s p System as an i m p l e m e n t a t i o n o f the V i r t u a l Machine and d i s c u s s some o f the d e s i g n c r i t e r i a and d i f f i c u l t i e s e n countered i n mapping the V i r t u a l Machine onto a p a r t i c u l a r environment. On the b a s i s o f our e x p e r i e n c e w i t h M u l t i l i s p we i n d i c a t e s e v e r a l weaknesses o f the V i r t u a l Machine which i m p a i r i t s adequacy as a b a s i s f o r a p o r t a b l e I n t e r l i s p System. i i i TABLE OF CONTENTS 1. I n t r o d u c t i o n 1 2. The I n t e r l i s p System 3 2.1 O r i g i n s of I n t e r l i s p 3 2.2 The I n t e r l i s p V i r t u a l Machine 6 2.3 The VM and the r e s t of I n t e r l i s p 7 3. The Design of the I n t e r l i s p V i r t u a l Machine 10 3.1 Machine A b s t r a c t i o n 10 3.2 The VM A b s t r a c t i o n 14 . 3.3 Data M a n i p u l a t i o n i n the VM 16 3.3.1 L i s t C e l l s 16 3.3.2 L i t e r a l Atoms 16 3.3.3 Numbers 17 3.3.4 S t r i n g s 18 3.3.5 F u n c t i o n a l Objects 20 3.3.6 Other Data Types 21 3.4 The Run-time Stack 22 3.4.1 A Model of M u l t i p l e Environments 22 3.4.2 The S p a g h e t t i Stack 25 3.4.3 Stack P o i n t e r s 27 3.4.4 A l t e r i n g the Flow of C o n t r o l 29 3.4.5 B l i p F i e l d s 30 3.4.6 Copying Frames 31 4. The Implementation of the V i r t u a l Machine 34 4.1 The R e p r e s e n t a t i o n of Objects 35 4.1.1 L i s t C e l l s 35 4.1.2 L i t e r a l Atoms 36 4.1.3 Numbers 37 4.2 Object Memory Management 38 4.2.1 Object Typing 39 4.2.2 Garbage C o l l e c t i o n 42 4.3 The S p a g h e t t i Stack 44 4.3.1 Stack Segments 45 4.3.2 Stack Elements 46 4.3.3 Stack Frames 47 4.3.4 Temporaries and B l i p F i e l d s 49 4.3.5 Argument B i n d i n g 51 4.4 The M u l t i l i s p I n t e r p r e t e r 52 4.4.1 The B a s i c Loop 52 4.4.2 Argument E v a l u a t i o n 54 4.4.3 F u n c t i o n I n v o c a t i o n 55 4.4.4 An Example: the Implementation of COND 56 Table of Contents i v 5. E v a l u a t i o n 59 5.1 The V i r t u a l Machine 59 5.1.1 System Dependencies 60 5.1.2 Complexity 61 5.1.3 Redundancy 63 5.1.4 Incompleteness 64 5.2 M u l t i l i s p 65 5.2.1 The Implementation Language 65 5.2.2 M u l t i l i s p and the VM 67 5.3 D i r e c t i o n s f o r Future Research 68 6. C o n c l u s i o n 70 B i b l i o g r a p h y 72 Appendix A SUBR's i n the VM and i n I n t e r l i s p 76 Appendix B Object R e p r e s e n t a t i o n i n M u l t i l i s p 78 Appendix C M u l t i l i s p L i s t Compaction 80 Appendix D M u l t i l i s p Stack Frame Layout 81 Appendix E M u l t i l i s p I n t e r p r e t e r Loop 84 Appendix F Annotated Trace of Stack Example 85 ACKNOWLEDGEMENTS I w i s h t o e x p r e s s my s i n c e r e g r a t i t u d e t o my s u p e r v i s o r s Dr. A l a n Mackworth and Dr. Ba r y P o l l a c k f o r t h e i r tremendous p a t i e n c e , i n s p i r a t i o n and c o n t i n u a l encouragement. I am a l s o g r e a t l y i n d e b t e d t o A l a n f o r h i generous f i n a n c i a l s u p p o r t i n the form o f a Research A s s i s t a n t s h i p as w e l l as ample computing r e s o u r c e s . I would l i k e t o thank Dan R a z z e l l f o r h i s e x c e l l e n t a s s i s t a n c e i n the development o f the s o f t w a r e , Dr. B i l l Havens f o r our many e n l i g h t e n i n g d i s c u s s i o n s and Da v i d Lowe f o r p r o v i d i n g some o f the b a s i c i d e a s f o r the i m p l e m e n t a t i o n . I d e d i c a t e t h i s t h e s i s t o my w i f e T r i s h a — her f a i t h , f o r b e a r a n c e and l o v i n g s u p p o r t have made i t a l l come t r u e 1 1. I n t r o d u c t i o n LISP remains today both a much c e l e b r a t e d and h i g h l y c o n t r o v e r s i a l programming language. Throughout i t s 20 y e a r s o f e x i s t a n c e , from i t s c o n c e p t i o n i n the l a t e 1950's by John McCarthy [McCarthy, 1960], who l a i d the t h e o r e t i c a l f o u n d a t i o n s , t o t o d ay's m u l t i t u d e o f v e r s i o n s , d e r i v a t i v e s and d i a l e c t s , such as MACLISP, QLISP, PLANNER, CONNIVER and INTERLISP, i t has remained s u r p r i s i n g l y s i m i l a r i n i t s b a s i c d e f i n i t i o n . Each o f the l a t e r systems c o n t a i n s a b a s i c LISP k e r n e l around which an ( o f t e n e l a b o r a t e ) c o l l e c t i o n o f programming and/or user s u p p o r t f a c i l i t i e s has been c o n s t r u c t e d . T h i s t h e s i s i s a st u d y o f the d e s i g n and i m p l e m e n t a t i o n o f the k e r n e l o f I n t e r l i s p as d e f i n e d i n "the I n t e r l i s p V i r t u a l Machine S p e c i f i c a t i o n " [Moore, 1976]. One o f our main c o n c e r n s w i l l be the p o r t a b i l i t y o f I n t e r l i s p , and t o what extend the V i r t u a l Machine promotes i t . I n Chapter 2 we s h a l l p r e s e n t a b r i e f h i s t o r i c o v e r v i e w o f I n t e r l i s p , i n t r o d u c e the I n t e r l i s p V i r t u a l Machine, and d e s c r i b e i n summary how the I n t e r l i s p System i n t e r a c t s w i t h the V i r t u a l Machine. The d e s i g n o f the I n t e r l i s p V i r t u a l Machine i s d i s c u s s e d i n Chapter 3, f o c u s i n g p r i m a r i l y on d a t a s p e c i f i c a t i o n s and c o n t r o l s p e c i f i c a t i o n s . Chapter 4 d i s c u s s e s M u l t i l i s p , a p a r t i a l i m p l e m e n t a t i o n o f the V i r t u a l Machine, p a r t i c u l a r l y the d i f f i c u l t i e s e n c o untered i n mapping the V i r t u a l Machine onto a p a r t i c u l a r environment and some o f the d e s i g n c r i t e r i a and d e c i s i o n s made i n t h i s i m p l e m e n t a t i o n . An e v a l u a t i o n o f the V i r t u a l Machine and o f the Chapter 1 implementation i s given i n some v i a b l e d i r e c t i o n s for t h e s i s i n Chapter 6 with a Chapter 5, as w e l l as a d i s c u s s i o n future research. We conclude th summary of our f i n d i n g s . 3 2. The I n t e r l i s p System 2.1 O r i g i n s of I n t e r l i s p In 1960 John McCarthy [McCarthy, 1960] p u b l i s h e d a paper that had a profound i n f l u e n c e on the A r t i f i c i a l I n t e l l i g e n c e community. T h i s paper presents a formal d e f i n i t i o n of r e c u r s i v e f u n c t i o n s f o r symbolic e x p r e s s i o n s and i n t r o d u c e s a programming system c a l l e d LISP embodying t h i s formalism. Two years l a t e r , the "LISP 1.5 Programmer's Manual" was p u b l i s h e d [McCarthy et a l . , 1962] which to date i s s t i l l an important and r e l e v a n t r e f e r e n c e f o r a l l beginning LISP'ers. The Manual d e s c r i b e s the LISP language i n a formal Meta-language, d e f i n e s the o p e r a t i o n of the LISP I n t e r p r e t e r , d e s c r i b e s added f e a t u r e s such as a r i t h m e t i c , a r r a y p r o c e s s i n g and the PROG f e a t u r e , and e x p l a i n s how to run the system. Although s t r o n g l y batch o r i e n t e d (cards and tapes f o r inp u t , p r i n t and punch f o r o u t p u t ) , t h i s e a r l y system running on the IBM 7090 c o n t a i n s most of what today would be co n s i d e r e d the e s s e n t i a l s of any LISP system i n c l u d i n g a compiler and a symbolic r e p r e s e n t a t i o n of Machine Language (LAP). Indeed, even today a l l LISP systems s t i l l i n c o r p o r a t e some o r i g i n a l LISP 1.5 or IBM 7090 i d i o s y n c r a s i e s ! In 1966 a v e r s i o n of LISP was developed by D.G. Bobrow and D.L. Murphy at B o l t , Beranek & Newman [Teitelman, 1978] which ran on D i g i t a l Equipment's PDP-1. T h i s v e r s i o n was e s s e n t i a l l y the same as the o r i g i n a l LISP 1.5. Chapter 2 4 An upwards c o m p a t i b l e v e r s i o n o f t h i s LISP was developed by Bobrow and Murphy i n 1967, c a l l e d 940 L I S P , f o r the SDS-940. T h i s v e r s i o n s u p p o r t e d many o f the f e a t u r e s t h a t c u r r e n t l y make up I n t e r l i s p : c o m p i l e d code was c o m p a t i b l e w i t h i n t e r p r e t e d code, e x t e n s i v e debugging f a c i l i t i e s were p r o v i d e d through u n i f o r m e r r o r p r o c e s s i n g , and the system c o n t a i n e d an e d i t o r s p e c i f i c a l l y d e s i g n e d f o r e d i t i n g s y m b o l i c e x p r e s s i o n s . But most i m p o r t a n t l y , 940 LISP was the f i r s t LISP system t h a t used v i r t u a l memory and s o f t w a r e p a g i n g [Bobrow & Murphy, 1967], thus g r e a t l y i n c r e a s i n g the amount o f f r e e s p a c e a v a i l a b l e t o the LISP programmer. The DWIM f a c i l i t y , w r i t t e n by W. T e i t e l m a n , was f i r s t i n c o r p o r a t e d i n 940 LISP i n 1968. DWIM (Do What I Mean) i s an au t o m a t i c s y n t a x e r r o r c o r r e c t i o n f a c i l i t y . A new LISP v e r s i o n , c o m p a t i b l e w i t h 940 LI S P , was devel o p e d by D.G. Bobrow, D.L. Murphy, A.K. H a r t l e y and W. T e i t e l m a n i n 1970. T h i s v e r s i o n , c a l l e d BBN LISP , was d e s i g n e d f o r the PDP-10 and ran under TENEX, a new and s o p h i s t i c a t e d o p e r a t i n g system d e s i g n e d by Bobrow and o t h e r s [1972]. F r e e d from p r e v i o u s hardware (memory) c o n s t r a i n t s , t he f o l l o w i n g y e a r s saw a r a p i d growth o f the system. I n 1971 a new and improved DWIM was i n s t a l l e d . The i n t r o d u c t i o n o f CLISP [ T e i t e l m a n , 1976] p r o v i d e d f o r a more A l g o l - l i k e program s y n t a x . The Programmer's A s s i s t a n t was i n t r o d u c e d i n 1972. (For a d e t a i l e d d e s c r i p t i o n o f these subsytems see [ T e i t e l m a n , 1 9 7 8 ] ) . Chapter 2 5 I n 1973 B o l t , Beranek & Newman and Xerox P a l o A l t o Research Center shared i n the maintenance and development o f BBN LISP. At t h i s time the name I n t e r l i s p was i n t r o d u c e d , both t o i n d i c a t e the j o i n t v e n t u r e and t o emphasize the h i g h l y i n t e r a c t i v e n a t u r e o f the system. The I n t e r l i s p C o m p i l e r was g r e a t l y improved i n 1974 through the n o t i o n o f b l o c k c o m p i l i n g , l i n k e d f u n c t i o n c a l l s and code swapping. B l o c k c o m p i l i n g i n v o l v e s c o m p i l i n g s e v e r a l f u n c t i o n s t o g e t h e r i n t o one b l o c k o f code. F u n c t i o n c a l l s w i t h i n the b l o c k are v e r y f a s t s i n c e s t a c k i n f o r m a t i o n f o r each i n v o c a t i o n i s kept t o a minimum, and the f u n c t i o n c a l l s t h emselves a r e l i n k e d . L i n k i n g f u n c t i o n s i n v o l v e s c o m p i l i n g f u n c t i o n c a l l s not by a p p l y i n g the f u n c t i o n a l i d e n t i f i e r but a p p l y i n g d i r e c t l y the c o n t e n t s o f the F u n c t i o n D e f i n i t i o n F i e l d o f the f u n c t i o n a l i d e n t i f i e r . The r e s u l t o f t h i s i s t h a t the c o n t e n t s o f the F u n c t i o n a l D e f i n i t i o n F i e l d need not be examined a t r u n t i m e . In 1975 the s p a g h e t t i s t a c k was i n c o r p o r a t e d i n t o I n t e r l i s p . T h i s s t a c k mechanism, based on the model o f m u l t i p l e s t a c k s as d e f i n e d by Bobrow and Wegbreit [1973] , i s d e s c r i b e d i n more d e t a i l i n Chapter 3. The system whose e v o l u t i o n has been d e s c r i b e d b r i e f l y here ( g e n e r a l l y r e f e r r e d t o as I n t e r l i s p - 1 0 ) i s r u n n i n g a t some dozen d i f f e r e n t l o c a t i o n s , on PDP-10's, under TENEX as w e l l as under the TOPS-20 o p e r a t i n g system. A number o f v e r s i o n s have been, or are i n the p r o c e s s o f b e i n g implemented, w i t h v a r y i n g Chapter 2 6 success, at the U n i v e r s i t y of Lynkoping i n Sweden, the U n i v e r s i t y of T e l A v i v i n I s r a e l , and the U n i v e r s i t y of B r i t i s h Columbia i n Vancouver. 2.2 The I n t e r l i s p V i r t u a l Machine In 1976 Xerox Palo A l t o Research Center p u b l i s h e d "The I n t e r l i s p V i r t u a l Machine S p e c i f i c a t i o n " [Moore, 1976]. The I n t e r l i s p V i r t u a l Machine (henceforth r e f e r r e d to as "the VM") was i n t r o d u c e d i n order to ensure c o m p a t i b i l i t y between v e r s i o n s and with other implementations. I t i s an attempt to capture i n a semi-formal way those p a r t s of I n t e r l i s p which are e s s e n t i a l to b r i n g up the remainder of the system. Acco r d i n g to the document's a b s t r a c t , "In order to implement the I n t e r l i s p System (...) on some p h y s i c a l machine, i t i s o n l y necessary to implement the I n t e r l i s p V i r t u a l Machine, s i n c e V i r t u a l Machine compatible source code f o r the r e s t of the I n t e r l i s p System can be obtained from p u b l i c l y a v a i l a b l e f i l e s . " The VM s p e c i f i e s a b s t r a c t o b j e c t s such as " I n t e g e r s " , " L i t e r a l Atoms", " L i s t C e l l s " , " S t r i n g s " , e t c . , a number of b a s i c LISP f u n c t i o n s to manipulate these o b j e c t s , the c o n t r o l flow and the method of v a r i a b l e b i n d i n g of the i n t e r p r e t e r , and input/output and i n t e r r u p t p r o c e s s i n g f a c i l i t i e s . A l t o g e t h e r some 250 LISP f u n c t i o n s (SUBR's) are d e f i n e d i n the document. Although the VM could be considered as a stand-alone LISP system, the r e a l power of I n t e r l i s p l i e s i n the a v a i l a b i l i t y of the packages d e s c r i b e d i n the p r e v i o u s s e c t i o n . Chapter 2 2.3 The VM and the r e s t o f I n t e r l i s p 7 I t can be seen from the above h i s t o r y t h a t the VM appeared a number o f y e a r s a f t e r most o f the I n t e r l i s p System was d e v e l o p e d . T h i s i s p r o b a b l y one o f the reasons t h a t the VM s p e c i f i c a t i o n s are n e i t h e r c o m p l e t e l y e r r o r - f r e e nor guaranteed t o be e i t h e r n e c e s s a r y or s u f f i c i e n t f o r implementing the remainder o f the I n t e r l i s p System. T h i s becomes i m m e d i a t e l y o b v i o u s when one s t u d i e s the f i r s t b o o t s t r a p f i l e , PUTDQ, one o f the above mentioned " V i r t u a l Machine c o m p a t i b l e s o u r c e code" f i l e s . T h i s f i l e i s the f i r s t f i l e t o be read a f t e r the VM has been implemented, and i t e n a b l e s the remainder o f the I n t e r l i s p System t o be read i n by means of the I n t e r l i s p f u n c t i o n LOAD. I t c o n t a i n s s e v e r a l i d i o s y n c r a s i e s t h a t are i l l u s t r a t i v e o f some o f the a f o r e m e n t i o n e d problems. For i n s t a n c e , the f i l e c o n t a i n s the f o l l o w i n g d e f i n i t i o n o f FIXP: [LAMBDA (X) (AND (NUMBERP X) (NOT (FLOATP X)) X] T h i s w i l l u n d o u b t e d l y work, because AND, NUMBERP, NOT and FLOATP are SUBR's d e f i n e d i n the VM. But so i s FIXP! In a s i m i l a r manner, IDIFFERENCE i s d e f i n e d as [LAMBDA (A B) (IPLUS A (MINUS B] Presumably the I n t e r l i s p - 1 0 C o m p i l e r produces good code f o r t h i s f u n c t i o n , but would i t p e r f o r m any b e t t e r than the SUBR Chapter 2 8 IDIFFERENCE as d e f i n e d i n the VM? Even worse i s the r e d e f i n i t i o n o f the VM SUBR SETPROPLIST: [LAMBDA (X Y) (CDR (FRPLACD X Y] where FRPLACD i s a f a s t ( i . e . , no t y p e c h e c k i n g ) non-VM v e r s i o n o f the SUBR RPLACD. T h i s d e f i n i t i o n i s p a r t i c u l a r l y o f f e n s i v e because i t makes s t r o n g assumptions about the u n d e r l y i n g r e p r e s e n t a t i o n o f both atoms and l i s t s . T h i s k i n d o f i n f o r m a t i o n ought t o be s t r i c t l y c o n f i n e d t o the VM i f the I n t e r l i s p System i s t o be p o r t a b l e . One o f the b i g g e s t o b s t a c l e s t o a c h i e v i n g a p o r t a b l e I n t e r l i s p System i s the c r e a t i o n o f an I n t e r l i s p C o m p i l e r . Because o f the sheer volume o f I n t e r l i s p s u p p o r t s o f t w a r e and the amount o f p r o c e s s i n g done by t h i s s o f t w a r e d u r i n g normal I n t e r l i s p s e s s i o n s , no i m p l e m e n t a t i o n can ever hope t o a t t a i n p r o d u c t i o n s t a t u s w i t h o u t the p r e s ence o f a c o m p i l e r . N a t u r a l l y , one would want t o implement such a c o m p i l e r i n I n t e r l i s p i t s e l f i n o r d e r t o keep the I n t e r l i s p k e r n e l as s m a l l as p o s s i b l e and t o improve m a i n t a i n a b i l i t y . The I n t e r l i s p - 1 0 System indeed c o n t a i n s a c o m p i l e r which produces code f o r the PDP-10. Many o f the a f o r e m e n t i o n e d f i l e s , i n c l u d i n g PUTDQ, r e l y t o some extend on the presence o f t h i s p a r t i c u l a r c o m p i l e r . S p e c i f i c a l l y , PUTDQ c o n t a i n s the f u n c t i o n LAPRD which not o n l y knows how t o read b i n a r y f i l e s produced by the c o m p i l e r , but i s i t s e l f d e f i n e d i n PDP-10 LAP ( L i s p Assembly Program)! Chapter 2 9 One way o f d e t e r m i n i n g how c l o s e l y the VM matches the r e s t o f the I n t e r l i s p System i s by comparing what each c o n s i d e r s t o be SUBR's. I t t u r n s out t h a t the VM [Moore, 1976] s p e c i f i e s 83 f u n c t i o n s (SUBR's) which the I n t e r l i s p R e f e r e n c e Manual [ T e i t e l m a n , 1978] c o n s i d e r s EXPR's (and hence these appear thr o u g h o u t the I n t e r l i s p System f i l e s t o be c o m p i l e d and l o a d e d through b o o t s t r a p p i n g ) ; the VM s p e c i f i e s 8 f u n c t i o n s t h a t are not r e c o g n i z e d as f u n c t i o n s i n the Manual; and the Manual e x p e c t s 41 SUBR's t o be d e f i n e d which do not appear i n the VM S p e c i f i c a t i o n ! (For a l i s t o f t h e s e f u n c t i o n s , see Appendix A.) The author s u s p e c t s t h a t c o n s i d e r a b l e e f f o r t i s r e q u i r e d t o b r i n g up the complete I n t e r l i s p System s t r i c t l y on the b a s i s o f the VM. Too many f i l e s c o n t a i n system-, machine-, and implementation-dependent " g l i t c h e s " such as i l l u s t r a t e d above. 10 3. The Design of the I n t e r l i s p V i r t u a l Machine 3.1 Machine A b s t r a c t i o n The n o t i o n of an A b s t r a c t Machine as an environment s p e c i f i c a t i o n has become i n c r e a s i n g l y popular i n the l a s t decade. Two such Machines that have gained wide acceptance are the PCODE Machine f o r the language P a s c a l [Nori et a l . , 1974], and the OCODE Machine f o r the language BCPL [Richards, 1969]. One key m o t i v a t i o n f o r A b s t r a c t Machines i s s i m p l i c i t y . The A b s t r a c t Machine i s d e f i n e d at a s u f f i c i e n t l y low l e v e l so that i t can be implemented on a r e a l machine with r e l a t i v e ease. As ' w e l l , the A b s t r a c t Machine i s s p e c i f i c a l l y designed with a p a r t i c u l a r h i g h - l e v e l language or system i n mind so that t h i s language i s (presumably) e a s i l y mapped i n t o the A b s t r a c t Machine. A second important m o t i v a t i o n f o r A b s t r a c t Machines i s p o r t a b i l i t y . A software system (e.g., a compiler, t e x t e d i t o r , database management system, etc.) may be co n s i d e r e d p o r t a b l e i f the complete system can be moved to a d i f f e r e n t machine and/or o p e r a t i n g system with l i t t l e or no m o d i f i c a t i o n s to the system r e q u i r e d . T h i s i s a l e s s r e s t r i c t i v e d e f i n i t i o n than machine independence, s i n c e f o r most u s e f u l systems there i s some i n t e r a c t i o n with the environment, and hence the environment i n t e r f a c e must almost always be modified f o r d i f f e r e n t machines and/or o p e r a t i n g systems. We co n s i d e r a system p o r t a b l e , then, (a) i f the system i s w r i t t e n i n a machine independent language, Chapter 3 11 (b) the environment i n t e r f a c e i s c l e a r l y i s o l a t e d and i t s f u n c t i o n a l i t y p r e c i s e l y d e f i n e d , and (c) no p a r t s o f the system make any assumptions about the u n d e r l y i n g s t r u c t u r e o f the environment but r e l y s o l e l y on the s p e c i f i e d environment i n t e r f a c e . N a t u r a l l y , t h e r e can be some b a s i c s p e c i f i c a t i o n s which d e f i n e the scope o f p o r t a b i l i t y and on which the e n t i r e system may r e l y (such as b y t e - and w o r d s i z e , presence o f a r e a l - t i m e c l o c k , presence o f secondary s t o r a g e , e t c . ) . LISP has o c c u p i e d a somewhat unorthodox p o s i t i o n i n the w o r l d o f programming languages. Most o f the commercial a p p l i c a t i o n s o f t w a r e r e l i e s on s t a n d a r d c o m p i l e d language environments. As an i n t e r p r e t e d system, LISP has a d i s t i n c t l y d i f f e r e n t f l a v o r . I t has been used p r i m a r i l y i n r e s e a r c h and academic environments f o r s o f t w a r e p r o j e c t s t h a t were h a r d l y ever meant t o l a s t beyond a few t e s t r u n s . I n o t h e r words, the A r t i f i c i a l I n t e l l i g e n c e community, as the p r i n c i p a l user o f L I S P , most o f t e n uses i t t o e x p l o r e and t e s t new models and t h e o r i e s , w i t h o u t much c a r e f o r p r o d u c t i o n q u a l i t y i m p l e m e n t a t i o n s . The s o f t w a r e i s i n a c o n t i n u o u s s t a t e o f f l u x , and i s u s u a l l y p r i v a t e t o a r e s e a r c h e r , a s m a l l r e s e a r c h team, or a department. The need f o r s o f t w a r e s h a r i n g beyond these s m a l l groups was h a r d l y ever p r e s e n t . Hence, p o r t a b i l i t y has not been such an i m p o r t a n t i s s u e f o r L I S P ' e r s as i t has been f o r more c o m m e r c i a l l y o r i e n t e d s o f t w a r e d e v e l o p e r s . T h i s s i t u a t i o n i s q u i c k l y c h a n g i n g . Chapter 3 12 The c o m p l e x i t y o f A l programs and systems i s r a p i d l y i n c r e a s i n g . More and more r e s e a r c h e r s are b e g i n n i n g t o f e e l the need f o r e x t e n s i v e system s u p p o r t i n o r d e r t o d e v e l o p , m a i n t a i n and expand t h e i r programs. The need f o r good LISP c o m p i l e r s i s growing as w e l l , i n t h a t the i n c r e a s i n g l y complex programs need f a s t e r e x e c u t i o n i n o r d e r t o remain u s a b l e , or because o f r e a l - t i m e c o n s t r a i n t s . At the same t i m e , the A l community i s r e a l i z i n g t h a t the e f f o r t o f d e v e l o p i n g e x t e n s i v e system s u p p o r t s o f t w a r e , such as I n t e r l i s p p r o v i d e s , i s q u i t e c o n s i d e r a b l e . The need f o r s h a r i n g i s becoming o b v i o u s . Both the A l community and the commercial w o r l d are becoming a c u t e l y aware o f the importance o f p o r t a b i l i t y . Not o n l y i s t h e r e the need f o r p o r t a b i l i t y a c r o s s l o c a t i o n s ( r u n n i n g on d i f f e r e n t machines and/or d i f f e r e n t o p e r a t i n g systems) so t h a t o t h e r s may use one's s o f t w a r e , which we c o u l d term " s p a t i a l p o r t a b i l i t y " . There i s a l s o the need f o r " t e m p o r a l p o r t a b i l i t y " — the a b i l i t y t o t r a n s p o r t e x i s t i n g s o f t w a r e t o new machines as they are developed so t h a t one can hope t o use one's own s o f t w a r e over the y e a r s . The i n c r e d i b l e advances i n the e l e c t r o n i c s i n d u s t r y made r e c e n t l y have caused a f l o o d o f more and more p o w e r f u l machines t o appear on the market. I t i s becoming q u i t e o b v i o u s t h a t the c u r r e n t c r i s i s i n s o f t w a r e development i s t o a l a r g e e x t e n t due t o the f a c t t h a t so much e x i s t i n g s o f t w a r e must be r e w r i t t e n , or adapted beyond r e c o g n i t i o n , t o accomodate new machines and e n v i r o n m e n t s . Chapter 3 ' 13 As was mentioned above, some f a i r l y s u c c e s s f u l attempts at p o r t a b i l i t y e x i s t i n the form of PCODE f o r P a s c a l systems and OCODE f o r the BCPL language. The c l e a r e s t example of the v i a b i l i t y of t h i s approach i s the overwhelming success of UCSD P a s c a l [Bowles, 1977] which i s becoming one of the most popular languages a v a i l a b l e on microcomputers. A few years ago at the U n i v e r s i t y of C a l i f o r n i a at San Diego, a complete P a s c a l environment was developed (Pascal to PCODE t r a n s l a t o r , t e x t e d i t o r with knowledge of P a s c a l source code, symbolic debugger, a f i l e system, and a PCODE i n t e r p r e t e r ) . T h i s environment was o r i g i n a l l y developed f o r the DEC PDP-11 but i s now a v a i l a b l e on at l e a s t 5 d i f f e r e n t p r o c e s s o r s (8080, Z80, 6502, 6800, 9900; soon on Z8000 and 68000). For each new p r o c e s s o r , o n l y the PCODE i n t e r p r e t e r and some c l e a r l y d e f i n e d I/O and i n t e r r u p t r o u t i n e s needed to be w r i t t e n or adapted to make the complete system a v a i l a b l e . The argument a g a i n s t PCODE as being too slow when i n t e r p r e t e d was n u l l i f i e d when Western D i g i t a l produced the P a s c a l Microengine, a processor which c o n t a i n e d PCODE i n microcode. The PERQ w o r k s t a t i o n from Three R i v e r s Computer C o r p o r a t i o n a l s o runs microcoded PCODE d i r e c t l y at a ra t e of 1 m i l l i o n PCODE i n s t r u c t i o n s per second [Meyers, 1980]. A s i m i l a r approach has been made i n recent years f o r LISP systems. At MIT, r e s e a r c h e r s are working on the development of the L i s p Machine [Weinreb & Moon, 1979] which i s a small p r o c e s s o r e x e c u t i n g LISP p r i m i t i v e s and support code i n microcode. At Xerox PARC a s i m i l a r p r o j e c t has been undertaken Chapter 3 14 [Deutsch, 1978]. The p o i n t o f t h i s approach i s that once a s u i t a b l e A b s t r a c t Machine has been d e f i n e d i t can be i n t e r p r e t e d or emulated on a l a r g e v a r i e t y of machines. So long as the r e s t of the system o n l y i n t e r a c t s with the A b s t r a c t Machine changing the r e a l machine w i l l be completely t r a n s p a r e n t . At the same time i t has been demonstrated that the A b s t r a c t Machine concept has added advantages. . Among o t h e r s , [Deutsch, 1973] has shown that programs can be represented very compactly by the i n s t r u c t i o n s of a s u i t a b l e A b s t r a c t Machine, much more so than by those of any r e a l machine. And G r i s s and Hearn [1979], who developed a p o r t a b l e compiler f o r Standard L i s p , have shown adequately t h a t code o p t i m i z a t i o n s can be made q u i t e e f f e c t i v e l y on the l e v e l of the A b s t r a c t Machine, or even at the LISP l e v e l (e.g., removal of t a i l r e c u r s i o n , c o m p i l i n g f o r value or e f f e c t , and standard o p t i m i z a t i o n techniques • such as removing loop i n v a r i a n t s ) . A t h i r d advantage of the A b s t r a c t Machine approach i s t h a t , s i n c e almost the e n t i r e system i s implemented i n LISP, the system i s e a s i l y maintained, m o d i f i e d or amended using a l l of the higher l e v e l LISP support software. 3.2 The VM A b s t r a c t i o n The VM goes c o n s i d e r a b l y beyond the A b s t r a c t Machine concept as d e f i n e d above. I t i s much more an a b s t r a c t i o n of the b a s i c s of a LISP system than an a b s t r a c t i o n of a machine on which a LISP system can e a s i l y be r e a l i z e d . Two important i n d i c a t i o n s of support f o r t h i s view e x i s t . F i r s t of a l l , a Chapter 3 15 c o n s i d e r a b l e p a r t o f the VM S p e c i f i c a t i o n i s d e d i c a t e d t o the d e s c r i p t i o n o f I n t e r l i s p f u n c t i o n s r a t h e r than a machine on which th e s e f u n c t i o n s are t o be implemented. These range from s i m p l e , b a s i c f u n c t i o n s such as CAR, CDR and CONS, t o complex subprograms t o p e r f o r m s t a c k scans and b a c k t r a c e s , s t r i n g m a n i p u l a t i o n s , f i l e h a n d l i n g , complete I/O, e t c . The second i n d i c a t i o n stems from the f a c t t h a t the c o m p i l e r i s not a f u n c t i o n a l p a r t o f the VM. The VM p l a c e s a few r e s t r i c t i o n s on a c o m p i l e r i f one i s p r e s e n t , but t h e r e i s no i n d i c a t i o n t h a t any c o m p i l e r would c o m p i l e I n t e r l i s p code i n t o V i r t u a l Machine code! S i n c e the c o m p i l e r (or a t l e a s t an assembler) i s not an i n t e g r a l p a r t o f the VM, one would assume i t i s w r i t t e n i n I n t e r l i s p i t s e l f . T h i s would d e f y the n o t i o n o f the V i r t u a l Machine as the l o w e s t , b a s i c , s e l f - c o n t a i n e d l e v e l o f the I n t e r l i s p System f o r two r e a s o n s : a. The c o m p i l e r must assume knowledge o f the u n d e r l y i n g r e a l machine, as w e l l as i n t i m a t e knowledge o f the p a r t i c u l a r s o f the i m p l e m e n t a t i o n o f the V i r t u a l Machine. b. The V i r t u a l Machine must be m o d i f i e d t o i n c o r p o r a t e knowledge o f the c o m p i l e r , and o f what i t p r o d u c e s , so t h a t the VM f u n c t i o n s ARGTYPE, FNTYP, CCODEP, ARGLIST and NARGS can r e c o g n i z e a CEXPR f u n c t i o n o b j e c t , b u t , more i m p o r t a n t l y , so t h a t the VM f u n c t i o n s EVAL, APPLY, and APPLY* know what t o do w i t h i t ! Chapter 3 16 3.3 Data M a n i p u l a t i o n i n the VM Although not a typed language i n the t r a d i t i o n a l sense, I n t e r l i s p p r o v i d e s an ample c o l l e c t i o n of b a s i c data types, as w e l l as f a c i l i t i e s f o r d e f i n i n g new types. A l l b a s i c types are d e f i n e d i n the V i r t u a l Machine, and f u n c t i o n s are d e s c r i b e d f o r the c r e a t i o n , a c c e s s i n g , and m o d i f i c a t i o n of i n s t a n c e s of these types. Some of these data types are d e s c r i b e d i n the f o l l o w i n g s u b s e c t i o n s . The VM f u n c t i o n TYPENAME r e t u r n s the name of the data type of the argument. 3.3.1 L i s t C e l l s These o b j e c t s , with typename LISTP, are the t r a d i t i o n a l LISP Cons c e l l s . They have the standard two f i e l d s Car and Cdr, and are manipulated by the VM f u n c t i o n s LISTP, CAR, CDR, CONS, RPLACA, RPLACD and LIST. The VM a l s o maintains a count of L i s t c e l l s c r e a t e d which i s accessable and m o d i f i a b l e through the f u n c t i o n CONSCOUNT. 3.3.2 L i t e r a l Atoms L i t e r a l Atoms, with typename LITATOM, are the t r a d i t i o n a l LISP i d e n t i f i e r s . Recognized by t h e i r Pname ( p r i n t name), they are unique (no two atoms can e x i s t with the same Pname), and e t e r n a l once c r e a t e d ( i . e . they can not be removed from the system). L i t e r a l Atoms have three f i e l d s which can be manipulated by the user: a "top l e v e l v a l u e " f i e l d , accessed through the f u n c t i o n s GETTOPVAL and SETTOPVAL; a "property l i s t " f i e l d , a c c e s s a b l e through GETPROPLIST and SETPROPLIST; and a Chapter 3 17 " f u n c t i o n d e f i n i t i o n " f i e l d , a c c e s s e d through GETD and PUTD. 3.3.3 Numbers I n t e r l i s p r e c o g n i z e s two t y p e s o f i n t e g e r s : S m a l l I n t e g e r s , w i t h typename SMALLP, and Large I n t e g e r s , w i t h typename FIXP. N o r m a l l y , the r e p r e s e n t a t i o n o f i n t e g e r s , r e q u i r e s a "box" i n which t h e s e i n t e g e r s can be d e p o s i t e d . The box can be r e c o g n i z e d as such and can be passed around f r e e l y w i t h o u t danger o f m i s i n t e r p r e t a t i o n (which would be the case i f the i n t e g e r i t s e l f would be passed a r o u n d ) . Large I n t e g e r s (FIXP) are d e p o s i t e d i n such boxes. S m a l l I n t e g e r s , however, a r e i n t e g e r s o f an ( u n s p e c i f i e d ) range which are m o d i f i e d c o n s i s t e n t l y t o become a d d r e s s e s i n t o i l l e g a l space (e.g., memory o c c u p i e d by the i n t e r p r e t e r i t s e l f ) . For t h i s l i m i t e d range o f a d d r e s s e s no wrong i n t e r p r e t a t i o n i s p o s s i b l e , so they can be passed around as i f they were p o i n t e r s t o o b j e c t s . S i n c e s m a l l i n t e g e r s (those around zero) occur the most f r e q u e n t l y , i t pays o f f t o m o d i f y these t o become fa k e a d d r e s s e s . T h i s i s a r e l a t i v e l y cheap p r o c e d u r e and does not r e q u i r e the s t o r a g e a l l o c a t o r (and p o s s i b l y the garbage c o l l e c t o r ) . The V i r t u a l Machine r e q u i r e s C h a r a c t e r Codes (numeric r e p r e s e n t a t i o n s o f c h a r a c t e r s ) t o be o f type SMALLP. (T h i s was presumably done because a l a r g e s e c t i o n o f I/O implemented i n I n t e r l i s p r e l i e s on C h a r a c t e r Code m a n i p u l a t i o n . ) O b v i o u s l y t h i s i s a v i o l a t i o n o f the v i r t u a l n a t u r e o f the VM s i n c e i t makes assumptions about the a d d r e s s i n g s t r u c t u r e o f the u n d e r l y i n g machine. Omission o f the SMALLP t y p e , however, w i l l Chapter 3 18 c r e a t e havoc i n the h i g h e r l e v e l I n t e r l i s p code, s i n c e EQ would f a i l on two C h a r a c t e r Codes r e p r e s e n t i n g the same c h a r a c t e r ! The b a s i c f u n c t i o n s f o r m a n i p u l a t i o n o f I n t e g e r s a re SMALLP, FIXP , F I X , IGREATERP, ILESSP, IPLUS, IDIFFERENCE, IMINUS, ITIMES, IQUOTIENT, and IREMAINDER. I n a d d i t i o n the f o l l o w i n g b i t m a n i p u l a t i o n f u n c t i o n s (which take I n t e g e r s as arguments) are p r o v i d e d : LOGAND, LOGOR, LOGXOR, LLSH ( L o g i c a l L e f t S H i f t ) , LRSH, LSH ( a r i t h m e t i c L e f t S H i f t ) and RSH. F l o a t i n g p o i n t numbers, w i t h typename FLOATP, are always boxed. F u n c t i o n s s i m i l a r t o the I n t e g e r ones are p r o v i d e d : FLOATP, FLOAT, FGREATERP, FLESSP, FPLUS, FDIFFERENCE, FMINUS, FTIMES, FQUOTIENT and FREMAINDER. The VM m a i n t a i n s a count o f both FIXP and FLOATP boxes, which i s a c c e s s a b l e through the f u n c t i o n BOXCOUNT. In a d d i t i o n t o these t y p e - s p e c i f i c numeric f u n c t i o n s , the VM s p e c i f i e s s e v e r a l m i x e d - m o d e - a r i t h m e t i c f u n c t i o n s , v i z . NUMBERP, MINUSP, GREATERP, LESSP, PLUS, DIFFERENCE, MINUS, TIMES, QUOTIENT, and REMAINDER, as w e l l as the f u n c t i o n s EXPT, SQRT, LOG, ANTILOG, SIN, COS, TAN, ARCSIN, ARCCOS, ARCTAN. A (pseudo-) random number g e n e r a t o r i s a l s o p r o v i d e d (RAND and RANDSET). The f u n c t i o n MINUSP i s s p e c i f i e d i n the VM i n terms o f FMINUSP and IMINUSP, a l t h o u g h those are not s p e c i f i e d as VM f u n c t i o n s ! 3.3.4 S t r i n g s S t r i n g s i n I n t e r l i s p have a two l e v e l r e p r e s e n t a t i o n . The l o w e s t l e v e l i s formed by a sequence o f c h a r a c t e r s , somewhere i n Chapter 3 19 memory. I n t e r l i s p o b j e c t s o f type STRINGP form the second l e v e l . These o b j e c t s have t h r e e f i e l d s : a " s o u r c e " f i e l d which p o i n t s t o a sequence o f c h a r a c t e r s ; a " p o s i t i o n " f i e l d c o n t a i n i n g the i n d e x i n t o the c h a r a c t e r sequence o f the s t a r t i n g c h a r a c t e r o f the S t r i n g ; and the " c h a r c o u n t " f i e l d , which i n d i c a t e s the number o f c h a r a c t e r s i n the S t r i n g . Two o b j e c t s o f type STRINGP may share the same sequence o f c h a r a c t e r s , hence m o d i f i c a t i o n s made to one S t r i n g may a f f e c t o t h e r S t r i n g s . The " s o u r c e " f i e l d may, presumably f o r reasons o f e f f i c i e n c y , p o i n t t o the c h a r a c t e r sequence r e p r e s e n t i n g the Pname o f a LITATOM. However, i n t h a t case a S t r i n g f u n c t i o n which m o d i f i e s c h a r a c t e r sequences f i r s t c r e a t e s a copy o f the c h a r a c t e r sequence and d e p o s i t s a p o i n t e r i n the " s o u r c e " f i e l d b e f o r e making the m o d i f i c a t i o n . O b v i o u s l y , any o t h e r S t r i n g s t i l l p o i n t i n g t o the Pname c h a r a c t e r sequence i s not a f f e c t e d when t h i s happens. The V i r t u a l Machine s p e c i f i e s the f o l l o w i n g S t r i n g m a n i p u l a t i o n f u n c t i o n s : STRINGP, STREQUAL, MKSTRING, CONCAT, RPLSTRING, SUBSTRING, GNC (Get Next C h a r a c t e r ) and GLC (Get L a s t C h a r a c t e r ) . P a t t e r n matching i s p r o v i d e d through the f u n c t i o n s STRPOS and STRPOSL. The l a t t e r f u n c t i o n i s c o n t r o l l e d by a b i t t a b l e . T h i s i s a r a t h e r s t r a n g e e n t i t y i n the VM — i t i s an o b j e c t the f u n c t i o n a l i t y o f which i s c l e a r l y d e f i n e d , which can be c r e a t e d and m o d i f i e d by the f u n c t i o n MAKEBITTABLE, and used by the f u n c t i o n STRPOSL, and y e t the VM does not r e c o g n i z e i t as a v a l i d o b j e c t ( i . e . , the f u n c t i o n BITTABLEP cannot be d e f i n e d ) ! Chapter 3 20 3.3.5 F u n c t i o n a l O b j e c t s The f l o w o f c o n t r o l w i t h i n the VM i s governed j o i n t l y by the a p p l i c a t i o n o f f u n c t i o n a l o b j e c t s and the b e h a v i o u r o f the run- t i m e s t a c k . S i n c e the a p p l i c a t i o n o f f u n c t i o n a l o b j e c t s i s q u i t e t r a d i t i o n a l we r e f e r the i n t e r e s t e d reader t o [ A l l e n , 1978] f o r a comprehensive e x p l a n a t i o n . The VM r e c o g n i z e s f o u r t y p e s o f F u n c t i o n a l O b j e c t s , v i z . EXPR's, CEXPR*s, SUBR's and FUNARG's. EXPR's are not a type by t h e m s e l v e s , but are L i s t s which are c o n c e p t u a l i z e d as F u n c t i o n a l O b j e c t s . F u r t h e r d i s t i n c t i o n o f F u n c t i o n a l O b j e c t s i s made based on the method o f t h e i r parameter b i n d i n g , namely whether the v a l u e o f the arguments (e.g., EXPR's) or the arguments themselves (e.g., FEXPR's) s h o u l d be bound t o the p a r a m e t e r s , and whether the F u n c t i o n a l O b j e c t t a k e s a d e f i n i t e ( e . g . , EXPR's) or an i n d e f i n i t e number o f arguments (e.g., EXPR*). S i m i l a r l y , the s u b c a t e g o r i e s CEXPR, CEXPR*, CFEXPR, CFEXPR*, SUBR, SUBR*, FSUBR and FSUBR* are r e c o g n i z e d . The CEXPR c o m b i n a t i o n s r e f e r t o c o m p i l e d v e r s i o n s o f t h e i r EXPR c o u n t e r p a r t s ; the SUBR c o m b i n a t i o n s are f u n c t i o n s t h a t were hand-coded and assembled by the implementor. A FUNARG o b j e c t i s a l i s t whose f i r s t element i s the L i t e r a l Atom FUNARG, whose second element i s a F u n c t i o n a l O b j e c t , and whose t h i r d element i s a S t a c k P o i n t e r which a c t s as an environment d e s c r i p t o r . FUNARG's w i l l be d e s c r i b e d i n more d e t a i l i n s e c t i o n 3.4.4. I n t e r l i s p does not r e q u i r e the number o f arguments t o match the number o f f o r m a l parameters i n the case o f s p r e a d - t y p e F u n c t i o n a l O b j e c t s . I f more arguments are s u p p l i e d than can be Chapter 3 21 bound they are i g n o r e d (but e v a l u a t e d i n the case o f E v a l - t y p e F u n c t i o n a l , O b j e c t s ! ) . I f l e s s arguments than parameters are s u p p l i e d , the r e m a i n i n g parameters are bound t o NIL. T h i s p r o v i d e s a f l e x i b l e and c o n v e n i e n t way o f s u p p l y i n g d e f a u l t s t o f u n c t i o n s . 3.3.6 Other Data Types The r e m a i n i n g b a s i c d a t a t y p e s r e c o g n i z e d by the VM are A r r a y s (ARRAYP), Hash A r r a y s (HARRAYP), S t a c k P o i n t e r s (STACKP), Read T a b l e s (READTABLEP) and T e r m i n a l T a b l e s (TERMTABLEP). A r r a y s are f u r t h e r d i s t i n g u i s h e d by t h e i r c o n t e n t s — e i t h e r I n t e g e r s or ( p o i n t e r s to) any I n t e r l i s p o b j e c t . Both k i n d s o f A r r a y have the same type name. The user can d i s t i n g u i s h them by means o f the f u n c t i o n ARRAYTYP. For a d e s c r i p t i o n o f Hash A r r a y s we r e f e r the i n t e r e s t e d r e ader t o Bobrow [1975]. Stack P o i n t e r s w i l l be d e s c r i b e d i n s e c t i o n 3.4.3. Read T a b l e s and T e r m i n a l T a b l e s are used by the i n p u t r o u t i n e s — the former d e t e r m i n e s the I n t e r l i s p s y n t a x ( i n c l u d i n g m a c r o s ) , the l a t t e r c o n t r o l s the a c t i o n s performed on i n t e r r u p t s i n i t i a t e d from the u s e r ' s t e r m i n a l . The VM a l l o w s the user t o d e f i n e h i s own d a t a t y p e s w i t h ' the f u n c t i o n DECLAREDATATYPE. T h i s f u n c t i o n t a k e s as arguments the name o f the new type and a l i s t o f f i e l d s p e c i f i c a t i o n s . V a l i d f i e l d s p e c i f i c a t i o n s are POINTER, FIXP, FLOATP, (SIGNEDBIT j ) and (BIT j ) . The r e v i s e d e d i t i o n o f the VM [Moore, 1979] o m i t s the (SIGNEDBIT j ) as a v a l i d f i e l d s p e c i f i c a t i o n a l t h o u g h some f u n c t i o n s o p e r a t i n g on user d e f i n e d d a t a t y p e s s t i l l Chapter 3 22 recognize i t . Instances of user data types can can be c r e a t e d and i n i t i a l i z e d with the f u n c t i o n NCREATE and t h e i r f i e l d s may be accessed and m o d i f i e d with the f u n c t i o n s FETCHFIELD and REPLACEFIELD, r e s p e c t i v e l y . 3.4 The Run-time Stack 3.4.1 A Model of M u l t i p l e Environments The I n t e r l i s p run-time stack s t r u c t u r e i s based on a model of m u l t i p l e environments proposed by D.G. Bobrow and B. Wegbreit [1973]. T h i s model was d e f i n e d i n r e c o g n i t i o n of the f a c t t h a t f o r many c o n t r o l and access environment s t r u c t u r e s the t r a d i t i o n a l l a s t - i n f i r s t - o u t stack d i s c i p l i n e i s inadequate. Many recent programming techniques such as b a c k t r a c k i n g , multiprogramming and the use of c o r o u t i n e s r e q u i r e that stack storage space a s s o c i a t e d with f u n c t i o n a c t i v a t i o n s be r e t a i n a b l e independent of the flow of c o n t r o l . The Bobrow and Wegbreit model allows f o r a r b i t r a r y r e t e n t i o n of a c t i v a t i o n r e c o r d s , y e t behaves e x a c t l y l i k e a LIFO stack i f r e t e n t i o n i s not r e q u i r e d . For each f u n c t i o n a c t i v a t i o n two storage components are d i s t i n g u i s h e d , v i z . data storage and c o n t r o l s t o r a g e . Data storage i s reserved f o r f u n c t i o n parameters and named v a r i a b l e s l o c a l to the f u n c t i o n . T h i s storage i s f i x e d i n s i z e s i n c e these storage requirements do not change d u r i n g the execution of the f u n c t i o n body. C o n t r o l storage i s used f o r temporary int e r m e d i a t e r e s u l t s of computation p l u s any other r e l e v a n t i n f o r m a t i o n p e r t a i n i n g to the f u n c t i o n a c t i v a t i o n and hence Chapter 3 23 v a r i e s i n s i z e d u r i n g the e x e c u t i o n o f the f u n c t i o n body. I n the Bobrow and Wegbreit model d a t a s t o r a g e i s c o n t a i n e d i n the " b a s i c frame" and c o n t r o l s t o r a g e i n the "frame e x t e n s i o n " . The frame e x t e n s i o n c o n t a i n s t h r e e p o i n t e r s t o o t h e r frames. The BLINK i s a p o i n t e r t o the a s s o c i a t e d b a s i c frame. The ALINK i s a p o i n t e r t o a c h a i n o f frame e x t e n s i o n s c o n s t i t u t i n g the a c c e s s environment. T h i s c h a i n i s used f o r a c c e s s i n g the v a l u e s o f f r e e v a r i a b l e s ( i . e . , a l l v a r i a b l e s t h a t are not bound i n the f u n c t i o n module's own b a s i c f r a m e ) . The CLINK i s a p o i n t e r t o a c h a i n o f frame e x t e n s i o n s c o n s t i t u t i n g the c o n t r o l environment. When e x e c u t i o n o f the f u n c t i o n body t e r m i n a t e s c o n t r o l i s passed back t o the f u n c t i o n whose frame e x t e n s i o n i s the f i r s t i n the c o n t r o l c h a i n . T h i s method o f g e n e r a l i z e d r e t u r n i s made p o s s i b l e through the e x i s t e n c e o f the " C o n t i n u a t i o n P o i n t " f i e l d i n the frame e x t e n s i o n . A t the time o f f u n c t i o n i n v o c a t i o n the c a l l e r r a t h e r than the c a l l e e saves the c o n t i n u a t i o n p o i n t o f the c o m p u t a t i o n i n h i s own frame e x t e n s i o n . T h i s a l l o w s the c a l l e r t o be r e a c t i v a t e d independent o f whether c o n t r o l i s r e t u r n i n g from the c a l l e e or from some o t h e r frame. A d d i t i o n a l f i e l d s g i v e n f o r frame e x t e n s i o n s are the " E x i t f n " f i e l d s p e c i f y i n g a c t i o n s t o be taken b e f o r e the f u n c t i o n e x i t s ; the "Framename" c o n t a i n i n g the name o f the f u n c t i o n ; the "Return Type" f i e l d f o r type c h e c k i n g o f r e t u r n e d v a l u e s when the f u n c t i o n body i s r e a c t i v a t e d ; the "USE" f i e l d c o n t a i n i n g a r e f e r e n c e count o f the frame e x t e n s i o n ; the " S i z e " and "Max" f i e l d s f o r memory management; and an u n s p e c i f i e d Chapter 3 24 number o f "Temporary" f i e l d s . The b a s i c frame a l s o has " S i z e " and "Max" f i e l d s as w e l l as the "CXT" f i e l d c o n t a i n i n g a count o f the number o f frame e x t e n s i o n s p o i n t i n g t o the b a s i c frame. Bobrow and Wegbreit s p e c i f y the p r i m i t i v e f u n c t i o n s G e t e x f n and Framenm t o o b t a i n the v a l u e s o f the " E x i t f n " and "Framename" f i e l d s , r e s p e c t i v e l y , and the f u n c t i o n S e t e x f n t o a l t e r t he v a l u e o f the " E x i t f n " f i e l d . I n a normal f u n c t i o n c a l l and r e t u r n sequence the b a s i c frame o f the c a l l e e w i l l have an e x t e n s i o n count o f one and both the ALINK and the CLINK o f the frame e x t e n s i o n w i l l p o i n t t o the c a l l e r ' s frame e x t e n s i o n . When the f u n c t i o n e x i t s both the b a s i c frame and the frame e x t e n s i o n are d e l e t e d and c o n t r o l r e t u r n s t o the c a l l e r . R e t e n t i o n o f s t a c k frames i s made p o s s i b l e by the i n t r o d u c t i o n o f a s p e c i a l d a t a type c a l l e d "environment d e s c r i p t o r " (ED). Bobrow and Wegbreit d e f i n e the f o u r p r i m i t i v e f u n c t i o n s E n v i r o n , S e t e n v , Mkframe and E n v e v a l which c r e a t e and a l t e r ED's, c r e a t e new frames w i t h s p e c i f i e d c o n t e x t l i n k s , and a l l o w e x e c u t i o n o f a co m p u t a t i o n i n a s p e c i f i e d c o n t e x t . Whenever c o n t r o l r e t u r n s t o a f u n c t i o n whose frame i s r e f e r e n c e d from o t h e r frames or from one or more ED's a copy o f the frame i s made and the com p u t a t i o n i s c o n t i n u e d i n the copy. When the f u n c t i o n e x i t s , i t s frame ( i . e . , the copy) i s d e l e t e d but the o r i g i n a l frame i s r e t a i n e d . S e v e r a l ways are p r o v i d e d f o r the user t o s p e c i f y frames: 1. An i n t e g e r N: (a) N = 0 s p e c i f i e s the frame which c a l l e d the p r i m i t i v e f u n c t i o n u s i n g the frame s p e c i f i c a t i o n ; (b) Chapter 3 25 N > 0 s p e c i f i e s the frame N l i n k s down the c o n t r o l l i n k c h a i n from the N = 0 frame; and (c) N < 0 s p e c i f i e s the frame |N| l i n k s down the access l i n k c h a i n from the N = 0 frame. 2. A l i s t of two elements (F,N) where F i s a framename and N i s an i n t e g e r . T h i s g i v e s the Nth frame with name F, where the s i g n of N s p e c i f i e s which environment c h a i n to descent. 3. The constant NIL. For a frame with NIL i n i t s ALINK f i e l d g l o b a l v a l u e s of f r e e v a r i a b l e s are to be used. I f c o n t r o l r e t u r n s from a frame whose CLINK i s NIL then the system h a l t s . I f an ED i s set to NIL then the storage i t p r e v i o u s l y r e f e r e n c e d i s r e l e a s e d . 4. An environment d e s c r i p t o r . The frame s p e c i f i e d i s the frame r e f e r e n c e d by the ED. 5. A l i s t o f one element which i s an ED. The frame s p e c i f i e d i s the frame r e f e r e n c e d by the ED. The p r i m i t i v e f u n c t i o n using^ the frame s p e c i f i c a t i o n w i l l execute Setenv(ED,NIL). T h i s i s sometimes necessary i n the case of Enveval s i n c e the user cannot do t h i s e x p l i c i t l y b efore the c a l l to Enveval because t h i s would i n v a l i d a t e the ED, nor can he do t h i s a f t e r the c a l l s i n c e c o n t r o l may never r e t u r n to t h a t p o i n t . 3.4.2 The Sp a g h e t t i Stack The run-time stack s t r u c t u r e i n the VM i s an ada p t a t i o n of the Bobrow and Wegbreit model as d e s c r i b e d i n the p r e v i o u s s e c t i o n . S e v e r a l d i f f e r e n c e s e x i s t that make the s p a g h e t t i Chapter 3 26 s t a c k behave s l i g h t l y d i f f e r e n t l y . The VM e x p l i c i t l y warns t h a t some d i f f e r e n c e s e x i s t , but does not attempt t o enumerate t h e s e . I n the f o l l o w i n g p aragraphs we s h a l l d i s c u s s t h e s e d i f f e r e n c e s i n d e t a i l . I n the VM, the "framename" f i e l d i s c o n t a i n e d i n the b a s i c frame r a t h e r than i n the frame e x t e n s i o n . Because frame e x t e n s i o n s can occur more f r e q u e n t l y than b a s i c frames ( b a s i c frames can be shared) t h i s l e a d s t o some ( r a t h e r i n s i g n i f i c a n t ) s a v i n g s i n space, but i t r e q u i r e s an e x t r a p o i n t e r d e r e f e r e n c e t o o b t a i n the framename (through the BLINK f i e l d o f the frame e x t e n s i o n ) . There i s no d i f f e r e n c e i n f u n c t i o n a l i t y . The VM S p e c i f i c a t i o n o f the s p a g h e t t i s t a c k makes no mention o f the " S i z e " , "Max", "USE" and "CXT" f i e l d s . The method o f s t a c k s p a c e a l l o c a t i o n and d e a l l o c a t i o n i s l e f t e n t i r e l y t o the implementor. The I n t e r l i s p s p a g h e t t i s t a c k model has no p r o v i s i o n s f o r e x i t f u n c t i o n s . Hence the " E x i t f n " f i e l d and the f u n c t i o n s G e t e x f n and S e t e x f n s p e c i f i e d i n the Bobrow and Wegbreit model do not e x i s t . The VM r e c o g n i z e s the need f o r a " C o n t i n u a t i o n P o i n t " f i e l d but does not e x p l i c i t l y i n c o r p o r a t e t h i s i n the frame e x t e n s i o n nor i s i t r e f e r r e d t o i n any o t h e r p a r t o f the VM S p e c i f i c a t i o n . I n s t e a d , the f i e l d i s c o n s i d e r e d p a r t o f the "Temporaries" and i t s maintenance i s l e f t t o the implementor. I n t e r l i s p p r o v i d e s g r e a t e r c o n t r o l over the c o n t e n t s o f frames than the Bobrow and Wegbreit model a l l o w s : a. The f u n c t i o n s STKNAME and STKNTHNAME a l l o w one t o o b t a i n the Chapter 3 27 c o n t e n t s o f the "framename" f i e l d and the f u n c t i o n SETSTKNAME m o d i f i e s t h i s f i e l d . SETSTKNAME i s a SUBR i n the I n t e r l i s p R e f e r e n c e Manual but i s o m i t t e d from the VM S p e c i f i c a t i o n . b. The f u n c t i o n s STKNARGS, STKARG, STKARGNAME, SETSTKARG, SETSTKARGNAME, STKSCAN and FRAMESCAN a l l o w one t o i n s p e c t or mo d i f y the b i n d i n g s i n a b a s i c frame. c. The f u n c t i o n s SETALINK and SETCLINK m o d i f y the c o r r e s p o n d i n g f i e l d s i n a frame e x t e n s i o n . They t e s t f o r c i r c u l a r i t y so t h a t the i n t e g r i t y o f s t a c k c h a i n s i s m a i n t a i n e d . A l l o w i n g a frame to be a member o f i t s own ALINK or CLINK c h a i n would cause an i n f i n i t e l o o p i n p a s s i n g c o n t r o l down the CLINK c h a i n as w e l l as i n f r e e v a r i a b l e l o o k u p down the ALINK c h a i n . These f u n c t i o n s are VM ( r e v i s e d e d i t i o n ) SUBR's but do not appear i n the Re f e r e n c e Manual. d. Frames and frame sequences can be c r e a t e d w i t h the VM SUBR's MKFRAME and COPYSTK. MKFRAME does not appear i n the Re f e r e n c e Manual. 3.4.3 S t ack P o i n t e r s The VM s p a g h e t t i s t a c k e q u i v a l e n t o f Environment D e s c r i p t o r s (ED's) are Stack P o i n t e r s . S t ack P o i n t e r s can be c r e a t e d by means o f the f u n c t i o n s STKPOS, STKNTH, MKFRAME, COPYSTK, STKSCAN and FUNCTION, r e c o g n i z e d as such w i t h the p r e d i c a t e STACKP, and t e s t e d f o r e q u a l i t y w i t h the f u n c t i o n EQP. A copy o f a Stack P o i n t e r , SP, can be o b t a i n e d by e x e c u t i n g (COPYALL SP) or (STKNTH 0 S P ) . The l a t t e r method i s g i v e n i n the R e f e r e n c e Manual but w i l l not work a c c o r d i n g t o the VM Chapter 3 28 s p e c i f i c a t i o n o f the f u n c t i o n STKNTH (presumably the VM d e f i n i t i o n i s e r r o n e o u s ) . The s p a g h e t t i s t a c k model a l l o w s one t o s p e c i f y frames i n a v a r i e t y o f ways as w e l l but the d i f f e r e n c e s are noteworthy: 1. An i n t e g e r N: (a) N = 0 s p e c i f i e s the frame which b e l o n g s t o the s t a c k f u n c t i o n i t s e l f , not the frame which c a l l e d the p r i m i t i v e f u n c t i o n u s i n g the frame s p e c i f i c a t i o n ; (b) N > 0 s p e c i f i e s the frame N l i n k s down the a c c e s s l i n k c h a i n from the N = 0 frame; and (c) N < 0 s p e c i f i e s the frame |N| l i n k s down the c o n t r o l l i n k c h a i n from the N = 0 frame. Hence the meaning o f the s i g n i s r e v e r s e d from the Bobrow and Wegbreit model. 2. The c o n s t a n t NIL. T h i s r e f e r s t o the frame o f the c u r r e n t l y a c t i v e f u n c t i o n ( i . e . , the s t a c k f u n c t i o n i t s e l f ) . 3. The c o n s t a n t T. T h i s r e f e r s t o the frame o f the top l e v e l p r o c e s s ( i . e . , the p r o c e s s e x e c u t i n g EVALQT). 4. Any atom o t h e r than NIL or T. T h i s s p e c i f i e s the f i r s t frame down the c o n t r o l l i n k o f the a c t i v e frame (the frame o f the s t a c k f u n c t i o n ) whose framename i s the atom g i v e n . 5. A Stack P o i n t e r . The frame s p e c i f i e d i s the frame r e f e r e n c e d by the Stack P o i n t e r . Because the c o n s t a n t NIL has d i f f e r e n t s e m a n t i c s from the Bobrow and Wegbreit model a d i f f e r e n t way o f r e l e a s i n g and r e u s i n g Stack P o i n t e r s has been d e f i n e d . The f u n c t i o n s RELSTK and CLEARSTK are p r o v i d e d t o e x p l i c i t l y r e l e a s e s t a c k s p a c e r e f e r r e d t o by a Stack P o i n t e r or by a l l Stack P o i n t e r s , r e s p e c t i v e l y . Chapter 3 29 I m p l i c i t r e l e a s e i s p r o v i d e d f o r by means o f a d d i t i o n a l arguments t o the s t a c k f u n c t i o n s d e s c r i b e d above. F l a g arguments s p e c i f y r e l e a s i n g a Stack p o i n t e r a f t e r the r e f e r e n c e d frame has been o b t a i n e d , and o p t i o n a l S t a c k P o i n t e r arguments a l l o w the VM t o reuse t h e s e Stack P o i n t e r s . The p r e d i c a t e RELSTKP can be used t o determine whether a Stack P o i n t e r i s r e f e r r i n g t o a s t a c k frame or has been r e l e a s e d . 3.4.4 A l t e r i n g the Flow o f C o n t r o l The VM d e f i n e s a number o f f u n c t i o n s which take frame s p e c i f i c a t i o n s as arguments and s e r v e t o a l t e r the f l o w o f c o n t r o l or a l l o w c o m p u t a t i o n s t o be performed i n a g i v e n e nvironment. The s i m p l e s t o f these are the f u n c t i o n s RETTO and RETFROM which cause c o n t r o l t o r e t u r n t o (from) the s p e c i f i e d frame. EVALV o b t a i n s the b i n d i n g o f the f i r s t argument (which must be a L i t e r a l Atom) i n the acce s s environment (the ALINK ch a i n ) s p e c i f i e d by i t s second argument. ENVEVAL and ENVAPPLY c r e a t e a dummy b a s i c frame w i t h framename NIL and no b i n d i n g s , and a dummy frame e x t e n s i o n w i t h ALINK and CLINK as s p e c i f i e d by t h e i r arguments, a f t e r which the form i s e v a l u a t e d , or the f u n c t i o n a p p l i e d , u s i n g t h i s dummy frame as the s t a r t i n g frame of the c u r r e n t a c c e s s and c o n t r o l environment. FUNARG F u n c t i o n a l O b j e c t s p r o v i d e a g e n e r a l method o f p e r f o r m i n g a com p u t a t i o n i n the c u r r e n t c o n t r o l environment u s i n g a d i f f e r e n t a c c e s s environment. FUNARG's are c r e a t e d w i t h the N o e v a l - t y p e f u n c t i o n FUNCTION which t a k e s two arguments: a Form and an Environment S p e c i f i c a t i o n (ES). I f ES i s NIL then Chapter 3 30 FUNCTION s i m p l y r e t u r n s Form, so i n t h i s mode FUNCTION i s e q u i v a l e n t t o QUOTE, e x c e p t t h a t i t s i g n a l s t o the c o m p i l e r t h a t Form i s a F u n c t i o n a l O b j e c t and s h o u l d be c o m p i l e d a c c o r d i n g l y . T h i s i s u s e f u l , f o r i n s t a n c e , f o r c o m p i l i n g open Lambda e x p r e s s i o n s . I f ES i s not NIL then i t can be e i t h e r a S t a c k P o i n t e r or a proper l i s t o f L i t e r a l Atoms. ( A c c o r d i n g t o the I n t e r l i s p R e f e r e n c e Manual, ES may a l s o be a L i t e r a l Atom, i n which case i t i s e v a l u a t e d f i r s t ; t h i s i s not s p e c i f i e d f o r the VM.) I f ES i s a l i s t a b a s i c frame i s c o n s t r u c t e d w i t h framename NIL and w i t h b i n d i n g s made up o f the atoms i n the l i s t and t h e i r v a l u e s i n the c u r r e n t a c c e s s environment. A dummy frame e x t e n s i o n i s c r e a t e d f o r t h i s b a s i c frame w i t h ALINK e q u a l t o the c u r r e n t a c c e s s c h a i n and CLINK s e t t o NIL, and FUNCTION r e t u r n s a l i s t o f t h r e e e l e m e n t s : the L i t e r a l Atom FUNARG, Form, and a St a c k P o i n t e r t o the frame j u s t c r e a t e d . I f ES i s a Stack P o i n t e r then FUNCTION j u s t r e t u r n s a l i s t o f the form (FUNARG Form E S ) . When a FUNARG e x p r e s s i o n i s a p p l i e d t o an argument l i s t , a dummy frame i s c r e a t e d w i t h i t s ALINK s e t t o the frame r e f e r e n c e d by the Stack p o i n t e r ( t h i r d element i n the FUNARG e x p r e s s i o n ) and i t s CLINK s e t t o the c u r r e n t c o n t r o l c h a i n . Then the Form o f the FUNARG e x p r e s s i o n i s a p p l i e d t o the o r i g i n a l argument l i s t i n t h i s environment. 3.4.5 B l i p F i e l d s I n t e r l i s p p r o v i d e s a means t o acce s s d i r e c t l y some f i e l d s on the s t a c k which p e r t a i n t o the f l o w o f c o n t r o l . These Chapter 3 31 f i e l d s , c a l l e d " B l i p f i e l d s " are a s s o c i a t e d w i t h the f u n c t i o n s EVAL, APPLY, COND, PROG, PROGN and PROG1. The l a s t f o u r use the b l i p f i e l d s *FORM* and *TAIL* t o h o l d the c u r r e n t form b e i n g e v a l u a t e d and the l i s t o f r e m a i n i n g forms t o be e v a l u a t e d , r e s p e c t i v e l y . EVAL and APPLY use thes e as w e l l as the b l i p f i e l d *FN* and a number o f b l i p f i e l d s *ARGVAL*. The f i e l d *FN* h o l d s the name o f a f u n c t i o n t o be c a l l e d , and the f i e l d s *ARGVAL* h o l d i n t e r m e d i a t e v a l u e s o f ( e v a l u a t e d ) arguments t o the f u n c t i o n . The VM l e a v e s i t t o the implementor t o d e c i d e whether th e s e b l i p f i e l d s are i n c o r p o r a t e d i n the "Temporaries" f i e l d o f the frame e x t e n s i o n or are b i n d i n g s i n the b a s i c frame o f the b l i p - u s i n g f u n c t i o n s . The b l i p f i e l d s can be a c c e s s e d and m o d i f i e d w i t h the f u n c t i o n s BLIPSCAN, BLIPVAL and SETBLIPVAL. Access t o thes e f i e l d s e n a b l e s the I n t e r l i s p e r r o r p r o c e s s o r ( p a r t i c u l a r l y , the DWIM f a c i l i t y ) t o i n s p e c t (and p o s s i b l y a l t e r ) the f l o w o f c o n t r o l and t o c o r r e c t e r r o n e o u s forms on the s t a c k . 3.4.6 Copying Frames Because the VM does not e x p l i c i t l y s t a t e a l l o f the d i f f e r e n c e s between the s p a g h e t t i s t a c k and the Bobrow and Wegbreit model, a g l a r i n g o m i s s i o n i n the VM S p e c i f i c a t i o n i s e a s i l y assumed by the implementor t o be an i n t e n d e d d e v i a t i o n from the o r i g i n a l model. The VM, a l t h o u g h v e r y p r e c i s e and s p e c i f i c i n most c a s e s , f a i l s t o s p e c i f y t h a t frames s h o u l d be c o p i e d whenever c o n t r o l r e t u r n s t o them and t h e i r r e f e r e n c e c o u n t s are g r e a t e r than one. T h i s c o p y i n g i s a l s o not mentioned Chapter 3 32 i n the Stack s e c t i o n o f the I n t e r l i s p R e f e r e n c e Manual [ T e i t e l m a n , 1978]. I t i s a r a t h e r i m p o r t a n t p o i n t because f a i l i n g t o implement t h i s causes f u n c t i o n s u s i n g the s p a g h e t t i s t a c k f a c i l i t i e s t o behave q u i t e d i f f e r e n t l y . C o n s i d e r the f o l l o w i n g d e f i n i t i o n o f the f u n c t i o n F00: [NLAMBDA (STP) (PRINT 'Hi) ([LAMBDA (FRAME) (COND ((STACKP FRAME) (SET STP FRAME)) (T (PRINT FRAME] (STKPOS 'F00)) (PRINT 'There) 'FOO-exit] The arguments t o STKPOS are "framename", "nth such frame", " s t a r t i n g frame" and " r e u s a b l e s t a c k p o i n t e r " . Hence, (STKPOS •F00) w i l l s e a r c h f o r the f i r s t frame down the c o n t r o l c h a i n whose frame name i s F00, s t a r t i n g the s e a r c h w i t h the c u r r e n t l y a c t i v e frame and r e t u r n i n g a new Stack P o i n t e r t o t h i s frame i f found. When frames are c o p i e d as d e s c r i b e d above, the f o l l o w i n g d i a l o g u e would ensue: * (F00 BAR) > H i > t h e r e > FOO-exit * (RETTO BAR ' H e l l o ) > H e l l o > t h e r e > FOO-exit The f u n c t i o n RETTO t a k e s t h r e e arguments, v i z . "frame to r e t u r n t o " , " v a l u e r e t u r n e d " and " r e l e a s e frame f l a g " . (For a d e t a i l e d Chapter 3 33 e x e c u t i o n t r a c e o f t h i s example see Appendix F.) I f frames a r e not c o p i e d , however, then a l l forms w i t h i n F00 a f t e r the c a l l t o STKPOS w i l l be executed w i t h i n the o r i g i n a l F00 frame, and r e t u r n i n g t o i t w i l l have no e f f e c t : * (F00 BAR) > H i > t h e r e > FOO-exit * (RETTO BAR ' H e l l o ) > H e l l o * In p e r s o n a l communications w i t h r e s e a r c h e r s a t Xerox PARC [ M a s i n t e r e t a l . , 1980] the author was in f o r m e d t h a t the s p a g h e t t i s t a c k conforms t o the Bobrow and Wegbreit model i n t h i s r e s p e c t and hence t h a t frames s h o u l d be c o p i e d when r e a c t i v a t e d w i t h a r e f e r e n c e count g r e a t e r than one (the one a c c o u n t i n g f o r the i m p l i c i t S t a ck P o i n t e r *ACTFRAME* which always p o i n t s t o the c u r r e n t l y a c t i v e f r a m e ) . 34 4. The Implementation of the V i r t u a l Machine M u l t i l i s p i s a ( p a r t i a l ) implementation of the I n t e r l i s p V i r t u a l Machine developed at the U n i v e r s i t y of B r i t i s h Columbia. The system i s w r i t t e n i n P a s c a l [Wirth, 1971] and c o n s i s t s of approximately 16500 l i n e s of P a s c a l source d i s t r i b u t e d over 21 f i l e s . Each f i l e c o n t a i n s a r e l a t i v e l y s e l f - c o n t a i n e d s e c t i o n of the system, such as memory management, i n p u t , output, i n t e r p r e t e r , and l o g i c a l groups of VM f u n c t i o n s . M u l t i l i s p was designed to be p o r t a b l e and i s c u r r e n t l y running on both the Amdahl 470 under MTS and the DEC VAX 11/780 under VMS. Developed on the Amdahl i n approximately 12 man-months, about 3 man-weeks were r e q u i r e d to t r a n s p o r t M u l t i l i s p to the VAX. M u l t i l i s p i s intended p r i m a r i l y f o r l a r g e - s c a l e systems with an autonomous d i s k o p e r a t i n g system s u p p o r t i n g v i r t u a l memory. Although developed f o r a machine with a wordsize of four bytes (32 b i t s ) , the system does not r e l y on t h i s f a c t . The only assumptions made are that memory i s b y t e - a d d r e s s a b l e , that a byte can c o n t a i n a Character Code, and that a word i s s u f f i c i e n t to hold any memory address. In t h i s Chapter we s h a l l d e s c r i b e the M u l t i l i s p system b r i e f l y and d i s c u s s some of the design i s s u e s that were encountered i n the implementation of the VM. Chapter 4 4.1 The R e p r e s e n t a t i o n o f O b j e c t s 35 A l t h o u g h not a l l I n t e r l i s p m e t a - o b j e c t s have a c o r r e s p o n d i n g O b j e c t a s s o c i a t e d w i t h them i n the VM S p e c i f i c a t i o n ( e.g., B i t t a b l e s ) t hey need t o have some r e c o g n i z a b l e r e p r e s e n t a t i o n . Hence M u l t i l i s p i n t r o d u c e s a t l e a s t one ( i n t e r n a l ) type name f o r e v e r y O b j e c t . The l a y o u t o f O b j e c t s i s s p e c i f i e d w i t h a P a s c a l r e c o r d w i t h case v a r i a n t s based on the o b j e c t type (see Appendix B ) . A l l I n t e r l i s p o b j e c t s have been implemented i n M u l t i l i s p w i t h the e x c e p t i o n o f T e r m i n a l T a b l e s f o r reasons which w i l l be g i v e n i n Chapter 5. In the f o l l o w i n g s u b s e c t i o n s we s h a l l d i s c u s s the i n t e r e s t i n g o b j e c t s i n more d e t a i l . 4.1.1 L i s t C e l l s A l a r g e number o f r e s e a r c h e r s have s t u d i e d the e f f i c i e n t r e p r e s e n t a t i o n o f LISP Cons c e l l s ([Hansen, 1969], [Cheney, 1970], [Wegbreit, 1972], [ C l a r k & Green, 1977], and [ M o r r i s , 1978], among o t h e r s ) . C l a r k and Green found i n t h e i r e x t e n s i v e s t u d y o f l i s t s t r u c t u r e s t h a t the CDR f i e l d s o f almost a l l l i s t c e l l s (>98%) p o i n t themselves t o o t h e r l i s t c e l l s or t o NIL. As w e l l , t hey found t h a t l i s t c e l l s are g e n e r a l l y l i n e a r and p o i n t e d t o by o n l y one o t h e r l i s t c e l l , so t h a t the CDR o f a l i s t c e l l i s f r e q u e n t l y a l l o c a t e d v e r y near t o the l i s t c e l l i t s e l f . Rather than a l l o c a t i n g a f u l l word f o r the CDR f i e l d o f a l i s t c e l l which can h o l d any f u l l memory address one can make use o f t h i s b e h a v i o u r o f l i s t s by encoding the d i s t a n c e o f the CDR from the l i s t c e l l i n the l i s t c e l l i t s e l f . S i n c e t h i s Chapter 4 36 d i s t a n c e i s g e n e r a l l y s m a l l t h i s encoding, r e f e r r e d to as CDR-Coding, r e q u i r e s very few b i t s . Because i n approximately one out of every four cases [Clark & Green, 1977] the CDR i s NIL, encoding t h i s i n f o r m a t i o n as w e l l f u r t h e r reduces memory requirements. T h i s form of l i s t compaction can save up to h a l f the t o t a l memory requirements of o r d i n a r y l i s t c e l l s . In paged memory systems t h i s has the added advantage of producing fewer d i r e c t memory r e f e r e n c e s , and hence fewer page f a u l t s . In M u l t i l i s p we have adopted the scheme of Immediate CDR-Coding. T h i s scheme rec o g n i z e s four d i f f e r e n t types of l i s t c e l l s : a. A l i s t c e l l whose CDR i s NIL b. A l i s t c e l l whose CDR i s the c e l l immediately f o l l o w i n g c. A f u l l l i s t c e l l (with both CAR and CDR f i e l d s ) d. An i n d i r e c t l i s t c e l l I n d i r e c t l i s t c e l l s are c e l l s t h a t were at one time Compact L i s t c e l l s , but whose CDR was r e p l a c e d by something other than NIL. A F u l l L i s t c e l l had to be c o n s t r u c t e d to h o l d the o r i g i n a l CAR f i e l d value and the new CDR f i e l d v a l u e . The address of the F u l l L i s t c e l l was l e f t i n the o r i g i n a l Compact c e l l which was marked as an I n d i r e c t c e l l . 4.1.2 L i t e r a l Atoms L i t e r a l Atoms are hashed i n t o a hash t a b l e by means of a polynomial hash f u n c t i o n on the Pname, us i n g l i n k e d l i s t s f o r c o n f l i c t r e s o l u t i o n . In order to avoid the use of LISP l i s t s i n hash buckets, L i t e r a l Atoms have a f o u r t h f i e l d , the "Hash Chapter 4 37 L i n k " , which i s a p o i n t e r t o the next atom i n the hash b u c k e t . The advantage i s , o f c o u r s e , t h a t CONS need not be c a l l e d f o r i n s e r t i o n o f a new L i t e r a l Atom, CAR and CDR need not be c a l l e d f o r s e a r c h i n g through the hash b u c k e t , and the Garbage C o l l e c t o r need not to t r a c e the hash b u c k e t s . O t h e r w i s e the f i e l d s are as d e s c r i b e d i n Chapter 3. 4.1.3 Numbers The i m p l e m e n t a t i o n o f boxed numbers ( i . e . , FIXP and FLOATP) i s s t r a i g h t f o r w a r d (see Appendix B ) . M e e t i n g the VM r e q u i r e m e n t of unique r e p r e s e n t a t i o n o f a t l e a s t a l l C h a r a c t e r Codes, however, proved t o be somewhat more d i f f i c u l t . Under a l a r g e t i m e - s h a r i n g system such as MTS or UNIX i t cannot be assumed t h a t the implementor i s a b l e t o o b t a i n and use the address range of memory where the system l o a d e r has l o a d e d the o b j e c t program c o n s t i t u t i n g the VM. Hence, u s i n g t h i s a d d ress range f o r SMALLP numbers i s not f e a s i b l e . Moreover, M u l t i l i s p r e q u i r e s a l l o b j e c t s t o be r e f e r e n c e d i n o r d e r t o o b t a i n t h e i r o b j e c t t y p e . ( T h i s w i l l be e x p l a i n e d i n the next s e c t i o n ) . M u l t i l i s p , t h e r e f o r e , a c q u i r e s a t system s t a r t - u p time a s e c t i o n o f memory from the o p e r a t i n g system which i s d e s i g n a t e d as SMALLP space. T h i s space remains the same thro u g h o u t the time M u l t i l i s p i s r u n n i n g . At each v a l i d a ddress w h i t h i n t h i s space the type i n d i c a t o r SMALLP i s d e p o s i t e d once a t the time o f i n i t i a l i z a t i o n . A l l S m a l l I n t e g e r s are mapped i n t o t h i s space by adding the address o f the m i d d l e o f the SMALLP space t o the v a l u e o f the S m a l l I n t e g e r , g i v i n g a l l S m a l l I n t e g e r s (between Chapter 4 38 -1024 and 1023 i n the c u r r e n t implementation) a unique r e p r e s e n t a t i o n . Each address so o b t a i n e d , when der e f e r e n c e d , y i e l d s the o b j e c t type SMALLP, yet f o r a l l Small Integers n e i t h e r the heap space a l l o c a t i o n mechanism nor the garbage c o l l e c t o r need be invoked. 4.2 Object Memory Management An important i s s u e i n the design and implementation of l a r g e - s c a l e LISP systems i s the way o b j e c t memory i s o r g a n i z e d . Nowhere i s the time-space dilemma more apparent than i n the o b j e c t memory manager. In g e n e r a l , the more emphasis i s p l a c e d on e f f i c i e n t memory a l l o c a t i o n , the more processor time i s r e q u i r e d to r e a l i z e i t . CDR-Coding, as i t was d e s c r i b e d i n s e c t i o n 4.1.1, i s an obvious example. T h i s scheme can save up to 50% of L i s t c e l l memory space, but the p r i c e one pays i s encoding and decoding of the L i s t c e l l s themselves. In the case of L i s t c e l l s the memory savings are s u f f i c i e n t l y s i g n i f i c a n t to j u s t i f y the i n c r e a s e d complexity, but i n other cases t h i s i s not immediately obvious. Two important c r i t e r i a have i n f l u e n c e d the design of the o b j e c t memory i n M u l t i l i s p . F i r s t of a l l , the requirement of p o r t a b i l i t y of M u l t i l i s p d i d not allow f o r using memory words c o n t a i n i n g p o i n t e r s f o r any other i n f o r m a t i o n . For i n s t a n c e , the Amdahl 470 (an IBM 370 d e r i v a t i v e ) uses a wordsize of 32 b i t s , but o n l y supports a 24 b i t address space, and one i s tempted to use the high order byte f o r other i n f o r m a t i o n . On Chapter 4 39 the o t h e r hand, a l t h o u g h the DEC VAX 11/780 a l s o uses a w o r d s i z e of 32 b i t s , i t s address space i s a f u l l 32 b i t s as w e l l . S e c o n d l y , on the p a r t i c u l a r system M u l t i l i s p was d e v e l o p e d (the M i c h i g a n T e r m i n a l System, s u p p o r t i n g l a r g e - s c a l e t i m e - s h a r i n g w i t h a c c o u n t i n g ) memory i s r e l a t i v e l y cheap t o a c q u i r e but p r o c e s s o r time i s a p r e c i o u s commodity. Hence, e x c e p t f o r l i s t c o m p a c t i o n , i n the time-space t r a d e o f f d e c i s i o n s s a v i n g s i n p r o c e s s o r time were u s u a l l y f a v o u r e d over space s a v i n g s . 4.2.1 O b j e c t T y p i n g There are b a s i c a l l y t h r e e methods f o r e s t a b l i s h i n g the type of o b j e c t s i n o b j e c t memory: a. The Boundary Check Method O b j e c t s are a l l o c a t e d i n f i x e d segments o f memory, each segment c o n t a i n i n g o b j e c t s o f o n l y one t y p e . The type o f an o b j e c t i s then d e t e r m i n e d by s e q u e n t i a l l y comparing the address o f the o b j e c t w i t h the known segment b o u n d a r i e s u n t i l the r i g h t segment i s found. T h i s method i s g e n e r a l l y u n s a t i s f a c t o r y because type d e t e r m i n a t i o n r e q u i r e s s e a r c h , and because expanding segments t o a l l o w f o r more o b j e c t s o f a c e r t a i n type i s u s u a l l y not f e a s i b l e . The method can be a p p r o p r i a t e where the implementor has complete c o n t r o l over the e n t i r e address space and can a l l o c a t e segments a t a b s o l u t e a d d r e s s e s . b. The P a g e t a b l e Method T h i s i s a f a r more f l e x i b l e method than Boundary C h e c k i n g . I t i s a p p l i c a b l e both i n environments where f u l l c o n t r o l o f the e n t i r e address space i s a v a i l a b l e and i n Chapter 4 40 those environments where a ( p o s s i b l y u n c o o p e r a t i v e ) o p e r a t i n g system i s r e s p o n s i b l e f o r page a l l o c a t i o n . Each page i s d e d i c a t e d t o one type o f o b j e c t o n l y . Pages are a l l o c a t e d p r e f e r a b l y on demand, and once a l l o c a t e d the e n t r y i n the p a g e t a b l e c o r r e s p o n d i n g to the page number i s a s s i g n e d a type i n d i c a t o r . Whenever more memory i s r e q u i r e d f o r a c e r t a i n o b j e c t type a new page i s r e q u e s t e d from the page manager, and i t s a s s o c i a t e d p a g e t a b l e e n t r y updated. O b j e c t t y p e s are then d e t e r m i n e d by the code sequence ObjectType := P a g e T a b l e [ O b j e c t A d d r e s s DIV P a g e s i z e ] ; W i t h t h i s method space i s h a r d l y ever wasted ( i . e . , a l l o c a t e d f o r a c e r t a i n type but not c u r r e n t l y i n u s e ) . As w e l l , memory p a r t i t i o n i n g on the b a s i s o f t y p e s i s dynamic and dependent o n l y on the c h a r a c t e r i s t i c s o f the t o t a l program c o n f i g u r a t i o n and the r u n - t i m e space r e q u i r e m e n t s . The o n l y memory "wasted" i s i n the form o f gaps l e f t a t the end o f a page. S i n c e type a l l o c a t i o n i s per page, where c o n s e c u t i v e pages a l l o c a t e d f o r a p a r t i c u l a r type are not n e c e s s a r i l y c o n t i g u o u s , l a r g e r o b j e c t s such as a r r a y s may not be a b l e t o use the remainder o f the c u r r e n t page but must be a l l o c a t e d i n a new page, l e a v i n g a gap i n the c u r r e n t page. c. The Tagged O b j e c t Method With t h i s method a l l o b j e c t s are a l l o c a t e d from one "heap". Each o b j e c t has a "type i n d i c a t o r " f i e l d , and hence the type o f an o b j e c t i s d e t e r m i n e d by the code sequence Chapter 4 41 ObjectType := O b j e c t @ . T y p e F i e l d ; The b a s i c a t t r a c t i o n o f t h i s method i s s i m p l i c i t y — b oth i n o b j e c t a l l o c a t i o n and i n type d e t e r m i n a t i o n . S i n c e t h e r e i s o n l y one heap o n l y one p o i n t e r i s r e q u i r e d t o i n d i c a t e the c u r r e n t heap t o p , whereas the P a g e t a b l e Method r e q u i r e s a t op-of-page p o i n t e r f o r e v e r y t y p e . I t i s t r u e t h a t each r e f e r e n c e w i t h the Tagged O b j e c t Method c o u l d cause a p a g e f a u l t , but t h i s i s t r u e a l s o f o r i ndexed a c c e s s i n g o f the p a g e t a b l e , u n l e s s the page manager can be i n s t r u c t e d t o keep the e n t i r e p a g e t a b l e p ermanently i n the a c t i v e w o r k i n g s e t (the s e t o f v i r t u a l pages mapped onto r e a l memory). I t i s a l s o t r u e t h a t the Tagged O b j e c t Method i s p o t e n t i a l l y w a s t e f u l o f memory, e s p e c i a l l y i n systems where word a l i g n m e n t i s e n f o r c e d . On the o t h e r hand, any garbage c o l l e c t i o n method w i l l r e q u i r e one or more b i t s f o r m a r k i n g , and i f no assumptions can be made about the number o f address b i t s i n a p o i n t e r , e x t r a space i s r e q u i r e d anyway. I f e x t r a b i t s are a v a i l a b l e i n a p o i n t e r word then t h e s e can be used f o r t a g s . However, i n t h a t case a p r i c e i s p a i d i n e x t r a p r o c e s s i n g s i n c e e v e r y p o i n t e r d e r e f e r e n c e w i l l t hen r e q u i r e masking out the tag b i t s . As w e l l , w i t h t h i s method CDR-Coding comes almost f o r f r e e by r e c o g n i z i n g f o u r d i f f e r e n t t y p e s o f L i s t c e l l s i n s t e a d o f one. Because o f the s i m p l i c i t y o f memory management w i t h the Tagged O b j e c t Method (and hence a s i m p l e r garbage c o l l e c t o r as w e l l ) , and the f a s t method o f type d e t e r m i n a t i o n t h i s l a s t method was chosen f o r the M u l t i l i s p system. However, the Chapter 4 42 Pagetable Method i s recognized as a s e r i o u s contender. U n f o r t u n a t e l y , resources were not a v a i l a b l e to experiment with both methods and to choose on the b a s i s of performance s t a t i s t i c s . Instead, the c h o i c e was made p u r e l y on reasoning and i n t u i t i v e a ppeal. (For a summary of the f i x e d memory requirements of o b j e c t s i n M u l t i l i s p f o r both the Amdahl 470 and the VAX 11/780 see Appendix B. The d i f f e r e n c e s are due to word alignment and packing of P a s c a l r e c o r d s , or the lack t h e r e o f ) . L i s t c e l l s are a l l o c a t e d from the top of the heapspace so t h a t CONS i s able to use compact r e p r e s e n t a t i o n s when a l i s t i s being c o n s t r u c t e d . Atoms are a l l o c a t e d i n a separate space so as to avoid unnecessary garbage c o l l e c t i o n (atoms can be c r e a t e d but not d e l e t e d ) . Character sequences a l s o are a l l o c a t e d i n a separate space r e c o g n i z i n g the need f o r a s p e c i a l , s t r i n g - s p e c i f i c garbage c o l l e c t o r (not yet implemented). A l l other o b j e c t s are a l l o c a t e d at the bottom of the heapspace. When the top and bottom p o i n t e r s of the heapspace meet the garbage c o l l e c t o r i s invoked. 4.2.2 Garbage C o l l e c t i o n A s i g n i f i c a n t number of papers have been p u b l i s h e d on the s u b j e c t of garbage c o l l e c t i o n . For a system which supports CDR-Coding of L i s t c e l l s , the c o m p a c t i f y i n g garbage c o l l e c t o r i s the n a t u r a l c h o i c e ([Hansen, 1969], [Cheney, 1970], [Wegbreit, 1972], [Deutsch & Bobrow, 1976], [Morris, 1978], [Baker, 1978]). M u l t i l i s p , with i t s s i n g l e heapspace, has a n o n - r e c u r s i v e , copying garbage c o l l e c t o r based on Cheney's A l g o r i t h m . Garbage Chapter 4 43 c o l l e c t i o n i s i n i t i a t e d by a q u i r i n g a second heapspace from the o p e r a t i n g system, i t s s i z e a t l e a s t e q u a l t o the s i z e o f the c u r r e n t heapspace (the a c t u a l s i z e i s a f u n c t i o n o f the amount o f a c t i v e heapspace a f t e r c o m p l e t i o n o f the p r e v i o u s garbage c o l l e c t i o n ) . Then a t r a c e i s s t a r t e d from the atom h a s h t a b l e , the r u n - t i m e s t a c k and a l l system p o i n t e r v a r i a b l e s . Each o b j e c t thus encountered i s c o p i e d t o the bottom o f the new heapspace. I f a L i s t c e l l i s encountered then the e n t i r e l i s t ( i n the CDR d i r e c t i o n ) i s c o p i e d , jumping through p o s s i b l e I n d i r e c t c e l l s , and making a l l c o p i e d c e l l s compact i f p o s s i b l e (see Appendix C ) . A bottom marker moves a l o n g the new heapspace as o b j e c t s are added. Once an o b j e c t has been c o p i e d t o the new heapspace the o l d o b j e c t i s smashed. I t s "type i n d i c a t o r " f i e l d i s r e p l a c e d by a s p e c i a l " t y p e " FORWARD, and the address of the copy i s l e f t i n the o r i g i n a l o b j e c t . ( T h i s o f c o u r s e assumes t h a t e v e r y o b j e c t i s a t l e a s t l a r g e enough t o c o n t a i n both a f o r w a r d i n g a d d ress and the s p e c i a l type mark FORWARD). When a l l d i r e c t l y a c c e s s i b l e o b j e c t s have thus been t r a c e d and c o p i e d , a t r a c e o f the new heapspace i s i n i t i a t e d by h a v i n g a s c a n n i n g p o i n t e r , s t a r t i n g a t the bottom o f the new heapspace, r e p e a t the p r o c e s s j u s t d e s c r i b e d f o r e v e r y r e l e v a n t p o i n t e r c o n t a i n e d i n c o p i e d o b j e c t s , u n t i l the s c a n n i n g p o i n t e r c a t c h e s up t o the bottom p o i n t e r . At t h a t p o i n t the garbage c o l l e c t i o n i s c o m p l e t e , the o l d heapspace can be d i s c a r d e d , and the s i z e o f the next heapspace determined on the b a s i s o f how much o f the new heapspace i s a c t i v e . A s p e c i a l push-down s t a c k i s employed f o r m a i n t a i n i n g Chapter 4 44 temporary p o i n t e r s i n t o the heap. Whenever some p a r t o f M u l t i l i s p i n v o k e s the s t o r a g e a l l o c a t o r , and t h e r e b y p o t e n t i a l l y causes a garbage c o l l e c t i o n t o o c c u r , r e l e v a n t l o c a l p o i n t e r s are pushed on t h i s s p e c i a l s t a c k , and popped a g a i n on r e t u r n from the s t o r a g e a l l o c a t o r . The garbage c o l l e c t o r c hecks t h i s s t a c k d u r i n g the i n i t i a l t r a c e o f i m m e d i a t e l y a c c e s s i b l e p o i n t e r s . 4.3 The S p a g h e t t i S t ack Because o f i t s c o m p l e x i t y the i m p l e m e n t a t i o n o f the s p a g h e t t i s t a c k i s a n o n - t r i v i a l t a s k . A number o f o b s e r v a t i o n s have i n f l u e n c e d the d e s i g n o f the c u r r e n t i m p l e m e n t a t i o n : a. A f a i r l y l a r g e amount o f s t o r a g e i s r e q u i r e d . F i r s t l y , each f u n c t i o n i n v o c a t i o n consumes more space than i s the case i n more c o n v e n t i o n a l s t a c k e n v i r o n m e n t s , because the s p a g h e t t i s t a c k has more overhead: n e i t h e r the ALINK nor the CLINK o f a frame n e c e s s a r i l y p o i n t t o the frame i m m e d i a t e l y above i t , hence an a d d i t i o n a l p o i n t e r i s r e q u i r e d p o i n t i n g t o the frame i m m e d i a t e l y p r e c e e d i n g the c u r r e n t frame so t h a t s t o r a g e o c c u p i e d by the l a t t e r can be r e t u r n e d t o the former; as w e l l , frames below the c u r r e n t one may be r e t a i n e d so t h a t the c u r r e n t frame must be aware o f i t s l o c a l " c e i l i n g " , which may not be e q u a l t o the end o f the s t a c k . T h i s s t a c k maintenance overhead i s a g g r e v a t e d because i t i s n e c e s s a r y f o r both the b a s i c frame and the frame e x t e n s i o n s i n c e they can e x i s t independent o f one a n o t h e r . S e c o n d l y , i f frames are r e t a i n e d than a l l t h e i r a n c e s t o r frames are n e c e s s a r i l y Chapter 4 45 r e t a i n e d as w e l l , which can render l a r g e s e c t i o n s o f the s t a c k u n u s a b l e i b. The s t a c k manager must be a b l e t o make e f f i c i e n t use o f " h o l e s " — these o c c u r , f o r i n s t a n c e , when t h r e e branches have been a l l o c a t e d c o n s e c u t i v e l y and the m i d d l e one i s s u b s e q u e n t l y r e l e a s e d . c. The i n t e g r i t y o f the s t a c k must a t a l l t i m e s be p r e s e r v e d . T h i s i s e s p e c i a l l y c r i t i c a l i n the case o f s t a c k o v e r f l o w . d. Under o p e r a t i n g systems such as MTS, where computing c o s t and performance depends on, among o t h e r t h i n g s , the amount o f v i r t u a l memory a c q u i r e d from the o p e r a t i n g system, i t i s d e s i r a b l e t o r e t u r n unused s t a c k space t o the system as soon as p o s s i b l e . Maintenance o f the s p a g h e t t i s t a c k i n M u l t i l i s p o c c u r s on t h r e e l e v e l s : the l o w e s t l e v e l i s concerned w i t h u n s t r u c t u r e d s t a c k space c a l l e d segments; the next l e v e l views the s t a c k as a c o l l e c t i o n o f s t a c k "elements"; the t h i r d l e v e l d e a l s w i t h frames as d e s c r i b e d i n Chapter 3. 4.3.1 S t a c k Segments Segments are b l o c k s o f c o n t i g u o u s memory a c q u i r e d from the o p e r a t i n g system. Segments are not n e c e s s a r i l y e q u a l i n s i z e nor are they c o n t i g u o u s . I n i t i a l l y , one segment i s a l l o c a t e d which i s p o i n t e d t o by CURRENT_SEGMENT. Segments are m a i n t a i n e d w i t h a s e p a r a t e s t a t i c " e x p a n s i o n s t a c k " a l l o w i n g f o r a f i x e d (but e a s i l y changed) number o f segments. Each e n t r y i n the ex p a n s i o n s t a c k has t h r e e f i e l d s , v i z . SEGMENT_START, Chapter 4 46 SEGMENT_END and SEGMENT_TOP. The SEGMENT_TOP f i e l d marks the t o p - o f - s t a c k l o c a l t o the segment. When the CURRENT_SEGMENT i s f u l l and more s t a c k space i s r e q u e s t e d by the next h i g h e r l e v e l , the Segment Manager scans a l l o t h e r e x i s t i n g segments f o r one which has a SEGMENT_TOP l e s s than SEGMENT_END (and t h e r e f o r e has room t o s p a r e ) . I f such a segment i s found i t i s made the CURRENT_SEGMENT; o t h e r w i s e a new segment i s a q u i r e d from the o p e r a t i n g system, made t o be the CURRENT_SEGMENT, and pushed o n t o the e x p a n s i o n s t a c k . I f t h i s f i l l s up the e x p a n s i o n s t a c k a Stack O v e r f l o w e r r o r i s s i g n a l e d . (Hence, the I n t e r l i s p e r r o r p r o c e s s o r can run i n t h i s l a s t segment). I f t h i s segment o v e r f l o w s as w e l l , n o t h i n g can be done and M u l t i l i s p a b o r t s . Whenever a segment becomes empty ( s i g n a l e d by the next h i g h e r l e v e l ) the Segment Manager scans the e x p a n s i o n s t a c k f o r a second segment marked as empty. I f i t f i n d s one i t i s r e t u r n e d t o the o p e r a t i n g system and the e x p a n s i o n s t a c k i s popped a c c o r d i n g l y . T h i s method o f r e l e a s i n g the second segment p r o v i d e s the n e c e s s a r y h y s t e r e s i s , which i f not p r e s e n t would cause tremendous t h r a s h i n g i n boundary c a s e s . For i n s t a n c e , i f the body o f a PROGN i s e x e c u t i n g a t the end o f a segment then f o r the e x e c u t i o n o f each form i n s i d e the PROGN a new segment would r e p e a t e d l y be a c q u i r e d from the o p e r a t i n g system and r e l e a s e d a g a i n i f h y s t e r e s i s were not p r o v i d e d . 4.3.2 Stack Elements Stack elements are c r e a t e d a t the top o f the CURRENT SEGMENT. They form a d o u b l y l i n k e d l i s t w i t h two Chapter 4 47 f i e l d s , LAST and NEXT, per element. LAST p o i n t s t o the element i m m e d i a t e l y p r e c e e d i n g the new element and NEXT p o i n t s t o the element i m m e d i a t e l y s u c c e e d i n g the new one (at the time o f c r e a t i o n , t h i s i s e q u i v a l e n t t o the end o f the segment). Each element has a t h i r d f i e l d , TOP, which p o i n t s t o the top o f the c u r r e n t element. Hence, the d i f f e r e n c e between the address o f an element and the address c o n t a i n e d i n i t s TOP f i e l d c o r r e s p o n d s t o the c o n t e n t s o f the " S i z e " f i e l d i n the Bobrow and Wegbreit model, and the d i f f e r e n c e between the NEXT f i e l d and the TOP f i e l d o f an element c o r r e s p o n d s t o the "Max" f i e l d i n the model. A c t u a l a d d r e s s e s were used i n s t e a d o f t h e s e " S i z e " and "Max" f i e l d s i n o r d e r t o a v o i d a r i t h m e t i c and thus t o speed up the Element Manager. R e l e a s i n g an element i s done w i t h the s t a n d a r d a l g o r i t h m f o r d e l e t i o n o f elements i n a d o u b l y - l i n k e d l i s t [Knuth, 1968]. When new segments are a q u i r e d a dummy element i s c r e a t e d a t the bottom o f the segment whose LAST p o i n t e r c o n t a i n s NIL, and whose NEXT p o i n t e r i s the same as the SEGMENT_END. Hence, i f the space o c c u p i e d be an element i s r e t u r n e d t o an element which has the a f o r e m e n t i o n e d LAST and NEXT c h a r a c t e r i s i c s the segment must be empty and t h i s i s s i g n a l e d t o the Segment Manager. 4.3.3 Stack Frames B a s i c frames and frame e x t e n s i o n s are c r e a t e d (by o v e r l a y ) w i t h i n elements (see Appendix D). The f u n c t i o n CRE_BASIC a l l o c a t e s b a s i c frames o f f i x e d s i z e , enough t o h o l d the f i x e d c o n t e n t s NAME, NARGS and REFCNT, and the number of b i n d i n g s Chapter 4 48 g i v e n as argument. The TOP f i e l d o f the element c o n t a i n i n g the b a s i c frame p o i n t s j u s t p a s t the l a s t b i n d i n g . Frame e x t e n s i o n s are a l l o c a t e d by MAKE_XFRAME i n an element b i g enough t o h o l d the f i x e d c o n t e n t s , such as USECNT, ALINK and CLINK, and some s t a c k b l o c k s ( d e s c r i b e d b e l o w ) . The TOP f i e l d o f the element i n i t i a l l y p o i n t s j u s t p a s t the l a s t f i x e d member o f the frame e x t e n s i o n . M u l t i l i s p c o n t r o l s the s t a c k v i a the frame c r e a t i o n and d e l e t i o n f u n c t i o n s and a c c e s s e s the s t a c k t h rough the i n t e r n a l s t a c k p o i n t e r *ACTFRAME* and a l l d y n a m i c a l l y a l l o c a t e d S t ack P o i n t e r s , and hence has ac c e s s t o a l l frame e x t e n s i o n s . B a s i c frames are o n l y a c c e s s i b l e through t h e i r c o r r e s p o n d i n g frame e x t e n s i o n s , and e v e r y frame e x t e n s i o n must have a b a s i c frame. T h i s poses a problem i n case o f s t a c k o v e r f l o w : e i t h e r a b a s i c frame i s c r e a t e d f i r s t and the s t a c k o v e r f l o w s when a t t e m p t i n g to c r e a t e the matching frame e x t e n s i o n , i n which case t h e r e i s a "ghost" element on the s t a c k t h a t i s not p o i n t e d t o by any frame e x t e n s i o n , y e t has been l i n k e d on the element l e v e l , which c o u l d t i e up an e n t i r e segment; or a frame e x t e n s i o n i s c r e a t e d f i r s t and the s t a c k o v e r f l o w s when a t t e m p t i n g t o c r e a t e the c o r r e s p o n d i n g b a s i c frame, i n which case t h e r e i s a frame e x t e n s i o n t h a t has been l i n k e d w i t h the r e s t o f the s t a c k ( i . e . , ALINK and CLINK, not LAST and NEXT) but t h a t has no b a s i c frame, v i o l a t i n g the i n t e g r i t y o f the s p a g h e t t i s t a c k . MULILISP's s o l u t i o n i s t o c o n s i s t e n t l y c r e a t e b a s i c frames f i r s t , then the frame e x t e n s i o n . CRE_BASIC s e t s the g l o b a l p o i n t e r CURRENT BASIC t o the newly c r e a t e d b a s i c frame; MAKE XFRAME s e t s Chapter 4 49 i t t o NIL. When the i n t e r n a l e r r o r r o u t i n e i s c a l l e d (which i n t u r n w i l l i n v o k e the I n t e r l i s p e r r o r h a n d l e r ) i t checks i f CURRENT_BASIC i s NIL, and i f not i t d e l e t e s t h i s "ghost" frame. 4.3.4 Temporaries and B l i p F i e l d s As can be seen from the above s e c t i o n s , c r e a t i n g and d e l e t i n g o f b a s i c frames and frame e x t e n s i o n s i s an e l a b o r a t e p r o c e s s . In o r d e r t o reduce s t a c k a c t i v i t y i n t e r n a l c a l l s t o EVAL do not cause c r e a t i o n o f the EVAL frame sequence. I n s t e a d , an e v a l - b l o c k i s pushed onto the frame e x t e n s i o n t h a t i s c a l l i n g EVAL (see Appendix D). These b l o c k s are a l l o c a t e d a t the TOP o f the element c o n t a i n i n g the frame e x t e n s i o n a f t e r which the TOP p o i n t e r i s a d j u s t e d . I f t h e r e i s no more room t o expand the frame e x t e n s i o n , the frame i s c o p i e d t o a l o c a t i o n where e x p a n s i o n i s p o s s i b l e , and the o l d frame d e l e t e d . D e l e t i o n o f the o l d frame i s s a f e because the f u n c t i o n r e q u i r i n g t h i s e x p a n s i o n i s c u r r e n t l y a c t i v e . I f t h e r e were any S t a c k P o i n t e r s r e f e r e n c i n g the f u n c t i o n ' s frame then i t i s now r u n n i n g i n an (unshared) copy o f i t s e l f . The e v a l - b l o c k s p r o v i d e room f o r the b l i p f i e l d s and the c o n t i n u a t i o n p o i n t . A s l i g h t l y d i f f e r e n t b l o c k i s used f o r h o l d i n g t e m p o r a r i e s . T h i s type o f b l o c k i s used by the f u n c t i o n READ, which r e q u i r e s a c e r t a i n number o f t e m p o r a r i e s f o r s e v e r a l purposes v e r y f r e q u e n t l y . A p o s s i b l e a l t e r n a t i v e t o the scheme o f e v a l - b l o c k s i s t o c o n s i d e r the dynamic p o r t i o n o f the frame e x t e n s i o n as a v a r y i n g s i z e a r r a y o f words, where a word may c o n t a i n a heap p o i n t e r , a Chapter 4 50 s t a c k p o i n t e r , an i n t e g e r , a c o n t i n u a t i o n p o i n t , or any o t h e r v a l u e . T h i s method c o u l d r e s u l t i n some memory s a v i n g s and t h e r e f o r e reduce the chance o f h a v i n g t o copy the frame e x t e n s i o n f o r l a c k o f e x p a n s i o n space. However, b e s i d e s the d i f f i c u l t y r e f e r r i n g t o such words i n P a s c a l , t h i s approach r e q u i r e s a s s o c i a t i n g i n d i c a t o r s w i t h e v e r y word i n d i c a t i n g what the word i s used f o r , so t h a t the v a r i o u s f u n c t i o n s d e a l i n g w i t h the s t a c k ( i n c l u d i n g the garbage c o l l e c t o r ) know how t o i n t e r p r e t the words. The i n d i c a t o r would occupy 1 byte on the VAX-11, but on the Amdahl 470 i t would t a k e another word so t h a t a l i g n m e n t i s g u a r a n t e e d . I t was d e c i d e d t h a t the e f f i c i e n c y o f t h i s approach i s too dependent on the u n d e r l y i n g machine. As w e l l , the e v a l - b l o c k approach a s s u r e s f a s t a c c e s s o f the f i e l d s i n s i d e b l o c k s ( i . e . , we know the o f f s e t s o f a l l f i e l d s such as *FORM* and don't need t o scan the s t a c k i n o r d e r t o f i n d them). However, a c o m p i l e r may n e c e s s i t a t e t h i s approach i n o r d e r t o make e f f i c i e n t use o f the s t a c k . In a d d i t i o n t o the i n t e r n a l s t a c k p o i n t e r *ACTFRAME* M u l t i l i s p has a c c e s s t o the c u r r e n t l y a c t i v e b l o c k through the i n t e r n a l s t a c k p o i n t e r *ACTBLOCK*. B l o c k s a re c r e a t e d and d e l e t e d by CRE_BLOCK and REL_ACTBLOCK which m a i n t a i n the v a l u e o f *ACTBLOCK* as w e l l , and always a p p l y t o the c u r r e n t l y a c t i v e frame. Thus, *ACTBL0CK* always p o i n t s t o the topmost b l o c k o f *ACTFRAME*. A frame e x t e n s i o n may have more than one b l o c k because o f EVAL's r e c u r s i o n , e.g. i n o r d e r t o e v a l u a t e : (CAR (FOO (BAR . . . ) ) ) the i n t e r p r e t e r needs a b l o c k t o e v a l u a t e the argument t o CAR. Chapter 4 51 T h i s e v a l u a t i o n , i n t u r n , needs a b l o c k t o e v a l u a t e the arguments t o F00, e t c . 4.3.5 Argument B i n d i n g Whether t o use deep b i n d i n g or s h a l l o w b i n d i n g i n LISP systems has been a c o n t r o v e r s i a l t o p i c f o r s e v e r a l y e a r s . The g e n e r a l argument i s t h a t v a r i a b l e a c c e s s i s a more f r e q u e n t o p e r a t i o n than v a r i a b l e b i n d i n g and hence employing a s h a l l o w b i n d i n g t e c h n i q u e s h o u l d r e s u l t i n b e t t e r system performance. T h i s i s t r u e o n l y f o r programs which c o n s i s t o f many l a r g e f u n c t i o n s and PROG's. For programs t h a t use s m a l l f u n c t i o n d e f i n i t i o n s and many open LAMBDA'S v a r i a b l e b i n d i n g o b v i o u s l y becomes more c r u c i a l than v a r i a b l e a c c e s s . Another f a c t o r i n d e t e r m i n i n g which b i n d i n g method i s more a d v a n t a g i o u s i s whether user programs p r i m a r i l y f o l l o w the t r a d i t i o n a l f l o w o f c o n t r o l or make use o f m u l t i - p r o g r a m m i n g , c o r o u t i n e s and b a c k t r a c k i n g . As soon as environment s w i t c h i n g becomes a s i g n i f i c a n t p a r t o f program e x e c u t i o n , o v e r a l l system performance q u i c k l y d e t e r i o r a t e s i f s h a l l o w b i n d i n g i s employed. The VM S p e c i f i c a t i o n f o r v a r i a b l e b i n d i n g f o l l o w s the deep b i n d i n g paradigm. Of c o u r s e , i mplementing e i t h e r s h a l l o w or deep b i n d i n g i s c o m p l e t e l y t r a n s p a r e n t t o the user (other than by i t s e f f e c t on performance) so the implementor can d e v i a t e from the VM S p e c i f i c a t i o n . M u l t i l i s p has opted f o r the deep b i n d i n g regime. The user community f o r which i t was o r i g i n a l l y d e v e l o p e d makes heavy use o f the s p a g h e t t i s t a c k f a c i l i t i e s f o r environment s w i t c h i n g and the c o s t f o r t h i s i n a shallow-bound Chapter 4 52 system can be h i g h . A l s o , deep b i n d i n g i n the c o n t e x t o f the s p a g h e t t i s t a c k i s c o n s i d e r a b l y e a s i e r t o c o n c e p t u a l i z e and t o implement than s h a l l o w b i n d i n g . U n f o r t u n a t e l y , r e s o u r c e s were not a v a i l a b l e t o o b t a i n s u b s t a n t i a l performance s t a t i s t i c s i n ord e r t o make a d e c i s i o n on the b a s i s o f t h e s e . I f s h a l l o w b i n d i n g were t o be implemented the b e s t scheme f o r environment s w i t c h i n g would p r o b a b l y be Ba k e r ' s r e r o u t i n g a l g o r i t h m [Baker, 1978] . 4.4 The M u l t i l i s p I n t e r p r e t e r 4.4.1 The B a s i c Loop On system s t a r t u p the s t a c k i s i n i t i a l i z e d w i t h a b a s i c frame w i t h framename T and no b i n d i n g s , a frame e x t e n s i o n w i t h NIL i n both the ALINK and CLINK f i e l d s , and an e v a l - b l o c k w i t h a r o u t i n e e x e c u t i n g EVALQT as c o n t i n u a t i o n p o i n t . T h i s frame sequence i s i n the VM r e f e r r e d t o as the " t o p frame". C o n t r o l can r e t u r n t o t h i s frame but can never r e t u r n from i t ( a t t e m p t i n g t o r e t u r n from a frame which has NIL i n i t s CLINK causes an e r r o r ) . The i n t e r p r e t e r i s c o n t i n u o u s l y r e a c t i v a t e d by o b t a i n i n g the c o n t i n u a t i o n p o i n t from *ACTBLOCK* and c a l l i n g the c o r r e s p o n d i n g c o n t i n u a t i o n r o u t i n e . The c o n t i n u a t i o n p o i n t i s an in d e x i n t o a branch t a b l e r a t h e r than an a c t u a l machine code address (see Appendix E ) . S i n c e M u l t i l i s p i s implemented i n a h i g h l e v e l language i t i s not o n l y i m p o s s i b l e t o o b t a i n the address o f any a c t u a l machine i n s t r u c t i o n but a l s o c o m p l e t e l y undermines the aim f o r p o r t a b i l i t y o f M u l t i l i s p . I n a d d i t i o n , Chapter 4 53 u s i n g i n d i c e s a l l o w s one t o modi f y the a c t i o n s taken f o r c o n t i n u a t i o n o f the system w i t h o u t a f f e c t i n g any o t h e r p a r t o f the system. I t t u r n s out t h a t v e r y few c o n t i n u a t i o n p o i n t s (24) need a c t u a l l y be d i s t i n g u i s h e d because f o r i n t e r m e d i a t e c a l l s and r e t u r n s o f a l l the M u l t i l i s p s u p p o r t r o u t i n e s the P a s c a l s t a c k i s used r a t h e r than the s p a g h e t t i s t a c k . B e f o r e the c o n t i n u a t i o n p r o c e d u r e f o r the a c t i v e frame i s in v o k e d a check i s made o f the frame's use co u n t . I f i t i s g r e a t e r than one the a c t i v e frame i s s p l i t so t h a t p r o c e s s i n g can c o n t i n u e i n a unique copy o f the frame. P r e c i s e l y because the P a s c a l s t a c k i s used f o r i n t e r n a l c a l l s t h e r e e x i s t s the danger o f r u n n i n g o u t o f P a s c a l s t a c k space. T h i s , o f c o u r s e , w i l l happen i f the i n t e r n a l c a l l t o EVAL i s r e c u r s i v e on the P a s c a l s t a c k as w e l l as the s p a g h e t t i s t a c k . Unwinding the P a s c a l s t a c k independent o f the f l o w o f M u l t i l i s p c o n t r o l i s done by p l a c i n g the c o n t i n u o u s i n t e r p r e t e r l o o p i n the main body o f the program, preceeded by a ( g l o b a l ) l a b e l (see Appendix E ) . M u l t i l i s p assumes the c o n v e n t i o n t h a t whenever the i n t e r n a l r o u t i n e s EVAL, APPLY, ERROR or POP_ACTFRAME are c a l l e d a branch i s exe c u t e d t o t h i s g l o b a l l a b e l , t h u s popping the P a s c a l s t a c k . Hence, whenever an i n t e r n a l r o u t i n e c a l l s t hese r o u t i n e s and c o n t r o l i s ex p e c t e d t o r e t u r n f o r f u r t h e r p r o c e s s i n g the r e t u r n w i l l not be made a c c o r d i n g t o the P a s c a l regime. I n s t e a d , a new b l o c k must be p r o v i d e d h o l d i n g the index o f the proper c o n t i n u a t i o n r o u t i n e . Chapter 4 54 4.4.2 Argument E v a l u a t i o n When EVAL e n c o u n t e r s a l i s t whose f i r s t argument i s a F u n c t i o n a l O b j e c t o f E v a l - t y p e a l l arguments need t o be e v a l u a t e d b e f o r e the f u n c t i o n can be c a l l e d . For t h i s purpose an e v a l - b l o c k i s c r e a t e d on top o f the c u r r e n t l y a c t i v e frame. The *FN* b l i p f i e l d i s s e t t o the F u n c t i o n a l O b j e c t , the *TAIL* f i e l d i s s e t t o the l i s t o f arguments, and the c o n t i n u a t i o n f i e l d c o n t a i n s the i n d e x f o r CNT_EVLIS, the c o n t i n u a t i o n p r o c e d u r e d e a l i n g w i t h argument e v a l u a t i o n . Each time t h i s p r o c e d u r e i s e n t e r e d (through a c a l l from the main i n t e r p r e t e r loop) the r e t u r n e d v a l u e i s pushed onto the c u r r e n t l y a c t i v e e v a l - b l o c k as a new *ARGVAL* and EVAL i s c a l l e d a g a i n on the next argument by CDR*ing down the *TAIL* f i e l d , u n t i l the argument l i s t i s e x h a u s t e d . A t t h i s p o i n t , a f t e r c h e c k i n g t h a t the *FN* b l i p f i e l d i s s t i l l a v a l i d F u n c t i o n a l O b j e c t ( i t c o u l d have been changed by SETBLIPVAL i n a lower f u n c t i o n c a l l ) , the f u n c t i o n can be c a l l e d . T h i s means t h a t the f o r m a l parameters o f the f u n c t i o n must be bound t o the v a l u e s o f the arguments c o n t a i n e d i n the *ARGVAL* f i e l d s . I d e a l l y , the *FN* f i e l d and the *ARGVAL* f i e l d s are p l a c e d i n the e v a l - b l o c k i n such a way t h a t the e v a l - b l o c k can be o v e r l a y e d w i t h a new b a s i c frame. The framename and the b i n d i n g s would then be i n p l a c e and o n l y the f o r m a l parameter names would have t o be f i l l e d i n , t h u s a v o i d i n g some unnecessary c o p y i n g . T h i s , however, would r e q u i r e t h a t we know p r e c i s e l y how the p a r t i c u l a r P a s c a l c o m p i l e r i n use aranges the f i e l d s w i t h i n r e c o r d s , t h e r e b y l o s i n g whatever c l a i m we had on M u l t i l i s p ' s p o r t a b i l i t y . M u l t i l i s p s o l v e s the problem Chapter 4 5 5 by introducing a set of special registers holding the argument values. When CNT_EVLIS has finished evaluation of the arguments a l l N *ARGVAL*1s are pulled from the active eval-block and deposited in the registers 1 to N. The remaining registers are set to NIL, thus accounting for missing arguments. The contents of the *FN* b l i p f i e l d are deposited in the special register CURRENT_FN, after which the currently active eval-block i s released. The next action depends on the function to be c a l l e d . 4.4.3 Function Invocation If the function i s a SUBR no further stack manipulation i s required. The Functional Object contains a f i e l d SUBR_ADDR (see Appendix A) which i s an index into a large branch table analogous to the branch table for continuation points. The SUBR is simply c a l l e d through the branch table. Each SUBR knows that i t s arguments are located in the global r e g i s t e r s . Only i f a SUBR needs an eval-block because i t in turn i s c a l l i n g EVAL (such as COND, PROG, etc.) i t c a l l s SETUP_FRAME which creates the proper frame sequence, using the values in the registers and in CURRENT_FN to assemble the basic frame. It then resets CURRENT_FN to NIL. A l l other SUBR's simply do their thing and return. If the SUBR returns, a branch i s made to the global l a b e l mentioned before to pop the Pascal stack. If any SUBR causes an error, the inter n a l error handler checks the contents of CURRENT_FN. If i t i s not NIL the spaghetti stack i s incomplete so the error handler c a l l s SETUP_FRAME to complete i t before activating the I n t e r l i s p error handler (in this case no Chapter 4 56 e v a l - b l o c k i s c r e a t e d , so t h a t , i f c o n t r o l ever r e t u r n s t o t h i s frame i t i s i m m e d i a t e l y d e l e t e d and c o n t r o l r e t u r n s t o the c a l l e r ) . A l l SUBR's i n c l u d i n g EVAL (and t h e r e f o r e a l l EXPR's as w e l l ) r e t u r n t h e i r r e s u l t i n r e g i s t e r 1. I f the f u n c t i o n i s an EXPR then SETUP_FRAME i s c a l l e d i m m e d i a t e l y t o c o n s t r u c t the prop e r frame sequence. In a d d i t i o n an e v a l - b l o c k i s c r e a t e d on top o f the new frame e x t e n s i o n . The *TAIL* b l i p f i e l d o f t h i s new b l o c k i s s e t t o the CDR o f the LAMBDA e x p r e s s i o n o f the f u n c t i o n (hence, t h i s i n c l u d e s the f o r m a l parameter l i s t o f the f u n c t i o n ) . The c o n t i n u a t i o n p o i n t i n the e v a l - b l o c k i s s e t t o an index c o r r e s p o n d i n g t o the PROGN c o n t i n u a t i o n p r o c e d u r e . Then a branch i s made t o the main i n t e r p r e t e r l o o p i n o r d e r t o pop the P a s c a l s t a c k . From t h e r e e x e c u t i o n c o n t i n u e s w i t h a c a l l t o the PROGN c o n t i n u a t i o n p r o c e d u r e which r e p e a t e d l y s e t s the *TAIL* f i e l d o f the c u r r e n t l y a c t i v e e v a l - b l o c k t o i t s CDR, and c a l l s EVAL on the CAR o f *TAIL* u n t i l t h i s i s exhausted (Note t h a t the f o r m a l parameter l i s t o f the LAMBDA e x p r e s s i o n was s k i p p e d the f i r s t time the PROGN r o u t i n e was e n t e r e d ) . A t t h i s p o i n t a c a l l t o POP ACTFRAME r e l e a s e s the c u r r e n t l y a c t i v e frame and a subsequent branch t o the main l o o p c o n t i n u e s the i n t e r p r e t e r a c c o r d i n g t o the v a l u e o f the c o n t i n u a t i o n f i e l d o f the topmost b l o c k o f the next a c t i v e frame. 4.4.4 An Example: the Imp l e m e n t a t i o n o f COND To i l l u s t r a t e the a c t i o n s f o r a b l i p u s i n g f u n c t i o n , l e t us examine the M u l t i l i s p i m p l e m e n t a t i o n o f COND: Chapter 4 57 p r o c e d u r e COND_VM; (* r e g l = l i s t o f c l a u s e s *) b e g i n NEW_ACTIVATION ( n i l , CONTINUE_COND, 0 ) ; (* T h i s c r e a t e s (a) the b a s i c frame f o r COND, t a k i n g the argument ( l i s t o f c l a u s e s ) from r e g i s t e r 1; (b) the frame e x t e n s i o n ; and (c) a b l o c k w i t h the s p e c i f i e d c o n t i n u a t i o n p o i n t . *) ACTBLOCK@.BLIP_TAIL := REG(.1.); EVAL (CAR (CAR (R E G ( . 1 . ) ) ) ) ; (* EVAL w i l l s e t the BLIP_FORM f i e l d o f ACTBLOCK to i t s argument. Then r e t u r n s the v a l u e o f i t s argument i n r e g i s t e r 1 i f a n o n - l i s t ; o t h e r w i s e the f u n c t i o n c a l l e d l e a v e s i t s r e s u l t i n r e g i s t e r 1. *) end (* cond vm * ) ; p r o c e d u r e CNT_COND; (* T h i s p r o c e d u r e i s c a l l e d o n l y from the main i n t e r p r e t e r l o o p . *) var NEXTFORM : PTR; b e g i n w h i l e REG(.l.) = A_NIL do (* R e s u l t r e t u r n e d from EVAL. *) b e g i n NEXTFORM := CAR_OF_POP (ACTBLOCK@.BLIP_TAIL); (* T h i s s e t s *TAIL* t o CDR (*TAIL*) and r e t u r n s i t s new CAR i f s t i l l a l i s t ; o t h e r w i s e r e t u r n s n i l . *) i f NEXTFORM = n i l then POP_ACTFRAME; (* POP_ACTFRAME d e l e t e s the COND frame and branches t o the main i n t e r p r e t e r l o o p . *) EVAL (CAR (NEXTFORM)); end; ACTBLOCK@.BLIP_TAIL := CAR (ACTBLOCK@.BLIP_TAIL); (* BLIP TAIL now p o i n t s t o the c l a u s e whose c o n d i t i o n succeeded. *) NEXTFORM := CAR_OF_POP (ACTBLOCK?.BLIP_TAIL); (* See i f t h e r e are any forms i n the c l a u s e o t h e r than the c o n d i t i o n . *) i f NEXTFORM = n i l then POP ACTFRAME; 7*" Note t h a t REG (. 1.) s t i l l c o n t a i n s the v a l u e o f the c o n d i t i o n . T h i s w i l l t h e r e f o r e a l s o be the r e s u l t o f the COND i f t h i s t e s t s u c c e e d s . I f n o t , proceed w i t h the i m p l i c i t PROGN. *) ACTBLOCK?.CONTINUATION := CONTINUE_PROGN; EVAL (NEXTFORM); end (* ent cond * ) ; Chapter 4 5 8 p r o c e d u r e CNT_NPROG; (* The c o n t i n u a t i o n p o i n t o f PROGN *) v a r NEXTFORM : PTR; b e g i n  r e p e a t NEXTFORM := CAR_OF_POP (ACTBLOCK@.BLIP_TAIL); i f NEXTFORM <> n i l then EVAL (NEXTFORM); u n t i l NEXTFORM = nTT; POP_ACTFRAME; end (* ent nprog * ) ; 59 5. E v a l u a t i o n 5.1 The V i r t u a l Machine The c o n s t r u c t i o n o f the I n t e r l i s p V i r t u a l Machine S p e c i f i c a t i o n was a t r u l y h e r o i c attempt t o c a p t u r e the e s s e n t i a l s o f the I n t e r l i s p system i n a s e m i - f o r m a l way. Many p r o s p e c t i v e implementors have been m i s l e d by the c o n c i s e f u n c t i o n d e f i n i t i o n s c o n t a i n e d i n a mere 110-page document. The M u l t i l i s p e f f o r t has c l e a r l y shown, however, t h a t a l a r g e body o f s o f t w a r e i s r e q u i r e d t o r e a l i z e the VM. And M u l t i l i s p , w i t h i t s 16500 l i n e s o f h i g h - l e v e l language code, i s o n l y a p a r t i a l i m p l e m e n t a t i o n ( f o r a l i s t o f m i s s i n g SUBR's, see Appendix A ) . I n s p i t e o f i t s t h o r o u g h n e s s , the VM s u f f e r s from a number of weaknesses which we s h a l l d i s c u s s i n t h i s c h a p t e r . The f a c t t h a t the VM was d e f i n e d p o s t f a c t o has had a s i g n i f i c a n t i n f l u e n c e on i t s d e s i g n . I t i s i n g e n e r a l much e a s i e r t o e s t a b l i s h the s p e c i f i c a t i o n o f a new language or s o f t w a r e system f i r s t , f o l l o w e d by an i m p l e m e n t a t i o n on the b a s i s o f t h e s e s p e c i f i c a t i o n s , a f t e r which the two i n t e r a c t i n a p r o c e s s o f c o n t i n u a l r e f i n e m e n t , than i t i s t o e x t r a c t t h e s e s p e c i f i c a t i o n s from an e x i s t i n g system — e s p e c i a l l y such a l a r g e and complex system as I n t e r l i s p . In the l a t t e r case a l l t o o o f t e n i d i o s y n c r a s i e s and machine- or system-dependencies are i n c o r p o r a t e d i n the d e s i g n i n o r d e r t o remain c o m p a t i b l e s i n c e the i n v e s t m e n t i n human and m a t e r i a l r e s o u r c e s i s too l a r g e t o a l l o w f o r major changes i n the system i t s e l f . Chapter 5 60 5.1.1 System Dependencies One a r e a where the VM shows i t s system dependencies i s Inp u t and Output. A v e r y complex I/O mechanism has been s p e c i f i e d i n the VM which r e l i e s h e a v i l y on an ASCII environment and a c h a r a c t e r - o r i e n t e d f i l e system, p a r t i c u l a r l y t h a t o f the TENEX o p e r a t i n g system [Bobrow e t a l . , 1 9 7 2], S o p h i s t i c a t e d user-programmable i n t e r r u p t f a c i l i t i e s are p r o v i d e d which a re d r i v e n by c o n t r o l c h a r a c t e r s from an ASCII keyboard. In an IBM environment a l l one has i s a s i n g l e BREAK or a t t e n t i o n - i n t e r r u p t key which causes an immediate p r o c e s s o r i n t e r r u p t . Moreover, under MTS, t e r m i n a l i n p u t and o u t p u t i s p r o c e s s e d i n the same manner as f i l e I/O — both are l i n e - o r i e n t e d . The user program (e.g., M u l t i l i s p ) e x e c u t e s a c a l l t o the system READ r o u t i n e a f t e r which i t i s suspended u n t i l the READ r o u t i n e r e t u r n s a b u f f e r . A l l t e r m i n a l e d i t i n g , such as c h a r a c t e r - and l i n e -d e l e t e , r e t y p e or c h a r a c t e r - i n s e r t i s handl e d by the system t e r m i n a l I/O d r i v e r . A t t e n t i o n i n t e r r u p t s do not a b o r t the READ but are s t a c k e d u n t i l the READ c o m p l e t e s . Machine independent I n p u t and Output s p e c i f i c a t i o n s are p r o b a b l y the g r e a t e s t c h a l l e n g e t o the d e s i g n e r o f p o r t a b l e s o f t w a r e systems. The I n t e r l i s p V i r t u a l Machine needs c o n s i d e r a b l e work i n t h i s a r e a b e f o r e i t can be c o n s i d e r e d p o r t a b l e . U n f o r t u n a t e l y , i t i s g e n e r a l l y agreed upon t h a t p a r t i c u l a r l y w i t h r e s p e c t t o I/O i n c r e a s e d p o r t a b i l i t y u s u a l l y means d e c r e a s e d system power. Many systems have p o w e r f u l i n t e r r u p t f a c i l i t i e s or g r a p h i c s c a p a b i l i t i e s which can o n l y be used e f f e c t i v e l y i f system dependencies are a l l o w e d . Chapter 5 61 5.1.2 Complex i t y A l t h o u g h some SUBR's, such as IQUOTIENT, can j u s t l y be c o n s i d e r e d m i n i m a l i n s t r u c t i o n s o f an a b s t r a c t machine, many f u n c t i o n s i n the VM are v e r y complex, a l l o w i n g a g r e a t v a r i e t y o f i n p u t s ( e . g . , s t a c k frame s p e c i f i c a t i o n s , c f . s e c t i o n 3.4.3), or p e r f o r m i n g l a r g e amounts o f p r o c e s s i n g (e.g., SETSYNTAX). We b e l i e v e t h a t the VM can be reduced i n s i z e c o n s i d e r a b l y i f SUBR's are d e f i n e d such t h a t they assume a t a l l t imes the c o r r e c t number and type o f arguments. Many SUBR's check the type o f t h e i r arguments and p r o v i d e d e f a u l t s or p e r f o r m d i f f e r e n t a c t i o n s depending on whether c e r t a i n arguments are p r e s e n t or n o t . A l l t h e s e checks and a d d i t i o n s can e a s i l y be brought t o a h i g h e r l e v e l i n the t o t a l I n t e r l i s p system h i e r a r c h y , thus s h i f t i n g the burden t o the c o m p i l e r . One p a r t i c u l a r type check t h a t g r e a t l y i n c r e a s e s the c o m p l e x i t y o f t h e VM i s performed on numeric arguments. The VM assumes t h a t no SUBR can be resumed a f t e r i t has g e n e r a t e d an e r r o r . The t e r m i n o l o g y used by the VM S p e c i f i c a t i o n i s "cause e r r o r n w i t h c u l p r i t x". The o n l y e x c e p t i o n s are i n the d e f i n i t i o n s o f the f u n c t i o n s FIX and FLOAT: FIX [ n ] I f F I X P [ n ] , r e t u r n n; e l s e i f FLOATP[n]: Represent and r e t u r n as an I n t e g e r the i n t e g e r p a r t o f n; e l s e , F I X [ E R R O R X [ L I S T [ T 0 ; n ] ] ] . The f u n c t i o n FLOAT has a s i m i l a r d e f i n i t i o n . ERRORX i s not a VM f u n c t i o n but i s one o f the t h r e e e n t r i e s i n t o the I n t e r l i s p e r r o r package. The VM i n v o k e s the e r r o r Chapter 5 62 package through FAULTEVAL i f EVAL i s c a l l e d w i t h a bad form, through FAULTAPPLY i f a bad F u n c t i o n a l O b j e c t i s a p p l i e d and through ERRORX i n a l l o t h e r c a s e s . The d e f i n i t i o n o f FIX i n d i c a t e s t h a t i t can r e t u r n an I n t e g e r even i f an e r r o r was caused. I f FIX were a SUBR t h a t i n t e r a c t e d o n l y w i t h the " o u t s i d e w o r l d " t h e r e would be no g r e a t d i f f i c u l t y i n implementing t h i s (at the c o s t o f some a d d i t i o n a l programming). The problem l i e s i n the f a c t t h a t the p h r a s e : I f not F I X P f n ] , l e t n be F I X [ n ] . i s one o f the most f r e q u e n t l y o c c u r r i n g i n the VM S p e c i f i c a t i o n . Hence, i f FIX can r e t u r n from an e r r o r , then e v e r y SUBR u s i n g FIX must a l s o be a b l e t o s u r v i v e a c a l l t o the e r r o r p r o c e s s o r (and t h e r e f o r e the i n t e r p r e t e r ) . I n o t h e r words, e v e r y SUBR must be i n a " c l e a n " s t a t e b e f o r e i t can c a l l F I X. T h i s causes a tremendous i n c r e a s e i n the c o m p l e x i t y o f the SUBR e n c o d i n g s . I f argument c h e c k i n g were t o be l i f t e d t o a h i g h e r l e v e l t h i s p roblem would s i m p l y d i s a p p e a r . For i n s t a n c e , the f u n c t i o n IDIFFERENCE i s d e f i n e d i n the VM a s : IDIFFERENCE[i;j] I f not F I X P f i ] , l e t i be F I X [ i ] . I f not F l X P f J ] , l e t j be F I X Q ] . Represent and r e t u r n as an I n t e g e r the i n t e g e r i - _ j . T h i s c o u l d be r e p l a c e d w i t h an I n t e r l i s p f u n c t i o n IDIFFERENCE [LAMBDA (I J) (%%IDIFF (FIX I) (FIX J ] u s i n g the SUBR d e f i n i t i o n Chapter 5 63 % % I D I F F [ i ; j ] R epresent and r e t u r n as an I n t e g e r the i n t e g e r There i s no reason why the c o m p i l e r s h o u l d not be a b l e t o produce a good t r a n s l a t i o n f o r t h i s f u n c t i o n assuming t h a t i t c o m p i l e s out bottom l e v e l f u n c t i o n s such as %%I D I F F . (Using p r e f i x c h a r a c t e r s such as %% would be q u i t e u s e f u l t o i n d i c a t e danger t o u n s k i l l e d programmers — c f . [Weinreb & Moon, 1979].) I n t e r l i s p - 1 0 a c t u a l l y uses t h i s i d e a i n many c a s e s . For i n s t a n c e , FRPLACD i s a SUBR i n I n t e r l i s p - 1 0 which does not check the v a l i d i t y o f i t s arguments; RPLACD i s a (compiled) f u n c t i o n t h a t checks both arguments and i f no e r r o r i s caused r e t u r n s FRPLACD on i t s arguments. I d e a l l y , the VM o n l y c o n t a i n s such "bottom" l e v e l f u n c t i o n s , making i t a much s m a l l e r and lower l e v e l s u b s e t o f I n t e r l i s p than i t c u r r e n t l y i s . I t w i l l be d i f f i c u l t but worth the e f f o r t t o c o n s t r u c t the s p e c i f i c a t i o n s o f such a s e t o f f u n c t i o n s i n a p o r t a b l e way. 5.1.3 Redundancy Many SUBR's i n the VM are d e f i n e d s t r i c t l y i n terms o f o t h e r VM f u n c t i o n s . T h i s redundancy causes the i m p l e m e n t a t i o n of the VM t o be s u b s t a n t i a l l y l a r g e r than i t need be u n l e s s the implementor e x e c u t e s a SUBR so d e f i n e d by s i m p l y c a l l i n g the r e l e v a n t f u n c t i o n s ( i n which case they might as w e l l have been l e f t i n LISP and c o m p i l e d ) . Some such f u n c t i o n s are the mixed mode a r i t h m e t i c f u n c t i o n s but t h e r e are many o t h e r s . For i n s t a n c e , the VM s p e c i f i c a t i o n o f INFILE i s I N F I L E [ f i l e ] R e t u r n INPUT[OPENFILE[file;INPUT;OLD]]. Chapter 5 64 The i n e f f i c i e n c y i n t r o d u c e d by c o m p i l i n g the c p r r e s p o n d i n g LISP form i n t o a CEXPR i s n e g l i g i b l e . 5.1.4 Incompleteness S e v e r a l VM f u n c t i o n s p e c i f i c a t i o n s are not c o m p l e t e . The most f r e q u e n t o m i s s i o n s are i n the form o f o m i t t e d " e l s e " c l a u s e s such as i n CHARACTER (which r e t u r n s a C h a r a c t e r i f i t s argument i s a v a l i d c h a r a c t e r code, but i f i t i s not the a c t i o n t o be taken i s not s p e c i f i e d ) . Another o m i s s i o n i s cause f o r g r e a t c o n c e r n : the l a c k o f a machine-independent a s s e m b l e r . I f I n t e r l i s p i s t o be p o r t a b l e then one d i r e n e c e s s i t y i s a p o r t a b l e c o m p i l e r w r i t t e n i n I n t e r l i s p which produces i n t e r m e d i a t e code f o r an a b s t r a c t machine, presumably i n l i s t f o r m a t . T h i s machine would be i n c o r p o r a t e d i n the VM ( o r , p r o b a b l y , a c o n s i d e r a b l y m o d i f i e d v e r s i o n o f i t ) . The VM s h o u l d then p r o v i d e ASSEMBLE, a SUBR which t a k e s the a f o r e m e n t i o n e d l i s t o f a b s t r a c t machine code as argument, and produces an o b j e c t o f type CEXPR i n whatever format the implementor d e s i r e s or i s f e a s i b l e . The i n t e r m e d i a t e code c o u l d be assembled "as i s " and i n t e r p r e t e d by the VM (analogous t o the P a s c a l PCODE i n t e r p r e t e r ) . T h i s would p r o b a b l y be too slow t o be e c o n o m i c a l but s t i l l would be c o n s i d e r a b l y f a s t e r than i n t e r p r e t e d LISP code. I t may a l s o be a u s e f u l d e v i c e f o r machine- and system-independent b o o t s t r a p p i n g . A l t e r n a t i v e l y , the i n t e r m e d i a t e code c o u l d be t r a n s l a t e d i n t o d i r e c t l y e x e c u t a b l e machine code u s i n g macros [ G r i s s & Chapter 5 65 Hearn, 1979], or one c o u l d use " t h r e a d e d c o d i n g " [ B e l l , 1973] where e v e r y i n t e r m e d i a t e code i n s t r u c t i o n would be t r a n s l a t e d i n t o a c a l l t o a s u p p o r t p r o c e d u r e implementing the a c t i o n s o f the i n s t r u c t i o n . I f the r e s t o f the I n t e r l i s p system makes no assumptions about the s p e c i f i c i m p l e m e n t a t i o n o f e i t h e r CEXPR o b j e c t s or the VM, then t h e r e i s some hope f o r a c o m p l e t e l y p o r t a b l e I n t e r l i s p system. However, u s i n g t h i s approach (as d e s i r a b l e as i t may seem a t f i r s t g l a n c e ) many q u e s t i o n s c o n c e r n i n g e f f i c i e n t use o f p r o c e s s o r , memory and p e r i p h e r a l r e s o u r c e s remain t o be r e s o l v e d . 5.2 M u l t i l i s p 5.2.1 The I m p l e m e n t a t i o n Language U s i n g P a s c a l as the i m p l e m e n t a t i o n language o f M u l t i l i s p has proved t o be q u i t e b e n e f i c i a l . The s t r i c t t y p i n g r u l e s g r e a t l y a i d e d i n m a i n t a i n i n g c o n s i s t e n c y o f the e n t i r e system. The h i g h degree o f d a t a a b s t r a c t i o n s u p p o r t e d by P a s c a l a l l o w e d e x p e r i m e n t i n g w i t h v a r i o u s d a t a and c o n t r o l s t r u c t u r e s w i t h r e l a t i v e ease. The r u n - t i m e Debug Package [ J o l l i f f e & P o l l a c k , 1979] a v a i l a b l e a t the U n i v e r s i t y o f B r i t i s h Columbia was e x p e c t e d t o be o f g r e a t h e l p i n development o f the system and a n a l y z i n g bugs due t o a d d r e s s i n g i n t e r r u p t s , e t c . A c t u a l l y , l i t t l e use was made o f t h i s f a c i l i t y : once c o m p i l e d c o r r e c t l y , a module u s u a l l y ran w i t h o u t f u r t h e r t r o u b l e . The ease w i t h which the e n t i r e M u l t i l i s p system was t r a n s p o r t e d t o the VAX 11/780 i s Chapter 5 6 6 another p l u s f o r P a s c a l as i m p l e m e n t a t i o n language. O b v i o u s l y , P a s c a l has i t s drawbacks as w e l l . P a r t i c u l a r l y , we found the l a c k o f c l e a n p o i n t e r a r i t h m e t i c d i s t u r b i n g . Pascal/UBC has a n i c e s o l u t i o n f o r t h i s problem. G e n e r i c type t r a n s f e r s a re a l l o w e d between s c a l a r s o f any t y p e , hence i n c r e m e n t i n g a p o i n t e r t o the next word l o o k s l i k e : PTRVAL := p t r ( i n t e g e r (PTRVAL) + BYTESPERWORD); where " p t r " i s the type o f PTRVAL. G e n e r i c type t r a n s f e r s do not r e s u l t i n e x t r a code — they are no-ops e f f e c t i v e a t c o m p i l e - t i m e . U n f o r t u n a t e l y , we c o u l d not use t h i s f e a t u r e s i n c e we were committed t o S t a n d a r d P a s c a l . The o n l y t ype t r a n s f e r a l l o w e d by S t a n d a r d P a s c a l i s between c h a r a c t e r s and i n t e g e r s , and the o n l y way t o p e r f o r m p o i n t e r a r i t h m e t i c i n S t a n d a r d P a s c a l i s by r e c o r d v a r i a n t o v e r l a y , a v e r y u n s a t i s f a c t o r y and machine-dependent method. A l l p o i n t e r s t h a t never r e q u i r e a r i t h m e t i c are indeed p o i n t e r s i n M u l t i l i s p . A l l o t h e r s , p r i m a r i l y those f o r the Heap and Stack Manager, are d e c l a r e d to be o f type ADDRESS, a r e c o r d w i t h p o i n t e r / i n t e g e r o v e r l a y . A second drawback i s t h a t P a s c a l has no p r o v i s i o n f o r f u n c t i o n a l v a r i a b l e s . A l t h o u g h f u n c t i o n a l arguments a r e a l l o w e d , and hence f o r m a l parameters t h a t " h o l d " a f u n c t i o n a l o b j e c t , t h i s o b j e c t i s not a s s i g n a b l e t o a d e c l a r e d v a r i a b l e . T h i s would have been u s e f u l i n t h a t p r o c e d u r e s implementing SUBR's as w e l l as c o n t i n u a t i o n p r o c e d u r e s themselves c o u l d have been d e p o s i t e d i n the M u l t i l i s p o b j e c t s o f type T_SUBR or Chapter 5 67 d e p o s i t e d i n the c o n t i n u a t i o n f i e l d s on the s t a c k , r e s p e c t i v e l y . I n s t e a d , we had to use branch t a b l e s which causes some slowdown i n system performance. T h i r d l y , i m plementing the VM i n a h i g h - l e v e l language such as P a s c a l has i n e v i t a b l y l e d t o a s i g n i f i c a n t r e d u c t i o n i n speed. The heap and s t a c k s u p p o r t i n p a r t i c u l a r need c o n s i d e r a b l e improvement t o become e c o n o m i c a l . (A s m a l l i n v e s t i g a t i o n , u s i n g a program w r i t t e n i n MAYA [Havens, 1978] which makes heavy use o f the s p a g h e t t i s t a c k f a c i l i t i e s , has shown t h a t M u l t i l i s p spent r o u g h l y 34% o f i t s time i n the S t ack Manager and another 18% i n the Heap Manager and i n the f u n c t i o n s CAR and CDR.) However, implementing the VM i n Assembly Language i s p r o h i b i t i v e because o f the s i z e o f the VM u n l e s s l a r g e amounts o f human and m a t e r i a l r e s o u r c e s are i n v e s t e d . The r e s u l t i n g i m p l e m e n t a t i o n would be s i g n i f i c a n t l y f a s t e r , but would be as u n - p o r t a b l e as the c u r r e n t I n t e r l i s p - 1 0 system. 5.2.2 M u l t i l i s p and the VM As was s t a t e d b e f o r e , M u l t i l i s p i s o n l y a p a r t i a l i m p l e m e n t a t i o n o f the I n t e r l i s p V i r t u a l Machine. In p a r t i c u l a r , many lower l e v e l I/O f u n c t i o n s have not y e t been implemented, and the T e r m i n a l T a b l e o b j e c t i s not p r e s e n t f o r the reasons g i v e n i n s e c t i o n 5.1.1. I n i t i a l l y , the I/O was r e d e f i n e d t o i n c o r p o r a t e the l i n e - o r i e n t e d n a t u r e o f the MTS o p e r a t i n g system and we ended up s i m u l a t i n g a l i n e - o r i e n t e d f i l e system on the VAX-11/780 under VMS which s u p p o r t s c h a r a c t e r f i l e I/O. The s i t u a t i o n i s now r e v e r s e d so t h a t the VAX v e r s i o n i s c o n s i s t e n t Chapter 5 68 w i t h the VM S p e c i f i c a t i o n . C h a r a c t e r f i l e I/O s i m u l a t i o n under MTS s t i l l remains t o be implemented. Because o f the i n c o m p a t i b i l i t i e s between the VM and the r e s t o f I n t e r l i s p s t a t e d i n s e c t i o n 2.3 we have not been a b l e t o l o a d and run s i g n i f i c a n t p o r t i o n s o f the I n t e r l i s p System. I t has t h e r e f o r e not y e t been p o s s i b l e t o determine the c o r r e c t n e s s o f M u l t i l i s p . We can o n l y be ( r e l a t i v e l y ) s u r e o f c o n f o r m i t y w i t h the VM S p e c i f i c a t i o n . So f a r as i s known t o the a u t h o r , no i m p l e m e n t a t i o n o f the I n t e r l i s p System has s t a r t e d w i t h a complete i m p l e m e n t a t i o n o f the I n t e r l i s p V i r t u a l Machine and o b t a i n e d the r e s t o f the system by means o f b o o t s t r a p p i n g the I n t e r l i s p - 1 0 f i l e s . So we cannot be s u r e t h a t i t i s even p o s s i b l e ! 5.3 D i r e c t i o n s f o r F u t u r e R esearch I n o r d e r t o a t t a i n the g o a l o f p o r t a b i l i t y o f I n t e r l i s p much work remains t o be done. F i r s t o f a l l , a r e d e s i g n o f the V i r t u a l Machine i s d e s i r a b l e i n o r d e r t o remove system dependencies and redundant f u n c t i o n d e f i n i t i o n s . The VM must become a m i n i m a l machine c o n t a i n i n g o n l y f u n c t i o n s or i n s t r u c t i o n s which are o r t h o g o n a l t o one another as much as p o s s i b l e . S e c o n d l y , a machine independent i n t e r f a c e between a c o m p i l e r and the VM i n the form o f i n t e r m e d i a t e code needs t o be d e s i g n e d , so t h a t the l a r g e amount of I n t e r l i s p s o f t w a r e can be run w i t h i n r e a l i s t i c bounds o f time and space. Chapter 5 69 T h i r d l y , much o f the h i g h e r l e v e l I n t e r l i s p s u p p o r t s o f t w a r e needs t o be examined and m o d i f i e d i n o r d e r t o remove a l l the p e c u l i a r i t i e s due t o the I n t e r l i s p - 1 0 i m p l e m e n t a t i o n . F o u r t h l y , the l e v e l on which the V i r t u a l Machine o p e r a t e s i s s u b j e c t t o f u r t h e r i n v e s t i g a t i o n . The VM i s c u r r e n t l y d e f i n e d as a s u b s e t o f the I n t e r l i s p System. Another approach to p o r t a b i l i t y i s t o d e f i n e the V i r t u a l Machine i n terms o f a b s t r a c t machine i n s t r u c t i o n codes analogous t o the P a s c a l PCODE machine. Both approaches appear t o have m e r i t and a p o s s i b l e s o l u t i o n t o t h i s dilemma might l i e i n a h y b r i d machine combining the advantages o f a b s t r a c t i o n a t the machine l e v e l w i t h the advantages o f complete (but minimal) SUBR d e f i n i t i o n s a t the language s u b s e t l e v e l . F i n a l l y , f u r t h e r i n v e s t i g a t i o n s are n e c e s s a r y t o determine the f e a s i b i l i t y and c o s t - e f f e c t i v e n e s s o f a p o r t a b l e I n t e r l i s p system. Both improvements i n s o f t w a r e d e s i g n and f u t u r e advances i n hardware c a p a b i l i t i e s may w e l l o f f s e t any i n i t i a l r e d u c t i o n s i n speed or i n c r e a s e s i n space r e q u i r e m e n t s due t o p o r t a b i l i t y o f the system. 70 6. C o n c l u s i o n I n t h i s t h e s i s we have examined the I n t e r l i s p V i r t u a l Machine and an i m p l e m e n t a t i o n t h e r e o f i n some d e t a i l , f o c u s s i n g our a t t e n t i o n p a r t i c u l a r l y on p o r t a b i l i t y i s s u e s . We have shown i n C h a p t e r s 3 and 5 t h a t the VM has been a u s e f u l d e v i c e i n d e s c r i b i n g the b a s i c s o f I n t e r l i s p but t h a t i t f a i l s i n a number o f r e s p e c t s . I t s system-dependencies, i n c o m p l e t e n e s s o f many SUBR d e f i n i t i o n s , the l a c k o f an i n t e r m e d i a t e code a s s e m b l e r , and i t s l a r g e s i z e because o f much t y p e - c h e c k i n g and d e f a u l t - p r o v i d i n g code a l l c o n f l i c t w i t h the concept o f a p o r t a b l e " v i r t u a l " machine. Chapter 4 d e s c r i b e d some o f the p a r t i c u l a r d i f f i c u l t i e s e n c o u ntered i n the i m p l e m e n t a t i o n o f the V i r t u a l Machine and some o f the s t r a t e g i e s employed i n d a t a , c o n t r o l and memory m a n i p u l a t i o n s . M u l t i l i s p s t i l l needs c o n s i d e r a b l e work t o make the i m p l e m e n t a t i o n o f the VM complete and t o t a l l y c o m p a t i b l e w i t h the remainder o f the I n t e r l i s p System. Chapter 2 has shown i n summary t h a t t h i s g o a l may not even be a t t a i n a b l e because o f the system dependencies i n c o r p o r a t e d i n the I n t e r l i s p b o o t s t r a p p i n g f i l e s . We b e l i e v e t h a t the A b s t r a c t Machine approach i s a v i a b l e way o f s p e c i f y i n g and implementing a p o r t a b l e I n t e r l i s p System. To t h i s end the V i r t u a l Machine needs c o n s i d e r a b l e r e v i s i o n and r e f i n e m e n t . I t i s our hope t h a t the M u l t i l i s p i m p l e m e n t a t i o n may be a gu i d e i n i s o l a t i n g those p a r t s o f the VM t h a t c u r r e n t l y Chapter 6 71 make i t d i f f i c u l t t o implement and n o n - p o r t a b l e . We b e l i e v e , f o r r easons s e t out i n Chapter 3, t h a t p o r t a b i l i t y s h o u l d be o f prime c o n c e r n t o a l l system d e v e l o p e r s , and p a r t i c u l a r l y t o those implementing LISP systems. The development c o s t s may be h i g h e r , but the advantages f a r outweigh the d i s a d v a n t a g e s . 72 B i b l i o g r a p h y 1. A l l e n . J . (1978) Anatomy o f LISP. M c G r a w - H i l l . New Y o r k , NY. 2. B a r t h , J.M. (1977) " S h i f t i n g Garbage C o l l e c t i o n Overhead t o Compile Time", Comm. ACM, V o l . 20, #7, pp. 513-518. 3. B a k e r , H.G. (1978) " L i s t P r o c e s s i n g i n R e a l Time on a S e r i a l Computer", Comm. ACM, V o l . 21, #4, pp. 280-294. 4. B a k e r , H.G. (1978) " S h a l l o w B i n d i n g i n L i s p 1.5", Comm. ACM, V o l . 21, #7, pp. 565-569. 5. B e l l , J.R. (1973) "Threaded Code", Comm. ACM, V o l . 16, #6, pp. 370-372. 6. B l a i r , F.W. (1979) LISP/370 Concepts and F a c i l i t i e s , T e c h n i c a l Report RC 7771, IBM Thomas J . Watson Research C e n t e r , New York, NY. 7. Bobrow, D.G. and Murphy, D.L. (1967) " S t r u c t u r e o f a LISP System U s i n g Two-Level S t o r a g e " , Comm. ACM, V o l . 10, #3, pp. 155-159. 8. Bobrow, D.G., B u r c h f i e l d , J.D., Murphy, D.L. and To m l i n s o n , R.S. (1972) "Tenex, a Paged Time S h a r i n g System f o r the PDP-10", Comm. ACM, V o l . 15, #3, pp. 135-143. 9. Bobrow, D.G. (1972) "Requirements f o r Advanced Programming Systems f o r L i s t P r o c e s s i n g " , Comm. ACM, V o l . 15, #7, pp. 618-627. 10. Bobrow, D.G. and W e g b r e i t , B. (1973) "A Model and St a c k I m p l e m e n t a t i o n o f M u l t i p l e E n v i r o n m e n t s " , Comm. ACM, V o l . 16, #10, pp. 591-603. 11. Bobrow, D.G. (1975) "A Note on Hash L i n k i n g " , Comm. ACM, V o l . 18, #7, pp. 413-415. 12. Bowles, K.L. (1977) Microcomputer Problem S o l v i n g U s i n g  P a s c a l , S p r i n g e r - V e r l a g . 13. Cheney, C.J. (1970) "A N o n r e c u r s i v e L i s t Compacting A l g o r i t h m " , Comm. ACM, V o l . 13, #11, pp. 677-678. 14. C l a r k , D.W. (1976) "An E f f i c i e n t L i s t - M o v i n g A l g o r i t h m U s i n g C o n s t a n t Workspace", Comm. ACM, V o l . 19, #6, pp. 352-354. B i b l i o g r a p h y 73 15. C l a r k , D.W. and Green, C.C. (1977) "An E m p i r i c a l Study of L i s t S t r u c t u r e i n LISP", Comm. ACM, V o l . 20, #2, pp. 78-87. 16. Cohen, J . (1967) "A Use of Fa s t and Slow Memories i n L i s t - P r o c e s s i n g Languages", Comm. ACM, V o l . 10, #2, pp. 82-86. 17. Comfort, W.T. (1964) "Multiword L i s t Items", Comm. ACM, V o l . 7, #6, pp. 357-362. 18. Cox, L.A. and T a y l o r , W.P. (1978) A P o r t a b l e LISP  I n t e r p r e t e r , UCRL-52417, Lawrence Livermore Laboratory, Pasadena, CA. 19. Deutsch, L.P. (1973) "A LISP Machine with Very Compact Programs", Proceedings of the T h i r d I n t e r n a t i o n a l J o i n t  Conference on A r t i f i c i a l ~ I n t e l l i g e n c e , pp. 697-703. 20. Deutsch, L.P. and Bobrow, D.G. (1976) An E f f i c i e n t , Incremental, Automatic Garbage C o l l e c t o r " , Comm. ACM, V o l . 19, #9, pp. 522-526. 21. Deutsch, L.P. (1978) "Experience with a Microprogrammed I n t e r l i s p System", IEEE Micro-11 Conference, pp. 128-129. 22. F e n i c h e l , R.R. and Yochelson, J.C. (1969) "a LISP Garbage-C o l l e c t o r f o r Virtual-Memory Computer systems", Comm. ACM, V o l . 12, #11, pp. 611-612. 23. F i s h e r , D.A. (1975) "Copying C y c l i c L i s t S t r u c t u r e s i n Lin e a r Time Using Bounded Workspace", Comm. ACM, V o l . 18, #5, pp. 251-252. 24. Fox, M.C. (1978) Machine A r c h i t e c t u r e and the Programming  Language BCPL, Master's T h e s i s , Univ. of B r i t i s h Columbia. 25. G r e e n b l a t t , R. (1974) The L i s p Machine, Working paper 79, MIT, Cambridge, MA. 26. G r i s s , M.L. and Hearn, A.C. (1979) A P o r t a b l e LISP  Compiler, UCP-76, Dept. o f Computer S c i e n c e , Univ. o f Utah, S a l t Lake C i t y , Utah. 27. Hansen, W.J. (1969) "Compact L i s t R e p r e s e n t a t i o n : D e f i n i t i o n , Garbage C o l l e c t i o n , and System Implementation", Comm. ACM, V o l . 12, #9, pp. 499-507. 28. Havens, W.S. (1978) A P r o c e d u r a l Model of Re c o g n i t i o n f o r  Machine P e r c e p t i o n , TR-78-3, Comp. Science Dept., Univ. o f B r i t i s h Columbia, Vancouver, Canada. B i b l i o g r a p h y 74 29. J e n s e n , K. and W i r t h , N. (1974) PASCAL - User Manual and  R e p o r t , S p r i n g e r - V e r l a g , B e r l i n . 30. J o l l i f f e , B. and P o l l a c k , B.W. (1979) UBC PASCAL:  Pascal/UBC Programmer's G u i d e , U n i v e r s i t y o f B r i t i s h C o l u m b i a , Vancouver, Canada. 31. Knuth, D.E. (1968) Fundamental A l g o r i t h m s , V o l I, Addison-Wesley, Reading, MA. 32. L i n d s t r o m , G. (1974) "Copying L i s t S t r u c t u r e s U s i n g Bounded Workspace", Comm. ACM, V o l . 17, #4, pp. 198-202. 33. M a s i n t e r , L.M., B u r t o n , R. and o t h e r s ( 1 9 8 0 ) p e r s o n a l communications , Xerox P a l o A l t o Research C e n t e r , P a l o A l t o , CA. 34. McCarthy, J . (1960) " R e c u r s i v e F u n c t i o n s o f S y m b o l i c E x p r e s s i o n s and T h e i r Computation by Machine, P a r t I " , Comm. ACM, V o l . 3, #4, pp. 184. 35. McCarthy, J . , Abrahams, P.W., Edwards, D.J., H a r t , T.P. and L e v i n , M.I. (1962) LISP 1. 5 Programmer's Manual, The M.I.T. P r e s s , Cambridge, MA. 36. Moore, J.S. (1976) The INTERLISP V i r t u a l Machine  S p e c i f i c a t i o n , Xerox P a l o A l t o Research C e n t e r , P a l o A l t o , CA ( r e v i s e d 1979). 37. M o r r i s , F.L. (1978) "A Time- and S p a c e - E f f i c i e n t Garbage Compaction A l g o r i t h m " , Comm. ACM, V o l . 2 1 , #8, pp. 662-665. 38. Meyers, W. (1980) "Computer G r a p h i c s : The Human I n t e r f a c e " , COMPUTER, V o l . 13, #6, pp. 45-54. 39. N o r i , K.V., Ammann, U., J e n s e n , K. and N a e g e l i , H.H. (1974) The PASCAL <P> C o m p i l e r : I m p l e m e n t a t i o n N o t e s , B e r i c h t e des I n s t i t u t s f u r I n f o r m a t i k , E i d g e n o s s i s c h e T e c h n i s c h e Hochschule Z u r i c h . 40. R e i n g o l d , E.M. (1973) "A N o n r e c u r s i v e L i s t Moving A l g o r i t h m " , Comm. ACM, V o l . 16, #5, pp. 305-307. 41. R i c h a r d s , M. (1969) "BCPL: A t o o l f o r c o m p i l e r w r i t i n g and systems programming", P r o c e e d i n g s o f the S p r i n g J o i n t  Computer C o n f e r e n c e , V o l . 34, pp. "5T7-566. 42. R i c h a r d s , M. (1971) "The P o r t a b i l i t y o f the BCPL C o m p i l e r " , S o f t w a r e - P r a c t i c e and E x p e r i e n c e , V o l . 1, #2, PP. 1 3 5 -1T6": B i b l i o g r a p h y 75 43. Robson, J.M. (1977) "A Bounded S t o r a g e A l g o r i t h m f o r Copying C y c l i c S t r u c t u r e s " , Comm. ACM, V o l . 20, #6, pp. 431-433. 44. S a n d e w a l l , E. (1978) "Programming an I n t e r a c t i v e E n vironment: the LISP E x p e r i e n c e " , ACM Computing S u r v e y s , V o l . 10, #1, pp. 35-71. 45. S c h o r r , H. and W a i t e , W.M. (1967) "An E f f i c i e n t Machine-Independent p r o c e d u r e f o r Garbage C o l l e c t i o n i n V a r i o u s L i s t S t r u c t u r e s " , Comm. ACM, V o l . 10, #8, pp. 501-506. 46. S t e e l e , G.L. (1977) "Macaroni i s B e t t e r than S p a g h e t t i " , P r o c e e d i n g s o f the Symposium on A r t i f i c i a l I n t e l l i g e n c e and  Programming Languages, pp. ^0^6. 47. T e i t e l m a n , W. (1976) "CLISP: C o n v e r s a t i o n a l L i s p " , IEEE T r a n s a c t i o n s on Computers, V o l . 25, #4, pp. 354-357. 48. T e i t e l m a n , W. (1978) INTERLISP R e f e r e n c e Manual, Xerox P a l o A l t o Research C e n t e r . 49. W e g b r e i t , B. (1972) "A G e n e r a l i z e d C o m p a c t i f y i n g Garbage C o l l e c t o r " , Computer J o u r n a l , V o l . 15, #3, pp. 204-208. 50. Weinreb, D. and Moon, D. (1979) L i s p Machine Manual, MIT, Cambridge, MA. 51. W i r t h , N. (1971) "The Programming Language PASCAL", A c t a I n f o r m a t i c a , V o l . 1, pp. 35-63. 76 Appendix A F u n c t i o n s d e c l a r e d as SUBR's i n the VM S p e c i f i c a t i o n and as EXPR's i n the I n t e r l i s p R e f e r e n c e Manual: ALPHORDER ANTILOG ARCCOS ARCSIN ARCTAN ARGLIST ARRAYSIZE ARRAYTYP CALLSCCODE CLOSEALL CLOSEF COPYALL COPYBYTES COS DCHCON DECLAREDATATYPE DEFEVAL DELETECONTROL DELFILE DIFFERENCE DISMISS DISPLAYTERMP DOBE DRIBBLE DUNPACK ECHOCONTROL EXPT FDIFFERENCE FETCHFIELD FILEPOS FIX FIXP FLESSP FLOAT FMINUS FNTYP FULLNAME FUNCTION GCD GCGAG GETDESCRIPTORS GETFIELDSPECS GETFILEINFO GETPROPLIST GETSYNTAX HARRAYP HARRAYSIZE I DATE IDIFFERENCE ILESSP IMINUS LESSP LOG LRSH MAKEBITTABLE MAPHASH NARGS NCREATE OPENFILE RAND RANDACCESSP RANDSET RECLAIM RELSTKP RENAMEFILE REPLACEFIELD RPLACA RPLACD RSH SETA SETFILEINFO SETPROPLIST SETSYNTAX SIN SKREAD SMALLP SQRT STORAGE STRPOS STRPOSL TAN USERDATATYPES USERNAME F u n c t i o n s d e c l a r e d as SUBR's i n the V i r t u a l Machine S p e c i f i c a t i o n which do not appear i n the I n t e r l i s p R e f e r e n c e Manual: BUFP MKFRAME SETCLINK CHANGECCODE OVERFLOW SETINTERRUPT GETINTERRUPT SETALINK Appendix A 77 F u n c t i o n s d e c l a r e d as SUBR's i n the I n t e r l i s p R e f e r e n c e which do not appear i n the VM S p e c i f i c a t i o n : ARRAYBEG BLKAPPLY BLKAPPLY* CLOSER DDT ELTD ERRORN ERRORSET ERRORSTRING ERROR! ESCAPE FCHARACTER FRPLACA FRPLACD GCMESS GETATOMVAL GETBLK HERALD INTERRUPTABLEP JSYS LOC MAKESYS NCONC NTYP OPENF OPENR OPNJFN PACK* RELBLK RESET RESETVARS RESUME SCODEP SETATOMVAL SETERRORN SETSBSIZE SETSTKNAME SWPARRAY SWPARRAYP SYSTEMTYPE VAG I n t e r l i s p V i r t u a l Machine SUBR's not y e t implemented i n M u l t i l i s p : BACKTRACE BKLINBUF BKSYSBUF BUFP CALLSCCODE CHANGECCODE CLEARBUF CONTROL COPYBYTES COPYTERMTABLE DELETECONTROL DISPLAYTERMP DOBE DRIBBLE DRIBBLEFILE ECHOCONTROL ECHOMODE FILEPOS GCD GCTRP GETFILEINFO GETINTERRUPT GETTERMTABLE I DATE INTERRUPTABLE LINBUF PRIN3 PRIN4 RAISE RANDACCESSP RATEST RATOM READP RESETTERMTABLE RSTRING SETFILEINFO SETINTERRUPT SETTERMTABLE SKREAD SYSBUF Appendix B M u l t i l i s p O b j e c t R e p r e s e n t a t i o n : PTR = @ OBJECT; OBJECT = packed r e c o r d case OBJTYPE T_INDIRECT T_CMPCT_NIL, T_CMPCT_NEXT T_LISTP T_FORWARD T LITATOM T_FIXP T_FLOATP T_IARRAYP T_PARRAYP T_HARRAYP T_READTABLEP T_STACKP T STRINGP OBJECT_TYPE o f (INDPTR : PTR) ; (CARPTR : PTR) ; (CARP, CDRP : PTR); (FWDPTR : PTR); (TOPVAL, PLIST, FUNDEF, HASH_LINK PNAME (IVAL (RVAL (IR_SIZE IR_VECTOR (PR_SIZE . PR_VECTOR (HR_SIZE HR VECTOR PTR; : STRING); INTEGER); REAL); : SHRTINT; INTVECTOR); SHRTINT; PTRVECTOR); SHRTINT; BINDVECTOR); (MACROS_ENABLED : BOOLEAN; READ_TAB LE : RDTBLVECTOR) (FRAMEP : STACKPTR; STP_LINK : PTR); (FIRST_CHAR, CHAR_COUNT : SHRTINT; SOURCE : PTR); T STRINGPNAME (STR : STRING); Appendix B T_BITTABLEP T USER TYPE T USER OBJECT T_DESCR_PTR, T_DESCR_BIT, T_DESCR_FIXP, T DESCR FLOATP T_CEXPR, T SUBR (BIT_TABLE : (TYPESIZE TYPENAME, LAST_DESCR, NEXT_TYPE (USERTYPE BYTES (OFFSET PREV DESCR (NPARAMS EVALFLAG , SPREADFLAG BITTBLVECTOR); : SHRTINT; : PTR) ; : PTR; : L I N E ) ; SHRTINT; PTR) ; : COUNTER; BOOLEAN; case OBJECT_TYPE o f T_CEXPR : ( ) ; (* no such t h i n g y e t *) T_SUBR : (SUBR_ADDR : SUBR_INDICES)) end (* o b j e c t * ) ; Memory r e q u i r e m e n t s i n b y t e s Pascal/UBC (Amdahl 470): VMS P a s c a l (VAX 11/780) M ARRAYP 4, M ARRAYP = 3 M BITTBLP = 516 M BITTBLP = 33 M CEXPR — 8, M CEXPR = 3 M COMPACT = 8 M COMPACT = 5 M DESCR = 8 M DESCR = 7 M FIXP = 8 M FIXP = 5 M FLOATP = 16 M FLOATP = 5 M FORWARD 8 M FORWARD = 5 M LISTP = 12 M LISTP = 9 M LITATOM = 22 M LITATOM = 19 M RDTBLP = 1028 M RDTBLP - 1026 M SMALLP = 2 M SMALLP 1 M STACKP = 12 M STACKP = 9 M STRINGP 12 M STRINGP = 9 M STRPNAME 4 M STRPNAME 3 M SUBR = 12 M SUBR - 5 M TERMTBLP = 8 M TERMTBLP - 5 M USERTYPE = 16 M USERTYPE = 15 M USEROBJ — 8 M USEROBJ = 5 80 Appendix C The a l g o r i t h m f o r n o n - r e c u r s i v e l i s t compaction used by the M u l t i l i s p Garbage C o l l e c t o r : p r o c e d u r e MOVE_LIST (var OLDLIST : PTR); (* I t e r a t i v e l i s t move and compaction p r o c e d u r e . *) (* W i l l a l s o work on c i r c u l a r l i s t s . *) (* On e x i t OLDLIST i s r e s e t t o address o f c o p i e d l i s t *) l a b e l 1; (* f o r f a s t C D R 1 i n g down the l i s t *) va r CARVAL, LIST, NEXT : PTR; b e g i n LIST := OLDLIST; (* l o c a l t o CDR down OLDLIST *) OLDLIST := HEAP_BOTTOM.P; (* and s e t var parameter *) L: i f HEAP_BOTTOM.I >= HEAP_TOP.I then ERROR (1 , n i l ) ; CARVAL := CAR ( L I S T ) ; (* NOTE: Not c o p i e d y e t ! *) NEXT := CDR ( L I S T ) ; (* Jumps t h r u i n d i r e c t c e l l s *) LIST@.OBJTYPE := T_FORWARD; (* l e a v e f o r w a r d i n g *) LIST@.FWDPTR := HEAP_BOTTOM.P; (* address b e h i n d *) w i t h HEAP_BOTTOM.P@ do T f NEXT@.OBJTYPE <= T_LISTP then b e g i n (* make compact-next *) OBJTYPE CARPTR HEAP_BOTTOM.I LIST = T_CMPCT_NEXT; = CARVAL; = HEAP_BOTTOM.I + M_COMPACT; = NEXT; goto 1; (* and CDR down the o l d l i s t *) end e l s e i f NEXT = A_NIL then (* make c o m p a c t - n i l *) b e g i n OBJTYPE CARPTR HEAP_BOTTOM.I end = T_CMPCT_NIL; = CARVAL; = HEAP BOTTOM.I + M COMPACT; e l s e (* NEXT p o i n t s t o an a l r e a d y c o p i e d l i s t or *) b e g i n (* t o some n o n - l i s t , so make a t r u e l i s t p *) OBJTYPE CARP CDRP HEAP_BOTTOM.I end; end (* move l i s t * ) ; = T_LISTP; = CARVAL; = NEXT; = HEAP BOTTOM.I + M LISTP; 81 Appendix D Stack frame d e c l a r a t i o n s ; STACKPTR = @ STACKFRAME; BLOCKPTR = @ STACKBLOCK; STACKFRAME = packed r e c o r d LAST, NEXT, TOP : ADDRESS; case BOOLEAN o f TRUE : (NAME : PTR; REFCNT, NARGS : COUNTER; ARGP : BINDVECTOR); (* s t a c k management *) (* B a s i c frame *) FALSE : (USECNT PROGFLAG, TRACEMARK MACROSTATUS ALINK, BLINK, CLINK TOP_BLOCK end (* s t a c k f r a m e * ) ; COUNTER; BOOLEAN; MACROSTATE; STACKPTR; BLOCKPTR); (* Frame e x t e n s i o n *) STACKBLOCK = packed r e c o r d LAST_BLOCK : BLOCKPTR; BLIP_FORM, BLIP_TAIL : PTR; BLOCKSIZE : COUNTER; CONTINUATION : CNT POINTS; (* e v a l or temp b l o c k *) (*. f o r frame e x t e n s i o n s *) case BLIP_ARGS TRUE : (NARGVALS BLIP_FN ARGVAL BOOLEAN o f COUNTER; PTR; PTRVECTOR); (* B l i p u s i n g *) FALSE : (DOTFLAG, BRACKETFLAG READFILE NTEMPS TEMPINT TEMP end (* s t a c k b l o c k * ) ; BOOLEAN; FILEINDEX; COUNTER; SHRTINT; PTRVECTOR) ; (* Temporaries *) Appendix D 82 G r a p h i c l a y o u t f o r s t a c k frames under VMS P a s c a l : === B a s i c frame l a y o u t : ( s i z e : 18 + 8 * NARGS byt e s ) *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | LAST | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | NEXT | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | TOP | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | NAME | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | REFCNT | NARGS | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* then f o r each b i n d i n g I : *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | ARGP(.I.).ITEM | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | ARGP(.I.).BINDING | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* === Frame e x t e n s i o n l a y o u t : ( s i z e : 30 byte s ) *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | LAST | *—I—l—l—l—l—l—l—*—l—l—l—l—l—I—l—*—l—l—I—l—I—I—I—*—I—I—I—I—I—I—I-—* | NEXT | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | TOP | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | USECNT |P|T| M I = = = = = = = I *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | ALINK | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | BLINK ^ | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | CLINK | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | TOP_BLOCK | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* where P : PROGFLAG, T : TRACEMARK, M : MACROSTATUS, === : unused Appendix D 83 === B l i p u s i n g b l o c k l a y o u t : ( s i z e : 19 + 4 * NARGVALS by t e s ) *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | L A S T _ B L O C K | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | B L I P FORM | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-"*"-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | B L I P T A I L | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-^"-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | B L O C K S I Z E | CONT'N |B|===| N A R G V A L S | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | B L I P _ F N | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* where CONT'N : C O N T I N U A T I O N , B : B L I P A R G S then f o r each * A R G V A L * I : *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | A R G V A L ( . I . ) | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* === Temporaries b l o c k l a y o u t : ( s i z e : 18 + 4 * NTEMPS by t e s ) *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | L A S T _ B L O C K | *_+_+_+_+_+_+_+_*_+_+_+_+_+_+_+_*_+_+_+_+_+_+_+_*_+_+_+_+_+_+_+_* | B L I P _ F O R M | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | B L I P _ T A I L | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | B L O C K S I Z E | CONT'N |B|D|F| R E A D F I L E | NT E M P S | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | T E M P I N T | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* where B : B L I P A R G S , D : D O T F L A G , F : B R A C K E T F L A G then f o r each temporary: *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* | T E M P ( . I . ) | *-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-* 84 Appendix E The i n f i n i t e l o o p o f the i n t e r p r e t e r : b e g i n (* M u l t i l i s p Main Progam *) (* I n i t i a l i z e the system *) 1111 : (* L a b e l f o r r e - e n t e r i n g the l o o p from ERROR, e t c . *) i f ATTN_INTERRUPT then ERROR (18, A _ N I L ) ; i f ACTBLOCK = n i l then POP_ACTFRAME; i f ACTFRAME@.USECNT > 1 then i f ACTFRAME <> TOPFRAME then SPLIT ACTFRAME; case ACTBLOCK?.CONTINUATION o f ~ DONT CONTINUE REL ACTBLOCK; CONTINUE TOPLEVEL : CNT TOPLEVEL; CONTINUE AND CNT AND; CONTINUE" "ARG : CNT ARG; CONTINUE" "COND CNT COND; CONTINUE "1 EVALQT i CNT1 EVALQT; CONTINUE "2 EVALQT CNT2 EVALQT; CONTINUE EVLIS : CNT EVLIS; CONTINUE" 1 PROG • CNT1 PROG; CONTINUE "2 PROG : CNT2 PROG; CONTINUE" "MAPATOMS : CNT MPATOMS; CONTINUE MAPHASH : CNT MPHASH; CONTINUE" OR : CNT OR; CONTINUE" PROG1 CNT 1PROG; CONTINUE" PROGN • CNT NPROG; CONTINUE 1 READ : CNT1 READ; CONTINUE 2 READ : CNT2 READ; CONTINUE 3 READ CNT3 READ; CONTINUE" "4 READ : CNT4 READ; CONTINUE" "5 READ • CNT5 READ; CONTINUE" 6 READ : CNT6 READ; CONTINUE" REHASH CNT REHASH; CONTINUE" SETARG : CNT SARG; CONTINUE" SETN : CNT NSET; CONTINUE" SETQ : CNT SETQ; end; g o t o 1111; 9999 : (* E x i t : got here through LOGOUT *) end (* M u l t i l i s p Main Program * ) . 85 A n n o t a t e d t r a c e o f s t a c k example F00 Appendix F * $run i n t r t v m > > Welcome t o M u l t i l i s p - v e r s i o n 2.0 - 01:35 / 05-07-80 > • • • ; quote (') s e t u p , CLEARSTKLST <- NIL • • • * (PUTDQ FOO * (NLAMBDA (STP) * (PRINT 'Hi) * ((LAMBDA (FRAME) * (COND ((STACKP FRAME) (SET STP FRAME)) * (T (PRINT FRAME)))) * (STKPOS 'FOO)) * (PRINT 'there) * 'FOO-exit)) > FOO * (DEBUG STACK) > STACK ; c a l l EVALQT + <><><> B a s i c c r e a t e d a t #0065505C EVALQT + <><><> Frame c r e a t e d a t #00655078 + <><><> B l o c k c r e a t e d . ; f o r r u n n i n g EVALQT ; c a l l READ * (FOO BAR) + <><><> B l o c k c r e a t e d . ; Read a l i s t + <><><> R e l e a s i n g b l o c k . ; l i s t done ; e x i t READ ; c a l l FOO + <><><> B a s i c c r e a t e d a t #006550B4 FOO + <><><> Frame c r e a t e d a t #006550D0 + <><><> B l o c k c r e a t e d . ; f o r r u n n i n g FOO +; <><><> B l o c k c r e a t e d . ; E v a l PRINT a r g + <><><> R e l e a s i n g b l o c k . ; PRINT a r g E v a l e d ; c a l l PRINT > H i ; e x i t PRINT + <><><> B l o c k c r e a t e d . ; E v a l LAMBDA a r g + <><><> B l o c k c r e a t e d . ; E v a l STKPOS a r g + <><><> R e l e a s i n g b l o c k . ; STKPOS a r g E v a l ' e d ; c a l l STKPOS + <><><> B a s i c c r e a t e d a t #00655124 STKPOS + <><><> Frame c r e a t e d a t #00655158 + <><><> R e l e a s i n g frame a t #00655158 + <><><> R e l e a s i n g b a s i c a t #00655124 STKPOS Appendix F 86 + <><><> S p l i t t i n g frame to #00655124 + <><><> R e l e a s i n g b l o c k . + <><><> B a s i c c r e a t e d a t #00655160 + <><><> Frame c r e a t e d a t #0065517C + <><><> B l o c k c r e a t e d . + <><><> B a s i c c r e a t e d a t #006551B8 + <><><> Frame c r e a t e d a t #006551D4 + <><><> B l o c k c r e a t e d . + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . + <><><> R e l e a s i n g frame a t #006551D4 + <><><> R e l e a s i n g b a s i c a t #006551B8 + <><><> R e l e a s i n g frame a t #0065517C + <><><> R e l e a s i n g b a s i c a t #00655160 + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . > t h e r e + <><><> R e l e a s i n g frame a t #00655124 + <><><> S p l i t t i n g frame t o #00655124 > FOO-ex i t + <><><> R e l e a s i n g frame a t #00655124 + <><><> B a s i c c r e a t e d a t #00655124 + <><><> Frame c r e a t e d a t #00655140 + <><><> B l o c k c r e a t e d . * (RETTO BAR (QUOTE H e l l o ) ) + <><><> B l o c k c r e a t e d . + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . + <><><> R e l e a s i n g b l o c k . + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . + <><><> B a s i c c r e a t e d a t #0065517C + <><><> Frame c r e a t e d a t #006551A8 + <><><> R e l e a s i n g frame a t #006551A8 + <><><> R e l e a s i n g b a s i c a t #0065517C ; r e a c t i v a t e FOO FOO ; LAMBDA a r g E v a l ' e d ; c a l l LAMBDA (LAMBDA (FRAME) — ) ; f o r r u n n i n g LAMBDA ; c a l l COND COND E v a l 1 s t c l a u s e E v a l STACKP a r g STACKP a r g E v a l ' e d c a l l STACKP e x i t STACKP E v a l SET ar g s SET a r g s E v a l ' e d c a l l SET e x i t SET e x i t COND COND ; e x i t LAMBDA (LAMBDA (FRAME) — ) ; E v a l PRINT a r g ; PRINT a r g E v a l ' e d ; c a l l PRINT ; e x i t PRINT ; e x i t FOO ; r e a c t i v a t e EVALQT EVALQT ; c a l l PRINT ; e x i t PRINT ; e x i t EVALQT ; c a l l EVALQT EVALQT ; f o r r u n n i n g EVALQT ; c a l l READ read read l i s t l i s t e x i t E v a l RETTO ar g s c a l l RETTO RETTO a l i s t a l i s t done done READ RETTO arg s E v a l ' e d ; r e l e a s e a c t i v e c h a i n RETTO Appendix F + <><><> R e l e a s i n g frame a t + <><><> R e l e a s i n g b a s i c a t + <><><> S p l i t t i n g frame t o + <><><> R e l e a s i n g b l o c k . + <><><> B a s i c c r e a t e d a t + <><><> Frame c r e a t e d a t + <><><> B l o c k c r e a t e d . + <><><> B a s i c c r e a t e d a t + <><><> Frame c r e a t e d a t + <><><> B l o c k c r e a t e d . + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . > H e l l o + <><><> R e l e a s i n g frame a t + <><><> R e l e a s i n g b a s i c a t + <><><> R e l e a s i n g frame a t + <><><> R e l e a s i n g b a s i c a t + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . > t h e r e + <><><> R e l e a s i n g frame a t + <><><> S p l i t t i n g frame t o > FOO-exit + <><><> R e l e a s i n g frame a t + <><><> B a s i c c r e a t e d a t + <><><> Frame c r e a t e d a t + <><><> B l o c k c r e a t e d . * (LOGOUT) + <><><> B l o c k c r e a t e d . + <><><> R e l e a s i n g b l o c k . > > Bye! (34 fun c a l l s , 14 b f 8 7 #00655140 ; r e l e a s e a c t i v e c h a i n #00655124 EVALQT ; r e a c t i v a t e FOO #00655124 FOO ; LAMBDA a r g E v a l ' e d ; c a l l LAMBDA #00655160 (LAMBDA (FRAME) — ) #0065517C ; f o r r u n n i n g LAMBDA ; c a l l COND #006551B8 COND #006551D4 ; E v a l 1 s t c l a u s e ; E v a l STACKP a r g ; STACKP a r g E v a l ' e d ; c a l l STACKP ; e x i t STACKP ; E v a l 2nd c l a u s e ; E v a l PRINT a r g ; PRINT a r g E v a l ' e d ; c a l l PRINT ; e x i t PRINT #006551D4 ; e x i t COND #006551B8 COND #0065517C ; e x i t LAMBDA #00655160 (LAMBDA (FRAME) — ) ; E v a l PRINT a r g ; PRINT a r g E v a l ' e d ; c a l l PRINT ; e x i t PRINT #00655124 ; e x i t FOO ; r e a c t i v a t e EVALQT #00655124 EVALQT ; c a l l PRINT ; e x i t PRINT #00655124 ; e x i t EVALQT ; c a l l EVALQT #00655124 EVALQT #00655140 ; f o r r u n n i n g EVALQT ; c a l l READ ; read a l i s t ; l i s t read ; e x i t READ ; c a l l LOGOUT ames, 18 frame e x t s , 60 b l o c k s ) 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051801/manifest

Comment

Related Items