The Cedar ProjectJim MorrisMarch 31, 1980Background and GoalsXerox plans to develop and market office systems of increasing power and internalcomplexity. It will be necessary to develop technologies for the solution of a broad range ofoffice problems. Such systems must be composed of separable, tractable components withstandard interfaces, yet be perceived by their users as customized and integrated.To facilitate these plans, the Palo Alto Research Center's Computer Science Laboratoryproduces prototype systems that provide interactive, personal computing services. Some ofthese systems are short-lived experiments to test novel ideas, and some are solid systemsthat are used by many people. It is important that some of these systems receive usebeyond the walls of CSL and PARC; this has proved to be a powerful means of technologytransfer as well as a way for us to learn more about large, distributed systems. Besidesoffice prototypes we also develop supporting systems such as compilers, operating systemcomponents and program verifiers that are of general interest to computer scientists.At any given time there are around sixty professionals in CSL. Although they are allsophisticated programmers, they have a wide range of goals and styles: systemprogramming, mathematics, hardware design, artificial intelligence, etc. Most of them arepermanent employees who can be expected to invest effort in learning how to use aprogramming system, but an appreciable fraction are visiting scientists or computer sciencestudents who can be productive only if they can assimilate the basic system quickly.The Cedar project is an effort by CSL to produce a new programming environment. Themain goal of this new environment is to increase programmer productivity, specifically theproductivity of the programmers in CSL over the next several years. This improvement willcome from three main sources: a language system that takes more responsibility for certainprogramming tasks, programming tools that make program development and debuggingfaster, and a package library that allows programmers to build upon one another's work. Toa large extent these facilities are made possible by the increased capabilities of a new seriesof computers (D-machines) we have designed and built for our research activities. Given theprecedent of the Alto system, it is plausible that the D-machines and Cedar will be used byother groups someday. Acceptance of this specific goal and its immediacy has made us conservative in our designs.In the main, we have restricted ourselves to those ideas which can be understood and put touse by the intended users in a timely fashion. While it is our business as Computer Science#bpX&c_\ $\ W SYThe Cedar Project2researchers to strive for new and revolutionary ideas, they are not required for Cedar.Indeed, employing the users of Cedar as guinea pigs for such ideas would tend to decreasetheir programming productivity in the time frame of interest.HistoryA few years ago CSL began the process of changing its basic hardware from the Alto to D-machines, a larger, Mesa-oriented machine, and the Dorado, a very powerful machine. Asthese machines began to materialize several people saw the opportunity to make a largestride in our approach to software. Specifically, the increased capacity of the Dorado madeit possible to contemplate using much higher level programming languages and morepowerful programming tools on a personal computer. In early 1978 a group began discussing various design alternatives and developed a generalconsensus on what features a new programming environment should have. The general ideawas that we wanted to combine the best features of the Lisp/Smalltalkenvironmentsautomatic storage management, delayed binding, fast turn-around, and anintegrated environmentwith those of the Mesa languagestatic checking, explicitinterfaces, and efficient use of machine resources.Later that year a larger group met and explored the possibilities of undertaking the effortstarting from a Lisp base or a Mesa base. Eventually the choice was made to start withMesa.In 1979 a large, distributed design effort was begun on many different topics: user facilities,display packages, language changes, communications, management of large programs,filing, etc. This effort was coordinated by a steering committee and involved a substantialfraction of the laboratory personnel. An external design review was held in September. Theorganization of the implementation efforts began in the late summer of 1979 andprogramming started in the Fall.The Cedar project makes heavy use of certain core software developed by the SystemsDevelopment Department (SDD) of the Office Products Division. As starting points for Cedarwe are using their implementations of the microcode for D-machines, the Mesa language,and the Pilot operating system. The interim Mesa environment uses the Tools environmentheavily. Finally, Ed Satterthwaite, a member of the Mesa group in SDD, has been a keycontributor to the Cedar project from the beginning.Core ProjectsThe core of the Cedar project consists of four levels rising from the raw hardware of the D$cf@qXGf b? _Pr ]q= Xp TqI RT Pz++ NFC L,% I3 FF CW A!$ ?d@ =/X(Y( :3 7C 4> 2 .#< ,Q *rP (=B & 475 # B = "4 [,, '&0 4 pX qE >\2The Cedar Project3machines to the system used by the system programmers: the microcode, the Kerneloperating system, the Mesa language, and User Facilities.Moving to D-machinesA significant improvement in our programming environment comes from changing ourhardware from Altos to D-machines. Not only are these machines larger than the Alto, theysupport a fully general virtual memory, are better suited to running Mesa, and allow us to usethe Pilot operating system. Pilot brings with it a carefully designed virtual memory, a goodfile system organization, and an improved process mechanism. Making this move will requirework to adapt SDD's microcode and operating system to our needs. The microcode for the D-machines, like the hardware itself, is not actually part of the Cedarproject, but is so crucial that we include it for completeness. It implements the Mesainstruction set, performs low-level I/O functions, and implements certain time-criticaloperations associated with automatic storage allocation.The Kernel operating system provides the basic facilities of an operating system: processes,virtual memory, and a local file system. It is essentially the Pilot operating system asamended for Cedar's needs. The Kernel does not address the management directories ordistributed files very extensively.Consolidation of Programming LanguagesFor several years, programmers at PARC and elsewhere have tended to fall into two groups:systems programmers who use compiled, machine-oriented languages (BCPL or Mesa) andprogrammers who use higher level languages (Lisp, Smalltalk). Locally, the first groupproduces systems that run on the Alto and receive widespread use by non-programmers.The second group produces prototypes which contain many new ideas, but cannot be usedwidely because they do not run on Altos or because they run too slowly for a non-author'spatience. Although this diversity in programming systems has its virtues, it has somedrawbacks:The communication of ideas between these two groups is impeded by issues such asthe syntax of the respective programming languages.Maintenance of multiple languages in a changing environment is not cost-effective.It is hard to produce an integrated system if the only common denominator is thehardware or file structure.Aside from its technical objectives, Cedar is an attempt to improve this communicationwithout compromising the essential styles of programming and system development of thesetwo groups. There are many factors, technical and non-technical, affecting this objective,$cf@qXGf b: _9 [rX Wq7 U0* ST QNN OB LA I K F"5 D'I( Bl8 > R <\,- :'F 7# 3rX& /q; -%. +K )WC '#M $L "%1 }".I3AR96 )H 8 2) y>]The Cedar Project4and we have not fully come to grips with all of them.Having made the decision to start with Mesa and perceiving our design goal to be roughlythe least upper bound of Mesa and Lisp, we singled out automatic storage management,delayed binding of type information, and the ability to manipulate programs as datastructures as the most important additions. An abstract machine definition is beingdeveloped to define a convenient interface for debugging and program manipulation and aprimer for Cedar Mesa is being written.An integrated system of toolsA striking advantage of Lisp and Smalltalk over Mesa is that they have integrated, verypowerful programming environments; where Mesa is only a compiler, linker, debugger, and ahandful of run-time routines. Lisp provides quick interaction while Mesa provides morethorough static checking at a more stately pace. We hope to create an environment forMesa programming that provides tools in the spirit of InterLisp and Smalltalk. Of course,there are intrinsic trade-offs between flexiblity and static checking; we seek compromisessatisfactory on the D-machines. At a minimum we hope to learn what is intrinsic and what ismerely stylistic. The Cedar User Facilities will consist of editing and debugging toolsincorporated into an integrated framework based upon some general purpose display andwindow packages.Allied ProjectsThere are some other basic system building activities in Cedar, but they are more open-ended than the core projects, and likely to outlive the Cedar project per se.System ModelsThis effort is directed at the problem of programming in the large: how to manage a large,evolving system with multiple versions. A new language (resembling a subset of Mesa) hasbeen developed to describe how configurations of modules are put together. Animplementation that operates by generating command files and configurations is currentlyunderway.Data BasesThe immediate goal is to provide programmers with a package that permits the rapid storageand retrieval of tuples in a data base. The system uses Juniper as its filing medium. Aninitial release for this system is planned for the summer of 1980. Some applications will thenbe tried; system models may be one of them. $cf@qXGf b5 ^BI \? Y< W T Up< S<' OrX K>q M I E F M DR BlE @71) >M ;H 94! 7f 2ppX .q!6 ,_Frq (=rX $aqJ "-C . /@ E  mrX q1) ]G )_ , =[^The Cedar Project5Filing FacilitiesThe long range goal is to develop a single, integrated file system which spans personal workstations and file servers in a graceful way. Its design includes an attempt to use the workstations' disks as caches rather than as permanent repositories of information. Its only shortterm objective is to provide a local directory system for the initial release of Cedar.Problems, Short-falls, and OpportunitiesPickled valuesSince Cedar is a one-language environment we have the opportunity to extend the Mesalanguage type system to facilitate inter-machine communication as carried out via theEthernet, file storage, and data bases. Earlier work on remote procedure calls addresseditself briefly to the question, but there has not been much thinking about it recently. Weneed a scheme that permits a Mesa value to be converted to a permanent (pickled) formsuitable for transmission to another machine or data base and subsequent incorporation intoa running Mesa program.Persistent EnvironmentIt is nice to be able to save an arbitrary state of a running environment in non-volatilememory from day to day. InterLisp, Smalltalk, and JaM all provide this facility; so there is nolack of models for what we want. Providing a persistent environment calls for the language'srun-time system to have a robustness not provided by the current Mesa system. One needsto worry about smashed structures, space leaks, and fragmentation. These problems havebeen addressed on a application-by-application basis in the past, but now the system musttake more responsibility. The compacting garbage collector is crucial in this regard.Performance Analysis ToolsWe need better tools for understanding the performance of running programs. The generalphilosophy of getting the functionality right and then improving the performance is notcredible if the second step cannot be accomplished in a straightforward way.Sharing of programs and packagesOne of the major arguments put forth for static checking, explicit interfaces, modularity, etc.is that they make the sharing and maintenance of programs easier. Also, removing concernfor storage management should make many interfaces simpler and more robust. At themoment, however, we do not have a good collection of packages. A major problem we havenot yet solved is the management of the information about packagesdocumentation, bug$cf@qXGf br ^Bq\ \W Y? W; RpX( Nr Jq F H|> FH K D6% AU ?[ =v 9TrX 5xq3& 3CQ 1N .A ,B *rH (=; $rX ?q J  > L rX qN 9 oC ;W #2 b =]LThe Cedar Project6reports, plans, etc. The work underway so far on specific packages is in the area of displays, data bases, andcaching. There is a long list of other useful packages to be developed (messagetransmission, forms, history lists, direct access to disk, dictionary service, teleconferencing,audio, direct access to network, string processing, small data base manager, ...).Remote procedure callsThe ability to communicate between computers in a simple and natural way is the goal of theremote procedure call mechanism. It enables experimentation with various distributedcomputing regimes. This ability will be addressed by the group working on the kernel. $cf@qXGf b ^B0) \." Y*6 WR SrX OqK MrA K>D J=V HELVETICA  HELVETICA  HELVETICA !$j/'%`{ cedar.bravoMorrisJanuary 4, 1982 3:38 PM