Hacker News Reader

Comment by lihaoyi | 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

View on HN

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.

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

Reply on news.ycombinator.com