GUIdebook > Articles > “A Retrospective on the Development of Star”

Star, officially known as the Xerox 8010 Information System, is a workstation for professionals, providing a comprehensive set of capabilities for the office environment. The Star software consists of just over 250,000 lines of code. Its development required 93 work years over a 3.5 year period.

The development of Star depended heavily on the use of powerful personal computers connected to a local-area network and on the use of the Mesa language and development environment. An Integration Service was introduced to speed up the building of Star and to relieve the programmers of many complex, but repetitive, tasks.

In 1975, the Systems Development Department (SDD) was formed inside Xerox to effect the technology transfer of research from the Xerox Palo Alto Research Center (PARC) into mainline Xerox office products. Central to this strategy was the development of a superior professional workstation, subsequently named Star, that was to provide a major step forward in several different domains of office automation.

PARC had developed a number of experimental software development tools and office tools based on the Alto personal computer [Thacker 82]. The most important of these tools was a combined modular implementation language and interactive development environment called Mesa [Mitchell 78]. Mesa played a key role in the construction of an integrated, distributed development environment of personal computers connected by a local-area network.

The experimental office tools were the result of several research projects that had produced extensive user-interface design knowledge. But these tools were not consistent in terms of software design, implementation language or user interface. The goal of Star was to use the base of experience accumulated at PARC to build an integrated system with a uniform user interface.

The first release of Star entered the marketplace in 1981. Star provides a relatively powerful personal computer in an elegant professional workstation (electronic Desktop) connected to a 10 mega-bits-per-second (Mbps), local-area network (Ethernet [Dalai 81]). Star provides a unique user interface and comprehensive office functions [Smith 82] including multi-font text editing integrated with graphics, sophisticated interactive layout¹, electronic mail, printing and filing, as well as a “personalized” data management system.

In this paper, we generally refer to Star development in the past tense, as if it had ended with the first release. Actually, that first release has already been replaced by later releases. Star is expected to evolve as a product for several more years – adding new functions and encompassing new domains.

From the start of 1977 through the first quarter of 1978, a functional specification was written for Star. Product specifications are often overly ambitious due to pressures from the marketing organization. In the case of Star, the problem was compounded because the very charter of the development organization was to be innovative. The staff of designers and implementors aspired to build the ultimate professional workstation. Concurrent with the writing of the functional specification, two experimental prototypes were developed at a cost of approximately 15 work years.

The design of the Star software began in the spring of 1978. The first release was completed early in October of 1981. Over that period of 3.5 years, 93 work years were expended by the Star development group, including project leaders, first- and second-level managers, and software integrators. The staff grew to 20 people within the first six months and then gradually increased to 45 people over the next three years.

The progress of Star development was interrupted several times when we discovered that fundamental components of the system required redesign to meet objectives. For example, three successive designs for interactive text, graphics and page layout were implemented.

About one-fifth of Star was working by the time it was determined that a subclassing mechanism would be needed to complete the system. Such a mechanism was subsequently designed and implemented [Curry 82]. The existing Star code was converted to use this new mechanism in several phases.

The initial text display and editing implementation supported an 8-bit character space. A little over a year before the end of development, this was replaced with a new design to support a 16-bit character space, including Japanese, Chinese, Russian and European characters.

Star workstation software was built on a specialized operating system known as Pilot [Horsley 79]. For historical reasons, we include a tree-structured file system as part of Star, even though it was split off as a separate project in 1980. There were six major releases of the Pilot operating system and five major releases of the file system during the course of Star development.

Each new release of underlying software required significant changes to Star code – sometimes to take advantage of new functionality, and sometimes to adapt to radically restructured interfaces. The last major restructuring of the file system occurred only three months before the first release of Star.

The barchart below shows the size of the operational corpus of Star code over the period of its development. A plot of functionality would have roughly the same shape. Star actually shrank during the conversion to the subclassing mechanism.

The first release of Star (including the file system but not Pilot) was composed of 401 interface (definitions) modules, 440 implementation (code) modules and 88 configuration description files. The modules contained 255,000 lines of code and the compiled system consisted of 908,000 bytes of Mesa opcodes.

Altogether, we probably wrote, integrated and had working, for some period of time, in excess of 400,000 lines of code. Moreover, we expect major components of the existing system to be rewritten in the future, based on our most recently evolved insights.

The 8000 workstation hardware was developed concurrently with the Star software. The 8000 workstation had two distinct uses for Star development: as an electronic Office Desktop, which is the Star product, and as a Programmer’s Desktop – a vehicle for software development which is currently only available inside Xerox.

The 8000 workstation consists of a processing unit and a user terminal. The 8000 processor was designed to be the processor in all SDD products (the 8000 series). The processing unit is installed in a wheeled cabinet that is small enough (12”×25”×28”) to fit conveniently under a table or beside a desk. It consists of a central processor (implemented with bit-slice microprocessor technology), a rigid disk (8 mega bytes (MB) or, with a second cabinet, 24MB), a floppy disk, connections for Ethernet and user terminal, and optional controllers for other devices. The memory system implements a 22-bit virtual and 20-bit real address space. The typical memory configuration includes 512KB of RAM.

The central processor is microprogrammed, so it allows an efficient implementation of a modular, high-level language such as Mesa through the specialization of the Mesa opcodes [Johnsson 82]. The 8000 processor runs about 500,000 Mesa opcodes per second. For typical (non-floating-point) processing, the 8000 processor has about one-half the speed of a DEC VAX 11/780 processor.

The user terminal consists of an 808 raster by 1024 pixel bitmapped display, a keyboard, and a pointing device called a “mouse” [Thacker 82]. The bitmapped display and mouse are of particular significance to the functionality of Star as well as for the use of the 8000 as a programming environment.

From the beginning of Star software development, every programmer had his own Alto. Later, Altos were supplemented by a more powerful personal computer, the Dolphin. Finally, 8000 workstations replaced both Altos and Dolphins as the personal computers for programmers. About two-thirds of the Star programmers have used all three of these computers in the course of Star’s development.

	Availability	Virtual memory	Typical memory	Disk capacity	Mesa compile
Alto	1977-81	NO	256KB	5MB	2 min.
Dolphin	1979-81	YES	576KB	24MB	1.5 min.
8000	1981-	YES	512KB	24MB	1 min.

Availability is for personal use of Star developers. Compile times are for a typical 600 line program.

The Alto was very good hardware for research purposes, but it lacked virtual memory and was therefore not suitable for a sophisticated product such as Star. The Dolphin (also known as the DO) was still research hardware, but its virtual memory capability, disk capacity and user terminal put it much closer to the 8000 than the Alto was. The Dolphin’s principal use for Star development was to emulate the 8000 workstation, while the latter was under development. During 1980, Dolphins were a critical resource for Star development. One Dolphin was provided for every 3-4 programmers. While each programmer had an Alto for his programming tasks, all execution and debugging had to be done on shared Dolphins.

An important feature was that all three computers were micro-programmed to run Mesa. All three systems could be used to compile and build systems as well as to execute them. In the terminology of Brooks [Brooks 75], our two early vehicle machines were able to imitate the target machine, albeit with a certain degradation in performance. This feature accelerated Star development and provided partial independence from the delivery schedule for 8000 hardware.

All three of the hardware systems used in the development of Star were interconnected via the Ethernet. As noted above, these systems came with only modest disk capacity and with no printing capability. Our requirements for large disk storage and printing were fulfilled by server elements on the Ethernet.

For most of the development of Star, the servers were Alto-based. File servers used in Star development had between 600 and 1,200 MB of online file storage. Print servers provided between 10 and 60 pages-per-minute raster printing to personal systems on the network. Librarian servers mediated access to libraries of source files stored on file servers.

To further complicate the process of developing Star, SDD was geographically split between El Segundo and Palo Alto, California. During 1981, roughly twenty-five programmers were located in El Segundo, and ten were located in Palo Alto. Communication servers connected the El Segundo Ethernet with the Palo Alto Ethernet via a 56 Kbps leased line.

The following diagram shows the portion of the Xerox internetwork (internal, connected Ethernets) that was relevant to the development of Star.

The internetwork made large-scale resources available to geographically-separated, personal computers on a cost-effective basis. It was also essential to the Integration Service, which we discuss later.

The network link between El Segundo and Palo Alto provided high-bandwidth, inter-personal electronic communication. Through electronic mail, minor developments, which might otherwise have gone unnoticed, were broadly publicized. This constant flow of information was a primary vehicle for the implementors to keep up to date on such a large project.

Much has already been written about the advantages of using Mesa for the development of system software [Horsley 79] [Lauer 79]. Our experience with Mesa in the development of Star supported the following key points made in the earlier papers:

High-level language. This was the most obvious benefit of Mesa. It provided the ability to “say” a lot in a single statement and improved the readability of the code.

Interface definitions modules (Defs). Defs allowed use of logical software objects by client modules without any knowledge of, or dependency on, the implementation modules. Such information hiding greatly facilitated the rapid growth of Star, as well as the redesigns and re-implementations of key functions in the system. Star contained 401 Defs.

Independent compilation of modules. Star was composed of 440 implementation modules, each of which could be recompiled without recompiling any of the others. The compiled modules were bound together into a tree-structured hierarchy of 88 configurations. Only those configurations on a direct path between a recompiled implementation module and the root configuration needed to be rebound. This feature made it possible for programmers to routinely achieve six or more compile-build-test cycles per day.

Strict type enforcement. The compiler and binder found many errors that traditionally would require tedious debugging. Also, when a working part of the system was converted to new interfaces, type enforcement found most errors, allowing Star to become operational again quickly.

Coding conventions. Star developmers chose to observe a set of formally specified coding style conventions, particularly in regard to naming types and variables. While not specifically part of Mesa, these conventions were made possible by Mesa’s provision for user-defined types. The naming conventions significantly enhanced the readability of Star code.

Many papers on software engineering have noted that software tools are as critical to the effectiveness of an environment as the hardware. The key tools, ranging from the obvious to the sublime, that were part of our development environment, are listed below.²

Compiler. Read interface and implementation source modules and produced object tiles called Binary Configuration Descriptions (BCDs).

Binder. Merged implementation module BCDs and/or configuration BCDs into configuration BCDs.

IncludeChecker. Examined the partial ordering of dependencies in a set of modules and/or configurations to determine which ones must be recompiled and/or rebound, and in what order, to insure type compatibility.

Packager. Rearranged code within bound contigurations BCDs to change swapping performance.

MakeBoot. Produced a “boot file” from a BCD which contains Pilot. A boot file was the basic executable object on 8000 systems.

CoPilot. Provided interactive, source-level debugging for Mesa programs, including a variety of performance monitoring and debugging tools.

Adobe. Submited problem reports to a data base on a file server, maintained the data base, and generated data for status reports. Was used extensively to keep track of problems with hardware as well as problems with software.

Bravo/Editor/Formatter/Find/Waterlily. Created and manipulated Mesa source programs and documentation, including string searches and line-by-line file comparisons. In the future, Star itself will be used for many of these same purposes.

Lister. Produced human-readable listings of BCD contents in many different formats.

Access/Librarian. Checked modules in and out of a source library maintained on a file server via a librarian server and updated the librarian server’s data base.

FTP/FileTool/Chat/Brownie. Transfered data files between workstations and file servers.

Empress/Print. Printed source listings, documentation, etc. on print servers.

Laurel/Hardy. Used to compose, send, receive and organize electronic mail.

As mentioned previously [Horsley 79], the original Alto-based environment was highly fragmented. Each tool was a separate context to and from which the programmer had to switch. This was burdensome, due as much to the attention and keystrokes required as to the time consumed. Furthermore, these tools had been developed by many different groups. They had radical differences in user interfaces, which taxed even the adaptability of systems programmers. These programmers frequently cited the context switching and differing user interfaces as major aggravations, if not measurable deterrents to progress.

Over the years, an integrated environment – a Programmer’s Desktop – was developed. This environment provided editing, compiling, binding, debugging, etc. in multiple co-existing windows on the Desktop. This integrated environment was only available for the last few months of Star development.

The increasing cost of software as a portion of overall computer system development is a well known fact of life. SDD was committed from the start to maximize the effectiveness of a relatively scarce and expensive resource-programmers.

Gutz, Wasserman and Spier present a thorough case for providing professional programmers with personal workstations, in the context of a network of larger-scale services [Gutz 81]. The Star experience supported their case. The personal environment was a key to the high productivity of Star development. The advantages included the following:

Vehicle machine = Target machine. This condition held at two points during Star’s development: at the beginning and at the end. Almost any degree to which a personal vehicle machine can approximate the target machine is a major benefit. The one year when it was necessary to “sign up” for Dolphins was significantly more frustrating and less productive.

Reliability. The operational independence of personal computers meant that a single workstation failure affected only one person.

Consistency/Performance. Second in importance to reliability is the consistent feedback/response that a personal computer provides. “A dependable 2-h[our] turnaround is better than an average 1-h[our] turnaround with high variability.” [Mills 76] Furthermore, the 8000 processor provided computing power comparable to modest timesharing systems.

Physical environment. Personal computing in an environment rich in services provided remotely via Ethernet freed programmers from many traditional restrictions – extreme noise, cold air, etc. The power of the 8000 and of the Programmer’s Desktop reduced programmers’ reliance on printed output. Portability was certainly an option, but the capital expense of an 8000 was such that they were not made available for home use.

Staffing. Hiring talented programmers has been especially difficult in recent years. We found that being able to offer a programmer his own personal computer with a powerful set of development tools was of great benefit in attracting and holding a talented staff.

Job satisfaction. Our programmers appreciate and enjoy having sufficient computing resources readily available to make full use of their time and talents.

We also noticed a few pitfalls with personal computing. There was a tendency for individuals to isolate themselves because of the autonomy of personal computing. Without careful coordination and direction, it was easy for considerable time and effort to be wasted.

Another interesting effect was that the overhead of doing a given task could be reduced to the point where it was tempting, if not automatic, to do it without appropriate forethought. For example, when it was easy to build a new version of the system, programmers would tend to stop debugging as soon as they found the first bug rather than making the most efficient use of each debugging opportunity. Under those conditions, it was also tempting to try a quick fix for a problem rather than taking time to really understand it.

At the end of the first year of development, Star had grown to 300 modules and 67,000 lines of code. This was far more than an individual programmer could fit on his Alto disks along with the necessary tools to build the system.

Of course, not all changes required compiling all of modules in Star. In fact, most changes required only a small number of modules to be recompiled. However, binding Star and building a boot file each required most of the available disk space as well as significant amounts of time.

File servers could solve the disk space problem. However, swapping files required a large number of keystrokes and introduced opportunities for error. A lot of creative time was spent on the rather mundane task of system building.

In part, this problem could have been alleviated by a system modeling/building tool. A system modeling tool would provide a formal description of the system and a means of automatically building a new version given an arbitrary revision. Such a tool would have allowed programmers more of an option to rebuild the system themselves, particularly overnight. System modeling was – and still is – an active research topic in SDD. However, even if system bulding were completely automatic, the time involved was frequently not appopriate for a personal workstation.

After the first few months of Star development we “rediscovered” the need for integrations – versions of the system that were complete, consistent, operational, and stored on a file server for public use as a basis for development. The requirements for an Integration Service enumerated below may seem quite logical and even obvious. While we recognized a few of them from the beginning, we discovered most of them along the way – by identifying bottlenecks and by experimenting with proposed solutions that we found in the literature or (re)invented ourselves.

Initially we tried to have individual programmers perform software system integrations on a rotating basis. It became increasingly difficult for each new integrator to learn the techniques that had been developed by his predecessors.

The Integration Service permanently accepted the responsibility for producing and storing integrations and for documenting the structural and procedural aspects of integrations.

Producing an integration included the following functions, among others:

compiling the right modules in the correct order;

binding the configurations in the correct order;

correcting syntax errors; and

building an executable system.

The Integration Service was staffed with para-programmers under the direction of a programmer.

We found performing integrations to be a sub-optimal use of programming talent. Performing integrations was a specialized, repetitive task, in many ways having little to do with programming and requiring good skills for interpersonal communication. The bulk of the work of performing Star integrations was done by a single para-programmer. A second integrator was added during 1981 when the Integration Service was expanded to support development of Services products and the file system in addition to Star.

The Integration Service tested what it built to insure operability of the system.

For an integration to be useful as a base for further development, it had to operate with a sufficient, known degree of correctness. We generally required that all modules submitted to the mainline integration be “unit tested,” but as Mills points out “...the difficulties show up at system integration time. ...there is seldom difficulty in programming the pieces, the modules; the main difficulty is that the modules seldom all run together as designed.” [Mills 76]

The Star project had a separate product testing group, but it was oriented toward testing fully documented “final” products. The Integration Service was in the best position to quickly determine the level of operability of the system and then either to initiate corrective action or to inform the programmers of any pitfalls that had been discovered. Even a malfunctioning system could often be used successfully by programmers as long as each programmer could be spared the burden of having to discover each malfunction himself.

The Integration Service acquired and organized computing resources to handle the burdens of large computing tasks.

The computing resources of the Integration Service expanded gradually to include nine Altos for compiling and binding, two Dolphins for system building, and an 8000 system for checkout. In addition, integrations used a library of over 200 2.5MB Alto disk packs, a dedicated file server with 600MB of storage, and 300MB of storage on three public file servers.

By taking advantage of opportunities to automate the integration procedures, we enabled a single para-programmer to keep up to eight workstations busy building different parts of Star for several different integrations simultaneously.

The integrator’s principal interactions with the programmers were through electronic mail and a well-publicized set of uniquely named directories on file servers for each integration. The Ethernet environment allowed these forms of interaction to work equally well with programmers in El Segundo or Palo Alto, except for the degradation caused by the 56 Kbps line between sites.

The most interesting contribution of the Integration Service was its management of parallel integrations.

Most Star development was planned to follow a single thread – the mainline series of integrations. But there were several situations where we were compelled to do some development work in parallel with the mainstream until it reached stability, and then to merge it into the mainstream. We had as many as four parallel integrations in progress at the peak of Star development.

Reworks of critical parts of the system were one such situation. For example, the input handler was largely reworked 3 years into the development of Star to provide a “virtual” or “soft” keyboard capability. Untested changes could not be introduced into the mainline integration sequence without running the risk of stopping all development until the new feature was operational.

In many cases, this problem could be handled adequately by an individual on his personal workstation. However, the changes frequently affected interface definitions which had such wide compilation dependencies that the computing effort would have swamped the programmer and his workstation.

One alternative to parallel integrations was to develop stand-alone test vehicles for critical parts of the system. We only chose this alternative in a few cases. In general, we found that testing changes in parallel integrations required much less programming resources than developing and maintaining test programs.

Parallel integrations were also used when we received a new version of Mesa, Pilot or the file system – especially when interfaces changed or massive recompilations were required. We call such parallel integrations conversions.

In converting to a new version of Mesa, Pilot, the file system or to some reworked component within Star, much of the work was systematic and straightforward editing that could be performed by para-programmers. We found that this was also a good training activity for new, junior programmers. The work was fairly easy, and it provided an opportunity to expose them to Mesa, to our coding standards, and to various domains of Star in a non-threatening way.

This was another example of work that could be done by para-programmers. Most of the work was routine, given a good source comparison program and complete lists of the sources that were changed in each integration being merged.

The key to our success with this technique was our simple method of accounting for all of the source changes that went into each integration. Every source file that was modified for a particular integration was stored by the programmers on a uniquely-named directory on a file server. As the files were processed by the integrator, the original source files were moved to a different uniquely-named directory. The names of both directories included the version number of the integration for easy traceability. At the end of the integration, the second directory contained all of the files which had been changed for that integration.

The net productivity of Star development was just over 2700 lines of code per work year. This compares favorably with Brooks, who cites 1500 lines per year for a typical project with “many interactions” [Brooks 75]. Boehm’s formulas for the nominal productivity of a project delivering 250K source lines yield 2066 lines per year for “semidetached software” and 1420 lines per year for “embedded software.” Star was probably more “semidetached” than “embedded”. The main factors contributing to our productivity were as follows:

High-level language. The number of lines of assembly language code required for Star would have been larger than the Mesa code by at least a factor of three. The manpower required would have increased by an even larger factor.

Language explicitness. Manually debugging the errors caught at compile time by Mesa’s type checking could easily have doubled the duration and cost of the project.

Source-level interactive debugging. This roughly halved the debugging time, thereby increasing overall progress by about 10%.

Sophisticated development environment. We estimate that the power of our tools and the flexibility of the Programmer’s Desktop have increased our programming output by about 30%. Overall gain for the project was about 10%. The attractiveness and rarity of our personal development environment made hiring easier and reduced turnover.

Personal computers. Personal computers with adequate capacity to support the Mesa development environment were essential to the development of this particular product. We feel certain that personal computers were cost effective relative to timesharing, but we do not have an adequate basis for quantative comparison.

Integration Service and parallel integrations. Our semi-automated integration procedures made parallel integrations practical. Parallel integrations enabled us to more than double the amount of development work that could be integrated and system tested in a given period of time, with a modest increase in less-skilled manpower. We estimate that parallel integrations shortened our total development schedule by 40%.

Electronic mail. Electronic mail was extremely important to Star development because the group was geographically split. Moreover, the ease of information dissemination to a large group in a non-preemptive fashion (vs. the telephone, for example) eliminated a lot of disruptive administrative overhead at a low cost.

Star was an ambitious undertaking. The design and implementation were inherently complex and entailed many uncertainties. Many future software projects will have these same characteristics. Like Star, such projects will benefit from a Mesa-like language, a source-level debugger, a comprehensive set of development tools, personal workstations connected to a local-area network, and an Integration Service.

¹ This paper was prepared on Star. The layout, fonts and graphics, as you see them, were viewed and edited directly on Star. The original document was printed on a Xerox 8044 laser printer.

² The diversity of tool names reflects the variety of groups which contributed to the development of these tools. Most of the tools with self-explanatory names were created for the integrated Mesa development environment.

[Boehm 81] Barry W. Boehm, Software Engineering Economics, Prentice-Hall, 1981.

[Brooks 75] Frederick P. Brooks, Jr., The Mythical Man-Month, Addison-Wesley Publishing Company, 1975.

[Curry 82] Gael Curry, Larry Baer, Daniel Lipkie and Bruce Lee, “Traits – An Approach to Multiple-Inheritance Subclassing,” Proceedings of the Proceedings Conference on Office Automation Systems, Philadelphia, Pennsylvania, June 1982.

[Dalai 81] Y.K. Dalai, “The Information Outlet: A new tool for office organization,” Proceedings of the Online Conference on Local Networks & Distributed Office Systems, London, England, May 1981. Also Xerox Office Products Division, Palo Alto, California, OPD-T8104, October 1981.

[Gutz 81] Steve Gutz, Anthony I. Wasserman, and Michael J. Spier, “Personal Development Systems for the Professional Programmer,” Computer, The IEEE Computer Society, April 1981.

[Horsley 79] Thomas R. Horsley and William C. Lynch, “Pilot: A Software Engineering Case Study,” Proceedings of the 4^th International Conference on Software Engineering, The IEEE Computer Society, September 1979.

[Johnsson 82] Richard K. Johnsson and John D. Wick, “An Overview of the Mesa Processor Architecture,” Proceedings of the Symposium on Architectural Support for Programming Languages and Operating Systems, Palo Alto, California, March 1982.

[Lauer 79] Hugh C. Lauer and Edwin H. Satterthwaite, “The Impact of Mesa on System Design,” Proceedings of the 4^th International Conference on Software Engineering, The IEEE Computer Society, September 1979.

[Mills 76] Harlan D. Mills, “Software Development,” IEEE Transactions on Software Engineering, v. SE-2, no. 4, pp. 265-273, 1976.

[Mitchell 78] J.G. Mitchell, W. Maybury, and R.E. Sweet, “Mesa Language Manual,” Technical report CSL-78-1, Xerox Corporation, Palo Alto Research Center, Palo Alto, California, February 1978.

[Smith 82] David Canfield Smith, Eric Harslem, Charles Irby, and Ralph Kimball, “The Star User Interface: An Overview,” to be published in the proceedings of NCC ‘82.

[Thacker 82] C.P. Thacker, E.M. McCreight, B.W. Lampson, R.F. Sproull and D.R. Boggs, “Alto: A Personal Computer,” Computer Structures: Principles and Examples, D. Siewiorek, D.G. Bell and A. Newell, editors, McGraw-Hill, 1982.