Slicing your 2D class/function matrix vertically or horizontally

Today, I want to talk about a problem that I don’t have a good solution for, and throw the floor open in the hope that someone else does.  Teach me, O commenters.

Suppose your program has to build a tree structure — for example, as the result of parsing a query in some kind of structured query language.  And suppose that, having built the tree, you want to do several different operations that involve walking that tree.  How do you design that program?

To make it concrete, consider my (rather aged) package CQL-Java, which — get ready for a big surprise — provides a CQL parser in Java.  CQL is a conceptually simple but very precise and expressive query language used in information retrieval, but for our current purposes all we need to know is that it supports structured boolean queries like these:

kernighan
kernighan and ritchie
(kernighan and ritchie) or fowler
kernighan and (ritchie or pike)

Our task is to parse such queries, and to be able to render them out either in an XML format called XCQL or in Index Data’s ugly but functional Prefix Query Format.

I guess we can all agree that we want an API something like this:

abstract class CQLParser {
  Node compile(String textualQuery);
}
class Node {
  String toXCQL();
  String toPQF();
}

And that the Node object returned from the parser is the root of a tree of nodes which represent the parse tree, where nodes can be of types And, Or and Term.  (In reality there are lots of other kinds of node, too, the we can ignore them for our purposes.)

Assuming that we’ve written the actual parser, the question becomes, where do we put the code that generates the formatted textual output that becomes the XCQL and PQF?  In the old days, especially if we were used to writing C, we’d have a pair of functions defined on the Node class, both switching on the node’s type and looking more or less like this:

Class Node {
  String toPQF() {
    if (type == AND) {
      return "@and " + left.toPQF() + " " + right.toPQF();
    } else if (type == OR) {
      return "@or " + left.toPQF() + " " + right.toPQF();
    } else {
      return term;
    }
  }
}

These days, of course, no-one would be so crass.  We’ve all read Fowler’s Refactoring, and we know that Switch Statements Are Evil.  In particular, we’ve read Fowler’s page 223, the introduction to his Replace Type Code with Subclasses refactoring, and we remember that it says:

Switches or if-then-else constructs […] test the value of the type code and then execute different code depending on the value of the type code.  Such conditionals need to be refactored with Replace Conditional with Polymorphism […]  The advantage of Replace Type Code with Subclasses is that it moves knowledge of the variant behaviour from clients of the class to the class itself.  If I add new variants, all I need to do is add a subclass.  Without polymorphism I have to find all the conditionals and change those.

So we’d be more likely to make Node an abstract class, and derive three subclasses, AndNode, OrNode and TermNode.  Then each of those subclasses would have its own little toPQF() method — and toXCQL() — and the Evil Switch Statement is avoided:

class AndNode extends Node {
  Node left, right;
  String toPQF() {
    return "@and " + left.toPQF() + " " + right.toPQF();
  }
}

class OrNode extends Node {
  Node left, right;
  String toPQF() {
    return "@or " + left.toPQF() + " " + right.toPQF();
  }
}

class TermNode extends Node {
  String term;
  String toPQF() {
    return term;
  }
}

And all is well with the world.

Or is it?

It’s certainly true, as Fowler points out, that if you later need to add support for a new node-type — let’s say a unary NOT node — you can do that by making a single new subtype, NotNode, say, and tweaking the parser to generate it.  Then the PQF generator is extended by the addition of NotNode::toPQF(), which returns “@not ” + subtree.toPQF().  It’s neat, clean and satisfying.

The problem comes when you want to add a new back-end — for example, when you want to be able to translate CQL into the query language of the Solr database.  Now that our Node class is split into four subclasses (and in reality, many more), we have to mess with all of those subclasses, adding a toSolr() method to each of them.  Whereas if we’d stayed with the old-fashioned single-node-class-with-a-type-indicator representation, we’d have to add only a single new method, Node::toSolr().

In fact, I am going to take the low road here, and rewrite the Fowler quote above:

Such class hierarchies need to be refactored with Replace Polymorphism with Conditional […]  The advantage of Replace Subclasses with Type Code is that it centralises knowledge of the variant behaviour from being spread among many classes to concentrated in one.  If I add new operations, all I need to do is add a method.  With polymorphism I have to find all the subclasses and change those.

To be clear, I am not saying that the single-class-with-type-indicator approach is always and necessarily better.  But I am a bit mystified that the subclasses-with-polymorphism is so universally and uncritically accepted as The Right Way, All The Time.

Even Fowler, who to his credit is usually careful not to insist on a One Right Way, seems to lose his moral compass when it comes to this particular design choice.  Although I’ve been critical of the more unthinking Fowlerite followers, I actually really like lots of things about Fowler himself: for example, his catalog of refactorings includes several complementary pairs, showing that he doesn’t in general consider that there is One Right Way.  (Pairs include: Extract Method vs. Inline Method; Hide Delegate vs. Remove Middle Man; Change Value to Reference vs. Change Reference to Value.)  But against this backdrop, his insistence that conditionals should always be replaced by polymorphism (note the imperative “need to be” in the quote above) is all the more puzzling.

The situation is this: when you have to implement n functions (such as the toPQF()toXCQL() and toSolr() methods above) across a class hierarchy of m classes (such as the AndNode, OrNode, TermNode and NotNode classes above), you need n×m code fragments — one to implement each function for each class.  The old-fashioned approach uses n functions each consisting of a switch statement covering the m versions; the fashionable approach uses n×m small methods, split across the m classes — which in practice always seems to mean m different source files, at least if you’re writing Java.  It seems to me that the choice of which is better depends on the relative sizes of n and m, and on how likely each is to change.  If you’re going to need lots of new types, then, yes, a class per type is the way to go; but if the set of types is fixed (as in the CQL parser where the structure of the parse tree is determined by the formal specification of CQL itself), and if many new functions are likely to be needed, then the old way may be the best.

In other words, you can slice your two-dimensional code-fragment matrix either vertically into classes, or horizontally into functions.  It seems obvious to me that different slicing directions are going to be better in different circumstances.  A reflexive Replace Conditional with Polymorphism reaction is not going to help.  (And when did the switch statement become synonymous with evil, anyway?)

And what about the distressingly common situation where you don’t have access to the original source-code, only object code?  What would you do if I’d distributed CQL-Java only as a .jar and not as source, and your job was to use it to generate Solr queries?  How would you implement the toSolr() method?

If you’re using Java, I don’t think you have any realistic option but to write a method like the first toPQF() that I listed near the start — a method that takes a Node as an argument, then interrogates it to figure of which of the Node subtypes it really is, and switches on the result, invoking itself recursively as needed.  So in that common case you’re back to square one anyway.

In more dynamic languages such as Perl, Python and Ruby, you can use the technique known variously as monkey-patching or duck-punching: just go ahead and extend the classes.  Add toSolr() methods after the event for AndNode, OrNode and the rest.  I did exactly this in 2007, in a Perl module called Simple2ZOOM, not previously having heard of the technique, and consequently feeling a bit dirty — I used it to add a toCQL()method to a parse-tree representing a PQF query, the opposite of what we’ve been considering here. Now that the technique has a name, I feel a bit better about it.  It’s actually a pretty cool way to get things done, although like most powerful techniques, it is prone to abuse if not done with taste and judgement.  (See also: Lisp macros, continuations, C++ templates, and well, pretty much all Perl programming techniques.)  I think the jury is out on whether monkey-patching is a good approach for this problem or not.

Is there a better way?  I don’t really know.  The Ruby way would be to pass a closureblock into a parse-tree walker provided by the library.  That closure would get invoked for each node in the parse-tree, and would … well, that’s where it falls down: each invocation of the closure would have to ask the node what its type is in order to know what to do, so we’re really back at the first version again.

OK, I’m done.  Will someone please tell me what obvious idea I am missing?

Update (a couple of hours later)

Quite a few people have suggested the Visitor pattern (from the Gang of Four book).  The best exposition I’ve seen of this is in munificent’s detailed comment at Reddit, which I commend to you all.  (Apart from anything else, he expounds both the pros and the cons of this approach).

I’m not wholly convinced that this is the cleanest and simplest approach, at least in dynamic languages; but it is, at least, nd excellent workaround for static languages.  For more thoughts on Visitor, see my earlier comment below in response to Phillip Howell.

Also: it turns out (also as mentioned by several commenters) that the conundrum I described here is not only a well-known one, it even has a name: the Expression Problem.

45 responses to “Slicing your 2D class/function matrix vertically or horizontally

  1. Phillip Howell

    I think the “better way” you’re looking for here is the visitor pattern, which is the general form of your ruby example. You avoid the big-switch through use of double dispatch back to the visiting object.

    Visitor even solves your “touching too many files” squick while avoiding my “big switches are evil and hard to maintain” squick.

  2. In a language like Common Lisp, where methods “belong” to generic functions rather than classes, the solution is somewhat cleaner because you don’t have to decide at the outset whether to slice horizontally or vertically.

    I.e. even if you don’t have access to the source code for the node classes, you can simply define a new generic function and methods:

    (defgeneric to-solr (node))
    (defmethod to-solr ((node and-node))
    …)
    …etc.

  3. I’ve been thinking about this a lot lately. In a perfect world, when you find yourself using switch statements to execute logic instead of polymorphism, chances are what you really want are functional programming constructs: algebraic datatypes and pattern matching.

    Of course you can’t do this in java. You might be able to in scala, which runs on the JRE. I’m not familiar enough with Scala syntax to write up an example. But it looks like this tutorial covers it in chapter 6…

    http://www.scala-lang.org/docu/files/ScalaTutorial.pdf

  4. Or, yeah, duh, a visitor would be the OO way to do it.

  5. Alisey Lebedev

    class PQF_Renderer < Node_Renderer
    “render_and:
    ““return concat(…)

    “render_or:
    ““return concat(…)

    Some rendering classes might not support Not nodes, some might do.

  6. congratulations! you’ve just discovered expression problem!

    you can solve it in scala (it was one of the requirements for the language), ocaml (with polymorphic variants) and there are a couple of solutions in haskell.

    those solutions are not so easy to use, so the most usable approach, is to decide up front whether you’re going to implement more new “classes” or “functions”.

  7. Phillip Howell, the visitor pattern is a clever workaround, for sure. But even leaving aside that fact that it only works on an object hierarchy that was designed in advance to support it, it still seems to me that all the identical accept() methods on the visitable element classes are a very verbose and roundabout way of doing a switch on the type.

    (For anyone who’s not familiar with Visitor, each visitable node type has to define its own identical method

    public void accept(CarElementVisitor visitor) {
         visitor.visit(this);
    }

    rather than inheriting that method from the abstract base class, so that the visited class’s type is known statically in the visitor.visit(this) invocation, allowing the visitor class itself to use compile-type argument-type overloading on its various visit() methods.)

    It’s cute, but is it actually any clearer than just switching on node type?

    I suppose its real advantage lies elsewhere: in that the knowledge of how to walk the visited structure lies in the structure rather than in the visitor. But even that is more illusory than real: the visitor still needs to know the visited structure in detail in order to provide all the relevant visit(VisitedClassSubtype) methods, and indeed to actually do anything useful.

  8. Here OO uses the Visitor pattern: instantiate your algorithm as an object (implementing Visitor), then use Double Dispatch to choose a method to execute based on the runtime type of your Visitor and the runtime type of your Node.

    Java doesn’t implement double-dispatch, only single. We fake it with two sequential single-dispatches, but this requires all classes on one side to list all classes on the other side, which is ugly and inextensible. You’ll still have to make a slicing decision.

    With proper multiple dispatch as in e.g. Common Lisp, that problem goes away. The code becomes pretty and the only slicing decision to make is where to store your code.

  9. Oh, and when I want to know about a pattern in OO programming I like to check the Design Patterns Java Compendium.
    http://www.patterndepot.com/put/8/JavaPatterns.htm

  10. Ben Rowland

    I know where you’re coming from with this. Its tempting to re-engineer good code to take it to that next level of structural beauty, and is very satisfying to do so.

    In my opinion, switches or if/else constructs only become ugly in several cases (har har): (i): a number of them – all conforming to the same flow of logic – are scattered all over your code-base. Even if there are only several; you have to think to be sure you’ve found them all. At that point it becomes natural to gather the knowledge for each branch into one place. And (ii): there are more than several lines of code within each branch. At this point you’re thinking of creating functions for each branch, and then it becomes obvious to gather these functions logically – et voila, a strategy pattern emerges.

    Situation (i) would start to occur if you added your toSolr() function to Node. You’d then have several switch statements – identical in structure but different in function. As you continue in this fashion, the danger of miscoding a clause (or missing one entirely) increases. The Node class could not promise to deliver on its contract of always handling every node type (and, or, etc). On the other hand, the strategy pattern would result in a clean(er) failure. [Aside: a missing implementation class may not be discovered until well into runtime, if loaded lazily from config. An interesting consequence of programming to interfaces].

    Of course, there’s also the standard advantage of each logical type being easier to understand and maintain if its in one place.

    On the other hand …. a strategy pattern would be overkill for only a few lines of code for each variant, unless you had a belief the code would grow in the foreseeable future. The danger of refactorings like these is illustrated in the facetious “Hello World” examples out there – weighing in at hundreds of lines, littered with Runnables, Observers, static factories, and a million other abused means of indirection. Refactoring demands a return on investment.

    I’m settling on a Yin-Yang point of view (or perhaps I am just lazy): it depends. For the small example its hard to see significant pros or cons of either approach. As the app grows in size, the maintenance challenges may favour one approach.

  11. Ben Rowland, you make an excellent point in your (ii) above. The appeal of the one-function-with-a-big-switch approach(*) is precisely that it is a single function; and as soon as the individual branches start getting complex enough that you want to start calving them off into their own separate functions, then the arguments against the polymorphism approach start to get weaker.

    Although even in that case, I think I prefer duck-punching, if only because it lets me keep all the code in a single source file, albeit as a sequence of small functions rather than a single big one. But I know some people have religious objections to that approach, and they may even be well-founded.

    All in all, I am inclined to concur with your own conclusion: “it depends” :-)

  12. bey0ndy0nder

    I have not given much thought on this (I completely agree with what you say regarding switching), but couldn’t you do some sort of keyword mapping. (I know this is just fancy switching.)

    Suppose we have a map, which maps node types (here it can be a string or enums) to delegates which “implements” the keywords. This way, you only to add new “output” mappings without modifying the traversal code. (I suppose the same thing can done with delegates.) And you can do this all in the same place, but you still have to add the operator functions themselves…which probably be easiest if you had one function that did a switch (LOL) and returned the “implemented operator.”

    (Also, what about some sort of templating magic?)

    So:

    
    //Somewhere
    KeywordMap.add("OR",getNewFormatOrFunction");
    //check the mapping is one-to-one
    ...
    //somewhere else
    Node
    {
    concat(KeywordMap("keyword"),
                   left(), right())
    }
    
    

    I know this is just fancy switching. But I can sort of see that it *could* be simpler than a polymorphic implementation, where you have to modify every Node class and add a new ouput method. Whereas now, you can add the new output method in a single place. (Like I said, fancy switching.)

    EPIC fail?

  13. I’m no expert, but the minute I saw your problem I thought of multiple dispatch.

    A method in C++ or Java dispatches according to the (run-time) type of one of the arguments (albeit an argument with a funny name, “this”, and funny syntactic sugar attached to it, but still just an argument). This is called single dispatch. In multiple dispatch, you can use the run-time type of more than one of the arguments.

    See also: http://en.wikipedia.org/wiki/Multiple_dispatch

  14. Multiple dispatch only helps if you reify your operation (toPQF(), toCQL(), etc.) as an object whose type can be used as one of those that the multiple dispatcher works from. I prefer not to do that if I can avoid it, because wrapping perfectly good functions in classes that have no other purposes is bowing to the articificial limitations of the language. Really, I am not trying to invoke a method on a pair of objects, each of whose type can value, but on a single object.

  15. bey0ndy0nder

    What I wrote above, I could just use a strategy pattern, where I would have a interface called OutputInterface. Then implement that with the specific output type, which returns the correct operator. So I would have onOr(), onAnd(), etc. This is still fancy switching though. But to me it would be better because you do not have to modify the traversal code. Maybe I missing the point?

  16. You could call it the worst of all worlds, but I would suggest a parser/compiler class using renderers (with an interface). The compiler class would still bear some switching logic in its toString() method and would call methods of the render providing a pair of arguments (e.g.: the add() method of the PQF-renderer).

    This way you would have all logic clearly readable in the compiler class and all implementations for a specific query language in a single renderer class. The level of “knowledge” incorporated in the renderer classes would be limited since they wouldn’t have to know anything about the tree. Further more the interface would reflect the logic of the compiler class, which might be handy while implementing a new compiler for a different task or query front end.

    By the way: I don’t think that any switching is an incarnation of evil and a foe of all maintainability. The conditional statement is the very essence of computing – and in the end the visitor-example is just switching obfuscated in type. The real problem starts with nested switches, and this could be avoided using renderer classes.

  17. bey0ndy0nder,

    Your most recent solution with the OutputInterface is morally
    equivalent to the Ruby version that I very briefly sketched in the
    main article — the difference is that in Ruby you just pass a block
    rather than having to go through all the rigmarole of defining and
    instantiating a visitor class. Something like this:

    root_node.visit do |node, sub1, sub2|
      case node
        when AndNode:  "@and " + sub1 + " " + sub2
        when OrNode:   "@or "  + sub1 + " " + sub2
        when NotNode:  "@not " + sub1
        when TermNode: node.term
        else raise "unknown node type " + node.class
      end
    end
    

    Actually, I quite like that. It’s certainly concise!

  18. May I suggest partial classes (http://msdn.microsoft.com/en-us/library/wa80x488%28VS.80%29.aspx ) and/or extension methods (http://msdn.microsoft.com/en-us/library/bb383977.aspx ). The former requires all the source code to be compiled, but allows you to put all the toSolr() methods in a single file. The latter can extend existing compiled types, but feels more like the monkey patching you mentioned.

  19. In C++, boost::variant supports the visitor pattern *without* having a class specifically designed to support it. i.e. you can have a boost::variant and Foo, Bar, Baz need not know anything about the fact that they may be used as part of a visitor pattern.

    Underneath the hood, boost::variant actually compiles down to a huge switch statement like you describe, but it’s completely abstracted away, and compile-time template INSANITY is used to map this to a single visitor class which is able to handle all the possible types.

    boost::variant is actually really freaking amazing.

  20. I’d say write proper unit tests and don’t explode any class hierarchies until you need to add a new node type or a new back end. YAGNI and all that.

    IMO, what you want to do is to bridge two separate class hierarchies. And guess what, there’s a pattern for that. And it ain’t the god damn Visitor pattern, it’s the Bridge pattern.

    In short, keep your node hierachy, create another hierarchy with classes Stream, XCQLStream and PQFStream.
    Make the stream call writeXCQL(this) or writePQF(this) on the node depending on which type of stream it is. This way you keep all node related functionality inside the nodes.

  21. May I suggest a functional programming language like Haskell:

    data Node = AndNode Node Node | OrNode Node Node | NotNode Node
    
    translate node = case node of
        AndNode a b     ->  "@and " ++ a ++ " " ++ b
        OrNode a b      ->  "@or "  ++ a ++ " " ++ b
        NotNode e       ->  "@not " ++ e
    

    Note that you don’t have to pretend that sub1 and sub2 are somehow available on all
    your nodes, because it is explicit which nodes contain what fields.

    ML is similar, and in addition checks that you have indeed taken care of all cases.

    Scala can also easily do this, but is a bit more verbose.

    root_node.visit do |node, sub1, sub2|
      case node
        when AndNode:  "@and " + sub1 + " " + sub2
        when OrNode:   "@or "  + sub1 + " " + sub2
        when NotNode:  "@not " + sub1
        when TermNode: node.term
        else raise "unknown node type " + node.class
      end
    end
    
  22. “IMO, what you want to do is to bridge two separate class hierarchies. And guess what, there’s a pattern for that. And it ain’t the god damn Visitor pattern, it’s the Bridge pattern.”

    What? No! I very expressly do NOT have two separate class hierarchies. I have exactly one, representing the nodes in the parse tree. toXCQL(), toPQF() and friends are functions/methods, not classes. And I certainly don’t want to introduce all the cognitive overhead of reifying them as classes — that is just the kind of thing I want to avoid doing in order to keep the Radius of Comprehension low.

    Otherwise you end up with documentation that says “in order to convert the parse tree to PQF, simply instantiate a PQFStream, which can be done my invoking the factory method createPQFStream on the abstract superclass Stream …” Surely none of us wants to go there? (And BTW., any time documentation uses the word “simply”, that is a dead giveaway that it’s describing something more complex than it needs to be.)

  23. Ahnfelt,

    The Haskell version of this is very nice — I particularly like the way that the cases of the switch statement let you declare formal parameter names for the members. Haskell is definitely on my list of languages to learn: I guess it’ll top of that list once I’ve established a satisfying understanding of Lisp.

    Your Scala version, though, looks to be identical to my Ruby version. Is this an astonishing coincidence, or an unfinished cut-and-paste?

  24. The mere fact that adding new ‘backends’ starts requiring you to pepper many different classes with new methods would seem to be an indicator that it’s not the right way to do it.

    Don’t get me wrong, I never believe in ‘right’ way ‘wrong’ way, but…

    Might a better approach be to extract the logic for each external service into a seperate class/classes and make an interface to expose the metadata needed to inform the external service classes of the required information?

  25. so you are asking how to write “Node.toPQF.Add”-like code?
    1. class func 3x
    2. 3x class func
    3. class 3x func

    what does it matter, when it’s all the same thing?
    the only limit is languages, and why do you think you’ll find general solution in non-general languages? my ideal language wouldnt bother me with this, it would provide me with 3 versions of code, whatever best fits my current context..

  26. Mike,

    Just adding toX-methods to your nodes for each new ouput format that comes along isn’t simple, it’s stupid. The nodes should know as little about PQF and XCQL and whatever other formats you dream up as possible.

    It *will* lead to hardcoding the available formats all over your application. Which means that you will have to go back and add support for your new toX-functions when you add a new format.

    Don’t confuse stupid with simple.

  27. The first consideration that came to mind was what language construct or factoring or whatever could help enforce completeness, ideally a compile time check that confirms that all of the possible node types have all the necessary generators. One advantage of having one bigm two level dispatch statement is that you can audit it on one page, at least until it gets too big. I know some languages have an “interface” construct in which an interface is a set of required methods. Are there other ways of ensuring completeness at compile time, rather than hoping that your test cases cover all the ground and the language defaults don’t hide any problems?

  28. Have to agree with Adde. Your Node class is doing way too much, and in danger of becoming a God class. It shouldn’t know about any of the external “views” such as PQF or XCQL. An XCQLParser should take an XCQLExpression and build a tree of Nodes. A PQFRenderer should accept that tree of Nodes and render a PQFExpression. Keeping the responsibilities separate means you can add additional parsers and renderers as needed without polluting any of the existing classes. Or have I missed something?

  29. Pingback: Top Posts — WordPress.com

  30. Vince, your argument is very compelling. Almost thou persuadest me to be a Fowlerite.

    And yet …

    Somewhere along the line, one of the classes (or class hierarchies) has to know something about the other — it’s just an irreducible aspect of the complexity of the problem. You rightly say that we don’t want the node class to have to know all about XCQL and PQF; that’s true. But it’s also true that we don’t want our XCQLWriter and PQFWriter classes to have to know all about the node structure. But we can’t have it both ways. XCQLWriter has to know, for example, that an AndNode has left and right subtrees. We can dress that up and try to conceal it behind yet another layer of indirection, an XCQLWriterForNodesWithLeftAndRightSubtrees subclass or something, but that doesn’t remove the knowledge, it just shifts it around a bit more.

    And if you’re not careful, if you go all Fowleriffic, you end up with the dumb situation where XCQLWriterForNodesWithLeftAndRightSubtrees hides the left-and-right-subtree-ness of AndNodes from XCQLWriter proper, but XCQLWriter still needs to know how to convey the ANDness of the node it’s dealing with, plus you need some dispatcher code that knows when to use an XCQLWriterForNodesWithLeftAndRightSubtrees. [Now that I’ve typed that classname three times, I am starting to wish I’d given it a different name :-)]. So you end in a much worse state than you started out in: rather than having one class simply and honestly knowing about another’s tree structure, or knowing about a query language, you now have the knowledge scattered to the four winds and distributed across half a dozen classes which are all to varying degrees dependent on each other.

    And that, for me, is the very worst kind of code of all. It’s the object-oriented equivalent of GOTO-rich spaghetti code from the early 1980s. Coming back to the concept of Radius of Comprehension, I think an important goal in software design is to localise knowledge. In fact, I wonder whether that might be even more important than (although of course not necessarily or even usually being in conflict with) encapsulation.

  31. Well objects have to know something about other objects or else they could not co-operate at all, so there will always be a degree of coupling between them. But I am firmly of the view that we seek to reduce that coupling as far as possible, and I don’t think your case provides a good enough counter-example to that principle.

    As you say, the cost of decoupling is distributed knowledge: every client who wants to do something with the parse tree model has to know that it consists of different node types (or at least the node types that the client cares about). But this is the only coupling that exists. Only if the model changes will the various clients need to be rebuilt, and there is absolutely no dependency between the clients themselves.

    The introduction of XCQLWriterForNodesWithLeftAndRightSubtrees and their ilk unnecessarily obfuscates the client implementation in my view, because the rendering of each node type (binary or unary) is trivially simple – the problem doesn’t call for additional complexity.

    Finally if you really don’t want to handle the different node types in your clients using flow of control statements, you could use method dispatching instead: simply register each node type in a map with an appropriate handler, then as each node arrives on your tree walk, look it up in the map and invoke the associated handler to render it:

    	for (Node node : tree.nodes) {
    		map.get(node.getClass()).emit(node);
    	}
    
  32. Or, to avoid the inadvertent reification of the handlers that I just introduced and to use handler methods as I originally intended:

        
        for (Node node : tree.nodes())  {
            map.get(node.getClass()).invoke(this, new Object[] {node});
       }
    
    
  33. Pingback: Frameworks and leaky abstractions « The Reinvigorated Programmer

  34. #!/usr/bin/ruby -w
    
    =begin
    I'm wondering if there is a simpler way to look at this.
    Nodes only have info about their type, and their descendants.
    They might need information about their precedence for this to 
    work properly, unless you always plan to fully bracket the results.
    Could be useful for parsing.  See Top Down Operator Precedence Parsers
    (V. Pratt) for example.  But never mind that for now.
    
    I'm wondering if there are only a few types of possible client for
    exploring this tree, which is basically an Abstract Syntax Tree.
    There is the interpreter, which executes the tree as an expression.
    There is the Prefix scribe.
    There is the Infix scribe.
    There is the Postfix scribe.
    There is the XML scribe and variants.
    
    =end
    class Node
      attr_accessor :name, :left, :right
    
      def initialize(l_thing=nil, r_thing=nil)
        @name = "abstract class [OOPS!]"
        @left = l_thing
        @right = r_thing
      end
    
    end
    
    # Holds a string, a terminal symbol
    class LeafNode
      def initialize(thing)
        @value = thing
      end
    
      def name
       @value
      end 
    
      def left
       return nil
      end
    
      alias :right :left
    end 
    
    class AndNode < Node
      def initialize(l_thing=nil, r_thing=nil)
        super
        @name = "AND"
      end
    end
    
    class OrNode < Node
      def initialize(l_thing=nil, r_thing=nil)
        super
        @name = "OR"
      end
    end
    
    class Client
    
      # Just to save time
      def initialize(top_node)
        @top_node = top_node
      end
    
      # spoken with a Lisp
      def prefix (node = @top_node)
        return unless node
        result = "(#{node.name}, #{prefix(node.left)}, #{prefix(node.right)})"
        result.gsub(/, , /,'')
      end
    
      # May the FORTH be with you
      def postfix (node = @top_node)
        return unless node
        " #{postfix(node.left)} #{postfix(node.right)} #{node.name}"
      end
    
      # Good old infix,
      def infix(node = @top_node)
        return unless node
        result = " (#{infix(node.left)}) #{node.name} (#{infix(node.right)}) "
        result.gsub(/\(\s*\)/, '')
      end
    
      # What's that egg smell?
      def xmlese(node = @top_node, indent = 0)
        return unless node
        tag = node.name
        result = "#{' ' * (indent)}\n"
        result += "#{' ' * (indent)}<#{tag}>\n"
        result += "#{' ' * (indent)}  "
        result +=    "<param>#{xmlese(node.left, indent + 4)}</param>\n"
        result += "#{' ' * (indent)}  "
        result +=    "<param>#{xmlese(node.right, indent + 4)}</param>\n"
        result += "#{' ' * (indent)}</#{tag}>\n"
        result += "#{' ' * (indent)}"
        return result.gsub(/<param>\s*<\/param>/, '')
      end
    
    end
    
    if __FILE__ == $0
    
      k_p = AndNode.new(LeafNode.new("Kernighan"), LeafNode.new("Pike"))
      k_r = AndNode.new(LeafNode.new("Kernighan"), LeafNode.new("Ritchie"))
      top_node = OrNode.new(k_p, k_r)
      
    
      client = Client.new top_node
    
      
      puts client.prefix
      puts
    
      puts client.postfix
      puts
    
      puts client.infix
      puts
    
      puts client.xmlese
    end
    
    =begin
    So all a node has to do is tell you its name [rank, and number :-)].
    The /(?:pre|in|post)fix/ stuff is all in the eye of the beholder.
    Then node.name could be node_name(node), a client method using the
    node class as a hash key, in case you want AND as And or 'and' or
    as an inverted v unicode glyph of some sort.  That way you just extend
    data, not code, to add to it.
    
    All the knowledge about syntax lives in the client.
    
            Hugh
    =end
    
  35. Hugh, your approach is nice so far as it goes, but I think the fact that you have to special-case the XML is an indication that something is wrong. The XML that you generate is a prefix form, so it ought to be possible to generate it by invoking the prefix() method with appropriate arguments.

    More generally, of course, your prefix(), postfix() and infix() methods correspond to a pre-order, post-order or in-order traversal of the tree.

    The other problem is that a solution like this, which tries to abstract away large chunks of the problem, inevitably suffers from Leaky Abstraction Syndrome (which by an amazing coincidence is the subject of the new entry that I posted an hour ago). It falls apart when dealing with real CQL parse trees because of the existence of various different kinds of leaf node (e.g. result-set refererences as well as search-terms) and even more because of more complex nodes such as SORT which includes a sort-specification to be applied to the records found by the search specification that is the tree it points to. So:

     
    public class CQLSortNode extends CQLNode {
        public CQLNode subtree;
        Vector<ModifierSet> sortKeys;
        // methods redacted
    }
    
  36. I think the question is a little ill-served by the example…or vice-versa. You’re asking a strategy question about a tactical situation.

    The Node class not only shouldn’t know about output formats.

    Node shouldn’t have subtypes for and, or, not, etc. The evil Fowler was talking about was switching on object types. In that case one suspects the types should be doing the work. And, or, not, etc. should be an enum or equivalent. You made them types because you wanted to add methods to them, methods to do things that aren’t part of their reason for existing: being an abstract parse tree.

    Node also shouldn’t know about CQL. Node should simply be way to build trees to pass between parsers and generators.

    (An advantage to that is that you might unexpectedly need to parse a different input language rather than generate a different output language.)

    About radius of attention: with a passive Node class, you would be thinking about CQL and Node, or PQF and Node, but not trying to fit CQL into PQF or PQF into CQL. And Node shouldn’t take much thought.

    Every change to the lingua franca requires changes to all the generators. Besides testing, and besides abusing type checking (most software patterns seem to be about going to a lot of effort to get type checking and dispatching to do the work) you could come up with, say, a format-version field and a compatibility check in each generator.

    But, in this tactical case, the lingua franca is the thing you would try to keep the most simple and stable. With NxM compilers they have the additional trick of making a powerful but simple IL, and encoding new input concepts out of existing IL primitives. But you aren’t in a complicated enough situation to need that.

  37. But, Steve, your proposal (very dumb Node class with an enum, intelligent XCQL and PQF renderers), is right back to the old C style of coding that we started with! All the renderers need intimate knowledge of the parse-tree structure. Now I’m not saying that’s a bad thing — not at all — but it’s interesting to me how very far from Fowleriffic orthodoxy it is.

  38. How do you get XML as prefix form? It has closing tags with the same name (+ a ‘/’), so “we do both kinds of affix: prefix and postfix”. If it were YAML, that would be prefix.

    “It falls apart when dealing with real CQL parse trees because of the existence of various different kinds of leaf node “.

    So you object to this solution because I have not answered some aspect which was not in the original question? :-)

    If you are going to have different leaf nodes, they still need to know how to represent themselves, which I have called name in my code. Now, it might be that you apply further transformations to that name in more complicated cases, but it is still a leaf node output at some point, whose syntactical idiosyncrasies will be handled by the client rather than the node itself. It would be like having to represent a struct, or a float, or …, in something generating C code, and various clients coping with K&R C, C89, C99, and C++, — all rather similar but critically different in certain aspects.

    And I don’t think this is a leaky abstraction. If your CQLSortNode cannot be treated as a CQLNode, then most sources I have read would argue that it has no business being a subclass of CQLNode. Perhaps it should use delegation instead. Without looking at the code I can make such sweeping statements easily enough! :-)

  39. Hugh, you are of course quite right about XML — a metaformat so hideously misengineered that you have to say everything twice, once before and once after the content. It’s pretty impressive what a shockingly bad format we can come up with when we really try. Future generations will look back on XML the way we look back on Victorian clothes — astonished, perplexed and rather amused that people once thought something so inconvenient and uncomfortable could possibly be rational.

    CQLSortNode is a perfectly good CQLNode; but it’s neither a CQLBinaryNode (like CQLAndNode and CQLOrNode), nor a CQLUnary node (like CQLNotNode). That’s the part of the abstraction that leaks — the assumption that we can model node content with something as pleasantly simple as one or two subtrees.

  40. Then consider this to be an exercise in BDD — Blog Driven Development. I’ve met the basic tests you set out already, give us a new test that fails.

    I’m working on the assumption that be that Binary, Unary, or N-ary, the structure will be the same, more or less. Well, infix will be tricky, but otherwise…

  41. But, Hugh, the bottom line remains the same however you slice it: EITHER the individual renderers need to know about the node types and the structures that they contain, OR the individual node types need to know about the rendered output formats. Isn’t that irreducible?

  42. It depends. The individual formatters will need to know how to format a node. If the node knows the arity of its structure, and the formatter knows how to process nodes of given arity, then provided the node knows what to pass to the formatter, it need know nothing more. And the formatter need only know what the node wants output, #{self.to_s} perhaps, and its arity (for infix, x * y, x * f(p,q,r), as examples) and the information coupling between them is minimized. If you are getting to the complexity of `eqn | tbl | troff` then things could get seriously tricky.

    Hack that Ruby I sent you to add a node that will break things for you, representative of a bad case, and I’ll see if I can keep things general and have it work. I’m really not fluent in Java.

    But, yes, there is a level of information beyond which this cannot be simplified. I know of Kolmogorov complexity, but in insufficient detail.
    Maybe Shannon information theory is sufficient to
    describe this lower bound. I think that we’ll find subclasses of Node have enough in common that a general definition of how to display a node *should* cover all of them. Otherwise the language must be horrible to read and write, with all its edge cases.

  43. Pingback: Page not found « The Reinvigorated Programmer

  44. EITHER the individual renderers need to know about the node types and the structures that they contain, OR the individual node types need to know about the rendered output formats. Isn’t that irreducible?

    Model View Controller, seperation of Data and Logic! Visitor Pattern is just not generic enough.

    A little bit of code says more than thousand words:
    #!/usr/bin/ruby

    #Model
    class Tree
    attr :data
    attr :children
    def initialize data, children = []
    @children = children
    @data = data
    end
    def add child
    @children << child
    end
    end

    #Controller
    class DepthFirst
    def self.traverse tree, formatter
    cnt = tree.children.count
    formatter.before tree.data, cnt
    tree.children.each_with_index do |c,i|
    traverse c, formatter
    formatter.between tree.data if i+1 < cnt
    end
    formatter.after tree.data, cnt
    end
    end

    #View
    class RenderXML
    def initialize
    @depth = 0 # just to show off
    end
    def before data, child_count
    @depth += 1
    print child_count == 0 ? "#{data}" : "\n"
    end
    def between data
    end
    def after data, child_count
    @depth -= 1
    puts child_count == 0 ? '' : ''
    end
    end
    #View
    class RenderPrefix
    def before data, child_count
    print child_count == 0 ? data : "@#{data}("
    end
    def between data
    print ','
    end
    def after data, child_count
    print child_count == 0 ? '' : ')'
    end
    end
    #View
    class RenderInfix
    def initialize
    @op_translate = { 'and' => '*', 'or' => '+' }
    end
    def before data, child_count
    print child_count == 0 ? data : '('
    end
    def between data
    raise "Unknown op #{data}" if @op_translate[data].nil?
    print @op_translate[data]
    end
    def after data, child_count
    print child_count == 0 ? '' : ')'
    end
    end

    #Data
    r = Tree.new 'and'
    r.add Tree.new 'or', [Tree.new('leaf1'), Tree.new('leaf2')]
    r.add Tree.new 'leaf3'

    #And Action!
    DepthFirst.traverse r, RenderXML.new
    puts
    DepthFirst.traverse r, RenderPrefix.new
    puts
    DepthFirst.traverse r, RenderInfix.new
    puts

    Not even the controller needs to know implementation details of either model or view. Just some interfaces need to be defined. Works also very well with statically typed languages but you can just write the most beautiful and concise code with ruby in my eyes ;)

  45. Ok try again with source tags

    #!/usr/bin/ruby
    
    #Model
    class Tree
      attr :data
      attr :children
      def initialize data, children = []
        @children = children
        @data = data
      end
      def add child
        @children << child
      end
    end
    
    #Controller
    class DepthFirst
      def self.traverse tree, formatter
        cnt = tree.children.count
        formatter.before tree.data, cnt
        tree.children.each_with_index do |c,i|
          traverse c, formatter
          formatter.between tree.data if i+1 < cnt
        end
        formatter.after tree.data, cnt
      end
    end
    
    #View
    class RenderXML
      def initialize
        @depth = 0 # just to show off
      end
      def before data, child_count
        @depth += 1
        print child_count == 0 ? "<data>#{data}</data>" : "<op func='#{data}' depth='#{@depth}'>\n"
      end
      def between data
      end
      def after data, child_count
        @depth -= 1
        puts child_count == 0 ? '' : '</op>'
      end
    end
    #View
    class RenderPrefix
      def before data, child_count
        print child_count == 0 ? data : "@#{data}("
      end
      def between data
        print ','
      end
      def after data, child_count
        print child_count == 0 ? '' : ')'
      end
    end
    #View
    class RenderInfix
      def initialize
        @op_translate = { 'and' => '*', 'or' => '+' }
      end
      def before data, child_count
        print child_count == 0 ? data : '('
      end
      def between data
        raise "Unknown op #{data}" if @op_translate[data].nil?
        print @op_translate[data]
      end
      def after data, child_count
        print child_count == 0 ? '' : ')'
      end
    end
    
    #Data
    r = Tree.new 'and'
    r.add Tree.new 'or', [Tree.new('leaf1'), Tree.new('leaf2')]
    r.add Tree.new 'leaf3'
    
    #And Action!
    DepthFirst.traverse r, RenderXML.new
    puts
    DepthFirst.traverse r, RenderPrefix.new
    puts
    DepthFirst.traverse r, RenderInfix.new
    puts
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s