On Thu, Oct 02, 2008 at 07:01:39PM +1000, Timothy S. Nelson wrote: > On Thu, 2 Oct 2008, Tim Bunce wrote: > >> On Wed, Oct 01, 2008 at 11:24:04PM -0400, Brandon S. Allbery KF8NH wrote: >>> On 2008 Oct 1, at 22:23, Timothy S. Nelson wrote: >>>> On Wed, 1 Oct 2008, Brandon S. Allbery KF8NH wrote: >>>>> On 2008 Oct 1, at 22:14, Timothy S. Nelson wrote: >>>>>> Hi all. I've enjoyed(?) reading over the February/March thread >>>>>> entitled "Musings on operator overloading". I've brought a few thoughts >>>>>> along; if they're old news, please tell me >>>>>> here to do more reading on it :). >>>>> >>>>> The Perl6 way to do this is grammars; using an XML grammar to pull data >>>>> out of an XML document is one of Larry's favorite examples. >>>> >>>> Ok, great. While I see how this does a great job of converting the >>>> string of data into a plex, it doesn't solve the problem of selecting the >>>> data from the plex in a glob-like (or XPath-like) fashion, which is what >>>> I'm talking about here. Have I missed something that will do that? >>> >>> I could have sworn there was a short and elegant example of using a grammar >>> to extract arbitrary information from an XML document, but I don't see it >>> in the documentation. I recall Trey Harris showing such an example on IRC >>> but not in a logged channel; maybe he'll see this message and jump in, or >>> if not I'll see if I can get him to write another example. >> >> 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. >> is that he wants to extract elements of a tree-like data structure >> (think DOM), not simply from a string representation of a structure >> (such as an XML document in a string). >> >> Thinking in terms of grammars, I'd ask the question: could grammars be >> used to match tree-like data structures? I think the current answer is no. >> Grammars are too tightly bound to the concept of a position in a linear >> string. > > I think Grammars would be great for turning a string into a tree. But > I > agree with you in that I don't see how they apply to what I'm talking about > :). > >> 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. 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. Tim.
