Compiling E: Phases of Transformations
Mark S. Miller
markm@caplet.com
Mon, 07 Aug 2000 19:12:07 -0700
At 10:23 AM 8/7/00 , Dean Tribble wrote:
>... the single best paper on the subject was in 1990 or thereabouts by Will Clinger. It was concise, and had in a much more obviously simple framework many fo the transformations that looked hard in Rabbit, etc.
But which paper is it? http://www.ccs.neu.edu/home/will/papers.html is
Clinger's list of publications. From a brief look, a plausible paper may be
"Lambda, the ultimate label, or a simple optimizing compiler for Scheme".
Since access to the paper at
http://www.acm.org/pubs/citations/proceedings/lfp/182409/p128-clinger/ costs
money, I'd like to know before I buy. Does
http://www.ccs.neu.edu/home/will/Twobit/ultimate.html have all the relevant
content?
The above paper does not yet seem to have shown up on Gnutella.
>Also, Appel's ML books apply the same techniques and explain them well.
Which book?
>Note that the constrained subset may have *additional* semantics over the language (for example, in Joule, order of statements became significant after some transformation stage).
A possible quibble: Is "additional semantics" another way of saying
"constrained subset"? In your example, Is a Kernel-Joule obligated to
execute a sequence of statements in sequence a constrained subset of
Kernel-Joule? In any case, I agree with your point.
>>... Ideally,
>>all interesting platform independent aspects of compilation can be embodied
>>in the source-to-source transformation phases.
>
>As should some aspects of the platform-dependent compilation (for example, some of the named compilers go all the way to register assignment!).
Agreed. That's part of the motivation for drawing a hard line at Kernel-E.
Everything platform dependent would go below this line.
>>Each such further constrained subset can be given a name. The following are
>>the language subsets and transformations I am currently thinking about for E.
>
>I would not assume that you will name all the stages. Once you have a compiler of this architecture, it is extremely useful to occasionally insert phases that do some really trivial thing (transform the code so that the number of references to a variable are stored in a constant expression (that will eventually be eliminated as dead code) right before the variable definition. Which language would that be? Often, the phases are the same sub language, you just know more.
If you know more, then the language has additional semantics, or represents
a constrained subset, or something. Ok, perhaps it's silly to say the
encoding between a pair of is a separately named *language*, but if you know
more about the output of a stage than its input, you have an encoding with
different properties. Since each is an encoding of a program, we may as
well say these are different programming languages -- all micro-variations
of each other.
So I might name the micro-variation of E output by your transformation
VarCounted-E.
>There's also a fundamental decision to make: Should everything be represented as syntactic expressions with the language (in which case you end up with the above bizarre extra expressions that nonetheless would compile to the same program? Or, should you use richer parse nodes that can represent the meta-information (such as number of references)? In the latter case, the parse nodes would "print" as a legal program, but any meta-information would be lost (or in encoded in comments, or in explicit meta-constructs such as type declarations).
This is indeed very important. Before Joule, I'd always done compilers the
old fashioned way -- by creating lots of new data structures. Joule was my
first experience with approximately the source-to-source approach, and it
was indeed the kind of mixed approach you suggest above. When I look at
Scheme compilers (well, Rabbit & Orbit so far), I see the early phases done
in a purely source-to-source fashion (except, possibly, for hygienic macro
expansion).
I don't currently have a strong opinion, and would love more feedback on
this matter. In the meantime, I'm going to proceed with the more radical
hypothesis and see how far I get with a purely source-to-source approach.
Two caveats: My parse trees do contain two additional pieces of information beyond an obvious representation of Kernel-E-like source text:
1) Source position information. I'll deal with this further in my response to Monty's message about #line directives.
2) A cache of the StaticScope
http://www.erights.org/javadoc/org/erights/e/elang/evm/StaticScope.html
describing scoping properties derived purely from this subtree in a local
manner. (Widitive scoping info, for you Xanadu folks.) Caching this info
per node has no semantic effect. Since it is only based on the tree's
contents and not the context, and since trees are immutable, we'd always get
the same answer for the same tree.
>Something to consider here: only rename variables that would shadow other variables. Then, *most* variables don't have gobbledygook on them. Only shadowing variables need renaming. The downside would be that later transformations could result in shadowing. Hmm. I guess the best thing to do is rename with a special character such that it's easy to strip the renaming (Joule uses another technique, but it is loosely equivalent to renaming by appending to every variable name the ID (and a separator) of the syntactic scope).
Ping raised a problem with special characters, or any similar trick that
results in names the user couldn't have written: It would be nice to be able
to take the text resulting in printing a tree and paste it into the
programming environment as a working program with the same meaning.
>>The transformation from User-E to Kernel-E is standard, portable, and
>>canonical. Modulo choice of generated names, two E implementations must
>
>This seems like a bad idea (and is the real reason I wrote this message). Any legal optimization (or indeed any optimization at all that the programmer is willing to risk) should be allowed prior to this. The compiler works on behalf of the programmer; why should you limit his tools. Think of the compiler as a tool that the programmer uses to produce kernel E.
I'm not sure if we're disagreeing or misunderstanding each other. When you speak of "the programmer", which programmer are you referring to? The E implementor or the E user? I want to provide the E user as platform-independent and deterministic a spec as possible. IMO, the one significant issue that Java got mostly right that Scheme got horribly wrong is the wiggle-room in the spec. The transformation from User-E to Kernel-E done by default should be deterministic. However, if an E user wishes to run his programs through a different transformation, great.
If this doesn't resolve the issue, could you say more?
>>Below this point, the transformations are expected to be useful across
>>compilation targets, but with possible differences for different targets.
>>In any case, the following transformations are invisible to unprivileged
>>normal users of E. The virtual machine must appear to be interpreting
>>Kernel-E.
>>-------------
>>
>>Transformation: Deslotifying -- de-reify variables-as-Slots. See
>> http://www.erights.org/enative/varcases.html#deslotify
>>
>>Language: Memory-E -- variables are no more than memory locations
>>
>>Transformation: Simplification -- constant folding, dead code elimination, ...
>> Possibly, some simplifications should be mixed into
>> earlier phases as well.
>>
>>Language: Memory-E but not as stupid
>
>Definitely many of these should happen early, and this is an area where you *want* people to extend the compilation process!
On Deslotifying, I now agree. I'm going to move it above the Auditing, so
Auditable-E variables can be understood as no more than memory locations.
This makes programs that operate on programs (such as auditors) simpler.
Sometimes much simpler. I put it below the line because I though that
Deslotifying would involve some choices dependent on the target platform. I
think I was confused.
On simplifying, I should probably split this into portable mandatory
simplifications vs other, and put the first above the line as well. Question:
should auditors accept a tree from which dead code had been eliminated, if
that dead code would have failed the audit?
>>Transformation: Early Declaration -- variables declared at their
>> allocation-contour. See
>> http://www.erights.org/enative/varcases.html#scoping
>>
>>Language: E-gen -- the last stage normally represented in E parse
>> trees.
>
>Same as the above. I assumed that this happened long before "kernel" E.
Yup, good point. Early Declaration must come after Alpha Renaming and
Deslotifying, otherwise it wouldn't be semantics-preserving to move the
variable declaration earlier. So now that it looks like we'll be
Deslotifying above the line, we could do early declaration there as well.
But does this make programs easier for other programs to reason about, or is
it only relevant to compilers? If only the latter, I see no strong argument
for it to be above or below the line. I suppose, when in doubt, place it
above the line, so the virtual machine can be simpler.
>BTW a comment on platform dependent optimizations: with syntactic patterns representing register assignment, the transformed code can still be a general, portable E program that just happens to run directly and best on a particular architecture.
Cool. As my two targets of current interest are C++/ENative and
JVM-Bytecodes/ELib, I can let those targets worry about register assignments
and such. However, a similar point applies to a difference between these
two platforms. C++ doesn't have a try/finally flow control construct as
such, but it does have local object variables with destructors, where the
destructors are guaranteed to be invoked whenever a finally-clause would
have been run. Therefore, when compiling to the C++ target only, (and
therefore below the line) I think I'll transform
try {
# attempt...
} finally {
# finally-cause...
}
into
try {
# attempt...
} finally {
(define _() {# finally-cause...})()
}
The finally-clause gets turned into a first-class anonymous thunk, which can
be stored in the local object variable, for that variable's destructor to invoke.
Cheers,
--MarkM