Visitor as a sum type (2018)

10 points by qiu

ahelwer

I found this section in Crafting Interpreters fairly insightful on this topic.

The Expression Problem

This problem is more fundamental than it may seem at first. We have a handful of types, and a handful of high-level operations like “interpret”. For each pair of type and operation, we need a specific implementation. Picture a table. Rows are types, and columns are operations. Each cell represents the unique piece of code to implement that operation on that type.

An object-oriented language like Java assumes that all of the code in one row naturally hangs together. It figures all the things you do with a type are likely related to each other, and the language makes it easy to define them together as methods inside the same class. This makes it easy to extend the table by adding new rows. Simply define a new class. No existing code has to be touched. But imagine if you want to add a new operation—a new column. In Java, that means cracking open each of those existing classes and adding a method to it.

Functional paradigm languages in the ML family flip that around. There, you don’t have classes with methods. Types and functions are totally distinct. To implement an operation for a number of different types, you define a single function. In the body of that function, you use pattern matching—sort of a type-based switch on steroids—to implement the operation for each type all in one place. This makes it trivial to add new operations—simply define another function that pattern matches on all of the types. But, conversely, adding a new type is hard. You have to go back and add a new case to all of the pattern matches in all of the existing functions.

Each style has a certain “grain” to it. That’s what the paradigm name literally says—an object-oriented language wants you to orient your code along the rows of types. A functional language instead encourages you to lump each column’s worth of code together into a function.

A bunch of smart language nerds noticed that neither style made it easy to add both rows and columns to the table. They called this difficulty the “expression problem” because—like we are now—they first ran into it when they were trying to figure out the best way to model expression syntax tree nodes in a compiler.

The book then goes on to use the Visitor pattern, which is indeed a hacked-together object-oriented way of getting functional-style pattern matching.

andyc
which is indeed a hacked-together object-oriented way of getting functional-style pattern matching.

I don't agree with this, in two ways:
1. The visitor pattern doesn't give you pattern matching. It gives you a function per node type, so in this sense it's less flexible than functional pattern matching.
2. The visitor pattern allows you decouple common traversal logic from the operation being performed on the AST, which is more flexible than pattern matching.
For example, I recently looked at Ruff, and it has evaluation order visitor base classes, and text order visitor base classes.

Another simple that decoupling lets you do is find node types at arbitrary depths. Example here: https://lobste.rs/s/jdgjjt/visitor_pattern_considered_pointless#c_jksgge (the comments are about how visitors are NOT pointless)
```
class Collect(visitor.TypedVisitor):  # subclass of SimpleVisitor

    # no traversal logic in this class

    def visit_str_expr(self, o: StrExpr) -> None:
        raw_string = format_strings.DecodeMyPyString(o.value)
        self.global_strings.Add(o, raw_string)
```
You can't find Str nodes or Var nodes at arbitrary depths with functional pattern matching.

Pattern matching tends to duplicate the traversal logic, which is what you want in some cases, but not others.

Compilers / type checkers / interpreters may have dozens of different visitors representing dozens of algorithms.

Crafting Intepreters has 2 instances of the visitor, which is enough to illustrate the extraction of the traversal logic:
```
class Resolver implements Expr.Visitor<Void>, Stmt.Visitor<Void> {

class Interpreter implements Expr.Visitor<Object>,
                             Stmt.Visitor<Void> {
```
Like Ruff, it generates the visitor base class with a script, from an AST definition (similar to Zephyr ASDL in https://oils.pub)

Just by reading those signatures, it should be clear that it's not like pattern matching.

Visitors are indded a bit twisty, and I would not use them unless there are multiple algorithms on the AST. And I noticed lots of people don't like the pattern, including https://grugbrain.dev/

But it is useful, depending on the problem, and widely used in many codebases.
- ahelwer
  I'm not sure how visitors get you traversal logic in a special way. Consider the case of (in Java):
  
  public Object visitInfixOp(InfixOp op) { Object left = op.left.accept(this); // Textual-order traversal logic here Object right = op.right.accept(this); // Evaluation-order traversal logic here }
  
  vs. in pattern matching, in the middle of a giant switch statement you would have something like (in OCaml):
  
  ... | InfixOp {left; right; op} -> let left = eval(left) in (* Textual-order traversal logic here *) let right = eval(right) in (* Evaluation-order traversal logic here *) ...
  
  It seems pretty similar.
  - andyc
    
    The difference is the ... you omitted from the "giant switch statement".
    
    Try writing out 2 different traversals of a medium-sized language: find all the string constant nodes at arbitrary depths, and find all the + operators. (That is not the only difference, but it is instructive)
    
    The Python example I gave above was complete -- the traversal logic is in the base class, and the derived class has one method
    
    It matters when you have multiple algorithms that walk the same tree, which is very common
    
    Or you can look more closely at the the code for Crafting Interpreters
    
    The base class is generated from the AST definition by a tool: https://github.com/munificent/craftinginterpreters/blob/master/java/com/craftinginterpreters/tool/GenerateAst.java#L141
    
    The derived classes are Resolver and Interpreter, with different parameterized types, quoted above
    
    Again, Rust has a match statement, but the rustc compiler uses visitors all over the place. The 2 techniques are useful in different situations
    
    There are many different kinds of tree traversals
    
    qiu
    
    It matters when you have multiple algorithms that walk the same tree
    
    Why not put the traversal logic in an iterator? Then, if you need to perform an operation on a specific node type, you don't need the whole match statement - just check if the current node has the type that is of interest to you:
    
    for n in nodes.iter() { if let NodeType:String(s) = n { // ... } }
    
    I like this pattern, because it doesn't need a lot of setup (like a separate class). It also doesn't couple the traversal logic with the idea of variation - the traversed object doesn't need to know if it's part of any enum.
    
    It's possible to replicate this in languages without sum types, but I think you'll have to fill out all arguments to the match() function to covers all cases, so it will be more verbose there - that's probably where the preference for visitors comes from in classic OOP languages.
  - andyc
    
    Shorter reply saying the same thing: the Rust compiler uses visitors all over the place, even though Rust has a match statement (unlike say Java)
    
    https://github.com/rust-lang/rust/blob/main/compiler/rustc_hir/src/intravisit.rs#L207
    
    https://github.com/rust-lang/rust/blob/main/compiler/rustc_ast/src/visit.rs
    
    https://doc.rust-lang.org/nightly/nightly-rustc/src/rustc_middle/mir/visit.rs.html
    
    So, pattern matching and visitors don't solve the same problem.
    
    (The Rust code seems to use a lot of macros; that is probably the equivalent of the textual code gen that Crafting Interpreters uses. The traversal logic often follows directly from the data type definitions)
  - jryans
    
    Eli Bendersky’s 2016 expression problem blog post also uses similar row / column thinking, perhaps worth a look.
  - munksgaard
    
    Functional paradigm languages in the ML family flip that around. There, you don’t have classes with methods. Types and functions are totally distinct. To implement an operation for a number of different types, you define a single function. In the body of that function, you use pattern matching—sort of a type-based switch on steroids—to implement the operation for each type all in one place. This makes it trivial to add new operations—simply define another function that pattern matches on all of the types. But, conversely, adding a new type is hard. You have to go back and add a new case to all of the pattern matches in all of the existing functions.
    
    There's some important nuance missing here. Specifically, it is only adding a new type to an existing sum type that is hard. You explicitly don't pattern match on "all the types", but only on the variants of a single sum type. Also, note that the variants of a sum type may contain duplicate "component types":
    
    type Op = Add of Int | Sub of Int
    
    Even though the types contained within each variant are identical, there is no chance of mistaking the two.