You don’t come across visitors every day, and they aren’t something to reach for instead of a simple switch, but if you are writing a Webpack or ESLint plugin or something like that, you might encounter them for traversing an AST. It’s not just an OO thing, either.
I learned the visitor pattern in pretty ideal circumstances: from a classmate, back in college, when we were writing a compiler together for a class project, and it was just what we needed.
The right conditions for a visitor are when you have a data structure with many different “node” types, and the traversal logic is not simple. In addition, you will be doing many different traversals. You might also be doing transformations on the structure. You might have a library running the traversals/transformations provided by the code that uses the library. There could be correctness or memory management considerations involved that you don’t want the client to have to worry about. You might want to “pipeline” multiple transformations, doing several manipulations in one traversal, in an efficient way. Common traversals might care about only certain types of nodes, like a particular lint rule might just be looking at string literals or references to global variables, but it needs to walk the entire syntax tree of a file of source code.
The problem with the visitor pattern is that it hides the traversal which can be good for some things but then lead to weird bugs (e.g. imagine walking a tree with a buffer in the visitor, then the thing that runs your visitor runs the nodes more than you expect and so on) e.g. I've seen bad code slip past a compiler because the visitor didn't realize it was being run on every node in the tree so it never actually found the pattern it was trying to match.
I wrote some Typescript AST walking code recently, and could not for the life of me figure out what the advantage of the visitor pattern was here. It seemed to only overcomplicate the implementation, made it much more difficult to track where you were in the tree and target specific nodes and seemed much easier to just call getChildren and iterate.
Had a very similar experience to yours with one important exception. The visitor pattern is relevant for traversing ASTs in single dispatch languages. Most notably, this includes Java and C++.
The alternative concept is multiple dispatch and it is way more anti-fragile.
This is where the next step in college literally was to learn the concept of cargo-culting. The concept of multiple dispatch is considerably more useful than single dispatch.
Many years later the realization hit, that OOP,
singletons, DB mocking and monads are the hard parts
[1,2]. Then you can even skip multiple dispatch in
favor of low latency. C++ wants this but its
ecosystem has no idea (as in zero) of how to get
there [3,4,5,6] (-Ofast -fno-fast-math). Then the
"Patterns" (capital P) melt away.
On a semi-related note, it seems worth pondering whether strict typing requirements and/or a missing garbage collector make macro programming and AST work so hard in non-lisp languages. Think I read somewhere that some people considered Rust macros hard. Sounded like they were harder than they should be, which means that the language designers piled on incidental complexity. Macros are difficult enough as it is. And worth it. Even Python pilfered the "with" syntax.
The visitor pattern is relevant in multiple dispatch also; just most of its boilerplate goes away, so that only the visitation remains: traverse the AST (or whatever structure) and invoke the given method with the node and visitor as arguments.
For list in Common Lisp, the ancient mapcar function can do this:
Multiple dispatch means that a method is selected based on the run-time type of more than one argument, rather than just "the object" (leftmost argument).
This is beneficial to the Visitor Pattern, because the pattern needs to traverse a structure with polymorphic nodes, and invoke logic that is based on the type of each node, and on the type of the visiting object.
The familiar single-dispatch Visitor Pattern introduces an emulation of double dispatch via two single dispatches. First a "accept" method is invoked on each Node of the traversed structure, taking the visitor as the argument. This accept method is a stub which calls the "visit" method on the visitor, passing the node as an argument. The static type of the node is known at that point, so the visitor can statically dispatch different overloads for different nodes. I possibly have some of this backwards, but it doesn't matter; it will work with different naming.
Under multiple dispatch, we can just call a single generic function visit which is dispatched for the node and visitor in one step. If it is a printing visitor, it prints the node, and so on.
This reminds me of when I was still in university.
During our compilers course we used the "Modern Compiler Implementation in Java" book. Because I was really into FP at the time, I instead used the "Modern Compiler Implementation in ML" version of this book (which was the original, the Java and C versions were made to make it more accessible).
We noticed during the course that my version was missing a whole chapter on visitors, likely because ML's pattern matching made this kind off trivial.
One of the other students made a similar remark, that software design patterns are sometimes failures of the language when they have no concise way of expressing these kinds of concepts.
«Design patterns are bug reports against your programming language» (Peter Norvig)
This is pithy, but only applies to some rote design patterns which you have to code every time because the language lacks a good way to factor them out.
Wider-scale patterns often express key approaches enabled by the language, and they can't go onto a one-size-fits-all library or language feature, because you tailor their implementation to your specific needs. They are less like repetitive patterns of a brick wall, and more like themes or motifs that keeps reappering because they are fruitful.
> that software design patterns are sometimes failures of the language when they have no concise way of expressing these kinds of concepts.
This is _the_ most common comment you hear in any language design discussion, and it's so boring. Java doesn't have visitors because it's the best the language could come up with. It has visitors because of a particular dogmatic adherence to OOP principles. A fundamentalist reading that says you're never supposed to have any control flow, only virtual method calls. Visitors come from the same place as Spring and the infamous AbstractSingletonProxyFactoryBean.
Java is perfectly capable of expressing an enum, and you can easily switch on that enum. The limitation that you have to express that enum as a type hierarchy, and therefore encounter the double dispatch problem is entirely OOP brainrot.
I think this is a bit of an exaggeration, unless you're talking about very modern versions of Java (sealed interfaces and better pattern matching). Java has no good way to attach different data types to each enum variant (a la ADTs) except inheritance, and until recently switching over class types was a PITA.
Enums were added in java 5 and I'm pretty sure you could switch on them from day one. From that point you just need a single class (call it TreeNode) that holds a value of that enum (say the node type) and some fields, and you can navigate it and switch over the node type without any sort of visitors.
"But what if I have a leaf node. Wont that have a child pointer, even though it doesn't need it" Sure it will. Who cares. You don't need to make it harder than it has to be. All the new stuff just enables you to get more type safety, it was never necessary.
You're getting downvoted but I don't think you're getting the benefit of understanding the disagreements. The benefit of visitor is for when you need multiple different TreeNode classes with different aspects, either different member variables or different methods/implementations themselves. In that case, the unused child ptrs are the smaller of the class modeling difficulties. For example, if you had a single base TreeNode class with the enum, after switching on the enum you need to explicitly downcast to the type. The dual-dispatch approach bakes this into the visit-accept protocol.
The last time I worked on a complex syntax tree structure, I used the approach you suggested because _editing_ a Visitor suite is a pain in the rear. Only terms that had special payload data (numbers, pointers to metadata objects, etc.) need downcasting.
Indeed there should be no control flow, only computing values of function application :)
Indeed, this is also absolutism, just of a different kind, that proved to be somehow more fruitful in the application programming domain. And, to my mind, it's mostly because functions can be pure and normally return a value, while methods are usually procedures mutating some hidden state.
OTOH in a different domain, system programming, control flow is a good abstraction over the close-by hardware, mutable state is all over the place in the form of hardware registers, and it's more fruitful to think in terms of state machines, not function application.
If a tool forced you to do repetitive irrelevant motions, it's just a wrong tool, you need to find or create a better one.
My experience was some 20-odd years ago, when I was trying to learn design patterns by implementing them in PHP. Specifically, I built the whole array of abstract and concrete factories and all that, until I realised that it can all be replaced by something like:
$className = "MyClass";
$classInstance = new $$className();
I disagree with the main thrust of the article, that the Visitor pattern is primarily a primitive way to do pattern matching.
For one, the Visitor pattern (as written in the article) fails to fulfill a core feature of Rust pattern matching, which is having a compact language to describe when something matches based on values, as opposed to the concrete type.
For another, you could equally well say that if-else blocks or ternary statements are also primitive pattern matching, if you're willing to stretch things that far.
In my view, the core reason people reached for the Visitor pattern in the past is that old Java didn't have convenient lambdas (anonymous functions). Visitors let you create an interface that mimics functional map.
Newer versions of Java have made lambdas much more convenient, so there's less motivation to reach for the Visitor pattern. You also saw this development in C#, where delegates were a language feature that often obviated rolling your own Visitors.
Visitors let you do both. That said, I have used visitor a lot and it never was in a context where lambdas would have helped. There wasn't any variability in the code path such that I might have different implementations of a function at different times, and as the Visitor would have some state in it (an accumulator, a set of config variables, etc.) composing those as lambdas and dispatching to them seems like it would have been less convenient.
I haven't looked at patterns since the GOF days, so maybe they grew closer to Alexander's as they matured, but the original ones were very much ways to speak about things so they'd be politically palatable in an everything-is-an-object world.
You just wanted some data? "Flyweight". You just wanted some functions? "Strategy". etc.
It amused me that Alexander's _A Pattern Language_ was 90% about habitability and 10% about building whereas I had the feeling GoF was the opposite.
That is, I believe Alexander's version of design patterns would have things like "Intention Revealing Names" and code reviews focusing on "Clarity, Consistency, and Correctness (in that order)"--things that help subsequent developors live in and enjoy the code and design.
Software exposes (at least) two faces ... the user facing one ("habitability") and the (future) developer facing one ("building").
GoF approaches from the "building" side since it was created by and for programmers. Another way of thinking about this is that GoF is describing the experience of the design as a developer having to "inhabit" it, rather than a user's experience of the same.
That's why Alexander is not a particularly useful book for builders, since it focuses on the user's experience of the design when inhabiting it, rather than the constructors' experience of the same design when creating or modifying it.
A version of GoF that focused on the user experience would be a completely different book than the one we know.
An insightful comment, but to be fair many important GoF design patterns like Composite and Decorator are genuinely object oriented, leveraging polymorphism and interfaces to produce order and elegance.
Object-oriented order and elegance compared to an object-infested mess of special cases and complications. Remember that 25 years ago C++ wasn't a pleasant place and Design Patterns was an impressive step forward.
Oh, I do remember the grim story really well. I was there. I still have all the books. And the scars.
Back then I was a young innocent programming soul trying to reconcile C++ and GoF and UML and all that. And Modern C++ Design. And const here const there const copy constructor by reference.
I spent about 12 years doing C++ at the very peak of its OOP hype and did the same... then finally left, certain that I would hate doing "real" work in any other language, and a funny thing happened...
I realized I was suffering from severe Stockholm Syndrome. Node.js was just.... so gd easy to do anything in. Maybe too easy (a la leftpad), but build/deploy cycles were instantaneous, adding new libraries was easy- again maybe too easy, JS has a tiny fraction of the footguns and you don't have to know them all to write code that isn't going to blow up on you or cause memory leaks and performance issues.
Python... was the same. I have even taken some dives into Java, and while I don't love the architectural monuments Java devs tend to produce, its still less of a hassle than C++.
I was so happy when there was a move towards templates and data oriented design and the priests of OOP were getting knocked off their pedestals- for a period you were at risk of getting shunned for not kneeling at the gods of OOP and the GOF book and UML diagrams.
I remember arguing for years with my father (also a programmer) about him writing either vanilla C, or writing C++ in (what would become) the data-oriented style.
...and look at me now!
I collect things in arrays, with no objects, preferrably in pure C. No classes, no objects, just arrays and transforming functions everywhere.
FP languages have their own patterns. Some of them can be plausibly cast as "fixing weaknesses" in them, too.
Multiparadigm languages end up with lots of patterns you need to learn, because while multiparadigm languages may support many approaches to a given problem, generally there are definitely better and worse approaches, specific to the language in question, and between the number of options, the subtly of their implementation details and how those interact with the problem, and the specific preferences of the language itself (because all multiparadigm languages still have preferences), it can take a multiparadigm language community a decade to work out the best pattern for a given task. The existence of many options inevitably expands the number of wrong options, or if you prefer, "distinctly suboptimal" options, as well.
I think the visitor mimics pattern matching, but it really behaves/feels different. I think the visitor is really closer to a bridge from OOP land into FP land.
In FP its difficult/impossible to add new types but simple to add new mappings/pipelines for those types.
In OOP its easy to add new types but difficult/impossible to add new mappings/pipelines for those types (try transforming a POJO without lombok @Builder and @Value).
The visitor pattern (an OOP concept) allows us to more easily add a new mapping/pipeline for a set of related types. Normally in OOP this would involve adding a new method to a base class, implementing these new "mappings" in each subclass. With the visitor instead you just implement the new visitor, this allows the logic for this particular "kind" of mapping (visitor) to be grouped together, rather than represented by a method on a base class.
Honest question: What is your current estimate of how much the OOP side is impacted differently by Composition vs. Inheritance, especially when contrasted with FP?
Honestly, for all the OOP talk about composition its rarely done well and afaik no major OOP language supports that paradigm, so it's a bit tough to say, as a really good take on it from a language level could affect my opinion a bit. Java 21 seems promising in this regard with switch + record, but the legacy java layer seems to drag it down.
Currently I'm not entirely convinced composition is a silver bullet that will save OOP and from what I've seen it is also somewhat antithetical to OOP - you are constructing a bunch of "has-a" relationships and expecting it to relate to behaviour (generally done by inheritance / "is-a"). So in "saving" OOP composition will likely kill it.
Instead I think we'll see more (especially newer) languages move towards FP by introducing composition (like rust / golang interfaces). I think it's because composition maps quite well to the FP concept of a composite data type (like a struct / tuple) as well as function composition. But at the same time I think we'll see a lot of in-between languages (again rust / golang) where we take some stuff from procedural+oop and mix it with a bit of functional programming (especially in data pipelining areas). Similar (but opposite) to how Java 8 introduced the streams monad.
I always tell people who obsess over design patterns as clean code and good coding practices to remember that design patterns often indicate a lack of language features.
For example, are you using a Builder? Would you use the Builder pattern if the language had named variables in arguments?
A builder can allow you create different kinds of objects from a common stem. They don't have to be bags of properties.
Say, SQLAlchemy is all built on chaining builder-like methods, which make one of the finest DSLs that translates to SQL. In the end, you build a representation of a SQL statement, but in no way could that work with named arguments alone.
Instead, consider named arguments as nice shortcuts over curried functions.
> Would you use the Builder pattern if the language had named variables in arguments?
Yes, absolutely. I see it all the time in the Ruby ecosystem and have used it myself in Ruby. Many times it gets called by a different name. I've seen it in Python and Elixir too.
I suppose any feature you need is a design pattern, and everything from functions onup are whys of implementing features your language doesn't natively support.
Whenever design patterns come up, folks start talking about language features. First of all, it's about natural language to describe a way of doing something. If you don't have a language to describe a design, then folks could and often would implement incompatible pieces. By having a common language, you solve for that. If I gave you two piece of wood and asked you to join them together. How would you? Does it matter how you join them? It absolute does matter. You might use nail, you might use screw, you might do glue. In carpentry there are design pattern for joints. You can tell someone to use a butt joint, a box joint, a pocket-hole joint, etc. Without these higher level language of design. You will have to explain and you might find out that explanation is not enough, you would need diagrams or models. The same with programming design patterns, without it, you will waste time explaining or drawing diagram. For the professional, these are the colloquial phrases of programming. If you're an enterprise application developer, or a game programmer or a cloud dev, your languages and often used patterns would vary. I say this as someone that learned lisp as a 2nd language a long time and a fan of functional languages. DPs are worth knowing and understanding.
Anyone who is interested in pattern matching and the visitor pattern (and the benefits of various encodings of state and behavior) who hasn't seen them should check out:
The author took the thesis in one direction, but there's another interesting way to think of it.
C++ is an epitaph for every discarded concept in OO design. Diamond inheritance, generics to a fault, operator overloading to a fault, the richness of STL types. Those "patterns" are dead, but the language features must continue to be supported.
Language features can be deprecated as obsolescent and after a period of obsolescence, removed.
"implicit int" declarations are no longer a C language feature. The (void) parameter list is now obsolescent; as of C23, () means the same thing as (void), like in C++.
Design patterns can end up in libraries. But library and language features are the same. A popular library which everyone uses cannot be thrown out overnight any more than a language feature.
> Now knowing about pattern matching, this is how I came to realise that the visitor pattern was pattern matching in an OO way.
The programming language needs to be very expressive to replace the visitor pattern with pattern matching. For example, you need GADTs. The cool thing about static languages with OOP is that OOP can hide a lot of type-level complexity. Also, in languages with runtimes optimized for virtual calls (e.g., the JVM, V8), pattern matching can have less performance than the visitor pattern, despite pattern matching now being a reality on the JVM at least (e.g., Java, Scala have pattern matching).
The difference between pattern matching and the visitor pattern is the difference between tagless-initial and tagless-final encodings, or data versus Church-encodings. And as a software engineer, it's good to be aware of their strengths and weaknesses.
People making this claim (that design patterns are just missing language features) always mention Visitor, but stop short of mentioning other design patterns, such as Observable/Listener, but also, the even less obvious: Monad or the Free Monad (i.e., still a design pattern, despite being able to comfortably express it in your language).
The visitor pattern is a way of getting multiple dispatch in a language with single dispatch.
It can also be seen as a way of encoding a functional solution to the expression problem in an OO language, which is useful when you have a set of objects and want to make it easy to add new operations to them, not create new types of objects.
If I may nitpick, the call to children’s accept methods should be in the visitor, not the parent. Imagine you’re writing an XMLGeneratorVisiter. The visit method for the parent would print <parent>, call child accepts, and then print </parent>. If you do it the way it is done here you lose the control on when the children are visited.
Also, the point of the visitor pattern is not just pattern matching/polymorphism. Of course you could do it with polymorphism or conditionals or whatever. But the visitor pattern reduces coupling and increases cohesion. So you get a more maintainable, testable code base. Pattern matching with a candied switch doesn’t give you that.
I've seen it said that Alexander working on this stuff just at the moment of peak OOP-timism is a great shame/tragedy. I'm inclined to agree.
Functional purists like to glibly say that their patterns are discovered rather than invented. I used to Pooh Pooh this a bit. Then I had to write a class just to have a function to call. They're right.
Design patterns are the real language though. A feature of a real language is that you can present a new concept. For example, a promise in an async programming is such a concept and it is not tied to a particular notation. Once you get that concept working in a notation that does not have it, then it can be fused into a notation, but then it becomes sort of frozen and ceases to evolve.
I got about halfway before completely losing the thread as I had no idea what was being said, unfortunately.
Is "visitor" pattern ever defined in this article?
Is there anything in this article explaining the assertion "Design Patterns Are Temporary, Language Features Are Forever"? I couldn't penetrate the specific example being discussed.
This is an article about design patterns (in particular the 1994-200x craze for them after the Gang of Four book was published). Having emerged from that era might be table stakes for understanding this article.
Visitor pattern is a code inversion where inheritance and/or function overloading fills in for a missing language feature (concise runtime pattern matching on types). It has its pros and cons but seemed like opening your third eye circa 1995.
I have a bug/hate relationship with the visitor pattern: how do I implement it without causing a stack overflow in languages without tail recursion optimization?
It always ends up in a loop with a lot of ifs inside.
I learned the visitor pattern in pretty ideal circumstances: from a classmate, back in college, when we were writing a compiler together for a class project, and it was just what we needed.
The right conditions for a visitor are when you have a data structure with many different “node” types, and the traversal logic is not simple. In addition, you will be doing many different traversals. You might also be doing transformations on the structure. You might have a library running the traversals/transformations provided by the code that uses the library. There could be correctness or memory management considerations involved that you don’t want the client to have to worry about. You might want to “pipeline” multiple transformations, doing several manipulations in one traversal, in an efficient way. Common traversals might care about only certain types of nodes, like a particular lint rule might just be looking at string literals or references to global variables, but it needs to walk the entire syntax tree of a file of source code.