On Thu, 2 Oct 2008, Tim Bunce wrote:
The key point Brandon is making, that I'm not sure you're answering,
You probably mean "OtherTim" (ie. me) instead of "Brandon" here :).
Yeap, sorry Tim.
(I've seen comments like this totally confuse everyone, so I thought
I'd better mention it. But no worries -- I'm not fussed :) ).
But I have a nagging suspicion that this is a very powerful idea.
Applying the expressive power of a grammar-like mechanism to
search, backtrack, and match within a tree-like data structure.
Is this new or has anyone discussed it before?
Not sure what you mean by "backtrack" in this context;
I was envisioning that the thing return an array of tree nodes
(although, now that I think about it, it could be useful as an
iterator too :) ). But that doesn't seem to be quite what you're
thinking, and so I'd be interested in hearing more about that too.
I'm suggesting that the same kind of logic used to find those sequences
of characters in a string that match a pattern (including backtracking
http://perldoc.perl.org/perlre.html#Backtracking) could be applied to
finding those sub-trees in a tree-like data structure which match a
pattern.
Like applying XPath to an XML DOM, only more general and taken further.
By "more general and taken further" I'm thinking of the same kind of
evoltion from simple regular expressions in perl5 to grammars in perl6.
An XPath query is like a perl5 regular expression.
The grammar concept in perl6 has taken the perl5 regular expression
"mini language" and extended it up into the perl6 langauge as classes
with method calls and features like hypothetical variables.
But perl6 grammars are tied to the concept of searching through a
sequence of characters. At any point the grammar is trying to match
against the current character position with lookahead or lookbehind.
I'm imagining a way of expressing a search through a tree-like data
structure with the same kind of richness and features as grammars
(methods, backtracking, hypothetical variables etc). Instead of
matching against "current character position" you'd be matching the
current node.
That fit in pretty well with what I was thinking, although from
possibly a slightly different angle than I'd thought of it before.
Perhaps I'm just daydreaming, or perhaps I'm thinking of bringing an
extended form of the Parrot Tree Grammar Engine to perl6:
"TGE is a tool for transforming trees. Think of it as a good
old-fashioned substitution, but instead of taking and returning strings,
it takes and returns trees."
http://search.cpan.org/~pmic/parrot-0.7.1/compilers/tge/TGE.pir
I've not looked at it closely enough to tell.
Hmm. Well, I was entirely unaware of it, so I guess that makes two of
us.
I think the following recent exchange on IRC may be relevant
(slightly edited :) ):
------------------------------------------------------------
* ruoso sees the issue of "tree grammar" appearing on the list again, and that
makes him remeber YAPC::EU::2007...
<masak> ruoso: why? (I wasn't there)
<ruoso> we had discussed this issue and we pretty much found out that XPath
and XQuery are good enough... and that we could have a XPath grammar
<ruoso> because XPath might look like being specific to XML, but it actually
isn't
<masak> no
<wayland76> Hmm
<wayland76> That's interesting :)
<wayland76> So does that mean that you're recommending that we implement
something XPath-like as a sublanguage?
<masak> it will happen
<ruoso> maybe not even XPath-like, but actually XPath
------------------------------------------------------------
I don't necessarily agree about implementing actual XPath for all tree
structures; I think XPath is pretty good for XML, but a) could be improved for
other types of trees, and b) is just a little to inflexible to be "Perl".
:)
---------------------------------------------------------------------
| Name: Tim Nelson | Because the Creator is, |
| E-mail: [EMAIL PROTECTED] | I am |
---------------------------------------------------------------------
----BEGIN GEEK CODE BLOCK----
Version 3.12
GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V-
PE(+) Y+>++ PGP->+++ R(+) !tv b++ DI++++ D G+ e++>++++ h! y-
-----END GEEK CODE BLOCK-----
