CSL Notebook Entry: Saffron Dealer Notes
XEROX
To
From
CSL James Rauen
PARC CSL
Subject
Date
Saffron Dealer Notes August 25, 1988
Copyright © 1988 by Xerox Corporation. All rights reserved.
FOR XEROX INTERNAL USE ONLY
Abstract Cedar gives its programmers more than enough rope to hang themselves, but never quite lets them kick the chair out from underneath. The incredible maze of Cedar "features" makes it rather nontrivial to produce a coherent specification of the language, much less an implementation, much less a coherent implementation. I will describe Saffron, a compiler which attempts to be such a coherent implementation of Cedar. I will discuss my work on Saffron this summer, describe some of Cedar's "features" which make it such a joy to implement, and show some highlights from the trip I took into the depths of the abyss of Weird Cedar.
Attributes Dealer, Cedar, compiler, Casaba
References 80CSL-XXX
Updating NotebookEntryFileName
Slide 1 (Title)
Weird Cedar
James Rauen
August 31, 1988
I'll talk a little bit about the motivations behind Saffron, an experimental Cedar compiler. I'll talk about what I've been doing for the past three months...the pit...how we finally clambered out of it. How Saffron works.
Slide 2
Why another Cedar compiler?
· Demonstrate the viability of Casaba
· Principled implementation of Cedar
· Type theory
· Experiments
principled => easy to maintain.
Slide 3
What is Cedar?
· CLRM
· Mesa manual
· The implementation
· Religion
The first problem I ran into was finding a definition of Cedar. Needless to say, this wasn't an easy task. There are at least four major sources, none of which is completely suitable.
The definitive source (and definitive here is in quotation marks) is the Cedar Language Reference Manual, Butler Lampson's work. Butler's book reads like Serbo-Croatian poetry at times; if you don't know Serbo-Croatian, it's not much use although you can still appreciate it. If you ever do take the time to plow through it, you'll find that Butler presents a very elegant definition of a language which he calls Cedar. Butler's Cedar bears a very strong resemblance to the current version of Cedar we all know and love, but there are also a lot of differences. Not the least of which is that Butler's Cedar is polymorphic. So we can't just say that CLRM is the definitive definition of Cedar, not without changing our idea of what Cedar is. There are also some bugs in CLRM which no one has gotten around to fixing. I'll get to some of these later.
But CLRM isn't the only definition around. There's also the Mesa manual. If you consider Cedar to be a strict superset of Mesa, where Mesa is the subset of programs which don't have the keyword "CEDAR" in their headers, then the Mesa subset should agree with what the Mesa manual says. On the other hand, if you don't buy the argument that Mesa is a strict subset of Cedar, I still think you'd agree that Cedar constructs should behave like their Mesa counterparts whenever possible. Either way, the Mesa manual provides at least a partial definition of Cedar.
Finally, we have the Cedar Religion.
What this all boils down to is that there is no canonical definition of Cedar. So, when I say to myself, "I'm going to sit down and write a Cedar compiler," I'm at a bit of a loss to say exactly which Cedar I'm compiling.
Well, one of the problems I saw with CLRM
Slide 4
Saffron
· Front end of a compiler
· Implements Cedar/Mesa ± Religion
· Implemented in Casaba
By "implements Cedar give-or-take Religion", I mean that
Slide 5
What Saffron Does
· Type Graph
· Context Tree
· Program Graph
Body
Slide 6
Weird Cedar I
a: INT ← b; a: INT = b;
b: INT ← a; b: INT = a;
a: INT = b; a: INT ← b;
b: INT ← a; b: INT = a;
Body
Slide 7
Weird Cedar II
a: INT ← b; a: INT = b;
b: INT ← 3; b: INT = 3;
a: INT = b; a: INT ← b;
b: INT ← 3; b: INT = 3;
Body
Slide 8
Into the Abyss
Three Innocuous Features
· Sequential processing of declarations
· Dependency analysis among named constants with compile-time values
· INLINE does not affect the meaning of a program, except maybe to make it illegal
Initializations (even defaults) don't happen until declaration time. You can assign to a variable before it gets defaulted.
Slide 9
Weird Cedar III
Foo1:
CEDAR
PROGRAM =
BEGIN
Three:
PROC
RETURNS [
INT] =
INLINE { RETURN[3] };
a: INT = b;
b: INT = Three[];
c: INT ← a;
END.
Body
Slide 10
Weird Cedar IV
Foo: TYPE = INT[0..LAST[Bar]];
Bar: TYPE = INT[FIRST[Foo]..10];
x: INT ← FIRST[Bar];
Body
Slide 11
Out of the Abyss
Dependency Graph
Nodes for:
· Values of named compile-time constants
· Bodies of inline procedures
· Initialization expressions of types
· SIZE, FIRST, LAST properties of types
Topological Sort
Reject circular dependency graph
Body