Scheme & HLL (was ...m4)

[Francois-Rene Rideau]

>> * we take a semantic subset of the HLL
>> * we define a approximate representation of it into Scheme
>
> Do you mean that we define this subset of the HLL (HLL-) in such a way
> that it is a superset of Scheme (Scheme+ = HLL-), so that the HLL-
> implementation is also an implementation for Scheme and that we can
> use it to interpret the code we've started writing in Scheme ?
   I meant some HLL- (that could be extended to full HLL by reflective means)
but not a superset of Scheme (though implemented in Scheme):
there are many low-level features in Scheme
that makes such thing not wishable:
- Scheme is not expressive enough as to read/write variable,
 which makes hashed remember table based attributes a pain to program
 consistenly.
- Scheme hasn't got any clean usable standard module system
- Scheme has almost no static typing at all.
That is, while anything can be constructed as a first-level object in Scheme,
its semantics doesn't allow to restrict constructions according to any
soundness rules. It has maximal positive expressivity, but as little
negative expressivity as a cleanly semantized language allows.


> Do you really want a HLL- interpreter in Scheme ?
   Yes sir, so that all our code may be bootstrapped ASAP.

> That means writing a
> full Scheme interpreter plus the extensions for the HLL-.
   Not exactly: HLL- needs not have any direct compatibility
with Scheme, as it is not founded on the same paradigm of "locations"
as the basic abstraction.
   Nevertheless, Scheme should be expressible simply in the HLL as easily
as the HLL- is in Scheme, and starting with a very Schemish implementation
that we'd hack (and possibly completely rewrite several times) until
we reach our HLL, is a good idea.
   So yes, somehow, this may mean we write a (non-standard)
Scheme interpreter that we refine.


> Or do you want
> to extend Scheme without an interpretation layer by, for exmeple, adding
> an simple object system implemented with a few standard Scheme functions ?
> (Like I've done in the Scheme code I've writen to relace the m4 code.)
   Err, I'm not sure what you mean about "w/o an interpretation layer".
Our compiler will surely produce something that could be used as
a HLL- interpreter, for which what we'll build upon Scheme
is a first approximation.
   I think that we should use some object system over Scheme,
be it only to ease further automatic translation to whatever HLL
we'd want to use.


>> * we program a LLL compiler using the subset,
>>   that we code using this representation
>> * we gradually extend the LLL compiler
>>   so as to implement the subset of the HLL,
>>   plus essential Tunes feature not found in Scheme.
>> * we finally leap into a bootstrapped system,
>>   as the compiled system is satisfactorily powerful
> 
> So the LLL compiler is just an incomplete version of the HLL compiler ?
   Yes, what else ? Actually, the LLL is some kind of a founding run-time
for the target HLL system.
   The LLL is meant as a target abstract machine that
would help us produce good quality code in a portable way,
until we possibly refine our compiler on every ported architecture
to adapt to every architecture's peculiarities.
   It would also serve as a basis
for a possible portable execution format,
if such semi-interpreted code proves *usually* more efficient
to transport and execute than uncompiled or fat-compiled code
(which seems a reasonable though unsure assumption).
   Anyway, unless the contrary gets proven (which I think possible),
I consider that a LLL
(that is some well-documented low-level calling convention)
is a good thing.


> But what I've started writing in Scheme is a compiler.
   Great ! That's exactly what we need !
  
> There is no
> parser because there is no input program to compile.
   Parsers will come later.
   We'd write one only when there is some trivially syntaxed
parenthesized HLL-.


>>> I'm not exactly clear on what we'll do with that LLL.
>>    As I said previously, all that relates to migration require a new
>> LLL to be defined, which can't be made *efficiently* on top of a HLL
>>[...]
> I suggest we write in Scheme but what we are writing
> is a compiler which produces (eventually) machine code.
   Yes, and the LLL is precisely the low-level model for machine
code to be produced, a set of calling conventions, etc,
that allow compiled programs to interact with hand-written
low-level (founding) modules.
   The LLL needn't have currently any more syntax than the HLL- has:
let's express it in any ad-hoc way, until we invent better ways.
   Remember the Tunes motto: "semantics, not syntax, counts".

> As I pointed out earlier, a subset of the compiling functions that will
> be present in the initial Scheme compiler writen in Scheme that my
> suggestion calls for will consitute the LLL. We are writing in Scheme
> but we are not simulating distribution, GC or presistency using Scheme, we
> are compiling these features to machine code using Scheme (through a
> bunch of compiling functions (the LLL) which produce code for the
> right platform).
   We seem to agree perfectly.
Just not starting from the same point of view ;)


>> Sure we could do assembly directly, but except where performance
>> is especially needed, a portable LLL is better (at least at first).
>
> We would be doing assembly but indirectly, through a portable LLL. Do
> you understand what I have in mind when I say that we'll do that but
> in Scheme ? The LLL would be just an intermediate representation in
> the compiling process. Humm.. the pieces are starting to fit in place
> in my mind now. You suggested Forth as the LLL. Now that doesn't seeme
> that bad to me since we'd be writing in Scheme higher-level functions
> that generate Forth source and pretty soon we'd have high-level
> functions to reduce to. And it is a popular approach in the implementation
> of compilers (at least Scheme compilers) to have an intermediate stack-based
> language. But the one we used in one of my classes to build a Scheme compiler
> was pretty simple. Maybe we should define our own or at least be carefull
> not to introduce a needlessly complex intermediate language.


> Yes. That's also a very popular way of building a system. Build an
> interpreter for X first and then implemplent in X a compiler for X.
> But if we are going to do that, we need to know now what we want in
> the HLL and how to implement. And all the work done currently in
> Scheme will have to be executable in the HLL eventually. It's not
> really a problem but maybe we shouldn't go to fast doing that stuff
> because it would probably be better if it were written directly in the
> HLL subset (at least I've been using a kind of object system which
> will make the result after the translation to the HLL a bit more
> appropriate).
   As long as we are ready to rewrite in better ways,
we'd better be quick to write some code,
so we can think about how to do it better,
and rewrite in these better ways.
   What we need is such write-test-think-rewrite cycle. After all,
this is an exploratory project, not a commercial entreprise (yet ;)


> I don't want to do it over Scheme. I want to write a Scheme compiler
> in Scheme and modify the compiler and bootstrap until it is a HLL
> compiler written in HLL.
   Ok.


> And if we want to translate our Scheme sources to another language, we
> can write a Scheme program that (read)s our sources and translate them
> automatically to the new language.
   Exactly.


> The question that remains is your question : do we do as I suggested
> and start by writing a Scheme compiler in Scheme and evolve it into a
> HLL compiler in HLL, or do we start with an HLL subset for which we
> may have to write an interpreter first ?
   Maybe both:
* we write our compiler in Scheme, then
* we see how we'd like parts of it to be implemented in the HLL,
* implement the HLL construct over the Scheme interpreter, then
* add the feature to the compiler.
   Ain't it a good plan ?


> We may not have to write an interpreter if we restrict the initial HLL
> subset to things that can be defined in Scheme (like an object
> system).  This would save us a lot of time in the short term and we
> could be bootstaped earlier (we need to be bootstraped to implement
> many hot HLL features like dynamic compilation, linking and
> execution).
   It will be hard to find things that can't get defined in Scheme,
though at times we may have to make dirty uses of Scheme reflectivity
to implement encapsulation.


> If we add only a bit to what Scheme offers in our initial
> HLL subset, but still need an interpretation layer, then not only do we
> face the cost of interepreting those added constructs but we also need
> an interpreter for all those Scheme-level constructs (but maybe
> we could use a free Scheme meta-circular interpreter to eliminate
> that cost (I've writen one in my classes so we could use that)).
> Note that an interpreter will slow our development cycles.
   I hope that hygienic (and not-so-hygienic) R4RS macros will
suffice to interpret any HLL- construct needed to write the compiler.
The target HLL- language could reverse the implementation order between
what are axioms and what are "macros".
   BTW, what are available extensions to Scheme hygienic macros ?

> Even if our initial HLL subset departs from many elements of Scheme, I
> suggest we still use its syntax until the semantics are sufficiently
> stable to design an appropriate syntax (or a few of them).
  ,--
\/
(Why ain't there an agreement symbol in the ASCII set, like the sign
used in GUI boxes ? ;)


> I think I would favor adding a type/object system that does not
> require a level of interpretation (I've used one before and think
> there are others available, and we can make our own).
   I agree fully again, though I don't have precise knowledge of
the various Scheme type/object systems. I'll ask the local Scheme guru...

> What else would you want to see in our initial language rather than
> have it added later once we have started bootstraping ?
   I'd like table-implemented dynamical annotations to be added,
even if this means a hole in the automatic Scheme GC:
for what we'd use the HLL-on-Scheme, it wouldn't hurt,
while it would enable us to program using a quite freer paradigm.


> And if we define our initial HLL subset differentially from Scheme,
> what Scheme constructs do we remove ?
   To begin with we'd remove car, cdr, cons, list, vector, set-car!,
set-cdr!, set!, etc. All these are truely dirty low-level constructs.
   Of course, particularly if we implement over Scheme,
we'd encapsulate all of them in "standard library" of
typed (or not-so-typed) annotated objects.
   We'd also replace define (and hence all the let family) by constructs
that'd allow freer annotation and early typing,
that is defining objects not by their implementation
in a particular paradigm, meaningful in an implicit context,
but by free aggregation of tagged information from whatever paradigm
one chooses, whose context can be made explicit dynamically.
   (there I go with my HLL delirium again :-)

--    ,        	                                ,           _ v    ~  ^  --
-- Fare -- rideau@clipper.ens.fr -- Francois-Rene Rideau -- +)ang-Vu Ban --
--                                      '                   / .          --
Join the TUNES project for a computing system based on computing freedom !
		   TUNES is a Useful, Not Expedient System
WWW page at URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"