Tunes compiler

[Patrick Premont]

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

What does the context define here ? Are the patterns allowed to reference
Scheme variables ? If patterns are objects which, like all others, result
from the application of eval with an environnement (context) then all
variable references should have now been done and replaced by their value.
Does the context you mention here refer only to pattern-variables ?

How do we formalise patterns and rules ? Can we mix Scheme in them ? How ?
Take the rule assemble the add of two registers for exemple :
Do we write
(list 'ADD x y) (list #x37 (f x) (g y))
or
('ADD x y) (#x37 (f x) (g y))

And what are f and g ? Can they be Scheme closures or must they be special
functions (our bijections for exemple) so that the types or x and y may
be infered ? Which side of the rule is/are evaluted by Scheme ? When ?
Before the pattern variables have been bound ? After ? Both ?
Does that mean we can't match a function application since it will do
the call instead of interpreting it as a "program" object to be matched.
There are a whole lot of possibilities. None of them has impressed me
so far. 

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

So that bijections can be both Scheme functions which may be applied
normally and structures which contain rules.

> Why not have clean first-class patterns,
> that we can use to match objects,
> yielding bindings in first-class contexts (dictionaries) ?

My hack is independent of that. I kind-of agree with what you suggest.
Except that I'm not you what you mean by a first-class pattern (if any
object can be a pattern then why do we need to distinguish patterns ?
But maybe that's the problem. Maybe we would need to define a precise
pattern language which excludes Scheme but allows _quoted_ reference
to it (so that it isn't confused with pattern function applications
etc...) and allows normal pattern-variables references and pattern
function applications.

> 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,
I'm all for that.
> 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.

The add-rule function is not a hack. It simply modifies (side-effect)
a rule collection. The 'add-rule message in the second arguement is a
hack but is hidden and is needed (for now) to make rule-based
functions real Scheme functions (on which "apply" works).  I'm all for
having first class rules. That's what "rule" did in my exemple.  I
think that rules should be normal applicable functions also. At least
eventually. We could have a simple operator "selective union" which
takes two functions and returns a function whose value at x is the
value of the first at x if x is in its domain and otherwise is the
value of the second at x. At first, only rules or the result of
previous unions could be passed to the selective union operator
because we wouldn't know the domains of other functions but in late
versions, all HLL functions should have a domain. As such there may
be no distinction between generic function and functions. However,
there may be a need to preserve this distinction. That is if we want
to be able to modify (side-effects) generic-functions by adding
"methods" (really functions) for exemple and not want functions to
be mutable.

> Of course, all this needn't be available in the first-step bootstrap compiler.

True of course. But it would be great if the initial step extended
nicely to the general case.

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

Yes. Well put.

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

Ok. But they are really equivalent to the macro system in my meta-circular
interpreter (that I wrote, not the logical Scheme I just sent you). Replace
my "lambda-macro" by "macro" and you have the whole difference (except
for the different syntactic environements explained in macros.txt).
The "define-macro" construct is identical. Exemple
(define-macro (unless condition else then) 
  (write "Processing macro which has acces to all of Scheme's power!")
  (list 'if condition else then)
It's like a lambda but it takes unevaluated arguements and returns the
program to be evaluated.

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

Could you give an exemple ? I don't even see why you'd want to match
a lambda and "be aware" of the lambda's argument names in its body.
When does the problem arise and what is it ?

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

See above. Please pinpoint the problem. And one more question, why do
we need first-class contexts to solve it ? Or how does it solve it ?
Of course there will be contexts in the implementation but do we
really have to give them to the user and be force to consider and
implement tons of other uses ? The Scheme environements and
pattern-matching environements are not necessarily the same thing and
there are plenty of other thing the word context could mean. By saying
that you want to provide first-class contexts, do you consider all
these possibilities ? I still think that contexts are not well
defined.  They seem to change meaning with the context :) In
MIT-Scheme there are syntax-tables, environements and storage. Those
are all contexts yet are very different. All they have in common is
that they are functions.  So I think using the word context is a sure
way to blur everything and trying to implement first-class contexts as
meaningless as first-class "functions" (in the abstract mathematical
sense). It is so abstract that there is nothing to implement. Could
you try to use the more meaningful terms like interpreter,
environement, extent, substitution list, storage, logical structure,
...  whichever is appropriate in the particular situation ?

This is something which has hindered my understanding of what you
wrote for a while. Note that the definition of contexts in the
Glossary is also different. It leans towards the logical structure,
which is clearly not specified simply by an environement.

Note that I'm focusing on problems here. We agree on many crucial points.
We should keep that in mind to put the fact that we keep arguing in
the proper context :)

How about everyone else on the list ? Are you lost ? Do you have comments ?

Patrick