tag:blogger.com,1999:blog-26866996.post3349987427389168905..comments2023-05-16T03:14:55.163-05:00Comments on JFKBits: Revisiting Tree Traversal PatternsUnknownnoreply@blogger.comBlogger7125tag:blogger.com,1999:blog-26866996.post-3681145760750345282012-01-05T04:56:00.438-06:002012-01-05T04:56:00.438-06:00When you iterate in the acceptor, you want to use ...When you iterate in the acceptor, you want to use a hierarchical visitor pattern http://c2.com/cgi/wiki?HierarchicalVisitorPattern instead of a regular visitor pattern. It doesn't allow you to change the traversal order but does solve your other issues.JPhttps://www.blogger.com/profile/17903447768422088280noreply@blogger.comtag:blogger.com,1999:blog-26866996.post-18858819390480948572008-01-23T01:35:00.000-06:002008-01-23T01:35:00.000-06:00barry: If I understand you from our off-line conve...barry: If I understand you from our off-line conversation, your technique lets you write just the visitor class, without needing to add the acceptor into the node classes.<BR/><BR/>That would be a bit better, especially if it allows different method signatures for different visitors. E.g. maybe an interpreter visitor's visit methods all return an Expr and a code formatter's visitor methods all return String.<BR/><BR/>The dispatch speed is another issue which would be interesting to cover sometime. It may not be quite so critical for some types of applications, if rolling your own double-dispatch lets you write a more compact structure. Standard disclaimer: it depends on what you're doing.JFKBitshttps://www.blogger.com/profile/13511809355394591863noreply@blogger.comtag:blogger.com,1999:blog-26866996.post-89281056434571416192008-01-19T14:49:00.000-06:002008-01-19T14:49:00.000-06:00What you're looking for is basically multiple disp...What you're looking for is basically multiple dispatch. The fact that most OO languages don't have them is annoying, I agree with you there.<BR/><BR/>I deal with the problem in .NET by dynamically creating code at runtime to select the correct method. I have a function which takes the visitor class (the class implementing the algorithm), and it creates a DynamicMethod instance with the right code to dispatch the different argument types to the correct methods, and it returns a delegate referencing this dynamic method.<BR/><BR/>It's not as fast as it could be with free access to the underlying platform's OO implementation, or even with help from the node classes, but it does work a lot faster than most other schemes.Barry Kellyhttps://www.blogger.com/profile/10559947643606684495noreply@blogger.comtag:blogger.com,1999:blog-26866996.post-91279246410570693932007-12-31T15:04:00.000-06:002007-12-31T15:04:00.000-06:00fabien;Your approach sounds like a callback style ...fabien;<BR/><BR/>Your approach sounds like a callback style variant, e.g. you have a general traverser to which you provide a callback which it invokes on each node. C++ functors (and the Boost.Function library) make that very easy to implement and is the style I am adopting these days. In particular, if you combined that with the multiple inheritance protocol class approach, you could even template the functor for maximal re-use. E.g., the functor takes a the protocol class type and a pointer to method and then calls the method on every node that casts to the protocol class. Then it's easy to add both new node types and new treatments.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-26866996.post-14019615595023733852007-12-29T12:51:00.000-06:002007-12-29T12:51:00.000-06:00The two styles (tree data types + external functio...The two styles (tree data types + external functions, and objects with embedded methods) are dual, and one can be mechanically translated into the other (visitor patterns are the canonical way for tree->OO translation). The catch is that a given representation is easy to extend in one dimension, and hard to extend in the other:<BR/><BR/>- in tree style, it's easy to add new treatments (new functions), and hard to add new data types (every function must be touched to add a case)<BR/><BR/>- in OO style conversely, it's easy to add new node types (create a new subclass), but hard to add new treatments (methods must be added into every class).<BR/><BR/>Unifying both styles' strengths is still an open problem. if you google `The Exression Problem' you'll find plenty of unconvincing academic papers about it :)<BR/><BR/>In the case of a language, clearly, you're more likely to have to create new treatments than new AST nodes, so you'd better pick the tree approach. The best compromize I've found yet is to provide a patchable traversal function: it explores the tree methodically without doing anything, but you can add arbitrary treatments in it, triggered by customizable predicates. I've blogged something about it here: <A HREF="http://metalua.blogspot.com/2007/12/code-walkers.html" REL="nofollow">metalua code walkers</A>. I wouldn't call it easy to use, but all the other approaches I've seen suck more :) Unsurpriaingly, patch functions use a lot of pattern matching (which is implemented as a metalua macro).<BR/>!Fabienhttps://www.blogger.com/profile/02739446213556869485noreply@blogger.comtag:blogger.com,1999:blog-26866996.post-57377625541170715862007-12-28T20:42:00.000-06:002007-12-28T20:42:00.000-06:00aog: This is helpful to think of comparing one are...aog: This is helpful to think of comparing one area to the overall effort. I'm sure I agree with you, the things you actually do to or with the nodes are more effort.<BR/><BR/>I have this memory of starting to write the umpteenth such algorithm in my compiler and wishing there was a way to abstract at least some of the boilerplate. And this was in ML, where I'm saying it's convenient. I think I did identify some algorithms where essentially an iterator is what was called for, so I could map a function over a tree.<BR/><BR/>It can also be argued that most of these traversal techniques become second nature after a while, so it really only matters when (a) teaching someone else (b) trying to remember how you did that stuff eight years ago.<BR/><BR/>Perhaps my point is simply that we do this stuff all the time, we might as well find an optimal way to do it, and what is that. It's a similar reason why folks care about map versus foreach versus for(i=0; i < max; i++) even though the body of the loop is what matters and where you put your coding effort.JFKBitshttps://www.blogger.com/profile/13511809355394591863noreply@blogger.comtag:blogger.com,1999:blog-26866996.post-3456416852810493952007-12-28T19:59:00.000-06:002007-12-28T19:59:00.000-06:00I'm not so sure. Those kinds of tree traversal are...I'm not so sure. Those kinds of tree traversal are like frictionless surfaces. Nice for illustrating a basic principle, but nothing like real life. What I find, when I do this kind of work, is that input error detection and description massively dominate the traversal logic. Making tree traversal simpler or even zero effort wouldn't make much difference to the total effort.<BR/><BR/>The only thing I have written in the last few years where the traversal was significant was a library where the traversal was so critical that it had to be hand rolled anyway, down to implementing the red-black logic.Anonymousnoreply@blogger.com