Scheme & HLL (was ...m4)

[Patrick Premont]

>    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.


> > Do you really want a HLL- interpreter in Scheme ?
>    Yes sir, so that all our code may be bootstrapped ASAP.
I too think we should bootstrap ASAP but my question is do
we want an interperter (something that analyses sources and
interprets), or just a bunch of "definable in Scheme"
extensions like a bunch of macros and functions.

(define (double x) (+ x x))
is an extension and in a sense it interprets the meaning of
"double" but that's not an interpreter or part of an
interpreter in my book. That'd be an interpreter :
(define (eval x)
  (if (equal? (car x) 'double)
      (apply + (map eval (cdr x)))
      ...))

> > 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.

By implementation here I assume you mean the compiler. I understand this
as an approval of the appoach I suggested a few messages earlier.

>    So yes, somehow, this may mean we write a (non-standard)
> Scheme interpreter that we refine.

And I undertand this as a modification on my approach in which we
don't start with Scheme by with something similar for which we write
an interpreter. This last refinement process you mention, I assume it
describes a process of refinement distinct from the refinement
suggested in my approach (which is the refinement of the compiler).

> > 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".

Adding functionnality without an interpretation layer is, for exemple,
defining a macro "annotation" which does what you want.
Adding functionnality with an interpretation layer is, for the
same exemple, (read)ing the source program passing it to an
(eval prog) function which you wrote and making sure that the eval function
does what you want whenever it detects the symbol 'annotation in
the program. I've illustrated the difference above with the "double"
function.

> > 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 ?

Yep. Except I'm not sure you realize that we'll be bootstraping right
after step #1. I'm assuming that by compiler you mean a Scheme compiler
(the subset we used to write it). But if we do that, that's
the approach I suggested earlier and it means that we don't need an
interpreter. We may bypass step 3 and implement the constructs directly
at step #4 by modifying the compiler. We self-compile and then the
new constructs are available, we may modify the system/compiler to use them.
Notice that at that point we already control the low-level representation
so we may already add hot features like dynamic compilation/linking.
The interpreter could be used as a test-bed if it is easier to
implement the new constructs in an interpreter rather than in a
compiler but not having to maintain two implementations is also
a considerable advantage. I think we'd be better off without
the interpreter.

Did I misinterpret your plan ? What do you think about the interpreter ?

> > 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.

What I mean by being definable in Scheme is definable w/o a layer of
interpretation. With interpretation anything can be done. But without
building an interprerter, you can't add macros that receive their
arguement unevaluated (as program fragments), manipulate them and
return the resulting program fragment which then gets evaluated automatically.
See what I mean by the layer of interpretation ?

> > 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.

So do I. Otherwise we will have to write an interpreter (by that I
mean writing a function "our-eval" that would be used like this
(our-eval (read)). So in that sense adding macros is not writing
an interpreter. That's w/o a layer of interpretation.

> 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 ?

Don't know. But I'm affraid we will need an interpretation layer.  You
mention reading and writing to variables as a feature that is lacking
is Scheme (I assume you mean some kind of first-class variables). I'm
not sure why you want that (at least for now), but that kind of thing
requires a layer of interpretation to be implemented. And if we
are going to have such a layer, we don't need to worry at all about
what power the Scheme macros offer us because we are not going
to need them. We will just add cases in the interpreter to interpret
the new constructs we want.

> > 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's your opinion on the level of interpretation. Do we need one ?
If we need one anyway we might as well implement the object system
in the interpreter.

> > 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.

We have discussed this before but I do not beleive you managed to
specify precisely what you meant by an (active/dynamic) annotation.
The HLL semantics page says that it is something that gets evaluated
with the object. I pointed out that objets don't get evaluated (except
for self-evaluating objects as a syntactic convenience so that you
don't have ot quote them), they get applied (in the case of functions)
or passed. In the case of functions, they already get to do whatever
they want when they are applied so if they want to launch a couple
of other attached functions (isn't that what annotation are ?) then
they can do that. And as for passing, I don't like the idea of making
objects concious of where they have passed and how many times. I don't
see what is gained and I fear that would be opening a can of worms because
the objects would now be able to change by themselves for no apparent
or deterministic reason (we don't care what happens to an object between
the passing an the receiving as long as it gets there unchanged).

Could you please take another shot at explaining what it is and how it
enables programming in a 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.

And what would we replace them with ? Lists and vectors could be
replaced by a type of lists which don't specify anything about their
lew-level implementation. Is that what you'd do ? Letting the system
decide what representation to use ? I think this automatic decision
won't be possible until the system is more developped.

>    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.

Annotated ? What does that mean here ?

>    We'd also replace define (and hence all the let family) by constructs
> that'd allow freer annotation and early typing,

Annotated ? What does that mean here ? (I really want to understand what
you have in mind.)

> 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 :-)

You want to do that (whatever that means :) in the first implementation
of the HLL- over Scheme (before any bootstrap) ?

These last points have been assuming that an initial implementation
of the HLL, pretty different from Scheme, would be written as an
interpreter before the Scheme (subset) compiler in Scheme (subset) is writen.
As I said earlier, as soon as we've got that compiler we can bootstrap
and we don't need the interpreter, we can start HLLizing our compiler.

Given the amount of redundancy in this message, you better not reply
to each comment separately. My main question is :
Do we need an interpreter since after step #1 (the compiler) we'll have
a bootstraped implementation to evolve into our HLL.

We've already settled other questions (which I did not reply to
since I agreed). If only we could settle this one we'd have a
pretty clear picture of what we're doing.

Patrick