Xerox PARC's Cedar
Wayne Folta
unlike Smalltalk--for which PARC spun-off a commercial producer: ParcPlace--
Cedar would be distributed Public Domain. Does anyone out there know
any details of Cedar, such as what it "looks like"? I'd also like to
know when it might be publicly available and if it might be available for
the Macintosh.
Wayne Folta (fo...@tove.umd.edu 128.8.128.42)
Steve_Ritacco
Cedar started out as Mesa, the implementation language of ViewPoint
and the Star software (among other things). It is a derivative of
Pascal but always quoted as being "industrial strength". When Mesa
became Cedar, certain features were added. A data type called "ropes",
a generic pointer type (ref. any), and a run time garbage collection
system. The name Cedar is also used for the entire programming/
productivity environment built around Cedar. If you want more info
about Cedar try looking through the past few years of ACM Transactions on
Programming languages.
Hope this is of some help!
Jef Poskanzer
}Cedar started out as Mesa, the implementation language of ViewPoint
}and the Star software (among other things).
Are you trying to attract people or frighten them away? Anyone who
knows anything about the internals of ViewPoint is now running for the
hills! But then you can write bad software in any language (Flon's
Law). Mesa was actually a damn good language. Unfortunately, the
Cedar folks basically ruined it.
Still, I'll be very happy if Xerox does release Cedar, so long as they
include sources. Then the first thing I'll do is rip out all the Cedar
junk and re-release it as Mesa (or Cedar--?).
}When Mesa
}became Cedar, certain features were added. A data type called "ropes",
}a generic pointer type (ref. any), and a run time garbage collection
}system.
Ropes (Cedar's "industrial strength" strings) are grotesque, just like
all the other interfaces the Cedar folks added to Mesa. There's an
artistry to good interface design, and the Cedar folks lacked it.
Generic pointers were in Mesa all along, and as for garbage
collection...
Adding garbage collection to a language that doesn't need it is an
admission of failure. Consider, there are two main kinds of errors
involving dynamic memory: forgetting to free an object, and referencing
an object after it has been freed. The first type is commonly called a
memory leak, and it is often easy to see (but not to find) by simply
watching the size of your program and noting that it grows over time.
The second type, often called a heap smash, is more pernicious; you
will typically only find it by accident, when you re-allocate the same
chunk of memory somewhere else in your program, and things start
failing randomly.
So what does garbage collection do? It gets rid of some memory leaks
(the kind where you put a pointer into a local variable and forget to
free it). It also converts heap smashes into memory leaks. True, your
program is now less likely to fail randomly and catastrophically; this
is a win. But it is now impossible to find any remaining memory
leaks. In the long run, your programs are *less* reliable.
It is much better to use proper programming discipline and modern
debugging tools than to punt the issue with the short term (and
expensive) fix of garbage collection.
---
Jef
Jef Poskanzer j...@helios.ee.lbl.gov ...well!pokey
"Don't worry about the world coming to an end today. It's already tomorrow in
Australia." -- Charles Schultz
Michael Rys
>Pascal but always quoted as being "industrial strength". When Mesa
>became Cedar, certain features were added. A data type called "ropes",
>a generic pointer type (ref. any), and a run time garbage collection
>system. The name Cedar is also used for the entire programming/
>productivity environment built around Cedar. If you want more info
Sounds like N. Wirth's Oberon got some of its ideas from Cedar (like GC
and the same name for OS and language...
(For information about Oberon cf Software Practise and Experience July
1988 (or around that time)).
+---------------------------------------------------------------+
| Michael Rys, V. Conzett Str. 34; CH-8004 Zuerich; Switzerland |
+---------------------------------------------------------------+
| UUCP: mr...@ethz.UUCP or EAN: mr...@ifi.ethz.ch |
| mr...@bernina.UUCP IPSANet: mrys@ipsaint |
| Voice: +41 1 242 35 87 |
+---------------------------------------------------------------+
-- Wovon man nicht sprechen kann, darueber muss man schweigen. --
Ludwig Wittgenstein, Tractatus logico-philosophicus
David Chase
>Adding garbage collection to a language that doesn't need it is an
>admission of failure. Consider, there are two main kinds of errors
>involving dynamic memory: forgetting to free an object, and referencing
>an object after it has been freed. The first type is commonly called a
>memory leak, and it is often easy to see (but not to find) by simply
>watching the size of your program and noting that it grows over time.
>The second type, often called a heap smash, is more pernicious; you
>will typically only find it by accident, when you re-allocate the same
>chunk of memory somewhere else in your program, and things start
>failing randomly.
>
>So what does garbage collection do? It gets rid of some memory leaks
>(the kind where you put a pointer into a local variable and forget to
>free it). It also converts heap smashes into memory leaks. True, your
>program is now less likely to fail randomly and catastrophically; this
>is a win. But it is now impossible to find any remaining memory
>leaks. In the long run, your programs are *less* reliable.
>
>It is much better to use proper programming discipline and modern
>debugging tools than to punt the issue with the short term (and
>expensive) fix of garbage collection.
I couldn't let this one pass. As I read it, you say that adding
garbage collection allows me to replace memory leaks and heap smashes
with memory leaks, and that is bad. I conclude that heap smashes are
good?
You should read Boehm and Weiser's SP&E paper [1] for a description
of a garbage collector that can be used with "a language that doesn't
need it" (C). Their experience was that their collector plugged more
leaks than it opened. I have used this collector, and the expense is
quite modest (typically 10% -- this may seem anomalously low, but
consider that most C programs don't allocate memory at the same
vicious rate that Lisp, ML, or Smalltalk programs do. Even so, Appel
et al make the [somewhat convincing] argument that garbage collection
is *cheaper* than alloc-free style memory management [2,3]). Using a
garbage collector, even in C, means that I don't need to worry about
smashes at all and need only worry about leaks a little, and lets me
spend time worrying about frivolous things like correctness and
algorithmic improvements. That is, I dispute the "expense" of garbage
collection; it has costs, but relatively minor ones. Furthermore,
"modern debugging tools" can do a much better job of providing
sensible information about memory leaks than they can about pointer
smashes. From a semantic point of view, a leaky program has meaning,
but trouble with its resource consumption. A pointer-smashing program
has no defined meaning, is much more difficult to reason about, and
may not even be debuggable at the "source level".
A typical memory-debugging tool maintains a hash table of the last few
PCs in a call chain, tags each block allocated with the index, and
performs the obvious reporting upon subsequent free or garbage
collection. I've done this in simple form to profile memory
allocation hot-spots, and Boehm and Weiser describe a more
sophisticated tool which turns a garbage-collector into a leak-finder
for programs which treat "free" as an assertion (this can also point
up potential pointer smashes, but this information is less reliable
because unused but still reachable pointers to memory may still exist
at the time of a garbage collection -- before you say "aha! a leak", I
should point out that any resulting leaked storage tends to get
collected during the next collection, and that Boehm and Weiser have
found that this happens comparatively rarely). For a programmer who
insists on banishing garbage collection from the finished code,
garbage collection can still serve as a development tool (and if you
claim that memory management must be designed in from the start, I'll
respond "aha! and I'll bet it doesn't make the design any easier!").
If you talk to former Cedar programmers and users (I work for one),
you will find that they insist on retaining the ability to work around
or avoid using the garbage collector in certain crucial pieces of
code, but that it is typically the memory manager of choice.
("Occasionally indispensable" does not mean "everywhere desirable").
It is also worth noting that programming takes on a different style,
given a garbage collector. Interface specifications need not include
details about whether a subroutine or its caller is responsible for
allocating or freeing a piece of storage. "Free(x)" is replaced by
"x = 0". Cleanup after errors is simpler; rather than leaking, or
requiring tedious code to undo allocations, a program can let the
garbage collector handle it.
Keep in mind that I am not arguing for a garbage collector per se, but
rather for its function. The *programmer* should see a system that
appears to be garbage-collected, but if the compiler can do away with
some of this and make it faster, so much the better.
I'm sure I'll hear more about this.
David
[1] AUTHOR = "Hans Boehm and Mark Weiser", TITLE = "Garbage Collection
in an Uncooperative Environment", JOURNAL = spe, YEAR = 1988, MONTH =
sep, PAGES={807--820}
[2] AUTHOR = "A. W. Appel and D. B. MacQueen", TITLE = "A Standard
{ML} Compiler", BOOKTITLE = FPLCA87, YEAR = 1987, PAGES = {301--324}
[3] AUTHOR = "Andrew W. Appel and John R. Ellis and Kai Li", TITLE =
"Real-time concurrent garbage collection on stock multiprocessors",
BOOKTITLE = PLDI, YEAR = 1988, PAGES= {11--20}
{PLDI = "{SIGPLAN} Symposium on Programming Language Design and
Implementation"}
{FPLCA87 = "Functional Programming Languages and Computer
Architecture"}
{spe = "Software, Practice and Experience"}
rob...@m.cs.uiuc.edu
Garbage-collection lets the machine do some of the programmer's work,
but some people argue that its more efficient to let the programmer do
this work. I suspect that eventually garbage collection will eventually
be considered an almost indispensable feature except for special purpose
machines (such as toaster controllers). Remember that similar arguments
of ``efficiency'' have been made for:
code generation (let the programmer pick op-codes)
virtual memory (let the programmer do overlays)
type checking (let the programmer find the bugs)
Of course an occasional assembly language statement, page control,
or type cast is nice, but by default I want the machine to do the work.
Arch D. Robison
University of Illinois at Urbana-Champaign
UUCP: {pur-ee,convex}!uiucdcs!robison
Internet: rob...@CS.UIUC.EDU
Bob Sperry
XDE and Viewpoint environments. My impression of this discussion is that
a number of people are "shooting from the hips". For the development of
a large software system I have not seen an environment better than
the Cedar environment. For developing robust, non-numeric code for "product"
software I have not seen a language I perfer to Mesa.
The reasons for developers leaving Xerox Parc are probably as numerous as
those that have left. Overall, I think that they were very happy with the
Cedar environment that they created, and very disillusioned with the
managements handling of their creation. The book "Fumbling the Future," only
touches the surface.
Currently, I am programming in C in a UNIX environment. Frankly, I don't
understand its popularity for a workstation. I perfer Cedar, yet I expect
to see a Cedar like environment coming from Japan long before I expect
to see one coming from Xerox. Currently, the best way for a workstation
manufacturer to differentiate themselves from the rest of the pack is
by offering a superior software environment.
Alien Wells
>I just read about Xerox PARC's newest OOPL, "Cedar". The article said that,
>unlike Smalltalk--for which PARC spun-off a commercial producer: ParcPlace--
>Cedar would be distributed Public Domain. Does anyone out there know
I was a co-op at PARC when Cedar was started, so I have some 'historical'
information that may be of interest, but I do not know anything of the
current state of its implementation.
Xerox developed (another) in-house language called 'Mesa' which was a
strongly typed language (somewhat reminescent of Pascal) with strong
modular abilities (a lot of the developers were Modula people). You
developed function prototypes through definition/interface files and
could 'plug-replace' different implementations. The facilities for
creating your own types were very nice (for its time).
Unlike Smalltalk (which Xerox 'officially' decided it had no commercial
interest in), Mesa was used extensively for in-house development work of
real products. The Xerox Star was developed in Mesa, as were a lot of the
high-end copiers Xerox was doing. I find your comment about Cedar to be
interesting, since I had thought Xerox had let Smalltalk go out public
domain while keeping Mesa proprietary (despite requests from a number
of universities and customers).
My understanding is that Cedar was started as a development environment
to surround the Mesa programming language, sort of the way the browser/etc
surrounds the Smalltalk language. Thre was a lot of talk about code-
sharing, language extensibility, environments, etc, etc. Sorry I can't
help with more, but Cedar was just getting going when I left ('80).
--
=============================================================================
A path is a terrible thing to waste ...
decvax!frog!cpoint!alien bu-cs!mirror!frog!cpoint!alien
=============================================================================
Ed Satterthwaite
add a little more history. I wrote major parts of the Mesa and Cedar
compilers (pre 1986 versions) and also take some of the credit and blame
for the language designs. I have not worked for Xerox since 1986, nor am
I currently active in the area of programming language or compiler design.
I hear rumors that there is now a version of the Cedar compiler that has
been liberated from Xerox' proprietary machine architectures. I otherwise
have no knowledge of the current state of the system or of Xerox' plans
for distribution.
Mesa is a so-called systems implementation language. It was originally
developed in the Computer Science Laboratory of Xerox PARC for programming
the Alto, but it arrived a little too late to completely displace BCPL for
that purpose. There were several generations of Mesa. The first version
was weakly typed and let the underlying hardware show through. Subsequent
versions were strongly typed and tried to abstract away from the hardware
a bit more. Although the syntax looks a lot like Pascal, the semantic
models underlying Mesa are much closer to Algol 68 (a much underrated
language) than to Pascal. The only major area in which we followed Pascal
instead of Algol 68 (variant records instead of unions) caused us no end
of subsequent grief.
Mesa has a strongly developed notion of modules that separate interface
definition and implementation, similar to Modula-2 or Ada. It preceded
both of those; in fact, Modula-2 appeared after Klaus Wirth had spent a
sabbatical period at PARC and used Mesa to write a nifty system for
interactive collaboration on design drawings. Other significant features
of Mesa include language support for lightweight processes (generally
successful), coroutines and exceptions (in retrospect, too grandiose and
baroque). It supports "object-oriented" programming for a number of
definitions of that term. It does not, however, have subclassing, except
by programmer convention and controlled breaches of the type system, so I
do not consider it a true OOP language.
To my knowledge, there is no good documentation of the Mesa language.
Despite some valiant efforts to patch it up over the years, the manual is
a disaster. Here are some references that try to convey the flavor, but
they are incomplete and obsolescent:
Geschke, Morris & Satterthwaite, Early experience with Mesa, Comm. ACM,
August 1977, 540-533.
Lauer & Satterthwaite, The impact of Mesa on system design. Proc. 4th
International Conference on Software Eng., Sept. 1979, 174-182.
Aside from providing some general intellectual stimulation, Smalltalk and
Mesa did not have much influence on one another. Smalltalk did pioneer a
lot of ideas about user interfaces and styles of interaction that later
showed up in Mesa-coded applications.
Mesa was subsequently ported to a series of Xerox workstations with
heavily microcoded architectures, the so called D-machines (Dolphin,
Dorado, Dandelion, etc.), some of which were marketed under 110x numbers.
The language was adopted by various engineering and development groups
within Xerox, most notably the ones that produced what became Star,
Viewpoint, MDE, etc. To my knowledge, Mesa was used for programming the
controller of only one high-end copier. By almost all measures, the code
was considered less satisfactory than the code written for a similar
copier in PDP-11 assembly language (a provocative result, although other
variables make it meaningless to draw strong conclusions from this).
"Cedar" is the name of both an integrated programming environment (base
system, language, support tools, set of conventions, libraries and
packages, etc.) and the language used in that environment. The former was
described by a long paper in TOPLAS several years ago; I don't have the
reference handy. The latter is an extension of Mesa. Significant
additions are automatic garbage collection and a dynamic type system based
on the notion of a universal reference (pointer) type, REF ANY. Other
postings have discussed the merits, or lack thereof, of garbage
collection; I sometimes found it very useful but tended to wave it off in
most of my own "serious" programming. REF ANY was an attempt to combine
the best features of statically and dynamically typed languages. IMHO, it
ended up achieving the worst of both worlds instead. It's unfortunate
that Modula-2+ and Modula-3 have retained REF ANY, especially since the
latter doesn't really seem to need it. In Cedar, REF ANY was widely used
in the standard interfaces, often in ugly ways that turned static errors
into dynamic ones. Its presence was also an excuse to avoid tackling
polymorphism in any really satisfactory way.
Most of the other Cedar extensions migrated back into Mesa. By
then, Mesa had accumulated a lot of fairly ugly warts and barnacles. It
would have been nice to expunge those from Cedar, but nearly all were
retained as "deprecated features" for backward compatibility. Again,
there was no really satisfactory documentation when I left in 1986. The
best approximation is a Xerox technical report:
A Description of the Cedar Language, Butler Lampson, CSL-83-15,
December 1983
but it's pretty heavy going, and the underpinnings presented in the first
few sections would now be done rather differently.
Ed Satterthwaite
e...@src.DEC.COM / {...}!decwrl!ehs
gil...@p.cs.uiuc.edu
Xerox released MESA to universities in 1985. I'm not sure what these
universities had to sign, but they were given full documentation (the
MESA programming language, the Pilot kernel operating system, and the
Tajo development environment). Big corporate customers like Boeing
were also given these things. At least 20 universities received a
grant of 20 machines or more, and the documentation. One thing that
Xerox DID NOT disclose was the architecture of the Dandelion
processor, and the microcoded machine language for the MESA processor.
In the late 1970's this was something great, but in today's world of
megabyte programs it is something incredibly crufty, like the 8088.
Cedar is PARC's guess at the programming technology of the 1990's --
they started with MESA as the basis language. MESA is a strongly
typed algorithmic language like PASCAL, with complexity that lays
between MODULA-II+ and ADA (incidentally, the DoD once asked Xerox to
disclose MESA, to avoid/help with the development of ADA. Xerox in
its infinite wisdom decided to keep MESA a secret). PARC added
features to give it the ability to be "type-safe". These features
include garbage collection, string handling, and automatic compiler
checks for the "safe" subset of the language.
One of the unique things about MESA is that you can develop dangerous
non-safe code (e.g. memory smashing is possible), and then turn on the
safety checking and debug the danger out of your code. The last thing
I heard was they were rewriting the Pilot O/S to be completely type-safe.
They were also working on a machine-independent version of the Cedar
language, called Mimosa.
Cedar is also the development environment that runs on dorados (about
the speed of a NeXT, with a turbo I/O system) . There are some really
crufty things about this environment, and some other very beautiful
things. For more information, see the many papers in the annual ACM
SOSP proceedings for the last 5 years.
Some of the amazing things of Cedar include protocol compilers, user
interface compilers, and incredible configuration management software.
But it shows it age, with some baroque drawbacks (such as a wierd file
system like the Mac's MFS, general fragility/crashability, and
language drawbacks due to the stale hardware architecture). The NeXT
user interface / development environment, which was recently written
from scratch by a development team that included many ex-Xerox
programmers, is probably cleaner and more desirable.
I was a developer in the Xerox XNS mail/clearinghouse team from summer
1984 to the summer of 1986. Anyone wish to carry the story further?
Don Gillies, Dept. of Computer Science, University of Illinois
1304 W. Springfield, Urbana, Ill 61801
ARPA: gil...@cs.uiuc.edu UUCP: {uunet,harvard}!uiucdcs!gillies
Mark Weiser
Jacobi, Kessler, and Weiser. Summary: it was hard, but we did it, and Cedar now runs on SPARC and 68020 (at least) based platforms. BTW, C makes a fine portable intermediate language if you keep it away from people.
A second paper will be appearing at the Symposium on Operating Systems Principles in December, describing the somewhat unusual portable operating system (sort of) that we built for the Cedar porting. It is general purpose, not Cedar specific, unlike the work in the paper above. This second paper is entitled "The Portable Common Runtime Approach to Interoperability", by Weiser, Demers, and hauser.
Of course, a Cedar which runs on many platforms is not yet a promise to make it universally available. Its possible we will, especially if there is lots of interest, but no definite plans yet.
I can have draft copies of either or both of the two papers sent to anyone who sends me a snail mail address.
-mark