Walt Disney Imagineering 1401 Flower Street P.O. Box 25020 Glendale, CA 91221 dani@wdi.disney.com
Other noteworthy aspects of Squeak include: a compact object format that typically requires only a single word of overhead per object; a simple yet efficient incremental garbage collector for 32-bit direct pointers; efficient bulk-mutation of objects; extensions of BitBlt to handle color of any depth and anti-aliased image rotation and scaling; and real-time sound and music synthesis written entirely in Smalltalk.
It includes platform-independent support for color, sound, and image processing. Originally developed on the Macintosh, members of its user community have since ported it to numerous platforms including Windows 95 and NT, Windows CE, all common flavors of UNIX, and the Acorn.
Squeak stands alone as a practical Smalltalk in which a researcher, professor, or motivated student can examine source code for every part of the system, including graphics primitives and the virtual machine itself, and make changes immediately and without needing to see or deal with any language other than Smalltalk. It also runs bit-identical images across its wide portability base. Three strands weave through this paper:
While Smalltalk met the technical desiderata, none of the available implementations gave us the kind of control we wanted over graphics, sound, and the Smalltalk engine itself, nor the freedom to port and distribute the resulting work, including its host environment, freely over the Internet. Moreover, we felt that we were not alone, that many others in the research community shared our desire for an open, portable, malleable, and yet practical object-oriented programming environment. It became clear that the best way to get what we all wanted was to build a new Smalltalk with these goals and to share it with this wider community.
We determined that implementation in C would be key to portability but none of us wanted to write in C. However, two of us had once adapted the Smalltalk formatter (pretty-printer) to convert a body of code to BCPL. Based on that experience, we determined to write and debug the virtual machine in Smalltalk. Then, in parallel, we would write (also in Smalltalk) a translator from Smalltalk to C, and thus let Smalltalk build its own production interpreter. Out of this decision grew the following plan for building a new Smalltalk system in the shortest possible time:
Produce a new image:
It was easy to stay motivated, because the virtual machine, running inside Apple Smalltalk, was actually simulating the byte codes of the transformed image just five weeks into the project. A week later, we could type "3 + 4" on the screen, compile it, and print the result, and the week after that the entire user interface was working, albeit in slow motion. We were writing the C translator in parallel on a commercial Smalltalk, and by the eighth week, the first translated interpreter displayed a window on the screen. Ten weeks into the project, we "crossed the bridge" and were able to use Squeak to evolve itself, no longer needing to port images forward from Apple Smalltalk. About six weeks later, Squeak's performance had improved to the point that it could simulate its own interpreter and run the C translator, and Squeak became entirely self-supporting.
We attribute the speed with which this initial work was accomplished to the Squeak philosophy: do everything in Smalltalk so that each improvement makes everything smaller, faster, and better. It has been a pleasant revelation to work on such low-level system facilities as real-time garbage collection and FM music synthesis from within the comfort and convenience of the Smalltalk-80 language and environment.
Once we had a stable, usable interpreter, the focus shifted from creation to evolution. Performance improved steadily and support for color, image transforms, sound synthesis, and networking were added. These improvements were made incrementally, as the need arose, and in parallel with other projects that relied on the stability of the virtual machine. Yet despite the apparent risk of frequent changes to the VM, Squeak has proven as dependable as most commercial Smalltalks we have used. We attribute this success partly to our passion for design simplicity but mostly to the strategy of implementing the virtual machine in Smalltalk.
The remainder of the paper discusses various aspects of the Squeak implementation, its memory footprint and performance, the evolution of its user community, and plans for its future.
The interpreter is structured as a single class that gets translated to C along with the Object Memory and BitBlt classes. In addition, a subclass (Interpreter Simulator) runs all the same code from within a Smalltalk environment by supporting basic mouse, file, and display operations. This subclass was the basis for debugging the Squeak system into existence. All of this code is included in the Squeak release and it can run its own image, albeit at a snail's pace (every memory access, even in BitBlt, runs a Smalltalk method). Having an interpreter that runs within Smalltalk is invaluable for studying the virtual machine. Any operation can be stopped and inspected, or it can be instrumented to gather timing profiles, exact method counts, and other statistics.
Although we have constantly amended the interpreter to achieve increasing performance, we have stayed pretty close to the Blue Book message interface between the Interpreter and the Object Memory. It is a testament to the original design of that interface that completely changing the Object Memory implementation had almost no impact on the Interpreter.
offset | contents | occurrence |
---|---|---|
-8 | size in words (30 bits), header type (2 bits) | 1% |
-4 | full class pointer (30 bits), header type (2 bits) | 18% |
0 | base header, as follows...
storage management (3 bits) object hash (12 bits) compact class index (5 bits) object format field (4 bits, see below) size in words (6 bits) header type (2 bits) |
100% |
0 | no fields |
1 | fixed pointer fields |
2 | indexable pointer fields |
3 | both fixed and indexable pointer fields |
4 | unused |
5 | unused |
6 | indexable word fields (no pointers) |
7 | unused |
8-11 | indexable byte fields (no pointers):
low 2 bits are low 2 bits of size in bytes |
12-15 | compiled methods: low 2 bits are low 2 bits of size in bytes.
The number of literals is specified in method header, followed by the indexable bytes that store byte codes. |
For Squeak, we determined to apply the same approach to our new system of 32-bit direct pointers. We were faced immediately with a number of challenges. First, we had to write an in-place mark phase capable of dealing with our variable-length headers, including those that did not have an actual class pointer in them. Then there was the need to produce a structure for remapping object pointers during compaction, since we did not have the convenient indirection of an object table. Finally there was the challenge of rectifying all the object pointers in memory within an acceptable time.
The remapping of object pointers was accomplished by building a number of relocation blocks down from the unused end of memory. A thousand such blocks are reserved outside the object heap, ensuring that at least one thousand objects can be moved even when there is very little free space. However, if the object heap ends with a free block, that space is also used for relocation blocks. If there is not enough room for the number of relocation blocks needed to do compaction in a single pass (almost never), then the compaction may be done in multiple passes. Each pass generates free space at the end of the object heap which can then be used to create additional relocation blocks for the next pass.
One more issue remained to be dealt with, and that was support of the become operation without an object table. (The Smalltalk become primitive atomically exchanges the identity of two objects; to Smalltalk code, each object appears to turn into, or "become," the other.) With an object table, the become primitive simply exchanges the contents of two object table entries. Without an object table, it requires a full scan of memory to replace every pointer to one object with a pointer to the other. Since full memory scans are relatively costly, we made two changes. First, we eliminated most uses of become in the Squeak image by changing certain collection classes to store their elements in separate Array objects instead of indexed fields. However, become operations are essential when adding an instance variable to a class with extant instances, as each instance must mutate into a larger object to accommodate the new variable. So, our second change was to restructure the primitive to one that exchanges the identity of many objects at once. This allows all the instances of a class to be mutated in a single pass through memory. The code for this operation uses the same technique and, in fact, the very same code, as that used to rectify pointers after compaction.
We originally sought to minimize compaction frequency, owing to the overhead associated with rectifying direct addresses. Our strategy was to do a fast mark and sweep, returning objects to a number of free lists, depending on size. Only when memory became overly fragmented would we do a consolidating compaction.
As we studied and optimized the Squeak garbage collector, however, we were able radically to simplify this approach. Since an incremental reclamation only compacts the new object space, it is only necessary to rectify the surviving new objects and any old objects that point to them. The latter are exactly those objects marked as root objects. Since there are typically just a few root objects and not many survivors (most objects die young), we discovered that compaction after an incremental reclamation could be done quickly. In fact, due to the overhead of managing free lists, it turned out to be more efficient to compact after every incremental reclamation and eliminate free lists altogether. This was especially gratifying since issues of fragmentation and coalescing had been a burden in design, analysis, and coding strategy.
Two policy refinements reduced the incremental garbage collection pauses to the point where Squeak became usable for real-time applications such as music and animation. First, a counter is incremented each time an object is allocated. When this counter reaches some threshold, an incremental collection is done even if there is plenty of free space left. This reduces the number of new objects that must be scanned in the sweep phase, and also limits the number of surviving objects. By doing a little work often, each incremental collection completes quickly, typically in 5-8 milliseconds. This is within the timing tolerance of even a fairly demanding musician or animator.
The second refinement is to tenure all surviving objects when the number of survivors exceeds a certain threshold, a simplified version of Ungar and Jackson's feedback-mediated tenuring policy [UnJa88]. Tenuring is done as follows. After the incremental garbage collection and compaction, the boundary between the old and new object spaces is moved up to encompass all surviving new objects, as if a full garbage collection had just been done. This "clears the decks" so that future incremental compactions have fewer objects to process. Although in theory this approach could hasten the onset of the next full garbage collection, such full collections are rare in practice. In any case, Squeak's relatively lean image makes full garbage collections less daunting than they might be in a larger system; a full collection typically takes only 250 milliseconds in Squeak. We have been using this storage manager in support of real-time graphics and music for over a year now with extremely satisfactory results. In our experience, 10 milliseconds is an important threshold for latency in interactive systems, because most of the other critical functions such as mouse polling, sound buffer output and display refresh take place at a commensurate rate.
It was relatively simple to extend the internal logic of BitBlt to handle multiple pixel sizes as long as source and destination bit maps are of the same depth. To handle operations between images of different depth, we provided a default conversion, and added an optional color map parameter to BitBlt to provide more control when appropriate. The default behavior is simply to extend smaller source pixels to a larger destination size by padding with zeros, and to truncate larger source pixels to a smaller destination pixel size. This approach works very well among the table-based colors because the color set for each depth includes the next smaller depth's color set as a subset. In the case of RGB colors, BitBlt performs the zero-fill or truncation independently on each color component.
The real challenge, however, involves operations between RGB and table-based color depths. In such cases, or when wanting more control over the color conversion, the client can supply BitBlt with a color map. This map is sized so that there is one entry for each of the source colors, and each entry contains a pixel in the format expected by the destination. It is obvious how to work with this for source pixel sizes of 8 bits or less (map sizes of 256 or less). But it would seem to require a map of 65536 entries for 16 bits or 4294967296 entries for 32-bit color! However, for these cases, Squeak's BitBlt accepts color maps of 512, 4096, or 32768 entries, corresponding to 3, 4, and 5 bits per color component, and BitBlt truncates the source pixel's color components to the appropriate number of bits before looking up the pixel in the color map.
Our bootstrapping strategy also depended on being able to debug the Smalltalk code for the Squeak virtual machine by running it under an existing Smalltalk implementation, and this approach was highly successful. Being able to use the powerful tools of the Smalltalk environment saved us weeks of tedious debugging with a C debugger. However, useful as it is for debugging, the Squeak virtual machine running on top of Smalltalk is orders of magnitude too slow for useful work: running in Squeak itself, the Smalltalk version of the Squeak virtual machine is roughly 450 times slower than the C version. Even running in the fastest available commercial Smalltalk, the Squeak virtual machine running in Smalltalk would still be sluggish.
The key to both practical performance and portability is to translate the Smalltalk description of the virtual machine into C. To be able to do this translation without having to emulate all of Smalltalk in the C runtime system, the virtual machine was written in a subset of Smalltalk that maps directly onto C constructs. This subset excludes blocks (except to describe a few control structures), message sending, and even objects! Methods of the interpreter classes are mapped to C functions and instance variables are mapped to global variables. For byte code and primitive dispatches, the special message dispatchOn:in: is mapped to a C switch statement. (When running in Smalltalk, this construct works by perform:-ing the message selector at the specified index in a case array; since a method invocation is much less efficient than a branch operation, this dispatch is one of the main reasons that the interpreter runs so much faster when translated to C).
The translator first translates Smalltalk into parse trees, then uses
a simple table-lookup scheme to generate C code from these parse trees.
There are only 42 transformation rules, as shown in Table 3. Four of these
are for integer operations that more closely match those of the underlying
hardware, such as unsigned shifts, and the last three are macros for operations
so heavily used that they should always be inlined. All translated code
accesses memory through six C macros that read and write individual bytes,
4-byte words, and 8-byte floats. In the early stages of development, every
such reference was checked against the bounds of object memory.
& | and: or: not + - * // \\ min: max: bitAnd: bitOr: bitXor: bitShift: < <= = > >= ~= == isNil notNil whileTrue: whileFalse: to:do: to:by:do: ifTrue: ifFalse: ifTrue:ifFalse: ifFalse:ifTrue: at: at:put: << >> bitInvert32 preIncrement integerValueOf: integerObjectOf: isIntegerObject: |
Early on, we implemented access to the Macintosh sound driver. As the performance of the Squeak system improved, we were delighted to find that we could actually synthesize and mix several voices of music in real time using simple wave table and FM algorithms written entirely in Smalltalk.
Nonetheless, these algorithms are compute-intensive, and we used this application as an opportunity to experiment with using C translation to improve the performance of isolated, time-critical methods. Sound synthesis is an ideal application for this, since nearly all the work is done by small loops with simple arithmetic and array manipulation. The sound generation methods were written so that they could be run directly in Smalltalk or, without changing a line of code, translated into C and linked into the virtual machine as an optional primitive. Since the sound generation code had already been running for weeks in Smalltalk, the translated primitives worked perfectly the first time they ran. Furthermore, we observed nearly a 40-fold increase in performance: from 3 voices sampled at 8 KHz, we jumped to over 20 voices sampled at 44 KHz.
Once we started playing with arbitrarily rotated and scaled images, we began to wish that the results of this crude warp were not so jagged. This led to support for over sampling and smoothing in the warp drive, which does a reasonable job of anti-aliasing in many cases. The approach is to average a number of pixels around a given source coordinate. Averaging colors is not a simple matter with the table-based colors of 8 bits or less. The approach we used is to map from the source color space to RGB colors, average the samples in RGB space, and map the final result back to the nearest indexed color via the normal depth-reducing color map.
As with the sound synthesis work, WarpBlt is completely described in Smalltalk, then translated into C to deliver performance appropriate to interactive graphics.
Smalltalk | Lines | C | Lines |
---|---|---|---|
Interpreter | 3951 | OS interface | 1681 |
Object Memory | 1283 | ||
BitBlt with Warp | 1313 |
Date | byte codes/sec | sends/sec |
---|---|---|
Apr. 14 | 458K | 22,928 |
May 20 | 1,111K | 60,287 |
May 23 | 1,522K | 69,319 |
July 9 | 2,802K | 134,717 |
Aug. 1 | 2,726K | 130,945 |
Sept. 23 | 3,528K | 141,155 |
Nov. 12 | 3,156K | 133,164 |
Dec. 12 | 3,410K | 169,617 |
Jan. 21 | 4,108K | 173,360 |
AppleST | ST/V | PP2.3 | PP2.5 | Squeak | SqueakPPC | |
---|---|---|---|---|---|---|
IntegerSum | 185.00 | 32.00 | 7.58 | 6.92 | 62.34 | 72.56 |
VectorSum | 99.00 | 30.00 | 10.30 | 11.50 | 61.70 | 41.01 |
PrimeSieve | 53.00 | 40.00 | 16.07 | 12.10 | 70.53 | 51.57 |
BubbleSort | 88.23 | 35.29 | 21.35 | 13.98 | 80.29 | 63.12 |
TreeSort | 43.90 | 5.00 | 20.29 | 1.98 | 16.33 | 7.31 |
MatrixMult | 40.79 | 6.00 | 22.80 | 2.94 | 18.00 | 36.74 |
Recurse | 28.26 | 9.47 | 3.73 | 2.08 | 50.26 | 35.19 |
We believe that Squeak can enjoy the same performance as commercial Smalltalk implementations without compromising malleability and portability. In our experience the byte code basis of the Smalltalk-80 standard [Inga78] is hard to beat for compactness and simplicity, and for the programming tools that have grown around it. Therefore dynamic translation is a natural avenue to high performance. The Squeak philosophy implies that both the dynamic translator and its target code sequences should be written and debugged in Smalltalk, then automatically translated into C to build the production virtual machine. By representing translated methods as ordinary Smalltalk objects, experiments with Self-style inlining and other optimizations could be done at the Smalltalk level. This approach is currently being explored as a way to improve Squeak's performance without adversely affecting its portability.
Three weeks later, we received a message announcing Ian Piumarta's first UNIX port of Squeak. He had ported it to seven additional UNIX platforms two weeks later. At the same time, Andreas Raab announced ports of Squeak for Windows 95 and Windows NT. Neither of these people had even contacted us before starting their porting efforts! A mere five weeks after it was released, Squeak was available on all the major computing platforms except Windows 3.1, and had an active and rapidly growing mailing list. Since that time, Squeak ports have been done for Linux, the Acorn RISC, and Windows CE, and several other ports are underway.
The Squeak release, including the source code for the virtual machine, C translator and everything else described in this paper, as well as all the ports mentioned above, is available through the following sites: <http://www.research.apple.com/research/proj/learning_concepts/squeak/> <ftp://ftp.create.ucsb.edu> <ftp://alix.inria.fr> <ftp://ftp.cs.uni-magdeburg.de/pub/ Smalltalk/free/squeak>
The Squeak license agreement explicitly grants the right to use Squeak in commercial applications royalty-free. The only requirement in return is that any ports of Squeak or changes to the base class library must be made available for free on the Internet. New applications and facilities built on Squeak do not need to be shared. We believe that this licensing agreement encourages the continued development and sharing of Squeak by its user community.
A number of recent systems translate complete Smalltalk programs into lower-level languages to gain speed, portability, or application packaging advantages. Smalltalk/X [Gitt95] and SPiCE [YaDo95] generate C code from programs using the full range of Smalltalk semantics, including blocks. Babel [MWH94] translates Smalltalk applications into CLOS, and includes a facility for automatically winnowing out unused classes and methods.
Producer [Cox87] translated Smalltalk programs into Objective C, but required the programmer to supply type declarations and rules for mapping dynamically allocated objects such as Points into Objective C record structures. Producer only supported a subset of Smalltalk semantics because it depended on the Objective C runtime and thus did not support blocks as first-class objects. Squeak's Smalltalk-to-C translator restricts the programmer to an even more limited subset of Smalltalk, but that subset closely mirrors the underlying processor architecture, allowing the translated code to run nearly as efficiently as if it were written in C directly. The difference arises from a difference in goals: The goal of Squeak's translation is merely to support the construction of its own virtual machine, a much simpler task than translating full-blown Smalltalk programs into C. Squeak's translator is more in the spirit of QUICKTALK [Ball86], a system that used Smalltalk to define new primitive methods for the virtual machine. Another Smalltalk-to-primitive compiler, Hurricane [Atki86], used a combination of user-supplied declarations and simple type inference to eliminate class checks and to inline integer arithmetic. Unlike Squeak's translator, Hurricane allowed the programmer to also use polymorphic arithmetic in the Smalltalk code to be translated. Neither QUICKTALK nor Hurricane attempted to produce an entire virtual machine via translation.
Type information can help a translator produce more efficient code by eliminating run-time type tests and enabling inlining. Typed Smalltalk [JGZ88] added optional type declarations to Smalltalk and used that type information to generate faster code. The quality of its code was comparable to that of QUICKTALK but, to the best of the authors' knowledge, the project's ultimate goal of producing a complete, stand-alone Smalltalk virtual machine was never realized. A different approach is to use type information gathered during program execution to guide on-the-fly optimization, as done in the Self [ChUn91] [H–lz94] and Animorphic [Anim96] virtual machines. Note that using types for optimization is independent of whether the programming language has type declarations. The Self and Animorphic virtual machines use type information to optimize declaration-free languages whereas Strongtalk [BrGr93], which augments Smalltalk with an optional type system to support the specification and verification of interfaces, ran on a virtual machine that knew nothing about those types. The subset of Smalltalk used for the Squeak virtual machine maps so directly to the fundamental data types of the hardware that the translator would not benefit from additional type information. However, we have contemplated building a separate primitive compiler that supports polymorphic arithmetic, in which case the declaration-driven optimization techniques of Hurricane and Typed Smalltalk would be beneficial.
We are collaborating with Ian Piumarta to produce a dynamic translation engine for Squeak, inspired by Eliot Miranda's BrouHaHa Smalltalk [Mira87] and his later work with portable threaded code. A top priority is to build the entire engine in Smalltalk to keep it entirely portable.
Just as we wanted Squeak to be endowed with music and sound capability, we also wanted it to be easily interconnected with the rest of the computing world. To this end, we are adding network stream and datagram support to the system. While not yet complete, the current facilities already support TCP/IP clients and servers on Macintosh and Windows 95/NT, with UNIX support to follow soon.
To achieve useful levels of performance, the Smalltalk code of the virtual machine is translated into C, yielding a speedup of approximately 450. Part of this performance gain, a factor of 3.4, can be attributed to the inlining of function calls in the translation process. The translator can also be used to generate primitive methods for computationally intensive inner loops that manipulate fundamental data types of the machine such as bytes, integers, floats, and arrays of these types.
The Squeak virtual machine, since its source code is publicly available, serves as an updated reference implementation for Smalltalk-80. This is especially valuable now that the classic Blue and Green Books [Gold83] [Kras83] are out of print. A number of design choices made in the Blue Book that were appropriate for the slower speed and limited address space of the computer systems of the early 1980's have been revisited, especially those relating to object memory and storage reclamation. Squeak also updates the multimedia components of this reference system by adding color support and image transformation capabilities to BitBlt and by including sound output. While Squeak is not the first Smalltalk to use modern storage management or to support multimedia, it makes a valuable contribution by delivering these capabilities in a small one-language package that is freely available, and that runs identically on all platforms.
References
[Anim96] Animorphic Systems, Exhibit at OOPSLA '96. Animorphic Systems was a small company that included several members of the Self team and produced extremely high performance virtual machines for Smalltalk and Java. The company has since been purchased by Sun Microsystems. [Atki86] Atkinson, R., "Hurricane: An Optimizing Compiler for Smalltalk," Proc. of the ACM OOPSLA '86 conf., September 1986, pp. 151-158. [BrGr93] Bracha, G. and Griswold, D., "Strongtalk: Typechecking Smalltalk in a Production Environment," Proc. of the ACM OOPSLA '93 conf., September 1993. [Ball86] Ballard, M., Maier, D., and Wirffs-Brock, A., "QUICKTALK: A Smalltalk-80 Dialect for Defining Primitive Methods," Proc. of the ACM OOPSLA '86 conf., September 1986, pp. 140-150. [ChUn91] Chambers, C. and Ungar, D., "Making Pure Object-Oriented Languages Practical," Proc. of the ACM OOPSLA '91 conf., November 1991, pp. 1-15. [Cox87] Cox, B. and Schmucker, K., "Producer: A Tool for Translating Smalltalk-80 to Objective-C," Proc. of the ACM OOPSLA '87 conf., October 1987, pp. 423-429. [Deut84] Deutsch, L., and Schiffman, A., "Efficient Implementation of the Smalltalk-80 System," Proc. 11th ACM Symposium on Principles of Programming Languages, January 1984, pp. 297-302. [Gitt95] Gittinger, Claus, Smalltalk/X, ,http://www.informatik.uni-stuttgart.de/stx/stx.html 1995. [Gold83] Goldberg, A. and Robson, D., Smalltalk-80: The Language and Its Implementation, Addison-Wesley, Reading, MA,1983. [H–lz94] H–lzle, U., Adaptive optimization for Self: Reconciling High Performance with Exploratory Programming, Ph.D. Thesis, Computer Science Department, Stanford University, 1994. [Inga78] Ingalls, D., "The Smalltalk-76 Programming System, Design and Implementation" Proc. 5th ACM Symposium on Principles of Programming Languages, Tucson, January 1978. [Inga88] Ingalls, D., Wallace, S., Chow, Y., Ludolph, F., and Doyle, K., "Fabrik: A Visual Programming Environment," Proc. of the ACM OOPSLA '88 conf., September 1988, pp. 176-190. [JGZ88] Johnson, R., Graver, J., and Zurawski, L.,"TS: An Optimizing Compiler for Smalltalk," Proc. of the ACM OOPSLA '88 conf., September 1988, pp. 18-26. [Kaeh86] Kaehler, Ted, "Virtual Memory on a Narrow Machine for an Object-Oriented Language," Proc. of the ACM OOPSLA '86 conf., September 1986, pp. 87-106. [Kras83] Krasner, G., ed., Smalltalk-80, Bits of History, Words of Advice, Addison-Wesley, Reading, MA,1983. [Malo95] Maloney, J. and Smith, R., "Directness and Liveness in the Morphic User Interface Construction Environment," UIST '95, November 1995. [Mira87] Miranda, E., "BrouHaHa—A Portable Smalltalk Interpreter," Proc. of the ACM OOPSLA '87 conf., October 1987, pp. 354-365. [MWH94] Moore, I., Wolczko, M., and Hopkins, T., "Babel—A Translator from Smalltalk into CLOS," TOOLS USA 1994, Prentice Hall, 1994. [Saun77] Saunders, S., "Improved FM Audio Synthesis Methods for Real-time Digital Music Generation," in Computer Music Journal 1:1, February 1977. Reprinted in Computer Music, Roads, C. and Strawn, J., eds., MIT Press, Cambridge, MA, 1985. [Unga84] Ungar, D.,"Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm," Proc. ACM Symposium on Practical Software Development Environments, April 1984, pp. 157-167. Also published as ACM SIGPLAN Notices 19(5), May 1984 and ACM Software Engineering Notes 9(3), May 1984. [UnJa88] Ungar, D. and Jackson, F.,"Tenuring Policies for Generation-Based Storage Reclamation," Proc. of the ACM OOPSLA '88 conf., September 1988, pp. 18-26. [YaDo95] Yasumatsu, K. and Doi, N., "SPiCE: A System for Translating Smalltalk Programs Into a C Environment," IEEE Transactions on Software Engineering 21(11), 1995, pp. 902-912.