Friday, January 9, 2015

The Visitor Pattern vs Object Composition

Over the last week or so, I've been going down a large refactoring of the wake compiler. And in all the hours I've spent rewriting the parse tree's data structure, I have yet to choose between two design patterns. Its possible that there is already a third that unifies the two, and if not then I'd like to share this problem as a little hole in computer science.

The design problem is as follows: say you want to traverse a binary tree.

We'd probably do something like:

class BinaryTree {
    Object item;
    BinaryTree left;
    BinaryTree right;
}

From here you have two choices. Either create your algorithms as methods on the tree:

   public Object findByPath(int binaryPath) {
       if(!binaryPath) return item;
       else if(binaryPath & 1) {
            return left.findByPath(binaryPath << 1);
        } else {
            return right.findByPath(binaryPath << 1);
        }
    }

or you could create a class for each algorithm that operates on the tree.

class BinaryPathFinder {

    public Object findByPath(BinaryTree root, int binaryPath) {
         if(!binaryPath) return root.item;
         else if(binaryPath & 1) {
             return findByPath(root.left, binaryPath << 1);
         } else {
             return findByPath(root.right, binaryPath << 1);
         }
     }
}

This could at times be the better approach -- a binary tree has many types of algorithms that could be performed on it, so this separates the algorithms from the data structure and allows users of your API to perform operations on your data that you didn't forsee.

But our tree isn't very typesafe right now. We'd be able to, for instance, set only a left node, or a right node, and/or set both nodes and a value at once. Maybe that's expected, but maybe not. Solving this typesafety is where we create the key differences between the Visitor pattern and plain 'ol object composition.

So, we can easily make it typesafe by going with the first approach:

interface BinaryTreeNode {
    public Object findByPath(int binaryPath);
}

class BinaryTreeLeaf  implements BinaryTreeNode {
    Object item;
    public Object findByPath(binaryPath) {
        return item;
     }
}

class BinaryTreeFork implements BinaryTreeNode {
    BinaryTreeNode left;
    BinaryTreeNode right;
    public Object findByPath(binaryPath) {
         ....
    }
}

But the problem is that we cannot decouple this data structure from its algorithm without actually worsening our typesafety with reverse casts and instanceof checks, turning BinaryTreeNodes into BinayTreeForks and BinaryTreeLeafs. In fact, without our algorithm's method 'findByPath(int)', our BinaryTreeNode interface would be 100% empty and 100% useless.

The Visitor pattern is a simple but clever solution to this problem.

interface BinaryTreeNode {
    public Object visit(BinaryTreeVisitor visitor);
}

interface BinaryTreeVisitor {
    public Object visit(BinaryTreeLeaf leaf);
    public Object visit(BinaryTreeFork fork);
}

class BinaryTreeLeaf implements BinaryTreeNode {
    Object item;
    public Object visit(BinayTreeVisitor visitor) {
        return visitor.visit(this);
    }
}

class BinaryTreeFork implements BinaryTreeNode {
     BinaryTreeNode left;
     BinaryTreeNode right;
     public Object visit(BinaryTreeVisitor visitor) {
         return visitor.visit(this);
     }
}

class BinaryTreeFindByPath implements BinaryTreeVisitor {
    public __construct(int binaryPath) {
        ...
    }

    public Object visit(BinaryTreeLeaf leaf) {
        ...
    }

    public Object visit(BinaryTreeFork fork) {
        ...
    }
}

Note: this may technically be a variation from the visitor pattern. The visitor pattern is often used to attach visitors to the tree in one step and then operate on it separately, while this does both in one step.

This visitor is more complicated here, because it needs to track the state of binaryPath, but the important thing is that its typesafe and decoupled. Especially assuming a stateless algorithm, this could once again be the better choice.

But there's an advantage to the non-visitor solution that gets lost once we make that change. Object composition allows us to create invisible little nifty wrapper classes around BinaryTree. For instance, we could write a quick little caching layer.

class BinaryTreeCache implements BinaryTreeNode {

    public __construct(BinaryTreeNode wrapped) { ... }
    public Object[] cache;
    public Object findByPath(int path) {
        if(cache[path]) return cache[path];
        else return wrapped.findByPath(path);
    }

}

This allows any single node (leaf or binary) to be cached, without caching all of them. You could use inheritance here, but you'd have to choose whether to extend BinaryTreeFork or BinaryTreeLeaf. With a composition based approach, you can extend a leaf, a branch, or one of your other wrapper classes, all seamlessly.

Notice that this behaviour would not work with the visitor pattern. Without extra code for detecting a change in the visitor, you would return an outdated, possibly nonsensical result. This is because we have no longer fully decoupled behaviour from the tree, and it may step on what is supposedly the visitor's job. It's supposed to be the visitors job to handle these behaviour changes, but the visitor can not easily add caching over individual nodes in as nearly elegant of a way.

You could definitely try to mix the two patterns naively, and for some things it would work. For instance, you could make a BinaryTreeNode that lazy-loads its contents from a file, which the visitor would be able to traverse without issue. But any tweaks to the behavior of your algorithm would not be guaranteed to play nicely with the visitor (timeouts, threading, probabilistics, distributing across servers).

Essentially, the object composition approach gives you the ability to separate how to configure an algorithm from the actual moment it runs. If you want a cache at every three layers and a distributed answer for every five, you can put all those if-statements into code that builds or transforms the tree, instead of putting those if-statements inside the code that operates on the tree.

Putting my rambling about the greatness of object composition aside, the advantages here specifically include:
  • Decoupling edge-case code from main use-cases
  • Separating configuration step from operations step
  • Code-driven configuration for maximum flexibility
  • Infinite layerability of edge-case wrappers
  • Easy to extend behaviour without breaking SRP
  • Small classes
  • Possibility of tree transformers that transform your configuration


By giving the visitor the responsibility of behaviour instead of the nodes, we need to be able to compose the visitor in order to compose behavior in these neat ways. But if we wrap or extend the visitor class, we end up changing the way that every leaf or branch is used. I can't see any easy ways around this.

So the question is, could the visitor pattern be upgraded to allow object composition to change the behaviour of the algorithm on a node by node basis? I'd welcome the solution, and it would live happily in the belly of the wake compiler to stand the test of time.

38 comments:

  1. Did you considered some kind of double dispatch, like in this blogpost (in german) – (here’s a english version via Google Translate)?

    ReplyDelete
    Replies
    1. the visitor pattern itself is double dispatch...maybe you're suggesting I need to like, a visitor on top of the visitor pattern, to do triple dispatch?

      Delete
  2. This comment has been removed by a blog administrator.

    ReplyDelete
  3. Thanks for your great and helpful presentation I like your good service. I always appreciate your post. That is very interesting I love reading and I am always searching for informative information like this.Also Checkout: angular 4 training in chennai | angularjs training in chennai | angularjs best training center in chennai | angularjs training in velachery

    ReplyDelete
  4. Hey, very nice site. I came across this on Google, and I am stoked that I did. I will definitely be coming back here more often. Wish I could add to the conversation and bring a bit more to the table, but am just taking in as much info as I can at the moment. Thanks .

    DedicatedHosting4u.com

    ReplyDelete
  5. Your post is very good. I got to learn a lot from your post. Thank you for sharing your article for us. it is amazing post
    what is seo
    types of seo

    ReplyDelete
  6. This is a fantastic idea! I like it a lot because it's super easy for the audience to see the value of opting in. wonderful and amazing post very use full your post thanks for sharing your article
    Android Application development
    Web application

    ReplyDelete
  7. Attend The Data Analytics Course Bangalore From ExcelR. Practical Data Analytics Course Bangalore Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analytics Course Bangalore.
    ExcelR Data Analytics Course Bangalore

    ReplyDelete
  8. Attend The Artificial Intelligence courses From ExcelR. Practical Artificial Intelligence courses Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Artificial Intelligence courses.
    ExcelR Artificial Intelligence courses

    ReplyDelete
  9. Its a great pleasure reading your post.Its full of information I am looking for and I love to post a comment that "The content of your post is awesome" Great work.
    ExcelR business analytics course in bangalore

    ReplyDelete
  10. Very nice, it’s really amazing and informative also. Visit OGEN Infosystem for Best Website Designing Company and get creative and responsive website designing.
    Best Website Designing Company in Delhi

    ReplyDelete
  11. Attend The Analytics Training Institute From ExcelR. Practical Analytics Training Institute Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Analytics Training Institute.
    ExcelR Analytics Training Institute

    ReplyDelete
  12. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    ExcelR Business Analytics Course

    ReplyDelete
  13. Excellent Blog! I would like to thank for the efforts you have made in writing this post. I am hoping the same best work from you in the future as well. I wanted to thank you for this websites! Thanks for sharing. Great websites!
    data science course in mumbai

    ReplyDelete
  14. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    data science course in mumbai

    ReplyDelete
  15. Such a very useful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.
    data analytics courses

    ReplyDelete
  16. I am a new user of this site so here i saw multiple articles and posts posted by this site,I curious more interest in some of them hope you will give more information on this topics in your next articles.
    ExcelR Artificial Intelligence course

    ReplyDelete
  17. I am a new user of this site so here i saw multiple articles and posts posted by this site,I curious more interest in some of them hope you will give more information on this topics in your next articles.
    ExcelR ai training in bangalore

    ReplyDelete

  18. Nice post. Thanks for sharing! I want people to know just how good this information is in your article. It’s interesting content and Great work.
    360DigiTMG best digital marketing courses in hyderabad

    ReplyDelete
  19. Nice post. Thanks for sharing! I want people to know just how good this information is in your blog. It’s interesting content and Great work.
    360DigiTMG digital marketing courses in hyderabad

    ReplyDelete
  20. Bài viết rất hay: Chúng tôi chuyên cung cấp các sản phẩm chất lượng sau:

    Lều xông hơi tại nhà



    Lều xông hơi hồng ngoại



    Cảm ơn các bạn!

    ReplyDelete
  21. Attend The Artificial Intelligence course From ExcelR. Practical Artificial Intelligence course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Artificial Intelligence course.
    Artificial Intelligence Course

    ReplyDelete
  22. Very interesting blog. Many blogs I see these days do not really provide anything that attracts others, but believe me the way you interact is literally awesome.You can also check my articles as well.

    Data Science In Banglore With Placements
    Data Science Course In Bangalore
    Data Science Training In Bangalore
    Best Data Science Courses In Bangalore
    Data Science Institute In Bangalore

    Thank you..

    ReplyDelete
  23. Very interesting blog. Many blogs I see these days do not really provide anything that attracts others, but believe me the way you interact is literally awesome.You can also check my articles as well.

    Data Science In Banglore With Placements
    Data Science Course In Bangalore
    Data Science Training In Bangalore
    Best Data Science Courses In Bangalore
    Data Science Institute In Bangalore

    Thank you..

    ReplyDelete
  24. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!

    data science course in vizag

    ReplyDelete
  25. Thanks for sharing nice post and nice urging commented at this place, I am in fact enjoying by these.I like visiting your site since I always come across interesting articles like this one. Keep sharing! Regards. Read more about

    selenium training in chennai

    selenium training in chennai

    selenium online training in chennai

    selenium training in bangalore

    selenium training in hyderabad

    selenium training in coimbatore

    selenium online training


    ReplyDelete
  26. Nice article...Thanks for sharing the post....
    We are providing the best master data services around the world....visit our website for more information..I am really enjoyed a lot when reading your well-written posts. It shows like you spend more effort and time to write this blog. I have saved it for my future reference. Keep it up the good work.Java training in Chennai

    Java Online training in Chennai

    Java Course in Chennai

    Best JAVA Training Institutes in Chennai

    Java training in Bangalore

    Java training in Hyderabad

    Java Training in Coimbatore

    Java Training

    Java Online Training

    ReplyDelete
  27. I like the helpful info you provide in your articles. I’ll bookmark your weblog and check again here regularly. I am quite sure I will learn much new stuff right here! Good luck for the next!
    Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.
    Azure Training in Chennai

    Azure Training in Bangalore

    Azure Training in Hyderabad

    Azure Training in Pune

    Azure Training | microsoft azure certification | Azure Online Training Course

    Azure Online Training

    ReplyDelete