dgreensp
5 days ago
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.
mhh__
5 days ago
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.
xelamonster
5 days ago
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.
dapperdrake
5 days ago
Someone else beat me to it. Will answer anyway.
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.
[1] http://somethingdoneright.net/2015/07/30/when-object-orienta...
[2] https://lobste.rs/s/vbivyq/synchronous_core_asynchronous_she...
[3] https://moyix.blogspot.com/2022/09/someones-been-messing-wit...
[4] https://news.ycombinator.com/item?id=32738206
[5] https://matklad.github.io/2023/11/15/push-ifs-up-and-fors-do... Note, that Fortran and Functional Analysis got this right ages ago. Excuses are now few and far between. All of use are late to the party.
[6] https://news.ycombinator.com/item?id=38282950
Edit: typo
kazinator
3 days ago
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:
(mapcar (lambda (node) (visit node visitor)) node-list)
We still have to write method specializations the different combinations of node and visitor types we need, for the generic function visit. (defmethoc visit ((left if-statement) (right print-visitor))
... logic for printing if statement
)
It's just less fragmented than the single dispatch version, because we don't have to perform two single dispatches to obtain one.PoignardAzur
5 days ago
What do you mean by "multiple dispatch"? What's an example of a multiple dispatch program?
kazinator
3 days ago
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.
Jtsummers
5 days ago
https://en.wikipedia.org/wiki/Multiple_dispatch
It means dynamic dispatching based on the types of multiple arguments not a single argument.
ebcode
5 days ago
here's an article with examples in Python and Julia:
https://medium.com/@AlexanderObregon/how-pythons-multiple-di...