Jumping Back and Forth

Thứ tự mà tâm trí ta tưởng tượng ra giống như một tấm lưới, hoặc một cái thang, được dựng lên để đạt được điều gì đó. Nhưng sau đó, bạn phải vứt cái thang đi, vì bạn nhận ra rằng, dù nó từng hữu ích, nó cũng chẳng có ý nghĩa gì.

Umberto Eco, The Name of the Rose

Chúng ta đã mất kha khá thời gian để đi đến đây, nhưng cuối cùng cũng sẵn sàng thêm control flow vào virtual machine của mình. Trong tree-walk interpreter mà ta xây cho jlox, ta hiện thực control flow của Lox bằng chính control flow của Java. Để execute một câu lệnh if của Lox, ta dùng câu lệnh if của Java để chạy nhánh được chọn. Cách đó hoạt động, nhưng chưa thật sự thỏa mãn. Bằng “phép màu” nào mà JVM hay CPU gốc lại hiện thực được câu lệnh if? Giờ khi ta đã có bytecode VM của riêng mình để “mổ xẻ”, ta có thể trả lời câu hỏi đó.

Khi nói về “control flow”, ta đang nói đến điều gì? “Flow” ở đây là cách luồng execute di chuyển qua văn bản chương trình. Gần như thể có một con robot tí hon bên trong máy tính, lang thang qua code của ta, execute từng mảnh ở chỗ này chỗ kia. Flow là con đường mà robot đó đi, và bằng cách kiểm soát robot, ta quyết định những phần code nào nó sẽ chạy.

Trong jlox, “điểm tập trung” của robot — đoạn code hiện tại — được ngầm định dựa trên AST node nào đang được lưu trong các biến Java và ta đang ở giữa đoạn Java code nào. Trong clox, điều này tường minh hơn nhiều. Trường ip của VM lưu địa chỉ của bytecode instruction hiện tại. Giá trị của trường này chính xác là “ta đang ở đâu” trong chương trình.

Việc execute bình thường diễn ra bằng cách tăng ip. Nhưng ta có thể thay đổi biến này theo bất kỳ cách nào mình muốn. Để hiện thực control flow, tất cả những gì cần làm là thay đổi ip theo những cách thú vị hơn. Cấu trúc control flow đơn giản nhất là câu lệnh if không có else:

if (condition) print("condition was truthy");

VM sẽ evaluate bytecode của biểu thức điều kiện. Nếu kết quả là truthy, nó tiếp tục và execute câu lệnh print trong thân. Trường hợp thú vị là khi điều kiện là falsey. Khi đó, quá trình execute sẽ bỏ qua nhánh then và tiếp tục sang câu lệnh tiếp theo.

Để bỏ qua một đoạn code, ta chỉ cần đặt ip tới địa chỉ của bytecode instruction ngay sau đoạn code đó. Để có điều kiện bỏ qua một đoạn code, ta cần một instruction kiểm tra giá trị trên đỉnh stack. Nếu nó là falsey, instruction này sẽ cộng một offset nhất định vào ip để nhảy qua một loạt instruction. Ngược lại, nó không làm gì và để luồng execute tiếp tục sang instruction kế tiếp như bình thường.

Khi compile sang bytecode, cấu trúc block lồng nhau tường minh của code sẽ biến mất, chỉ còn lại một chuỗi instruction phẳng. Lox là một ngôn ngữ structured programming, nhưng bytecode của clox thì không. Một tập hợp “đúng” — hoặc “sai”, tùy cách nhìn — các bytecode instruction có thể nhảy vào giữa một block, hoặc từ scope này sang scope khác.

VM sẽ vui vẻ execute điều đó, ngay cả khi kết quả khiến stack rơi vào trạng thái không xác định hoặc không nhất quán. Vậy nên, dù bytecode là unstructured, ta sẽ đảm bảo compiler chỉ sinh ra code “sạch” duy trì cùng cấu trúc và mức lồng nhau như chính Lox.

Đây chính xác là cách CPU thật hoạt động. Dù ta lập trình chúng bằng ngôn ngữ cấp cao buộc phải có control flow có cấu trúc, compiler sẽ hạ chúng xuống thành các lệnh nhảy thô. Ở tầng thấp nhất, hóa ra goto là control flow “thật” duy nhất.

Dù sao thì, tôi không định triết lý quá nhiều. Điều quan trọng là: chỉ cần một conditional jump instruction, ta đã đủ để hiện thực câu lệnh if của Lox, miễn là nó không có else. Vậy hãy bắt đầu thôi.

23 . 1Câu lệnh If

Đến chương này thì bạn biết quy trình rồi. Bất kỳ tính năng mới nào cũng bắt đầu từ front end và đi qua toàn bộ pipeline. Một câu lệnh if là… một statement, nên ta sẽ gắn nó vào parser ở đó.

  if (match(TOKEN_PRINT)) {
    printStatement();

  } else if (match(TOKEN_IF)) {
    ifStatement();

  } else if (match(TOKEN_LEFT_BRACE)) {

Khi gặp từ khóa if, ta chuyển việc compile sang hàm này:

static void ifStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'if'.");
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after condition."); 

  int thenJump = emitJump(OP_JUMP_IF_FALSE);
  statement();

  patchJump(thenJump);
}

Đầu tiên, ta compile biểu thức điều kiện, được bao quanh bởi dấu ngoặc. Ở runtime, điều đó sẽ để lại giá trị điều kiện trên đỉnh stack. Ta sẽ dùng nó để quyết định có execute nhánh then hay bỏ qua.

Tiếp theo, ta phát sinh một instruction mới OP_JUMP_IF_FALSE. Nó có một toán hạng cho biết cần offset ip bao nhiêu — tức bỏ qua bao nhiêu byte code. Nếu điều kiện là falsey, nó sẽ điều chỉnh ip theo giá trị đó. Đại khái như thế này:

Nhưng ta gặp một vấn đề. Khi đang ghi toán hạng của instruction OP_JUMP_IF_FALSE, làm sao ta biết phải nhảy bao xa? Ta chưa compile nhánh then, nên chưa biết nó chứa bao nhiêu bytecode.

Để giải quyết, ta dùng một mẹo kinh điển gọi là backpatching. Ta phát sinh lệnh nhảy trước, với một toán hạng offset tạm thời. Ta ghi nhớ vị trí của instruction chưa hoàn thiện này. Tiếp đó, ta compile phần thân then. Khi xong, ta sẽ biết cần nhảy bao xa. Lúc đó, ta quay lại và thay thế offset tạm bằng giá trị thật, giờ đã có thể tính toán được. Giống như khâu một miếng vá vào tấm vải code đã compile sẵn vậy.

Chúng ta sẽ mã hóa mẹo này thành hai hàm helper.

static int emitJump(uint8_t instruction) {
  emitByte(instruction);
  emitByte(0xff);
  emitByte(0xff);
  return currentChunk()->count - 2;
}

Hàm đầu tiên phát sinh một bytecode instruction và ghi một toán hạng tạm thời (placeholder) cho jump offset. Ta truyền opcode vào như một tham số vì sau này sẽ có hai instruction khác nhau dùng chung helper này. Ta dùng hai byte cho toán hạng jump offset. Một offset 16-bit cho phép ta nhảy qua tối đa 65.535 byte code, con số này là quá đủ cho nhu cầu của ta.

Hàm này trả về vị trí (offset) của instruction vừa được phát sinh trong chunk. Sau khi compile xong nhánh then, ta lấy offset đó và truyền vào hàm sau:

static void patchJump(int offset) {
  // -2 to adjust for the bytecode for the jump offset itself.
  int jump = currentChunk()->count - offset - 2;

  if (jump > UINT16_MAX) {
    error("Too much code to jump over.");
  }

  currentChunk()->code[offset] = (jump >> 8) & 0xff;
  currentChunk()->code[offset + 1] = jump & 0xff;
}

Hàm này quay lại bytecode và thay toán hạng tại vị trí đã cho bằng giá trị jump offset đã tính toán. Ta gọi patchJump() ngay trước khi phát sinh instruction tiếp theo mà ta muốn lệnh nhảy trỏ tới, nên nó sẽ dùng số lượng bytecode hiện tại để xác định cần nhảy bao xa. Trong trường hợp câu lệnh if, điều đó nghĩa là ngay sau khi compile xong nhánh then và trước khi compile câu lệnh tiếp theo.

Vậy là xong phần compile time. Giờ hãy định nghĩa instruction mới.

  OP_PRINT,

  OP_JUMP_IF_FALSE,

  OP_RETURN,

Bên phía VM, ta hiện thực nó như sau:

        break;
      }

      case OP_JUMP_IF_FALSE: {
        uint16_t offset = READ_SHORT();
        if (isFalsey(peek(0))) vm.ip += offset;
        break;
      }

      case OP_RETURN: {

Đây là instruction đầu tiên ta thêm vào có toán hạng 16-bit. Để đọc nó từ chunk, ta dùng một macro mới.

#define READ_CONSTANT() (vm.chunk->constants.values[READ_BYTE()])

#define READ_SHORT() \
    (vm.ip += 2, (uint16_t)((vm.ip[-2] << 8) | vm.ip[-1]))

#define READ_STRING() AS_STRING(READ_CONSTANT())

Macro này lấy hai byte tiếp theo từ chunk và ghép chúng thành một số nguyên không dấu 16-bit. Như thường lệ, ta undef macro này khi dùng xong.

#undef READ_BYTE

#undef READ_SHORT

#undef READ_CONSTANT

Sau khi đọc offset, ta kiểm tra giá trị điều kiện trên đỉnh stack. Nếu nó là falsey, ta áp dụng jump offset này vào ip. Ngược lại, ta giữ nguyên ip và luồng execute sẽ tự động tiếp tục sang instruction kế tiếp sau lệnh nhảy.

Trong trường hợp điều kiện là falsey, ta không cần làm gì thêm. Ta đã điều chỉnh ip, nên khi vòng lặp dispatch instruction bên ngoài quay lại, nó sẽ tiếp tục execute tại instruction mới, bỏ qua toàn bộ code trong nhánh then.

Lưu ý rằng lệnh nhảy này không pop giá trị điều kiện khỏi stack. Vậy nên ta vẫn chưa hoàn toàn xong, vì điều này để lại một giá trị “lơ lửng” trên stack. Ta sẽ xử lý nó sớm thôi. Tạm bỏ qua điều đó, giờ ta đã có một câu lệnh if hoạt động trong Lox, chỉ với một instruction nhỏ hỗ trợ ở runtime trong VM.

23 . 1 . 1Mệnh đề Else

Một câu lệnh if mà không hỗ trợ mệnh đề else thì như Morticia Addams mà thiếu Gomez vậy. Thế nên, sau khi compile nhánh then, ta sẽ tìm từ khóa else. Nếu có, ta compile nhánh else.

  patchJump(thenJump);

  if (match(TOKEN_ELSE)) statement();

}

Khi điều kiện là falsey, ta sẽ nhảy qua nhánh then. Nếu có nhánh else, ip sẽ trỏ ngay vào đầu code của nó. Nhưng như vậy là chưa đủ. Đây là luồng dẫn đến vấn đề:

Nếu điều kiện là truthy, ta execute nhánh then như mong muốn. Nhưng sau đó, luồng execute lại chạy thẳng vào nhánh else. Ối! Khi điều kiện là true, sau khi chạy nhánh then, ta cần nhảy qua nhánh else. Như vậy, trong cả hai trường hợp, ta chỉ execute một nhánh duy nhất, như sau:

Để hiện thực điều đó, ta cần một lệnh nhảy khác từ cuối nhánh then.

  statement();

  int elseJump = emitJump(OP_JUMP);

  patchJump(thenJump);

Ta patch offset này sau khi kết thúc phần thân nhánh else.

  if (match(TOKEN_ELSE)) statement();

  patchJump(elseJump);

}

Sau khi execute nhánh then, lệnh này sẽ nhảy tới câu lệnh tiếp theo sau nhánh else. Khác với lệnh nhảy trước, lệnh này là vô điều kiện. Ta luôn thực hiện nó, nên cần một instruction khác thể hiện điều đó.

  OP_PRINT,

  OP_JUMP,

  OP_JUMP_IF_FALSE,

Ta interpret nó như sau:

        break;
      }

      case OP_JUMP: {
        uint16_t offset = READ_SHORT();
        vm.ip += offset;
        break;
      }

      case OP_JUMP_IF_FALSE: {

Không có gì bất ngờ ở đây — điểm khác biệt duy nhất là nó không kiểm tra điều kiện và luôn áp dụng offset.

Giờ ta đã có cả nhánh then và else hoạt động, vậy là gần xong. Phần cuối cùng là dọn dẹp giá trị điều kiện còn sót lại trên stack. Hãy nhớ, mỗi statement phải có stack effect bằng 0 — sau khi statement execute xong, chiều cao stack phải bằng lúc trước.

Ta có thể để instruction OP_JUMP_IF_FALSE tự pop điều kiện, nhưng sắp tới ta sẽ dùng lại instruction này cho các toán tử logic, nơi ta không muốn pop điều kiện. Thay vào đó, ta sẽ để compiler phát sinh một vài instruction OP_POP rõ ràng khi compile câu lệnh if. Ta cần đảm bảo mọi đường đi qua code sinh ra đều pop điều kiện.

Khi điều kiện là truthy, ta pop nó ngay trước code bên trong nhánh then.

  int thenJump = emitJump(OP_JUMP_IF_FALSE);

  emitByte(OP_POP);

  statement();

Ngược lại, ta pop nó ở đầu nhánh else.

  patchJump(thenJump);

  emitByte(OP_POP);

  if (match(TOKEN_ELSE)) statement();

Instruction nhỏ này cũng có nghĩa là mọi câu lệnh if đều có một nhánh else ngầm, ngay cả khi người dùng không viết mệnh đề else. Trong trường hợp họ bỏ qua, nhánh này chỉ đơn giản là loại bỏ giá trị điều kiện.

Luồng execute đầy đủ và đúng sẽ trông như sau:

Nếu bạn lần theo luồng execute, bạn sẽ thấy nó luôn chạy đúng một nhánh và đảm bảo giá trị điều kiện được pop trước. Việc còn lại chỉ là thêm một chút hỗ trợ cho disassembler.

      return simpleInstruction("OP_PRINT", offset);

    case OP_JUMP:
      return jumpInstruction("OP_JUMP", 1, chunk, offset);
    case OP_JUMP_IF_FALSE:
      return jumpInstruction("OP_JUMP_IF_FALSE", 1, chunk, offset);

    case OP_RETURN:

Hai instruction này có định dạng mới với toán hạng 16-bit, nên ta thêm một hàm tiện ích mới để disassemble chúng.

static int jumpInstruction(const char* name, int sign,
                           Chunk* chunk, int offset) {
  uint16_t jump = (uint16_t)(chunk->code[offset + 1] << 8);
  jump |= chunk->code[offset + 2];
  printf("%-16s %4d -> %d\n", name, offset,
         offset + 3 + sign * jump);
  return offset + 3;
}

Vậy là xong, ta đã hoàn thiện một cấu trúc control flow. Nếu đây là một bộ phim thập niên 80, nhạc montage sẽ vang lên và phần còn lại của cú pháp control flow sẽ tự lo liệu. Tiếc là thập niên 80 đã qua lâu rồi, nên ta sẽ phải tự mình cày tiếp.

23 . 2Toán tử logic

Chắc bạn còn nhớ từ jlox, các toán tử logic and và or không chỉ là một cặp toán tử nhị phân như + và -. Vì chúng short-circuit và có thể không evaluate toán hạng bên phải tùy vào giá trị của toán hạng bên trái, chúng hoạt động giống các biểu thức control flow hơn.

Về cơ bản, chúng là một biến thể nhỏ của câu lệnh if với mệnh đề else. Cách dễ nhất để giải thích là cho bạn xem luôn code của compiler và luồng control flow mà nó tạo ra trong bytecode. Bắt đầu với and, ta gắn nó vào bảng parse expression ở đây:

  [TOKEN_NUMBER]        = {number,   NULL,   PREC_NONE},

  [TOKEN_AND]           = {NULL,     and_,   PREC_AND},

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

Từ đó, việc xử lý được chuyển sang một hàm parser mới.

static void and_(bool canAssign) {
  int endJump = emitJump(OP_JUMP_IF_FALSE);

  emitByte(OP_POP);
  parsePrecedence(PREC_AND);

  patchJump(endJump);
}

Tại thời điểm hàm này được gọi, biểu thức phía bên trái đã được compile xong. Nghĩa là ở runtime, giá trị của nó sẽ nằm trên đỉnh stack. Nếu giá trị đó là falsey, ta biết toàn bộ and sẽ là false, nên ta bỏ qua toán hạng bên phải và giữ nguyên giá trị bên trái làm kết quả của cả biểu thức. Ngược lại, ta loại bỏ giá trị bên trái và evaluate toán hạng bên phải, giá trị này sẽ trở thành kết quả của toàn bộ biểu thức and.

Bốn dòng code kia làm đúng như vậy. Luồng execute trông như sau:

Giờ bạn thấy vì sao OP_JUMP_IF_FALSE giữ lại giá trị trên đỉnh stack. Khi toán hạng bên trái của and là falsey, giá trị đó vẫn ở lại để trở thành kết quả của cả biểu thức.

23 . 2 . 1Toán tử logic or

Toán tử or phức tạp hơn một chút. Đầu tiên, ta thêm nó vào bảng parse.

  [TOKEN_NIL]           = {literal,  NULL,   PREC_NONE},

  [TOKEN_OR]            = {NULL,     or_,    PREC_OR},

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

Khi parser gặp token or ở dạng infix, nó sẽ gọi hàm này:

static void or_(bool canAssign) {
  int elseJump = emitJump(OP_JUMP_IF_FALSE);
  int endJump = emitJump(OP_JUMP);

  patchJump(elseJump);
  emitByte(OP_POP);

  parsePrecedence(PREC_OR);
  patchJump(endJump);
}

Trong một biểu thức or, nếu toán hạng bên trái là truthy, ta sẽ bỏ qua toán hạng bên phải. Do đó, ta cần nhảy khi giá trị là truthy. Ta có thể thêm một instruction riêng, nhưng để minh họa rằng compiler có thể tự do ánh xạ ngữ nghĩa của ngôn ngữ sang bất kỳ chuỗi instruction nào nó muốn, tôi hiện thực nó bằng cách tận dụng các lệnh nhảy đã có.

Khi toán hạng bên trái là falsey, nó sẽ thực hiện một cú nhảy nhỏ qua câu lệnh tiếp theo. Câu lệnh đó là một lệnh nhảy vô điều kiện qua phần code của toán hạng bên phải. “Điệu nhảy” nhỏ này thực chất tạo ra một cú nhảy khi giá trị là truthy. Luồng execute trông như sau:

Thành thật mà nói, đây không phải cách tốt nhất để làm. Có nhiều instruction hơn để dispatch và nhiều overhead hơn. Không có lý do gì or lại chậm hơn and. Nhưng cũng khá thú vị khi thấy rằng ta có thể hiện thực cả hai toán tử mà không cần thêm instruction mới nào. Mong bạn bỏ qua sự “tự thưởng” này của tôi.

OK, đó là ba cấu trúc branching trong Lox. Ý tôi là, đây là những tính năng control flow chỉ nhảy tiến qua code. Các ngôn ngữ khác thường có dạng rẽ nhánh nhiều hướng như switch và có thể là biểu thức điều kiện như ?:, nhưng Lox thì giữ mọi thứ đơn giản.

23 . 3Câu lệnh While

Giờ ta đến với các câu lệnh lặp (looping), những câu lệnh nhảy lùi để code có thể được execute nhiều hơn một lần. Lox chỉ có hai cấu trúc vòng lặp: while và for. Vòng lặp while đơn giản hơn nhiều, nên ta sẽ bắt đầu với nó trước.

    ifStatement();

  } else if (match(TOKEN_WHILE)) {
    whileStatement();

  } else if (match(TOKEN_LEFT_BRACE)) {

Khi gặp token while, ta gọi:

static void whileStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'while'.");
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after condition.");

  int exitJump = emitJump(OP_JUMP_IF_FALSE);
  emitByte(OP_POP);
  statement();

  patchJump(exitJump);
  emitByte(OP_POP);
}

Phần lớn đoạn này giống với câu lệnh if — ta compile biểu thức điều kiện, được bao quanh bởi dấu ngoặc bắt buộc. Tiếp theo là một lệnh nhảy bỏ qua câu lệnh thân ngay sau đó nếu điều kiện là falsey.

Ta patch lệnh nhảy sau khi compile xong phần thân và đảm bảo pop giá trị điều kiện khỏi stack ở cả hai nhánh. Điểm khác biệt duy nhất so với câu lệnh if là vòng lặp. Nó trông như thế này:

  statement();

  emitLoop(loopStart);

  patchJump(exitJump);

Sau phần thân, ta gọi hàm này để phát sinh một lệnh “loop”. Lệnh này cần biết phải nhảy lùi bao xa. Khi nhảy tiến, ta phải phát sinh lệnh theo hai giai đoạn vì chưa biết sẽ nhảy bao xa cho đến khi phát sinh xong lệnh nhảy. Giờ ta không gặp vấn đề đó nữa. Ta đã compile xong điểm trong code mà ta muốn nhảy về — ngay trước biểu thức điều kiện.

Tất cả những gì cần làm là ghi lại vị trí đó khi compile.

static void whileStatement() {

  int loopStart = currentChunk()->count;

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'while'.");

Sau khi execute phần thân của vòng lặp while, ta nhảy ngược lại ngay trước điều kiện. Như vậy, ta sẽ đánh giá lại biểu thức điều kiện ở mỗi vòng lặp. Ta lưu số lượng instruction hiện tại của chunk vào loopStart để ghi nhận offset trong bytecode ngay trước biểu thức điều kiện sắp compile. Sau đó, ta truyền nó vào hàm helper này:

static void emitLoop(int loopStart) {
  emitByte(OP_LOOP);

  int offset = currentChunk()->count - loopStart + 2;
  if (offset > UINT16_MAX) error("Loop body too large.");

  emitByte((offset >> 8) & 0xff);
  emitByte(offset & 0xff);
}

Hàm này giống như sự kết hợp giữa emitJump() và patchJump(). Nó phát sinh một lệnh loop mới, nhảy lùi vô điều kiện theo một offset cho trước. Giống như các lệnh nhảy, sau đó là một toán hạng 16-bit. Ta tính offset từ instruction hiện tại đến điểm loopStart mà ta muốn nhảy về. Phần + 2 là để tính cả kích thước của chính toán hạng của lệnh OP_LOOP mà ta cũng cần nhảy qua.

Từ góc nhìn của VM, thực ra không có khác biệt ngữ nghĩa nào giữa OP_LOOP và OP_JUMP. Cả hai đều chỉ cộng một offset vào ip. Ta hoàn toàn có thể dùng một instruction duy nhất cho cả hai và cho nó một toán hạng offset có dấu. Nhưng tôi nghĩ sẽ dễ hơn nếu tránh việc thao tác bit phức tạp để tự đóng gói một số nguyên 16-bit có dấu vào hai byte, và vì ta còn dư opcode, nên tại sao không dùng luôn?

Lệnh mới được định nghĩa ở đây:

  OP_JUMP_IF_FALSE,

  OP_LOOP,

  OP_RETURN,

Và trong VM, ta hiện thực nó như sau:

      }

      case OP_LOOP: {
        uint16_t offset = READ_SHORT();
        vm.ip -= offset;
        break;
      }

      case OP_RETURN: {

Điểm khác biệt duy nhất so với OP_JUMP là phép trừ thay vì phép cộng. Phần disassembly cũng tương tự.

      return jumpInstruction("OP_JUMP_IF_FALSE", 1, chunk, offset);

    case OP_LOOP:
      return jumpInstruction("OP_LOOP", -1, chunk, offset);

    case OP_RETURN:

Vậy là ta đã có câu lệnh while. Nó gồm hai lệnh nhảy — một lệnh nhảy tiến có điều kiện để thoát vòng lặp khi điều kiện không thỏa mãn, và một lệnh nhảy lùi vô điều kiện sau khi execute phần thân. Luồng execute trông như sau:

23 . 4Câu lệnh For

Câu lệnh lặp còn lại trong Lox là vòng lặp for quen thuộc, được kế thừa từ C. So với vòng lặp while, nó phức tạp hơn nhiều. Nó có ba mệnh đề, tất cả đều là tùy chọn:

• Phần khởi tạo (initializer) có thể là khai báo biến hoặc một biểu thức. Nó chạy một lần ở đầu câu lệnh.
• Mệnh đề điều kiện là một biểu thức. Giống như trong vòng lặp while, ta thoát vòng lặp khi nó evaluate ra giá trị falsey.
• Biểu thức tăng (increment) chạy một lần ở cuối mỗi vòng lặp.

Trong jlox, parser sẽ “desugar” vòng lặp for thành một AST tổng hợp cho vòng lặp while với một số phần bổ sung ở trước và cuối thân vòng lặp. Ở đây, ta sẽ làm điều tương tự, nhưng sẽ không đi qua bước tạo AST. Thay vào đó, bytecode compiler sẽ tận dụng các lệnh nhảy (jump) và vòng lặp (loop) mà ta đã có sẵn.

Ta sẽ triển khai từng phần một, bắt đầu với từ khóa for.

    printStatement();

  } else if (match(TOKEN_FOR)) {
    forStatement();

  } else if (match(TOKEN_IF)) {

Hàm này gọi một helper function. Nếu ta chỉ hỗ trợ vòng lặp for với các mệnh đề rỗng như for (;;), thì có thể hiện thực nó như sau:

static void forStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");
  consume(TOKEN_SEMICOLON, "Expect ';'.");

  int loopStart = currentChunk()->count;
  consume(TOKEN_SEMICOLON, "Expect ';'.");
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

  statement();
  emitLoop(loopStart);
}

Phần đầu sẽ có một loạt dấu câu bắt buộc. Sau đó ta compile phần thân. Giống như với vòng lặp while, ta ghi lại bytecode offset ở đầu thân vòng lặp và phát sinh một lệnh loop để nhảy về điểm đó sau khi chạy xong. Giờ ta đã có một bản hiện thực hoạt động của vòng lặp vô hạn.

23 . 4 . 1Mệnh đề khởi tạo (Initializer clause)

Giờ ta sẽ thêm mệnh đề đầu tiên — initializer. Nó chỉ chạy một lần, trước phần thân, nên compile khá đơn giản.

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");

  if (match(TOKEN_SEMICOLON)) {
    // No initializer.
  } else if (match(TOKEN_VAR)) {
    varDeclaration();
  } else {
    expressionStatement();
  }

  int loopStart = currentChunk()->count;

Cú pháp hơi phức tạp vì ta cho phép hoặc là khai báo biến, hoặc là một biểu thức. Ta dựa vào sự xuất hiện của từ khóa var để phân biệt. Với trường hợp biểu thức, ta gọi expressionStatement() thay vì expression(). Hàm này sẽ tìm dấu chấm phẩy (semicolon) — thứ ta cũng cần ở đây — và đồng thời phát sinh một lệnh OP_POP để loại bỏ giá trị. Ta không muốn initializer để lại bất cứ thứ gì trên stack.

Nếu một câu lệnh for khai báo biến, biến đó phải được giới hạn phạm vi trong thân vòng lặp. Ta đảm bảo điều này bằng cách bao toàn bộ câu lệnh trong một scope.

static void forStatement() {

  beginScope();

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");

Rồi đóng scope đó ở cuối.

  emitLoop(loopStart);

  endScope();

}

23 . 4 . 2Mệnh đề điều kiện (Condition clause)

Tiếp theo là biểu thức điều kiện, dùng để thoát vòng lặp.

  int loopStart = currentChunk()->count;

  int exitJump = -1;
  if (!match(TOKEN_SEMICOLON)) {
    expression();
    consume(TOKEN_SEMICOLON, "Expect ';' after loop condition.");

    // Jump out of the loop if the condition is false.
    exitJump = emitJump(OP_JUMP_IF_FALSE);
    emitByte(OP_POP); // Condition.
  }

  consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

Vì mệnh đề này là tùy chọn, ta cần kiểm tra xem nó có thực sự tồn tại không. Nếu bị bỏ qua, token tiếp theo chắc chắn phải là dấu chấm phẩy, nên ta dựa vào đó để nhận biết. Nếu không có dấu chấm phẩy, tức là có biểu thức điều kiện.

Trong trường hợp đó, ta compile nó. Sau đó, giống như với while, ta phát sinh một lệnh nhảy có điều kiện để thoát vòng lặp nếu điều kiện là falsey. Vì lệnh nhảy này giữ lại giá trị trên stack, ta pop nó trước khi execute phần thân. Điều này đảm bảo ta loại bỏ giá trị khi điều kiện là true.

Sau phần thân vòng lặp, ta cần patch lệnh nhảy đó.

  emitLoop(loopStart);

  if (exitJump != -1) {
    patchJump(exitJump);
    emitByte(OP_POP); // Condition.
  }

  endScope();
}

Ta chỉ làm điều này khi có mệnh đề điều kiện. Nếu không có, sẽ không có lệnh nhảy nào để patch và cũng không có giá trị điều kiện nào trên stack để pop.

23 . 4 . 3Mệnh đề tăng (Increment clause)

Tôi để phần thú vị nhất lại cuối cùng — mệnh đề increment. Nó khá rắc rối. Trong code, nó xuất hiện trước phần thân, nhưng lại execute sau phần thân. Nếu ta parse thành AST và sinh code trong một pass riêng, ta có thể đơn giản duyệt vào và compile field body của AST for trước khi compile mệnh đề increment.

Tiếc là, ta không thể compile mệnh đề increment sau, vì compiler của ta chỉ duyệt code một lần. Thay vào đó, ta sẽ nhảy qua phần increment, chạy phần thân, nhảy ngược lại lên increment, chạy nó, rồi mới sang vòng lặp tiếp theo.

Nghe hơi kỳ, nhưng này, vẫn còn hơn là phải tự quản lý AST trong bộ nhớ bằng C, đúng không? Đây là code:

  }

  if (!match(TOKEN_RIGHT_PAREN)) {
    int bodyJump = emitJump(OP_JUMP);
    int incrementStart = currentChunk()->count;
    expression();
    emitByte(OP_POP);
    consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

    emitLoop(loopStart);
    loopStart = incrementStart;
    patchJump(bodyJump);
  }

  statement();

Một lần nữa, đây là mệnh đề tùy chọn. Vì đây là mệnh đề cuối, nếu bị bỏ qua, token tiếp theo sẽ là dấu ngoặc đóng. Khi có increment, ta cần compile nó ngay bây giờ, nhưng chưa được execute. Vậy nên, trước tiên, ta phát sinh một lệnh nhảy vô điều kiện để bỏ qua code của mệnh đề increment và tới phần thân vòng lặp.

Tiếp theo, ta compile chính biểu thức increment. Thường thì đây là một phép gán. Dù là gì, ta chỉ chạy nó vì tác dụng phụ, nên cũng phát sinh một lệnh pop để loại bỏ giá trị của nó.

Phần cuối hơi tinh vi một chút. Đầu tiên, ta phát sinh một lệnh loop. Đây là vòng lặp chính đưa ta trở lại đầu vòng for — ngay trước biểu thức điều kiện nếu có. Lệnh loop này xảy ra ngay sau increment, vì increment chạy ở cuối mỗi vòng lặp.

Sau đó, ta thay đổi loopStart để trỏ tới offset nơi bắt đầu biểu thức increment. Sau này, khi ta phát sinh lệnh loop sau câu lệnh thân, nó sẽ nhảy lên biểu thức increment thay vì nhảy về đầu vòng lặp như khi không có increment. Đây là cách ta “đan” increment vào để nó chạy sau phần thân.

Nghe có vẻ rối, nhưng mọi thứ đều ổn. Một vòng lặp đầy đủ với tất cả các mệnh đề sẽ compile thành luồng execute như sau:

Giống như khi hiện thực vòng lặp for trong jlox, ta không cần đụng gì đến runtime. Tất cả đều được compile xuống các thao tác control flow nguyên thủy mà VM đã hỗ trợ sẵn. Trong chương này, ta đã tiến một bước nhảy vọt lớn — clox giờ đã Turing complete. Ta cũng đã bao quát khá nhiều cú pháp mới: ba câu lệnh và hai dạng biểu thức. Vậy mà chỉ cần thêm ba instruction đơn giản. Tỉ lệ công sức/hiệu quả này là khá ấn tượng đối với kiến trúc của VM.

// Kiểm tra xem ma trận có chứa số 0 không.
bool found = false;
for (int x = 0; x < xSize; x++) {
  for (int y = 0; y < ySize; y++) {
    for (int z = 0; z < zSize; z++) {
      if (matrix[x][y][z] == 0) {
        printf("found");
        found = true;
        break;
      }
    }
    if (found) break;
  }
  if (found) break;
}

for (int x = 0; x < xSize; x++) {
  for (int y = 0; y < ySize; y++) {
    for (int z = 0; z < zSize; z++) {
      if (matrix[x][y][z] == 0) {
        printf("found");
        goto done;
      }
    }
  }
}
done: