Handling Constant TLA⁺ Expressions

This tutorial page covers the next three chapters in Crafting Interpreters:

1. Chapter 5: Representing Code
2. Chapter 6: Parsing Expressions
3. Chapter 7: Evaluating Expressions

Same as the book, we could build a parser for our entire minimal TLA⁺ language subset before moving on to interpreting it, but that would be boring! Instead we focus on a simple vertical slice of the language: expressions. And not just any expressions, constant expressions - expressions that do not contain variables or identifiers that we would have to resolve. Just primitive literal values stuck together, not too much more advanced than a simple calculator app. This will give us a skeleton on which to hang the rest of the language.

Each section in this tutorial corresponds to one or more sections of Crafting Interpreters (henceforth referred to as "the book"). First read the section of the book, then read the corresponding commentary & modifications given by this tutorial.

Chapter 5 focuses more on concepts than code, so this section will not have many TLA⁺-specific modifications. However, since this tutorial is intended to be self-contained code-wise, all necessary code is reproduced.

Everything before Section 5.1.3: A Grammar for Lox expressions applies equally to TLA⁺. The ambiguous first-draft grammar for Lox expressions can be adapted to TLA⁺:

expression     → literal
               | unary
               | binary
               | ternary
               | set
               | grouping ;

literal        → NUMBER | "TRUE" | "FALSE" ;
grouping       → "(" expression ")" ;
unary          → (( "ENABLED" | "-" ) expression ) | ( expression "'" ) ;
binary         → expression operator expression ;
ternary        → "IF" expression "THEN" expression "ELSE" expression;
set            → "{" ( expression ( "," expression )* )? "}"
operator       → "=" | "+" | "-" | ".." | "/\" | "\/" | "<"  | "\in" ;

There are a few interesting differences. The unary rule now captures both prefix and suffix operators, which both only accept a single parameter. The ternary rule matches the IF/THEN/ELSE operator, with the three parameters being the predicate, the true branch, and the false branch. There is also the set rule matching finite set literals like {1, 2, 3} or the empty set {}. The operators are changed to the set of operators defined in our TLA⁺ implementation. These are all the expressions we can use without introducing the concept of identifiers referring to something else.

While some programmers might have an aversion to generating code, the approach taken in the book is actually very convenient - as you will discover if you take some time to prototype & play around with different class representations of the parse tree! In Section 5.2.2: Metaprogramming the trees, the main differences in the GenerateAst class reflect our modification of the Lox grammar in the previous section:

package com.craftinginterpreters.tool;
 
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.List;
 
public class GenerateAst {
  public static void main(String[] args) throws IOException {
    if (args.length != 1) {
      System.err.println("Usage: generate_ast <output directory>");
      System.exit(64);
    }
    String outputDir = args[0];
    defineAst(outputDir, "Expr", Arrays.asList(
      "Binary   : Expr left, Token operator, Expr right",
      "Grouping : Expr expression",
      "Literal  : Object value",
      "Unary    : Token operator, Expr expr",
      "Ternary  : Token operator, Expr first, Expr second, Expr third",
      "Set      : List<Expr> elements"
    ));
  }
}

In the defineAst function, we only need to modify the output code so that it uses the package .tla instead of .lox; add this after the main method of GenerateAst:

  private static void defineAst(
      String outputDir, String baseName, List<String> types)
      throws IOException {
    String path = outputDir + "/" + baseName + ".java";
    PrintWriter writer = new PrintWriter(path, "UTF-8");
 
    writer.println("package com.craftinginterpreters.tla;");
    writer.println();
    writer.println("import java.util.List;");
    writer.println();
    writer.println("abstract class " + baseName + " {");
 
 
    // The AST classes.
    for (String type : types) {
      String className = type.split(":")[0].trim();
      String fields = type.split(":")[1].trim();
      defineType(writer, baseName, className, fields);
    }
    writer.println("}");
    writer.close();
  }

Finally, the defineType method - added after the defineAst method - is unchanged:

  private static void defineType(
      PrintWriter writer, String baseName,
      String className, String fieldList) {
    writer.println("  static class " + className + " extends " +
        baseName + " {");
 
    // Constructor.
    writer.println("    " + className + "(" + fieldList + ") {");
 
    // Store parameters in fields.
    String[] fields = fieldList.split(", ");
    for (String field : fields) {
      String name = field.split(" ")[1];
      writer.println("      this." + name + " = " + name + ";");
    }
 
    writer.println("    }");
 
    // Fields.
    writer.println();
    for (String field : fields) {
      writer.println("    final " + field + ";");
    }
 
    writer.println("  }");
  }

Section 5.3 introduces the Visitor pattern. No TLA⁺-specific differences are necessary when modifying GenerateAst to support it. Insert this line in defineAst():

    writer.println("abstract class " + baseName + " {");
 
    defineVisitor(writer, baseName, types);
 
    // The AST classes.

This calls the defineVisitor function which writes the visitor interface, defined as follows:

  private static void defineVisitor(
      PrintWriter writer, String baseName, List<String> types) {
    writer.println("  interface Visitor<R> {");
 
    for (String type : types) {
      String typeName = type.split(":")[0].trim();
      writer.println("    R visit" + typeName + baseName + "(" +
          typeName + " " + baseName.toLowerCase() + ");");
    }
 
    writer.println("  }");
  }

Again insert some lines in defineAst() to create the abstract accept method:

      defineType(writer, baseName, className, fields);
    }
 
    // The base accept() method.
    writer.println();
    writer.println("  abstract <R> R accept(Visitor<R> visitor);");
 
    writer.println("}");

Finally, insert some lines in defineType to add a types-specific accept method in each output class:

    writer.println("    }");
 
    // Visitor pattern.
    writer.println();
    writer.println("    @Override");
    writer.println("    <R> R accept(Visitor<R> visitor) {");
    writer.println("      return visitor.visit" +
        className + baseName + "(this);");
    writer.println("    }");
 
    // Fields.

Our generated syntax tree node types now support the visitor pattern!

Section 5.4 provides an implementation of a visitor called AstPrinter that prints out the parse tree. There are a few TLA⁺-specific modifications, starting of course with the package name:

package com.craftinginterpreters.tla;
 
class AstPrinter implements Expr.Visitor<String> {
  String print(Expr expr) {
    return expr.accept(this);
  }
}

We also have some modifications and additions to the visit methods of the AstPrinter class, again reflecting our modified TLA⁺-specific grammar:

  @Override
  public String visitBinaryExpr(Expr.Binary expr) {
    return parenthesize(expr.operator.lexeme,
                        expr.left, expr.right);
  }
 
  @Override
  public String visitGroupingExpr(Expr.Grouping expr) {
    return parenthesize("group", expr.expression);
  }
 
  @Override
  public String visitLiteralExpr(Expr.Literal expr) {
    if (expr.value == null) return "nil";
    return expr.value.toString();
  }
 
  @Override
  public String visitUnaryExpr(Expr.Unary expr) {
    return parenthesize(expr.operator.lexeme, expr.expr);
  }
 
  @Override
  public string visitTernaryExpr(Expr.Ternary expr) {
    return parenthesize(expr.operator.lexeme, expr.first,
                        expr.second, expr.third);
  }
 
  @Override
  public string visitSetExpr(Expr.Set expr) {
    return parenthesize("Set", expr.elements.toArray(Expr[]::new));
  }

The parenthesize method is unchanged from the book and should be inserted after the visit methods:

  private String parenthesize(String name, Expr... exprs) {
    StringBuilder builder = new StringBuilder();
 
    builder.append("(").append(name);
    for (Expr expr : exprs) {
      builder.append(" ");
      builder.append(expr.accept(this));
    }
    builder.append(")");
 
    return builder.toString();
  }

It isn't necessary to define a main method in the AstPrinter class, but if you'd like to try it out you are free to copy the one given in the book.