表达式求值

你是我的造物主，但我却是你的主人；服从！

玛丽·雪莱，《科学怪人》

如果你想为本章营造合适的氛围，试着召唤一场雷暴，那种在故事高潮时喜欢猛烈地拉开百叶窗的旋转风暴。也许还可以加上几道闪电。在本章中，我们的解释器将屏住呼吸，睁开眼睛，并执行一些代码。

语言实现让计算机执行用户源代码命令的方式多种多样。它们可以将其编译为机器码，将其翻译为另一种高级语言，或者将其简化为虚拟机运行的某种字节码格式。然而，对于我们的第一个解释器，我们将采用最简单、最短的路径，并直接执行语法树。

现在，我们的解析器只支持表达式。因此，为了“执行”代码，我们将评估表达式并生成一个值。对于我们可以解析的每种表达式语法—字面量、运算符等—我们需要相应的代码块，该代码块知道如何评估该树并生成结果。这引发了两个问题

1. 我们生成哪些类型的值？

2. 我们如何组织这些代码块？

让我们逐一解决 . . . 

7 . 1值的表示

在 Lox 中，值 由字面量创建，由表达式计算，并存储在变量中。用户将它们视为 Lox 对象，但它们是在解释器编写的底层语言中实现的。这意味着要连接 Lox 的动态类型和 Java 的静态类型。Lox 中的变量可以存储任何（Lox）类型的值，甚至可以在不同的时间点存储不同类型的值。我们可能会使用什么 Java 类型来表示它？

鉴于具有该静态类型的 Java 变量，我们还必须能够在运行时确定它保存的值类型。当解释器执行 + 运算符时，它需要确定是添加两个数字还是连接两个字符串。是否有一种 Java 类型可以容纳数字、字符串、布尔值等等？是否有一种类型可以告诉我们它的运行时类型？是的！就是久经考验的 java.lang.Object。

在解释器中需要存储 Lox 值的地方，我们可以使用 Object 作为类型。Java 有其基本类型的包装版本，它们都继承自 Object，因此我们可以将它们用于 Lox 的内置类型

给定一个静态类型为 Object 的值，我们可以使用 Java 的内置 instanceof 运算符确定运行时值是数字、字符串还是其他类型。换句话说，JVM 自身的对象表示方便地为我们提供了实现 Lox 内置类型所需的一切。当我们添加 Lox 的函数、类和实例的概念时，我们还需要做一些额外的工作，但 Object 和包装的基本类型类足以满足我们现在需要的类型。

7 . 2表达式求值

接下来，我们需要代码块来实现我们可以解析的每种表达式类型的求值逻辑。我们可以将这些代码塞进类似 interpret() 方法的语法树类中。实际上，我们可以告诉每个语法树节点，“自行解释”。这是四人帮的 解释器设计模式。这是一个很棒的模式，但就像我之前提到的，如果我们将各种逻辑塞进树类中，它会变得很乱。

相反，我们将重用我们很酷的 访问者模式。在上一章中，我们创建了一个 AstPrinter 类。它接收一个语法树并递归地遍历它，构建一个字符串，最终将其返回。这几乎与真正的解释器所做的事情完全相同，只是它不是连接字符串，而是计算值。

我们从一个新类开始。

package com.craftinginterpreters.lox;

class Interpreter implements Expr.Visitor<Object> {
}

该类声明它是一个访问者。访问方法的返回类型将是 Object，这是我们在 Java 代码中用来引用 Lox 值的根类。为了满足访问者接口，我们需要为解析器生成的四个表达式树类中的每一个定义访问方法。我们将从最简单的开始 . . . 

7 . 2 . 1求值字面量

表达式树的叶子—所有其他表达式都由这些语法原子组成—是 字面量。字面量几乎已经是值，但区分很重要。字面量是语法片段，它生成一个值。字面量始终出现在用户源代码中的某个地方。很多值是由计算生成的，并且在代码本身中不存在。那些不是字面量。字面量来自解析器的领域。值是解释器的概念，是运行时世界的组成部分。

因此，就像我们在解析器中将字面量标记转换为字面量语法树节点一样，现在我们将字面量树节点转换为运行时值。事实证明这很简单。

  @Override
  public Object visitLiteralExpr(Expr.Literal expr) {
    return expr.value;
  }

我们在扫描时就迫切地生成了运行时值，并将其塞入标记中。解析器获取该值并将其放入字面量树节点中，因此要评估字面量，我们只需将其取出来即可。

7 . 2 . 2求值括号

接下来最简单的节点要评估的是分组—通过在表达式中使用显式括号获得的节点。

  @Override
  public Object visitGroupingExpr(Expr.Grouping expr) {
    return evaluate(expr.expression);
  }

一个 分组 节点包含对包含在括号内的表达式的内部节点的引用。要评估分组表达式本身，我们递归地评估该子表达式并将其返回。

我们依赖此辅助方法，它只需将表达式发送回解释器的访问者实现中

  private Object evaluate(Expr expr) {
    return expr.accept(this);
  }

7 . 2 . 3求值一元表达式

与分组类似，一元表达式也有一个必须先评估的子表达式。不同之处在于一元表达式本身之后会做一些工作。

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

    switch (expr.operator.type) {
      case MINUS:
        return -(double)right;
    }

    // Unreachable.
    return null;
  }

首先，我们评估操作数表达式。然后，我们将一元运算符本身应用于该结果。有两个不同的表达式，由运算符标记的类型标识。

这里展示的是 -，它对子表达式的结果取反。子表达式必须是数字。由于我们在 Java 中静态地不知道这一点，因此我们在执行操作之前将其强制转换。这种类型转换发生在运行时，当 - 被评估时。这就是使语言动态类型的核心所在。

你开始看到求值如何递归地遍历树了。在我们评估其操作数子表达式之前，我们无法评估一元运算符本身。这意味着我们的解释器正在执行后序遍历—每个节点都在执行自身工作之前评估其子节点。

另一个一元运算符是逻辑非。

    switch (expr.operator.type) {

      case BANG:
        return !isTruthy(right);

      case MINUS:

实现很简单，但这个“真值”是什么意思？我们需要做一个小的旁路，去探索西方哲学的一个重要问题：什么是真理？

7 . 2 . 4真值和假值

好吧，也许我们不会真正深入讨论这个问题，但至少在 Lox 的世界里，我们需要确定当你使用除 true 或 false 以外的东西在逻辑运算中（如 ! 或任何其他需要布尔值的地方）时会发生什么。

我们可以简单地说这是一个错误，因为我们不接受隐式转换，但大多数动态类型语言没有那么禁欲。相反，它们获取所有类型的值的集合，并将它们划分为两个集合，其中一个集合被定义为“true”（真）、“truthful”（真实）或（我最喜欢）“truthy”（真值），而另一个集合则为“false”（假）、“falsey”（假值）。这种划分在某种程度上是任意的，在一些语言中会变得很奇怪。

Lox 遵循 Ruby 的简单规则：false 和 nil 是假值，其他所有东西都是真值。我们这样实现它

  private boolean isTruthy(Object object) {
    if (object == null) return false;
    if (object instanceof Boolean) return (boolean)object;
    return true;
  }

7 . 2 . 5求值二元运算符

现在开始处理最后一个表达式树类：二元运算符。其中有很多，我们将从算术运算符开始。

  @Override
  public Object visitBinaryExpr(Expr.Binary expr) {
    Object left = evaluate(expr.left);
    Object right = evaluate(expr.right); 

    switch (expr.operator.type) {
      case MINUS:
        return (double)left - (double)right;
      case SLASH:
        return (double)left / (double)right;
      case STAR:
        return (double)left * (double)right;
    }

    // Unreachable.
    return null;
  }

我认为你可以弄清楚这里发生了什么。与一元否定运算符的主要区别在于我们有两个操作数需要计算。

我遗漏了一个算术运算符，因为它有点特殊。

    switch (expr.operator.type) {
      case MINUS:
        return (double)left - (double)right;

      case PLUS:
        if (left instanceof Double && right instanceof Double) {
          return (double)left + (double)right;
        } 

        if (left instanceof String && right instanceof String) {
          return (String)left + (String)right;
        }

        break;

      case SLASH:

+ 运算符也可以用来连接两个字符串。为了处理这种情况，我们不只是假设操作数是特定类型并进行强制转换，而是动态地检查类型并选择相应的操作。这就是为什么我们需要我们的对象表示来支持 instanceof 的原因。

接下来是比较运算符。

    switch (expr.operator.type) {

      case GREATER:
        return (double)left > (double)right;
      case GREATER_EQUAL:
        return (double)left >= (double)right;
      case LESS:
        return (double)left < (double)right;
      case LESS_EQUAL:
        return (double)left <= (double)right;

      case MINUS:

它们基本上与算术运算符相同。唯一的区别是算术运算符生成的值类型与操作数相同（数字或字符串），而比较运算符总是生成一个布尔值。

最后一对运算符是相等运算符。

      case BANG_EQUAL: return !isEqual(left, right);
      case EQUAL_EQUAL: return isEqual(left, right);

与需要数字的比较运算符不同，相等运算符支持任何类型的操作数，甚至混合类型。你不能问 Lox 3 是否小于 "three"，但你可以问它是否等于它。

与真值一样，相等逻辑被提升到一个单独的方法中。

  private boolean isEqual(Object a, Object b) {
    if (a == null && b == null) return true;
    if (a == null) return false;

    return a.equals(b);
  }

这是 Lox 对象在 Java 中的表示方式细节之一。我们需要正确地实现 Lox 的相等概念，这可能与 Java 的不同。

幸运的是，两者非常相似。Lox 在相等中不执行隐式转换，Java 也不执行。我们必须对 nil/null 进行特殊处理，这样如果我们尝试对 null 调用 equals()，就不会抛出 NullPointerException。除此之外，我们就没事了。Java 的equals() 方法在 Boolean、Double 和 String 上具有我们对 Lox 想要的行为。

就是这样！这就是我们正确解释有效 Lox 表达式所需的所有代码。但无效表达式怎么办？特别地，当子表达式评估为与执行的操作不匹配类型的对象时会发生什么？

7 . 3运行时错误

我漫不经心地在子表达式生成 Object 并且运算符要求它是数字或字符串时塞入了强制转换。这些强制转换可能会失败。即使用户的代码有错误，如果我们想要制作一个可用的语言，我们有责任优雅地处理这些错误。

现在该谈谈运行时错误了。在前面的章节中，我花费了大量笔墨讨论错误处理，但那些都是语法或静态错误。这些错误在任何代码执行之前被检测到并报告。运行时错误是在程序运行时语言语义要求我们检测和报告的失败（因此得名）。

现在，如果操作数的类型不匹配正在执行的操作，Java 强制转换将失败，JVM 将抛出 ClassCastException。这会将整个堆栈展开并退出应用程序，将 Java 堆栈跟踪输出到用户。这可能不是我们想要的。Lox 是用 Java 实现的这一事实应该是一个对用户隐藏的细节。相反，我们希望他们理解发生了Lox 运行时错误，并向他们提供与我们的语言和程序相关的错误消息。

Java 行为确实有一点好处。当错误发生时，它会正确地停止执行任何代码。假设用户输入了一些类似于以下的表达式

2 * (3 / -"muffin")

你不能否定松饼，所以我们需要在内部的 - 表达式中报告运行时错误。这反过来意味着我们无法评估 / 表达式，因为它没有有意义的右操作数。* 也是如此。因此，当运行时错误发生在某个表达式深处时，我们需要一直逃逸出来。

我们可以打印运行时错误，然后中止进程并完全退出应用程序。这确实有一点戏剧性的风格。就像编程语言解释器版本的麦克风掉落。

虽然这很诱人，但我们应该做一些不那么灾难性的事情。虽然运行时错误需要停止评估表达式，但它不应该终止解释器。如果用户正在运行 REPL 并且在一行代码中存在错误，他们应该仍然能够继续会话并在之后输入更多代码。

7 . 3 . 1检测运行时错误

我们的树遍历解释器使用递归方法调用来评估嵌套表达式，我们需要从所有这些调用中展开。在 Java 中抛出异常是一种很好的方法。但是，我们不会使用 Java 自身的强制转换失败，而是定义一个特定于 Lox 的异常，以便我们可以按照我们想要的方式处理它。

在执行强制转换之前，我们自己检查对象的类型。因此，对于一元 -，我们添加了

      case MINUS:

        checkNumberOperand(expr.operator, right);

        return -(double)right;

检查操作数的代码是

  private void checkNumberOperand(Token operator, Object operand) {
    if (operand instanceof Double) return;
    throw new RuntimeError(operator, "Operand must be a number.");
  }

当检查失败时，它会抛出以下异常之一

package com.craftinginterpreters.lox;

class RuntimeError extends RuntimeException {
  final Token token;

  RuntimeError(Token token, String message) {
    super(message);
    this.token = token;
  }
}

与 Java 强制转换异常不同，我们的类跟踪标识用户代码中运行时错误来源的标记。与静态错误一样，这有助于用户知道在哪里修复他们的代码。

我们需要对二元运算符进行类似的检查。由于我答应你，实现解释器需要的每一行代码我都会介绍，所以我会将它们全部列出来。

大于

      case GREATER:

        checkNumberOperands(expr.operator, left, right);

        return (double)left > (double)right;

大于或等于

      case GREATER_EQUAL:

        checkNumberOperands(expr.operator, left, right);

        return (double)left >= (double)right;

小于

      case LESS:

        checkNumberOperands(expr.operator, left, right);

        return (double)left < (double)right;

小于或等于

      case LESS_EQUAL:

        checkNumberOperands(expr.operator, left, right);

        return (double)left <= (double)right;

减法

      case MINUS:

        checkNumberOperands(expr.operator, left, right);

        return (double)left - (double)right;

除法

      case SLASH:

        checkNumberOperands(expr.operator, left, right);

        return (double)left / (double)right;

乘法

      case STAR:

        checkNumberOperands(expr.operator, left, right);

        return (double)left * (double)right;

所有这些都依赖于这个验证器，它与一元验证器几乎相同

  private void checkNumberOperands(Token operator,
                                   Object left, Object right) {
    if (left instanceof Double && right instanceof Double) return;
    
    throw new RuntimeError(operator, "Operands must be numbers.");
  }

最后一个剩余的运算符，再次是那个与众不同的，是加法。由于 + 对数字和字符串进行了重载，因此它已经具有检查类型的代码。我们只需要在两个成功情况都不匹配的情况下才失败。

          return (String)left + (String)right;
        }

        throw new RuntimeError(expr.operator,
            "Operands must be two numbers or two strings.");

      case SLASH:

这让我们能够检测到评估器内部深处的运行时错误。错误正在被抛出。下一步是编写捕捉这些错误的代码。为此，我们需要将 Interpreter 类连接到驱动它的主 Lox 类中。

7 . 4连接解释器

visit 方法是 Interpreter 类的核心，是真正的工作发生的地方。我们需要在它们周围包裹一层外衣，以便与程序的其余部分进行交互。Interpreter 的公共 API 只是一个方法。

  void interpret(Expr expression) { 
    try {
      Object value = evaluate(expression);
      System.out.println(stringify(value));
    } catch (RuntimeError error) {
      Lox.runtimeError(error);
    }
  }

这接受表达式语法树并对其进行评估。如果成功，evaluate() 将返回结果值的 object。interpret() 将其转换为字符串并显示给用户。为了将 Lox 值转换为字符串，我们依赖于

  private String stringify(Object object) {
    if (object == null) return "nil";

    if (object instanceof Double) {
      String text = object.toString();
      if (text.endsWith(".0")) {
        text = text.substring(0, text.length() - 2);
      }
      return text;
    }

    return object.toString();
  }

这是像 isTruthy() 这样的代码片段之一，它跨越了用户对 Lox 对象的视图及其在 Java 中的内部表示之间的界限。

这很简单。由于 Lox 的设计是为了让来自 Java 的人熟悉，所以布尔值在两种语言中看起来都一样。两个边缘情况是 nil，我们使用 Java 的 null 来表示，以及数字。

Lox 即使对于整数值也使用双精度数。在这种情况下，它们应该在没有小数点的情况下打印。由于 Java 同时具有浮点数和整型类型，因此它希望你了解你在使用哪种类型。它通过在整数值 double 后添加显式的 .0 来告诉你。我们不关心这一点，所以我们从末尾删除它。

7 . 4 . 1报告运行时错误

如果在评估表达式时抛出了运行时错误，interpret() 会捕捉到它。这使我们能够向用户报告错误，然后优雅地继续。我们现有的所有错误报告代码都位于 Lox 类中，因此我们也把这个方法放在那里

  static void runtimeError(RuntimeError error) {
    System.err.println(error.getMessage() +
        "\n[line " + error.token.line + "]");
    hadRuntimeError = true;
  }

我们使用与 RuntimeError 关联的标记来告诉用户在错误发生时正在执行哪一行代码。更理想的情况是向用户提供完整的调用堆栈，以显示他们是如何到达执行该代码的。但我们还没有函数调用，所以我想我们不必担心它。

在显示错误之后，runtimeError() 设置了这个字段

  static boolean hadError = false;

  static boolean hadRuntimeError = false;

  public static void main(String[] args) throws IOException {

该字段扮演着微不足道但重要的角色。

    run(new String(bytes, Charset.defaultCharset()));

    // Indicate an error in the exit code.
    if (hadError) System.exit(65);

    if (hadRuntimeError) System.exit(70);

  }

如果用户正在运行一个 Lox来自文件的脚本，并且发生了运行时错误，我们会设置一个退出代码，以便在进程退出时通知调用进程。并非每个人都关心 shell 礼仪，但我们关心。

7 . 4 . 2运行解释器

现在我们有了解释器，Lox 类可以开始使用它了。

public class Lox {

  private static final Interpreter interpreter = new Interpreter();

  static boolean hadError = false;

我们将该字段设为静态的，这样在 REPL 会话中，对 run() 的连续调用将重用同一个解释器。这现在没有区别，但稍后解释器将存储全局变量时会有区别。这些变量应该在整个 REPL 会话中保持不变。

最后，我们从 上一章 中删除了用于打印语法树的临时代码行，并将其替换为：

    // Stop if there was a syntax error.
    if (hadError) return;

    interpreter.interpret(expression);

  }

现在我们有了完整的语言管道：扫描、解析和执行。恭喜你，你拥有了自己的算术计算器。

正如你所看到的，解释器非常简陋。但 Interpreter 类和我们今天设置的 Visitor 模式构成了一个框架，后面章节会填充它，使它充满有趣的内部机制—变量、函数等。目前，解释器没有做太多事情，但它已经活了！

Object[] stuff = new Integer[1];
stuff[0] = "not an int!";