Hacker News Reader

> 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 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.

P.S. Thanks for the real perfomance data!

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 :)

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.

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]

[1] http://gcc.gnu.org/wiki/ListOfCompilerBooks

The Clang and Swift compilers use Visitors for just about everything AST related.