Evaluating Expressions

Bạn là người tạo ra tôi, nhưng tôi mới là chủ của bạn; Hãy tuân lệnh!

Mary Shelley, Frankenstein

Nếu bạn muốn tạo đúng không khí cho chương này, hãy thử hình dung một cơn giông bão — kiểu bão xoáy cuồng loạn thích hất tung cánh cửa sổ vào đúng cao trào của câu chuyện. Có thể thêm vài tia sét cho kịch tính. Trong chương này, interpreter của chúng ta sẽ hít một hơi, mở mắt ra, và bắt đầu execute code.

Có đủ mọi cách để một language implementation khiến máy tính làm theo những gì source code của người dùng yêu cầu. Nó có thể compile sang machine code, dịch sang một ngôn ngữ bậc cao khác, hoặc chuyển thành một định dạng bytecode để một virtual machine chạy. Nhưng với interpreter đầu tiên của chúng ta, ta sẽ chọn con đường đơn giản và ngắn nhất: execute trực tiếp syntax tree.

Hiện tại, parser của chúng ta chỉ hỗ trợ expression. Vậy nên, để “execute” code, ta sẽ evaluate một expression và tạo ra một giá trị. Với mỗi loại cú pháp expression mà ta có thể parse — literal, operator, v.v. — ta cần một đoạn code tương ứng biết cách evaluate cây đó và tạo ra kết quả. Điều này dẫn đến hai câu hỏi:

1. Chúng ta sẽ tạo ra những loại giá trị nào?

2. Chúng ta sẽ tổ chức các đoạn code đó ra sao?

Hãy giải quyết từng câu một…

7 . 1Representing Values

Trong Lox, value được tạo ra bởi literal, tính toán bởi expression, và lưu trữ trong variable. Người dùng nhìn thấy chúng như các object Lox, nhưng chúng được implement bằng ngôn ngữ nền mà interpreter của chúng ta viết bằng nó. Điều này có nghĩa là ta phải bắc cầu giữa thế giới dynamic typing của Lox và static typing của Java. Một variable trong Lox có thể lưu trữ giá trị của bất kỳ kiểu (Lox) nào, và thậm chí có thể lưu các giá trị thuộc các kiểu khác nhau ở những thời điểm khác nhau. Vậy ta sẽ dùng kiểu Java nào để biểu diễn điều đó?

Với một biến Java có static type như vậy, ta cũng cần có khả năng xác định kiểu giá trị mà nó đang giữ ở runtime. Khi interpreter execute toán tử +, nó cần biết liệu đang cộng hai số hay nối hai chuỗi. Có kiểu Java nào có thể chứa số, chuỗi, Boolean, và nhiều thứ khác không? Có kiểu nào cho ta biết kiểu runtime của nó không? Có chứ! Chính là java.lang.Object quen thuộc.

Ở những chỗ trong interpreter mà ta cần lưu một giá trị Lox, ta có thể dùng Object làm kiểu. Java có các phiên bản boxed của các kiểu nguyên thủy, tất cả đều là subclass của Object, nên ta có thể dùng chúng cho các kiểu built-in của Lox:

Với một giá trị có static type là Object, ta có thể xác định giá trị runtime của nó là số, chuỗi hay gì khác bằng cách dùng toán tử instanceof tích hợp của Java. Nói cách khác, chính representation object của JVM đã tiện lợi cung cấp cho ta mọi thứ cần để implement các kiểu built-in của Lox. Sau này, khi thêm các khái niệm function, class, và instance của Lox, ta sẽ phải làm thêm một chút, nhưng Object và các lớp boxed primitive là đủ cho các kiểu mà ta cần ngay bây giờ.

7 . 2Evaluating Expressions

Tiếp theo, ta cần những đoạn code để implement logic evaluate cho mỗi loại expression mà ta có thể parse. Ta có thể nhét code đó vào các class của syntax tree, kiểu như một method interpret(). Về bản chất, ta sẽ bảo mỗi node của syntax tree: “Tự interpret chính mình đi”. Đây chính là Interpreter design pattern của nhóm Gang of Four. Đây là một pattern hay, nhưng như tôi đã nói trước đó, nó sẽ trở nên lộn xộn nếu ta nhồi đủ loại logic vào các class của tree.

Thay vào đó, ta sẽ tái sử dụng Visitor pattern “ngầu” của mình. Trong chương trước, ta đã tạo class AstPrinter. Nó nhận vào một syntax tree và đệ quy duyệt qua nó, xây dựng một chuỗi và cuối cùng trả về chuỗi đó. Đó gần như chính xác là những gì một interpreter thực sự làm, chỉ khác là thay vì nối chuỗi, nó tính toán giá trị.

Bắt đầu với một class mới.

package com.craftinginterpreters.lox;

class Interpreter implements Expr.Visitor<Object> {
}

Class này khai báo rằng nó là một visitor. Kiểu trả về của các visit method sẽ là Object — lớp gốc mà ta dùng để tham chiếu đến một giá trị Lox trong code Java. Để thỏa mãn interface Visitor, ta cần định nghĩa các visit method cho từng class của expression tree mà parser của chúng ta tạo ra. Ta sẽ bắt đầu với cái đơn giản nhất…

7 . 2 . 1Evaluating literals

Các lá của một expression tree — những mảnh cú pháp nguyên tử mà tất cả các expression khác được cấu thành từ đó — chính là literal. Literal gần như đã là value rồi, nhưng sự phân biệt này rất quan trọng. Literal là một phần cú pháp tạo ra một value. Literal luôn xuất hiện đâu đó trong source code của người dùng. Rất nhiều value được tạo ra bởi quá trình tính toán và không hề tồn tại trực tiếp trong code. Những cái đó không phải literal. Literal thuộc về “lãnh địa” của parser. Value là một khái niệm của interpreter, thuộc về thế giới của runtime.

Vì vậy, cũng giống như khi ta chuyển một literal token thành một literal syntax tree node trong parser, bây giờ ta sẽ chuyển literal tree node đó thành một runtime value. Việc này hóa ra lại rất đơn giản.

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

Chúng ta đã tạo ra runtime value từ rất sớm, ngay trong lúc scanning và nhét nó vào token. Parser lấy value đó và đặt vào literal tree node, nên để evaluate một literal, ta chỉ việc lấy nó ra.

7 . 2 . 2Evaluating parentheses

Node đơn giản tiếp theo để evaluate là grouping — node mà bạn nhận được khi dùng dấu ngoặc đơn rõ ràng trong một expression.

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

Một node grouping có tham chiếu đến một node con bên trong, chứa expression nằm trong dấu ngoặc đơn. Để evaluate bản thân grouping expression, ta đệ quy evaluate subexpression đó và trả về kết quả.

Chúng ta dựa vào helper method này, vốn chỉ đơn giản gửi expression quay lại cho implementation visitor của interpreter:

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

7 . 2 . 3Evaluating unary expressions

Giống như grouping, unary expression có một subexpression duy nhất mà ta phải evaluate trước. Khác biệt là bản thân unary expression sẽ làm thêm một chút việc sau đó.

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

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

    // Unreachable.
    return null;
  }

Đầu tiên, ta evaluate operand expression. Sau đó, ta áp dụng unary operator lên kết quả đó. Có hai loại unary expression khác nhau, được xác định bởi loại của operator token.

Ví dụ ở đây là -, dùng để đảo dấu kết quả của subexpression. Subexpression này phải là một số. Vì trong Java ta không thể statically biết điều đó, nên ta cast nó trước khi thực hiện phép toán. Việc cast này diễn ra ở runtime khi - được evaluate. Đây chính là cốt lõi của việc một ngôn ngữ được gọi là dynamically typed.

Bạn bắt đầu thấy cách evaluation duyệt cây một cách đệ quy. Ta không thể evaluate bản thân unary operator cho đến khi evaluate xong operand subexpression. Điều đó có nghĩa interpreter của chúng ta đang thực hiện duyệt hậu tự (post-order traversal) — mỗi node evaluate các node con trước khi làm công việc của chính nó.

Unary operator còn lại là logical not.

    switch (expr.operator.type) {

      case BANG:
        return !isTruthy(right);

      case MINUS:

Phần implement rất đơn giản, nhưng “truthy” ở đây nghĩa là gì? Ta cần rẽ ngang một chút sang một trong những câu hỏi lớn của triết học phương Tây: Thế nào là sự thật?

7 . 2 . 4Truthiness and falsiness

OK, có thể chúng ta sẽ không thật sự bàn về câu hỏi muôn thuở này, nhưng ít nhất trong thế giới của Lox, ta cần quyết định điều gì xảy ra khi bạn dùng một thứ không phải true hoặc false trong một phép logic như ! hoặc bất kỳ chỗ nào cần Boolean.

Chúng ta có thể nói đó là lỗi vì không chấp nhận chuyển đổi ngầm, nhưng hầu hết các ngôn ngữ dynamically typed không khắc khổ đến vậy. Thay vào đó, chúng lấy toàn bộ tập hợp value của mọi kiểu và chia thành hai nhóm: một nhóm được định nghĩa là “true”, “truthful” hoặc (tôi thích nhất) “truthy”, và phần còn lại là “false” hoặc “falsey”. Cách chia này phần nào mang tính tùy ý và trở nên kỳ quặc trong một vài ngôn ngữ.

Lox theo quy tắc đơn giản của Ruby: false và nil là falsey, còn mọi thứ khác đều là truthy. Chúng ta implement điều đó như sau:

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

7 . 2 . 5Evaluating binary operators

Tiếp theo là expression tree class cuối cùng: binary operator. Có một vài toán tử loại này, và chúng ta sẽ bắt đầu với các toán tử số học.

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

Tôi nghĩ bạn có thể đoán được chuyện gì đang diễn ra ở đây. Khác biệt chính so với toán tử unary negation là chúng ta có hai toán hạng để evaluate.

Tôi đã bỏ qua một toán tử số học vì nó hơi đặc biệt.

    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:

Toán tử + cũng có thể được dùng để nối hai chuỗi. Để xử lý điều đó, ta không chỉ đơn giản giả định toán hạng thuộc một kiểu nhất định rồi cast chúng, mà ta kiểm tra kiểu một cách động và chọn phép toán phù hợp. Đây là lý do tại sao representation object của chúng ta cần hỗ trợ instanceof.

Tiếp theo là các toán tử so sánh.

    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:

Chúng về cơ bản giống với toán tử số học. Khác biệt duy nhất là trong khi toán tử số học tạo ra giá trị có kiểu giống với toán hạng (số hoặc chuỗi), thì toán tử so sánh luôn trả về Boolean.

Cặp toán tử cuối cùng là equality.

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

Không giống toán tử so sánh vốn yêu cầu toán hạng là số, toán tử equality hỗ trợ toán hạng thuộc bất kỳ kiểu nào, thậm chí là kiểu hỗn hợp. Bạn không thể hỏi Lox xem 3 có nhỏ hơn "three" hay không, nhưng bạn có thể hỏi nó có bằng nhau không.

Giống như truthiness, logic equality được tách ra thành một method riêng.

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

    return a.equals(b);
  }

Đây là một trong những chỗ mà chi tiết về cách chúng ta biểu diễn object Lox trong Java trở nên quan trọng. Chúng ta cần implement đúng khái niệm equality của Lox, vốn có thể khác với Java.

May mắn là hai bên khá giống nhau. Lox không thực hiện chuyển đổi ngầm trong equality và Java cũng vậy. Chúng ta chỉ cần xử lý đặc biệt nil/null để tránh NullPointerException khi gọi equals() trên null. Ngoài ra thì ổn. Method equals() của Java trên Boolean, Double và String có hành vi đúng như ta muốn cho Lox.

Và thế là xong! Đây là toàn bộ code chúng ta cần để interpret đúng một Lox expression hợp lệ. Nhưng còn một expression không hợp lệ thì sao? Đặc biệt là khi một subexpression evaluate ra object có kiểu sai so với phép toán đang được thực hiện?

7 . 3Runtime Errors

Tôi đã khá “liều” khi nhét các phép cast bất cứ khi nào một subexpression tạo ra một Object nhưng toán tử lại yêu cầu nó phải là số hoặc chuỗi. Những phép cast đó hoàn toàn có thể thất bại. Dù code của người dùng có sai, nếu chúng ta muốn tạo ra một ngôn ngữ dễ dùng, thì chúng ta có trách nhiệm xử lý lỗi đó một cách “êm đẹp”.

Đã đến lúc nói về runtime error. Ở các chương trước, tôi đã tốn khá nhiều giấy mực để nói về xử lý lỗi, nhưng tất cả đều là lỗi syntax hoặc static. Những lỗi đó được phát hiện và báo trước khi bất kỳ code nào được execute. Runtime error là những lỗi mà semantics của ngôn ngữ yêu cầu chúng ta phải phát hiện và báo trong khi chương trình đang chạy (đúng như tên gọi).

Hiện tại, nếu một toán hạng có kiểu sai so với phép toán đang thực hiện, phép cast của Java sẽ thất bại và JVM sẽ ném ra ClassCastException. Điều đó sẽ “tháo” toàn bộ stack và thoát ứng dụng, đồng thời “phun” một Java stack trace ra cho người dùng. Đây rõ ràng không phải điều chúng ta muốn. Việc Lox được implement bằng Java nên là một chi tiết ẩn với người dùng. Thay vào đó, ta muốn họ hiểu rằng một runtime error của Lox đã xảy ra, và nhận được thông báo lỗi liên quan đến ngôn ngữ của chúng ta và chương trình của họ.

Tuy nhiên, hành vi của Java cũng có một điểm tốt: nó dừng execute ngay khi lỗi xảy ra. Giả sử người dùng nhập một expression như:

2 * (3 / -"muffin")

Bạn không thể negate một muffin, nên ta cần báo runtime error tại expression - bên trong. Điều đó đồng nghĩa ta không thể evaluate expression / vì nó không có toán hạng phải hợp lệ. Tương tự với *. Vậy nên khi một runtime error xảy ra sâu bên trong một expression, ta cần thoát ra hoàn toàn.

Chúng ta có thể in ra runtime error rồi hủy tiến trình và thoát ứng dụng hoàn toàn. Cách này cũng có chút “drama” — kiểu như phiên bản interpreter của ngôn ngữ lập trình thực hiện một cú “mic drop”.

Nghe cũng hấp dẫn, nhưng có lẽ ta nên làm gì đó ít “tận thế” hơn. Một runtime error cần dừng việc evaluate expression, nhưng không nên “giết” luôn interpreter. Nếu người dùng đang chạy REPL và gõ nhầm một dòng code, họ vẫn nên tiếp tục phiên làm việc và nhập thêm code sau đó.

7 . 3 . 1Detecting runtime errors

Tree-walk interpreter của chúng ta evaluate các expression lồng nhau bằng cách gọi method đệ quy, và ta cần “tháo” ra khỏi tất cả các lời gọi đó. Ném một exception trong Java là một cách tốt để làm điều này. Tuy nhiên, thay vì dùng lỗi cast sẵn có của Java, ta sẽ định nghĩa một lỗi riêng cho Lox để xử lý theo cách mình muốn.

Trước khi cast, ta sẽ tự kiểm tra kiểu của object. Ví dụ, với unary -, ta thêm:

      case MINUS:

        checkNumberOperand(expr.operator, right);

        return -(double)right;

Code để kiểm tra toán hạng là:

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

Khi kiểm tra thất bại, nó sẽ ném ra một trong những lỗi này:

package com.craftinginterpreters.lox;

class RuntimeError extends RuntimeException {
  final Token token;

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

Không giống exception cast của Java, class của chúng ta sẽ lưu token xác định vị trí trong code người dùng nơi runtime error xảy ra. Giống như với static error, điều này giúp người dùng biết cần sửa code ở đâu.

Chúng ta cần kiểm tra tương tự cho các binary operator. Vì tôi đã hứa sẽ cho bạn thấy từng dòng code cần thiết để implement interpreter, nên tôi sẽ liệt kê hết.

Greater than:

      case GREATER:

        checkNumberOperands(expr.operator, left, right);

        return (double)left > (double)right;

Greater than or equal to:

      case GREATER_EQUAL:

        checkNumberOperands(expr.operator, left, right);

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

Less than:

      case LESS:

        checkNumberOperands(expr.operator, left, right);

        return (double)left < (double)right;

Less than or equal to:

      case LESS_EQUAL:

        checkNumberOperands(expr.operator, left, right);

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

Subtraction:

      case MINUS:

        checkNumberOperands(expr.operator, left, right);

        return (double)left - (double)right;

Division:

      case SLASH:

        checkNumberOperands(expr.operator, left, right);

        return (double)left / (double)right;

Multiplication:

      case STAR:

        checkNumberOperands(expr.operator, left, right);

        return (double)left * (double)right;

Tất cả những cái này đều dựa vào validator này, gần như giống hệt với cái dùng cho unary:

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

Toán tử cuối cùng còn lại, và lại là một ngoại lệ, chính là phép cộng. Vì + được overload cho cả số và chuỗi, nó đã có sẵn code để kiểm tra kiểu. Tất cả những gì ta cần làm là báo lỗi nếu không rơi vào một trong hai trường hợp hợp lệ đó.

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

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

      case SLASH:

Như vậy là ta đã phát hiện được runtime error sâu bên trong bộ evaluator. Lỗi đã được ném ra. Bước tiếp theo là viết code để bắt chúng. Để làm điều đó, ta cần kết nối class Interpreter vào class Lox chính, nơi điều khiển toàn bộ.

7 . 4Hooking Up the Interpreter

Các visit method chính là “ruột” của class Interpreter, nơi công việc thực sự diễn ra. Ta cần “bọc” một lớp bên ngoài để giao tiếp với phần còn lại của chương trình. Public API của Interpreter chỉ đơn giản là một method.

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

Method này nhận vào một syntax tree của một expression và evaluate nó. Nếu thành công, evaluate() trả về một object chứa giá trị kết quả. interpret() sẽ chuyển nó thành chuỗi và hiển thị cho người dùng. Để chuyển một Lox value thành chuỗi, ta dùng:

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

Đây là một trong những đoạn code giống như isTruthy(), đóng vai trò “bắc cầu” giữa cách người dùng nhìn thấy Lox object và cách chúng được biểu diễn nội bộ trong Java.

Cách làm khá đơn giản. Vì Lox được thiết kế để quen thuộc với những ai đến từ Java, nên các giá trị như Boolean trông giống hệt ở cả hai ngôn ngữ. Hai trường hợp đặc biệt là nil, mà ta biểu diễn bằng null của Java, và số.

Lox dùng số double-precision ngay cả cho giá trị nguyên. Trong trường hợp đó, chúng nên được in ra mà không có dấu thập phân. Vì Java có cả kiểu số thực và số nguyên, nó muốn bạn biết mình đang dùng loại nào. Nó thể hiện điều đó bằng cách thêm .0 vào các double có giá trị nguyên. Chúng ta không quan tâm đến điều đó, nên ta sẽ cắt phần đó đi.

7 . 4 . 1Reporting runtime errors

Nếu một runtime error bị ném ra khi evaluate expression, interpret() sẽ bắt nó. Điều này cho phép ta báo lỗi cho người dùng và tiếp tục chạy một cách êm đẹp. Tất cả code báo lỗi hiện tại của chúng ta nằm trong class Lox, nên ta sẽ đặt method này ở đó:

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

Chúng ta dùng token gắn với RuntimeError để cho người dùng biết dòng code nào đang được execute khi lỗi xảy ra. Tốt hơn nữa là đưa cho họ toàn bộ call stack để thấy họ đã đi đến đoạn code đó như thế nào. Nhưng hiện tại ta chưa có function call, nên cũng chưa cần lo.

Sau khi hiển thị lỗi, runtimeError() sẽ gán giá trị cho field này:

  static boolean hadError = false;

  static boolean hadRuntimeError = false;

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

Field này đóng một vai trò nhỏ nhưng quan trọng.

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

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

    if (hadRuntimeError) System.exit(70);

  }

Nếu người dùng đang chạy một script Lox từ file và xảy ra runtime error, ta sẽ đặt exit code khi tiến trình thoát để tiến trình gọi nó biết. Không phải ai cũng quan tâm đến “nghi thức” shell, nhưng chúng ta thì có.

7 . 4 . 2Running the interpreter

Giờ chúng ta đã có một interpreter, class Lox có thể bắt đầu sử dụng nó.

public class Lox {

  private static final Interpreter interpreter = new Interpreter();

  static boolean hadError = false;

Ta khai báo field này là static để các lần gọi run() liên tiếp trong một phiên REPL sẽ tái sử dụng cùng một interpreter. Điều này hiện tại chưa tạo ra khác biệt, nhưng sau này khi interpreter lưu trữ các biến global, chúng sẽ cần được giữ nguyên trong suốt phiên REPL.

Cuối cùng, ta xóa dòng code tạm thời từ chương trước — dòng in ra syntax tree — và thay bằng đoạn này:

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

    interpreter.interpret(expression);

  }

Giờ chúng ta đã có một pipeline ngôn ngữ hoàn chỉnh: scanning, parsing và execution. Chúc mừng, bạn đã có cho riêng mình một chiếc máy tính số học mini.

Như bạn thấy, interpreter hiện tại vẫn còn khá “xương xẩu”. Nhưng class Interpreter và Visitor pattern mà ta thiết lập hôm nay chính là bộ khung mà các chương sau sẽ “nhồi” thêm những phần thú vị — biến, hàm, v.v. Ngay lúc này, interpreter chưa làm được nhiều, nhưng nó đã “sống” rồi!

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