Reading 27: Little Languages II

Since our introduction to recursive data types, we’ve been implementing functions on these types using the Interpreter pattern:

• declare the operation as an instance method in the interface that defines the datatype, and
• implement the operation in each concrete variant.

In terms of the Composite pattern, composite variants (e.g. Concat in Music, Not in Formula) will implement the operation recursively, and primitive variants (e.g. Note in Music, Variable in Formula) will implement base cases.

For example, here’s the Boolean formula recursive datatype again:

Formula = Variable(name:string)
          + Not(formula:Formula)
          + And(left:Formula, right:Formula)
          + Or(left:Formula, right:Formula)

Suppose we want to add an operation variables to Formula that returns the set of all variable names mentioned in the formula. We saw how to do this in a reading exercise in Recursive Data Types (at the time, using immutable set type ImSet).

interface Formula {
    // ... other operations ...
    /** @returns all the variables that appear in this Formula */
    variables(): Set<string>;
}

class Variable implements Formula {
    public readonly name: string;
    // ... constructor, other operations ...

    public variables(): Set<string> {
        return new Set([this.name]);
    }
}

// assume we have this helper function:
/** @returns the union of set1 and set2 */
function setUnion(set1: Set<E>, set2: Set<E>): Set<E>;

class Not implements Formula {
    public readonly formula: Formula;
    // ... constructor, other operations ...
    public variables(): Set<string> {
(missing answer)
    }
}
class And implements Formula {
    public readonly left: Formula;
    public readonly right: Formula;
    // ... constructor, other operations ...
    public variables(): Set<string> {
        return setUnion(this.left.variables(), this.right.variables());
    }
}
class Or implements Formula {
    public readonly left: Formula;
    public readonly right: Formula;
    // ... constructor, other operations ...
    public variables(): Set<string> {
        return setUnion(this.left.variables(), this.right.variables());
    }
}

Dynamic dispatch of method calls is what powers the Interpreter pattern.

Understanding dynamic dispatch requires recalling the distinction between static type and dynamic type. The static type of a variable or method call return is the type found in its declaration. Because it is declared in the code, it is known to the compiler at compile-time.

But at runtime, an object variable or method call return refers to an actual object value in memory. This object has a type, called its dynamic type, which is the class it was constructed from.

Dynamic dispatch means that the dynamic type of the object value is used to decide which method body to execute. If a variable is declared as Formula f, but the dynamic type of its value is a concrete type that implements Formula, then the code that runs when we call f.variables() is that concrete type’s implementation of the variables method. If f points to a Not object, then f.variables() runs Not.variables().

The dynamic type of an object value does not have to be identical to the static type of a variable that points to it. When the static type is an interface, in fact, then the dynamic type is always different, because a dynamic type must be a class. (Recall that interfaces don’t have constructors, so only a class can produce an object value at runtime.)

But the dynamic type must be consistent with the static type in an important way: the dynamic type is always a subtype of the static type. This guarantees that any method we can call for the static type also exists in the dynamic type, with the same or stronger spec. Not is a concrete variant class that implements the Formula interface, so it is a subtype of Formula. TypeScript enforces this requirement by static checking; you can’t, for example, just write f = "not", because string is not a subtype of Formula.

const f1: Formula = new And(new Variable("x"), new Not(new Variable("y")));
const f2: Not = new Not(new Variable("y"));

Downsides of Interpreter pattern

Going back to the functional definitions you wrote in the Recursive Data Types reading exercise:

variables(Variable(x)) = setAdd(x, emptySet())
variables(Not(f))      = variables(f)
variables(And(f1, f2)) = setUnion(variables(f1), variables(f2))
variables(Or(f1, f2))  = setUnion(variables(f1), variables(f2))

Translating those cases directly into code on our classes from above, we’d like to write something like this:

function variables(f: Formula):Set<string> {
    switch(f) {
    case (variable: Variable):
        return new Set([variable.name]);
    case (not: Not):
        return variables(not.formula);
    case (and: And):
        return setUnion(variables(and.left), variables(and.right));
    case (or: Or):
        return setUnion(variables(or.left), variables(or.right));
    }
}

Bad pattern matching in TypeScript

function variables(f: Formula):Set<string> {
    if (f instanceof Variable) {
        const variable = f as Variable;
        return new Set([variable.name]);
    } else if (f instanceof Not) {
        const not = f as Not;
        return variables(not.formula);
    } else if (f instanceof And) {
        const and = f as And;
        return setUnion(variables(and.left), variables(and.right));
    } else if (f instanceof Or) {
        const or = f as Or;
        return setUnion(variables(or.left), variables(or.right));
    } else {
        throw new Error("don't know what " + f + " is");
    }
}

function variables(f: Formula):Set<string> {
    if (f instanceof Variable) {
        const variable = f as Variable;
        return new Set([variable.name]);
    } else if (f instanceof Not) {
        const not = f as Not;
        return variables(not.formula);
    } else if (f instanceof And) {
        const and = f as And;
        return setUnion(variables(and.left), variables(and.right));
    } else if (f instanceof Or) {
        const or = f as Or;
        return setUnion(variables(or.left), variables(or.right));
    } else {
        throw new Error("don't know what " + f + " is");
    }
}

To find our way to a different approach, consider what we want: a function on a recursive data type. Instead of thinking about the function as a piece of code, use the big idea from Little Languages I: representing the function as data.

Our example operation has the type signature:

variables : Formula → Set<‍string>

Can we represent it as a lambda expression instead?

const variables = (f: Formula) => {
    // ... did that help?
};

This doesn’t get us anywhere. The body of the lambda still only knows that f is a Formula, and that’s not enough to implement an appropriate recursive or base case of extracting variables.

Let’s try defining a new type instead, specifically to represent functions on Formula, implemented case-wise:

/**
 * Represents a function on different kinds of Formulas.
 * @param <R> the type of the result of the function
 */
interface FormulaFunction<R> {

    /** @returns this applied to `variable` */
    onVariable(variable: Variable): R;

    /** @returns this applied to `not` */
    onNot(not: Not): R;

    /** @returns this applied to `and` */
    onAnd(and: And): R;

    /** @returns this applied to `or` */
    onOr(or: Or): R;
}

Now define the variables operation as a class that implements FormulaFunction:

class VariablesInFormula implements FormulaFunction<Set<string>> {

    // The base case works nicely:

    public onVariable(variable: Variable): Set<string> {
        return new Set([variable.name]);
    }

    // But we're not sure how to implement recursive calls:

    public onNot(not: Not): Set<string> {
        return ???; // how to apply this to not.formula?
    }

    public onAnd(and: And): Set<string> {
        return setUnion(???); // how to apply this to and.left & and.right?
    }

    public onOr(or: Or): Set<string> {
        return setUnion(???); // how to apply this to or.left & or.right?
    }
}

The code for onNot, onAnd, and onOr would be easy to write, but only once we understand how to make the recursive calls that apply the function — this — to their arguments’ Formula children. If we can answer that question, we’ll also answer the question of how to use one of these Variables­In­Formula objects in the first place:

const f: Formula = ...;
const getVariables: FormulaFunction<Set<string>> = new VariablesInFormula();
const theVariables: Set<string> = ...; // how to call getVariables on f?

How can we go from calling some method on a Formula object — like f in this code — to calling the variant-specific method we need? We use double dispatch, which means two method calls in succession:

• the first method call uses dynamic dispatch to reach a concrete variant (e.g. And, Or, etc.)
• the variant then makes a second method call, also using dynamic dispatch, on the object representing the recursive function (e.g. VariablesInFormula, or some other implementation of FormulaFunction).

The first method call serves as an entry point for clients to invoke their function by passing the function as a parameter:

interface Formula {

    // ... other operations ...

    /**
     * Call a function on this Formula.
     * @param <R> the type of the result
     * @param fn the function to call
     * @returns fn applied to this
     */
    callFunction<R>(fn: FormulaFunction<R>): R;
}

And we’ll implement this callFunction operation in each variant to make the second function call, with each concrete variant now taking responsibility for revealing its dynamic type to the Formula­Function:

class Variable implements Formula {
    // ... fields, other methods, etc. ...
    
    public callFunction<R>(fn: FormulaFunction<R>): R {
        return fn.onVariable(this);
    }
}
class Not implements Formula {
    // ... fields, other methods, etc. ...
    
    public callFunction<R>(fn: FormulaFunction<R>): R {
        return fn.onNot(this);
    }
}
class And implements Formula {
    // ... fields, other methods, etc. ...
    
    public callFunction<R>(fn: FormulaFunction<R>): R {
(missing answer)
    }
}
class Or implements Formula {
    // ... fields, other methods, etc. ...
    
    public callFunction<R>(fn: FormulaFunction<R>): R {
(missing answer)
    }
}

So a call to callFunction, as implemented by all four variants, immediately turns around with a call to the appropriate onVariant method of the passed-in function. Now we can complete our recursive implementations in Variables­In­Formula, and call it:

class VariablesInFormula implements FormulaFunction<Set<string>> {
    
    public onVariable(variable: Variable): Set<string> {
        return new Set([variable.name]);
    }
    
    public onNot(not: Not): Set<string> {
(missing answer)
    }
    
    public onAnd(and: And): Set<string> {
        return setUnion(and.left.callFunction(this),
                        and.right.callFunction(this));
    }
    
    public onOr(or: Or): Set<string> {
        return setUnion(or.left.callFunction(this),
                        or.right.callFunction(this));
    }
}

const f: Formula = ...;
const getVariables: FormulaFunction<Set<string>> = new VariablesInFormula;
const theVariables: Set<string> = ??? ;

Suppose we represent the formula (P ∨ Q) ∧ ¬R. Following the datatype definition, the structure is:

And( Or(Variable("P"), Variable("Q")),
     Not(Variable("R")) )

Let f be that Formula instance.

class And implements Formula {
    public callFunction<R>(fn: FormulaFunction<R>): R {
      return fn.onAnd(this);
    } /* ... rest of class not shown */
}
class VariablesInFormula implements FormulaFunction<Set<string>> {
    public onAnd(and: And): Set<string> {
        return setUnion(and.left.callFunction(this),
                        and.right.callFunction(this));
    } /* ... rest of class not shown */
}
class Or implements Formula {
    public callFunction<R>(fn: FormulaFunction<R>): R {
      return fn.onOr(this);
    } /* ... rest of class not shown */
}
class VariablesInFormula implements FormulaFunction<Set<string>> {
    public onOr(or: Or): Set<string> {
        return setUnion(or.left.callFunction(this),
                        or.right.callFunction(this));
    } /* ... rest of class not shown */
}
class Variable implements Formula {
    public callFunction<R>(fn: FormulaFunction<R>): R {
        return fn.onVariable(this);
    } /* ... rest of class not shown */
}
class VariablesInFormula implements FormulaFunction<Set<string>> {
    public onVariable(variable: Variable): Set<string> {
        return new Set([variable.name]);
    }  /* ... rest of class not shown */  
}
class Not implements Formula {
    public callFunction<R>(fn: FormulaFunction<R>): R {
        return fn.onNot(this);
    } /* ... rest of class not shown */
}
class VariablesInFormula implements FormulaFunction<Set<string>> {
    public onNot(not: Not): Set<string> {
      return not.formula.callFunction(this);
    } /* ... rest of class not shown */
}
class Variable implements Formula {
    public callFunction<R>(fn: FormulaFunction<R>): R {
        return fn.onVariable(this);
    } /* ... rest of class not shown */
}
class VariablesInFormula implements FormulaFunction<Set<string>> {
    public onVariable(variable: Variable): Set<string> {
        return new Set([variable.name]);
    } /* ... rest of class not shown */   
}

If we run f.callFunction(getVariables), its execution will unfold following the structure of the expression.

Hover or tap on each step to see corresponding highlights in the snapshot diagram and the code on the right.

What we have created with the FormulaFunction type and callFunction operation is a special kind of iterator, one that walks over the tree structure of a Formula and processes nodes in the tree one at a time. The name for this pattern is Visitor:

• A visitor implements switch over types: the code above to implement Variables­In­Formula reads pretty closely to our original goal of a switch statement, but each case is given its own onVariant method.

• A visitor represents a function over a recursive type: we can create an instance of a particular Formula­Function, pass it around, apply it as needed, etc. If the function we’re representing takes additional parameters, we can make them arguments to the constructor and store those values in fields to be referenced as we go. The exercise at the end of this section explores this idea.

• A visitor also acts like an iterator, walking over the tree structure of a Formula and applying a function to each node of the tree, in much the same way that iteration steps through a collection of elements like a list or set.

We’ll make a few changes to nomenclature to arrive at a final version of our Formula visitor:

• We’ll call it FormulaVisitor instead of FormulaFunction.
• Walking a visitor over an instance is called accepting it, so we’ll rename callFunction to accept.

Here is the code:

interface FormulaVisitor<R> {  // renamed from FormulaFunction<R>
    onVariable(variable: Variable): R;
    onNot(not: Not): R;
    onAnd(and: And): R;
    onOr(or: Or): R;
}

interface Formula {

    accept<R>(visitor: FormulaVisitor<R>): R; // renamed from callFunction()

    // ... other operations ...
}

class Variable implements Formula {
    // ...
    public accept<R>(visitor: FormulaVisitor<R>):R {
        return visitor.onVariable(this);
    }

}
class Not implements Formula {
    // ...
    public accept<R>(visitor: FormulaVisitor<R>):R {
        return visitor.onNot(this);
    }
}
class And implements Formula {
    // ...
    public accept<R>(visitor: FormulaVisitor<R>):R {
        return visitor.onAnd(this);
    }
}
class Or implements Formula {
    // ...
    public accept<R>(visitor: FormulaVisitor<R>):R {
        return visitor.onOr(this);
    }
}

class VariablesInFormula implements FormulaVisitor<Set<string>> {
    public onVariable(variable: Variable): Set<string> {
        return new Set([variable.name]);
    }
    public onNot(not: Not): Set<string> {
        return not.formula.accept(this);
    }
    public onAnd(and: And): Set<string> {
        return setUnion(and.left.accept(this), and.right.accept(this));
    }
    public onOr(or: Or): Set<string> {
        return setUnion(or.left.accept(this), or.right.accept(this));
    }
}

Calling it with:

const f: Formula = ...;
const variables: Set<string> = f.accept(new VariablesInFormula);

class EvaluateVisitor implements FormulaVisitor<▶▶A◀◀> {

    public constructor(
        private readonly map: ▶▶B◀◀
    ) {
    }
    public onVariable(variable: Variable): ▶▶A◀◀ {
        return ▶▶C◀◀(variable.name) ?? assert.fail(variable.name+' undefined');
    }
    public onNot(not: Not): ▶▶A◀◀ {
        return ! not.formula.accept(this);
    }
    public onAnd(and: And): ▶▶A◀◀ {
        return and.left.accept(this) ▶▶D◀◀ and.right.accept(this);
    }
    public onOr(or: Or): ▶▶A◀◀ {
        return or.left.accept(this)  ▶▶E◀◀ or.right.accept(this);
    }
}

/**
 * @param formula
 * @param map must have a key for every variable in formula
 * @returns the value of the formula with variables substituted with their values in the map
 */
function evaluate(formula: Formula, map: Map<string,boolean>): boolean {
    return ▶▶F◀◀.accept(new EvaluateVisitor(▶▶G◀◀));
}

function evaluate(formula: Formula, map: Map<string,boolean>): boolean {
    return formula.accept({
        onVariable(variable: Variable) { return map.get(variable.name); },
        onNot(not: Not) { ▶▶A◀◀ },
        onAnd(and: And) { return evaluate(and.left, map)  &&  evaluate(and.right, map); },
        onOr(or: Or)    { return evaluate(or.left,  map)  ||  evaluate(or.right,  map); },
    });
}

To understand the contrast between the Visitor pattern and the Interpreter pattern, it helps to imagine all the code for all the operations of Formula as if it were written down in a table, with the variant classes across the top and the operations down the side. An entry in the table is the code that implements that operation for that variant. Here is part of the table (written compactly in mathematical notation rather than TypeScript):

Now we can compare the Interpreter pattern and the Visitor pattern for implementing functions over a recursive data type:

Interpreter

Code is grouped by column. Each variant has all the code for that variant, implementing all the operations.

Visitor

Code is grouped by row. All the code for an operation will reside in a visitor class, with code to handle all the variants.

The Interpreter pattern makes it easier to add new variants, because we don’t have to change any of our existing code: we just need to implement all the various operations as methods in the new variant class.

The Visitor pattern makes it easier to add new operations. Instead of having to modify both the interface and every variant class, we just need to create a new, e.g., FormulaVisitor implementation with all the code for our new operation. There is no change to existing classes or interfaces.

Therefore, if adding new operations is a change we want to be most ready for, we might choose to define a visitor interface and write our functions as visitors.

We will also use the Visitor pattern when we intend clients of our type to know and understand its underlying structure and implement their own operations — and we’ve already seen a common and important use case for this: parse trees! Looking at code we’ve written to transform a concrete syntax tree into an abstract syntax tree, notice a smelly pattern:

function makeAST(parseTree: ParseTree<IntegerGrammar>): IntegerExpression {
    switch (parseTree.name) {
    case IntegerGrammar.ROOT:
        // ... call makeAST recursively on child ...
    case IntegerGrammar.SUM:
        // ... iterate over children and create Plus expressions ...
    case IntegerGrammar.PRIMARY:
        // ... call makeAST recursively on child ...
    case IntegerGrammar.NUMBER:
        const n = parseInt(parseTree.text;
        return new Number(n);
    default:
        throw new Error("should never get here");
    }
}

There’s that default case throwing an exception again: we don’t have static checking to make sure we’ve covered all the variants. We’re also stuck talking about generic ParseTree nodes. If there are multiple concrete variants of ParseTree, we would need to use unsafe casting to call any helpful operations they define. ParserLib has the advantage of simplicity, but in a more complex parsing package, we are likely to find makeAST implemented with a visitor.

And what works for concrete syntax trees is often very helpful for abstract syntax trees, where the implementor offers AST clients a visitor interface to define their own operations by walking recursively over the tree.

The Visitor pattern overcomes a missing feature in many object-oriented languages, giving us a type-safe way to represent and implement functions over a recursive data type as self-contained modules.

If we expect to add new operations to our recursive ADT in the future, using visitor makes our code ready for change without sacrificing the safety from bugs provided by static checking.

If we are building a little language where the ADT is designed for the purpose of allowing clients to define their own operations on our type from outside our implementation classes, visitor makes this possible.