In fact, it's a rather old question: what is better 1) a declarative approach with pattern matching or 2) Visitor pattern from OOP world.
Ok, better for what? Let's take a practical example: AST transformations inside a compiler. You may find Visitor pattern use only in a few Java-related compiler textbooks. For some reason almost every good compiler/compiler textbook uses pattern matching: Appel, nanopass, CompCert, DMS etc.
Ok, but the real point of the article is not that "visitors" are more readable and easy to use, but they are more perfomant, right? Do we have any profiling here? Maybe with a good GC it will cost almost nothing for us to build another tree in terms of speed? We remember the words about "premature optimization", and any "manual optimization" which makes the algorithm structure foggy is evil so (necessary evil -- in some rare cases). In some declarative languages pattern matching constructs are converted to a fast decision trees by compiler. There are some "lazy" approaches to pattern matching.
Or you can just provide a list of transforming (maybe some composition of transformations) functions to your generic pattern matching function. It's almost the same as using "visitors", but you don't need to call "The Team Architect™, for supervising the object oriented quality of your software" :)
> You may find Visitor pattern use only in a few Java-related compiler textbook
The Java standard library uses ASM heavily for it’s method handle JIT compiler implementation, which is all visitor based. As does the Scala compiler. ASM is extremely widespread for anyone doing jvm bytecode work and isn’t exactly something you find only in textbooks
> Maybe with a good GC it will cost almost nothing for us to build another tree in terms of speed
Not sure what environment you work in, but converting uPickle to a visitor-based architecture from recursive transformation sped it up 3x on the JVM and 10x on Node.js. I’d love to have a GC that could elide the intermediate trees but the GCs I have aren’t up to snuff
I think you've (re)discovered the -morphisms. E.g. anamorphism, catamorphism, hylomorphism. Data structure traversals of various kinds can usually be cast in terms of these morphisms.
As it turns out GHC is usually pretty good at optimizing this kind of thing due to the extremely aggressive inlining which is possible when you know that there are no side effects. It'll often handle compositions of traversals with no sweat. (I think it's sort of all lumped in as "fusion".)
EDIT: See tel's comment in this thread. He always understands and explains it much better than I can.
I guess things you've mentioned are widespread inside the Java community. But let's consider the things that have more global impact to compiler writers. For example, Scala LMS is a very interesting and promising recent project. Take a look at its source code -- no Visitor pattern inside. Visitor pattern may be necessary part of "Java culture", but for Scala I see no real reason to keep using it.
Not quite a part of "Java culture". See Roslyn compiler, .NET Expression tree, C++ `std::visit` or tons of DOM tree rewriting js stuff.
Actually `visitor` and `pattern matching` are not mutually exclusive. imo the only difference is that in the visitor pattern, if you don't have anything to update, you just return the original node.
Thank you! I agree that just using of pattern matching may be not enough. But, instead of Visitor Pattern, I would use generic traversal "strategies" (combinators). My ideal is a DSL with first-class term rewriting rules + user definable strategies which take these rules as arguments. In fact, I already use such DSL for compiler writing :)
Pattern matching isn't used in the Java community because it doesn't exist, and there is nothing inherent in pattern matching that makes it less performant than double virtual dispatch. And anyone who thinks the visitor pattern is more readable is probably not someone I want to code with. The visitor pattern is very high on boilerplate and makes the flow of your code harder to read.
> For some reason almost every good compiler/compiler textbook uses pattern matching: Appel, nanopass, CompCert, DMS etc.
Here is Appel's Java-based compiler book: https://eden.dei.uc.pt/~amilcar/pdf/CompilerInJava.pdf. It's full of visitors. If the same book's ML version uses pattern matching instead, then that says a lot about the different implementation languages and not much about what you wanted to claim.
Well, it's another "Java-related compiler textbook". And this edition has a coauthor (Jens Palsberg) who is responsible for all OOP/Java-related things in the book. I recommend to read original ML edition even for Java developers. And I'm not the only one who recommends it.
"Comment by Vladimir N. Makarov: Another good book to start to study compilers from parser to code generation and basic optimizations. I especially like the version in ML (Modern compiler implementation in ML).
Comment by Steven Bosscher: The version in ML is the best of the three. The other two look too much like "had to do this"-books where algorithms are translated from ML, which makes them look very unnatural in C/Java." [1]
This is pretty common in Haskell using the "recursion schemes" technique. The idea is to note that any recursive data type can be constructed by laying many "layers" down. For instance
data Json
= Str String
| Int Int
| Dict [(String, Json)]
has the "layer" type
data JsonLayer x
= StrL String
| IntL Int
| DictL [(String, x)]
You could also "layerize" the list in here which is what the author did with the DictVisitor, but I'll leave it as is for simplicity now.
We can recover the original type using the layers and the "type level fixed point operator"
On the other hand, we can recursively consume values of `Fix JsonLayer` (and, equivalently, Json) with functions of the shape
type Alg f a = f a -> a
type JsonAlg a = JsonLayer a -> a
In other words, it tells us how to get a result from a single layer (where the recursive parts have already had their results computed). This is the Json visitor, though you can rewrite the type to be something more familiar
-- isomorphic to Alg JsonLayer a
data JsonVisitor a =
JsonVisitor
{ onStr :: String -> a
, onInt :: Int -> a
, onDict :: [(String, a)] -> a
}
You can write a function which consumes Fix'd data types using an appropriate Alg that is totally generic, or you can write a specific one for consuming Json using `Alg JsonLayer`
-- commonly seen as consume :: (JsonLayer a -> a) -> (Json -> a)
consume :: JsonVisitor a -> (Json -> a)
consume v (Str s) = onStr v s
consume v (Int i) = onInt v i
consume v pairs = onDict v $ map (\(n, json) -> (n, consume v json)) pairs
The general solution for heterogenous layers requires indexing the layers. The x type variable ends up having kind `Index -> *` for your index type Index.
Not in all languages. You can easily implement a visitor pattern with purely static dispatch in, say, Rust or C++. I suspect that any JIT that performs sufficient specialization/inlining will also achieve the same result once warm.
It isn't overhead to have a dynamic dispatch; you're traversing a runtime structure with variable shape. I can always construct a Map that will force you into a the case of dynamic dispatch in JSON. The only way we could remove that overhead is by fully fixing the shape of the tree and all maps at compile time (which has its uses, but in a different context).
The fact that you can fuse multiple passes into one alteration (or reconstruction) of the tree is what's a removal of overhead.
Since you're on the hook for a polymorphic call anyways in a rewrite of a runtime runtime structure, I think this is not the "overhead" that anyone was talking about.
Overhead would "loosely" relate to better performance, and v-table dispatch type that visitor pattern is built upon, cannot be considered 'zero overhead'.
It's a trade off and the article shows no proof the of an improved performance by reducing the 'overhead'. For example object allocation in JVM is really cheap (pointer bump in the TLAB + check&perfectly predicted jump), reusing objects in a cycling list/buffer is similar, etc. In the end the post is about performance and I pointed that the multiple mentions of 'zero overhead' are incorrect.
Ah yes. So triggering a GC in the middle of your duplicated tree-on-heap traversal will totally not risk any pipeline stalls. I'm sure that N vtable calls per node is totally worse than re-enumerating the objects on the heap N times.
When I talk about how the OO community has anti-intellectual toxicity can try to buzzword bingo architecture away, Visitor is my go to example. Because that's sure what it seems like to me.
You will 100% end up with pipeline stalls with a sufficiently large, random input anyways. This complaint about vtables is not substantial in this case, and I welcome you to prove they do.
I don’t think this is true. If you know the set of functions that can be dispatched to, you could inline them in a jump table / switch statement. JVM could definitely do this since it doesn’t even need to know the full set; it could inline new functions as it encounters them. This is all theoretical, of course.
There are inline caches (IC) and JVM uses that to a point. The inline caching for hotspot is 2 targets with guard checks[0] and then a polymorphic call. However if there are no dominating/common calls the IC is useless.
On top of that JVM has an inline budget and just stops at a point. So the switch stuff ain't happening for megamorph.
Monomophisation is a common optimization on the JVM, combined with a guard condition that de-optimizes should the type assertion fail. Not sure if that only affects the hot path.
It's moot either way. There is dynamic dispatch based on use provided inputs. There will always be lookups, jumps, and cache misses regardless of the syntax or semantics.
Is it moot? With templates, the Visitor type is selected at compile time and needn't even be polymorphic. The member function call(s) can often be inlined. Pretty sure there is no dynamic dispatch or jumps in such a scenario. Cache misses, sure, but I don't think that's important in this case.
Almost always these systems operate on external inputs like source files or JSON blobs. You cannot compile time collapse the branching needed to parse that sort of thing.
The visitor pattern is an alternative to dynamic dispatch. Normally instead of using dynamic dispatch you inverse caller and callee roles and pass 'this'. The article uses a variation of the classic visitor pattern.
Meta about the article: "Let's use a simplified JSON style tree consisting of only a few types" followed immediately by "Here's the Scala code with a discussion of Scala specific implementation details".
Not exactly all that friendly a method to discuss a topic. Someone at a point in their career where they may have derived value from this blog post is likely to be immediately and hopelessly lost.
Instead, introduce one thing at a time. If you're talking about a new concept, don't introduce it using a complex language - use something the reader will be familiar with. I personally dislike JavaScript, but it's still a much better choice for this. Or Python. Or even plain old Java - lots of folks cut their teeth in college on Java.
The author writes Scala libraries and tools and blogs about Scala. It's "not friendly" only if you're expecting him to write for a different audience than the one he's addressing.
I was going to say the same thing. I've converted XML processing code that took hours to run into code that took minutes just by switching to SAX parsing. The lower overhead has a drastic impact on runtime.
Is this actually double dispatch? Visitor is a pattern that can be used for double dispatch, but I only count one guaranteed dispatch here.
I'm not convinced that folks here saying, "We just us pattern matching like functional programming does" actually know how modern functional programming does this. From the perspective of runtime overhead and code size, this approach is very similar to recursion-schemes.
Where RS excels over this approach is not in the use of pattern matching, but in the fact that it can reuse the functor structure to not even have to write the descending algorithm; it comes for free as part of your fixpoint functor.
I do think visitor pattern, type classes and pattern matching have different areas where responsibility lies and how it is distributed (with pattern matching the most local, visitor pattern extensible without by classes and type classes - which I prefer - extensible at the call site).
I think the Visitor pattern is an antipattern. I've never seen a non-trivial application that didn't become a huge mess. It fundamentally violates the basic OO principle of encapsulating state and behavior. Anything else -- reifying the events into first-class types, factoring out the overlap into a new type, generics, even Scala-style traits -- is better.
The whole point is to separate behavior from the datastructure. Yes, this doesn't fit nicely into OO principles, but strictly that's true any time you externally query an object for state and make a conditional decision based on the result.
Inevitably, any method (visitor, pattern matching, if elsif) of customizable walking of a tree datastructure separates behavior from the tree object. That's the point, though, again.
Now, you can say wanting to do that (customizable tree walking) in itself is an antipattern and shouldn't be done. That just doesn't match well with reality.
I've seen many cases where the visitor pattern is about the best one can do. Yes, it becomes ugly but that's usually due to the complexity of the attempted tree walking, e.g. for transformation.
A lot of the alternative approaches in the functional world become ugly too once there's a need to offer maximum customizability, e.g. in terms of order of evaluation.
If you are able to sufficiently constrain the domain you can get away with some simplied templates, but where I see visitors most often is in API's wanting to offer any kind of tree walking.
We absolutely use a variant of this technique in Haskell. We absolutely do not need type classes (of any order) to make it work (although type classes and type families certainly clean up the implication). We need a Fixpoint lifting, a way to consider an object as a functor (which we could do at the value level). The rest is simple functions.
I was surprised how similar it looks in Java. I hadn't considered how it would look.
Yeah, there is a neatness to it. I manage to achieve a similar thing with recursive generators in python quite often, which ends up being quite concise.
For processing JSON in Clojure, I've used zippers, modifying the tree or leaf nodes by protocol dispatch. More because it seems how the task is "supposed" to be done in Clojure rather than based on any particular understanding of whether there are alternative methods out there, and if so, which would be the better method.
I think in C# nowadays I'd implement Select and SelectMany for the data type I want to visit, and then use LINQ. This is one pattern which is easier in a functional approach. I presume it would be easy to do something similar in Scala?
Yes, but from a functional perspective you need to do extra work to make generalized recursive applications possible. If you're interested, the name is "Recursion Schemes". Avoid the paper, its notation is too challenging. This blog has a long running series which is much better: http://blog.sumtypeofway.com/an-introduction-to-recursion-sc...
Looks like the pattern effectively linearizes the hierarchical structure. So you can stream or iterate over the ouput of a visitor run, as the author said.
Could one just implement an iterator on top of a tree structure? This would be similar but be imperative right rather than declarative as you would not provide a “callback”, but pull out nodes directly.
Why is this article even remotely applicable here, Dr. Frank? Not only does this technique factor away the recursive part of the algorithm from the transformative, but it improves performance at the same time. Any time you can abstract to a simpler requirement (that is more testable) and gain performance, this is like finding a silver dollar at the beach. You should take it and be thankful.
I think an awful lot of OO programmers see "visitor pattern" and immediately their body clenches because they've been given warnings over and over about how "multiple dispatch is dangerous and confusing." And when it's used in specialized code instead of generic code, that's true. But when it's used to separate business logic from algorithmic implementation, it's nearly always a net win.
Fellow (?) functional programmer here. I would generally use a recursive descent algorithm on a tree. That's the natural approach, yes? But the entire point of the article was that if you use a streaming approach you can get some performance benefits.
I would say it's not totally trivial in most languages, and that it's slightly more extra work in functional languages.
The code is scala, actually. Even still I am surprised the article is top of hackner news (for something rather obvious and polymorhic calls are not zero overhead in jvm)
Our current principal engineer has implemented the visitor pattern for a bunch of things in our current project. It's a quite ugly implementation we shot down in code review and then we had an entire meeting where he defended it and eventually it got let in.
He's used the visitor pattern in a few other areas as well. I'm not a big fan.
This technique improves readability, improves abstraction, improves testability, and improves performance.
Please don't confuse your superstitions or local culture's distaste for properly researched architecture for a more general sense of code quality. Simply saying, "I saw the word visitor and got mad," not only is disrespectful to the author, but it's disrespectful to your entire profession.
Visitor pattern definitely does not automatically improve readability or clarity. (In the general case! Summing values would be an exception.) In fact, I'd see it as a performance/readability tradeoff in any language where recursive tree processing is ergonomic.
Not even knowing the language involved, there's really not much to say.
I'm not referring to the Visitor pattern in Abstract, I'm referring to the specific solution the author of the article we are discussing employed.
There is no such thing as a pattern that always increases clarity. That's not what patterns are for, so that's unsurprising. It's the case though that this specific application has pretty much only benefits.
Given the fact that this is a combination of well-known techniques, trivially offers performance benefits, and makes the transformation part of the code testable in isolation from the process or recursion, it's a smart first pass. I think most experienced OO engineers could sit down and write this in one pass.
Calling it overengineered is pretty ridiculous IMO. "Over-engineered" doesn't mean, "Because software training is often inadequate someone might encounter this for the first time in industry rather than in school."
Ok, better for what? Let's take a practical example: AST transformations inside a compiler. You may find Visitor pattern use only in a few Java-related compiler textbooks. For some reason almost every good compiler/compiler textbook uses pattern matching: Appel, nanopass, CompCert, DMS etc.
Ok, but the real point of the article is not that "visitors" are more readable and easy to use, but they are more perfomant, right? Do we have any profiling here? Maybe with a good GC it will cost almost nothing for us to build another tree in terms of speed? We remember the words about "premature optimization", and any "manual optimization" which makes the algorithm structure foggy is evil so (necessary evil -- in some rare cases). In some declarative languages pattern matching constructs are converted to a fast decision trees by compiler. There are some "lazy" approaches to pattern matching.
Or you can just provide a list of transforming (maybe some composition of transformations) functions to your generic pattern matching function. It's almost the same as using "visitors", but you don't need to call "The Team Architect™, for supervising the object oriented quality of your software" :)