Re: [q-lang-users] Q and Aardappel

[<Dr....@t-...>]

Hi, John,

thanks for the pointer to Wouter's PhD thesis, it's a very interesting 
read. I'm still studying it, but maybe I can already comment on some of 
your suggestions from the perspective on how they could be implemented 
for Q, so that we can further discuss it.

> 1) Specificity ordering.  AA does not assign meaning to the source-code
> order of equations; instead, a specificity meta-rule is used to order
> them.  Letting < stand for "is more specific than", the rule is
> 
> 	variable < number < atom < bag < tree

Yes, I agree that the specificity order is a nice way to resolve the 
problem with overlapping rules in different modules. Adding this to the 
Q bytecode compiler wouldn't be a big deal (just sort the rule lists 
attached to the final states in the matching automaton according to a 
different criterion). However, there's the problem with rules of equal 
specificity (in particular, if the left-hand sides of rules are equal), 
which frequently arise in sequences of conditional equations like:

fac N	= N*fac (N-1) if N>0;
	= 1 otherwise;

In Q these are actually treated as two separate equations for the same 
left-hand side fac N, which would give an error with the specificity 
order. There are other, more complex examples like this where the 
textual order seems preferable to me, especially when backtracking using 
the fail construct is involved (which admittedly is a feature that goes 
beyond standard rewriting). Now one could combine specificity and 
textual order, but I think that might be confusing for the programmer, 
so I'd rather stick with a single rule choice strategy.

> 2) Normal form declarations.  AA allows a declaration that a particular
> tree is in normal form and so not reducible.  This is essentially
> a left-hand side without a right-hand side.  This is particularly
> important in local definitions; it allows a form to be locally normal
> without worrying about whether it's globally normal as well due to a
> conflict between local and global names.

I see a problem with this approach, namely that normal forms are not 
"well-defined" anymore. If normalization using term rewriting is at the 
core of your language semantics then this is a serious issue. Especially 
if the language allows terms to be evaluated in a lazy fashion, as is 
the case in Q. Then suddenly the value of a subterm will depend on what 
context it is evaluated in, wreaking havoc on referential transparency. 
It's precisely for this reason that Q does not allow local rules, but 
only local variable definitions.

For instance, let's assume for the moment that `where' is used to 
introduce a local rule like:

foo X	= bar X where Y+Z = Y;

Let's further assume that a+b is in normal form. We have that foo (a+b) 
=> bar (a+b) by invoking the above rule. Now the local rule dictates 
that a+b => a, so the end result would be bar a, even though a+b was in 
normal form outside this rule and the foo X rule doesn't rewrite the a+b 
subterm itself. Or don't we reduce a+b because it comes from "outside"? 
But what happens then if foo is a special form, and hence the argument 
*is* evaluated in the context of the rule?

There's also a Q-specific implementation issue: When foo is a special 
form, the interpreter has to decide whether the argument of foo needs 
evaluation. The interpreter currently does some optimizations to keep 
track of terms which it already knows to be in normal form, so that it 
doesn't do any (obviously) useless reevaluations. This would not be 
possible anymore, because there's no way to predict whether a+b will 
always be a normal form -- in some rules it is, in others (like the 
above) it isn't. So it would have to reevaluate all special arguments 
anyway. This has a *huge* impact on performance; actually it would make 
special forms, as Q provides them, impractical.

As much as I'd like to have local rules in Q (I've given this feature 
some thought before), I always stumble on these semantic and 
implementation difficulties. These troubles don't arise in languages 
like Haskell because of the constructor discipline. So I think that 
local rules are a no-no in general rewriting. I'd really liked to be 
convinced otherwise, though. ;-) I'll have to take a closer look at 
Aardappel and see how it deals with this issue.

> 3) Concurrent reduction.  AA trees can be placed in unordered tree bags.
> A tree bag is in normal form iff the trees in it are, and if any of them
> are not, they are reduced concurrently.  Every tree is deemed to be in a
> bag called its container; the top-level tree is in a singleton container.

That sounds like a useful feature indeed. I'll have to take a closer 
look at this in the thesis, though, before I can come up with a more 
informed opinion. :) What are the main benefits of this approach when 
compared to traditional multithreading?

> I'd be interested to hear comments on these ideas, and
> I'll be happy to provide more details.

Thanks for bringing up these ideas, I really think that your points 
deserve further discussion. Maybe we can add some of these features to Q 
to make it better.

Cheers,
Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikwissenschaft.uni-mainz.de/~ag