Thank you Paul for your truly insightful response. I will try to clarify a few things though,
On Fri, Jun 22, 2012 at 7:09 PM, Paul Gearon <[email protected]> wrote: > On Fri, Jun 22, 2012 at 9:30 AM, Dimitris Spanos <[email protected]> wrote: >> Hello all, >> >> I'm trying to traverse and process the algebra expression tree for a >> SPARQL query. For this purpose, I have created a class that implements >> OpVisitor and visits the entire tree in a top-down fashion. Ideally, I >> would like to be able to pass information from a visited operator to >> its children and vice versa, but I'm not sure how I can do this in an >> elegant way (using just some global class variables does not seem >> sufficient). > > From parents to children and back up again is reasonably > straightforward. Just have the visitor keep a stack of where it's > visited (so the visitor knows about the parent to the current Op), and > accumulate results as it finishes processing an Op (so the visitor has > information about what the processing of child Ops returned). > In order for an Op to be processed and do stuff with it, I need to have a view of all its ancestors and all its descendants (for example, let's say that I want to have at hand the variables appearing in all its descendant Ops so that I know where bindings might come from and I also want to know the variables mentioned in ancestor Ops in order to be able to decide on which variables will get passed on parent Ops and finally be projected). I suppose this could be trivially implemented if it wasn't for an Op tree and the visitor pattern, since with the latter I can inspect/visit only one node at a time and I only have access to class variables that may store previously computed or intermediate results. So, my thought was to start traversing top-down (I really have no choice, do I?), and gradually get the ancestor information as every Op is visited, store it *somewhere* and as soon as reach the bottom of the tree, traverse it bottom-up to get the information from the descendants, combine it with the ancestor information already computed and proceed for every Op. One question is where can I store the intermediate results acquired through the top-down traversal and this is where the transformation that I'm considering comes into play. The nodes of the transformed tree will be mere Op extensions that would just hold the extra ancestor variable information, nothing fancy that would make tree processing more convenient. >> I guess a naive way to deal with it would be to start from the top of >> the tree, visit every Op, transform it to a custom extension of the >> respective Op that will maybe hold a link to the parent (already >> transformed) Op and store the information that will get passed to its >> children. At the same time, every such transformed Op will be inserted >> into a Stack and, after the top-down traversal is done, popped out in >> reverse order in order to go back up the tree and pass information >> from children Ops to parent Ops. > > I think that what you're describing here is a transformation of the > tree into another tree. That works, but it's more than what you said > in the first paragraph (where you just need to have results of > processing children, plus knowledge of what your parents are). > > Personally, I prefer to update the nodes in my trees so that they can > be transformed directly, rather than being mapped to an equivalent > tree before transforming. However, in the case of Op I can appreciate > why you may not want to touch the existing structure. I would go for that too and not bother with a transformation just to store the intermediate results. > If you just need the info of where you are in the tree as you process > it, then I recommend just keeping a stack in the tree walker that you > use. If you need to see "across the tree" as you're processing, then > mapping the tree to an equivalent that is more amenable to processing > (as you suggest) is preferable to modifying Op. > >> Is there another more straightforward procedure to accomplish this? > > For this kind of processing, I really, *really* prefer using Clojure > (using protocols to extend Op would make this a breeze). However, I > don't see that getting inserted into the Jena dependencies any time > soon. ;-) > Put in my "to learn" list... >> Sorry for sounding completely abstract, I hope I'm making (some) >> sense, any ideas/hints/pointers to examples would be very much >> appreciated! > > That's OK. I sometimes find that the large amounts of boilerplate that > Java requires for things like the visitor pattern can get in the way > of seeing exactly how to accomplish something. > > Paul Thanks again for the advice, now I know I'm on the right track and I'm not missing out on a cleaner solution. Dimitris
