forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-33.html
843 lines (694 loc) · 43.9 KB
/
book-Z-H-33.html
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
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http:https://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http:https://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta name="generator" content="HTML Tidy for Linux (vers 7 December 2008), see www.w3.org" />
<title>Structure and Interpretation of Computer Programs</title>
<link href="book-Z-C.css" title="default" rel="stylesheet" type="text/css" />
<meta name="robots" content="noindex,follow" />
</head>
<body>
<mbp:pagebreak />
<p><a name="%_sec_5.3"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_5.3">5.3 Storage
Allocation and Garbage Collection</a></h2>
<p><a name="%_idx_5828"></a><a name="%_idx_5830"></a> In
section <a href="book-Z-H-34.html#%_sec_5.4">5.4</a>, we
will show how to implement a Scheme evaluator as a register
machine. In order to simplify the discussion, we will assume that
our register machines can be equipped with a <em>list-structured
memory</em>, in which the basic operations for manipulating
list-structured data are primitive. Postulating the existence of
such a memory is a useful abstraction when one is focusing on the
mechanisms of control in a Scheme interpreter, but this does not
reflect a realistic view of the actual primitive data operations
of contemporary computers. To obtain a more complete picture of
how a Lisp system operates, we must investigate how list
structure can be represented in a way that is compatible with
conventional computer memories.</p>
<p>There are two considerations in implementing list structure.
The first is purely an issue of representation: how to represent
the ``box-and-pointer'' structure of Lisp pairs, using only the
storage and addressing capabilities of typical computer memories.
The second issue concerns the management of memory as a
computation proceeds. The operation of a Lisp system depends
crucially on the ability to continually create new data objects.
These include objects that are explicitly created by the Lisp
procedures being interpreted as well as structures created by the
interpreter itself, such as environments and argument lists.
Although the constant creation of new data objects would pose no
problem on a computer with an infinite amount of rapidly
addressable memory, computer memories are available only in
finite sizes (more's the pity). Lisp systems thus provide an
<a name="%_idx_5832"></a><em>automatic storage allocation</em>
facility to support the illusion of an infinite memory. When a
data object is no longer needed, the memory allocated to it is
automatically recycled and used to construct new data objects.
There are various techniques for providing such automatic storage
allocation. The method we shall discuss in this section is called
<em>garbage collection</em>.</p>
<p><a name="%_sec_5.3.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.3.1">5.3.1 Memory as
Vectors</a></h3>
<p>A conventional computer memory can be thought of as an array
of cubbyholes, each of which can contain a piece of information.
Each cubbyhole has a unique name, called its <a name="%_idx_5834"></a><em>address</em> or <a name="%_idx_5836"></a><em>location</em>. Typical memory systems
provide two primitive operations: one that fetches the data
stored in a specified location and one that assigns new data to a
specified location. Memory addresses can be incremented to
support sequential access to some set of the cubbyholes. More
generally, many important data operations require that memory
addresses be treated as data, which can be stored in memory
locations and manipulated in machine registers. The
representation of list structure is one application of such
<a name="%_idx_5838"></a><a name="%_idx_5840"></a><em>address
arithmetic</em>.</p>
<p>To model computer memory, we use a new kind of data structure
called a <a name="%_idx_5842"></a><em>vector</em>. Abstractly, a
vector is a compound data object whose individual elements can be
accessed by means of an integer index in an amount of time that
is independent of the index.<a href="#footnote_Temp_744" name="call_footnote_Temp_744" id="call_footnote_Temp_744"><sup><small>5</small></sup></a> In order
to describe memory operations, we use two primitive Scheme
procedures for manipulating vectors:</p>
<ul>
<li>
<tt>(vector-ref <<em>vector</em>>
<<em>n</em>>)</tt> returns the <em>n</em>th element of
the vector.
<p><a name="%_idx_5848"></a><a name="%_idx_5850"></a></p>
</li>
<li><tt>(vector-set! <<em>vector</em>> <<em>n</em>>
<<em>value</em>>)</tt> sets the <em>n</em>th element of
the vector to the designated value.</li>
</ul>
<p>For example, if <tt>v</tt> is a vector, then <tt>(vector-ref v
5)</tt> gets the fifth entry in the vector <tt>v</tt> and
<tt>(vector-set! v 5 7)</tt> changes the value of the fifth entry
of the vector <tt>v</tt> to 7.<a href="#footnote_Temp_745" name="call_footnote_Temp_745" id="call_footnote_Temp_745"><sup><small>6</small></sup></a> For
computer memory, this access can be implemented through the use
of address arithmetic to combine a <em>base address</em> that
specifies the beginning location of a vector in memory with an
<em>index</em> that specifies the offset of a particular element
of the vector.</p>
<p><a name="%_sec_Temp_746"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_746">Representing Lisp data</a></h4>
<p><a name="%_idx_5852"></a><a name="%_idx_5854"></a> We can use
vectors to implement the basic pair structures required for a
list-structured memory. Let us imagine that computer memory is
divided into two vectors: <a name="%_idx_5856"></a><tt>the-cars</tt> and <a name="%_idx_5858"></a><tt>the-cdrs</tt>. We will represent list
structure as follows: A pointer to a pair is an index into the
two vectors. The <tt>car</tt> of the pair is the entry in
<tt>the-cars</tt> with the designated index, and the <tt>cdr</tt>
of the pair is the entry in <tt>the-cdrs</tt> with the designated
index. We also need a representation for objects other than pairs
(such as numbers and symbols) and a way to distinguish one kind
of data from another. There are many methods of accomplishing
this, but they all reduce to using <a name="%_idx_5860"></a><a name="%_idx_5862"></a><em>typed
pointers</em>, that is, to extending the notion of ``pointer'' to
include information on data type.<a href="#footnote_Temp_747" name="call_footnote_Temp_747" id="call_footnote_Temp_747"><sup><small>7</small></sup></a> The data
type enables the system to distinguish a pointer to a pair (which
consists of the ``pair'' data type and an index into the memory
vectors) from pointers to other kinds of data (which consist of
some other data type and whatever is being used to represent data
of that type). Two data objects are <a name="%_idx_5868"></a>considered to be the same (<tt>eq?</tt>) if
their pointers are identical.<a href="#footnote_Temp_748" name="call_footnote_Temp_748" id="call_footnote_Temp_748"><sup><small>8</small></sup></a>
Figure <a href="#%_fig_5.14">5.14</a> illustrates the use of
this method to represent the list <tt>((1 2) 3 4)</tt>, whose
box-and-pointer diagram is also shown. We use letter prefixes to
denote the data-type information. Thus, a pointer to the pair
with index 5 is denoted <tt>p5</tt>, the empty list is denoted by
the pointer <tt>e0</tt>, and a pointer to the number 4 is denoted
<tt>n4</tt>. In the box-and-pointer diagram, we have indicated at
the lower left of each pair the vector index that specifies where
the <tt>car</tt> and <tt>cdr</tt> of the pair are stored. The
blank locations in <tt>the-cars</tt> and <tt>the-cdrs</tt> may
contain parts of other list structures (not of interest
here).</p>
<p><a name="%_fig_5.14"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.14:</b> Box-and-pointer and
memory-vector representations of the list <tt>((1 2) 3
4)</tt>.
</div>
<table width="100%">
<tr>
<td><img src="ch5-Z-G-7.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>A pointer to a number, such as <tt>n4</tt>, might consist of a
type indicating numeric data together with the actual
representation of the number 4.<a href="#footnote_Temp_749" name="call_footnote_Temp_749" id="call_footnote_Temp_749"><sup><small>9</small></sup></a> To deal
with numbers that are too large to be represented in the fixed
amount of space allocated for a single pointer, we could use a
distinct <a name="%_idx_5880"></a><em>bignum</em> data type, for
which the pointer designates a list in which the parts of the
number are stored.<a href="#footnote_Temp_750" name="call_footnote_Temp_750" id="call_footnote_Temp_750"><sup><small>10</small></sup></a></p>
<p><a name="%_idx_5882"></a>A symbol might be represented as a
typed pointer that designates a sequence of the characters that
form the symbol's printed representation. This sequence is
constructed by the Lisp reader when the character string is
initially encountered in input. Since we want two instances of a
symbol to be recognized as the ``same'' symbol by <tt>eq?</tt>
and we <a name="%_idx_5884"></a>want <tt>eq?</tt> to be a simple
test for equality of pointers, we must ensure that if the reader
sees the same character string twice, it will use the same
pointer (to the same sequence of characters) to represent both
occurrences. To accomplish this, the reader maintains a table,
traditionally called the <a name="%_idx_5886"></a><em>obarray</em>, of all the symbols it has ever
encountered. When the reader encounters a character string and is
about to construct a symbol, it checks the obarray to see if it
has ever before seen the same character string. If it has not, it
uses the characters to construct a new symbol (a typed pointer to
a new character sequence) and enters this pointer in the obarray.
If the reader has seen the string before, it returns the symbol
pointer stored in the obarray. This process of replacing
character strings by unique pointers is called <a name="%_idx_5888"></a><a name="%_idx_5890"></a><em>interning</em>
symbols.</p>
<p><a name="%_sec_Temp_751"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_751">Implementing
the primitive list operations</a></h4>
<p><a name="%_idx_5892"></a><a name="%_idx_5894"></a>Given the
above representation scheme, we can replace each ``primitive''
list operation of a register machine with one or more primitive
vector operations. We will use two registers, <tt>the-cars</tt>
and <tt>the-cdrs</tt>, to identify the memory vectors, and will
assume that <tt>vector-ref</tt> and <tt>vector-set!</tt> are
available as primitive operations. We also assume that numeric
operations on pointers (such as incrementing a pointer, using a
pair pointer to index a vector, or adding two numbers) use only
the index portion of the typed pointer.</p>
<p>For example, we can make a register machine support the
instructions</p>
<p><a name="%_idx_5896"></a><a name="%_idx_5898"></a></p>
<p>
<tt>(assign <<em>reg<sub>1</sub></em>> (op car) (reg <<em>reg<sub>2</sub></em>>))<br />
<br />
(assign <<em>reg<sub>1</sub></em>> (op cdr) (reg <<em>reg<sub>2</sub></em>>))<br />
</tt></p>
<p>if we implement these, respectively, as</p>
<p>
<tt>(assign <<em>reg<sub>1</sub></em>> (op vector-ref) (reg the-cars) (reg <<em>reg<sub>2</sub></em>>))<br />
<br />
(assign <<em>reg<sub>1</sub></em>> (op vector-ref) (reg the-cdrs) (reg <<em>reg<sub>2</sub></em>>))<br />
</tt></p>
<p>The instructions</p>
<p><a name="%_idx_5900"></a><a name="%_idx_5902"></a></p>
<p>
<tt>(perform (op set-car!) (reg <<em>reg<sub>1</sub></em>>) (reg <<em>reg<sub>2</sub></em>>))<br />
<br />
(perform (op set-cdr!) (reg <<em>reg<sub>1</sub></em>>) (reg <<em>reg<sub>2</sub></em>>))<br />
</tt></p>
<p>are implemented as</p>
<p><tt>(perform<br />
(op vector-set!) (reg the-cars) (reg <<em>reg<sub>1</sub></em>>) (reg <<em>reg<sub>2</sub></em>>))<br />
<br />
(perform<br />
(op vector-set!) (reg the-cdrs) (reg <<em>reg<sub>1</sub></em>>) (reg <<em>reg<sub>2</sub></em>>))<br />
</tt></p>
<p><a name="%_idx_5904"></a><tt>Cons</tt> is performed by
allocating an unused index and storing the arguments to
<tt>cons</tt> in <tt>the-cars</tt> and <tt>the-cdrs</tt> at that
indexed vector position. We presume that there is a special
register, <a name="%_idx_5906"></a><tt>free</tt>, that always
holds a pair pointer containing the next available index, and
that we can increment the index part of that pointer to find the
next free location.<a href="#footnote_Temp_752" name="call_footnote_Temp_752" id="call_footnote_Temp_752"><sup><small>11</small></sup></a> For
example, the instruction</p>
<p>
<tt>(assign <<em>reg<sub>1</sub></em>> (op cons) (reg <<em>reg<sub>2</sub></em>>) (reg <<em>reg<sub>3</sub></em>>))<br />
</tt></p>
<p>is implemented as the following sequence of vector
operations:<a href="#footnote_Temp_753" name="call_footnote_Temp_753" id="call_footnote_Temp_753"><sup><small>12</small></sup></a></p>
<p><tt>(perform<br />
(op vector-set!) (reg the-cars) (reg free) (reg <<em>reg<sub>2</sub></em>>))<br />
(perform<br />
(op vector-set!) (reg the-cdrs) (reg free) (reg <<em>reg<sub>3</sub></em>>))<br />
(assign <<em>reg<sub>1</sub></em>> (reg free))<br />
(assign free (op +) (reg free) (const 1))<br />
</tt></p>
<p>The <tt>eq?</tt> operation</p>
<p>
<tt>(op eq?) (reg <<em>reg<sub>1</sub></em>>) (reg <<em>reg<sub>2</sub></em>>)<br />
</tt></p>
<p>simply tests the equality of all fields in the registers, and
<a name="%_idx_5910"></a><a name="%_idx_5912"></a><a name="%_idx_5914"></a><a name="%_idx_5916"></a>predicates such as
<tt>pair?</tt>, <tt>null?</tt>, <tt>symbol?</tt>, and
<tt>number?</tt> need only check the type field.</p>
<p><a name="%_sec_Temp_754"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_754">Implementing
stacks</a></h4>
<p><a name="%_idx_5918"></a> Although our register machines use
stacks, we need do nothing special here, since stacks can be
modeled in terms of lists. The stack can be a list of the saved
values, pointed to by a special register <tt>the-stack</tt>.
Thus, <tt>(save <<em>reg</em>>)</tt> can be implemented
as</p>
<p><a name="%_idx_5920"></a></p>
<p>
<tt>(assign the-stack (op cons) (reg <<em>reg</em>>) (reg the-stack))<br />
</tt></p>
<p><a name="%_idx_5922"></a>Similarly, <tt>(restore
<<em>reg</em>>)</tt> can be implemented as</p>
<p>
<tt>(assign <<em>reg</em>> (op car) (reg the-stack))<br />
(assign the-stack (op cdr) (reg the-stack))<br />
</tt></p>
<p>and <tt>(perform (op initialize-stack))</tt> can be
implemented as</p>
<p><tt>(assign the-stack (const ()))<br /></tt></p>
<p>These operations can be further expanded in terms of the
vector operations given above. In conventional computer
architectures, however, it is usually advantageous to allocate
the stack as a separate vector. Then pushing and popping the
stack can be accomplished by incrementing or decrementing an
index into that vector.</p>
<p><a name="%_thm_5.20"></a> <b>Exercise
5.20.</b> Draw the box-and-pointer representation and
the memory-vector representation (as in figure <a href="#%_fig_5.14">5.14</a>) of the list structure produced by</p>
<p><tt>(define x (cons 1 2))<br />
(define y (list x x))<br /></tt></p>
<p>with the <tt>free</tt> pointer initially <tt>p1</tt>. What is
the final value of <tt>free</tt> ? What pointers represent the
values of <tt>x</tt> and <tt>y</tt> ?</p>
<p><a name="%_thm_5.21"></a> <b>Exercise
5.21.</b> <a name="%_idx_5924"></a>Implement register
machines for the following procedures. Assume that the
list-structure memory operations are available as machine
primitives.</p>
<p>a. Recursive <tt>count-leaves</tt>:</p>
<p><tt>(define (count-leaves tree)<br />
(cond ((null? tree) 0)<br />
((not (pair? tree)) 1)<br />
(else (+ (count-leaves (car tree))<br />
(count-leaves (cdr tree))))))<br />
</tt></p>
<p>b. Recursive <tt>count-leaves</tt> with explicit counter:</p>
<p><tt>(define (count-leaves tree)<br />
(define (count-iter tree n)<br />
(cond ((null? tree) n)<br />
((not (pair? tree)) (+ n 1))<br />
(else (count-iter (cdr tree)<br />
(count-iter (car tree) n)))))<br />
(count-iter tree 0))<br /></tt></p>
<p><a name="%_thm_5.22"></a> <b>Exercise
5.22.</b> <a name="%_idx_5926"></a><a name="%_idx_5928"></a>Exercise <a href="book-Z-H-22.html#%_thm_3.12">3.12</a> of section <a href="book-Z-H-22.html#%_sec_3.3.1">3.3.1</a> presented an
<tt>append</tt> procedure that appends two lists to form a new
list and an <tt>append!</tt> procedure that splices two lists
together. Design a register machine to implement each of these
procedures. Assume that the list-structure memory operations are
available as primitive operations.</p>
<p><a name="%_sec_5.3.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.3.2">5.3.2 Maintaining
the Illusion of Infinite Memory</a></h3>
<p><a name="%_idx_5930"></a></p>
<p>The representation method outlined in section <a href="#%_sec_5.3.1">5.3.1</a> solves the problem of implementing list
structure, provided that we have an infinite amount of memory.
With a real computer we will eventually run out of free space in
which to construct new pairs.<a href="#footnote_Temp_758" name="call_footnote_Temp_758" id="call_footnote_Temp_758"><sup><small>13</small></sup></a>
However, most of the pairs generated in a typical computation are
used only to hold intermediate results. After these results are
accessed, the pairs are no longer needed -- they are
<em>garbage</em>. For instance, the computation</p>
<p>
<tt>(accumulate + 0 (filter odd? (enumerate-interval 0 n)))<br />
</tt></p>
<p>constructs two lists: the enumeration and the result of
filtering the enumeration. When the accumulation is complete,
these lists are no longer needed, and the allocated memory can be
reclaimed. If we can arrange to collect all the garbage
periodically, and if this turns out to recycle memory at about
the same rate at which we construct new pairs, we will have
preserved the illusion that there is an infinite amount of
memory.</p>
<p>In order to recycle pairs, we must have a way to determine
which allocated pairs are not needed (in the sense that their
contents can no longer influence the future of the computation).
The method we shall examine for accomplishing this is known as
<em>garbage collection</em>. Garbage collection is based on the
observation that, at any moment in a Lisp interpretation, the
only objects that can affect the future of the computation are
those that can be reached by some succession of <tt>car</tt> and
<tt>cdr</tt> operations starting from the pointers that are
currently in the machine registers.<a href="#footnote_Temp_759" name="call_footnote_Temp_759" id="call_footnote_Temp_759"><sup><small>14</small></sup></a> Any
memory cell that is not so accessible may be recycled.</p>
<p>There are many ways to perform garbage collection. The method
we shall examine here is called <a name="%_idx_5932"></a><a name="%_idx_5934"></a><em>stop-and-copy</em>. The basic idea is to
divide memory into two halves: ``working memory'' and ``free
memory.'' When <tt>cons</tt> constructs pairs, it allocates these
in working memory. When working memory is full, we perform
garbage collection by locating all the useful pairs in working
memory and copying these into consecutive locations in free
memory. (The useful pairs are located by tracing all the
<tt>car</tt> and <tt>cdr</tt> pointers, starting with the machine
registers.) Since we do not copy the garbage, there will
presumably be additional free memory that we can use to allocate
new pairs. In addition, nothing in the working memory is needed,
since all the useful pairs in it have been copied. Thus, if we
interchange the roles of working memory and free memory, we can
continue processing; new pairs will be allocated in the new
working memory (which was the old free memory). When this is
full, we can copy the useful pairs into the new free memory
(which was the old working memory).<a href="#footnote_Temp_760" name="call_footnote_Temp_760" id="call_footnote_Temp_760"><sup><small>15</small></sup></a></p>
<p><a name="%_sec_Temp_761"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_761">Implementation
of a stop-and-copy garbage collector</a></h4>
<p>We now use our register-machine language to describe the
stop-and-copy algorithm in more detail. We will assume that there
is a register called <a name="%_idx_5966"></a><tt>root</tt> that
contains a pointer to a structure that eventually points at all
accessible data. This can be arranged by storing the contents of
all the machine registers in a pre-allocated list pointed at by
<tt>root</tt> just before starting garbage collection.<a href="#footnote_Temp_762" name="call_footnote_Temp_762" id="call_footnote_Temp_762"><sup><small>16</small></sup></a> We also
assume that, in addition to the current working memory, there is
free memory available into which we can copy the useful data. The
current working memory consists of vectors whose base addresses
are in <a name="%_idx_5968"></a><a name="%_idx_5970"></a>registers called <tt>the-cars</tt> and
<tt>the-cdrs</tt>, and the free memory is in registers called
<a name="%_idx_5972"></a><a name="%_idx_5974"></a><tt>new-cars</tt> and <tt>new-cdrs</tt>.</p>
<p>Garbage collection is triggered when we exhaust the free cells
in the current working memory, that is, when a <tt>cons</tt>
operation attempts to increment the <tt>free</tt> pointer beyond
the end of the memory vector. When the garbage-collection process
is complete, the <tt>root</tt> pointer will point into the new
memory, all objects accessible from the <tt>root</tt> will have
been moved to the new memory, and the <tt>free</tt> pointer will
indicate the next place in the new memory where a new pair can be
allocated. In addition, the roles of working memory and new
memory will have been interchanged -- new pairs will be
constructed in the new memory, beginning at the place indicated
by <tt>free</tt>, and the (previous) working memory will be
available as the new memory for the next garbage collection.
Figure <a href="#%_fig_5.15">5.15</a> shows the arrangement
of memory just before and just after garbage collection.</p>
<p><a name="%_fig_5.15"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.15:</b> Reconfiguration of memory by
the garbage-collection process.
</div>
<table width="100%">
<tr>
<td><img src="ch5-Z-G-8.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_idx_5976"></a><a name="%_idx_5978"></a>The state of
the garbage-collection process is controlled by maintaining two
pointers: <tt>free</tt> and <tt>scan</tt>. These are initialized
to point to the beginning of the new memory. The algorithm begins
by relocating the pair pointed at by <tt>root</tt> to the
beginning of the new memory. The pair is copied, the
<tt>root</tt> pointer is adjusted to point to the new location,
and the <tt>free</tt> pointer is incremented. In addition, the
old location of the pair is marked to show that its contents have
been moved. This marking is done as follows: In the <tt>car</tt>
position, we place a special tag that signals that this is an
already-moved object. (Such an object is traditionally called a
<a name="%_idx_5980"></a><em>broken heart</em>.)<a href="#footnote_Temp_763" name="call_footnote_Temp_763" id="call_footnote_Temp_763"><sup><small>17</small></sup></a> In the
<tt>cdr</tt> position we place a <a name="%_idx_5988"></a><em>forwarding address</em> that points at the
location to which the object has been moved.</p>
<p>After relocating the root, the garbage collector enters its
basic cycle. At each step in the algorithm, the <tt>scan</tt>
pointer (initially pointing at the relocated root) points at a
pair that has been moved to the new memory but whose <tt>car</tt>
and <tt>cdr</tt> pointers still refer to objects in the old
memory. These objects are each relocated, and the <tt>scan</tt>
pointer is incremented. To relocate an object (for example, the
object indicated by the <tt>car</tt> pointer of the pair we are
scanning) we check to see if the object has already been moved
(as indicated by the presence of a broken-heart tag in the
<tt>car</tt> position of the object). If the object has not
already been moved, we copy it to the place indicated by
<tt>free</tt>, update <tt>free</tt>, set up a broken heart at the
object's old location, and update the pointer to the object (in
this example, the <tt>car</tt> pointer of the pair we are
scanning) to point to the new location. If the object has already
been moved, its forwarding address (found in the <tt>cdr</tt>
position of the broken heart) is substituted for the pointer in
the pair being scanned. Eventually, all accessible objects will
have been moved and scanned, at which point the <tt>scan</tt>
pointer will overtake the <tt>free</tt> pointer and the process
will terminate.</p>
<p>We can specify the stop-and-copy algorithm as a sequence of
instructions for a register machine. The basic step of relocating
an object is accomplished by a subroutine called
<tt>relocate-old-result-in-new</tt>. This subroutine gets its
argument, a pointer to the object to be relocated, from a
register named <a name="%_idx_5990"></a><tt>old</tt>. It
relocates the designated object (incrementing <tt>free</tt> in
the process), puts a pointer to the relocated object into a
register called <a name="%_idx_5992"></a><tt>new</tt>, and
returns by branching to the entry point stored in the register
<tt>relocate-continue</tt>. To begin garbage collection, we
invoke this subroutine to relocate the <tt>root</tt> pointer,
after initializing <tt>free</tt> and <tt>scan</tt>. When the
relocation of <tt>root</tt> has been accomplished, we install the
new pointer as the new <tt>root</tt> and enter the main loop of
the garbage collector.</p>
<p><tt>begin-garbage-collection<br />
(assign free (const 0))<br />
(assign scan (const 0))<br />
(assign old (reg root))<br />
(assign relocate-continue (label reassign-root))<br />
(goto (label relocate-old-result-in-new))<br />
reassign-root<br />
(assign root (reg new))<br />
(goto (label gc-loop))<br /></tt></p>
<p>In the main loop of the garbage collector we must determine
whether there are any more objects to be scanned. We do this by
testing whether the <tt>scan</tt> pointer is coincident with the
<tt>free</tt> pointer. If the pointers are equal, then all
accessible objects have been relocated, and we branch to
<tt>gc-flip</tt>, which cleans things up so that we can continue
the interrupted computation. If there are still pairs to be
scanned, we call the relocate subroutine to relocate the
<tt>car</tt> of the next pair (by placing the <tt>car</tt>
pointer in <tt>old</tt>). The <tt>relocate-continue</tt> register
is set up so that the subroutine will return to update the
<tt>car</tt> pointer.</p>
<p><tt>gc-loop<br />
(test (op =) (reg scan) (reg free))<br />
(branch (label gc-flip))<br />
(assign old (op vector-ref) (reg new-cars) (reg scan))<br />
(assign relocate-continue (label update-car))<br />
(goto (label relocate-old-result-in-new))<br />
</tt></p>
<p>At <tt>update-car</tt>, we modify the <tt>car</tt> pointer of
the pair being scanned, then proceed to relocate the <tt>cdr</tt>
of the pair. We return to <tt>update-cdr</tt> when that
relocation has been accomplished. After relocating and updating
the <tt>cdr</tt>, we are finished scanning that pair, so we
continue with the main loop.</p>
<p><tt>update-car<br />
(perform<br />
(op vector-set!) (reg new-cars) (reg scan) (reg new))<br />
(assign old (op vector-ref) (reg new-cdrs) (reg scan))<br />
(assign relocate-continue (label update-cdr))<br />
(goto (label relocate-old-result-in-new))<br />
<br />
update-cdr<br />
(perform<br />
(op vector-set!) (reg new-cdrs) (reg scan) (reg new))<br />
(assign scan (op +) (reg scan) (const 1))<br />
(goto (label gc-loop))<br /></tt></p>
<p>The subroutine <tt>relocate-old-result-in-new</tt> relocates
objects as follows: If the object to be relocated (pointed at by
<tt>old</tt>) is not a pair, then we return the same pointer to
the object unchanged (in <tt>new</tt>). (For example, we may be
scanning a pair whose <tt>car</tt> is the number 4. If we
represent the <tt>car</tt> by <tt>n4</tt>, as described in
section <a href="#%_sec_5.3.1">5.3.1</a>, then we want the
``relocated'' <tt>car</tt> pointer to still be <tt>n4</tt>.)
Otherwise, we must perform the relocation. If the <tt>car</tt>
position of the pair to be relocated contains a broken-heart tag,
then the pair has in fact already been moved, so we retrieve the
forwarding address (from the <tt>cdr</tt> position of the broken
heart) and return this in <tt>new</tt>. If the pointer in
<tt>old</tt> points at a yet-unmoved pair, then we move the pair
to the first free cell in new memory (pointed at by
<tt>free</tt>) and set up the broken heart by storing a
broken-heart tag and forwarding address at the old location.
<tt>Relocate-old-result-in-new</tt> uses a register <a name="%_idx_5994"></a><tt>oldcr</tt> to hold the <tt>car</tt> or the
<tt>cdr</tt> of the object pointed at by <tt>old</tt>.<a href="#footnote_Temp_764" name="call_footnote_Temp_764" id="call_footnote_Temp_764"><sup><small>18</small></sup></a></p>
<p><tt>relocate-old-result-in-new<br />
(test (op pointer-to-pair?) (reg old))<br />
(branch (label pair))<br />
(assign new (reg old))<br />
(goto (reg relocate-continue))<br />
pair<br />
(assign oldcr (op vector-ref) (reg the-cars) (reg old))<br />
(test (op broken-heart?) (reg oldcr))<br />
(branch (label already-moved))<br />
(assign new (reg free)) <em>; new location for pair</em><br />
<em>;; Update <tt>free</tt> pointer.</em><br />
(assign free (op +) (reg free) (const 1))<br />
<em>;; Copy the <tt>car</tt> and <tt>cdr</tt> to new memory.</em><br />
(perform (op vector-set!)<br />
(reg new-cars) (reg new) (reg oldcr))<br />
(assign oldcr (op vector-ref) (reg the-cdrs) (reg old))<br />
(perform (op vector-set!)<br />
(reg new-cdrs) (reg new) (reg oldcr))<br />
<em>;; Construct the broken heart.</em><br />
(perform (op vector-set!)<br />
(reg the-cars) (reg old) (const broken-heart))<br />
(perform<br />
(op vector-set!) (reg the-cdrs) (reg old) (reg new))<br />
(goto (reg relocate-continue))<br />
already-moved<br />
(assign new (op vector-ref) (reg the-cdrs) (reg old))<br />
(goto (reg relocate-continue))<br /></tt></p>
<p>At the very end of the garbage-collection process, we
interchange the role of old and new memories by interchanging
pointers: interchanging <tt>the-cars</tt> with <tt>new-cars</tt>,
and <tt>the-cdrs</tt> with <tt>new-cdrs</tt>. We will then be
ready to perform another garbage collection the next time memory
runs out.</p>
<p><tt>gc-flip<br />
(assign temp (reg the-cdrs))<br />
(assign the-cdrs (reg new-cdrs))<br />
(assign new-cdrs (reg temp))<br />
(assign temp (reg the-cars))<br />
(assign the-cars (reg new-cars))<br />
(assign new-cars (reg temp))<br /></tt></p>
<div class="smallprint">
<hr />
</div>
<div class="footnote">
<p><a href="#call_footnote_Temp_744" name="footnote_Temp_744" id="footnote_Temp_744"><sup><small>5</small></sup></a> We could
represent memory as lists of items. However, the access time
would then not be independent of the index, since accessing the
<em>n</em>th element of a list requires <em>n</em> - 1
<tt>cdr</tt> operations.</p>
<p><a href="#call_footnote_Temp_745" name="footnote_Temp_745" id="footnote_Temp_745"><sup><small>6</small></sup></a> For
completeness, we should specify a <tt>make-vector</tt>
operation that constructs vectors. However, in the present
application we will use vectors only to model fixed divisions
of the computer memory.</p>
<p><a href="#call_footnote_Temp_747" name="footnote_Temp_747" id="footnote_Temp_747"><sup><small>7</small></sup></a> This is
precisely the same <a name="%_idx_5864"></a><a name="%_idx_5866"></a>``tagged data'' idea we introduced in
chapter 2 for dealing with generic operations. Here,
however, the data types are included at the primitive machine
level rather than constructed through the use of lists.</p>
<p><a href="#call_footnote_Temp_748" name="footnote_Temp_748" id="footnote_Temp_748"><sup><small>8</small></sup></a> Type
information may be encoded in a variety of ways, depending on
the details of the machine on which the Lisp system is to be
implemented. The execution efficiency of Lisp programs will be
strongly dependent on how cleverly this choice is made, but it
is difficult to formulate general design rules for good
choices. The most straightforward way to implement typed
pointers is to allocate a fixed set of bits in each pointer to
be a <a name="%_idx_5870"></a><em>type field</em> that encodes
the data type. Important questions to be addressed in designing
such a representation include the following: How many type bits
are required? How large must the vector indices be? How
efficiently can the primitive machine instructions be used to
manipulate the type fields of pointers? Machines that include
special hardware for the efficient handling of type fields are
said to have <a name="%_idx_5872"></a><em>tagged
architectures</em>.</p>
<p><a href="#call_footnote_Temp_749" name="footnote_Temp_749" id="footnote_Temp_749"><sup><small>9</small></sup></a> This
decision on the <a name="%_idx_5874"></a><a name="%_idx_5876"></a><a name="%_idx_5878"></a>representation of
numbers determines whether <tt>eq?</tt>, which tests equality
of pointers, can be used to test for equality of numbers. If
the pointer contains the number itself, then equal numbers will
have the same pointer. But if the pointer contains the index of
a location where the number is stored, equal numbers will be
guaranteed to have equal pointers only if we are careful never
to store the same number in more than one location.</p>
<p><a href="#call_footnote_Temp_750" name="footnote_Temp_750" id="footnote_Temp_750"><sup><small>10</small></sup></a> This is
just like writing a number as a sequence of digits, except that
each ``digit'' is a number between 0 and the largest number
that can be stored in a single pointer.</p>
<p><a href="#call_footnote_Temp_752" name="footnote_Temp_752" id="footnote_Temp_752"><sup><small>11</small></sup></a> There
are other ways of finding free storage. For example, we could
link together all the unused pairs into a <a name="%_idx_5908"></a><em>free list</em>. Our free locations are
consecutive (and hence can be accessed by incrementing a
pointer) because we are using a compacting garbage collector,
as we will see in section <a href="#%_sec_5.3.2">5.3.2</a>.</p>
<p><a href="#call_footnote_Temp_753" name="footnote_Temp_753" id="footnote_Temp_753"><sup><small>12</small></sup></a> This is
essentially the implementation of <tt>cons</tt> in terms of
<tt>set-car!</tt> and <tt>set-cdr!</tt>, as described in
section <a href="book-Z-H-22.html#%_sec_3.3.1">3.3.1</a>.
The operation <tt>get-new-pair</tt> used in that implementation
is realized here by the <tt>free</tt> pointer.</p>
<p><a href="#call_footnote_Temp_758" name="footnote_Temp_758" id="footnote_Temp_758"><sup><small>13</small></sup></a> This
may not be true eventually, because memories may get large
enough so that it would be impossible to run out of free memory
in the lifetime of the computer. For example, there are about
3× 10<sup>13</sup>, microseconds in a year, so if we were
to <tt>cons</tt> once per microsecond we would need about
10<sup>15</sup> cells of memory to build a machine that could
operate for 30 years without running out of memory. That much
memory seems absurdly large by today's standards, but it is not
physically impossible. On the other hand, processors are
getting faster and a future computer may have large numbers of
processors operating in parallel on a single memory, so it may
be possible to use up memory much faster than we have
postulated.</p>
<p><a href="#call_footnote_Temp_759" name="footnote_Temp_759" id="footnote_Temp_759"><sup><small>14</small></sup></a> We
assume here that the stack is represented as a list as
described in section <a href="#%_sec_5.3.1">5.3.1</a>, so
that items on the stack are accessible via the pointer in the
stack register.</p>
<p><a href="#call_footnote_Temp_760" name="footnote_Temp_760" id="footnote_Temp_760"><sup><small>15</small></sup></a> This
idea was invented and first implemented <a name="%_idx_5936"></a>by Minsky, as part of the implementation of
<a name="%_idx_5938"></a>Lisp for the PDP-1 at the <a name="%_idx_5940"></a>MIT Research Laboratory of Electronics. It was
further developed by <a name="%_idx_5942"></a><a name="%_idx_5944"></a>Fenichel and Yochelson (1969) for use in the
Lisp implementation for <a name="%_idx_5946"></a>the Multics
time-sharing system. Later, <a name="%_idx_5948"></a>Baker
(1978) developed a ``real-time'' version of the method, which
does not require the computation to stop during garbage
collection. Baker's idea was extended by <a name="%_idx_5950"></a><a name="%_idx_5952"></a><a name="%_idx_5954"></a>Hewitt, Lieberman, and Moon (see Lieberman and
Hewitt 1983) to take advantage of the fact that some structure
is more volatile and other structure is more permanent.</p>
<p>An alternative commonly used garbage-collection technique is
the <a name="%_idx_5956"></a><a name="%_idx_5958"></a><em>mark-sweep</em> method. This consists of
tracing all the structure accessible from the machine registers
and marking each pair we reach. We then scan all of memory, and
any location that is unmarked is ``swept up'' as garbage and
made available for reuse. A full <a name="%_idx_5960"></a>discussion of the mark-sweep method can be
found in Allen 1978.</p>
<p>The Minsky-Fenichel-Yochelson algorithm is the dominant
algorithm in use for large-memory systems because it examines
only the useful part of memory. This is in contrast to
mark-sweep, in which the sweep phase must check all of memory.
A second advantage of stop-and-copy is that it is a <a name="%_idx_5962"></a><a name="%_idx_5964"></a><em>compacting</em>
garbage collector. That is, at the end of the
garbage-collection phase the useful data will have been moved
to consecutive memory locations, with all garbage pairs
compressed out. This can be an extremely important performance
consideration in machines with virtual memory, in which
accesses to widely separated memory addresses may require extra
paging operations.</p>
<p><a href="#call_footnote_Temp_762" name="footnote_Temp_762" id="footnote_Temp_762"><sup><small>16</small></sup></a> This
list of registers does not include the registers used by the
storage-allocation system -- <tt>root</tt>, <tt>the-cars</tt>,
<tt>the-cdrs</tt>, and the other registers that will be
introduced in this section.</p>
<p><a href="#call_footnote_Temp_763" name="footnote_Temp_763" id="footnote_Temp_763"><sup><small>17</small></sup></a> The
term <em><a name="%_idx_5982"></a>broken heart</em> was coined
by David Cressey, who wrote a garbage collector for <a name="%_idx_5984"></a><a name="%_idx_5986"></a>MDL, a dialect of
Lisp developed at MIT during the early 1970s.</p>
<p><a href="#call_footnote_Temp_764" name="footnote_Temp_764" id="footnote_Temp_764"><sup><small>18</small></sup></a> The
garbage collector uses the low-level predicate
<tt>pointer-to-pair?</tt> instead of the list-structure
<tt>pair?</tt> operation because in a real system there might
be various things that are treated as pairs for
garbage-collection purposes. For example, in a Scheme system
that conforms to the IEEE standard a procedure object may be
implemented as a special kind of ``pair'' that doesn't satisfy
the <tt>pair?</tt> predicate. For simulation purposes,
<tt>pointer-to-pair?</tt> can be implemented as
<tt>pair?</tt>.</p>
</div>
</body>
</html>