4 ms·

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?

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

lihaoyi 8y ago
> 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
- richard_shelton 8y ago
  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!
  - v-yadli 8y ago
    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.
    - richard_shelton 8y ago
      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 :)
- lomnakkus 8y ago
  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.
tom_mellior 8y ago
> 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 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.
- richard_shelton 8y ago
  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 http://gcc.gnu.org/wiki/ListOfCompilerBooks
sreque 8y ago
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.
fooker 8y ago
The Clang and Swift compilers use Visitors for just about everything AST related.

lihaoyi 8y ago

> 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

richard_shelton 8y ago
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!
- v-yadli 8y ago
  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.
  - richard_shelton 8y ago
    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 :)
lomnakkus 8y ago
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.

tom_mellior 8y ago

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

richard_shelton 8y ago
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 http://gcc.gnu.org/wiki/ListOfCompilerBooks

sreque 8y ago

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.

fooker 8y ago

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