Tunes compiler

[Francois-Rene Rideau]

Dear Tunespeople,
   I understand you were taken off-balance as you missed the beginning of
the discussion between Patrick and I
(I'll send it to any french-speaking taker,
but there'd still lack dumps of ytalk sessions,
which I partially kept and would be quite unreadable).
   Do not hesitate to ask for clarifications, rationale, etc.
   
   The subject is to bootstrap Tunes by the HLL rather than by the LLL,
as was tried earlier. The LLL will then be the HLL-generated
run-time system of HLL-compiled programs.
   Scheme was chosen as the basis for the HLL compiler as its trivial
syntax and small well-defined semantics let us focus on the semantics
(we can always add infix or postfix syntax later).

   So here is my reply to Patrick's last mail in this discussion...


>>> I'd say that there is no static typing. All types are dynamic concepts in
>>> Scheme. This makes efficiency a real problem for the compiler.
>>    Beyond the terminology, we agree.
>>    Shall we start with an efficient Scheme compiler like Bigloo ?
>> Maybe we could just write a front-end to the Bigloo code generator ?
> Wouldn't that prevent us from using the low level representations we want ?
   I admit I'll have to read the Bigloo sources carefully before I can say
anything. That was just a suggestion.
Depending on the way Bigloo back-end relies on flat address space
with coarse-grain memory mapping, it may or may not be a good choice.


>>    You are right. Then, either we choose to stick
>> to the original meta-language for long,
>> in which case I'd like to use a most expressive extension
>> of Scheme (rather than a least subset) as the meta-language,
> Yes.
>
>> or we choose to bootstrap the language by writing extension compilers
>> in restricted previous versions,
>
> I like that.
   Note that the two ways aren't incompatible:
instead of having a one bootstrapping sequence of extension compilers,
we could have a bootstrapping sequence of
(bootstrapping sequences of extension compilers)...


[about possibly symmetric rewrite rules as a way to program]
   Note that this provides a programming paradigm more generic than "OO",
where patterns are a cleaner way to achieve
multi-argument-dispatching methods,
where binding was left orthogonal to dispatch,
so we no more have the all-early-or-all-late binding problems of C++
(or the all-static or all-dynamic problem of dylan generic methods).
   First-class patterns with pattern-patterns and first-class contexts
allow neat reflective programming
(you can << unify (pattern1) (pattern2) in context (c1) >>)
and thus dynamically-defined partial evaluation.

> But I suggest we give them the ability to
> accept "messages" through a second optional argument. This would allow
> us to implement high-order and introspective functions on the ruled
> based functions. For exemple passing 'invert as the second arguement
> could return the inverted function.  Passing '(add-rule somerule)
> could add a rule. Then we'd hide these hacks in normal functions
> "invert" and "add-rule" which operate on rule based functions.
   I'm not sure why such hack should be used.
Why not have clean first-class patterns,
that we can use to match objects,
yielding bindings in first-class contexts (dictionaries) ?
Then it would be fairly easy to have first-class rules,
first-class generic functions,
and write a generic (invert) function to (try to) invert generic functions,
while manipulating rules based would be a matter of cleanly building
new generic functions by selecting rules, which would be quite cleaner
and more powerful than any 'add-rule hack.
Of course, all this needn't be available in the first-step bootstrap compiler.

> As Fare suggests further down, it would be nice if the pattern-matching
> engine was the basis for the future type system. [...]
> The rule based function can be seen as
> a generic function with uses a very powerful type system.
Yup. The pattern system is the very powerful type system.
By restricting the patterns a program use,
we automatically obtain a program with a stricter type system.
   By making the system as expressive as maths,
we can have programs with formal specifications.
The tactics and meta-tactics to decide if the match succeeds
(when using such expressivity, we cannot rely on decidable match algorithms)
are then a proof system.
A partial evaluator applied to the proof would extract the
"useful" computational projection of the program,
discarding the proofs of statically known match whose value is not used,
or replacing them when only their type is needed by a "type instance token",
still discarding the exact value.


> We may eventually create versions of ruled-based functions which allow
> many rules to be applicable at the same time. Many rule selection
> techniques are then possible (writing AI rule-based systems with this
> would be very appropriate). On rule selection technique could be to
> chose the rule whose matching part is subsumed by the others, the
> least general rule.  That would implement inheritance.
Yup. See above that letting rule-decision tactic open
(it needn't even be specified as deterministic)
is what allows us to build powerful formal specification systems out of it.


>> in which case we'd rather compile
>> to the host operating system before we compile to Tunes.
>
> What do you mean here ? The extension compiler is compiling from the
> extended language to the unextended language, which is most likely to
> be independent of the operating system.
Ok.

>>> We'll have to choose a particular implementation anyway for macros.
>>    Where are the docs for MIT-Scheme macros ?
>
> It is not in the reference manual. I've got a file macros.txt in my
> doc directory. This is a very recent release (7.4.2 for OS/2). Do you
> have that file ?
My distribution seemingly doesn't have the docs.
Could you mail me this file before I have a chance to download
a more complete distribution ?


>> In particular, there would be patterns to match lambda's,
> lambdas ? lambdas are source and are therefore standard s-exps which
> can be matched by any list-matching pattern. Or maybe you meant closures ?
> Right now these are closed so we can't match the closures components.
>
> Wait. I think I understand what you want. You want a pattern that will match
> any lambda's source like :
> (lambda (var args) (var body))
> But that is not a property of the pattern matching system. It is simply
> a particular pattern. Do I understand you ?
   I want the pattern matcher to be aware that in the body,
binding were extended with the variables in the lambda,
so I can achieve consistent matching of lambda's.
This just isn't trivial, and again, I see first-class context as
an easy way to achieve just this in the general case.

>> patterns to match patterns, taking contextual effects into account, etc.
>> [This is why, again, it seems to me that first-class contexts are of
>> foremost importance: to allow to easily construct such patterns].
> 
> I don't see where first-class contexts come into this.
   See above: if I want to consistently match and rewrite stuff inside
bodies of lambdas, I'd better have first-class contexts.

>>> I don't think we need modules yet (to write the compiler). The main
>>> problem they solve is that they allow many namespaces. [...]
>>> We can simply use the seperate files method [...]
>>     I'm not convinced. But let's write code and convince
>> ourselves/each-other the only truely convincing way:
>> by writing the actual compiler...
>
> Absolutely. Except that I have slightly modified my position as I now
> suggest adding the pattern-matching and rule based functions to the
> language (through an extension compiler) before we write the main
> compiler. But in a way that is writing the compiler (from the top).
> I suggest this extension because I have a very precise idea of how to
> do it (outlined earlier) and it is clearly something we need.
   If you add first-class contexts, or solve the lambda-body-matching
problem consistently without, I'm with you !

> Fare, do you understand and agree with my suggested extension ?
Yup, except for the above point.

--    ,        	                                ,           _ 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/"