# Smalltalk-80: Bits of History, Words of Advice

Glenn Krasner

► To cite this version:

Glenn Krasner. Smalltalk-80: Bits of History, Words of Advice. 1983. hal-05185384

HAL Id: hal-05185384

https://inria.hal.science/hal-05185384v1

Submitted on 26 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Smalltalk-80

*Bits of History, Words of Advice*

Glenn Krasner, Editor

Xerox Palo Alto Research Center

<figure><img src="image_2.png" /></figure>

Addison-Wesley Publishing Company

Reading, Massachusetts • Menlo Park, California

London • Amsterdam • Don Mills, Ontario • Sydney
This book is in the
**Addison-Wesley series in Computer Science**

MICHAEL A. HARRISON
CONSULTING EDITOR

Cartoons drawn by Jean Depoian

**Library of Congress Cataloging in Publication Data**

Main entry under title:

Smalltalk-80 : bits of history, words of advice.

Bibliography: p.

Includes index.

1. Smalltalk-80 (Computer system) I. Krasner,

Glenn. II. Title: Smalltalk-eighty.

QA76.8.S635S58 1983 001.64'.25 83-5985

ISBN 0-201-11669-3

Reprinted with corrections, June 1984

Copyright © 1983 by Xerox Corporation.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. Published simultaneously in Canada.

ISBN 0-201-11669-3
CDEFGHIJ-AL-8987654
# Preface

The Software Concepts Group of Xerox Palo Alto Research Center (PARC) has been working on the problem of how to give users access to large amounts of computing power. We have concentrated our efforts on the study of software systems, rather than on the creation of specific hardware packages. Our method has been to develop a software system called Smalltalk, to create applications in that system, and then, based on our experiences developing the applications, to design the next system. We have developed and used three major Smalltalk systems over the last 10 years, as well as a few minor variations.

We have documented and released the latest of these systems, the Smalltalk-80 system. We published a description of the system and a complete specification of its implementation in the book, *Smalltalk-80: The Language and Its Implementation*. This first book, however, does not cover the use of the system or programming style for writing large applications in the system. These topics are covered in the forthcoming books *Smalltalk-80: The Interactive Programming Environment* and *Smalltalk-80: Creating a User Interface and Graphical Applications*. Nor does the first book discuss implementation techniques beyond the formal specification, which is the subject of this book, *Smalltalk-80: Bits of History, Words of Advice*.

To check the accuracy and the clarity of the first book, we invited a number of groups outside of Xerox to build implementations of the Smalltalk-80 system. Those groups uncovered problems with the written description, and with the system itself, which we then corrected. They also formed the beginning of a community of Smalltalk
implementors with whom we can discuss our ideas, and from whom we
can learn about successful and less successful implementation experi-
ences. Paul McCullough of Tektronix suggested that all the
implementors submit papers describing their experiences to a software
engineering journal or to collect papers from each group into book
form. This book, then, is the outcome of that suggestion.

The papers in this book should be of value to other Smalltalk-80
implementors. To implement the Smalltalk-80 system, one has to match
the specification with his or her own hardware environment. Each of
the groups represented in this book had different experiences with this
problem. In addition, some of the groups tested (or speculated about)
various schemes for better Smalltalk-80 virtual machine implementa-
tions.

In addition to Smalltalk-80 implementors, software engineers should
be interested in the papers in this book. Although they are written in
the context of Smalltalk-80 implementations, the papers cover the gen-
eral software engineering topics of managing large software projects,
virtual memory design and implementation, software caching mecha-
nisms, and mapping software needs onto hardware design.

The papers in this book raise more issues than they resolve.
Smalltalk is still quite young—the Smalltalk-80 system is just a snap-
shot of research in progress. There are many other issues that need to
be raised and many ideas that need to be tested before some of the reso-
lutions can be found. It is our hope that this collection of works will get
other implementors thinking about key issues in Smalltalk implemen-
tations.

Part One of this book is a collection of papers that provide some
background and history of the Smalltalk-80 implementation. The first
paper is by Adele Goldberg, manager of the Xerox PARC Software Con-
cepts Group (SCG); it describes the history of releasing the Smalltalk-80
system to the non-Xerox world. Dan Ingalls, who has been the chief ar-
chitect of the many Smalltalk implementations, tells how the previous
systems led up to the Smalltalk-80 system. Glenn Krasner, also of SCG,
presents the design of the format of files that are used for sharing
Smalltalk-80 code among implementations. The last paper in this sec-
tion is by Allen Wirfs-Brock of Tektronix, and explores the various de-
sign decisions that Smalltalk-80 implementors may face.

In Part Two we present papers that describe the experiences four
implementors had in bringing their systems to life. Paul McCullough
writes about the process they went through at Tektronix, including a
step-by-step description taken directly from their logs. His paper points
out how valuable the outside implementors were at discovering prob-
lems with the system and its documentation. Joe Falcone and Jim
Stinger describe the experience they had at Hewlett-Packard bringing
up a couple of implementations. Peter Deutsch, of Xerox SCG, gives
some details of how he took advantage of hardware architecture to increase the performance of his Smalltalk-80 implementation. Stoney Ballard and Steve Shirron describe an implementation they made at Digital Equipment Corp., which differs radically from the suggested implementation of the storage manager, in order to provide improved performance.

Descriptions of implementation experiences help others make their design choices; actual measurements and analyses provide additional concrete help. Part Three is a collection of measurements made by the implementation groups. The first paper, by Kim McCall of Xerox SCG, describes a set of benchmarks that is provided in the Smalltalk-80 system to help measure the performance of an implementation. All the implementation groups were willing to run these benchmarks, and a comparison of their results is included in the paper. This gives a number of implementations against which new implementors can measure their progress. Rick Meyers and Dave Casseres of Apple Computer provide an interesting set of analyses of their MC68000-based implementation. David Ungar and David Patterson of the University of California Berkeley give a before-and-after description of the process of measuring an implementation, optimizing the time-consuming parts, and measuring the effects of the optimizations. Joe Falcone made measurements of the Hewlett-Packard implementation that compare static properties with dynamic properties of the system. Finally, Tom Conroy and Ed Pelegri-Llopart of UC Berkeley present an analytic model for measuring the potential performance gains of a particular cache scheme for Smalltalk-80 implementations.

In Part Four we present papers that look toward the future of Smalltalk systems and propose ideas for extending the Smalltalk-80 system beyond its initial form. The first paper is a description by Ted Kaehler and Glenn Krasner of Xerox SCG of an object-oriented virtual memory design. Steve Putz, also of SCG, presents a solution to the problem of coordinating changes made by many people to an evolving Smalltalk-80 system. Jason Penney describes his implementation of a file system at Tektronix, and discusses the use of the Smalltalk-80 system for programming. From the University of Washington, Guy Almes, Alan Borning, and Eli Messinger, present an analysis of the potential for implementing the Smalltalk-80 system on the Intel iAPX432 microprocessor. Although they did not actually implement the system, their paper provides a good analysis of how to match an object-oriented system to object-oriented hardware. Applying compiler technology, Robert Hagmann of the University of California, Berkeley, proposes ways to increase the performance of a Smalltalk-80 implementation. The last paper, by Scott Baden of the University of California, Berkeley, proposes hardware architecture support that would enhance the performance of implementations.
**Acknowledgments**

We would like to thank the authors, their co-workers, and their organizations for their contributions to this book, for their diligence during the release and review process, and for their willingness to be open about the strengths and weaknesses of their Smalltalk-80 implementations. We would also like to thank the Xerox Research management for allowing us to release the Smalltalk-80 system, thus widening the community of Smalltalk implementors with whom we can share experiences and insights.

Many people contributed to the production of this book. Each author also acted as an editor of an early draft of another author's paper. Janet Moreland helped coordinate this swapping with copying and mailing. Doug Carothers answered legal questions. Ted Kaehler provided other bits of help, and Frank Zdybel added some words of his own. Dave Robson built the translator that allowed us to deliver manuscripts electronically. Eileen Colahan of the International Computaprint Corporation was extremely cooperative and flexible in turning these electronic manuscripts into print. The cartoons in the book are by Ted Kaehler, redrawn by Addison-Wesley artist Jean Depoian. Adele Goldberg merged the images into the cover design with help from Rebecca Cannara. Particular thanks go to production editor Fran Fulton for her cooperation and patience, and to Jim DeWolf and Cheryl Wurzbacher of Addison-Wesley.

Registered trademarks mentioned in this book are: AED-512, Advanced Electronic Design, Inc.; UNIX, Bell Laboratories; DEC, DECSYSTEM, DECSYSTEM20, UNIBUS and VAX, Digital Equipment Corporation; HP-IB, Hewlett-Packard; GPIB, National Instruments; BitPadOne, Summagraphics Corporation; and Smalltalk-80, Xerox Corporation.

Palo Alto, California

June 1983

G. E. K.
# Contents

PART ONE Background 1

1 The Smalltalk-80 System Release Process
Adele Goldberg 3

2 The Evolution of the Smalltalk Virtual Machine
Daniel H. H. Ingalls 9

3 The Smalltalk-80 Code File Format Glenn Krasner 29

4 Design Decisions for Smalltalk-80 Implementors
Allen Wirfs-Brock 41

PART TWO Experiences Implementing the Smalltalk-80 System 57

5 Implementing the Smalltalk-80 System: The
Tektronix Experience Paul L. McCullough 59

6 The Smalltalk-80 Implementation at Hewlett-
Packard Joseph R. Falcone, James R. Stinger 79

7 The Dorado Smalltalk-80 Implementation: Hard-
ware Architecture's Impact on Software
Architecture L. Peter Deutsch 113

8 The Design and Implementation of
VAX/Smalltalk-80
Stoney Ballard, Stephen Shirron 127
PART THREE Measurements and Analyses of Implementations 151

9 The Smalltalk-80 Benchmarks Kim McCall 153

10 An MC68000-Based Smalltalk-80 System Richard Meyers, David Casseres 175

11 Berkeley Smalltalk: Who Knows Where the Time Goes? David M. Ungar, David A. Patterson 189

12 The Analysis of the Smalltalk-80 System at Hewlett-Packard Joseph R. Falcone 207

13 An Assessment of Method-Lookup Caches for Smalltalk-80 Implementations Thomas J. Conroy, Eduardo Pelegri-Llopart 239

PART FOUR Proposals for the Future of the Smalltalk-80 System 249

14 LOOM—Large Object-Oriented Memory for Smalltalk-80 Systems Ted Kaehler, Glenn Krasner 251

15 Managing the Evolution of Smalltalk-80 Systems Steve Putz 273

16 Implementing a Smalltalk-80 File System and the Smalltalk-80 System as a Programming Tool D. Jason Penney 287

17 Implementing a Smalltalk-80 System on the Intel 432: A Feasibility Study Guy Almes, Alan Borning, Eli Messinger 299

18 Preferred Classes: A Proposal for Faster Smalltalk-80 Execution Robert Hagmann 323

19 Low-Overhead Storage Reclamation in the Smalltalk-80 Virtual Machine Scott B. Baden 331

Index 343
PART ONE

<figure><img src="image_3.png" /></figure>

DEBUGGING AFTER A
SMALLTALK CRASH
# The Smalltalk-80 System Release Process

Adele Goldberg

Manager, Software Concepts Group
Xerox Palo Alto Research Center
Palo Alto, California

## Introduction

The Smalltalk-80 system has its roots in the Xerox Palo Alto Research Center starting more than 10 years ago. During a decade of research, three major systems were designed, implemented, and tested with a variety of users. The systems were named for the year in which they were designed. The first two were Smalltalk-72 and Smalltalk-76. The latest version, called the Smalltalk-80 system, was developed to be adaptable for implementation on a large number and variety of computers.

The Smalltalk research efforts focus on increasing the support that computing systems can provide to users who are not computer scientists by profession. These efforts are centered on the visual impact of bitmapped graphics, on highly interactive user interfaces, and on increased flexibility in terms of user programmability. Among the outcomes of this work were the basic concepts of windows, menus (textual and iconic), and scroll bars. Implementations of these concepts are used to expand the virtual space of a display screen; they typically emphasize the use of pointing devices rather than keyboards for selecting objects (documents, devices) and operations on objects (commands).

In 1979 and 1980, requests and clearances were agreed upon within the Xerox Corporation to permit the dissemination of the Smalltalk-80
system to the non-Xerox world. The stated purposes of this dissemination were to:

1. expand the community of Smalltalk programmers in order to gain more general experience with how people can use the language;

2. expand the community of programming language researchers who study aspects of the Smalltalk style of programming;

3. influence hardware designers to consider ways in which to provide increased performance for the Smalltalk style of interaction; and

4. establish a standard for Smalltalk as an object-oriented programming language and a graphics-based, interactive program development environment.

The dissemination was planned in three parts: a series of introductory articles, a book giving detailed system specifications, and a magnetic tape containing the system itself. The series of articles would provide an early and less formal introduction to the Smalltalk-80 system. Ultimately, these articles were published in the August 1981 special issue of *Byte* magazine. The system specification was divided into two major components—the Virtual Machine and the Virtual Image. The Virtual Machine for a particular hardware system consists of an interpreter, a storage manager, and primitives for handling the input/output devices. The Virtual Image is a collection of objects that make up descriptions of classes providing basic data structures (including numbers), basic graphics and text, compiler, decompiler, debugger, and viewing and user interface support. The Virtual Image contains approximately 10,000 objects. The proposed book would contain the formal specifications for the implementation of the Virtual Machine, as well as a description of the language and the interfaces to the objects in the Virtual Image. The proposed tape would contain a digital representation of the Virtual Image that could be loaded into a hardware system on which the Virtual Machine had been implemented.

All systems running the Smalltalk-80 system would therefore look the same; each would have to support bitmapped graphics and a pointing device for controlling a cursor on the graphics display. The issue of protecting the software was resolved by copyrighting the Virtual Image and publicly disclosing the Virtual Machine; licensing under copyright grants the licensee the right to reproduce the Image only for incorporation into a hardware product of the licensee. Any unincorporated reproduction and distribution is prohibited. The modular approach to the Smalltalk design made this form of protection feasible.
An initial attempt to produce a book about the Smalltalk system described the design of an unfinished system that was to be called Smalltalk-80. Chapters of the book were written in the spring and summer of 1979. Since much of this written material described how to implement the system, an appropriate review of the material required following the specifications and actually implementing the Virtual Machine. This was accomplished by involving members of software groups of several computer manufacturers in the process of review and implementation. Although the Smalltalk systems had received a great deal of publicity since Smalltalk-72 was first designed, few people outside Xerox's research centers had actually used them before this review.

The cautious invitation issued to six companies was to read the book material in order to understand the nature of the system. Reviewers were also invited to visit the Xerox Palo Alto Research Center in order to see a live demonstration of the system. If they were still interested in the system after reading the written material and participating in a demonstration, they were invited to enter the second phase of review—an actual implementation. A company could only accept the invitation if it had (1) the required hardware (at least a 16-bit processor, a bitmapped display, and a way of indicating locations on the display), and (2) a software team on the project that consisted of regular employees only.

Only four of those invited were able to enter the second phase of the review, Apple Computer, Digital Equipment Corporation, Hewlett-Packard, and Tektronix. These four companies agreed to share in debugging the formal specification of the Virtual Machine. Problems encountered and general design advice would be exchanged with all participants. Besides assisting in completing a book about the system, this review process would test the ability of these manufacturers to successfully create a full implementation of the Smalltalk-80 system based on the information provided in the book. Success would be measured by each manufacturer's ability to "read and adopt" the Virtual Image; a more subjective measurement would be the actual performance of the system on each manufacturer's hardware.

By 1982, the review process was complete enough that a revision of the book was possible. Actually, the written material was treated much the way the Smalltalk software had been treated over the decade of research—it was thrown away, with the exception of the (now debugged) formal specification of the Virtual Machine. All of the chapters were rewritten. Because of the volume of material that was to be disseminated, the book became three books—one for the programmer and language designer (Smalltalk-80: The Language and Its Implementation), one for the user and programming environments designer (Smalltalk-80: The Interactive Programming Environment), and one for
the applications designer (Smalltalk-80: Creating a User Interface and Graphical Applications).

For their participation in the review process, each manufacturer received a right to use the Smalltalk-80 Virtual Image in their research and in their developed hardware products. Thus the Virtual Machine has been provided outside Xerox without obligation, while the Virtual Image for use in conjunction with the Machine has been licensed under the auspices of copyright. That is, the reproduction and redistribution of the Virtual Image or portions of the Virtual Image are permitted only as incorporated into a product of these manufacturers/licensees.

## The Review Process

The first tape containing a Virtual Image was delivered February 17, 1981. The image file contained 328 records, 512 bytes per record. The purpose of this tape was to debug the image file format, and to get the reviewers started loading in and running a version of Smalltalk. The image had two deficiencies: the source code for the class hierarchy was primarily a subset of the system, and the primitives called from each class had only preliminary class/method and number assignments. The reviewers were also provided a detailed memo instructing them how to read the image file format and summarizing the information provided in the book on formats for object pointers, object space, contexts, compiled methods, and classes.

As part of the agreement, telephone consultation was available to the implementors. Any major bugs or discrepancies in the specifications were reported via telephone and logged. It was possible to monitor each implementor's progress with respect to their discovery of or compensation for the bugs. The process of revising the system image itself was carried out at Xerox with the aid of electronic mail: bug reports, bug fixes, status reports, and new ideas were typically communicated electronically. Eventually these communications evolved into a Smalltalk-80 subsystem called the Version Manager which supported (re-)configuration of new system releases.

The second tape was delivered on July 24, 1981. In addition to the image file (this time 589 records long), the tape contained a file of the source code, a file into which the system writes its "audit trail" of changes, and three files containing traces generated by the Smalltalk-80 simulator as it executes the first bytecodes in the Virtual Image. The traces were made by running the formal specification of the interpreter written in Smalltalk-80 code (the code is included in the chapters of the book).
The three traces, provided in all subsequent tape releases, show decreasing levels of detail over increasing durations.

1. The first trace shows all memory references, allocations, bytecodes, message transmissions, returns, and primitive invocations for the first 115 bytecodes executed.

2. The second trace shows only the bytecodes, message transmissions, returns, and primitives for the first 409 bytecodes.

3. The third trace shows message transmissions, primitives, and returns for the first 1981 bytecodes.

The traces allow the implementors to compare their system's actual behavior with the "expected" behavior.

This second tape contained a full system according to the specification of the Smalltalk-80 Virtual Machine. All the source code had either been rewritten according to the class hierarchy for Smalltalk-80, or had been translated from the Smalltalk-76 classes into the Smalltalk-80 syntax. However, this translated code was not the definition for the final system.

The third tape was delivered four months later on November 18, 1981. It contained the same kinds of files as were provided on the second tape. By this time, however, the system user interface had been completely rewritten and a great deal of new functionality had been provided in the program development environment. The image file was now 977 records long.

Once again, the Virtual Machine had been changed, in particular, several primitives were added. This time the changes were mostly those discussed and agreed upon by the implementors who attended the "First Ever Smalltalk-80 Implementors' Conference" held September 24-25, 1981, in Palo Alto. Much of the discussion at this conference centered around the uses of reference counting, garbage collecting, and method caches. The Smalltalk-80 system design separates storage management from the Virtual Machine specification. The various implementors were able to try out several storage management schemes, as well as several different approaches to reference counting. Source code management was also discussed, notably the solution of making source code bona fide Smalltalk objects in a virtual memory system, rather than trying to use external text files. Benchmarks for comparing system implementations were specified, and agreement was reached on writing a book on implementation considerations (that is, the book in which this chapter appears).

A fourth tape was later provided in order to distribute a Virtual Image that had been used for some time and in which many bugs had been fixed and some new features added. In particular, the fourth im-
age added a model interface to a file system. The image file was now 1011 records long. The implementors who had been successful in running the third tape were able simply to load and run this fourth tape, without any changes to their Virtual Machine implementation. The goal of distributing system releases as Virtual Images was thus reached and the review process terminated.

## Additional Collaborations

Prior to the delivery of the third image, an additional research license was given to the University of California at Berkeley in order to provide material for study by a graduate seminar on computer architecture (taught by Professors David Patterson, John Ousterhout, and Richard Fateman). The students in the seminar obtained an early version of the Hewlett-Packard implementation of the Smalltalk-80 Virtual Machine on which to run the Virtual Image provided by Xerox. After some initial use and study, the students wrote their own implementation in the C language for a VAX/780. The purpose in executing this license was to establish a close collaboration with a group of researchers experienced with the application of state-of-the-art hardware architecture technology to high-level programming languages.

Once the review process was completed, a special collaboration was formulated with the Fairchild Laboratory for Artificial Intelligence Research (FLAIR). Several implementations had been carried out on hardware systems consisting of an MC68000 processor, from which several clever ideas for improving the performance of the interpreter had been devised. The researchers at Xerox and FLAIR felt that by working together they could combine these clever ideas into a MC68000-based system with better performance than so far demonstrated. At the time that this chapter was written, this implementation project was still under way.

## A Final Word

The book review process, as envisioned by the research team, satisfied two needs: publication of research results, and setting a standard for a new form of personal computing. Publication took the form of written articles; the quantity of material and the integrated presentation of that material required a full book and a special issue of a magazine. The published system, however, was best appreciated in its dynamic form; publication was best served by distribution of the actual system software. Through this distribution, a shared system base has been created.
# The Evolution of the Smalltalk Virtual Machine

Daniel H. H. Ingalls

Software Concepts Group

Xerox Palo Alto Research Center

Palo Alto, California

## Introduction

In this paper we record some history from which the current design of the Smalltalk-80 Virtual Machine springs. Our work over the past decade follows a two- to four-year cycle that can be seen to parallel the scientific method and is shown in Fig. 2.1. The paper appears in two

<figure><img src="image_4.png" /><figcaption>Figure 2.1</figcaption></figure>
sections that are relatively independent of one another. The first section traces the evolution of the current design from the perspective of form following function. It follows the major implementation challenges and our solutions to them. The second section relates some of the methodology which evolved in pursuing this cycle of reincarnation. Readers who are less interested in the details of Smalltalk can skip to the second section and interpret our experience relative to other programming languages and systems.

## Form Follows Function

From the first Smalltalk interpreter to the definition of the Smalltalk-80 Virtual Machine, the Smalltalk language has been characterized by three principal attributes:

* Data stored as objects which are automatically deallocated,

* Processing effected by sending messages to objects,

* Behavior of objects described in classes.

In spite of other opinions to the contrary, we consider these to be the hallmarks of the "object-oriented" style of computing. In this section we shall trace the evolution of the underlying machinery which has supported language systems in this style over the last ten years. Some of the changes have augmented the power of the language, and some have increased its efficiency. Each change can be seen as an attempt to bring the underlying machinery more into harmony with the day-to-day demands of object-oriented programming.

The very first Smalltalk evaluator was a thousand-line BASIC program which first evaluated 3+4 in October 1972. It was followed in two months by a Nova assembly code implementation which became known as the Smalltalk-72 system¹.

Smalltalk-72

☐ **Storage Management** Objects were allocated from a linked list of free storage using a first-fit strategy. Objects which were no longer accessible were detected by reference-counting. They were then returned to the free storage list, with adjacent entries being automatically coalesced. Since pointers were direct memory addresses, compaction would have been complicated, and was not attempted. Contexts, the suspended stack frames, were managed specially as a stack growing down from high memory while normal allocation grew up from low memory. This separation reduced the tendency to leave "sandbars"
when returning values from deep calls, a problem in the absence of compaction.

□ Token Representation of Code All code was stored in a single tree made up of instances of Array (it was called Vector then), a variable-length array of pointers. The code in this tree represented a pattern description, similar to Meta. Fig. 2.2 presents the Smalltalk-72 definition of a class of dotted-pair objects, followed by a few examples of its use. Responses printed by the system are underlined.

<table><caption>Figure 2.2</caption><tr><td>to pair</td><td>to is the defining word, as in LOGO.</td></tr><tr><td>| head tail</td><td>| declares instance variable names.</td></tr><tr><td>(isnew &rarr;</td><td>isnew is true if an instance is just created.</td></tr><tr><td>(" head &larr; :: " tail &larr; :</td><td>" means literally the next token, here the names head and tail.</td></tr><tr><td>&lt; head &rarr;</td><td>&larr; is a message like any other.</td></tr><tr><td>(&lt; &larr; &rarr;</td><td>: fetches the next value from the incoming. message stream.</td></tr><tr><td>(" head &larr; :</td><td></td></tr><tr><td>&uarr; head)</td><td></td></tr><tr><td>&lt; tail &rarr;</td><td>&lt; matches the next literal token like the Smalltalk-80 message peekFor:</td></tr><tr><td>(&lt; &larr; &rarr;</td><td>false &rarr; (body) does nothing, but</td></tr><tr><td>(" tail &larr; :</td><td>true &rarr; (body) evaluates the body, and then leaves the outer scope.</td></tr><tr><td>&uarr; tail)</td><td>In this way several such constructs work as a CASE statement.</td></tr><tr><td>&lt; print &rarr;</td><td></td></tr><tr><td>(" [ print. head print. ": print.</td><td></td></tr><tr><td>tail print. "] print))</td><td></td></tr><tr><td>pair</td><td></td></tr><tr><td>" a &larr; pair 2 5</td><td>Here a pair is created, called a.</td></tr><tr><td>[2.5]</td><td></td></tr><tr><td>a tail &larr; pair 3 7</td><td>a gets its tail changed.</td></tr><tr><td>[2.[3.7]]</td><td></td></tr><tr><td>b tail head</td><td>a's tail ([3.7]) gets the message head.</td></tr><tr><td>3</td><td></td></tr></table>

The code was viewed by the interpreter as simply a stream of tokens. The first one encountered was looked up in the dynamic context, to determine the receiver of the subsequent message. The name lookup began with the class dictionary of the current activation. Failing there, it moved to the sender of that activation and so on up the sender chain. When a binding was finally found for the token, its value became the receiver of a new message, and the interpreter activated the code for that object's class.
In the new context, the interpreter would begin executing the receiver's code, matching it with the token stream which followed the original occurrence of the receiver. Various matching operators would select a route through the code which corresponded to the message pattern encountered. The matching vocabulary included matching a literal token, skipping a token, picking up a token literally, and picking up the value of a token. The latter operation invoked the same dynamic lookup described above for the receiver.

☐ **Classes** Most class properties were stored in a single dictionary. Instance variable names were denoted by a special code which included their offset in the instance. Class variables appeared in the same dictionary as normal name/value pairs. Another entry gave the size of instances, and another gave the "code" for the class. When a class was mentioned in code, it would automatically produce a new instance as a value. The unfortunate result of this special behavior was to make classes unable to be treated as ordinary objects.

☐ **Applications** Smalltalk-72 was ported to the Alto² as soon as the first machines were built, and it provided a stable environment for experimentation over the next few years. The Alto provided a large bitmap display and a pointing device, and thus made an ideal vehicle for working with graphical user interfaces.

Development of the Smalltalk-72 system began with Textframes and Turtles. Textframes provided text display with independent composition and clipping rectangles; Turtles gave us line drawing capability, modeled after Papert's experiments with turtle geometry³. In both cases, Smalltalk's ability to describe multiple instances added considerable leverage to these primitive capabilities. Soon many interesting and useful applications were written, including a mouse-driven program editor, a structured graphics editor, an animation system and a music system. Finally, Smalltalk-72 served as the basis for an experimental curriculum in object-oriented computing for high-school children⁴.

☐ **Shortcomings** The Smalltalk-72 system was used heavily by a dozen people for four years. The many practical applications gave us a lot of experience with the power of classes and the message-sending metaphor. In the course of this work, we also became increasingly aware of many limitations in the Smalltalk-72 system.

Dynamic lookup of tokens was both inefficient and unmodular. The dynamic lookup tempted some programmers to write functions which "knew" about their enclosing context. This code would then cause subtle errors when apparently innocent changes were made in the outer level.

Small
The message stream model was complicated and inefficient. One could not tell what a given piece of code meant in isolation. This became a problem as we attempted to build larger systems in which modularity was more of an issue. Also, a considerable amount of time was wasted on execution-time parsing (determining whether the result of a receiver expression should gobble the next token in the execution stream).

As mentioned above, classes were not first-class objects. Also, as our experience increased, we came to realize the need for inheritance. This was felt first in the commonality of behavior of Arrays, Strings, and sub-Arrays. For the time being, we referred to common functions from these similar classes so as to factor the behavior, but it was clear that some sort of inheritance mechanism was needed.

In 1974 we produced a major redesign of the Smalltalk interpreter with the aim of cleaning up its semantics and improving its performance. While the redesign was a mixed success, Smalltalk-74 was the site of several advances which fed into the later systems.

* **Message Stream Formalism** We succeeded in formalizing the operation of the interpreter, a step in the direction of simplicity and generality. For instance, we were able to provide a programmer-accessible object which represented the incoming message stream. Thus, not only could all the message stream operations be examined in Smalltalk, but the user could also define his own extensions to the message stream semantics. While this was a local success, it did not solve either of the real problems: token interpretation overhead, and non-modularity of receiver-dependent message parsing.

* **Message Dictionaries** Classes were given a message dictionary to allow primary message matching to be done by hashing. This did not do much for execution speed, since the previous interpreter had tight code for its linear scan, but it did help compilation a great deal since a single message could be recompiled without having to recompile all the code for the class. Unfortunately classes were still not able to be treated as normal objects.

* **BitBlt** Smalltalk-74 was the first Smalltalk to use BitBlt as its main operation for bitmap graphics. The specification for BitBlt arose out of earlier experience with Turtle graphics, text display, and other screen operations such as scrolling and menu overlays. Our specification of BitBlt has been used by others under the name RasterOp⁵. While the general operation was available to the Smalltalk programmer, much of the system graphics were still done in machine-coded primitives, owing to inadequate performance of the token interpreter.
☐ OOZE Smalltalk-74 was the system in which the OOZE ("Object-Oriented Zoned Environment")⁶ virtual memory was first implemented. OOZE provided uniform access to 65K objects, or roughly a million words of data. Smalltalk-74 served as the development environment for OOZE, so that when Smalltalk-76 was designed, OOZE was debugged and ready for use.

☐ Applications In addition to the previous applications which we had developed, Smalltalk-74 served as host to an information retrieval system and complete window-oriented display interface. Owing to the virtual memory support, it was possible to integrate many functions in a convenient and uniform user interface.

In 1976 we carried out a major redesign of the Smalltalk language and implementation⁷. It addressed most of the problems encountered in the previous four years of experience with Smalltalk:

* Classes and contexts became real objects;

* A class hierarchy provided inheritance;

* A simple yet flexible syntax for messages was introduced;

* The syntax eliminated message stream side-effects and could be compiled;

* A compact and efficient byte-encoded instruction set was introduced;

* A microcode emulator for this instruction set ran 4 to 100 times faster than previous Smalltalks; and

* OOZE provided storage for 65K objects—roughly the capacity of the Alto hardware.

The design for this system was completed in November of 1976 and seven months later the system was working. This included a full rewrite of all the system class definitions.

The Smalltalk-76 design stood the test of time well. It was used for four years by 20 people daily and 100 people occasionally. A large portion of the design survives unchanged in the Smalltalk-80 system. However, the Smalltalk-76 design did have some snags which we encountered during our four-year experience.

☐ Block Contexts Smalltalk-76 had to provide a mechanism for passing unevaluated code which was compatible with a compiled representation. A syntax was devised which used open-colon keywords for

Smalltalk-76

Experience with Smalltalk-76
passing unevaluated expressions (the semantics were the same as the
square bracket construct in the Smalltalk-80 language). This approach
was supported by block contexts which allowed executing code remote-
ly. Since the Smalltalk-76 design had no experience to draw from, it
was weak in several areas.

One problem which was discovered in the process of supporting error
recovery was that block contexts could not be restarted because they
did not include their initial PC as part of their state. This was not nor-
mally needed for looping, since all such code fragments ended with a
branch back to the beginning. Happily, we were able to fix this by de-
fining a new subclass.

Two other problems were discovered with remote contexts when
users began to store them as local procedures. For one thing, there was
no check in the interpreter to recover gracefully if such a piece of code
executed a return to sender after the originating context had already
returned. Also, the system could crash if remote contexts were made to
call one another recursively, since they depended on their home context
for stack space, rather than having their own stack space.

There were two other weaknesses with remote code. There was an
assymmetry due to use of open-colon keywords. For example one would
write

`newCursor showWhile: [someExpression]`

to cause a different cursor to appear during execution of
someExpression. But if the code contained a variable, *action*, which was
already bound to remote code, one wanted that variable to be passed di-
rectly, as with a closed-colon keyword. The only way to handle this
without needing a pair of messages with and without evaluation was to
write

`newCursor showWhile [action eval].`

This would do the right thing, but caused an extra remote evaluation
for every level at which this strategy was exercised. Besides being cost-
ly, it was just plain ugly.

Another weakness of remote contexts was that, while they acted
much like nullary functions, there was no way to extend the family to
functions which took arguments.

Finally, there was a question about variable scoping within remote
code blocks. Smalltalk-76 had no scoping, whereas most other languages
with blocks did.

All of these problems with RemoteContexts were addressed one way
or another in the Smalltalk-80 design.
☐ **Compilation Order** The Smalltalk-76 interpreter assumed that the receiver of a message would be on the top of the execution stack, with arguments below it. The number of arguments was not specified in the "send" instruction, but was determined from the method header after message lookup. From the designer's perspective this seemed natural; the only other reasonable choice would be for the receiver to lie underneath the arguments, as in the Smalltalk-80 system. In this case it seemed necessary to determine the number of arguments from the selector in order to find the receiver in the stack, and this looked both complex and costly to do at run time. There were two problems with having the receiver on the top of the stack. First the compiler had to save the code for the receiver while it put out the code for the arguments. This was no problem for three of the compilers which we built, but one particularly simple compiler design foundered on this detail. The second problem with post-evaluation of receivers was that the order of evaluation differed from the order of appearance in the code. Although one should not write Smalltalk code which depends on such ordering, it did happen occasionally, and programmers were confused by the Smalltalk-76 evaluation scheme.

☐ **Instruction Set Limitations** The Smalltalk-76 instruction set was originally limited to accessing 16 instance variables, 32 temps, and 48 literals. These limits were both a strain on applications and on the instruction set. A year later we added extended instructions which relieved these limits. This was important for applications, and it also took pressure off the future of the instruction set. With extended codes available, we had the flexibility to change the instruction set to better reflect measured usage patterns. For example we found that we could get rid of the (non-extended) instructions which accessed literals 33-48, because their usage was so low. Such measurements led us eventually to the present Smalltalk-80 instruction set.

☐ **Address Encoding** In OOZE, object pointers encoded class information in the high 9 bits of each pointer. This had the benefit of saving one word per object which would have been needed to point to the class of the object. In fact, it actually saved two words on many objects because classes contained the length of their instances. Variable length objects had separate class-parts for common lengths (0 through 8). However, the address encoding had several weaknesses. It squandered 128 pointers on each class, even though some never had more than a couple of instances. It also set a limit on the number of classes in the system (512). This did not turn out to be a problem, although an earlier limit of 128 did have to be changed. Finally, owing to the encoding, it was not possible to use object pointers as semantic indirection. For this reason, Smalltalk-76 could not support become: (mutation of objects through pointer indirection) as in later Smalltalks.

Experience with
OOZE
☐ **Capacity** While the OOZE limitation of 65K objects is small by today's standards, it served well on the Alto. The Alto has a 2.5 megabyte disk, and with a mean object size of 16 words, OOZE was well matched to this device.

☐ **Interpreter Overhead** OOZE had a couple of weaknesses in the area of performance, which only became significant after our appetites had increased from several years' experience. One was that the object table required at least one hash probe for every object access, even just to touch a reference count. Another was a design flaw in the management of free storage which required going to the disk to create a new temporary object if its pointer had been previously placed on a free list. We designed a solution to both of these problems. Temporary objects would be treated specially with pointers which were direct indexes into their object table. Freelists would only be consulted when an object "mailed" and needed a permanent pointer assigned. Because temporary objects account for many accesses, much of the overhead of probing the permanent object table would be eliminated. Since Smalltalk-76's days seemed numbered, we did not take the time to implement this solution.

Efficiency and
Portability:
Smalltalk-78

In 1977 we began a project to build a portable computer capable of running the Smalltalk system. Known internally as NoteTaker, it began as a hand-held device for taking notes, but ended up as a suitcase-sized Smalltalk machine. Several factors converged to define this project. We wanted to be able to bring Smalltalk to conferences and meetings to break through the abstractions of verbal presentations. With the Intel 8086 and other 16-bit microprocessors (the Z8000 and MC68000 were coming, but not available yet), we felt that enough computing power would be available to support Smalltalk, even without microcode. Finally, portability seemed to be an essential ingredient for exploring the full potential of personal computing.

The design challenge was significant. We were moving to an environment with less processing power, and the whole system had to fit in 1/4 Mbyte, since there was no swapping medium. Also we faced transporting 32K bytes of machine code which made up the Smalltalk-76 system, and it seemed a shame not to learn something in the process. The result of these forces was the design of Smalltalk-78.

☐ **Cloned Implementation** The Smalltalk-78 implementation was significant in that it was not built from scratch. We were happy enough with the basic model that we transported the entire Smalltalk level of the system from Smalltalk-76. In order to do this, we used the system tracer (see p. 24) which could write a clone of the entire system onto an image file. This file could then be loaded and executed by the Smalltalk-78 interpreter. The tracer had provisions in it for transmut-
<figure><img src="image_5.png" /><figcaption>Figure 2.3</figcaption></figure>

ing object formats as necessary, and even for changing the instruction set used in the methods.

☐ **Indexed OT** The Smalltalk-78 design centered around an indexed object table, which is the same design as in the Smalltalk-80 system. This greatly simplified object access and yet retained the indirection which made for easy storage management in Smalltalk-76. Reference counts were stored as one byte of the 4-byte table entry. Given an object pointer in a register, a reference count could be incremented or decremented with a single add-byte instruction with an overflow check.

☐ **Small Integers** Since there would not be room in core for more than 10K objects or so, it was possible to encode small integers (-16384 to 16383) in part of the pointer space. Since object table indices would all be even (on the 8086, they were multiples of 4), we encoded small integers as two's complement integers in the high-order 15 bits, with the low-order bit turned on. With this design, allocation of integer results was trivial, integer literals could be stored efficiently, and integer values did not need to be reference counted.

☐ **In-line Contexts** In order to save time allocating new contexts, and to take advantage of the stack-oriented instructions available in most microprocessors, the representation of contexts was redesigned. Instead of having a separate object for each context, a large object was allocated for each process, in which contexts could be represented as conventional
stack frames. This special representation complicated the handling of
blocks and the debugger, requiring an interface which referred to the
process and an offset within the process.

In addition to reduced allocation time, the time to transfer argu-
ments was eliminated by allowing the contexts to overlap; the top of
one context's stack (receiver and arguments) was the base of the next
context's frame.

□ *Reduced Kernel—The Leverage of BitBlt*
We have always sought to reduce the size of the Smalltalk kernel. This is not only an aesthetic desideratum; kernel code is inaccessible to the normal user, and we have always tried to minimize the parts of our system which can not be examined and altered by the curious user. In this particular case, we were also moving to a new machine. While writing a certain amount of machine code seemed inevitable, we did not relish the idea of transcribing all 32K bytes of code which comprised the Smalltalk-76 kernel. Fortunately, much of that bulk consisted of various routines to compose and display text, to draw lines and implement Turtle geometry, and to provide various interfaces to bitmap graphics such as moving rectangles, and copying bits to buffers as for restoring the background under menus.

The definition of BitBlt grew out of our experience with text, lines and other bitmap graphics. Now the constraints of the NoteTaker implementation provided the motivation to implement all these capabilities in Smalltalk, leaving only the one primitive BitBlt operation in the kernel. This was a great success in reducing the size of the kernel. The full NoteTaker kernel consisted of around 6K bytes of 8086 code. This figure did not include Ethernet support, real-time clock, nor any significant support for process scheduling.

□ *Performance*
The performance of the NoteTaker was interesting to compare with the Alto. The Smalltalk instruction rate improved by a factor of two, and yet the display of text was much slower (being in Smalltalk, rather than machine code). By adding a small primitive for the inner loop of text display and line drawing, this decrease was largely compensated. User response for such actions as compiling was significantly improved, owing to the faster execution and to the freedom from the swapping delays of OOZE.

□ *Mutability*
Smalltalk-78 used no encoding of object pointers other than for small integers. Class pointers and length fields (for variable-length objects) were stored just as any other fields. It was therefore possible in this design to allow mutation of objects, and this was made available as the primitive method for become:.
# The Evolution of the Smalltalk Virtual Machine

□ **Relevance** We learned a great deal from the NoteTaker challenge, even though only 10 prototypes were built. We made the system much more portable, and had demonstrated that the new generation of microprocessors could indeed support Smalltalk. The decision not to continue the project added motivation to release Smalltalk widely.

## TinyTalk

At the same time as the NoteTaker implementation, we performed an experiment⁸ to see if a very simple implementation could run on a conventional microprocessor such as a Z80 or 6502. This implementation used marking garbage collection instead of reference-counting, and was able to use simple push and pop operations on the stack as a result. A method cache largely eliminated the overhead in message lookup and, since primitive codes were included in the cache, access to primitives was fast. The system did actually fit in 64K bytes with a little bit of room to spare. Another experiment which was done in conjunction with this implementation was to demonstrate that a special case of BitBlt for characters could run much faster than the general version.

## Smalltalk-80

With Smalltalk-78 behind us, few changes were made to the Virtual Machine to produce the Smalltalk-80 Virtual Machine. The main change was an increase in power from allowing blocks with arguments. Beyond this, mostly we cleaned up many details, some of which supported more extensive cleanups in the Smalltalk level of the system.

□ **Contexts Again** We felt that the optimized contexts of Smalltalk-78 did not justify the loss in clarity which they entailed. So in the Smalltalk-80 language we reverted to Contexts as objects, leaving such optimizations up to implementors clever enough to hide their tricks entirely from Smalltalk. In order to simplify the management of Contexts in the Virtual Machine, we decided to use two sizes of contexts instead of making them truly variable-length. This meant that, if separate free lists were managed for these two lengths, storage for contexts could be allocated and freed with relatively little fragmentation and coalescence overhead.

□ **Blocks with Arguments** While the syntax changed little in the Smalltalk-80 language (open colon and other non-ASCII selectors were banished), our extended discussions of syntax led to the current description for blocks with arguments. In fact, this required no change to the Virtual Machine, but it had the feel of such a change in the language.

□ **BlockContexts** We re-engineered BlockContexts in the Smalltalk-80 language. Smalltalk-78 had already handled their recursive application by providing independent stack space for each invocation. Beyond this, mechanisms were defined for checking and diagnosing such anomalous conditions as returning to a context which has already returned.
☐ **Compilation Order** Smalltalk-78 had perpetuated the post-evaluation of receiver expressions so as to avoid delving into the stack to find the receiver. In the Smalltalk-80 language, however, we encoded the number of arguments in the send instruction. This enabled strictly left-to-right evaluation, and no one has since complained about surprising order of evaluation. We suspect that this change will yield further fruit in the future when someone tries to build a very simple compiler.

☐ **Instruction Set** In addition to revamping the send instructions, we made several other improvements to the instruction set. We completed the branch instructions by adding branch-if-true. We put in 2- and 3-byte extensions to retain reasonable compactness without restricting functionality. We also added a few compact codes for returning true and false, and for pop-and-store into temps and fields of the receiver.

☐ **Methods** The encoding of method headers followed the earlier Smalltalk-78 design. In order to simplify the allocation of contexts, a bit was included to indicate whether a large frame was necessary to run the method or not.

## Future Directions

While the present Smalltalk design has evolved over a decade now, that does not mean it is finished. As when one climbs a large mountain, the higher reaches are gradually revealed and it seems there is as much to do now as when we started.

☐ **Virtual Memory** An obvious shortcoming of the Smalltalk-80 specification is that it does not include a virtual memory. There are several reasons for this. Our experience with OOZE suggested that object-oriented approaches might be significantly better than simple paging, and we did not want to commit ourselves to one or the other. From our experience with porting the system from one interpreter to another, it was clear to us that implementors could experiment with the virtual memory issue fairly easily, while still working from the Smalltalk-80 image specification. The current object formats allow a simple resident implementation, and yet lend themselves to extension in most of the obvious directions for virtual memory.

☐ **Reducing Concepts** It is always useful to reduce the number of concepts in a language when possible. Smalltalk distinguishes many levels of refinement: subclassing, instantiation, blocks and contexts, to name a few. It is likely that some of these distinctions can be dissolved, and that a cleaner virtual machine design would result.

☐ **Typing and Protocols** While the Smalltalk-80 language is not a typed language in the normal sense, there is nonetheless an implicit notion of variable type in the protocol (full set) of messages which must be
understood by a given variable. We have described an experimental system based on this notion of type⁹, and a serious treatment of this approach would likely involve changes to the Virtual Machine.

☐ *Multiple Inheritance* While the Smalltalk-80 system does not provide for multiple inheritance, we have described an experimental system which supports multiple superclasses using the standard Virtual Machine¹⁰. This is another area in which serious use of the new paradigm might suggest useful changes to the Virtual Machine.

☐ *Tiny Implementations* While, on one end of the spectrum, we seek to build vastly larger systems, we should not ignore the role of small systems. To this end, there is a great deal of room for experimentation with small systems that provide the essential behavior of the Smalltalk-80 system. Threaded interpreters offer simplicity and speed, and it shouldn't be difficult to capture the essence of message sending in an efficient manner.

## Maintaining an Evolving Integrated System

We have had considerable experience maintaining an evolving integrated system. In this section we cover several of the challenges and our solutions which support the Smalltalk approach to software engineering.

### *Applying the Smalltalk Philosophy*

One way of stating the Smalltalk philosophy is to "choose a small number of general principles and apply them uniformly." This approach has somewhat of a recursive thrust, for it implies that once you've built something, you ought to be using it whenever possible. For instance, the conventional approach to altering such kernel code as the text editor of a programming system is to use off-line editing tools and then reload the system with the new code and try it out. By contrast, Smalltalk's incremental compilation and accessibility of kernel code encourages you to make the change while the system is running, a bit like performing an appendectomy on yourself.

The recursive approach offers significant advantages, but it also poses its own special problems. One of the benefits is that system maintainers are always using the system, so they are highly motivated to produce quality. Another benefit is high productivity, deriving from the elimination of conventional loading and system generation cycles. Consistent with the Smalltalk philosophy as articulated above, things are
also simpler; the tools and the task are one, so there are fewer versions to worry about. The complementary side of this characteristic is that if the only version is compromised, you are "down the creek without a paddle."

<figure><img src="image_6.png" /><figcaption>Figure 2.4</figcaption></figure>

The Snapshot
Concept

The Alto had a particularly nice characteristic as a personal machine: being based on a removable disk pack, once you had installed your personal pack, any machine you used behaved as your personal machine. When we built the Smalltalk environment, based on an extensible programming language, we arranged the system so that when you terminated a working session, or *quit*, the entire state of your system was saved as a *snapshot* on the disk. This meant that as Smalltalk came to be a stand-alone environment, containing all the capabilities of most operating systems as well as the personal extensions of its owner, any Alto instantly took on that specialized power as soon as you inserted your disk and *resumed* your working session. The snapshot also served as a useful checkpoint in case of fatal errors.

In the later virtual memory systems, OOZE automatically saved a snapshot from time to time, which could subsequently be resumed following catastrophes such as loss of power or fatal programming errors. The robustness of OOZE in this respect was remarkable, but owing to the finite latency period of the checkpointing process, it was necessary to act quickly when fatal errors were recognized, lest they be enshrined forever in the mausoleum of a snapshot. In such circumstances, the alert user would quickly reach around to the rear of the keyboard and press the "boot" button of the Alto before the next automatic snapshot.
Then he could resume his work from a previous state saved a few minutes before. This process was known as "booting and resuming." The term came to be jokingly applied to other situations in life, such as unsuccessful research efforts and other less serious endeavors.

*Minimum Kernel for Maximum Flexibility*

Most systems are built around a kernel of code which cannot easily be changed. In our Smalltalk systems, the kernel consists of machine code and microcode necessary to implement a virtual Smalltalk machine. You clearly want the kernel to be as small as possible, so that you encounter barriers to change as infrequently as possible. For example, in Smalltalk-72 it was a great improvement when the primitive read routine was supplanted by one written in Smalltalk, since it could then be easily changed to handle such extensions as floating-point constants.

Speed comes into play here, because if the kernel is not fast enough, it will not support certain functions being implemented at a higher level. This was the case for text display in Smalltalk-76. Similarly, generality is important, for the more general the kernel is, the more kernel-like functions can be built at a higher level. For example, the one BitBlt primitive in Smalltalk-80 supports line drawing, text, menus and freehand graphics.

*The Fear of Standing Alone*

While Smalltalk-72 and -74 were used as long-lived evolving images, the systems as released were always generated from scratch, by reading a set of system definitions into a bootstrap kernel. With the Smalltalk-76 system, we took a bold step and opted to ignore support for system generation. The system was built in two parts: a Virtual Machine was written in microcode and machine code, and a virtual image was cross-compiled from a simulation done in Smalltalk-74. Although this paralleled our previous strategy, we knew that we would soon abandon support for Smalltalk-74, and thus the Smalltalk-76 system would be truly stand-alone. In other words, if a bit were dropped from the system image, or if a reference-count error occurred, there would be no way to recover the state of the system except to backtrack through whatever earlier versions of the system had been saved. As the system became more reliable, we went for days and then weeks without starting over, and finally we realized that Smalltalk-76 was on its own. If this sounds risky to you, think of how we felt!

*Standing Alone Without Fear: The System Tracer*

While the foregoing approach may seem foolhardy, we actually had a plan: Ted Kaehler said that he would write a Smalltalk program, the *system tracer*, which would run inside of Smalltalk and copy the whole system out to a file while it was running. Considerable attention would have to be paid to the parts of the system which were changing while the process ran. Two months after the launch of Smalltalk-76, Ted's first system tracer ran and produced a clone without errors. While we
<figure><img src="image_7.png" /><figcaption>Figure 2.5</figcaption></figure>

all breathed a sigh of relief at this point, the full implications only dawned on us gradually. This truly marked the beginning of an era: there are many bits in the Smalltalk-80 release of today which are copies of those bits first cloned in 1977.

The system tracer solved our most immediate problem of ensuring the integrity of the system. It caught and diagnosed inaccurate reference counts, of which there were several during the first few months of Smalltalk-76. Also, although it took four hours to run, it performed the function of a garbage collector, reclaiming storage tied up in circular structures, and reclaiming pointers lost to OOZE's zoning by class. The essential contribution of the system tracer, however, was to validate our test-pilot philosophy of living in the system we worked on. From this point on, we never started from scratch again, but were able to use the system we knew so well in order to design its follow-ons.
<figure><img src="image_8.png" /><figcaption>Figure 2.6</figcaption></figure>

Spawning and
Mutation

As time passed we found that the system tracer had even more potential than we had imagined. For one thing, it offered an answer to the problem of using a fully integrated system for production applications. This problem manifests itself in several ways: a fully integrated system contains many components which are not needed in production, such as compiler, debugger, and various editing and communications facilities. Also, at a finer grain, much of the symbolic information which is retained for ease of access may be wasteful, or even objectionable (for security reasons) in a production release of the system.

The system tracer could be instructed to spawn an application with all unnecessary information removed. This could be done post facto, thus freeing application programmers from the integrated/production dichotomy until the final release of a product. In actual fact, since the goal of our research is integration, we never pursued the full potential of the system tracer to drop out such "product" applications. The closest we came was to eliminate unnecessary parts of the system when we were short of space for certain large projects.

The possibility of using the system tracer to produce mutations became evident soon after its creation, and we took full advantage of this. For instance, prior to the Smalltalk-80 release, we wanted to convert from our own private form of floating-point numbers to the standard IEEE format. In this case, we simply included an appropriate transformation in the system tracer and wrote out a cloned image which used the new format. Then we replaced the floating-point routines in the Virtual Machine and started up the new image. Similar transformations have been used to change the instruction set of the Virtual Machine, to change the format of compiled methods, and to change the encoding of small integers. It was in this manner that Smalltalk-78 and -80 were built out of Smalltalk-76.
It is hard to say how far one should take this approach. Sometimes a change is so fundamental that it requires starting again from the ground up, as we did from Smalltalk-74 to -76. Even in such cases though, it seems easiest to simulate the new environment in the old, and then use the simulation to produce the actual new system.

<figure><img src="image_9.png" /><figcaption>Figure 2.7</figcaption></figure>

The Virtual Image

When we decided to release the Smalltalk-80 system, the question arose as to what form it should take. From the discussion above, it should be clear why we chose the virtual image (a fancier term for snapshot) format. This was the one way in which we could be sure that the release would set a standard. Any implementation, if it worked at all, would look and behave identically, at least in its initial version. At the same time, we tried to decouple the image format as much as possible from such implementation-related details as reference counting versus garbage collection, machine word size, and pointer size. At the time of this writing, implementations exist which vary in all of these parameters. It should be possible to decouple similarly our choice of bitmap display representation, but this project was not of immediate interest to us.

Conclusion

The evolution of the Smalltalk system is a story of good and bad designs alike. We have learned much from our experiences. Probably the greatest factor that keeps us moving forward is that we use the system all the time, and we keep trying to do new things with it. It is this "liv-
ing-with" which drives us to root out failures, to clean up inconsistencies, and which inspires our occasional innovation.

References

1. Goldberg, Adele, and Kay, Alan, Eds., "Smalltalk-72 Instruction Manual", Xerox PARC Technical Report SSL-76-6, 1976.

2. Thacker, C. P., et al., "Alto: A Personal Computer", in *Computer Structures: Readings and Examples*, 2nd Edition, Eds. Sieworek, Bell, and Newell, McGraw-Hill, New York, 1981; (also Xerox PARC CSL-79-11), Aug. 1979.

3. Papert, Seymour, *Mindstorms*, Basic Books, New York, 1980.

4. Goldberg, Adele, and Kay, Alan, "Teaching Smalltalk", Xerox PARC Technical Report SSL-77-2, June 1977.

5. Newman, William, and Sproull, Robert, Principles of Interactive Computer Graphics, 2nd Edition, McGraw-Hill, New York, 1979.

6. Kaehler, Ted, "Virtual Memory for an Object-Oriented Language", *Byte*, vol. 6, no. 8, Aug. 1981.

7. Ingalls, Daniel H. H., "The Smalltalk-76 Programming System: Design and Implementation", Conference Record, Fifth Annual ACM Symposium on Principles of Programming Languages, 1978.

8. McCall, Kim, "TinyTalk, a Subset of Smalltalk-76 for 64KB Microcomputers", *Sigsmall Newsletter*, Sept. 1980.

9. Borning, Alan H., and Ingalls, Daniel H. H., "A Type Declaration and Inference System for Smalltalk", Ninth Symposium on Principles of Programming Languages, pp. 133-141, Albuquerque, NM, 1982.

10. ______________, "Multiple Inheritance in Smalltalk-80", pp. 234-237, Proceedings at the National Conference on Artificial Intelligence, Pittsburgh, PA, 1982.
# The Smalltalk-80 Code File Format

Glenn Krasner

Software Concepts Group
Xerox Palo Alto Research Center
Palo Alto, California

## Introduction

In the Smalltalk-80 system, programmers define classes and methods incrementally by editing in system browsers. At some point, programmers may want to share their class descriptions with others using different Smalltalk-80 systems. Some means of communication is therefore required. We have chosen to use files as the means of communication, and call such files *code files*.

Code files for the Smalltalk-80 system allow the programmer to communicate source code (class descriptions or parts of class descriptions) between one Smalltalk-80 system and another (possibly the same system, later in time). The format of such files was devised as a result of a number of design considerations:

* Restrictions on the allowable character set,

* Whether to allow the code to be "readable" when printed on conventional printers,

* Whether to retain/allow more than one emphasis of the text (font and face changes),

* Whether to include source code in the system image (core) or to place it on external files,

Copyright © Xerox Corporation 1982. All rights reserved.
* Whether to allow for executable expressions in addition to source code of methods, and

* Whether to provide for system crash recovery.

The Smalltalk-80 code file format is restricted to contain a common set of characters ("printing" ASCII characters plus a small number of control characters). It gives up the ability to have multiple emphases of text in order to be as good (or as bad) on conventional printers as it would be on more capable printers (raster laser xerographic printers, for example). The approach taken keeps source methods on file storage to minimize the amount of core used, includes intermingling of executable expressions with source code for methods, and provides for some amount of system recovery.

## Background

The Smalltalk-80 system is powerful and comprehensible, in part because everything in the system is treated in a uniform way, as an object. However, at the point where the Smalltalk-80 system meets the external world, this uniformity cannot be maintained. The external world does not consist of Smalltalk-80 objects, but rather of disk files, network communication, hardware storage devices, and printers. These define a much more limited structure of information. For example, disk files typically consist of collections of 8-bit bytes; networks define a limited set of data that can be communicated; hardware storage devices define what kinds and, more importantly, how much information can be handled; and printers typically are restricted to a small number of characters as the only data they can handle. If the Smalltalk-80 programmer never had to meet this external world, there would be no problem. Everything he or she dealt with would be within the Smalltalk-80 system. For some programmers, this is sufficient. Most programmers, however, must meet the external world because they want to share information with some other system. The Smalltalk-80 code file format is a format for representing code objects (i.e., source code for methods or expressions), especially for communication via the media of electronic secondary storage and paper.

## Constraints and Goals

The constraints and goals for the design of the format consisted of:

* Having a format that would serve as a communications protocol among Smalltalk-80 systems and from a system to paper. We saw
the paper version as being used by people not fortunate enough to have display-based browsers and, perhaps more importantly, as one in which algorithms or pieces of code could be published.

* Having a format that could be printed without translation on conventional printers. We are interested in first having the world build Smalltalk engines, with bit-map displays and good pointing devices and lots of computing power. Later, we expect them to want to use good printers; we are willing to wait before we require them to do so.

* Having a format that would look satisfactory on paper. Often this means allowing multiple font and type face information, as well as formatting information. However, given the first goals, it means not having extra characters that describe such information cluttering up the printed page.

* Having the source code for the more than 4000 methods in the system take up as little main memory as possible. We expect that reasonable Smalltalk-80 machines will have virtual memories, where space restrictions would not be a problem. However, the number of bytes taken up by the source code alone (more than a million) would preclude most current machines from having *any* resident implementation. Therefore the file format was to serve as a somewhat limited form of virtual memory.

* Having a format that would include executable expressions. Typically what people want to communicate between systems includes method definitions, class descriptions, and class initialization expressions. By providing for executable expressions, all these desires can be met.

* Minimizing the amount of disk space taken up. For example, one would not want an entire disk system to become full of text when only a small percentage of the text is actually needed.

* Allowing a certain amount of recovery from system disasters. The Smalltalk-80 system is one in which it is possible to change almost anything. This provides great power and flexibility, but has the danger that a system change could destroy the system itself. It was desired that code files, since they are somewhat external to the system itself, could provide recovery from such disasters.

## The Code File Format

Smalltalk-80 code files are defined as text files that contain only the "printing" ASCII characters, codes 32 (space) through 127 (DEL), plus carriage return, line feed, tab and form feed (codes 13, 10, 9 and 12, re-
respectively). The file is broken into *chunks*, which are sequences of characters terminated by an exclamation point (!), with exclamation points within a chunk doubled. The meanings of chunks will be described in the sections to follow.

Exclamation point was chosen for a number of reasons. It is not used as a Smalltalk-80 selector. It is used in English at the end of sentences, so it is a reasonable terminator. It tends not to appear in code, so it rarely has to be doubled. Also, it is thin, so we felt it would not be too obtrusive on the page.

## File Streams

The interface between Smalltalk-80 objects and disk files is encapsulated by the Smalltalk-80 classFE propriate and random access of disk files through the following protocol

<table><tr><td>class name</td><td>FE</td></tr><tr><td>superclass</td><td>ExternalStream</td></tr></table>

### opening and closing

**openOn: aString**

Answer an instance ofFE representing the disk file named aString.

**close**

Close the file.

### sequential accessing

**next**

Answer the character in the file after the current position, and update the position.

**nextPut: aCharacter**

Store aCharacter as the character of the file after the current position, and update the position.

**atEnd**

Answer true if the current position is at the end of the file, false if it is not.

**setToEnd**

Set the current position to be the end of the file.

### random accessing

**position**

Answer the current position.

**position: anInteger**

Set the current position to be anInteger.

Two messages were added toFE to deal with chunks, one to read a chunk from the file, and another to write a chunk onto the file
## fileln/Out

### nextChunk

Answer a string that is the chunk starting at the current position, undoubling embedded exclamation points, and excluding the terminator.

### nextChunkPut: aString

Write aString as a chunk starting at the current position, doubling embedded exclamation points, and terminating it with an exclamation point.

## Code Files Used for Source Methods

The Smalltalk-80 system relies on the code file format to read and write the source methods of the system. In this way, the files are used to communicate information from the system to itself at a later point in time. Each CompiledMethod in the system keeps a short (3-byte) encoding of the location of its source. This encoding includes which of four file streams contains the chunk of source code for that method and the position, within that file, of the first character of its chunk. A global array called SourceFiles points to the four file streams.

The code for getting the source method in class CompiledMethod could be*

###attiSource

| sourceIndex sourceFile sourcePosition |

sourceIndex -> self sourceIndex.

sourceFile -> SourceFiles at: sourceIndex.

sourcePosition -> self sourcePosition.

sourceFile position: sourcePosition.

↑sourceFile nextChunk

Of the four file streams, one, SourceFiles at: 1, is a read-only file stream of source methods. It is known as the *sources file*. Periodically all the source code of the system may be condensed into this file.

The second file stream, SourceFiles at: 2, is a file stream to which every change to the system sources is appended. It is known as the *changes file*. When a method is changed and recompiled, its new source code is appended to this file (and the encoding bytes of the CompiledMethod are changed to point at the new source). Periodically, the changes file may be condensed as well. Since this file grows while a programmer is working, the changes file may want to be condensed much more often than the sources file. The third and fourth file streams are currently unused.

<footnote>*For implementation efficiency, the code in the Smalltalk-80 system is not actually this, but provides the same function.</footnote>
The code in class CompiledMethodto store a new source code string could be

storeSourceString: aString

| sourceFile sourcePosition |
sourceFile - SourceFiles at: 2.
sourceFile setToEnd.
sourcePosition - sourceFile position.
self setSourceIndex: 2
sourcePosition: sourcePosition.
sourceFile nextChunkPut: aString.

Because the changes file is only altered by appending to it, previous versions can always be found. Periodically, a Smalltalk-80 programmer will make a snapshot of the state of the system. If the system crashes at a later time, then, when the system is resumed at the point of snapshot, the compiled methods in the snapshot of the system will still point to their place in the files at the time the snapshot was made. The end of the file will contain changes added between the snapshot and the crash, and these can be recovered. For example, suppose a programmer changed the definition of主义Source in class CompiledMethod once (version A), then made a snapshot, then changed it twice (versions B and C), and the system crashed because of an error in C. Then the system can be restarted at the snapshot point, the source and compiled method for主义Source will be version A, but versions B and C will be near the end of the changes file. The programmer could look at the end of the changes file, copy version B into the browser for compilation, and ignore C. Then the programmer has recovered to the equivalent of just before the C change brought down the system.

To improve recovery, the system also records several other things on
the changes file. For example, whenever the user executes an expres-
sion in a code editor, the expression is appended as a chunk on the
changes file. Also, when the user performs a system snapshot, a chunk
consisting of the comment "---SNAPSHOT---" is appended to the
changes file, marking the occurrence of a snapshot.

Code Files
Used for
Shared Code

Besides storing the system sources, the code file format serves to com-
municate code and expressions between one system and another. For
this we have added a level of syntax and semantics above the chunk
level. The syntax and semantics are defined and implemented by the
message fileln in class FileStream,
### fileIn

```java
| aString sawExclamation |
self position: 0.
[self atEnd]
whileFalse:
    [sawExclamation -> self peekFor: $!.
     aString -> self nextChunk.
     sawExclamation
      ifFalse: [Compiler evaluate: aString]
      ifTrue: [(Compiler evaluate: aString) fileInFrom: self]]
```

### peekFor: aCharacter

```java
"Answer true and move past if next = aCharacter"
self next = aCharacter
ifTrue: [^true]
ifFalse: [self position: self position - 1. ^false]
```

That is, when sent the message fileIn, a file stream looks for an exclamation point. As long as it does not see one, it reads and has class Compiler evaluate the next chunk as a Smalltalk-80 expression. If it did see an exclamation point, then after the expression is evaluated, it hands the stream (itself) to the object that was returned as the value of the expression (see example below).

In particular, the methodsFor: aString message sent to a class will return an instance of ClassCategoryReader that has its instance variable myClass set to the class, and its instance variable myCategory set to the string. The class category reader will respond to the fileInFrom: message by reading chunks from the file stream. Each chunk is presumed to be the source for a method, and, for each chunk, the class category reader has the compiler compile it and install the compiled method in the proper class and category. This continues until an empty chunk is found.

### fileInFrom: aFileStream

```java
| aString |
[aFileStream atEnd or: [(aString -> aFileStream nextChunk) empty]]
whileFalse:
    [Compiler compile: aString
       forClass: myClass
       inCategory: myCategory]
^self
```

For example, the code for fileIn, peekFor: aCharacter, and fileInFrom: aFileStream would appear in a code file as
```java
!FileStream methodsFor: 'filel/O'!
fileln
| aString sawExclamation |
self position: 0.
[self atEnd]
whileFalse:
    [sawExclamation ← self peekFor: $!!
     aString ← self nextChunk.
     sawExclamation
        ifFalse: [Compiler evaluate: aString]
        ifTrue: [(Compiler evaluate: aString) filelnFrom: self]]
    peekFor: aCharacter
    "Answer true and move past if next = aCharacter"
self next = aCharacter
    ifTrue: [↑true]
    ifFalse: [self position: self position - 1. ↑false]!!

!ClassCategoryReader methodsFor: 'filel/O'!
filelnFrom: aFileStream
| aString |
[aFileStream atEnd or: [(aString ← aFileStream nextChunk) empty]]
whileFalse:
    [Compiler compile: aString
     forClass: myClass
     inCategory: myCategory]
↑self!!
```

The class category reader created by the expressionindeStream methodsFor: 'filel/O' will read and compile the methods for fileln and peekFor: aCharacter before returning control to the file stream; the reader created by ClassCategoryReader methodsFor: 'filel/O' will read in only the method for filelnFrom: aFileStream.

The example shows a number of visual properties that make it easier to read code format files when they are printed. Each category is delimited by a short "methodsFor:" line; it is easy to locate the names of the class and the category for each. Each method is a visual chunk with all but its first line indented. This of course, depends on the programmer keeping the convention of including a tab before each line other than the message pattern. This convention is supported by the "format" command in the code editor.

In addition to the source code for methods, the code file format and its interpretation allow any expression to be saved on a file. In particular, one may save an entire class description from a Smalltalk-80 system. That file will consist of an expression defining the class, followed by an expression setting the global comment of the class, followed by
the source code for the methods in the class, in the format described above. When a file stream on such a file, in this or some other system, is told to fileln, it will recreate the entire class description.

Users could also define their own "readers," objects created with expressions preceded by an exclamation point, just as ClassCategoryReaders are created with the "methodsFor:" expressions. These user-defined readers would be used for creating an object with special external representation, just as class category readers create methods whose external representations are strings of characters formatted for readability.

Note: In addition to this, since many classes have initialization code especially for class variables, if the message initialize is defined in the class, the expression chunk `<class> initialize!` will appear at the end of the file containing the class definition. Then, when the file is told to file in, the initialization code will be executed after the methods are compiled.

## Code File Format for Both Source Methods and Shared Code

The conventions for shared code given in the previous section are also followed in the two source code files. That is, the sources file is organized as a sequence of class descriptions in the above format, arranged alphabetically by class name, with form feeds between them. The compiled methods in the system point to the beginning of their chunks. In this way, printing out the sources file will give an alphabetical listing of the system sources with page breaks between each class.

The changes file is a collection of chunks of the form

```
! <class name> methodsFor: '<categoryName>' !
<source method> !!
```

The compiled methods in the system that point to the changes file also only point to the beginning of their chunks. The chunks appended to the changes file when the user evaluates an expression are in the executable form

`<expression>!`

This means that the sources file could be filed in to redefine the system classes to their state before changes were made, and the changes file could be filed in to redefine the changes and re-execute the expressions made since changes were started. The Smalltalk-80 system provides two ways of looking at the changes file for recovery, to create a view on a file whose contents are the last few thousand characters of the changes file and to create a ChangeList browser to view the changes.
## Matching the Goals and Constraints

The Smalltalk-80 code file format meets most of the goals and satisfies most of the constraints of its design. It serves as a communications format between systems. It is used extensively, not only for source code within a system, but also for exchanging source code between systems. In addition, because it is restricted to the standard ASCII character set, it can be printed on conventional printers as well as on more capable printers.

The code files have a reasonable appearance on paper. Of course, this is a matter of taste. In a few years we will likely no longer consider its appearance reasonable because our opinions of "reasonable appearance" will change. Methods are "chunked" together, and the "methodsFor:" lines separate categories of methods. Except for the single exclamation point at the end of each method, there are no characters to distract the reader. The form feeds between class descriptions also help the readability of the code.

The amount of main memory required to handle sources is quite small, especially compared with the size of the source code itself. It requires only 3 bytes per compiled method, plus the space taken up by the interpretation code (outlined in this paper). Compared with over a million bytes of source code, this is a great savings and considered worth the added complexity.

The format includes executable expressions. The system currently uses this feature sparingly—for class descriptions and initialization, and for recording expressions evaluated by the user. However, the format provides a generality that can be exploited in the future.

Disk space efficiency is a compromise in our design. Having one read-only sources file does help meet this goal since multiple systems can share this file. At Xerox, we often keep this shared file on a remote server, where multiple systems can access it and where it does not take up any local disk space. On the other hand, constantly appending to the changes file consumes disk space. The Smalltalk-80 development style often involves defining and redefining methods many times. Since each definition is appended to the changes file, this causes the file to grow. However, the user can invoke the system's ability to compact the changes file at any time by sending the message `compactChanges` to Smalltalk, an instance of `SystemDictionary`.

Although using the changes file in this way is wasteful of disk storage, there is the advantage that a considerable amount of recovery from system crashes is possible. By recording all code changes and many other user events on the changes file, the programmer can recover should the system go down. In particular, if a programmer is experimenting with the user interface code and makes a mistake that renders the interface unusable, there will be a trail of the experiments when the system is restarted.
## Other Paths

A couple of other directions in the design of the Smalltalk-80 code file format that we did not take are worth noting. One direction would have been to invent a standard representation for the Smalltalk-80 virtual memory, and insist that everyone's system use it. The advantages with this would have been that the source code would fit in the system and that no special mechanism would be needed to retain system sources. However, it would not solve the communication problem, nor the recovery problem.

Another idea we discussed was to store only comments and temporary variable names on the files; the other pieces of text could be generated by the system, as is currently done by the Decompile. The benefits here are that fewer characters of disk space are needed and that code would appear in a consistent "pretty-printed" way. We decided that the disadvantages of this approach outweigh its advantages. Although it saves disk space in terms of the number of characters, there would be extra space used (either on disk or in main memory) to describe the mapping between comments and their place in the methods. This mapping would also involve a more complex computation. Another major disadvantage is that the code files would not be human readable. Also, we did not want to give up the flexibility of storing and displaying the code in the way it was typed, rather than in the pretty-printer's format. Keeping the sources "as is" seemed an easier approach than designing a more flexible pretty-printer, and even a flexible pretty printer would not provide that total flexibility.

The Smalltalk-80 system uses only two of the four source file streams provided; it does not exploit the flexibility that four can provide. One could imagine ways to use two more files. For example, one of the files could be used as a read-only version of the condensed changes file, providing a level of system backup between the sources and changes file.

Another direction that we did not pursue was to allow the text stored on the files to have multiple emphases (font and face changes) of the text. The Smalltalk-76 system¹ had two formats that preserved emphases, and produced listings that were easier to read and that allowed programmers to tailor the visual aspects of their code to suit their tastes. Since the Smalltalk-80 principles allow such tailoring in other areas of the system, tailoring source text ought to be allowed as well. Unfortunately, we were unable to design a file format that allowed both emphasis description and direct printing of the file on conventional printers. Solutions to keeping emphasis descriptions always involved using non-ASCII characters or had extra characters which would clutter the page if directly printed. We assume that in the future more printers will be available that print many fonts and faces. When this is the case (or to help make this be the case), we hope that some other standard that preserves emphases will emerge.
**Conclusion**

The Smalltalk-80 code file format was developed to allow communication between the flexible world of a Smalltalk-80 system and the less flexible world of disks, networks, storage devices and printers. It is used by the system to keep the source code for the methods on disk files, rather than within the memory of a resident system. It is also used to communicate changes between one system and another, and to provide a level of recovery from errors. The format is flexible enough to allow both code (source methods) and executable Smalltalk-80 expressions to be read in and/or evaluated; it also includes a general mechanism to allow objects in the Smalltalk-80 system to read and interpret the files. The format satisfies its design constraints and leaves the door open for several useful extensions.

**References**

1. Ingalls, Daniel H. H., "The Smalltalk-76 Programming System: Design and Implementation", Conference Record, Fifth Annual ACM Symposium on Principles of Programming Languages, 1978.
# Design Decisions for Smalltalk-80 Implementors

Allen Wirfs-Brock

Tektronix, Inc.
Beaverton, Oregon

## Abstract

The Smalltalk-80 virtual machine specification describes the required behavior of any Smalltalk-80 interpreter. The specification takes the form of a model implementation of a Smalltalk-80 interpreter. An implementor of a Smalltalk-80 interpreter is not required to exactly copy the data structures and algorithms of the model interpreter. The only requirement is that any Smalltalk-80 interpreter exhibit external behavior which is identical to that described by the formal specification. The implementor is free to make design tradeoffs that may increase the performance of the implementation while preserving the required external behavior. This paper identifies some of the design decisions which face a Smalltalk-80 implementor and discusses several design trade-offs.

## Introduction

The Smalltalk-80 virtual machine specification as it appears in *Smalltalk-80: The Language and Its Implementation*¹ describes the required low level behavior of any Smalltalk-80 implementation. The
specification takes the form of a Smalltalk-80 "program" which exhibits this behavior. One approach to the implementation of a Smalltalk-80 interpreter is to literally translate this program into some appropriate implementation language. While this approach will result in an interpreter which exhibits the required behavior, the performance of the resulting interpreter may be unsatisfactory.

An alternate implementation approach is to construct an interpreter that uses algorithms and data structures which differ from those used in the formal specification. These would be chosen to optimize performance for the host implementation environment. Such an interpreter may achieve higher performance but requires greater implementation effort.

This paper presents an overview of the design decision space which confronts the implementors of Smalltalk-80 interpreters. Specifically, it examines some of the potential design trade-offs concerning the host hardware and implementation language, the interpreter data structures, the actual execution of Smalltalk-80 instructions, and the creation and destruction of objects. Even though the design issues are examined assuming an interpreter implementation utilizing a conventional computer or microprocessor as a host, many of the trade-offs should be applicable to a microcoded or hardware implementation.

## The Formal Specification

The first part of the Smalltalk-80 virtual machine specification defines the virtual machine architecture. This includes the definition of the primitive data types, the instruction set, and the interface to the object memory manager. The second part describes the internal operation of the object memory manager. An implementation of the Smalltalk-80 virtual machine is commonly referred to as a Smalltalk-80 interpreter. The formal specification completely defines the required behavior of a Smalltalk-80 interpreter.

The formal specification takes the form of a collection of Smalltalk-80 methods which implement a Smalltalk-80 interpreter. It is, in effect, an implementation of a "model interpreter." Within this model the "registers" of the virtual machine are represented as Smalltalk-80 instance variables, the data structures are explicitly defined via constant field offsets and bit masks, and the required semantics of the interpreter are implicit in the behavior of the methods. The model bytecode interpreter implementation can be viewed as the definition of the correct behavior of a Smalltalk-80 implementation.
The specification does not place any particular requirements upon the internal implementation of the object memory manager. Of course, it assumes that any implementation will correctly preserve stored data and that this data will be available to the interpreter when requested. The memory manager implementation chapter may also be viewed as a model for how an object memory manager may be implemented.

An implementor of a Smalltalk-80 interpreter must design and construct an interpreter whose behavior conforms to that defined by the formal specification. One method of accomplishing this is to directly translate the Smalltalk-80 methods of the model implementation into an appropriate implementation language. One might even consider using a program to perform this translation. Figure 4.1 gives an example of a method from the formal specification and Figure 4.2 shows how it might be translated into Pascal.

The principal advantage of the direct translation approach is that it is a simple method of obtaining a semantically correct interpreter. It also is a very good way for an implementor to learn how the interpreter works internally. The principal disadvantage associated with this approach is that the resulting interpreter may exhibit disappointing performance levels. The data structures and algorithms of the book's interpreter were selected to provide a clear definition of the required behavior; they will probably not be optimal for any particular host computer. The challenge for a Smalltalk-80 implementor is to design an interpreter which will yield acceptable performance within some particular host environment. At Tektronix, we utilized the direct translation approach (see Chapter 5) and were able to very quickly build a working (but slow) Smalltalk-80 implementation. Experience gained from this initial implementation enabled us to later design a significantly improved second generation interpreter.

**initializeGuaranteedPointers**

"Undefined Object and Booleans"
nilPointer ← 2.
falsePointer ← 4.
truePointer ← 6.
"and so on ..."

**pushConstantBytecode**

currentBytecode = 113 ifTrue: [↑self push: truePointer].
currentBytecode = 114 ifTrue: [↑self push: falsePointer].
currentBytecode = 115 ifTrue: [↑self push: nilPointer].
currentBytecode = 116 ifTrue: [↑self push: minusOnePointer].
currentBytecode = 117 ifTrue: [↑self push: zeroPointer].
currentBytecode = 118 ifTrue: [↑self push: onePointer].
currentBytecode = 119 ifTrue: [↑self push: twoPointer].

<caption>Figure 4.1</caption>
<figure><img src="image_10.png" /></figure>

## The Host Processor

The first major design decision which will confront a Smalltalk-80 implementor will be the choice of the hardware which will host the implementation. In many situations the implementor will have little freedom in this area. Where the implementor has the freedom to select the host processor, there are a number of considerations which should enter into the decision process.

A processor which is to host a Smalltalk-80 interpreter should be fast. An interpreter which executes 10,000 bytecodes per second may be perceived by a Smalltalk-80 programmer to be quite slow. The original Tektronix implementation, which could execute 3500 bytecodes per second, was considered to be just barely usable. The Xerox Dolphin implementation executes 20,000 bytecodes per second and is considered to have "adequate" performance, while the Xerox Dorado at 400,000 bytecodes per second has excellent performance (see Chapter 9). At 10,000 bytecodes per second the interpreter will have, on the average, only 100 microseconds in which to fetch, decode, and execute each bytecode. At a more acceptable performance level of 100,000 bytecodes per second, the interpreter will have only 10 microseconds for each bytecode.

A Smalltalk-80 host processor architecture must support a large amount of main memory (either real or virtual). The standard Smalltalk-80 virtual image consists of approximately 500,000 bytes of
Smalltalk-80 objects. To this must be added the space for interpreter, the interpreter's data structures, the display bitmap, and additional space to contain objects created dynamically as the system runs. The total requirements of the system will easily approach one million bytes of memory with even a modest application. Although it may be possible to configure a virtual image with fewer features and more modest memory requirements, this can be most easily done utilizing an operational Smalltalk-80 system. For this reason, the implementor will need a development system with at least 1 megabyte of main memory.

By caching a number of variables which represent the execution state of a Smalltalk-80 method in internal registers, an implementation will probably get dramatically improved performance. A good host processor should have sufficient internal registers to allow these values to be cached in its registers. The exact number of registers needed to contain cached values will depend upon the specifics of the interpreter design. However, as a general rule, 8 is probably not enough while 32 is probably more than enough. For example, one of our implementations for the Motorola 68000 processor could have easily made use of several more than the 15 registers which were available.

Smalltalk-80 interpreters frequently look up values in tables and follow indirect references. For this reason it is desirable that the host processor provide good support for indexed addressing and indirection.

Hardware support for the Smalltalk-80 graphics model is another major consideration. Smalltalk-80 graphics is entirely based upon the manipulation of bitmaps. Although some implementations have simulated this model using other display technologies (for example, by using a vector oriented raster terminal), the results have been less than satisfactory (see Chapter 5). Acceptable results will only be achieved if an actual hardware bitmapped display is provided. A frequent concern of new implementors is the performance of BitBlt, the bitmap manipulation operation. One concern is whether specific hardware support will be required for this operation. Our experience with the 68000 was that adequate BitBlt performance was easy to achieve with straightforward coding, while adequate bytecode interpreter performance was very difficult to achieve. This leads us to believe that a host processor capable of achieving adequate performance when interpreting bytecodes will probably perform adequately when BitBlt-ing. In particular, the processor's ability to perform shifting and masking operations will affect the overall performance of BitBlt.

## The Implementation Language

The choice of an implementation language for a Smalltalk-80 interpreter is typically a trade-off between the ease of implementation of the interpreter and the final performance of the system. Implementors should
consider using a high-level programming language as the first implementation tool. A high-level language based interpreter can be quickly implemented and should be relatively easy to debug. Unfortunately, the final performance of such implementations may be disappointing. This may be the case even if a very good optimizing compiler is used.

It is generally accepted that the code generated for a large program by an optimizing compiler will be "better" than that which a human assembly language programmer would write for the same problem. Conversely, for short code sequences, a human programmer can usually write better code than that generated by an optimizing compiler. Although a Smalltalk-80 interpreter may appear to be a complex piece of software, it is actually a relatively small program. For example, our assembly language implementation for the Motorola 68000 contains approximately 5000 instructions. Furthermore, a large portion of the execution time tends to be spent executing only a few dozen of the instructions. These instruction sequences are short enough that carefully written assembly code can achieve significantly better performance than optimized compiler generated code. Our 68000 bytecode dispatch routine consists of five instructions, while the bodies of many of the push and pop bytecodes consist of only one or two instructions.

A successful Smalltalk-80 interpreter design will consist of an efficient mapping of the virtual machine architecture onto the available resources of the host processor. Such a mapping will include the global allocation of processor resources (registers, preferred memory locations, instruction sequences, etc.) for specific purposes within the interpreter. An assembly language programmer will have complete freedom to make these allocations. Such freedom is typically unavailable to a high-level language programmer who must work within a general purpose resource allocation model chosen by the designers of the compiler.

## Object Pointer Formats

The most common form of data manipulated by a Smalltalk-80 interpreter are Object Pointers (commonly referred to as Oop). An Oop represents either an atomic integer value in the range -16,384 to 16,383 or a reference to some particular Smalltalk-80 object. The formal specification uses a standard representation for Oop. This representation defines an Oop to be a 16-bit quantity. The least significant of the 16 bits is used as a tag which indicates how the rest of the bits are to be interpreted. If the tag bit is a 0 then the most significant 15 bits are interpreted as an object reference. If the tag bit is a 1 then the most significant 15 bits are interpreted as a 2's complement integer value.
Note that the size of an Oop determines both the total number of objects which may exist at any time (32,768) and the range of integer values upon which arithmetic is primitively performed.

Because Oops are used so frequently by the interpreter, their format can have a large impact upon the overall performance of the interpreter. The most common operations performed upon Oops by the interpreter are testing the tag bit, accessing the object referenced by an Oop, extracting the integer value from an Oop, and constructing an Oop from an integer.

Even though the standard Oop format pervades the formal specification, use of a different format will not violate the criteria for conformance to the specification. This is possible because the internal format of an Oop is invisible to the Smalltalk-80 programmer.

There are several possible alternative Oop formats which may offer varying performance advantages. One alternative is to change the position of the tag bit.

Placing the tag bit in the least significant bit position (the position in the standard Oop format) is most appropriate for a processor which reflects the value of this bit in its condition codes. This is the case for the Xerox processors² upon which the Smalltalk-80 system was originally developed, and for some common microprocessors. Using such a processor, the tag bit is automatically "tested" each time an Oop is accessed. A simple conditional branch instruction can then be used by the interpreter to choose between integer and object reference actions. Processors which lack this feature will require a more complex instruction sequence, shifting the Oop, a masking operation, and comparison to perform the same test.

Placing the tag in the most significant bit position causes the tag to occupy the sign-bit position for 16-bit 2's complement processors. For a processor that has condition codes which reflect the value of the sign bit, a test of the tag becomes a simple branch on positive or negative value.

Other factors which will affect the tag bit position might include the relative performance cost of setting the least significant bit as opposed to the most significant bit (is adding or logical or-ing a 1 less expensive than the same operation involving 32,768) for converting an integer into an Oop, and the relative cost of shifts as opposed to adds for converting Oops into table indices.

The standard format uses a tag bit value of 1 to identify an integer value and a tag bit value of 0 to identify an object identifier. Inverting this interpretation has potentially useful properties, some of which are also dependent upon the choice of tag bit position. For example, if a tag value 0 is used to indicate an integer valued Oop and the tag occupies the least significant bit position, then SmallInteger values are, in effect, 2's complement values which have been scaled by a factor of 2. Such
values can be added and subtracted (the most common arithmetic operations) without requiring a conversion from the Oop format and the result will also be a valid SmallInteger Oop. Only one of the operands of a multiplication operation will need to be converted from the Oop format for the operation to yield a valid SmallInteger Oop.

If a tag value of 0 is used to indicate object identifier Oops and the tag occupies the most significant bit position, then object identifier Oops can serve as direct indices into a table of 8-bit values on byte addressable processors. This would allow reference counting to be implemented using an independent table of 8-bit reference-count values which is directly indexed using Oops. For a word addressed processor, the standard format allows Oops to be used to directly index a 2 word per entry object table.

## The Object Memory

The object memory implementation described in the formal specification views the object memory as being physically divided into 16 physical segments, each containing 64K 16-bit words. Individual objects occupy space within a single segment. Object reference Oops are translated into memory addresses using a data structure known as the Object Table. The object table contains one 32-bit entry for each of the 32K possible object referencing Oops. Each object table entry has the following format:

<table><tr><td>Bits 0-15 (lsb):</td><td>The word offset of the object within its segment</td></tr><tr><td>Bits 16-19:</td><td>The number of the segment which contains the object</td></tr><tr><td>Bit 20:</td><td>Reserved</td></tr><tr><td>Bit 21:</td><td>Set if the Oop associated with this entry is unused</td></tr><tr><td>Bit 22:</td><td>Set if the fields of this object contain Oops</td></tr><tr><td>Bit 23:</td><td>Set if object contains an odd number of 8 bit fields</td></tr><tr><td>Bits 24-31 (msb):</td><td>This object's reference count</td></tr></table>

For each segment there is a set of linked lists which locate all free space within the segment. In addition there is a single list which links all unassigned Oops and object table entries. Objects are linked using Oop references.

The above design includes several implicit assumptions about the memory organization of the host processor. It assumes that the unit of memory addressability is a 16-bit word. It assumes that the processor uses a segmented address space and that each segment contains 64K
words. Finally, it assumes that at most 1024K words (16 segments) are
addressable. This organization may be considerably different from that
of an actual host processor. Many processors support a large, byte ad-
dressable, linear address space. Although the formal specification's de-
sign can be mapped onto such a memory organization, such a mapping
will result in reduced interpreter performance if it is carried out dy-
namically.

An object memory design will consist of two inter-related elements,
the organization of the actual object space and the format of the object
table. The goal of the design will usually be to minimize the time re-
quired to access the fields of an object when given an Oop. However, if
main memory is limited, the goal of the design may be to limit the size
of the object table. A performance oriented object table will usually be
represented as an array which is directly indexed by Oops (or a simple
function on Oops). A hash table might be used for a space efficient ob-
ject table representation³.

The most important component of an object table entry is the field
which contains the actual address of the associated object within the
object space. Ideally this field should contain the physical memory ad-
dress of the object represented so that it may be used without any
masking or shifting operations. Such a format will permit the contents
to be used to directly address the associated object, either by loading
the field into a processor base register or by some type of indirect ad-
dressing mechanism. In this case, the size of the address field will be
the size of a physical processor address.

If the host processor's physical address is larger than the 20-bits used
in the formal specification, the size of an object table entry will have to
be increased beyond 32-bits or the size of the reference count and flag
bits will have to be decreased. Since Oops are typically used as scaled
indexes into the object table, it is desirable that the size of an object ta-
ble entry be a power-of-two multiple of the processor's addressable word
size so that object table offsets may be computed by shifting instead of
multiplication. For most conventional processors, 64-bits (8 bytes, four
16-bit words, two 32-bit words) would be the next available size. Howev-
er, a 64-bit object table entry will require 256K bytes and will probably
contain many unused bits. An alternate approach is to use separate
parallel arrays to hold the address fields and the reference count/flag
fields of each entry. This results in an effective entry size which is
greater than 32-bits without requiring a full 64-bit entry. Decreasing
the size of the reference-count field is another valid alternative. Since
most reference count values are either very small (8 or less) or have
reached the overflow value where they stick⁴, a reference-count field
size of 3 or 4 bits should be adequate. The main consideration will be
whether the host processor can efficiently access such a field.
## The Bytecode Interpreter

The bytecode interpreter performs the task of fetching and executing individual Smalltalk-80 bytecodes (virtual machine instructions). Before examining the actual functioning of the bytecode interpreter, we will consider the general question of time/space trade-offs within Smalltalk-80 implementations. A complete, operational Smalltalk-80 system requires approximately one million bytes of storage to operate. The actual interpreter will occupy only a small fraction of this. (Our first implementation, which was very bulky, required approximately 128K bytes for the interpreter. A later assembly language implementation for the same host needed less than 25K bytes.) Since Smalltalk-80 interpreters seem to strain the computational resources of conventional processors, most interpreter designs will tend towards reducing execution time at the expense of increasing the total size of the implementation.

The model implementation in the formal specification takes an algorithmic approach to interpretation. The interpreter fetches a bytecode, shifts and masks it to extract the operation code and parameter fields, and uses conditional statements to select the particular operation to be performed. While this approach is quite effective for illustrating the encoding of the bytecodes it is often not suitable for a production interpreter because of the computation required to decode each bytecode. A more efficient implementation technique for the bytecode dispatch operation may be to use the bytecode as an index into a 256-way dispatch table which contains the addresses of the individual routines for each bytecode. For example, rather than using one routine, as in the example in Fig. 3.1, there could be seven individual routines, each one optimized for pushing a particular constant value.

The model implementation exhibits a high degree of modularity. This is particularly true in the area of the interface between the bytecode interpreter and the object memory manager. The bytecode interpreter makes explicit calls to object memory routines for each memory access. The performance of a production implementation can, however, be improved by incorporating intimate knowledge of the object memory implementation into the bytecode interpreter. Many object memory accesses may be performed directly by the interpreter without actually invoking separate routines within the object memory manager.

As mentioned earlier, the selection of which interpreter state values to cache is a critical design decision for the bytecode interpreter. The designer must evaluate the cost of maintaining the cached values (loading the values when a context is activated and storing some of the values back into the context when it is deactivated) relative to the actual performance gains from using the cached values. The evaluation should consider the average duration of an activation. Our observations indicate that most activations span a small number of bytecodes (less than
10). Caching too much of the active context can thus lead to situations where considerable execution time is spent caching values that are not used over the span of the activation.

The model implementation caches the actual `Oop` values of several context fields. This implies that these values must be decoded into real memory addresses (performing an object table lookup or conversion from `SmallInteger` format) each time they are used. An alternative is to decode these values when they are fetched from the active context and to cache the addresses. This means that the cached program counter would be the actual address of the next bytecode and that the cached stack pointer would be the actual address of the top element of the active context's stack. If this technique is used, care must be taken that the cached values are correctly updated, e.g., when the memory manager changes the physical location of objects (performs a segment compression). It is also essential that the values of the stack pointer and program counter field get updated when the active context changes.

The Smalltalk-80 system's required support for multiple processes, when implemented in an obvious manner, can impose an overhead upon each bytecode. The formal specification requires that a process switch may occur before each bytecode is fetched. An obvious way to implement this requirement is to have a global boolean flag which indicates that a process switch is pending, and to test this flag before fetching each bytecode. This technique has the disadvantage that the overhead of testing this flag occurs for each bytecode executed even though actual process switches are infrequent. Since the number of instructions required to implement most bytecodes is relatively small, this test can be a significant overhead. Alternative implementations techniques can avoid this overhead. For example, the address of the bytecode dispatcher might be stored in a processor register. Routines which implement bytecodes would then terminate by branching to the address contained in the registers. A pending process switch could then be signaled by changing the address in the register to the address of the routine which performs process switches. When the current bytecode finishes, control would therefore be transferred to the process switcher.

Memory
Management

The routines of the formal specification's object memory manager may be grouped into two categories. The first category consists of those routines which support accesses to objects. The second category consists of those routines which support the allocation and deallocation of objects.
The access routines (such as `fetchPointer:ofObject:` and `storeByte:ofObject:withValue:`) are used by the bytecode interpreter to store and retrieve the information contained in the fields of objects. In many implementations of the bytecode interpreter, these functions will not be performed by independent routines, but will be implicitly performed by inline code sequences within the routines of the interpreter. The object allocation and deallocation routines form the bulk of the memory manager.

Collectively, the memory management routines will probably comprise the most complex part of a Smalltalk-80 interpreter implementation. In addition, unless great care is taken in their design, the percentage of execution time spent in these routines can easily dominate the time spent in all other parts of the interpreter. Our initial implementation was found to be spending 70% of its time within memory management routines (see Chapter 5).

## Object Allocation

The bytecode interpreter normally requests the allocation of an object in two circumstances. The first circumstance is the execution of a primitive method (most commonly the primitive `new` or `new:`) which explicitly calls for the creation of a new object. The second circumstance is the activation of a new method. This implicitly requires the creation of a context object to represent the state of the activation. The formal specification provides a single generalized set of routines which handle both types of allocation requests. These routines perform the following actions. First they must assign an `Oop` which will be used to refer to the new object. Second they must find an area of free storage within the object memory, large enough to contain the requested object. Next they must initialize any internal data structures (for example an object table entry or object length field) used to represent the object. Finally, they must initialize the fields of the object with a null value.

Observation of actual Smalltalk-80 implementations indicates that the vast majority of allocation requests are for the creation of context objects (see Chapter 11). In addition, most of these requests are for the smaller of the two possible context sizes. A memory manager design which optimizes the creation of a small context object should thus yield better performance.

There are a number of possible approaches to achieving such an optimization. A memory manager might have a dedicated list of available contexts. These available contexts might be preinitialized and have pre-assigned `Oops` associated with them. If the memory manager attempts to ensure that this list will not be empty (perhaps by using a background process to maintain the list), then a context could usually be allocated by simply removing the first element from the list.
A memory manager might choose to dedicate a memory segment to the allocation of contexts. Since such a segment would only contain objects of a single size, the actual allocation and deallocation process should be simplified.

Any scheme to optimize context allocation must, of course, conform to the formal specification's requirement that a context behaves as a normal Smalltalk-80 object. The representation of activation records (contexts) as objects contributes much to the power of Smalltalk-80 (it allows programs such as the Smalltalk-80 debugger to be implemented) but requires a large amount of system overhead to support. A major challenge to Smalltalk-80 implementors is to develop techniques to reduce this overhead while preserving the inherent power of context objects.

Storage reclamation is the second major function of the Smalltalk-80 memory manager. While the Smalltalk-80 storage model allows a program to explicitly request the creation of an object, it does not require a program to explicitly request that an object be deallocated. Once an object has been allocated it must remain in existence as long as it is accessible from any other object. An object may only be deallocated if no references to it exist. It is the memory manager's responsibility to automatically deallocate all inaccessible objects. This process is commonly referred to as garbage collection⁵. The classical method (called mark/ sweep) of performing garbage collection is to periodically halt processing, identify all inaccessible objects, and then deallocate them. This is commonly done as a two-phase process. First all accessible objects are marked. This requires starting at some root object and traversing all accessible pointers in the system. Second, all unmarked objects are deallocated. With a large object memory, such a process may consume a considerable period of time (ranging from several seconds to several minutes). Because of the interactive nature of the Smalltalk-80 system, such delays are unacceptable. Instead, a garbage collection technique which distributes the storage reclamation overhead over the entire computation is required. The most commonly known technique for achieving this is reference counting. This is the technique used by the formal specification's model implementation.

Reference counting requires that each object have associated with it a count of the number of pointers to it which exist in the system. Each time an Oop is stored into a field the reference count of the object associated with the Oop is incremented. Since storing an Oop into a field must overwrite the previous contents of the field, the reference count associated with the old value is decremented. When the reference count of an object reaches zero, the object is deallocated. The deallocation of
an object invalidates any object references contained in it and hence will decrement their reference counts. This may recursively cause other objects to be deallocated.

Although reference counting eliminates the long delays characteristic of mark/sweep collection, it introduces considerable overhead into the normal operations of the system. We have found that for our host processor (a Motorola 68000), the code sequences that implement simple bytecodes such as the push and pop operations using reference counting are several times longer than the equivalent routines without reference counting. A Smalltalk-80 interpreter design that can decrease this overhead should have greatly improved performance.

There are several possible approaches to achieving this improved performance. One technique which reduces the actual counting overhead is called deferred reference counting⁶. It is based upon the observations that the most frequent and most dynamic object references occur from context objects and that many of these references are quite transitory. For example, assigning an object to a variable causes the object's reference count to be first increased by one as it is pushed onto the context's stack, then decreased by one as it is popped from the stack, and finally increased by one as it is stored into the variable. Our measurements show that "store instance variable" bytecodes (the most common means of creating an object reference from a non-context object) account for less than 4% percent of the dynamically executed bytecodes. If the need to perform reference counting for references contained within contexts is eliminated, then almost all of the reference counting overhead will have been eliminated.

## A Second Generation Design

The first Tektronix Smalltalk-80 interpreter was implemented in Pascal on a Motorola 68000 (see Chapter 5). Even though the performance of this implementation was so poor that it was only marginally useful, the experience gained from this effort enabled us to design a new interpreter which exhibits much better performance. In developing this second generation interpreter we encountered many of the design tradeoffs mentioned in the previous sections of this paper. The new interpreter was designed and implemented by the author over a period of approximately nine months.

We choose to continue using a 68000 as the host for the new interpreter but component advances enabled us to use a 10 Mhz processor with one memory wait state instead of an 8 Mhz processor with two wait states. We choose to implement the interpreter in assembly language.
guage. In addition, great care was taken in choosing the code sequences
for all of the frequently executed portions of the interpreter. The com-
mon byte codes are all open coded with separate routines for each possi-
ble instruction parameter.

The active context's stack pointer, instruction pointer, and home con-
text pointer are cached in 68000 base registers as 68000 addresses. The
stack pointer representation was chosen such that 68000 stack-oriented
addressing modes could be used to access the active context stack. Oth-
er registers are dedicated to global resources such as addressing the ob-
ject table and accessing free context objects.

The Oop format chosen requires only a simple add instruction to con-
vert an Oop into an object table index. Object table entries can be di-
rectly loaded into base registers for accessing objects. A separate
reference-count table is used. Deferred reference counting is used to
limit the reference-counting overhead and to streamline the code se-
quences for push/pop bytecodes. Complete context objects are not creat-
ed for leaves of the message send tree. Context objects are only created
if a method references the active context or causes another new context
to be activated.

The initial (before any tuning and without some optional primitives)
performance benchmarks of our second generation interpreter (see
Chapter 9) show that it is between five and eight times faster than our
original implementation. We feel that these results demonstrate that it
is feasible to build usable microprocessor based Smalltalk-80 implemen-
tations.

**Summary and**
**Conclusions**

For any given host processor, its performance as a Smalltalk-80 host
can potentially vary widely depending upon how the Smalltalk-80 inter-
preter is implemented. The goal of a Smalltalk-80 implementor should
be to achieve the best possible mapping of the Smalltalk-80 virtual ma-
chine specification onto the chosen host computer. To accomplish this,
the implementor will need to intimately understand both the internal
dynamic behavior of the Smalltalk-80 virtual machine and the idiosyn-
crasies of the host processor. We would recommend that an
implementor gain an understanding of the behavior of the virtual ma-
chine by first using a high-level language to implement the interpreter
as described by the formal specification. This implementation can then
be used to study the actual behavior of the Smalltalk-80 system and ex-
plore design alternatives. Finally, a new implementation should be
designed which takes maximum advantage of the characteristics of the
host processor. We have presented a few of the design alternatives which should be considered by Smalltalk-80 implementors as they develop their interpreters.

## References

1. Goldberg, Adele, and Robson, David, *Smalltalk-80: The Language and Its Implementation*, Addison-Wesley, Reading, MA, 1983.

2. Lampson, Butler W., "The Dorado: A High Performance Personal Computer," Xerox PARC Technical Report CSL-81-1, Jan. 1981.

3. Kaehler, Ted, "Virtual Memory for an Object-Oriented Language," *Byte* vol. 6, no. 8, pp. 378-387, Aug. 1981.

4. Baden, Scott, "Architectural Enhancements for an Object-Based Memory System," CS-292R Class Report, Computer Science Div., Dept. of E.E.C.S., University of California, Berkeley, CA, Fall 1981.

5. Cohen, Jacques; "Garbage Collection of Linked Data Structures", *ACM Computing Surveys* vol. 13, no. 3, pp. 341-367, Sept. 1981.

6. Deutsch, L. Peter, and Bobrow Daniel G., "An Efficient Incremental Automatic Garbage Collector," *Communications of the ACM* vol. 19, no. 9, pp. 522-526, Sept. 1976.
PART TWO

<figure><img src="image_11.png" /></figure>

FLASH

HERE WE GO!

OF TOO MATE!

LATER...

3+4

DODD, 9 teep

2

EARTH

ONCE MORE!

Hmmm...

LATER...

3+4

LAD COMPILER DOES NOT

ONDERSTAND = 'H, 3EP'

THIS DUGHT TO
BE BETTER!

WELL, NOW...

LATER...

3+4

CLASS TEXT IMAGE

CH! I THINK I
KNOW WHAT
THAT IS...

LATER...

3+4

q

ALL RIGHT!

HEY EVERYBODY
SMALL TALK WORKS!
# Implementing the Smalltalk-80 System: The Tektronix Experience

Paul L. McCullough*

Tektronix, Inc.
Beaverton, Oregon

## Introduction

The Tektronix Smalltalk-80 implementation went through a number of hardware and software phases. Our experience will probably prove to be similar to that of other research and prototype groups desiring to implement the Smalltalk-80 system. At best, we will point out some mistakes to avoid; at the very least we can provide an entertaining view of our successes and follies.

This paper gives an overview of our initial hardware and software environments and our initial implementation design. We then present a fairly detailed account of debugging our first system. Next, we describe the evolution of our hardware, software, and development tools. We conclude with some observations and conclusions about the Smalltalk-80 system and its implications for the future.

Readers should note that we were debugging both our implementation and the formal specification. Although we detected a number of errors in the formal specification, these errors have since been corrected and are discussed herein to provide historical perspective.

<footnote>*Mr. McCullough is currently employed by Xerox Palo Alto Research Center, Palo Alto, California. Copyright © Tektronix, Inc., 1982. All rights reserved.</footnote>
## Initial Goals

Initially we had four goals for our Smalltalk-80 work:

* Learn about the Smalltalk-80 system, in particular the implementation of the virtual machine,

* Learn about programming in the Smalltalk-80 language,

* Report on errors in the book draft, and

* Implement the virtual machine, realizing that it would not be our final implementation.

Tektronix had no previous experience with object-oriented software, so we were very interested in having a system with which we could interactively program in the Smalltalk-80 language, and in studying the Smalltalk-80 virtual machine. As part of our agreement with Xerox, we were to use our implementation as a means to detect errors in the book draft and to identify ways in which the book might be made clearer. We realized that our initial implementation would suffer from performance problems, but felt that a timely implementation was more desirable than a high performance one.

## Initial Hardware

Our initial hardware consisted of:

* Motorola 68000 processor (8 MHz)

* 4 MHz proprietary bus

* 768 Kbytes of RAM

* Tektronix 4025 terminal

* A microprocessor development system, used as a file server

The choice of hardware was based on the availability of a Tektronix designed 68000-based system, along with the need for a large, preferably linear, address space. We also wanted to use a processor amenable to the construction of personal workstations. The Tektronix 4025 terminal is a raster graphics terminal, primarily oriented toward drawing vectors. While our bitmapped display was being designed, the 4025 served as an interim display device. Because the initial Smalltalk-80 virtual image did not depend on the use of a file system, we only used the microprocessor development system as a file server to load and store virtual images.
## Software Development Environment

Our virtual machine was developed in a cross-compilation environment using a DECSYSTEM-20. The bulk of the virtual machine was written in a dialect of the proposed ISO Standard Pascal. This particular dialect of Pascal supports the independent compilation of modules and produces assembly language files which are assembled and linked. The resulting executable file is downloaded to the 68000-based system over a 1200 baud serial line. Though the 1200 baud line was an obvious bottleneck, the Pascal software already existed on the DECSYSTEM-20 and we had no desire to port it.

## Initial Software

According to Dan Ingalls: "an operating system is a collection of things that don't fit into a language. There shouldn't be one"¹. Taking those words to heart, we chose to implement our virtual machine on a system that had no operating system. This choice meant that we could not rely on runtime services normally provided by an operating system and had to write those portions that we needed, such as routines to handle input/output to an RS-232 port and perform IEEE 32-bit floating point arithmetic.

Our software implementation team consisted of three software engineers. We chose to partition the programming task into three distinct parts:

* Object Memory Manager

* Interpreter and Primitives

* BitBlt

### Object Memory Manager

The initial object memory manager was, for the most part, a strict translation from Smalltalk-80 to Pascal of the methods presented in the formal specification. During the translation phase, we noted four minor typographical errors in the draft of the book involving improper bit masks, or incorrect variable, constant, or method names. We chose to implement the reference-counting garbage collector. Later, because the image creates circular garbage, we added a simple, recursive, mark-sweep collector. The translation process took less than one week and resulted in a working memory manager that maintained a very clear boundary between itself and the rest of the virtual machine. As discussed below, this clear differentiation is both a blessing and a curse.

With minor changes due to different dialects of Pascal, we were able to run programs that tested the object memory manager on the DECSYSTEM-20 with its more sophisticated debugging and perform-
ance monitoring software. The test programs read the virtual image, then made calls to the various entry points in the memory manager. Then, with Pascal write statements and the debugger, we were able to examine the state of the object space and determine whether the memory manager was working correctly. These tests indicated several errors in the book's methods: for example, the method that determined where to find the last pointer of an object was incorrect for CompiledMethods, and the recursive freer needed an extra guard to prevent SmallIntegers from being passed off to the pointerBitOf: routine.

At this point, we were able to run test programs that created instances of classes, stored object pointers in other objects, destroyed such links and thus invoked the deallocation of objects, and performed compactions of the object space. Further testing demonstrated that the book's method for swapPointersOf:and: was also incorrect.

In order to speed up the performance of the deallocation portions of the memory manager, we modified the countDown: routine to call forAllObjectsAccessibleFrom:suchThatDo: only when the object's reference count was going to drop to zero, thus saving a procedure activation that was usually unnecessary.

A few other minor changes provided us with a memory manager that was tested on the DECSYSTEM-20. Thus, we had a great deal of assurance that the memory manager would perform correctly on the 68000-based system. Also, we felt that when problems were encountered in our implementation of the virtual machine, we could concentrate on looking for the problem in the bytecode interpreter or primitives, and could ignore the memory manager. In actual practice we made many, many runs of the virtual machine before any problems were found in the memory manager. We heartily recommend having a trustworthy memory manager.

In parallel with the development of the object memory manager, we coded the bytecode interpreter and primitives. The interpreter and many of the primitives were written in Pascal. The arithmetic primitives were coded in assembly language in order to simplify the maintenance of the small integer tag bit.

The outer block of the interpreter consists of a call to an initialization routine and a loop containing a very large case statement that acts as the bytecode dispatcher. While the memory manager was a fairly literal translation of the book's methods, much greater care was exercised in the construction of the interpreter. Code that in the book was several message sends was often collapsed into a single Pascal statement. We included in our interpreter the capability of producing traces which duplicate those supplied with the virtual image by Xerox.

In order to give the reader a measure of the complexity of implementing an interpreter (in Pascal), we present the lengths (in
printer pages at 60 lines per page) of some of the major routines. These
figures include the length of tracing code:

* Looking up a message, including the `perform:` primitive: two and one-half pages

* Sending a message (including cache lookup): one and one-half pages

* Executing the current method, including the primitives written in Pascal: twelve pages

* Returning a value from the active context: one and one-half pages

* The scan characters primitive (used for text composition): three and one-half pages

* Large integer primitives: four pages

* Process primitives: five pages

We strongly recommend that the first implementation of an interpreter be in a high-level language. By writing the virtual machine in a high-level language, implementors gain a more thorough understanding of the virtual machine as well as a much more quickly completed implementation.

The BitBlt primitive handles all graphics in the Smalltalk-80 system. Due to its importance, we decided to have one person concentrate on its implementation. The routines to implement BitBlt were written in assembly language and closely reflect the structure of the BitBlt methods in the book. To assist in the debugging of BitBlt, there are many conditionally assembled calls to the Pascal runtime print routines. The main BitBlt routine accepts one argument, the address of a Pascal record containing the various BitBlt parameters. When called, the routines perform the following actions:

* Clip the source parameters to the physical size of the source form

* Clip the clipping rectangle to the true size of the destination form

* Clip and adjust the source origin

* Compute the masks necessary for the logical operations

* Check for possible overlap of the source and destination forms

* Calculate the offsets for the starting and ending words

* Copy the bits as appropriate

BitBlt
Certain optimizations are performed for the special cases of clearing, setting, or complementing the destination forms. BitBit is approximately 2 Kbytes of assembly code.

## Summary of Runs

We maintained a fairly detailed log of our attempts to get the virtual machine up and running. The comments we made for each of these runs may be helpful to future implementors of the virtual machine. This summary should provide a sense of the types of errors and problems one should expect when implementing the virtual machine.

1. Reached the first send, then encountered an error in a debugging routine we had written.

2. Reached the first send again, encountered another error in a debugging routine.

3. Encountered a Pascal compiler bug.

4. Reached first send of the @ selector, and discovered that we had transcribed the constant for class SmallInteger incorrectly.

5. The method specified in the book for initializing the stack pointer of a new context was incorrect.

6. We forgot to initialize the sender field when creating a context.

7. In the book, the method returnValue:to: caused the reference count of the sender context to go to zero (thereby making the sender garbage) just before returning to that context. We had to explicitly increase the reference count of the sender context, perform the return, then explicitly decrement the reference count.

8. We had decided to implement the "common selector" bytecodes using full message lookup. Unfortunately, the method header for selector == in class Object did not specify the execution of a primitive. We patched the image to specify the correct primitive number.

9. The first conditional branch we encountered failed because we did not advance the instruction pointer past the second byte of the instruction.

10. We discovered that the source code for SmallInteger < did not specify a primitive, resulting in an infinite recursion. We patched the image again.

11. Discovered that other methods of class SmallInteger did not have primitives specified. We retrenched to executing the following selectors without lookup: class, ==, arithmetics, relationals.
12. Selector `at:` failed. Our fault, in the routine `positive16BitValueOf:` a `>` should have been a `<`.

13. Multiply primitive failed due to an assembly language coding error.

14. All relational primitives written in assembly language had an incorrect (and uninitialized) register specified.

15. Made it through the first trace. (Listings of four traces of the interpreter's internal operations were included with the first distribution of the virtual image. Subsequent distributions included three traces.)

16. The book's method for the primitive value: caused the stack to be off-by-one.

17. Once again, we found an error initializing the stack pointer of new contexts.

18. Again, the stack pointer is off. These three errors were caused by an incorrect constant in the book draft.

19. A message selector was not found. Another run is necessary to determine what happened.

20. At the beginning of execution for a block, the cached stack pointer is one too large. In the past, message sends and returns have worked because the routine that stored the stack pointer decremented it.

21. We had coded the `at:put:` primitive incorrectly: we forgot to have it return anything, hence the stack was off-by-one.

22. We incorrectly coded the `at:put:` primitive with an uninitialized variable.

23. The `at:put:` primitive had a `>` that should have been a `>=`.

24. The `SmallInteger` `bitShift:` primitive added in the `SmallInteger` bit, but should have `Or'ed it in.

25. Interpreting lots of bytecodes, unfortunately not the correct ones. Apparently, we took a bad branch somewhere.

26. We found that the book's methods for the bytecode `"push self"` did not necessarily work for block contexts.

27. Almost through the fourth trace when the `SmallInteger` division primitive failed to clear the high-order half of a register. The error was detected by a Pascal runtime check.
28. Through the fourth trace when Sensor primMousePoint dies because of a clash between the interpreter and the Pascal runtimes.

29. We are well beyond the fourth trace when we discover that the method frame:window:para:style:printing: has a MethodHeader extension that specifies primitive number 0. We had assumed that an extension always specified a valid primitive number, but find that it may also be used to specify a method with more than four arguments.

30. We have changed all unimplemented primitives so that they fail, and now correctly handle primitive 0 in MethodHeader extensions. By now, we should have something up on the 4025 display, but do not. Investigating, we find that the book says that the bitmap for a Form is the first field, whereas the sources say it is the second field.

31. We are halftoning the display. We have to make a few adjustments to prevent overrunning the display. Halftoning will take a long time, approximately two hours. After a while, a runtime exception was raised by a Pascal support routine that contained a bug.

32. The "T" for the TopView window title tab is present on the display. Interpreter stopped after sending copyTo: to a SmallInteger.

33. We have disabled halftoning to the 4025, continuing with the study of the problem of sending copyTo: to a SmallInteger.

34. The problem is that the BitBlt primitive, copyBits did not return anything, thus forcing the stack off by one. Similarly, beDisplay, and beCursor did not return anything. We have added more display memory to the 4025.

35. Hurray! "Top View" window title tab is on the screen. Pascal runtime checks detected an out-of-range scalar while setting up arguments for copyBits. We have always assumed that BitBlt arguments are unsigned, but that is not so. We were told that BitBlt should do source clipping, so we will add that to BitBlt.

36. The entire "Top View" window is on the display, then erased. We eventually crashed because we are out of object space, but unsure why.

37. We are out of object space because the book's methods for superclass send was incorrect: another level of indirection is necessary.

38. We now have "Top View" window, Browser, and Transcript window on the display. Interpreter stopped when the mouseButtons primitive failed.
39. We turned on halftoning to see what would happen. This was a mistake because windows are halftoned black and then white. We decided to reload and try again without halftoning.

40. We have reached the idle loop, checking if the mouse is in any window. We changed the position of the mouse (by altering two memory locations) and placed it within the browser. The browser awoke and refreshed four of its panes. The fifth pane (code pane) caused an interpreter crash with a Pascal out-of-range error due to a minor bug in the mod primitive.

41. Great excitement! We have refreshed the window containing a "Congratulations!!" message. Eventually we crashed because the Float < primitive fails. The system tried to put up a Notify window, but had difficulty because of other primitive failures. However, it was able to put up messages in the Transcript window. For a system that is not yet fully implemented, it is amazingly robust. We noticed that certain BitBlt operations seem to put up incorrect information, then erase it. For example, putting up the "Top View" title tab, the text reads "Top Vijkl" for a short time, and the incorrect part is then repainted. Investigation showed the method computeMasks to have a < selector that should have been a <=, an error carried over from the book.

42. Generally poking around with the system. We have found that we need floating point primitives in order for scroll bars to work, so we have implemented all but the fractionalPart primitive. Rather than develop an IEEE Floating Point package, we acquired one from another group at Tektronix. We have also speeded up BitBlt by using 4010-style graphics commands with the 4025.

43. We have implemented object memory statistics to report the number of fetchPointers, storePointers, etc. performed. We have also added a lookup cache for faster message send processing. A clerical error in the caching routines crashes the virtual machine.

44. An uninitialized variable causes the cache to misbehave.

45. The cache is functioning well. Our initial algorithm is to exclusive-or the Oops of the receiver's class and the method, then extract bits 3-7 and index a 256 element array of 8 byte entries. The interpreter definitely runs faster with the cache. The cache consists of the Oop of the selector, Oop of the receiver's class, Oop of the method, the most significant byte of the method header, and one byte indicating either the primitive index or 0.

46. Tried a new hash function, shifting two bits to the left before the exclusive-or because we observed that theOops of different selec-
tors in the same class are very similar to one another. Some speedup was noted.

47. Another hash function, this time adding the `Oops` rather than exclusive-oring them. No noticeable change. We did move the mouse to the first pane of the Browser and crashed the system when the interpreter passed a `SmallInteger` to the memory manager.

48. Further examination of the previous problem shows that we did not cut the stack back far enough after a value: message. This bug was carried over into our code from the book, but only appears when sending value: within an iterative loop.

49. We have fixed value:, now we need to write the perform: primitive.

50. We have installed perform:, but get an infinite recursion because the floating point package is *not* IEEE format. We will write one in Pascal.

51. With the new floating point code, we can now cut text, pop up menus, and so on. This is great!

At this point, we added some simple performance monitoring code. We counted the number and type of object memory references, the number of bytecodes executed, and information concerning the performance of the lookup cache. For each bytecode executed, an average of just under 10 object memory references were made. The majority were calls to `fetchPointer:`, then `storePointer:`, `fetchByte:`, and `fetchClass:`. The various lookup cache algorithms were found to perform either fairly well (50 to 70% hit rate) or very poorly (20% or worse hit rate). Evidently, caching algorithms either perform quite well or miserably.

We feel that we were able to implement a relatively complex piece of software in less than six weeks (that is, from nothing to a working system) in less than 60 runs for several reasons:

* Summary of Initial Software

* We were fortunate to have very good software engineers.

* We had a well-defined task.

* Because it took so long to load the virtual image (about 10 minutes) from the file server and so long (again, 10 minutes) to download our virtual machine from the host, we were very careful in coding and in analyzing crashes. We were also sharing the hardware with another group, so we made good use of our time on the machine.

* The specification, though not without error, was well written.
## The Second Virtual Image

About this time, we received the second virtual image from Xerox Palo Alto Research Center (PARC). With this image, the handling of primitive methods was much cleaner, access to BitBlt was improved, the kernel classes were rewritten, and a source code management system was added. Several significant changes to the virtual machine specification were made, with the intention that these would be the final modifications. The second image also made use of the process primitives, while the first image did not.

Because a general cleanup of our interpreter seemed a good idea, and because a fair amount of the interpreter needed to be changed to support processes and new primitive numbers, we rewrote much of it. A history of our runs for the second virtual image follows:

1. We got our "Initializing..." message, and the system crashed because we were trying to initialize the cursor frame buffer. Since our bitmap display was not yet available, the presence of this code was premature.

2. We are through one-third of the first trace, but a conditional branch bytecode branched the wrong way.

3. Several problems noted:

* Metaclass names no longer print properly on our traces.

* We encountered off-by-one errors in stack operations while handling bytecode 187 because we forgot to adjust the stack index.

* We encountered off-by-one errors in stack operation for `SmallInteger //`.

* Our trace does not print operands for `SmallInteger *` properly.

* We need to carefully check the code for all stack operations.

4. M68000 stack overflow causes parity errors.

5. We are through trace 1, and three-quarters through trace 2 when Pascal detects an out-of-range scalar because the routine `returnValue/to:` returned to a deallocated block context. We had failed to increase a reference count.

6. We are almost halfway through trace 3 when we hit an unimplemented process primitive. We also noticed the primitive return of an instance variable did not pop the receiver, thus causing the stack to be off-by-one.
7. We are about 60% through trace 3 when we try to add nil to an instance of class Rectangle. Caused by our coding error: when a direct execution send fails, we fail to tidy up the stack pointer.

8. We find that we need to implement the process primitives.

9. BitBit fails to clear the high-order bits of a register causing a crash on the 21380th message sent.

10. Sending the selector `+` to an Array fails. Stack is off-by-one because the copyBits primitive failed to return self.

11. We find that the resume: primitive does not work due to an uninitialized variable.

12. More problems with resume:, it fails to set a boolean.

13. More problems with the resume: primitive: the process to be resumed has nil as its instruction pointer because the initial instruction pointer is not set in primitiveBlockCopy.

14. The resume: primitive works finally! Unfortunately, the wait primitive does not because of an incorrectly coded branch.

15. The wait primitive works, and we are through the third trace correctly. We forgot to code the setting of the success boolean for primitive become:, so a notify window is created.

16. Fired up the system. We have executed more than 15,000,000 bytecodes and it is still alive!

In order to improve performance, we made many changes to the interpreter and the memory manager. Changes to the interpreter included the caching of absolute addresses in the interpreter, thus employing considerably fewer calls to the memory manager. For example, to extract the fields of a source form, rather than a fetchPointer call to the memory manager for every field, the interpreter merely cached an absolute address and stepped through a range of offsets. Within the memory manager, many procedure calls were replaced with macro calls that were expanded by a macro preprocessor. Not only did this save the overhead of procedure calls, but quite often allowed common subexpression elimination to occur, thus actually decreasing the amount of compiler-generated code.

We also sped up certain parts of the interpreter based on where we believed the interpreter was spending its time. With these optimizations, performance is approximately 470 bytecodes a second.

An observation: Utilizing a raw computer (that is, one without an underlying operating system) to implement a Smalltalk-80 system is a double-edged sword: on the one hand, you can place data structures and
code anywhere in the system, and you have complete control of the
hardware. On the other hand, the lack of performance monitoring tools
and underlying file systems can be a problem because it takes time to
implement them, rather than just interfacing to them.

## Second Version of the Hardware

At about this time, we added floppy disks to the system, as well as a
utility program that could save and restore arbitrary memory locations
on the disks, thus freeing us from the microprocessor development sys-
tem file server. The 10 minute delay for the loading of a virtual image
was reduced to about 45 seconds. A more dramatic change to the hard-
ware was the addition of our bitmap display. No longer would we have
to translate bitmap operations to vector drawing commands on the
4025, nor wait for a window to be halftoned. We also added a standard
Tektronix keyboard and a mouse. In order for the mouse and keyboard
(as well as portions of the Smalltalk-80 software) to work, we also added
a one millisecond timer interrupt.

As part of another project, a new M68000 processor board was made
available to us. Recall that the bus that we were using ran at 4 MHz,
which introduced wait states into the M68000. The new processor board
used a one longword data cache and a one longword instruction cache
to reduce bus requests. This resulted in a 70% speedup in system per-
formance, to approximately 800 bytecodes per second.

## The Third Virtual Image

At this point, our goal became to build a virtual machine that was
clearly faster (approximately 4000 bytecodes per second), but to do it
quickly and at relatively low expense. The method we chose was to de-
velop a performance analysis tool and, using the results of the measure-
ments, to rewrite time consuming portions of the virtual machine in
assembly language. The following sections summarize our findings and
our techniques for speeding up the virtual machine.

## Performance Modeling Tool

To monitor the execution of the virtual machine, we developed a simple
analysis tool that was called by the one millisecond timer interrupt rou-
tine. Each time it was called, it stored the value of the interrupted
M68000 program counter. By changing a memory location, a routine could be activated to print a histogram showing ranges of program addresses, the number of times the program counter was found to be within the range, and the percentage of time spent within the range. The size of the address range for each line of the histogram was selectable by the user. We mapped routine addresses to these ranges so that the histogram showed time spent in each routine. This tool proved to be invaluable in speeding up the virtual machine.

Prior to utilizing this tool, we decided to measure how much time was spent in the interrupt service routine. The Smalltalk-80 virtual machine expects a timer interrupt every millisecond and the routine checks the mouse and keyboard motion registers. If a change has occurred, the routine makes note of the change so that the bytecode dispatch loop can create a Smalltalk-80 event. Like much of our virtual machine, our timer interrupt routine was initially written in Pascal. Because the interrupt routine has many basic blocks, and the optimizer of the Pascal compiler operates only upon one basic block at a time, the interrupt service routine spent a great deal of time reloading registers with previously loaded values. We discovered that an amazing 30% of the M68000 cycles were going to the interrupt service routine! One of the first optimizations that we performed was to take the Pascal compiler-generated code and to perform flow analysis on it. The new interrupt service routine consumed 9% of the M68000 cycles. Future plans call for hardware to track mouse and keyboard events, and for timers to interrupt the M68000 only when necessary (for example, when an instance of class Delay has finished its wait period).

## The Results of Performance Monitoring

The performance monitoring tool showed us some statistics that were surprising to us (the percentage figures presented below do not include time spent in the interrupt service routine nor the performance monitoring tool). Approximately 70% of the M68000 cycles were being spent in the memory manager, 20% in the interpreter and primitives, and 10% in BitBlt. The bulk of the time in the memory manager was spent in only a few routines: fetchPointer:ofObject:, storePointer:ofObject:withValue:, fetchClassOf:, countUp:, countDown:, and two sets of routines generally referred to as the recursive freer and the niller. Previous statistics we gathered had indicated that fetchPointer:ofObject: and storePointer:ofObject:withValue: were popular routines, but they were relatively short and (so it seemed) should consume relatively little processor time.
Looking at the Pascal-generated code, we felt that we could do far better with assembly language, and we recoded all memory manager routines that the interpreter and primitives could call directly. Recoding `fetchPointer:ofObject:` resulted in a 4.5% speedup. Next, we recoded `storePointer:ofObject:withValue:` and achieved an additional 13% speedup. The major difference between these two routines is in reference counting: when storing pointers, reference counts must be updated; when fetching pointers they do not. Although we had previously concluded that reference counting was an expensive operation, we now had measurements of just how expensive. After recoding in assembly language all the routines callable by the interpreter and primitives, the system was an aggregate 19% faster.

Next, we considered routines that were private to the memory management module. From the histograms, it was obvious that we spent a great deal of time initializing just-instantiated objects to nil pointers (or zeroes for non-pointer objects). This inefficiency again arose from the strict basic block analysis of the Pascal compiler. For the price of a procedure call to an assembly language routine, we were rewarded with a speedup of nearly 10%.

Another major change to the memory manager came in the area of the so-called recursive freer. When an object's reference count drops to zero, this set of routines is activated to decrement the reference counts of the object's referents and, should their counts drop to zero, recursively free them. The first attempt at speeding up this process was done in Pascal and resulted in nearly a 10% speedup. Later on, we rewrote the recursive freer again in assembly language achieving an additional speedup.

The instantiation of objects was also expensive because several procedure calls were made. We rewrote this code (still in Pascal), collapsing several procedures into one. Later, the instantiation routines were rewritten in assembly language.

Changes to the interpreter and primitives were done in an interesting manner. Recall that we had a functioning, albeit slow, interpreter. With the belief that it is far better to change one thing at a time, rather than everything at once, we modified a small portion of the interpreter and tested the change. Once the change was shown to be satisfactory, we changed another part of the interpreter.

Initially, we rewrote the bytecode dispatch routine, but, in keeping with our philosophy of small changes, none of the bytecode interpretation routines. Thus, the assembly language bytecode dispatch routine set a boolean indicating that the assembly language dispatch had failed and that the Pascal routine would have to take over. Then we added bytecode interpretation routines, more or less one at a time. Eventually, we were able to discard the Pascal dispatch loop and bytecode interpreters completely.
Once all the bytecode interpretation routines were completed, we turned our attention to the primitive routines. These changes were accomplished in a similar manner: initially, all assembly language primitives failed, forcing the Pascal-coded primitives to run. We would then select a primitive, code it in assembly language, and test it. Once it was found to be acceptable, we selected another primitive to re-code. Finally, the Pascal primitives were discarded. Rather than call high-frequency primitive routines, we included many of them in-line.

In order to save some procedure calls to the memory manager when instantiating objects, the interpreter first tries to directly acquire the new object off the free lists. If the attempt fails, the interpreter calls the memory manager. Such "fuzzing" of the line between the pieces of the virtual machine seem necessary to achieve acceptable performance on current microprocessors. This demonstrates how a clear boundary between the memory manager and the rest of the virtual machine is both a blessing and a curse.

The changes to the memory manager and interpreter eventually resulted in a 3500 bytecode per second system.

## The Third and Fourth Images

Our technique of making incremental changes to the virtual machine enabled us to use a working system and to bring up new virtual images as they were received from Xerox. A log of the attempts to run the third image follows:

1. At Xerox, the display bitmap is simply an object in the object space. In our implementation, the display bitmap lives at a specific address, and we encountered a problem because this image sends the become: primitive to the current display object. We modified our code in the become: routine.

2. We encountered a Pascal subscript-out-of-range error. The routine that returns instance variables was coded incorrectly, due to an error in the book's specification.

3. There are some new primitives related to the Xerox implementation in the image. We modified our interpreter to understand them.

4. A bit of Smalltalk folklore: "If 3 + 4 works, everything works." We typed 3 + 4 into a window and executed it. It did not work because the SmallInteger size message returned the wrong result.
5. Executing "Circle exampleOne" causes infinite recursion because the graphics classes were coded incorrectly by Xerox. They had not noticed this problem because the Xerox implementation of primitive new: did not comply with the formal specification, allowing their code to execute.

6. The system is up and working.

The fourth image was brought up on the first attempt.

## Some Observations

If we analyze the coding errors that we encountered in our various implementations, we find that most fall into the following categories:

* Off-by-one errors

* Failing to return the correct object, or failing to return any object (leading to off-by-one errors)

* Conditional branch reversals

* Errors in the specification

Perhaps the most painful part of debugging a virtual machine is finding the off-by-one errors. These errors typically arise in primitive handling and in the stack activation records. Certain primitives may fail, and Smalltalk-80 methods are expected to take over. During the development of the virtual machine, it is quite common to damage the object references on the stack or to misadjust the stack pointer resulting in off-by-one errors. When returning from a procedure call in many stack machines (the M68000 is an example), if the processor's stack has an extra argument or does not have a return value, the correct return address will not be found, and the processor will return to an erroneous location. The typical result is a system crash. In the Smalltalk-80 virtual machine, the return address (actually the sender field) of the activation record (an instance of either class MethodContext or class BlockContext) is always in a known place, and a correct return can always be made and the machine will definitely not crash. Nonetheless, the interpreter (or primitives) may have pushed an incorrect result value or left garbage on the stack. Only later will this type of error manifest itself. These errors can be time-consuming and relatively difficult to find.

Errors resulting from conditional branch reversals are common, and are not further discussed here.
We certainly found our share of errors in the specification of the Smalltalk-80 virtual machine. This statement should not be taken as an affront to the Software Concepts Group at Xerox PARC. They were both developing and documenting two complex software products (the Smalltalk-80 system itself and the underlying virtual machine), and it was our job to point out discrepancies. Indeed, they produced an amazingly well constructed software system, and future implementors should have fewer problems with their own implementations.

We have programmed very few application programs in the Smalltalk-80 language. However, we do have one very definite data point in this area. Our file system (see Chapter 16) was totally developed in the Smalltalk-80 system and in a relatively short time period. All debugging was done using the Smalltalk-80 system: we never used the Pascal or assembly language debugging tools.

A final observation: the routines collectively known as primitives are about one-third to one-half of the implementation effort. Bear this in mind when scheduling an implementation.

## Conclusions

Our work with the Smalltalk-80 system has shown it to be a robust, well-engineered piece of software. The initial, albeit incomplete, virtual machine required six weeks of effort by three software engineers, primarily using a high-level language. This resulted in a slow but useable system. By monitoring where the virtual machine spent its time, we were able to construct a system with adequate performance. For first-time implementors, we heartily recommend a similar approach.

Without question, the Smalltalk-80 system will have a strong impact on many areas of computer science, including language design, system architecture, and user interfaces. Perhaps most importantly, the system and language cause the user to think about problems in new ways.

## Acknowledgments

Many people contributed to our Smalltalk-80 effort. Allen Wirfs-Brock designed and implemented the Pascal-based interpreters and primitives and the initial assembly language enhancements. Jason Penney designed and implemented BitBlt, the floating point package, the floppy disk driver, and the assembly-enhanced interpreters. Joe Eckardt designed our excellent bitmap display and has made interesting modifications to the Smalltalk-80 code. Tom Kloos and John Theus designed
and maintained our M68000 system, as well as the interface to the
mouse, keyboard, and floppy disks. Allen Otis graciously shared his
hardware with us in the early days of the project and made some of the
first measurements of the virtual machine. Larry Katz made many sug-
gestions for the improvement of the book and served as our unofficial
kibitzer during the implementation and provided much food for
thought. We would like to acknowledge the various managers (Jack
Grimes, Don Williams, Dave Heinen, George Rhine, and Sue Grady)
who had the foresight and wisdom to allow us to work on the project.
Glenn Krasner, of Xerox PARC, provided answers to our questions and
provided us with ideas for speeding up our implementation. And, we
would like to thank Adele Goldberg and the Software Concepts Group
of Xerox PARC for including us in the book review and implementation
process. Without them, we would have naught.

References

1. Ingalls, Daniel H. H., "Design Principles Behind Smalltalk", *Byte* vol. 6, no. 8, pp. 286-298, Aug. 1981.
<figure><img src="image_12.png" /></figure>
# The Smalltalk-80 Implementation at Hewlett-Packard

Joseph R. Falcone

James R. Stinger*

Computer Research Center
Hewlett-Packard Laboratories
Palo Alto, California

## Introduction

This report describes one of the four test sites for the Smalltalk-80 release process: a personal computing research group at the Computer Research Center of Hewlett-Packard Laboratories in Palo Alto. The following sections present a history of the work at Hewlett-Packard, an overview of our implementation, a description of the development environment, and some conclusions. A comprehensive analysis of the Hewlett-Packard implementation is in the companion paper (see Chapter 12).

## Smalltalk-80 Project at Hewlett-Packard

The Smalltalk project at Hewlett-Packard Laboratories received authorization on December 8, 1980. Beginning in November of 1981 the project slowed considerably, and the new year found nearly all development at a halt. The project officially closed on February 22, 1982, though some independent and academic work on the system continues. The im-

<footnote>*The views expressed herein are those of the authors, and do not necessarily represent the position of Hewlett-Packard or any commitment to products or services. Copyright © Joseph R. Falcone and James R. Stinger, 1982. All rights reserved.</footnote>
implementation portion of the project produced nine releases on five distinct host architectures. Documentation review and background work took one person-year of our group's time. We produced the first release of HP Smalltalk in two months, and subsequent releases followed coinciding with the availability of new Smalltalk images and new host computers. The analysis of these systems consumed another person-year.

This section describes our experience implementing a Smalltalk-80 system according to the specifications distributed during the test program. When the project began, neither the documentation nor the software was complete, a fact which profoundly influenced the duration, scope, and direction of the project.

## Project History

The first three months of the project involved reviewing chapters of the Smalltalk-80 implementation guide and selecting the first host machine for the implementation. The first few chapters covered the underlying philosophy of Smalltalk and set the ground rules for an implementation. As time passed, the chapters concerned with the specifics of implementation began to arrive.

The Smalltalk-80 language itself was the specification language used to describe the implementation. We felt that this hindered our efforts in two ways. First, it forced us to learn Smalltalk before we had our own system, and at a time when Xerox possessed the only Smalltalk-80 engines (and even those were incomplete). Second, it introduced some unwelcome ambiguity into the specification.

Initially we considered the HP 3000 Series 44 for the implementation host because of its stack architecture and position as the fastest HP processor then available (approximately 0.5 MIPS). This strategy seemed appropriate for the Smalltalk-80 virtual machine architecture as we understood it. However, after studying the matter further, we became aware of several implementation obstacles. We determined that Smalltalk would perform significantly better on the Series 44 if we put it directly on the bare machine, instead of layering it on MPE, the HP 3000 operating system. As there is a tight coupling between MPE and the microcode on the Series 44, the Smalltalk-80 virtual machine code on the bare Series 44 would have to satisfy the expectations of the microcode for MPE structures. We also were not sure how Smalltalk would behave in an environment with separate code and data segments (enforced by hardware), as is the case on the Series 44. We explored changing the microcode of the Series 44, but we felt that the task would take too much effort, especially since none of the members of the group had microcoding experience. We also considered modifying the Smalltalk-80 compiler to produce Series 44 machine code, but Xerox advised that this would be difficult without a working Smalltalk system on which to do it. Because of these problems, plus time restrictions, we decided to postpone putting Smalltalk on the HP 3000 Series 44.
Instead, we decided to implement our first Smalltalk-80 system in Pascal under TOPS-20 on a DECSYSTEM-20 mainframe. Our selection of Pascal as the implementation language reflected the investigative nature of the project. We were not sure that a strongly-typed high-level language could implement the Smalltalk-80 virtual machine as specified, and it was an interesting exercise to try to do it and find out for ourselves.

Around the middle of March we felt we had enough information about the Smalltalk-80 virtual machine to begin writing the interpreter. The first test release Smalltalk-80 image also arrived in March. The DEC-20 implementation proved sufficient and useful for the early stages when many subtle implementation points were unclear. In particular, the type and range checking in Pascal exposed many implementation problems as we progressed. Such experimentation with the manner of the implementation continued throughout the project.

By the middle of April, the first version of the object memory manager was operating. This version included dynamic memory management via reference counts. A month later, the interpreter managed to execute up to the first invocation of a primitive method. We had included a monitor which allowed us to observe the operation of the system via a motion picture display (see p. 103 for more details on the development environment). Two weeks later, on June 5, 1981, we reached a project milestone: we ran the first Smalltalk-80 test image successfully. This system on the DEC-20 became the first HP Smalltalk release.

Although the system ran, we did not have graphics capability until the middle of the summer. This used an HP 2647 terminal connected to the DEC-20 system, and unfortunately, it took 50 minutes to display a single Smalltalk screen. We knew from the start that our DEC-20 did not have a suitable graphics device, so as early as April we began to explore different approaches. We had already ordered a Lexidata 3400 bit-mapped graphics system with an HP-IB (IEEE-488) interface for the proposed HP 3000 Series 44 implementation. Using a National Instruments GPIB11-2 IEEE-488 interface, we could connect the Lexidata to the VAX-11/780 UNIX system owned by our department. After much discussion, we adopted this plan. We gained several advantages by transferring our efforts to VAX UNIX. First, it allowed us to use our Lexidata system as the graphics device. Second, it took advantage of the UNIX and C expertise of a team member. Third, and most importantly, it would give us a version of Smalltalk which could be portable across UNIX engines.

In the process of moving from the DEC-20 to the VAX, we converted the entire system from Pascal to C. We developed editor command scripts for the code conversion to automate the process as much as possible. Over the course of the next month, as we completed various parts of the system on the DEC-20, we moved them to the VAX, so that by June 19 we had transferred the entire system.
The object memory was the first part of the system transferred to UNIX. Because of its dependence on the memory architecture of the host machine, the memory manager was almost completely rewritten. A version of it was running during the first week of May. We eventually rewrote about half of the original Pascal code as part of the move to UNIX. The recoding was necessary partly for reasons of efficiency and partly to take advantage of certain VAX features. In addition to rewriting the object memory manager, we redesigned the execution monitor, the memory inspector, and the input/output routines. Most of the small, frequently-called Pascal procedures became macros. The interpreter and primitive routines remained relatively unchanged. We also integrated the object memory inspector into the execution monitor, so that one could switch between them to examine objects during debugging. By the end of the conversion process, the HP Smalltalk-80 system consisted of 7500 lines of C code. Remarkably, it executed a dozen or so instructions after its first successful compilation on UNIX.

Although some work continued on the DEC-20 Smalltalk-80 system, particularly with the graphics interface, most of our effort shifted to the UNIX version. By the end of June we had fast and slow versions of both the object memory manager and the bytecode interpreter. The fast versions coded many of the C procedures of the slow versions as macros. Although the fast versions were indeed faster, they were less useful for debugging since C debugger breakpoints could only be set on the initiation or completion of a macro, leaving the intermediate steps of the expansion inaccessible. In addition, the slow version of object memory performed much error checking which efficiency considerations had eliminated from the fast version. Once the interpreter stabilized, we discarded the slow version of it, primarily to simplify version management.

A prime reason for moving the Smalltalk system to UNIX was to take advantage of certain tools, such as the C profiling facility *prof*. It showed not only where the system was spending its time, but also how fast it was running. Using the information gained from the profiles we were able to improve the performance of the system considerably through the following techniques:

1. We used structure casts overlaying object memory for contexts and other fixed-size objects to reduce access time. After setting up the base address, these casts allow direct access of all elements of the structure.

2. We expanded small procedures with few invocations in-line.

3. We recoded *very* small procedures as macros.

4. We cached frequently accessed information in special variables, including the stack and instruction pointers as absolute addresses, and the current active context and method as base addresses.
When the second image release arrived in June, instead of abandoning the first image and focusing our attention on converting the system to run the new release, we decided to work with the first image until it was fully functional. We felt the effort would pay off when getting the system to work on subsequent image releases. Unfortunately, the purpose of the first image, as stated by Xerox, was merely to provide a vehicle for debugging the Smalltalk-80 virtual machine interpreter. Thus, there was, no documentation available on the user interface for this first image; neither did we have a complete Smalltalk source listing. Also, the Lexidata graphics system was not available until the end of June. To help ease the problem of not having any graphics output before that time, we modified the scanword primitive to display any text on the session terminal that would normally appear on the graphics device. Thus, we saw text output a full two weeks before we saw our first Smalltalk screen.

By the middle of August, keyboard input was working, including an appropriate mapping of the keys into the Smalltalk character set and a keyboard polling scheme that did not cause the system to wait for a character to be typed if none was in the buffer.

In early September we started to convert the system for the second image while finishing the implementation for the first image. After solving a number of very elusive problems, everything except floating point worked. We were able to do 32 factorial in 14 seconds, 100 factorial in 90 seconds, and 200 factorial in 360 seconds. At this point our chief concern was simply getting Smalltalk to work, and the slow operation of the system was the least of our worries.

By the end of September we had recompiled our first method in the browser, run the *Turtle demo* successfully, and managed to get the snapshot facility working. Early in October we discovered how to declare variables which permitted more sophisticated top-level programming. By the middle of October, the floating point primitives were working. One annoying problem with testing the system was that the code which executed after loading a Smalltalk snapshot refreshed all the windows and required some time-consuming reorganization on entry to the first browser pane. To get around this, we constructed *work images* which were snapshots of the system taken after these tasks had concluded. We also generated a version of the system which did not incorporate the object memory inspector or the execution monitor. We used this new sleek version for demonstrations and software development, while we continued to debug with the original system. By this time the original system contained over 10,000 lines of C code. These systems constituted the second release of HP Smalltalk and the first on VAX UNIX.

We began to make the changes necessary to run the second image in the beginning of September. By the first week in October the system executed up to the first invocation of the inputSemaphore primitive.
This was a major accomplishment since the second image had required a significant restructuring of the system. There were changes in input/output handling, primitive invocation, and process management (for multiple processes). We also discovered that some of the class Oops in the second image differed from those in the previous version. This was a recurring problem with each new release and the system would behave somewhat strangely until we remembered to check the classOops. By the end of the first week in November the system was 95% functional with the second image, and only a few unimplemented primitives remained.

At about this time, Dave Patterson, representing the University of California at Berkeley, obtained a research license from Xerox enabling him to study the Smalltalk-80 system in his graduate seminar on computer architecture. Dave requested a copy of our UNIX Smalltalk system for his studies, and upon receiving clearance from Xerox to do so, we delivered the second release HP system to him. We expended very little effort in porting the system to their VAX; it took them considerably longer to interface their graphics terminal to it. The experiences of the Berkeley Smalltalk group are discussed in Chapter 11.

By early December the system was fully operational with the second image. This system featured an early version of the new Smalltalk-80 user interface, and it became the third release of HP Smalltalk. We provided this release to Berkeley for use in their studies, since it differed significantly from the previous one.

Also in December, Xerox delivered the third Smalltalk-80 image. The system required only minor modifications for this new image, so it was running in a few days. However, there were some minor bugs that needed attention before it was fully functional. More serious were a number of problems with the Smalltalk code itself which made it necessary to revise this image release (see p. 96).

At this point we were ready to consider enhancements to the system. We added a more flexible image handler, a garbage collector, an optimized object memory system, and a method lookup cache. In addition, we implemented the `replaceFrom/to:with:startingAt:` method as a primitive to speed up string processing. The third image system with these modifications constituted the fourth release of a HP Smalltalk-80 system. The project closed shortly after this release, and there have been no significant structural changes to the system since. All project members went on to new assignments in the research center.

Cancellation was a major, but not fatal, setback as we undauntedly reached another milestone on March 13, 1982 when the system executed the `testStandardTests` benchmark without error. Nagging object memory allocator problems had thwarted previous attempts to run the complete benchmark for some time. Unfortunately, as the project had been closed for nearly a month, we could only spare a few moments
here and there to work on the system. Debugging was usually done in
pairs, and we found it particularly difficult to coordinate our schedules
now that we were all working on different projects. But we were deter-
mined to attain full functionality, and, given our limitations, it was
quite an achievement.

Two weeks later, the fourth Smalltalk-80 image arrived from Xerox.
Again, the modifications for this image were minor and took only a few
days to make. Enhancements to this version of the HP Smalltalk-80
system include an improved object memory inspector, an increase in
the speed of drawing lines by implementing the drawLoopX:Y: primitive,
and a new hard-copy facility for the Printronix line printer and the
Versatec electrostatic plotter. The system also includes a mechanism
for displaying Smalltalk screens on HP graphics terminals, at about
three minutes per image—an improvement over the previous 50 min-
utes in the first release.

On April 28, 1982 we released our fifth version of the Smalltalk-80
system, which we call *HP Labs Smalltalk-84* for historical reasons re-
lated to our internal release numbering. This version was the first
made available for use by staff at Hewlett-Packard Laboratories Com-
puter Research Center.

In parallel with the documentation and analysis of the system, we
made a number of modifications to the fifth release. Many of these
modifications were a direct result of having to explain our implementa-
tion in this and other technical reports. Documenting the system in de-
tail exposed many aspects that we had overlooked in our rush for
implementation. In addition, the battery of tests used to generate the
statistics in the companion report suggested many subtle ways to im-
prove performance. In tests this revised version of HP Smalltalk-84 exe-
cutes from 33% to 500% faster than our previous systems. We released
this sixth version on September 13, 1982.

## Overview of the System

Smalltalk is similar to other language implementations at Xerox Palo
Alto Research Center in that it has its own virtual machine. The
Smalltalk-80 virtual machine consists of a byte-oriented instruction set
or *bytecodes* together with an associated support environment. Porting
the Smalltalk-80 system to a new machine involves implementing a
Smalltalk-80 virtual machine emulator to execute bytecodes and man-
age resources such as memory, time, files, and graphics. The distribu-
tion format for the Smalltalk-80 system is an *image* or *snapshot*,
somewhat analogous to an APL workspace.
The virtual machine is in three parts: the bytecode interpreter, the primitives, and the object memory. The interpreter dispatches and executes the bytecodes. The primitives are the gateway through which the system makes requests to the underlying resource managers. The memory manager maintains a dynamic object store for the system.

The interpreter is the core of the Smalltalk-80 virtual machine emulator. The Smalltalk-80 virtual machine is an abstract architecture designed to execute Smalltalk and is similar to the P-machine of Pascal. It is a stack machine with a byte-oriented instruction set encoded chiefly to conserve space. Its most unusual aspect is the message send facility, roughly analogous to procedure call in conventional architectures. There are no computational instructions as such because message sends perform their function, with special cases to expedite the more popular ones (such as arithmetic and logical operations). The implementations of most bytecodes are only a few lines of code, but certain types of message sends require many lines of code for selector lookup and context activation, since the worst case amounts to a late-binding procedure call.

Our first implementation of the Smalltalk-80 virtual machine interpreter was a literal translation of the specification we were reviewing: each Smalltalk-80 method in the specification became a Pascal procedure in the DEC-20 version. When we moved the system to UNIX, we converted many of these procedures into C parameterized macros and consolidated several sets of interrelated procedures. These changes helped to avoid the substantial overhead of procedure invocation for most simple operations. In fact, often the consolidated code took less time than the original with the embedded procedure call. The parameterized macro facility gave us the best of both worlds—we moved many short procedures into in-line code without sacrificing the documentation value of the calling structure.

We structured the interpreter as a large switch statement encased in an instruction fetch loop. Early on we made several significant performance enhancements:

1. We moved most of the simple bytecode emulation into the switch cases to eliminate procedure call overhead (which is considerable on some hosts).

2. We cached `Oops` and addresses of the active context and method to speed up the frequent bytecode fetch and stack push/pop operations.

3. We also cached the Smalltalk-80 virtual machine instruction pointer (IP) and stack pointer (SP) in the form of C address pointers, instead of representing them as integer field offsets.