-
Notifications
You must be signed in to change notification settings - Fork 2
/
revguts.doc
4106 lines (3222 loc) · 171 KB
/
revguts.doc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Title = "Revised Internal Design of Spice Lisp",
Author = "Skef Wholey
Scott E. Fahlman
Joseph Ginder",
Cruft = "
DRAFT
",
Number = "S026 [Revised
1
", Index = "Lisp", File = "CMUC::<Wholey.Australia>Revguts.Mss" ]
Acknowledgments
The following people have been contributors to this and earlier versions of
the design of the Spice Lisp instruction set: Guy L. Steele Jr., Gail
E. Kaiser, Walter van Roggen, Neal Feinberg, Jim Large, and Rob MacLachlan.
The original instruction set was loosely based on the MIT Lisp Machine
instruction set.
The FASL file format was designed by Guy L. Steele Jr. and Walter van Roggen,
and the appendix on this subject is their document with very few modifications.
2
1. Introduction
1.1. Scope and Purpose
NOTE: This document describes a new implementation of Spice Lisp as it is to
be implemented on the PERQ, running the Spice operating system, Accent. This
new design is undergoing rapid change, and for the present is not guaranteed to
accurately describe any past, present, or future implementation of Spice Lisp.
All questions and comments on this material should be directed to Skef Wholey
(Wholey@CMU-CS-C).
This document specifies the instruction set and virtual memory architecture
of the PERQ Spice Lisp system. This is a working document, and it will change
frequently as the system is developed and maintained. If some detail of the
system does not agree with what is specified here, it is to be considered a
bug.
Spice Lisp will be implemented on other microcodable machines, and
implementations of Common Lisp based on Spice Lisp exist for conventional
machines with fixed instructions sets. These other implementations are very
different internally and are described in other documents.
1.2. Notational Conventions
Spice Lisp objects are 32 bits long. The low-order bit of each word is
numbered 0; the high-order bit is numbered 31. If a word is broken into
smaller units, these are packed into the word from right to left. For example,
if we break a word into bytes, byte 0 would occupy bits 0-7, byte 1 would
occupy 8-15, byte 2 would occupy 16-23, and byte 3 would occupy 24-31. In
these conventions we follow the conventions of the VAX; the PDP-10 family
follows the opposite convention, packing and numbering left to right.
All Spice Lisp documentation uses decimal as the default radix; other radices
will be indicated by a subscript (as in 77 ) or by a clear statement of what
8
radix is in use.
3
2. Data Types and Object Formats
2.1. Lisp Objects
Lisp objects are 32 bits long. They come in 32 basic types, divided into
three classes: immediate data types, pointer types, and forwarding pointer
types. The storage formats are as follows:
Immediate Data Types:
31 27 26 0
------------------------------------------------------------------------
| Type Code (5) | Immediate Data (27) |
------------------------------------------------------------------------
Pointer and Forwarding Types:
31 27 26 25 24 1 0
------------------------------------------------------------------------
| Type Code (5) | Space Code (2) | Pointer (24) | Unused (1) |
------------------------------------------------------------------------
2.2. Table of Type Codes
Code Type Class Explanation
---- ---- ----- -----------
0 Misc Immediate Trap object, stacks, system tables
1 Bit-Vector Pointer Vector of bits
2 Integer-Vector Pointer Vector of integers
3 String Pointer Character string
4 Bignum Pointer Bignum
5 Long-Float Pointer Long float
6 Complex Pointer Complex number
7 Ratio Pointer Ratio
8 General-Vector Pointer Vector of Lisp objects
9 Function Pointer Compiled function header
10 Array Pointer Array header
11 Symbol Pointer Symbol
12 List Pointer Cons cell
13-15 Unused
16 + Fixnum Immediate Fixnum >= 0
17 - Fixnum Immediate Fixnum < 0
18 + Short-Float Immediate Short float >= 0
19 - Short-Float Immediate Short float < 0
20 Character Immediate Character object
21 Values-Marker Immediate Multiple values marker
22 Call-Header Immediate Control stack call frame header
23 Catch-Header Immediate Control stack catch frame header
24 Catch-All Immediate Catch-All object
25 GC-Forward Forward Object in newspace of same type
26-31 Unused
4
2.3. Table of Space Codes
Code Space Explanation
---- ----- -----------
0 Dynamic-0 Storage normally garbage collected, space 0.
1 Dynamic-1 Storage normally garbage collected, space 1.
2 Static Permanent objects, never moved or reclaimed.
3 Read-Only Objects never moved, reclaimed, or altered.
2.4. Immediate Data Type Descriptions
Misc Reserved for assorted internal values. Bits 25-26 specify a
sub-type code.
0 Trap Illegal object trap. If you fetch one of
these, it's an error except under very
specialized conditions. Note that a word of
all zeros is of this type, so this is useful
for trapping references to uninitialized
memory. This value also is used in symbols to
flag an undefined value or definition.
1 Control-Stack-Pointer
The low 25 bits are a pointer into the control
stack. This is a word pointer that points to
the proper virtual memory address. Pointers of
this form are returned by certain system
routines for use by debugging programs.
2 Binding-Stack-Pointer
The low 25 bits are a pointer into the binding
stack. This is a word pointer that points to
the proper virtual memory address. Pointers of
this form are returned by certain system
routines for use by debugging programs.
3 System-Table-Pointer
The low 25 bits are a pointer into an area of
memory used for system tables. This is a word
pointer into an area of the address space
reserved for data sent and received in Accent
messages.
Fixnum A 28-bit two's complement integer. The sign bit is stored as
part of the type code.
Short-Float As with fixnums, the sign bit is stored as part of the type
code. The format of short floating point number can be viewed
as follows:
5
31 28 27 26 19 18 0
------------------------------------------------------------
| Type code (4) | Sign (1) | Expt (8) | Mantissa (19) |
------------------------------------------------------------
The sign of the mantissa is moved to the left so that these
flonums can be compared just like fixnums. The exponent is the
binary two's complement exponent of the number, plus 128; then,
if the mantissa is negative, the bits of the exponent field are
inverted. The mantissa is a 21-bit two's complement number
with the sign moved to bit 27 and the leading significant bit
(which is always the complement of the sign bit and hence
carries no information) stripped off. The short flonum
representing 0.0 has 0's in bits 0 - 27. It is illegal for the
sign bit to be 1 with all the other bits equal to 0. This
-38 +38
encoding gives a range of about 10 to 10 and about 6
digits of accuracy. Note that long-flonums are available for
those wanting more accuracy, but they are less efficient to use
because they generate garbage that must be collected later.
Character A character object holding a character code, control bits, and
font in the following format:
31 27 26 24 23 16 15 8 7 0
---------------------------------------------------------------
| Type code (5) | Unused (3) | Font (8) | Bits (8) | Code (8) |
---------------------------------------------------------------
Values-Marker Used to mark the presence of multiple values on the stack. The
low 16 bits indicate how many values are being returned. Note
then, that only 65535 values can be returned from a
multiple-values producing form. These are pushed in order,
then the Values-Marker is pushed.
Call-Header Marks the start of each call frame on the control stack. The
low-order 27 bits are used as a place to stash information for
certain special kinds of calls.
For a normal function call, as created by the CALL or CALL-0
instruction, the low 27 bits are always 0.
Bit 22, if 1, indicates an ``escape to macro'' call frame,
created when a macro-instruction cannot be completed entirely
within the microcode. In this case, bits 16-17 indicate where
the result is supposed to go (see section 6.3).
Bit 21, if 1, indicates a call frame that will accept multiple
values to be returned. Such frames are created by
Call-Multiple, and cause Return to take certain special
actions. See section 6.1.3 for details.
6
Bits 22 and 21 are mutually exclusive. It is undefined what
happens when both of these are on at once.
Catch-Header Marks a catch frame on the control stack. If bit 21 is on,
this indicates that the catching form will accept multiple
values. See section 6.2 for details.
Catch-All Object used as the catch tag for unwind-protects. Special
things happen when a catch frame with this as its tag is
encountered during a throw. See section 6.2 for details.
2.5. Pointer-Type Objects and Spaces
Each of the pointer-type lisp objects points into a different space in
virtual memory. There are separate spaces for Bit-Vectors, Symbols, Lists, and
so on. The 5-bit type-code provides the high-order virtual address bits for
the object, followed by the 2-bit space code, followed by the 25-bit pointer
address. This gives a 31-bit virtual address to a 32-bit word; since the PERQ
is a word-addressed machine, the low-order bit will be 0, and under Accent, the
high order bit will be 0 (because the operating system lives in the upper half
of the address space). This leaves us with a 30-bit virtual address. In
effect we have carved a 30-bit space into a fixed set of 24-bit subspaces, not
all of which are used.
The space code divides each of the type spaces into four sub-spaces, as shown
in the table above. At any given time, one of the dynamic spaces is considered
newspace, while the other is oldspace. The garbage collector continuously
moves accessible objects from oldspace into newspace. When oldspace contains
no more accessible objects it is considered empty. A ``flip'' can then be
done, turning the old newspace into the new oldspace. All type-spaces are
flipped at once. Allocation of new dynamic objects always occurs in newspace.
Optionally, the user (or system functions) may allocate objects in static or
read-only space. Such objects are never reclaimed once they are allocated --
they occupy the space in which they were initially allocated for the lifetime
of the Lisp process. The advantage of static allocation is that the GC never
has to move these objects, thereby saving a significant amount of work,
especially if the objects are large. Objects in read-only space are static, in
that they are never moved or reclaimed; in addition, they cannot be altered
once they are set up. Pointers in read-only space may only point to read-only
or static space, never to dynamic space. This saves even more work, since
read-only space does not need to be scavenged, and pages of read-only material
do not need to be written back onto the disk during paging.
Objects in a particular type-space will contain either pointers to
garbage-collectable objects or words of raw non-garbage-collectable bits, but
not both. Similarly, a space will contain either fixed-length objects or
variable-length objects, but not both. A variable-length object always
contains a 24-bit length field right-justified in the first word, with the
fixnum type-code in the high-order four bits. The remaining four bits can be
used for sub-type information. The length field gives the size of the object
in 32-bit words, including the header word. The garbage collector needs this
information when the object is moved, and it is also useful for bounds
7
checking.
The format of objects in each space are as follows:
Symbol Each symbol is represented as a fixed-length block of boxed
Lisp cells. The number of cells per symbol is 5, in the
following order:
0 Value cell for shallow binding.
1 Definition cell: a function or list.
2 Property list: a list of attribute-value pairs.
3 Print name: a string.
4 Package: the obarray holding this symbol.
List A fixed-length block of two boxed Lisp cells, the CAR and the
CDR.
General-Vector Vector of lisp objects, any length. The first word is a fixnum
giving the number of words allocated for the vector (up to 24
bits). The highest legal index is this number minus 2. The
second word is vector entry 0, and additional entries are
allocated contiguously in virtual memory. General vectors are
sometimes called G-Vectors. (See section 2.8 for further
details.)
Integer-Vector Vector of integers, any length. The 24 low bits of the first
word give the allocated length in 32-bit words. The low-order
28 bits of the second word gives the length of the vector in
entries, whatever the length of the individual entries may be.
The high-order 4 bits of the second word contain access-type
information that yields, among other things, the number of bits
per entry. Entry 0 is right-justified in the third word of the
vector. Bits per entry will normally be powers of 2, so they
will fit neatly into 32-bit words, but if necessary some empty
space may be left at the high-order end of each word. Integer
vectors are sometimes called I-Vectors. (See section 2.8 for
details.)
Bit-Vector Vector of bits, any length. Bit-Vectors are represented in a
form identical to I-Vectors, but live in a different space for
efficiency reasons.
Bignum Bignums are infinite-precision integers, represented in a
format identical to I-Vectors. Each bignum is stored as a
series of 8-bit bytes, with the low-order byte stored first.
The representation is two's complement, but the sign of the
number is redundantly encoded in the subtype field of the
bignum: positive bignums are sub-type 0, negative bignums
sub-type 1. The access-type code is always 8-Bit.
Long-Float Long floats are stored as two consecutive words of bits, in the
following format:
8
31 30 20 19 0
---------------------------------------------------------------
| Sign (1) | Exponent (11) | Fraction (20) |
---------------------------------------------------------------
| Fraction (32) |
---------------------------------------------------------------
The exponent is biased by 1023. Exponents of 0 and 2047 are
reserved. The most significant bit of the fraction is stripped
off since it is always the complement of the sign bit, and
carries no information.
Ratio Ratios are stored as two consecutive words of Lisp objects,
which should both be integers.
Complex Complex numbers are stored as two consecutive words of Lisp
objects, which should both be numbers.
Array This is actually a header which holds the accessing information
and other information about the array. The actual array
contents are held in a vector (either an I-Vector or G-Vector)
pointed to by an entry in the header. The header is identical
in format to a G-Vector. For details on what the array header
contains, see section 2.8.3.
String A vector of bytes. Identical in form to I-Vectors with the
access type always 8-Bit. However, instead of accepting and
returning fixnums, string accesses accept and return character
objects. Only the 8-bit code field is actually stored, and the
returned character object always has bit and font values of 0.
Function A compiled Spice Lisp function consists of both lisp objects
and raw bits for the code. The Lisp objects are stored in the
Function space in a format identical to that used for general
vectors, with a 24-bit length field in the first word. This
object contains assorted parameters needed by the calling
machinery, a pointer to an 8-bit I-Vector containing the
compiled byte codes, a number of pointers to symbols used as
special variables within the function, and a number of lisp
objects used as constants by the function. For details of the
code format and definitions of the byte codes, see section 5.1.
2.6. Forwarding Pointers
GC-Forward When a data structure is transported into newspace, a
GC-Forward pointer is left behind in the first word of the
oldspace object. This points to the same type-space in which
it is found. For example, a GC-Forward in G-Vector space
points to a structure in the G-Vector newspace. GC-Forward
pointers are only found in oldspace.
9
2.7. System and Stack Spaces
The virtual addresses below 08000000 are not occupied by Lisp objects,
16
since Lisp objects with type code 0 are immediate objects. Some of this space
is used for other purposes by Lisp. The current allocations are as follows:
Address (base 16) Use
------------------- ---
00000000 - 01FFFFFF Microcode tables
02000000 - 03FFFFFF Control Stack
04000000 - 05FFFFFF Binding Stack
06000000 - 07FFFFFF System tables
Microcode tables for a given process are never accessed by Lisp-level code
from that process (the SAVE function looks at the allocation table of another
Lisp process). These tables contain allocation information for the various
spaces and pointers to functions that are called when escapes to macrocode are
done. There are currently two microcode tables:
Address (base 16) Use
------------------- ---
00010000 - 00010100 Allocation table
00020000 - 00020100 Escape function table
The format of the allocation table is described in chapter 4, and the format of
the escape function table is described in section 6.3.
The control stack grows upward (toward higher addresses) in memory, and is a
framed stack. It contains only general Lisp objects (with some random things
encoded as fixnums or Misc codes). Every object pointed to by an entry on this
stack is kept alive. The frame for a function call contains an area for the
function's arguments, an area for local variables, a pointer to the caller's
frame, and a pointer into the binding stack. The frame for a Catch form
contains similar information. The precise stack format can be found in chapter
3.
The special binding stack also grows upward. This stack is used to hold
previous values of special variables that have been bound. It grows and
shrinks with the depth of the binding environment, as reflected in the control
stack. This stack contains symbol-value pairs, with only boxed Lisp objects
present.
System table space is used to interface Lisp to the operating system. This
is the only part of the address space that contains invalid memory, so all
Accent messages received will appear in this space. Since files are sent and
received in messages, all files will be mapped into this space. Data in system
table space may be accessed and altered by the instructions described in
section 5.2.11.
There are significant performance advantages to be gained by aligning all
objects on the PERQ's ``quad-word'' (64-bit) boundaries. This happens
automatically for conses, long-floats, complex numbers, and ratios, which are
10
all two Lisp-words long. For all other pointer-type objects, the allocator
makes sure that the object starts on a quad-word boundary, wasting a word with
a Misc-Trap code if necessary. Thus, every pointer (except possibly for stack
and system area pointers) will have its two low-order bits 0. User-level code
should never have to notice this distinction.
2.8. Vectors and Arrays
Common Lisp arrays can be represented in a few different ways in Spice Lisp
-- different representations have different performance advantages. Simple
general vectors, simple vectors of integers, and simple strings are basic Spice
Lisp data types, and access to these structures is quicker than access to
non-simple (or ``complex'') arrays. However, all multi-dimensional arrays in
Spice Lisp are complex arrays, so references to these is always through a
header structure.
2.8.1. General Vectors
G-Vectors contain Lisp objects. The format is as follows:
------------------------------------------------------------------
| Fixnum code (4) | Subtype (4) | Allocated length (24) |
------------------------------------------------------------------
| Vector entry 0 (Additional entries in subsequent words) |
------------------------------------------------------------------
Note that the subtype field overlaps the type field -- this means that the
subtype can change the sign bit of the fixnum. The first word of the vector is
a header indicating its length; the remaining words hold the boxed entries of
the vector, one entry per 32-bit word. The header word is of type fixnum. It
contains a 3-bit subtype field, which is used to indicate several special types
of general vectors. At present, the following subtype codes are defined:
0 Normal. Used for assorted things.
1 Named structure created by DEFSTRUCT, with type name in entry
0.
2 EQ Hash Table, last rehashed in dynamic-0 space.
3 EQ Hash Table, last rehashed in dynamic-1 space.
4 EQ Hash Table, must be rehashed.
Following the subtype is a 24-bit field indicating how many 32-bit words are
allocated for this vector, including the header word. Legal indices into the
vector range from zero to the number in the allocated length field minus 2,
inclusive. The index is checked on every access to the vector. Entry 0 is
stored in the second word of the vector, and subsequent entries follow
contiguously in virtual memory.
Once a vector has been allocated, it is possible to reduce its length by
11
using the Shrink-Vector instruction, but never to increase its length, even
back to the original size, since the space freed by the reduction may have been
reclaimed. This reduction simply stores a new smaller value in the length
field of the header word.
It is not an error to create a vector of length 0, though it will always be
an out-of-bounds error to access such an object. The maximum possible length
24
for a general vector is 2 -2 entries, and that is only possible if no other
general vectors are present in the space.
Objects of type Function and Array are identical in format to general
vectors, though they have their own spaces. In both cases, only 0 is currently
used in the sub-type field of the header word.
2.8.2. Integer Vectors
I-Vectors contain unboxed items of data, and their format is more complex.
The data items come in a variety of lengths, but are of constant length within
a given vector. Data going to and from an I-Vector are passed as Fixnums,
right justified. Internally these integers are stored in packed form, filling
32-bit words without any type-codes or other overhead. The format is as
follows:
----------------------------------------------------------------
| Fixnum code (4) | Subtype (4) | Allocated length (24) |
----------------------------------------------------------------
| Access type (4) | Number of entries (28) |
----------------------------------------------------------------
| Entry 0 right justified |
----------------------------------------------------------------
Note that the subtype field overlaps the type field -- this means that the
subtype can change the sign bit of the fixnum. The first word of an I-Vector
contains the Fixnum type-code in the top 4 bits, a 4-bit subtype code in the
next four bits, and the total allocated length of the vector (in 32-bit words)
in the low-order 24 bits. At present, the following subtype codes are defined:
0 Normal. Used for assorted things.
1 Code. This is the code-vector for a function object.
The second word of the vector is the one that is looked at every time the
vector is accessed. The low-order 28 bits of this word contain the number of
valid entries in the vector, regardless of how long each entry is. The lowest
legal index into the vector is always 0; the highest legal index is one less
than this number-of-entries field from the second word. These bounds are
checked on every access. Once a vector is allocated, it can be reduced in size
but not increased. The Shrink-Vector instruction changes both the allocated
length field and the number-of-entries field of an integer vector.
12
The high-order 4 bits of the second word contain an access-type code which
indicates how many bits are occupied by each item (and therefore how many items
are packed into a 32-bit word). The encoding is as follows:
0 1-Bit 8 Unused
1 2-Bit 9 Unused
2 4-Bit 10 Unused
3 8-Bit 11 Unused
4 16-Bit 12 Unused
5 Unused 13 Unused
6 Unused 14 Unused
7 Unused 15 Unused
In I-Vectors, the data items are packed into the third and subsequent words
of the vector. Item 0 is right justified in the third word, item 1 is to its
left, and so on until the allocated number of items has been accommodated. All
of the currently-defined access types happen to pack neatly into 32-bit words,
but if this should not be the case, some unused bits would remain at the left
side of each word. No attempt will be made to split items between words to use
up these odd bits. When allocated, an I-Vector is initialized to all 0's.
As with G-Vectors, it is not an error to create an I-Vector of length 0, but
it will always be an error to access such a vector. The maximum possible
28 24
length of an I-Vector is 2 -1 entries or 2 -3 words, whichever is smaller.
Objects of type String are identical in format to I-Vectors, though they have
their own space. Strings always have subtype 0 and access-type 3 (8-Bit).
Strings differ from normal I-Vectors in that the accessing instructions accept
and return objects of type Character rather than Fixnum.
Bignums are also identical in format and operation to I-Vectors, though they
may also be operated on directly by microcoded routines. For details of the
currently-defined sub-types and their access-codes, see section 2.5.
2.8.3. Arrays
An array header is identical in form to a G-Vector. Like any G-Vector, its
first word contains a fixnum type-code, a 4-bit subtype code, and a 24-bit
total length field (this is the length of the array header, not of the vector
that holds the data). At present, the subtype code is always 0. The entries
in the header-vector are interpreted as follows:
0 Data Vector This is a pointer to the I-Vector, G-Vector, or string that
contains the actual data of the array. In a multi-dimensional
array, the supplied indices are converted into a single 1-D
index which is used to access the data vector in the usual way.
1 Number of Elements
This is a fixnum indicating the number of elements for which
there is space in the data vector.
13
2 Fill Pointer This is a fixnum indicating how many elements of the data
vector are actually considered to be in use. Normally this is
initialized to the same value as the Number of Elements field,
but in some array applications it will be given a smaller
value. Any access beyond the fill pointer is illegal.
3 Displacement This fixnum value is added to the final code-vector index after
the index arithmetic is done but before the access occurs.
Used for mapping a portion of one array into another. For most
arrays, this is 0.
4 Range of First Index
This is the number of index values along the first dimension,
or one greater than the largest legal value of this index
(since the arrays are always zero-based). A fixnum in the
24
range 0 to 2 -1. If any of the indices has a range of 0, the
array is legal but will contain no data and accesses to it will
always be out of range. In a 0-dimension array, this entry
will not be present.
5 - N Ranges of Subsequent Dimensions
The number of dimensions of an array can be determined by looking at the
length of the array header. The rank will be this number minus 6. The maximum
array rank is 65535 - 6, or 65529.
The ranges of all indices are checked on every access, during the conversion
to a single data-vector index. In this conversion, each index is added to the
accumulating total, then the total is multiplied by the range of the following
dimension, the next index is added in, and so on. In other words, if the data
vector is scanned linearly, the last array index is the one that varies most
rapidly, then the index before it, and so on.
2.9. Symbols Known to the Microcode
A large number of symbols will be pre-defined when a Spice Lisp system is
fired up. A few of these are so fundamental to the operation of the system
that their addresses have to be assembled into the microcode. These symbols
are listed here. All of these symbols are in static space, so they will not be
moving around.
NIL 5C000000 The value of NIL is always NIL; it is an error to
16
alter it. NIL is unique among symbols in that you can take its
CAR and CDR, yielding NIL in either case.
T 5C00000C The value of T is always T; it is an error to alter
16
it.
%SP-Internal-Apply
5C000018 The function stored in the definition cell of this
16
14
symbol is called by the microcode whenever compiled code calls
an interpreted function. See section 6.1.2 for details.
%SP-Internal-Error
5C000024 The function stored in the definition cell of this
16
symbol is called whenever an error is detected during the
execution of a byte instruction. See section 6.4 for details.
%SP-Software-Interrupt-Handler
5C000030 The function stored in the definition cell of this
16
symbol is called whenever a software interrupt occurs. See
section 6.6 for details.
%SP-Internal-Throw-Tag
5C00003C This symbol is bound to the tag being thrown when a
16
Catch-All frame is encountered on the stack. See section 6.2
for details.
15
3. Runtime Environment
3.1. Control Registers
To describe the instructions in chapter 5 and the complicated control
conventions in chapter 6 requires that we talk about a number of ``machine
registers.'' All of these registers will be treated as if they contain 32-bit
Lisp objects.
Control-Stack-Pointer
The stack pointer for the control stack, an object of type
Misc-Control-Stack-Pointer. Points to the first unused word in
Control-Stack space; this upward growing stack uses a
write-increment/decrement-read discipline.
TOS The top entry of the control stack, which is kept in a register
for efficiency. References to local variables are faster if
they can assume that the local in question is on the stack in
main memory and that it has not popped up into the TOS
register. To ensure this, the compiler adds an extra local
variable to each function, so that none of the locals that are
actually used can ever pop into TOS.
Binding-Stack-Pointer
The stack pointer for the special variable binding stack, an
object of type Misc-Binding-Stack-Pointer. The binding stack
follows the same write-increment/decrement-read discipline as
the control stack.
Active-Frame An object of type Misc-Control-Stack-Pointer which points to
the first word of the call frame for the currently executing
function. The virtual address of the start of the arguments
and locals area of the active frame is this pointer plus a
constant (see section 3.3).
Open-Frame An object of type Misc-Control-Stack-Pointer which points to
the first word of the call frame currently being built (i.e.
whose arguments are being evaluated).
Active-Catch An object of type Misc-Control-Stack-Pointer which points to
the first word of the most recent catch frame built.
Active-Function The compiled function object for the function that is currently
being executed. The virtual address of the start of the
symbols and constants area of the current function is this
pointer plus a constant (see section 3.2).
Active-Code The I-Vector of instructions for the currently executing
function.
PC A pointer into I-Vector space that indicates the next quadword
from which the instruction buffer will be filled. This and the
hardware BPC determine the next instruction to be executed.
16
When a PC is pushed on the stack by a Call or Catch
instruction, it is stored in the form of a 16-bit offset from
the base of the Active-Code vector and the BPC:
31 27 26 20 19 16 15 0
---------------------------------------------------------------
| Trap type code (5) | Unused (7) | BPC (4) | Offset (16) |
---------------------------------------------------------------
3.2. Function Object Format
Each compiled function is represented in the machine as a Function Object.
This is identical in form to a G-Vector of lisp objects, and is treated as such
by the garbage collector, but it exists in a special function space. (There is
no particular reason for this distinction. We may decide later to store these
things in G-Vector space, if we become short on spaces or have some reason to
believe that this would improve paging behavior.) Usually, the function
objects and code vectors will be kept in read-only space, but nothing should
depend on this; some applications may create, compile, and destroy functions
often enough to make dynamic allocation of function objects worthwhile.
The function object contains a vector of header information needed by the
function-calling mechanism: a pointer to the I-Vector that holds the actual
code. Following this is the so-called ``symbols and constants'' area. The
first few entries in this area are fixnums that give the offsets into the code
vector for various numbers of supplied arguments. Following this begin the
true symbols and constants used by the function. Any symbol used by the code
as a special variable or the name of another function will appear here. Fixnum
constants in the range of -256 to +255 can be generated within the byte code,
and so do not need to be stored in the constants area as full-word constants.
After the one-word G-Vector header, the entries of the function object are as
follows:
0 A fixnum with bit fields as follows:
0 - 14: Number of symbols/constants in this fn object (0 to 32K-1).
This number includes the optional-arg offsets.
15 - 26: Not used.
27: 0 => All args evaled. 1 => This is a FEXPR.
1 Pointer to the unboxed Code vector holding the macro-instructions.
2 A fixnum with bit fields as follows:
0 - 7: The minimum legal number of args (0 to 255).
8 - 15: The maximum number of args, not counting &rest (0 to 255).
16 - 26: Number of local variables allocated on stack (0 to 2047).
27: 0 => No &rest arg. 1 => One &rest arg.
3 Name of this function (a symbol).
4 Vector of argument names, in order, for debugging use.
5 The symbols and constants area starts here.
This word is entry 0 of the symbol/constant area.
The first few entries in this area are fixnums representing
the code-vector entry points for various numbers of
optional arguments. See section 6.1.2.
17
3.3. Control-Stack Format
The Spice Lisp control stack is a framed stack. Call frames, which hold
information for function calls, are intermixed with catch frames, which hold
information used for non-local exits. In addition, the control stack is used
as a scratchpad for random computations.
3.3.1. Call Frames
At any given time, the machine contains pointers to the current top of the
control stack, the start of the current active frame (in which the current
function is executing), and the start of the most recent open frame. In
addition, there is a pointer to the current top of the special binding stack.
An open frame is one which has been partially built, but which is still having
arguments for it computed. When all the arguments have been computed and saved
on the frame, the function is then started. This means that the call frame is
completed, becomes the current active frame, and the function is executed. At
this time, special variables may be bound and the old values are saved on the
binding stack. Upon return, the active frame is popped away and the result is
either sent as an argument to some previously opened frame or goes to some
other destination. The binding stack is popped and old values are restored.
The active frame contains pointers to the previously-active frame, to the
most recent open frame, and to the point to which the binding stack will be
popped on exit, among other things. Following this is a vector of storage
locations for the function's arguments and local variables. Space is allocated
for the maximum number of arguments that the function can take, regardless of
how many are actually supplied.
In an open frame, the structure is built up to the point where the arguments
are stored. Thus, as arguments are computed, they can simply be pushed on the
stack. When the function is finally started, the remainder of the frame is
built. A call frame looks like this:
0 Header word. Type Call-Frame-Header.
1 Function object or EXPR for this call.
2 Pointer to previous active frame. Type Misc-Control-Stack-Ptr.
3 Pointer to previous open frame. Type Misc-Control-Stack-Ptr.
4 Pointer to previous binding stack. Type Misc-Binding-Stack-Ptr.
5 Saved PC of caller. A fixnum.
6 Args-and-locals area starts here. This is entry 0.
The first slot is pointed to by the Active-Frame register if this frame is
currently active, and by the Open-Frame register if this frame is the currently
opened frame.
3.3.2. Catch Frames
Catch frames contain much of the same information that call frames do, and
have a very similar format. A catch frame holds the function object for the
current function, a stack pointer to the current active and open frames, a
18
pointer to the current top of the binding stack, and a pointer to the previous
catch frame. When a Throw occurs, an operation equivalent to returning from
this catch frame (as if it were a call frame) is performed, and the stacks are
unwound to the proper place for continued execution in the current function. A
catch frame looks like this:
0 Header word. Type Catch-Frame-Header.
1 Function object for this call.
2 Pointer to current active frame.
3 Pointer to current open frame.
4 Pointer to current binding stack.
5 Destination PC for a Throw.
6 Tag caught by this catch frame.
7 Pointer to previous catch frame.
The conventions used to manipulate call and catch frames are described in
chapter 6.
3.4. Binding-Stack Format
Each entry of the binding-stack consists of two boxed (32-bit) words. Pushed
first is a pointer to the symbol being bound. Pushed second is the symbol's
old value (any boxed item) that is to be restored when the binding is popped.
19
4. Storage Management
New objects are allocated from the lowest unused addresses within the
specified space. Each allocation call specifies how many words are wanted, and
a Free-Storage pointer is incremented by that amount. There is one of these
Free-Storage pointers for each space, and it points to the lowest free address
in the space. There is also a Clean-Space pointer associated with each space
that is used during garbage collection. These pointers are stored in a table
in the microcode table area which is indexed by type and space code. The
address of the Free-Storage pointer for a given space is
(+ alloc-table-base (lsh type 4) (lsh space 2)).
The address of the Clean-Space pointer is
(+ alloc-table-base (lsh type 4) (lsh space 2) 2).
PERQ Spice Lisp uses a stop-and-copy garbage collector to reclaim storage.
The Collect-Garbage instruction performs a full GC. The algorithm used is a
degenerate form of Baker's incremental garbage collection scheme. When the
Collect-Garbage instruction is executed, the following happens:
1. The current newspace becomes oldspace, and the current oldspace
becomes newspace.
2. The newspace Free-Storage and Clean-Space pointers are initialized
to point to the beginning of their spaces.
3. The contents of the ``registers inside the barrier'' are
transported. There are only three such registers: Active-Function,
Active-Code, and TOS. However, the PC is stored internally as an
absolute address, so it must be recomputed if the code vector in
Active-Code is transported. This is easily done by subtracting
Active-Code from PC before it is transported, and adding it back in
afterwards. Because the Active-Code vector will be transported from
a quadword boundary to a quadword boundary, the PERQ's internal BPC
needn't be modified.
4. The control stack and binding stack are scavenged.
5. Each static pointer space is scavenged.
6. Each new dynamic space is scavenged. The scavenging of the dynamic
spaces is done until an entire pass through all of them does not
result in anything being transported. At this point, every live
object is in newspace.
A Lisp-level GC function must return the oldspace pages to Accent.
4.1. The Transporter
The transporter moves objects from oldspace to newspace. It is given an
address A, which contains the object to be transported, B. If B is an
immediate object, a pointer into static space, a pointer into read-only space,
20
or a pointer into newspace, the transporter does nothing.
If B is a pointer into oldspace, the object it points to must be moved. It
may, however, already have been moved. Fetch the first word of B, and call it
C. If C is a GC-forwarding pointer, we form a new pointer with the type code
of B and the low 27 bits of C. Write this into A.
If C is not a GC-forwarding pointer, we must copy the object the B points to.
Allocate a new object of the same size in newspace, and copy the contents.
Replace C with a GC-forwarding pointer to the new structure, and write the
address of the new structure back into A.
Hash tables maintained with an EQ relation need special treatment by the
transporter. Whenever a G-Vector with subtype 2 or 3 is transported to
newspace, its subtype code is changed to 4. The Lisp-level hash-table
functions will see that the subtype code has changed, and re-hash the entries
before any access is made.
4.2. The Scavenger
The scavenger looks through an area of pointers for pointers into oldspace,
transporting the objects they point to into newspace. The stacks and static
spaces need to be scavenged once, but the new dynamic spaces need to be
scavenged repeatedly, since new objects will be allocated while garbage
collection is in progress. To keep track of how much a dynamic space has been
scavenged, a Clean-Space pointer is maintained. The Clean-Space pointer points
to the next word to be scavenged. Each call to the scavenger scavenges the
area between the Clean-Space pointer and the Free-Storage pointer. The
Clean-Space pointer is then set to the Free-Storage pointer. When all
Clean-Space pointers are equal to their Free-Storage pointers, GC is complete.
To maintain (and create) locality of list structures, list space is treated
specially. Two separate Clean-Space pointers are maintained for list space:
one for cars and one for cdrs. The scavenger works on the Clean-Cdr pointer
unless it is at the Free-Storage pointer, in which case it works on the
Clean-Car pointer. When Clean-Car, Clean-Cdr, and the Free-Storage pointer for
list space coincide, list space has been completely scavenged.
4.3. Purification
Garbage is created when the files that make up a Spice Lisp system are
loaded. Many functions are needed only for initialization and bootstrapping
(e.g. the ``one-shot'' functions produced by the compiled for random forms