[q-lang-users] Q and Aardappel

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

I've just discovered Q, and it looks extremely interesting.  I came to
eager tree rewrite languages via Wouter van Oortmessen's Aardappel
(henceforth AA), which implements much the same model but puts a GUI
face on it.  Q is a much more industrial-strength system than AA, which
is research software.  However, there are a few interesting features of
AA which I think it would be good to have in a future version of Q.

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

(I'll talk about bags later.)  Trees are ordered according to the
specificity of their first children; if that is the same, the second child
is used, and so on.  In cases where two equations are equally specific,
an error is signaled.

Using specificity ordering is a kind of analogue to the inclusion polymorphism
of methods in OO languages: more specific rules are applied before more
general ones.  In this way we can place multiple equations in different
modules without problems.

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.

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.

Equations are extended to allow a bag of patterns on the left-hand
side and a bag of results on the right-hand side.  An equation cannot
be applied (and is said to be blocked) until it is able to match and
atomically remove normal-form trees from the container of the tree
it is being applied to.  This is equivalent to a Linda IN.  After the
equation is applied, the bag of results is instantiated and placed into
the same container.  This is equivalent to a Linda OUT.

I'd be interested to hear comments on these ideas, and
I'll be happy to provide more details.	AA is documented at
http://wouter.fov120.com/files/lang/aardappel/thesis.pdf , specifically
pp. 7-17 (tree rewriting, Linda), pp. 28-38 (Aardappel), pp. 44-57
(design decisions), pp. 61-71 (formal semantics), pp. 85-89 (example).
These page numbers are the hard-copy ones; add 3 for the PDF page
numbers.)  The 1992 Q paper is cited.

-- 
A witness cannot give evidence of his           John Cowan
age unless he can remember being born.          jc...@re...
  --Judge Blagden                               http://www.ccil.org/~cowan