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

[<jc...@re...>]

Albert Graef scripsit:

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

Thank you for the swift and hospitable response!

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

AA handles this by treating if-then-else as syntactic sugar for its
local rules (where $foo is a notation for meta-level variables and _
is an anonymous variable as in Prolog):

	if $x then $y else $z  <===>  f($x) where f(true) = $y; f(_) = $z} end

	$x when $p = $e  <===>  f($e) where f($p) = $x; f(Y) = Y end

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

Actually, I don't think it would be all that confusing, especially if
the parser provides helpful warnings.  The implementation (as opposed
to the definition) of AA falls back to document order; I think it ought
to provide a warning when it does that.

For specificity as the kind of polymorphism appropriate for tree
rewriting, see the thesis pp. 44-48 (printed page numbers as always;
add 3 for PDF page numbers).

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

AA does indeed reduce foo(a+b) to bar(a) in this case.

> But what happens then if foo is a special form, and hence the argument
> *is* evaluated in the context of the rule?

I would have no problems with disallowing local rules in special
forms altogether.  I think that would also eliminate your problem with
implementation as well, although I am not sure I understand it.

The thesis is short on examples of local rules other than those that
reduce to conditionals, which Q handles differently.  But in general
I think they are the Right Thing from the viewpoint of encapsulation;
they allow you to simplify "deep and hairy" rules.   Also, unifying
local variables, conditionals, and functional arguments is aesthetically
attractive.  See the thesis pp. 48-50.

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

The problem with traditional threads is sharing, which ends up
being done with low-level monitors or even lower-level semaphores.
Functional programming languages can be as concurrent as you want, but
they lack object identity.  AA provides object identity for containers
(tree spaces as WvO calls them), but the level of sharing is less than
that of an imperative language (where anyone can in principle observe
the current state -- local scope and objects make this better, but don't
really solve the problem) and more than that of a pure functional language
where there is no state to observe.

The thesis pp. 13-21 and pp. 51-57 are more eloquent than I can be on
the virtues of Linda-style concurrency and its applicability to tree
rewriting.

> >I'd be interested to hear comments on these ideas, and
> >I'll be happy to provide more details.
> 
> Maybe we can add some of these features to Q to make it better.

Great!

-- 
"[T]he Unicode Standard does not encode         John Cowan
idiosyncratic, personal, novel, or private      http://www.ccil.org/~cowan
use characters, nor does it encode logos        http://www.reutershealth.com
or graphics."                                   jc...@re...