運算式求值

你是我的創造者，但我才是你的主人；服從我！

瑪麗·雪萊，《科學怪人》

如果你想為本章節適當地營造氣氛，試著召喚一場雷暴，那種喜歡在故事高潮時猛然打開百葉窗的旋風暴雨。也許可以再加入幾道閃電。在本章中，我們的直譯器將會吸氣、睜開眼睛，並執行一些程式碼。

語言實作有很多方式讓電腦執行使用者原始碼的指令。它們可以將其編譯為機器碼、將其翻譯成另一種高階語言，或是將其簡化為某種位元碼格式供虛擬機器執行。然而，對於我們的第一個直譯器，我們將採取最簡單、最短的路徑，直接執行語法樹本身。

目前，我們的解析器僅支援運算式。因此，為了「執行」程式碼，我們將對運算式求值並產生一個值。對於我們可以解析的每一種運算式語法—字面值、運算子等等—我們需要一組對應的程式碼片段，知道如何評估該樹並產生結果。這引發了兩個問題

1. 我們產生哪些種類的值？

2. 我們如何組織這些程式碼片段？

一次解決一個問題 . . . 

7 . 1表示值

在 Lox 中，值是由字面值建立、由運算式計算，並儲存在變數中。使用者將這些視為 Lox 物件，但它們是以我們的直譯器所使用的底層語言實作的。這意味著要橋接 Lox 動態型別和 Java 靜態型別的世界。Lox 中的變數可以儲存任何（Lox）型別的值，甚至可以在不同時間點儲存不同型別的值。我們可以使用哪種 Java 型別來表示它？

給定一個具有該靜態型別的 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> {
}

該類別宣告它是個訪問者。visit 方法的傳回型別將為 Object，即我們在 Java 程式碼中用來指稱 Lox 值的根類別。為了滿足訪問者介面，我們需要為解析器產生的四個運算式樹類別中的每一個定義 visit 方法。我們從最簡單的開始 . . . 

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」或「真」，或（我最喜歡的）「真值」，其餘為「false」或「假值」。這種劃分在某些程度上是任意的，並且在一些語言中變得奇怪。

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);
  }

這是我們以 Java 來表示 Lox 物件的細節所在。我們需要正確實現 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() 會傳回結果值的物件。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 既有浮點數型別又有整數型別，它希望你知道你正在使用的是哪一種。它會透過在整數值的雙精度值中加入明確的 .0 來告訴你。我們不在乎那個，所以我們將其從結尾駭掉。

7.4.1報告執行階段錯誤

如果在評估運算式時拋出執行階段錯誤，interpret() 會捕獲它。這讓我們可以向使用者報告錯誤，然後優雅地繼續。我們現有的所有錯誤報告程式碼都存在於 Lox 類別中，所以我們也將這個方法放在那裡

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

我們使用與 Runtime Error 相關聯的 token 來告訴使用者，當錯誤發生時，程式碼執行到哪一行。更好的是，我們可以提供使用者完整的呼叫堆疊，來顯示他們是如何到達執行該程式碼的。但是我們還沒有函式呼叫，所以我想我們還不用擔心這個。

在顯示錯誤之後，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!";