Reading Time: 8 minutes

A year and a half ago I picked up Crafting Interpreters. The project guides programmers through building their own interpreters for the Lox programming language. I started writing a blog series about my progress. You can see all the posts so far right here.

Then I put it down for a while to focus on learning to teach. Now that I know how to teach (LOLOLOLOL), I’m finally getting back to it. We left off in 2019 with writing a parser. Now, it’s time to dive into chapter 7 and execute the code we have parsed.

In this chapter, we have to do two things:

1. Map each of our existing symbols in Lox to their execution in Java
2. Handle Lox encountering a symbol that isn’t in Lox, or that isn’t associated with the proper types.

This post covers the first thing. The next post will cover the second thing.

Organizing our Execution Code: The Visitor Pattern

So far, we have the following grammatical structures parsed and ready for interpretation:

1. Literal expressions (for example, the string “Hallo!”, the number 3, or the boolean true)
2. Unary expressions with a symbol and one operand (for example, the number -3 or the boolean !true)
3. Binary expressions with a symbol and two operands (like 3 <= 3 or "Polly " + " wanna cracker")
4. Grouping expressions that combine the above expressions (like (-1 + 4) < (10 * 2))

Bob explains that we have two ways to orient our code. We could do it with objects, by having each of these expressions represented as classes handling all their own operations, or we could do it with functions that switch their behavior based on which type of expression they have been passed. The former (object) pattern makes it less work to add a new expression class and more work to add a new behavior, since we have to crack open every existing class to do it. The latter (functional) pattern makes it less work to add a new behavior, since we just need to write a new function without changing existing code. Adding a new expression, though, means cracking open all the existing functions and adding a case to each.

That tradeoff, by the way, can help us decide whether to pursue an object-based or a function-based approach. We can attempt to predict whether our code is more likely to grow in the types direction or the behaviors direction, and then we can orient the solution to make it easier to do whichever one we’ll be doing more of in the future. (That’s right: it’s 2021, we’re not picking object-based or function-based patterns according to what angry dudes on HackerNews said is universally better anymore! I’ve written about this!)

But what if we sort of need flexibility in both directions?

This is where the Visitor Pattern comes in handy. We have used this pattern once in this interpreter before, to implement the printers that printed out our abstract syntax trees. Bob mentions that the visitor pattern is rather poorly understood and that its nomenclature (Visitor and accept) doesn’t help. I tend to agree.

I’m going to try to explain it now with an step-by-step walkthrough and an example: midwifery. The situation: we have three different types of at-home birth represented with classes. We want one consolidated place to keep midwifery tasks for each of the three types of at-home birth. The parents should not have to know about the midwifery tasks associated with their birth method.

Step 1: All the classes that need custom behavior implement an “Accept” method.

The superclass looks like this (example in Java):

abstract class ParentsHome {
    abstract void accept(Visitor visitor);
}

and then the subclasses might go like:

class LamazeBirthHome extends ParentsHome {
     void accept(Visitor visitor) {
         return visitor.supportLamazeBirth(this);
     }  
}

class BradleyBirthHome extends ParentsHome {
     void accept(Visitor visitor) {
         return visitor.supportBradleyBirth(this);
     }  
}

class WaterBirthHome extends ParentsHome {
     void accept(Visitor visitor) {
         return visitor.supportWaterBirth(this);
     }  
}

I chose this example as opposed to something more rooted in the software world because traditional explanations of the visitor pattern use “accept” as the name of the method, so I wanted something that fit that to help you bridge the analogy gap when you’re reading about this pattern from other sources.

The birth parent or parents are accepting a visitor with a special set of skills into their home—in this case, it’ll be a midwife. Then, when the visitor gets there, the visitor is the one with the knowledge about what needs to happen next, and they execute the method for what to do, taking in the home as an argument so they can tailor the treatment to the needs of the home they’re in.

Step 2: An interface defines the different behaviors the visitor can do.

So in our case, the Midwife class implements an interface called Visitor:

interface Visitor {
        void supportLamazeBirth(LamazeBirthHome home);
        void supportBradleyBirth(BradleyBirthHome home);
        void supportWaterBirth(WaterBirthHome home);
}

class Midwife implements Visitor {
       // implements the three methods above, presumably with medical stuff
       //  that has to happen to support each kind of birth.
}

“Visitor” is generalized here so that it can prescribe the different behaviors associated with different homes to other kinds of specialists. For example, we could add a doula to the mix like this:

class Doula implements Visitor {
       // Doulas focus more on supporting the parent and aren't medically trained
       // but they have various things they do to support a home birth, too.
}

Step 3: At call time, the visitor brings the necessary behavior to the class that needs it.

// RUNTIME WHERE BABY IS GETTING BORN

waterBirthHome.accept(midwife);
waterBirthHome.accept(doula);

One point to mention about the visitor pattern as I have explained it is that it doesn’t 100% solve the problem of having to crack open old stuff to add new stuff. Were we to add a new birth method, we need to add a new ParentsHome subclass, but we’d also have to add a method for it to our Visitor interface and then implement it in each implementor. We luckily won’t need to go change the existing ParentsHome subclasses since the accept method works for any visitor. So the visitor pattern’s convenience relies on the idea that there will be fewer types of visitor than there are types of classes to visit. Keep that in mind if you decide to bust this out on your own software.

In our interpreter, that pattern holds.

We have a tree printer and an interpreter, both of which implement Visitor, and each of which needs to be prepared to operate on four existing classes of expressions. So already we have more classes that need behavior than we have visitors that need to provide it. Plus, in our code, we have more expressions coming: conditionals, iteration, and so on. Each one will need an accept method, and we’ll need to add a method for each to our Visitor interface.

Speaking of which…

Our interpreter implements this interface (The R is a generic and not inherently part of the visitor pattern, but in this case we need it to return different results for each kind of expression):

interface Visitor<R> {
    R visitBinaryExpr(Binary expr);
    R visitGroupingExpr(Grouping expr);
    R visitLiteralExpr(Literal expr);
    R visitUnaryExpr(Unary expr);
}

I won’t show you the whole interpreter (Bob does in the book, and here is the code in full), but I’ll choose one method to demonstrate the idea:

@Override
public Object visitUnaryExpr(Expr.Unary expr) {
        Object right = evaluate(expr.right);

        switch (expr.operator.type) {
            case MINUS:
                checkNumberOperand(expr.operator, right); //we'll get to this later
                return -(double) right;
            case BANG:
                return !isTruthy(right); //we'll also get to this later
        }

        ...
}

You can see that what we are doing here is returning the Java equivalent of our Lox type if it is a unary expression (a literal expression with a – or a ! operator in front of it). We check which of the operators it is: if the operator is a minus and the operand is a number, we cast the operand to a number and return the negated version. If the operator is a bang, then we check if the operand is true or false, switch that value with a bang in Java, and return the result. So it goes for each type of expression, with the interpreter implementing a method to figure out what to evaluate that expression to.

We dispatch one of these methods when an expression needs to be evaluated:

private Object evaluate(Expr expr) {
    return expr.accept(this); // "this" is, in this case, an instance of the interpreter
}

We call that from another interpreter method that executes in the main Lox loop. I’ll show you that in the next post because it has some error handling around it that’s more germane to the next post than this one 🙂.

If you liked this post, you might also like…

The rest of the Crafting Interpreters series

This post about structural verification (I’m just figuring you’re into objectcraft, so)

This post about why use, or not use, an interface (specifically in Python because of the way Python does, or rather doesn’t exactly do, interfaces)