超類別

你可以選擇朋友，但你無法選擇家人，而且無論你是否承認，他們仍然是你的親人，當你不承認時，你看起来就很愚蠢。

哈波·李，《梅岡城故事》

這是我們向虛擬機器添加新功能的最後一章。我們幾乎已經將整個 Lox 語言都塞進去了。剩下的只有繼承方法和呼叫超類別方法。之後我們還有另一章，但它不會引入任何新行為。它只會讓現有的東西更快。 完成這一章，你將擁有一個完整的 Lox 實作。

本章中的某些內容會讓你想起 jlox。 我們解析 super 呼叫的方式幾乎相同，儘管是透過 clox 更複雜的機制將狀態儲存在堆疊上。 但這次我們有一種完全不同、更快的處理繼承方法呼叫的方式。

29 . 1繼承方法

我們將從方法繼承開始，因為它是比較簡單的部分。 為了喚起你的記憶，Lox 的繼承語法如下所示

class Doughnut {
  cook() {
    print "Dunk in the fryer.";
  }
}

class Cruller < Doughnut {
  finish() {
    print "Glaze with icing.";
  }
}

在這裡，Cruller 類別繼承自 Doughnut，因此，Cruller 的實例繼承了 cook() 方法。 我不知道我為什麼要強調這個。 你知道繼承是如何運作的。 讓我們開始編譯新的語法。

  currentClass = &classCompiler;

  if (match(TOKEN_LESS)) {
    consume(TOKEN_IDENTIFIER, "Expect superclass name.");
    variable(false);
    namedVariable(className, false);
    emitByte(OP_INHERIT);
  }

  namedVariable(className, false);

在我們編譯類別名稱後，如果下一個 token 是 <，則表示我們找到了超類別子句。 我們消耗超類別的識別符號 token，然後呼叫 variable()。 該函式採用先前消耗的 token，將其視為變數參考，並發出程式碼以載入變數的值。 換句話說，它會按名稱查找超類別並將其推入堆疊。

之後，我們呼叫 namedVariable() 將執行繼承的子類別載入堆疊，接著是 OP_INHERIT 指令。 該指令將超類別連接到新的子類別。 在上一章中，我們定義了 OP_METHOD 指令，透過將方法新增至其方法表來變更現有的類別物件。 這很類似—OP_INHERIT 指令採用現有的類別，並對其應用繼承的效果。

在之前的範例中，當編譯器處理這段語法時

class Cruller < Doughnut {

結果是這個位元組碼

在我們實作新的 OP_INHERIT 指令之前，我們需要偵測一個邊緣案例。

    variable(false);

    if (identifiersEqual(&className, &parser.previous)) {
      error("A class can't inherit from itself.");
    }

    namedVariable(className, false);

一個類別不能是它自己的超類別。 除非你可以接觸到一位精神錯亂的核物理學家和一輛經過大幅改造的 DeLorean，否則你不能從自己繼承。

29 . 1 . 1執行繼承

現在來看新的指令。

  OP_CLASS,

  OP_INHERIT,

  OP_METHOD

沒有要擔心的運算元。 我們需要的兩個值—超類別和子類別—都可以在堆疊上找到。 這表示反組譯很容易。

      return constantInstruction("OP_CLASS", chunk, offset);

    case OP_INHERIT:
      return simpleInstruction("OP_INHERIT", offset);

    case OP_METHOD:

解譯器是事情發生的地方。

        break;

      case OP_INHERIT: {
        Value superclass = peek(1);
        ObjClass* subclass = AS_CLASS(peek(0));
        tableAddAll(&AS_CLASS(superclass)->methods,
                    &subclass->methods);
        pop(); // Subclass.
        break;
      }

      case OP_METHOD:

從堆疊頂部向下，我們有子類別，然後是超類別。 我們抓取這兩者，然後進行繼承操作。 這是 clox 採取與 jlox 不同路徑的地方。 在我們的第一個解譯器中，每個子類別都儲存對其超類別的參考。 在方法存取時，如果我們在子類別的方法表中找不到該方法，我們會透過繼承鏈遞迴查看每個祖先的方法表，直到找到它為止。

例如，在 Cruller 的實例上呼叫 cook() 會讓 jlox 踏上這個旅程

這是在方法調用期間執行的許多工作。 它很慢，更糟的是，繼承方法在祖先鏈中越往上，速度就越慢。 這不是一個好的效能故事。

新方法快得多。 當宣告子類別時，我們會將所有繼承類別的方法複製到子類別自己的方法表中。 稍後，當呼叫方法時，任何從超類別繼承的方法都會在子類別自己的方法表中找到。 繼承完全不需要額外的執行階段工作。 在宣告類別時，工作就完成了。 這表示繼承方法呼叫與正常方法呼叫的速度完全一樣—單次雜湊表查找。

我偶爾會聽到這種技術被稱為「向下複製繼承」。 它簡單且快速，但與大多數最佳化一樣，你只能在某些限制下使用它。 它在 Lox 中有效，因為 Lox 類別是封閉的。 一旦類別宣告完成執行，該類別的方法集合就永遠不會變更。

在 Ruby、Python 和 JavaScript 等語言中，可以打開現有的類別，並在其中塞入一些新方法，甚至移除它們。 這會破壞我們的最佳化，因為如果這些修改發生在超類別之後子類別宣告執行，子類別將不會採用這些變更。 這會破壞使用者期望繼承始終反映超類別的目前狀態。

對我們來說幸運的是（但對喜歡此功能的使用者來說則不然，我想），Lox 不允許你修補猴子或打孔鴨子，因此我們可以安全地應用此最佳化。

那方法覆寫呢？ 將超類別的方法複製到子類別的方法表中，不會與子類別自己的方法衝突嗎？ 幸運的是，不會。 我們在建立子類別的 OP_CLASS 指令之後，但在編譯任何方法宣告和 OP_METHOD 指令之前，發出 OP_INHERIT。 在我們向下複製超類別的方法時，子類別的方法表為空。 子類別覆寫的任何方法都會覆寫表格中繼承的項目。

29 . 1 . 2無效的超類別

我們的實作簡單快速，這正是我喜歡虛擬機器程式碼的方式。 但它並不穩健。 沒有任何東西可以阻止使用者從根本不是類別的物件繼承

var NotClass = "So not a class";
class OhNo < NotClass {}

顯然，任何有自尊的程式設計師都不會這樣寫，但我們必須防範那些沒有自尊的潛在 Lox 使用者。 一個簡單的執行階段檢查可以解決這個問題。

        Value superclass = peek(1);

        if (!IS_CLASS(superclass)) {
          runtimeError("Superclass must be a class.");
          return INTERPRET_RUNTIME_ERROR;
        }

        ObjClass* subclass = AS_CLASS(peek(0));

如果我們從超類別子句中的識別符號載入的值不是 ObjClass，我們會報告一個執行階段錯誤，讓使用者知道我們對他們和他們的程式碼有什麼看法。

29 . 2儲存超類別

你有沒有注意到，當我們新增方法繼承時，我們實際上沒有從子類別新增對其超類別的任何參考？ 在我們複製繼承的方法後，我們會完全忘記超類別。 我們不需要掌握超類別，所以我們沒有。

這不足以支援 super 呼叫。 由於子類別可能覆寫超類別方法，我們需要能夠取得超類別方法表。 在我們開始使用該機制之前，我想喚起你對 super 呼叫如何靜態解析的記憶。

回到 jlox 的美好時光，我向你展示了這個棘手的範例來解釋 super 呼叫的調度方式

class A {
  method() {
    print "A method";
  }
}

class B < A {
  method() {
    print "B method";
  }

  test() {
    super.method();
  }
}

class C < B {}

C().test();

在 test() 方法的主體內，this 是 C 的實例。 如果 super 呼叫是相對於接收器的超類別來解析的，那麼我們會查看 C 的超類別 B。但是 super 呼叫是相對於發生 super 呼叫的周圍類別的超類別來解析的。 在這種情況下，我們在 B 的 test() 方法中，所以超類別是 A，程式應該列印「A method」。

這表示 super 呼叫不會根據執行階段實例動態解析。 用於查找方法的超類別是靜態的—實際上是詞彙—呼叫發生的位置的屬性。 當我們將繼承新增到 jlox 時，我們利用了這種靜態特性，將超類別儲存在與我們用於所有詞彙範圍的相同 Environment 結構中。 幾乎就像解譯器看到上面的程式這樣

class A {
  method() {
    print "A method";
  }
}

var Bs_super = A;
class B < A {
  method() {
    print "B method";
  }

  test() {
    runtimeSuperCall(Bs_super, "method");
  }
}

var Cs_super = B;
class C < B {}

C().test();

每個子類別都有一個隱藏變數，儲存對其超類別的參考。 每當我們需要執行 super 呼叫時，我們都會從該變數存取超類別，並告訴執行階段開始在那裡尋找方法。

我們會使用與 clox 相同的方法。 不同之處在於，我們使用位元組碼虛擬機器的值堆疊和 upvalue 系統，而不是 jlox 的堆積配置 Environment 類別。 機制有點不同，但整體效果是一樣的。

29 . 2 . 1超類別區域變數

我們的編譯器已經發出程式碼將超類別載入堆疊。 我們不是將該 slot 作為暫時的，而是建立一個新的範圍並使其成為區域變數。

    }

    beginScope();
    addLocal(syntheticToken("super"));
    defineVariable(0);

    namedVariable(className, false);
    emitByte(OP_INHERIT);

建立新的詞彙範圍可確保如果我們在同一範圍內宣告兩個類別，每個類別都有不同的區域 slot 來儲存其超類別。 因為我們總是將此變數命名為「super」，如果我們沒有為每個子類別建立範圍，變數就會發生衝突。

我們將變數命名為「super」的原因與我們使用「this」作為 this 表達式解析的隱藏區域變數的名稱相同：「super」是一個保留字，這保證了編譯器的隱藏變數不會與使用者定義的變數衝突。

差別在於，當編譯 this 表達式時，我們很方便地有一個詞法單元 (token) 在手邊，它的詞素 (lexeme) 是 "this"。但這裡我們就沒這麼幸運了。取而代之的是，我們加入一個小幫手函式，為給定的常數字串建立一個合成詞法單元。

static Token syntheticToken(const char* text) {
  Token token;
  token.start = text;
  token.length = (int)strlen(text);
  return token;
}

由於我們為父類別變數開啟了一個局部作用域，我們需要將它關閉。

  emitByte(OP_POP);

  if (classCompiler.hasSuperclass) {
    endScope();
  }

  currentClass = currentClass->enclosing;

在編譯完類別主體及其方法後，我們彈出作用域並捨棄 "super" 變數。這樣一來，該變數就可以在子類別的所有方法中存取。這是一個有點沒意義的優化，但我們只在有父類別子句的情況下才建立作用域。因此，我們只有在有父類別子句時才需要關閉作用域。

為了追蹤這一點，我們可以在 classDeclaration() 中宣告一個小型的區域變數。但很快地，編譯器中的其他函式也會需要知道周圍的類別是否為子類別。因此，我們不妨協助未來的自己，現在就將此事實儲存為 ClassCompiler 中的一個欄位。

typedef struct ClassCompiler {
  struct ClassCompiler* enclosing;

  bool hasSuperclass;

} ClassCompiler;

當我們第一次初始化 ClassCompiler 時，我們假設它不是子類別。

  ClassCompiler classCompiler;

  classCompiler.hasSuperclass = false;

  classCompiler.enclosing = currentClass;

然後，如果我們看到父類別子句，我們就知道我們正在編譯一個子類別。

    emitByte(OP_INHERIT);

    classCompiler.hasSuperclass = true;

  }

這個機制讓我們在執行期能夠從任何子類別的方法中存取周圍子類別的父類別物件—只需發出程式碼以載入名為 "super" 的變數即可。該變數是方法主體之外的局部變數，但我們現有的上層值 (upvalue) 支援使 VM 能夠捕獲該局部變數於方法主體內，甚至在巢狀於該方法內的函式中。

29 . 3父類別呼叫

有了這個執行期支援，我們準備好實作父類別呼叫了。一如既往，我們從頭到尾，從新的語法開始。父類別呼叫自然而然地以 super 關鍵字開頭。

  [TOKEN_RETURN]        = {NULL,     NULL,   PREC_NONE},

  [TOKEN_SUPER]         = {super_,   NULL,   PREC_NONE},

  [TOKEN_THIS]          = {this_,    NULL,   PREC_NONE},

當表達式剖析器遇到 super 詞法單元時，控制會跳到一個新的剖析函式，該函式會像這樣開始

static void super_(bool canAssign) {
  consume(TOKEN_DOT, "Expect '.' after 'super'.");
  consume(TOKEN_IDENTIFIER, "Expect superclass method name.");
  uint8_t name = identifierConstant(&parser.previous);
}

這與我們編譯 this 表達式的方式非常不同。與 this 不同，super 詞法單元不是一個獨立的表達式。取而代之的是，它後面的點和方法名稱是語法中不可分割的一部分。但是，括號中的引數列表是分開的。與正常的方法存取一樣，Lox 支援取得對父類別方法的引用作為閉包，而不調用它。

class A {
  method() {
    print "A";
  }
}

class B < A {
  method() {
    var closure = super.method;
    closure(); // Prints "A".
  }
}

換句話說，Lox 沒有真正的父類別呼叫表達式，它有父類別存取表達式，你可以選擇立即調用它們。因此，當編譯器遇到 super 詞法單元時，我們會消耗後續的 . 詞法單元，然後尋找方法名稱。方法是動態查找的，因此我們使用 identifierConstant() 來取得方法名稱詞法單元的詞素，並將其儲存在常數表中，就像我們對屬性存取表達式所做的那樣。

這是編譯器在消耗那些詞法單元後所做的事情

  uint8_t name = identifierConstant(&parser.previous);

  namedVariable(syntheticToken("this"), false);
  namedVariable(syntheticToken("super"), false);
  emitBytes(OP_GET_SUPER, name);

}

為了存取目前實例上的父類別方法，執行期需要接收者和周圍方法類別的父類別。第一個 namedVariable() 呼叫產生程式碼，以查找隱藏變數 "this" 中儲存的目前接收者，並將其推入堆疊。第二個 namedVariable() 呼叫發出程式碼，以從其 "super" 變數中查找父類別，並將其推到頂部。

最後，我們發出一個新的 OP_GET_SUPER 指令，其運算元 (operand) 是方法名稱的常數表索引。這需要記住很多東西。為了使其具體化，請考慮以下範例程式

class Doughnut {
  cook() {
    print "Dunk in the fryer.";
    this.finish("sprinkles");
  }

  finish(ingredient) {
    print "Finish with " + ingredient;
  }
}

class Cruller < Doughnut {
  finish(ingredient) {
    // No sprinkles, always icing.
    super.finish("icing");
  }
}

為 super.finish("icing") 表達式發出的位元組碼看起來和運作方式如下

前三個指令使執行期能夠存取它執行父類別存取所需的三個資訊片段

1. 第一個指令將實例載入到堆疊上。

2. 第二個指令載入解析方法的父類別。

3. 然後，新的 OP_GET_SUPER 指令將要存取的方法名稱編碼為運算元。

其餘指令是用於評估引數列表和呼叫函式的正常位元組碼。

我們幾乎準備好在直譯器中實作新的 OP_GET_SUPER 指令。但在我們執行此操作之前，編譯器有一些錯誤需要負責回報。

static void super_(bool canAssign) {

  if (currentClass == NULL) {
    error("Can't use 'super' outside of a class.");
  } else if (!currentClass->hasSuperclass) {
    error("Can't use 'super' in a class with no superclass.");
  }

  consume(TOKEN_DOT, "Expect '.' after 'super'.");

父類別呼叫僅在方法主體內（或在巢狀於方法內的函式中）才有意義，並且僅在具有父類別的類別的方法內才有效。我們使用 currentClass 的值來偵測這兩種情況。如果它是 NULL 或指向沒有父類別的類別，我們會報告這些錯誤。

29 . 3 . 1執行父類別存取

假設使用者沒有將 super 表達式放在不允許的位置，他們的程式碼會從編譯器傳遞到執行期。我們有了一個新的指令。

  OP_SET_PROPERTY,

  OP_GET_SUPER,

  OP_EQUAL,

我們像其他採用常數表索引運算碼的指令一樣反組譯它。

      return constantInstruction("OP_SET_PROPERTY", chunk, offset);

    case OP_GET_SUPER:
      return constantInstruction("OP_GET_SUPER", chunk, offset);

    case OP_EQUAL:

你可能會預期更難的東西，但解釋新指令類似於執行正常的屬性存取。

      }

      case OP_GET_SUPER: {
        ObjString* name = READ_STRING();
        ObjClass* superclass = AS_CLASS(pop());

        if (!bindMethod(superclass, name)) {
          return INTERPRET_RUNTIME_ERROR;
        }
        break;
      }

      case OP_EQUAL: {

與屬性一樣，我們從常數表中讀取方法名稱。然後，我們將其傳遞給 bindMethod()，該函式會在給定類別的方法表中查找方法，並建立一個 ObjBoundMethod 以將結果閉包捆綁到目前實例。

關鍵差異在於我們傳遞給 bindMethod() 的哪個類別。對於正常的屬性存取，我們使用 ObjInstance 自己的類別，這為我們提供了我們想要的動態分派。對於父類別呼叫，我們不使用實例的類別。相反，我們使用包含類別的靜態解析父類別，編譯器已方便地確保該父類別位於堆疊頂部等待我們。

我們彈出該父類別並將其傳遞給 bindMethod()，該函式會正確跳過該父類別與實例自身類別之間的任何子類別中的任何覆寫方法。它還正確包含父類別從其任何父類別繼承的任何方法。

其餘的行為是相同的。彈出父類別會將實例留在堆疊頂部。當 bindMethod() 成功時，它會彈出實例並推入新的繫結方法。否則，它會報告執行期錯誤並回傳 false。在這種情況下，我們中止直譯器。

29 . 3 . 2更快的父類別呼叫

我們現在可以運作父類別方法存取了。由於回傳的物件是一個 ObjBoundMethod，然後你可以調用它，我們也可以運作父類別呼叫了。就像上一章一樣，我們已經達到了一個 VM 具有完整且正確語義的地步。

但是，也像上一章一樣，它速度相當慢。同樣，我們正在為每個父類別呼叫配置堆積 ObjBoundMethod，即使大多數時候下一個指令是 OP_CALL，該指令會立即解包該繫結方法，調用它，然後捨棄它。事實上，對於父類別呼叫，這種情況甚至更可能發生，而不是一般的方法呼叫。至少對於方法呼叫，使用者有可能實際上是在調用儲存在欄位中的函式。對於父類別呼叫，你始終在查找方法。唯一的問題是你是否立即調用它。

如果編譯器在父類別方法名稱之後看到左括號，它當然可以自行回答這個問題，因此我們將繼續執行與我們對方法呼叫所做的相同的最佳化。取出載入父類別並發出 OP_GET_SUPER 的兩行程式碼，並將它們替換為此

  namedVariable(syntheticToken("this"), false);

  if (match(TOKEN_LEFT_PAREN)) {
    uint8_t argCount = argumentList();
    namedVariable(syntheticToken("super"), false);
    emitBytes(OP_SUPER_INVOKE, name);
    emitByte(argCount);
  } else {
    namedVariable(syntheticToken("super"), false);
    emitBytes(OP_GET_SUPER, name);
  }

}

現在，在我們發出任何東西之前，我們會尋找括號中的引數列表。如果我們找到一個，我們會編譯它。然後，我們載入父類別。之後，我們發出一個新的 OP_SUPER_INVOKE 指令。這個超級指令結合了 OP_GET_SUPER 和 OP_CALL 的行為，因此它採用兩個運算元：要查找的方法名稱的常數表索引以及要傳遞給它的引數數量。

否則，如果我們沒有找到 (，我們會繼續將表達式編譯為父類別存取，就像我們之前所做的那樣，並發出一個 OP_GET_SUPER。

沿著編譯管道向下移動，我們的第一站是一個新的指令。

  OP_INVOKE,

  OP_SUPER_INVOKE,

  OP_CLOSURE,

就在它過去，是它的反組譯器支援。

      return invokeInstruction("OP_INVOKE", chunk, offset);

    case OP_SUPER_INVOKE:
      return invokeInstruction("OP_SUPER_INVOKE", chunk, offset);

    case OP_CLOSURE: {

父類別調用指令具有與 OP_INVOKE 相同的運算元集，因此我們重用相同的輔助程式來反組譯它。最後，管道將我們傾倒到直譯器中。

        break;
      }

      case OP_SUPER_INVOKE: {
        ObjString* method = READ_STRING();
        int argCount = READ_BYTE();
        ObjClass* superclass = AS_CLASS(pop());
        if (!invokeFromClass(superclass, method, argCount)) {
          return INTERPRET_RUNTIME_ERROR;
        }
        frame = &vm.frames[vm.frameCount - 1];
        break;
      }

      case OP_CLOSURE: {

這少量的程式碼基本上是我們對 OP_INVOKE 的實作，並混合了一些 OP_GET_SUPER。但是，堆疊的組織方式存在一些差異。使用未最佳化的父類別呼叫，父類別會被彈出，並由已解析函式的 ObjBoundMethod 替換，然後再執行呼叫的引數。這確保在執行 OP_CALL 時，繫結方法位於引數列表下方，執行期預期閉包呼叫的該位置。

使用我們的最佳化指令，事情會稍微混亂

現在，解析父類別方法是調用的一部分，因此引數需要在我們查找方法時已經在堆疊上。這表示父類別物件位於引數的頂端。

除此之外，其行為大致上與先執行 OP_GET_SUPER 再執行 OP_CALL 相同。首先，我們取出方法名稱和參數計數運算元。然後，我們從堆疊頂端彈出父類別，以便在其方法表中查找方法。這樣做很方便地使堆疊設定正確，以進行方法呼叫。

我們將父類別、方法名稱和參數計數傳遞給現有的 invokeFromClass() 函數。該函數會在指定的類別上查找給定的方法，並嘗試使用給定的參數數量建立對該方法的呼叫。如果找不到方法，則返回 false，並且我們退出直譯器。否則，invokeFromClass() 會將新的 CallFrame 推送到方法閉包的呼叫堆疊上。這會使直譯器的快取 CallFrame 指標失效，因此我們需要更新 frame。

29 . 4一個完整的虛擬機器

回顧一下我們所創建的內容。根據我的計算，我們編寫了大約 2,500 行相當乾淨、直接的 C 程式碼。這個小程式包含了—相當高階的！—Lox 語言的完整實作，具有完整的運算子優先順序表和一套控制流程語句。我們實作了變數、函數、閉包、類別、欄位、方法和繼承。

更令人印象深刻的是，我們的實作可以移植到任何具有 C 編譯器的平台上，並且速度夠快，足以在真實世界的生產環境中使用。我們有一個單遍位元組碼編譯器、一個用於內部指令集的緊湊虛擬機器直譯器、緊湊的物件表示法、一個用於儲存變數而無需堆積分配的堆疊，以及一個精確的垃圾收集器。

如果您出去開始研究 Lua、Python 或 Ruby 的實作，您會驚訝地發現其中有多少內容現在對您來說很熟悉。您已經顯著提升了對程式語言運作方式的知識，這反過來讓您對程式設計本身有更深入的理解。這就像您以前是賽車手，現在您也可以打開引擎蓋並修理引擎一樣。

如果您願意，可以在這裡停止。您擁有的兩個 Lox 實作都是完整且功能齊全的。您已經製造了汽車，現在可以隨心所欲地駕駛它了。但是，如果您希望在賽道上進行更多調整和微調以獲得更高的性能，還有一個章節。我們不新增任何新功能，但我們會加入一些經典的優化，以進一步提升性能。如果聽起來很有趣，請繼續閱讀 . . .