Calls and Functions

Bất kỳ vấn đề nào trong khoa học máy tính cũng có thể được giải quyết bằng một tầng gián tiếp khác. Ngoại trừ vấn đề có quá nhiều tầng gián tiếp.

David Wheeler

Chương này đúng là một “con quái vật”. Tôi thường cố gắng chia nhỏ tính năng thành từng phần dễ nuốt, nhưng đôi khi bạn phải nuốt trọn cả bữa. Nhiệm vụ tiếp theo của chúng ta là functions. Ta có thể bắt đầu chỉ với khai báo function, nhưng điều đó chẳng hữu ích mấy khi bạn không thể gọi chúng. Ta có thể làm phần gọi hàm, nhưng lại chẳng có gì để gọi. Và tất cả phần hỗ trợ runtime trong VM để phục vụ cả hai thứ đó cũng chẳng đem lại nhiều giá trị nếu nó không kết nối với thứ gì bạn có thể thấy. Vậy nên, chúng ta sẽ làm tất cả. Khá nhiều việc, nhưng khi xong, bạn sẽ thấy rất đáng.

24 . 1Function Objects

Thay đổi cấu trúc thú vị nhất trong VM lần này nằm ở stack. Chúng ta đã có một stack cho biến cục bộ và giá trị tạm thời, nên coi như đã đi được nửa đường. Nhưng ta chưa có khái niệm call stack. Trước khi tiến xa hơn, ta sẽ phải xử lý điều đó. Nhưng trước hết, hãy viết chút code. Tôi luôn thấy dễ chịu hơn khi bắt đầu hành động. Chúng ta không thể làm được nhiều nếu chưa có cách biểu diễn function, nên hãy bắt đầu từ đó. Từ góc nhìn của VM, function là gì?

Một function có phần thân có thể execute, tức là có bytecode. Ta có thể compile toàn bộ chương trình và tất cả khai báo function vào một Chunk khổng lồ duy nhất. Mỗi function sẽ có một con trỏ trỏ tới instruction đầu tiên của code của nó bên trong Chunk.

Đây cũng gần giống cách compile sang native code, nơi bạn nhận được một khối machine code nguyên khối. Nhưng với bytecode VM của chúng ta, ta có thể làm ở mức trừu tượng cao hơn một chút. Tôi nghĩ mô hình gọn gàng hơn là cho mỗi function một Chunk riêng. Ta cũng sẽ cần thêm một số metadata khác, nên hãy nhét tất cả vào một struct ngay bây giờ.

  struct Obj* next;
};

typedef struct {
  Obj obj;
  int arity;
  Chunk chunk;
  ObjString* name;
} ObjFunction;

struct ObjString {

Functions là first-class trong Lox, nên chúng cần là các object Lox thực sự. Vì vậy, ObjFunction có cùng phần header Obj mà tất cả các loại object khác chia sẻ. Trường arity lưu số lượng tham số mà function mong đợi. Sau đó, ngoài chunk, ta lưu cả tên của function. Điều này sẽ hữu ích khi báo lỗi runtime dễ đọc.

Đây là lần đầu tiên module “object” cần tham chiếu tới Chunk, nên ta thêm một include.

#include "common.h"

#include "chunk.h"

#include "value.h"

Giống như với string, ta định nghĩa một số hàm tiện ích để làm việc với function Lox trong C dễ hơn. Kiểu như một phiên bản “lập trình hướng đối tượng” đơn giản. Đầu tiên, ta khai báo một hàm C để tạo một function Lox mới.

  uint32_t hash;
};

ObjFunction* newFunction();

ObjString* takeString(char* chars, int length);

Phần hiện thực nằm ở đây:

ObjFunction* newFunction() {
  ObjFunction* function = ALLOCATE_OBJ(ObjFunction, OBJ_FUNCTION);
  function->arity = 0;
  function->name = NULL;
  initChunk(&function->chunk);
  return function;
}

Ta dùng ALLOCATE_OBJ() để cấp phát bộ nhớ và khởi tạo header của object để VM biết nó thuộc loại object nào. Thay vì truyền tham số để khởi tạo function như với ObjString, ta thiết lập function ở trạng thái “trắng” — arity bằng 0, không tên, không code. Những thông tin này sẽ được điền sau khi function được tạo.

Vì có một loại object mới, ta cần thêm một object type mới vào enum.

typedef enum {

  OBJ_FUNCTION,

  OBJ_STRING,
} ObjType;

Khi xong việc với một function object, ta phải trả lại phần bộ nhớ mà nó đã mượn từ hệ điều hành.

  switch (object->type) {

    case OBJ_FUNCTION: {
      ObjFunction* function = (ObjFunction*)object;
      freeChunk(&function->chunk);
      FREE(ObjFunction, object);
      break;
    }

    case OBJ_STRING: {

Case trong switch này chịu trách nhiệm giải phóng chính ObjFunction cũng như bất kỳ vùng nhớ nào nó sở hữu. Functions sở hữu chunk của chúng, nên ta gọi hàm “giống destructor” của Chunk.

Lox cho phép bạn in bất kỳ object nào, và functions là first-class objects, nên ta cũng cần xử lý chúng.

  switch (OBJ_TYPE(value)) {

    case OBJ_FUNCTION:
      printFunction(AS_FUNCTION(value));
      break;

    case OBJ_STRING:

Hàm này gọi tới:

static void printFunction(ObjFunction* function) {
  printf("<fn %s>", function->name->chars);
}

Vì function biết tên của mình, nên nó có thể tự “giới thiệu”.

Cuối cùng, ta có một vài macro để chuyển đổi value thành function. Đầu tiên, đảm bảo value của bạn thực sự là một function.

#define OBJ_TYPE(value)        (AS_OBJ(value)->type)

#define IS_FUNCTION(value)     isObjType(value, OBJ_FUNCTION)

#define IS_STRING(value)       isObjType(value, OBJ_STRING)

Nếu điều đó đúng, bạn có thể an toàn cast Value thành con trỏ ObjFunction bằng cách dùng:

#define IS_STRING(value)       isObjType(value, OBJ_STRING)

#define AS_FUNCTION(value)     ((ObjFunction*)AS_OBJ(value))

#define AS_STRING(value)       ((ObjString*)AS_OBJ(value))

Vậy là mô hình object của chúng ta đã biết cách biểu diễn functions. Tôi đang nóng máy rồi đấy. Sẵn sàng cho phần khó hơn chưa?

24 . 2Biên dịch sang Function Object

Hiện tại, compiler của chúng ta giả định rằng nó luôn biên dịch vào một chunk duy nhất. Khi mỗi function có code riêng nằm trong các chunk riêng biệt, mọi thứ sẽ phức tạp hơn. Khi compiler gặp một khai báo function, nó cần phát sinh code vào chunk của function đó khi biên dịch phần thân. Cuối phần thân function, compiler cần quay lại chunk trước đó mà nó đang làm việc.

Điều này ổn với code bên trong thân function, nhưng còn code không nằm trong đó thì sao? “Top level” của một chương trình Lox cũng là code dạng mệnh lệnh, và chúng ta cần một chunk để biên dịch nó. Ta có thể đơn giản hóa compiler và VM bằng cách đặt cả code top-level này vào bên trong một function được định nghĩa tự động. Bằng cách đó, compiler luôn ở trong một thân function nào đó, và VM luôn chạy code bằng cách gọi một function. Giống như toàn bộ chương trình được bọc bên trong một main() ngầm định.

Vậy nên, trước khi đến với function do người dùng định nghĩa, hãy thực hiện việc tái cấu trúc để hỗ trợ function top-level ngầm định này. Bắt đầu với struct Compiler. Thay vì trỏ trực tiếp tới một Chunk mà compiler sẽ ghi code vào, nó sẽ giữ tham chiếu tới function object đang được xây dựng.

typedef struct {

  ObjFunction* function;
  FunctionType type;

  Local locals[UINT8_COUNT];

Chúng ta cũng có một enum FunctionType nhỏ. Nó cho phép compiler biết khi nào đang biên dịch code top-level và khi nào đang biên dịch thân function. Phần lớn compiler không quan tâm đến điều này — đó là lý do tại sao đây là một lớp trừu tượng hữu ích — nhưng ở một vài chỗ, sự phân biệt này lại quan trọng. Chúng ta sẽ gặp một ví dụ sau.

typedef enum {
  TYPE_FUNCTION,
  TYPE_SCRIPT
} FunctionType;

Mọi chỗ trong compiler trước đây ghi vào Chunk giờ cần thông qua con trỏ function. May mắn là từ nhiều chương trước, chúng ta đã đóng gói việc truy cập chunk vào hàm currentChunk(). Chỉ cần sửa ở đó là phần còn lại của compiler sẽ ổn.

Compiler* current = NULL;

static Chunk* currentChunk() {
  return &current->function->chunk;
}

static void errorAt(Token* token, const char* message) {

Chunk hiện tại luôn là chunk thuộc về function mà ta đang biên dịch. Tiếp theo, ta cần thực sự tạo function đó. Trước đây, VM truyền một Chunk cho compiler để nó điền code vào. Giờ thì compiler sẽ tạo và trả về một function chứa code đã compile của top-level — vốn là tất cả những gì chúng ta hỗ trợ hiện tại — của chương trình người dùng.

24 . 2 . 1Tạo function khi compile

Chúng ta bắt đầu luồng này trong compile(), hàm entry point chính của compiler.

  Compiler compiler;

  initCompiler(&compiler, TYPE_SCRIPT);

  parser.hadError = false;

Có khá nhiều thay đổi trong cách khởi tạo compiler. Đầu tiên, ta khởi tạo các trường mới của Compiler.

static void initCompiler(Compiler* compiler, FunctionType type) {
  compiler->function = NULL;
  compiler->type = type;

  compiler->localCount = 0;

Sau đó, ta cấp phát một function object mới để compile vào đó.

  compiler->scopeDepth = 0;

  compiler->function = newFunction();

  current = compiler;

Việc tạo một ObjFunction trong compiler có thể trông hơi lạ. Function object là biểu diễn runtime của một function, nhưng ở đây ta lại tạo nó khi compile. Cách nghĩ là: function giống như một literal string hoặc number. Nó tạo ra một cầu nối giữa thế giới compile-time và runtime. Khi chúng ta đến với khai báo function, chúng thực sự là literal — một dạng ký pháp tạo ra giá trị của một kiểu dựng sẵn. Vì vậy, compiler tạo function object trong quá trình compile. Sau đó, ở runtime, chúng chỉ đơn giản được gọi.

Đây là một đoạn code kỳ lạ khác:

  current = compiler;

  Local* local = &current->locals[current->localCount++];
  local->depth = 0;
  local->name.start = "";
  local->name.length = 0;

}

Hãy nhớ rằng mảng locals của compiler dùng để theo dõi stack slot nào gắn với biến cục bộ hoặc biến tạm nào. Từ giờ trở đi, compiler sẽ ngầm “giữ chỗ” stack slot số 0 cho mục đích nội bộ của VM. Chúng ta gán cho nó một tên rỗng để người dùng không thể viết một identifier tham chiếu tới nó. Tôi sẽ giải thích điều này khi nó trở nên hữu ích.

Đó là phần khởi tạo. Chúng ta cũng cần một vài thay đổi ở phía kết thúc khi compile xong một đoạn code.

static ObjFunction* endCompiler() {

  emitReturn();

Trước đây, khi interpret() gọi vào compiler, nó truyền vào một Chunk để ghi code. Giờ thì compiler tự tạo function object, nên chúng ta sẽ trả về function đó. Ta lấy nó từ compiler hiện tại ở đây:

  emitReturn();

  ObjFunction* function = current->function;

#ifdef DEBUG_PRINT_CODE

Và trả nó về cho compile() như sau:

#endif

  return function;

}

Đây cũng là lúc thích hợp để chỉnh sửa thêm một chút trong hàm này. Trước đó, chúng ta đã thêm code chẩn đoán để VM dump bytecode đã disassemble nhằm debug compiler. Giờ ta cần sửa lại để nó vẫn hoạt động khi chunk được tạo ra nằm bên trong một function.

#ifdef DEBUG_PRINT_CODE
  if (!parser.hadError) {

    disassembleChunk(currentChunk(), function->name != NULL
        ? function->name->chars : "<script>");

  }
#endif

Hãy chú ý đoạn kiểm tra xem tên của function có phải NULL không. Function do người dùng định nghĩa thì có tên, nhưng function ngầm định mà chúng ta tạo cho code top-level thì không, và ta cần xử lý điều đó một cách gọn gàng ngay cả trong code chẩn đoán của chính mình. Nói về chuyện này:

static void printFunction(ObjFunction* function) {

  if (function->name == NULL) {
    printf("<script>");
    return;
  }

  printf("<fn %s>", function->name->chars);

Người dùng không thể lấy tham chiếu tới function top-level và thử in nó, nhưng code chẩn đoán DEBUG_TRACE_EXECUTION in toàn bộ stack thì có thể và thực sự làm điều đó.

Lên một tầng tới compile(), ta chỉnh lại signature hàm.

#include "vm.h"

ObjFunction* compile(const char* source);

#endif

Thay vì nhận một chunk, giờ nó trả về một function. Trong phần hiện thực:

ObjFunction* compile(const char* source) {

  initScanner(source);

Cuối cùng, ta đến với một chút code thực sự. Ta thay đổi phần cuối của hàm thành:

  while (!match(TOKEN_EOF)) {
    declaration();
  }

  ObjFunction* function = endCompiler();
  return parser.hadError ? NULL : function;

}

Ta lấy function object từ compiler. Nếu không có lỗi compile, ta trả về nó. Ngược lại, ta báo lỗi bằng cách trả về NULL. Cách này giúp VM không cố execute một function có thể chứa bytecode không hợp lệ.

Cuối cùng, chúng ta sẽ cập nhật interpret() để xử lý khai báo mới của compile(), nhưng trước đó còn một số thay đổi khác cần thực hiện.

24 . 3Call Frames

Đã đến lúc thực hiện một bước nhảy khái niệm lớn. Trước khi có thể hiện thực khai báo và lời gọi function, chúng ta cần chuẩn bị cho VM sẵn sàng xử lý chúng. Có hai vấn đề chính cần quan tâm:

24 . 3 . 1Cấp phát biến cục bộ

Compiler cấp phát stack slot cho các biến cục bộ. Vậy điều đó sẽ hoạt động thế nào khi tập hợp biến cục bộ trong chương trình được phân tán qua nhiều function?

Một lựa chọn là giữ chúng hoàn toàn tách biệt. Mỗi function sẽ có một tập slot riêng trong stack của VM mà nó sở hữu vĩnh viễn, ngay cả khi function đó không được gọi. Mỗi biến cục bộ trong toàn bộ chương trình sẽ có một vùng nhớ riêng trong VM mà nó giữ cho mình.

Tin hay không thì tùy, nhưng các implementation ngôn ngữ lập trình thời kỳ đầu đã từng làm như vậy. Những compiler Fortran đầu tiên cấp phát bộ nhớ tĩnh cho từng biến. Vấn đề hiển nhiên là điều này cực kỳ kém hiệu quả. Phần lớn function không ở trạng thái đang được gọi tại bất kỳ thời điểm nào, nên việc giữ bộ nhớ không dùng cho chúng là lãng phí.

Vấn đề cơ bản hơn là đệ quy. Với đệ quy, bạn có thể “đang ở trong” nhiều lời gọi tới cùng một function cùng lúc. Mỗi lời gọi cần vùng nhớ riêng cho các biến cục bộ của nó. Trong jlox, chúng ta giải quyết điều này bằng cách cấp phát động bộ nhớ cho một environment mỗi khi function được gọi hoặc khi vào một block. Trong clox, chúng ta không muốn chịu chi phí hiệu năng đó ở mỗi lần gọi function.

Thay vào đó, giải pháp của chúng ta nằm đâu đó giữa cách cấp phát tĩnh của Fortran và cách tiếp cận động của jlox. Value stack trong VM dựa trên quan sát rằng các biến cục bộ và biến tạm thời có hành vi theo kiểu last-in first-out. May mắn cho chúng ta, điều này vẫn đúng ngay cả khi bạn thêm lời gọi hàm vào. Đây là một ví dụ:

fun first() {
  var a = 1;
  second();
  var b = 2;
}

fun second() {
  var c = 3;
  var d = 4;
}

first();

Hãy đi từng bước qua chương trình và xem tại mỗi thời điểm, biến nào đang nằm trong bộ nhớ:

Khi luồng execute đi qua hai lời gọi hàm, mọi biến cục bộ đều tuân theo nguyên tắc: bất kỳ biến nào được khai báo sau nó sẽ bị loại bỏ trước khi biến đầu tiên cần được loại bỏ. Điều này đúng ngay cả giữa các lời gọi hàm. Ta biết rằng ta sẽ xong việc với c và d trước khi xong với a. Có vẻ như ta hoàn toàn có thể cấp phát biến cục bộ trên value stack của VM.

Lý tưởng nhất, ta vẫn muốn xác định vị trí của mỗi biến trên stack ngay tại compile time. Điều đó giúp các instruction bytecode làm việc với biến trở nên đơn giản và nhanh chóng. Trong ví dụ trên, ta có thể hình dung việc này một cách đơn giản, nhưng không phải lúc nào cũng làm được. Xem thử ví dụ sau:

fun first() {
  var a = 1;
  second();
  var b = 2;
  second();
}

fun second() {
  var c = 3;
  var d = 4;
}

first();

Trong lần gọi đầu tiên tới second(), c và d sẽ nằm ở slot 1 và 2. Nhưng trong lần gọi thứ hai, ta cần chừa chỗ cho b, nên c và d phải nằm ở slot 2 và 3. Do đó, compiler không thể cố định một slot chính xác cho mỗi biến cục bộ xuyên suốt các lời gọi hàm. Nhưng bên trong một hàm nhất định, vị trí tương đối của mỗi biến cục bộ là cố định. Biến d luôn nằm ngay sau c. Đây chính là điểm mấu chốt.

Khi một hàm được gọi, ta không biết đỉnh stack sẽ ở đâu vì nó có thể được gọi từ nhiều ngữ cảnh khác nhau. Nhưng, bất kể đỉnh stack ở đâu, ta vẫn biết tất cả biến cục bộ của hàm sẽ nằm ở đâu so với điểm bắt đầu đó. Vậy nên, giống như nhiều vấn đề khác, ta giải quyết bài toán cấp phát này bằng một tầng gián tiếp.

Khi bắt đầu mỗi lời gọi hàm, VM sẽ ghi lại vị trí của slot đầu tiên nơi các biến cục bộ của hàm đó bắt đầu. Các instruction làm việc với biến cục bộ sẽ truy cập chúng bằng chỉ số slot tương đối với vị trí này, thay vì tương đối với đáy stack như hiện tại. Tại compile time, ta tính toán các slot tương đối đó. Tại runtime, ta chuyển slot tương đối thành chỉ số tuyệt đối trên stack bằng cách cộng thêm vị trí bắt đầu của lời gọi hàm.

Cứ như thể hàm có một “cửa sổ” hoặc “frame” bên trong stack lớn hơn, nơi nó có thể lưu các biến cục bộ của mình. Vị trí của call frame được xác định tại runtime, nhưng bên trong và tương đối với vùng đó, ta biết chính xác mọi thứ nằm ở đâu.

Tên gọi lịch sử cho vị trí được ghi lại này — nơi các biến cục bộ của hàm bắt đầu — là frame pointer vì nó trỏ tới đầu call frame của hàm. Đôi khi bạn sẽ nghe thấy base pointer, vì nó trỏ tới slot gốc của stack, nơi tất cả biến của hàm được đặt lên.

Đó là mảnh dữ liệu đầu tiên mà ta cần theo dõi. Mỗi khi gọi một hàm, VM sẽ xác định slot đầu tiên trên stack nơi các biến của hàm đó bắt đầu.

24 . 3 . 2Return addresses

Hiện tại, VM duyệt qua luồng instruction bằng cách tăng trường ip. Hành vi thú vị duy nhất là ở các instruction điều khiển luồng, vốn thay đổi ip với một giá trị offset lớn hơn. Gọi một hàm thì khá đơn giản — chỉ cần đặt ip trỏ tới instruction đầu tiên trong chunk của hàm đó. Nhưng khi hàm chạy xong thì sao?

VM cần quay lại chunk nơi hàm được gọi và tiếp tục execute tại instruction ngay sau lời gọi. Do đó, với mỗi lời gọi hàm, ta cần theo dõi vị trí sẽ nhảy về khi lời gọi kết thúc. Đây được gọi là return address vì nó là địa chỉ của instruction mà VM sẽ quay lại sau khi gọi xong.

Và một lần nữa, nhờ có đệ quy, có thể tồn tại nhiều return address cho cùng một hàm, nên đây là thuộc tính của từng lần gọi chứ không phải của bản thân hàm.

24 . 3 . 3The call stack

Vậy là, với mỗi lần gọi hàm đang hoạt động — tức là mỗi lời gọi chưa trả về — chúng ta cần theo dõi vị trí trên stack nơi các biến cục bộ của hàm đó bắt đầu, và vị trí mà caller sẽ tiếp tục execute. Chúng ta sẽ đặt thông tin này, cùng với một số dữ liệu khác, vào một struct mới.

#define STACK_MAX 256

typedef struct {
  ObjFunction* function;
  uint8_t* ip;
  Value* slots;
} CallFrame;

typedef struct {

Một CallFrame đại diện cho một lần gọi hàm đang diễn ra. Trường slots trỏ vào value stack của VM tại slot đầu tiên mà hàm này có thể sử dụng. Tôi đặt tên ở dạng số nhiều vì — nhờ vào “đặc sản” của C là “con trỏ gần như là mảng” — chúng ta sẽ xử lý nó như một mảng.

Cách hiện thực return address hơi khác một chút so với mô tả trước đó. Thay vì lưu return address trong frame của callee, caller sẽ lưu ip của chính nó. Khi trả về từ một hàm, VM sẽ nhảy tới ip của CallFrame của caller và tiếp tục từ đó.

Tôi cũng nhét vào đây một con trỏ tới function đang được gọi. Chúng ta sẽ dùng nó để tra cứu constants và cho một vài việc khác.

Mỗi khi một hàm được gọi, chúng ta tạo một struct như thế này. Chúng ta có thể cấp phát động chúng trên heap, nhưng như vậy sẽ chậm. Lời gọi hàm là một thao tác cốt lõi, nên cần nhanh nhất có thể. May mắn là, ta có thể áp dụng cùng một quan sát như với biến: lời gọi hàm có tính chất stack. Nếu first() gọi second(), thì lời gọi tới second() sẽ hoàn tất trước khi first() hoàn tất.

Vì vậy, trong VM, chúng ta tạo sẵn một mảng các CallFrame và xử lý nó như một stack, giống như cách ta làm với mảng value.

typedef struct {

  CallFrame frames[FRAMES_MAX];
  int frameCount;

  Value stack[STACK_MAX];

Mảng này thay thế cho các trường chunk và ip mà trước đây chúng ta lưu trực tiếp trong VM. Giờ đây, mỗi CallFrame có ip riêng và con trỏ riêng tới ObjFunction mà nó đang execute. Từ đó, ta có thể truy cập chunk của function.

Trường frameCount mới trong VM lưu chiều cao hiện tại của CallFrame stack — tức là số lượng lời gọi hàm đang diễn ra. Để giữ cho clox đơn giản, dung lượng của mảng này là cố định. Điều này có nghĩa là, giống như nhiều implementation ngôn ngữ khác, có một độ sâu gọi hàm tối đa mà chúng ta có thể xử lý. Với clox, nó được định nghĩa ở đây:

#include "value.h"

#define FRAMES_MAX 64
#define STACK_MAX (FRAMES_MAX * UINT8_COUNT)

typedef struct {

Chúng ta cũng định nghĩa lại kích thước của value stack dựa trên giá trị này để đảm bảo có đủ stack slot ngay cả trong những cây lời gọi rất sâu. Khi VM khởi động, CallFrame stack sẽ rỗng.

  vm.stackTop = vm.stack;

  vm.frameCount = 0;

}

Header “vm.h” cần truy cập ObjFunction, nên ta thêm một include.

#define clox_vm_h

#include "object.h"

#include "table.h"

Giờ chúng ta sẵn sàng chuyển sang file hiện thực của VM. Sẽ có kha khá việc “dọn dẹp” ở đây. Chúng ta đã chuyển ip ra khỏi struct VM và đưa vào CallFrame. Ta cần sửa mọi dòng code trong VM có đụng tới ip để xử lý điều đó. Ngoài ra, các instruction truy cập biến cục bộ theo stack slot cũng cần được cập nhật để làm việc tương đối với trường slots của CallFrame hiện tại.

Chúng ta sẽ bắt đầu từ trên xuống và xử lý lần lượt.

static InterpretResult run() {

  CallFrame* frame = &vm.frames[vm.frameCount - 1];

#define READ_BYTE() (*frame->ip++)

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

#define READ_CONSTANT() \
    (frame->function->chunk.constants.values[READ_BYTE()])

#define READ_STRING() AS_STRING(READ_CONSTANT())

Đầu tiên, ta lưu CallFrame trên cùng hiện tại vào một biến local bên trong hàm execute bytecode chính. Sau đó, ta thay thế các macro truy cập bytecode bằng các phiên bản truy cập ip thông qua biến đó.

Giờ chúng ta sẽ đến với từng instruction cần được “chăm sóc” một chút.

      case OP_GET_LOCAL: {
        uint8_t slot = READ_BYTE();

        push(frame->slots[slot]);

        break;

Trước đây, OP_GET_LOCAL đọc slot local được chỉ định trực tiếp từ mảng stack của VM, nghĩa là nó đánh chỉ số slot tính từ đáy stack. Giờ đây, nó truy cập mảng slots của frame hiện tại, tức là truy cập slot theo số thứ tự tương đối so với điểm bắt đầu của frame đó.

Việc gán giá trị cho một biến local cũng hoạt động tương tự.

      case OP_SET_LOCAL: {
        uint8_t slot = READ_BYTE();

        frame->slots[slot] = peek(0);

        break;

Các instruction nhảy (jump) trước đây thay đổi trường ip của VM. Giờ thì chúng cũng làm điều tương tự nhưng với ip của frame hiện tại.

      case OP_JUMP: {
        uint16_t offset = READ_SHORT();

        frame->ip += offset;

        break;

Tương tự với jump có điều kiện:

      case OP_JUMP_IF_FALSE: {
        uint16_t offset = READ_SHORT();

        if (isFalsey(peek(0))) frame->ip += offset;

        break;

Và instruction vòng lặp nhảy lùi của chúng ta:

      case OP_LOOP: {
        uint16_t offset = READ_SHORT();

        frame->ip -= offset;

        break;

Chúng ta có một đoạn code chẩn đoán in ra từng instruction khi nó được execute để giúp debug VM. Đoạn này cũng cần hoạt động với cấu trúc mới.

    printf("\n");

    disassembleInstruction(&frame->function->chunk,
        (int)(frame->ip - frame->function->chunk.code));

#endif

Thay vì truyền vào chunk và ip của VM, giờ ta đọc từ CallFrame hiện tại.

Bạn thấy đấy, thực ra cũng không quá khó. Hầu hết các instruction chỉ dùng macro nên không cần chỉnh sửa. Tiếp theo, ta lên một tầng tới đoạn code gọi run().

InterpretResult interpret(const char* source) {

  ObjFunction* function = compile(source);
  if (function == NULL) return INTERPRET_COMPILE_ERROR;

  push(OBJ_VAL(function));
  CallFrame* frame = &vm.frames[vm.frameCount++];
  frame->function = function;
  frame->ip = function->chunk.code;
  frame->slots = vm.stack;

  InterpretResult result = run();

Cuối cùng, chúng ta kết nối các thay đổi ở compiler trước đó với các thay đổi ở back-end vừa thực hiện. Đầu tiên, ta truyền source code vào compiler. Nó trả về một ObjFunction mới chứa code top-level đã compile. Nếu nhận về NULL, nghĩa là có lỗi compile-time và compiler đã báo lỗi. Trong trường hợp đó, ta dừng lại vì không thể chạy gì được.

Ngược lại, ta lưu function này lên stack và chuẩn bị một CallFrame ban đầu để execute code của nó. Giờ bạn sẽ thấy vì sao compiler dành riêng stack slot số 0 — đó là nơi lưu function đang được gọi. Trong CallFrame mới, ta trỏ tới function, khởi tạo ip của nó trỏ tới đầu bytecode của function, và thiết lập “cửa sổ” stack của nó bắt đầu từ đáy value stack của VM.

Điều này giúp interpreter sẵn sàng bắt đầu execute code. Sau khi chạy xong, trước đây VM sẽ giải phóng chunk được hardcode. Giờ ObjFunction sở hữu code đó, nên ta không cần làm vậy nữa. Kết thúc interpret() giờ chỉ đơn giản là:

  frame->slots = vm.stack;

  return run();

}

Phần code cuối cùng còn tham chiếu tới các trường cũ của VM là runtimeError(). Chúng ta sẽ quay lại nó sau trong chương này, nhưng tạm thời sửa thành:

  fputs("\n", stderr);

  CallFrame* frame = &vm.frames[vm.frameCount - 1];
  size_t instruction = frame->ip - frame->function->chunk.code - 1;
  int line = frame->function->chunk.lines[instruction];

  fprintf(stderr, "[line %d] in script\n", line);

Thay vì đọc chunk và ip trực tiếp từ VM, nó lấy từ CallFrame trên cùng của stack. Như vậy function sẽ hoạt động trở lại và hành xử như trước.

Nếu mọi thứ được làm đúng, clox đã trở lại trạng thái chạy được. Chạy thử và nó… vẫn làm đúng như trước. Chúng ta chưa thêm tính năng mới nào, nên hơi hụt hẫng. Nhưng toàn bộ hạ tầng đã sẵn sàng. Giờ hãy tận dụng nó.

24 . 4Function Declarations

Trước khi có thể làm call expression, ta cần có cái để gọi, nên sẽ làm function declaration trước. Từ khóa fun mở đầu cho phần này.

static void declaration() {

  if (match(TOKEN_FUN)) {
    funDeclaration();
  } else if (match(TOKEN_VAR)) {

    varDeclaration();

Điều này chuyển quyền điều khiển tới đây:

static void funDeclaration() {
  uint8_t global = parseVariable("Expect function name.");
  markInitialized();
  function(TYPE_FUNCTION);
  defineVariable(global);
}

Functions là giá trị first-class, và một function declaration đơn giản là tạo và lưu nó vào một biến mới khai báo. Vậy nên ta parse tên giống như bất kỳ khai báo biến nào khác. Function declaration ở top-level sẽ gán function cho một biến global. Bên trong block hoặc function khác, function declaration sẽ tạo biến local.

Ở một chương trước, tôi đã giải thích cách biến được định nghĩa qua hai giai đoạn. Điều này đảm bảo bạn không thể truy cập giá trị của biến ngay trong phần khởi tạo của chính nó. Điều đó sẽ tệ vì biến chưa có giá trị.

Functions không gặp vấn đề này. Việc một function tham chiếu tới tên của chính nó bên trong thân là an toàn. Bạn không thể gọi function và execute thân của nó cho tới khi nó được định nghĩa đầy đủ, nên bạn sẽ không bao giờ thấy biến ở trạng thái chưa khởi tạo. Trên thực tế, việc cho phép điều này rất hữu ích để hỗ trợ các hàm local đệ quy.

Để làm được điều đó, ta đánh dấu biến của function declaration là “initialized” ngay khi compile tên, trước khi compile thân. Như vậy tên có thể được tham chiếu bên trong thân mà không gây lỗi.

Tuy nhiên, ta cần một bước kiểm tra:

static void markInitialized() {

  if (current->scopeDepth == 0) return;

  current->locals[current->localCount - 1].depth =

Trước đây, ta chỉ gọi markInitialized() khi đã biết mình đang ở trong local scope. Giờ, function declaration ở top-level cũng sẽ gọi hàm này. Khi đó, không có biến local nào để đánh dấu — function được gán cho một biến global.

Tiếp theo, ta compile chính function — danh sách tham số và block body. Để làm điều đó, ta dùng một helper riêng. Helper này sinh code để để lại function object kết quả trên đỉnh stack. Sau đó, ta gọi defineVariable() để lưu function đó vào biến đã khai báo.

Tôi tách riêng code compile tham số và thân vì sau này sẽ tái sử dụng khi parse method declaration trong class. Hãy xây dựng dần dần, bắt đầu với:

static void function(FunctionType type) {
  Compiler compiler;
  initCompiler(&compiler, type);
  beginScope(); 

  consume(TOKEN_LEFT_PAREN, "Expect '(' after function name.");
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after parameters.");
  consume(TOKEN_LEFT_BRACE, "Expect '{' before function body.");
  block();

  ObjFunction* function = endCompiler();
  emitBytes(OP_CONSTANT, makeConstant(OBJ_VAL(function)));
}

Hiện tại, ta chưa quan tâm tới tham số. Ta parse một cặp ngoặc đơn rỗng, sau đó là thân hàm. Thân bắt đầu bằng dấu ngoặc nhọn mở, ta parse ở đây. Sau đó, ta gọi hàm block() sẵn có, vốn biết cách compile phần còn lại của block bao gồm cả dấu ngoặc nhọn đóng.

24 . 4 . 1A stack of compilers

Phần thú vị nằm ở chỗ xử lý compiler ở đầu và cuối. Struct Compiler lưu trữ dữ liệu như slot nào thuộc về biến cục bộ nào, chúng ta đang ở mức lồng nhau bao nhiêu block, v.v. Tất cả những thứ đó đều gắn với một function duy nhất. Nhưng giờ front end cần xử lý việc compile nhiều function lồng nhau bên trong nhau.

Mẹo để quản lý việc này là tạo một Compiler riêng cho mỗi function đang được compile. Khi bắt đầu compile một function declaration, ta tạo một Compiler mới trên C stack và khởi tạo nó. initCompiler() đặt Compiler đó thành compiler hiện tại. Sau đó, khi compile thân hàm, tất cả các hàm sinh bytecode sẽ ghi vào chunk thuộc về function của Compiler mới này.

Khi tới cuối block body của function, ta gọi endCompiler(). Hàm này trả về function object vừa compile xong, và ta lưu nó như một constant trong bảng constant của function bao quanh nó. Nhưng khoan, làm sao ta quay lại function bao quanh? Ta đã mất nó khi initCompiler() ghi đè con trỏ compiler hiện tại.

Ta giải quyết bằng cách coi chuỗi các Compiler lồng nhau như một stack. Khác với Value và CallFrame stack trong VM, ta sẽ không dùng mảng. Thay vào đó, ta dùng linked list. Mỗi Compiler trỏ ngược về Compiler của function bao quanh nó, cho tới Compiler gốc của code top-level.

} FunctionType;

typedef struct Compiler {
  struct Compiler* enclosing;

  ObjFunction* function;

Bên trong struct Compiler, ta không thể tham chiếu tới typedef Compiler vì khai báo đó chưa hoàn tất. Thay vào đó, ta đặt tên cho chính struct và dùng tên đó cho kiểu của field. C đúng là kỳ quặc.

Khi khởi tạo một Compiler mới, ta lưu compiler sắp không còn là hiện tại nữa vào con trỏ đó.

static void initCompiler(Compiler* compiler, FunctionType type) {

  compiler->enclosing = current;

  compiler->function = NULL;

Rồi khi một Compiler kết thúc, nó “pop” chính nó khỏi stack bằng cách khôi phục compiler trước đó thành compiler hiện tại.

#endif

  current = current->enclosing;

  return function;

Lưu ý rằng ta thậm chí không cần cấp phát động các struct Compiler. Mỗi cái được lưu như một biến local trên C stack — hoặc trong compile() hoặc function(). Linked list các Compiler được “xâu chuỗi” qua C stack. Lý do ta có thể có số lượng không giới hạn là vì compiler của chúng ta dùng recursive descent, nên function() sẽ tự gọi lại chính nó khi có các function declaration lồng nhau.

24 . 4 . 2Function parameters

Function sẽ chẳng hữu ích mấy nếu bạn không thể truyền tham số cho chúng, nên giờ ta sẽ làm phần parameters.

  consume(TOKEN_LEFT_PAREN, "Expect '(' after function name.");

  if (!check(TOKEN_RIGHT_PAREN)) {
    do {
      current->function->arity++;
      if (current->function->arity > 255) {
        errorAtCurrent("Can't have more than 255 parameters.");
      }
      uint8_t constant = parseVariable("Expect parameter name.");
      defineVariable(constant);
    } while (match(TOKEN_COMMA));
  }

  consume(TOKEN_RIGHT_PAREN, "Expect ')' after parameters.");

Về mặt ngữ nghĩa, một parameter đơn giản là một biến cục bộ được khai báo trong phạm vi từ vựng ngoài cùng của thân hàm. Ta có thể tận dụng cơ chế sẵn có của compiler để khai báo biến cục bộ có tên nhằm parse và compile parameters. Khác với biến cục bộ, vốn có initializer, ở đây không có code để khởi tạo giá trị cho parameter. Chúng ta sẽ thấy chúng được khởi tạo thế nào sau khi làm phần truyền đối số trong lời gọi hàm.

Nhân tiện, ta ghi nhận arity của function bằng cách đếm số parameter parse được. Thông tin metadata khác mà ta lưu cùng function là tên của nó. Khi compile một function declaration, ta gọi initCompiler() ngay sau khi parse tên hàm. Điều đó có nghĩa là ta có thể lấy tên ngay lúc đó từ token trước đó.

  current = compiler;

  if (type != TYPE_SCRIPT) {
    current->function->name = copyString(parser.previous.start,
                                         parser.previous.length);
  }

  Local* local = &current->locals[current->localCount++];

Lưu ý rằng ta cẩn thận tạo một bản sao của chuỗi tên. Hãy nhớ rằng lexeme trỏ trực tiếp vào chuỗi source code gốc. Chuỗi đó có thể bị giải phóng khi compile xong. Function object mà ta tạo trong compiler tồn tại lâu hơn compiler và kéo dài tới runtime. Vì vậy nó cần một chuỗi tên được cấp phát trên heap riêng để giữ lại.

Tuyệt. Giờ ta có thể compile function declaration, như thế này:

fun areWeHavingItYet() {
  print "Yes we are!";
}

print areWeHavingItYet;

Chỉ là ta chưa thể làm gì hữu ích với chúng.

24 . 5Function Calls

Kết thúc phần này, chúng ta sẽ bắt đầu thấy một số hành vi thú vị. Bước tiếp theo là gọi hàm. Thường thì ta không nghĩ theo cách này, nhưng một biểu thức gọi hàm thực chất giống như một toán tử ( dạng infix. Bên trái là một biểu thức có độ ưu tiên cao — thường chỉ là một identifier — biểu thị thứ sẽ được gọi. Tiếp theo là dấu ( ở giữa, sau đó là các biểu thức đối số (argument) được phân tách bằng dấu phẩy, và cuối cùng là dấu ) để kết thúc.

Cách nhìn ngữ pháp hơi lạ này giải thích cách chúng ta gắn cú pháp vào bảng phân tích (parsing table).

ParseRule rules[] = {

  [TOKEN_LEFT_PAREN]    = {grouping, call,   PREC_CALL},

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

Khi parser gặp dấu ngoặc đơn mở ngay sau một biểu thức, nó sẽ chuyển sang một hàm parser mới.

static void call(bool canAssign) {
  uint8_t argCount = argumentList();
  emitBytes(OP_CALL, argCount);
}

Chúng ta đã đọc xong token (, nên bước tiếp theo là compile các đối số bằng một helper riêng argumentList(). Hàm này trả về số lượng đối số mà nó compile được. Mỗi biểu thức đối số sẽ sinh code để lại giá trị của nó trên stack, sẵn sàng cho lời gọi hàm. Sau đó, ta phát sinh một instruction OP_CALL mới để gọi hàm, dùng số lượng đối số làm toán hạng (operand).

Chúng ta compile các đối số bằng “người bạn” này:

static uint8_t argumentList() {
  uint8_t argCount = 0;
  if (!check(TOKEN_RIGHT_PAREN)) {
    do {
      expression();
      argCount++;
    } while (match(TOKEN_COMMA));
  }
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after arguments.");
  return argCount;
}

Đoạn code này chắc sẽ trông quen thuộc từ jlox. Ta xử lý các đối số miễn là còn tìm thấy dấu phẩy sau mỗi biểu thức. Khi hết, ta đọc dấu ngoặc đơn đóng cuối cùng và xong.

À, gần xong thôi. Trong jlox, ta đã thêm một kiểm tra ở compile-time để đảm bảo bạn không truyền quá 255 đối số cho một lời gọi. Lúc đó, tôi đã nói rằng vì clox cũng sẽ cần một giới hạn tương tự. Giờ bạn có thể thấy lý do — vì chúng ta nhét số lượng đối số vào bytecode như một toán hạng 1 byte, nên chỉ có thể tối đa 255. Ta cũng cần xác minh điều này trong compiler này.

      expression();

      if (argCount == 255) {
        error("Can't have more than 255 arguments.");
      }

      argCount++;

Đó là phần front end. Giờ hãy chuyển sang back end, với một điểm dừng nhanh ở giữa để khai báo instruction mới.

  OP_LOOP,

  OP_CALL,

  OP_RETURN,

24 . 5 . 1Binding arguments to parameters

Trước khi đi vào hiện thực, ta nên nghĩ về trạng thái stack tại thời điểm gọi hàm và những gì cần làm từ đó. Khi tới instruction gọi hàm, chúng ta đã execute xong biểu thức cho hàm được gọi, tiếp theo là các đối số của nó. Giả sử chương trình của ta như sau:

fun sum(a, b, c) {
  return a + b + c;
}

print 4 + sum(5, 6, 7);

Nếu ta tạm dừng VM ngay tại instruction OP_CALL cho lời gọi sum(), stack sẽ trông như thế này:

Hãy hình dung từ góc nhìn của chính sum(). Khi compiler compile sum(), nó tự động cấp phát slot số 0. Sau đó, nó cấp phát các slot local cho các tham số a, b và c, theo thứ tự. Để thực hiện lời gọi tới sum(), ta cần một CallFrame được khởi tạo với hàm được gọi và một vùng slot stack mà nó có thể dùng. Sau đó, ta cần thu thập các đối số truyền vào hàm và đặt chúng vào đúng slot tương ứng với các tham số.

Khi VM bắt đầu execute thân của sum(), ta muốn “cửa sổ” stack của nó trông như thế này:

Bạn có nhận ra rằng các slot đối số mà caller thiết lập và các slot tham số mà callee cần đều ở đúng thứ tự không? Thật tiện lợi! Đây không phải là ngẫu nhiên. Khi tôi nói về việc mỗi CallFrame có “cửa sổ” riêng vào stack, tôi chưa bao giờ nói rằng các cửa sổ đó phải tách biệt. Không có gì ngăn cản chúng ta cho chúng chồng lấn lên nhau, như thế này:

Phần trên cùng của stack của caller chứa hàm được gọi, theo sau là các đối số theo thứ tự. Ta biết caller không có slot nào khác phía trên đang được dùng, vì mọi biến tạm cần thiết khi đánh giá các biểu thức đối số đã bị loại bỏ. Phần đáy của stack của callee chồng lấn sao cho các slot tham số khớp chính xác với vị trí các giá trị đối số đã có sẵn.

Điều này có nghĩa là ta không cần làm bất kỳ công việc nào để “gắn đối số vào tham số”. Không có việc sao chép giá trị giữa các slot hay qua các environment. Các đối số đã ở đúng vị trí cần thiết. Khó mà tìm được cách nào nhanh hơn thế.

Đến lúc hiện thực instruction gọi hàm.

      }

      case OP_CALL: {
        int argCount = READ_BYTE();
        if (!callValue(peek(argCount), argCount)) {
          return INTERPRET_RUNTIME_ERROR;
        }
        break;
      }

      case OP_RETURN: {

Ta cần biết hàm được gọi và số lượng đối số truyền vào. Ta lấy số lượng đối số từ toán hạng của instruction. Thông tin này cũng cho ta biết vị trí của hàm trên stack bằng cách đếm ngược từ đỉnh stack qua các slot đối số. Ta chuyển dữ liệu đó cho hàm callValue() riêng. Nếu hàm này trả về false, nghĩa là lời gọi gây ra lỗi runtime. Khi đó, ta dừng interpreter.

Nếu callValue() thành công, sẽ có một frame mới trên CallFrame stack cho hàm được gọi. Hàm run() có một con trỏ cache tới frame hiện tại, nên ta cần cập nhật nó.

          return INTERPRET_RUNTIME_ERROR;
        }

        frame = &vm.frames[vm.frameCount - 1];

        break;

Vì vòng lặp dispatch bytecode đọc từ biến frame đó, khi VM execute instruction tiếp theo, nó sẽ đọc ip từ CallFrame của hàm vừa được gọi và nhảy tới code của nó. Công việc execute lời gọi bắt đầu ở đây:

static bool callValue(Value callee, int argCount) {
  if (IS_OBJ(callee)) {
    switch (OBJ_TYPE(callee)) {
      case OBJ_FUNCTION: 
        return call(AS_FUNCTION(callee), argCount);
      default:
        break; // Non-callable object type.
    }
  }
  runtimeError("Can only call functions and classes.");
  return false;
}

Ở đây có nhiều việc hơn là chỉ khởi tạo một CallFrame mới. Vì Lox là ngôn ngữ dynamically typed, không có gì ngăn người dùng viết code tệ kiểu như:

var notAFunction = 123;
notAFunction();

Nếu điều đó xảy ra, runtime cần báo lỗi một cách an toàn và dừng lại. Vậy nên việc đầu tiên ta làm là kiểm tra kiểu của giá trị mà ta đang cố gọi. Nếu nó không phải là function, ta báo lỗi và thoát. Ngược lại, lời gọi thực sự diễn ra ở đây:

static bool call(ObjFunction* function, int argCount) {
  CallFrame* frame = &vm.frames[vm.frameCount++];
  frame->function = function;
  frame->ip = function->chunk.code;
  frame->slots = vm.stackTop - argCount - 1;
  return true;
}

Phần này chỉ đơn giản là khởi tạo CallFrame tiếp theo trên stack. Nó lưu một con trỏ tới function đang được gọi và đặt ip của frame trỏ tới đầu bytecode của function. Cuối cùng, nó thiết lập con trỏ slots để cấp cho frame “cửa sổ” của nó vào stack. Phép tính ở đây đảm bảo rằng các đối số đã có trên stack sẽ thẳng hàng với các tham số của function:

Dấu - 1 nhỏ kia là để tính tới stack slot số 0 mà compiler đã dành riêng cho việc thêm method sau này. Các tham số bắt đầu ở slot số 1, nên ta cho cửa sổ bắt đầu sớm hơn một slot để chúng thẳng hàng với các đối số.

Trước khi tiếp tục, hãy thêm instruction mới này vào disassembler.

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

    case OP_CALL:
      return byteInstruction("OP_CALL", chunk, offset);

    case OP_RETURN:

Và thêm một bước nhỏ nữa. Giờ khi ta đã có một hàm tiện lợi để khởi tạo CallFrame, ta cũng có thể dùng nó để thiết lập frame đầu tiên cho việc execute code top-level.

  push(OBJ_VAL(function));

  call(function, 0);

  return run();

OK, quay lại với phần gọi hàm . . . 

24 . 5 . 2Runtime error checking

Cơ chế chồng lấn các “cửa sổ” stack hoạt động dựa trên giả định rằng một lời gọi truyền chính xác một đối số cho mỗi tham số của function. Nhưng, một lần nữa, vì Lox không phải statically typed, một người dùng bất cẩn có thể truyền quá nhiều hoặc quá ít đối số. Trong Lox, ta định nghĩa đây là một lỗi runtime, và báo lỗi như sau:

static bool call(ObjFunction* function, int argCount) {

  if (argCount != function->arity) {
    runtimeError("Expected %d arguments but got %d.",
        function->arity, argCount);
    return false;
  }

  CallFrame* frame = &vm.frames[vm.frameCount++];

Khá đơn giản. Đây là lý do ta lưu arity của mỗi function bên trong ObjFunction của nó.

Có một lỗi khác cần báo, lỗi này ít liên quan tới sự bất cẩn của người dùng hơn là của chính chúng ta. Vì mảng CallFrame có kích thước cố định, ta cần đảm bảo một chuỗi lời gọi quá sâu không làm tràn nó.

  }

  if (vm.frameCount == FRAMES_MAX) {
    runtimeError("Stack overflow.");
    return false;
  }

  CallFrame* frame = &vm.frames[vm.frameCount++];

Trên thực tế, nếu một chương trình tiến gần tới giới hạn này, rất có thể là do bug trong một đoạn code đệ quy mất kiểm soát.

24 . 5 . 3Printing stack traces

Nhân nói về runtime error, hãy dành chút thời gian để làm cho chúng hữu ích hơn. Dừng lại khi gặp runtime error là quan trọng để ngăn VM “nổ tung” theo một cách khó lường. Nhưng chỉ đơn giản thoát ra thì không giúp người dùng sửa code gây ra lỗi đó.

Công cụ kinh điển để hỗ trợ debug lỗi runtime là stack trace — bản in ra của từng function vẫn đang execute khi chương trình chết, và vị trí execute tại thời điểm đó. Giờ khi ta đã có call stack và tiện lợi lưu tên của từng function, ta có thể hiển thị toàn bộ stack này khi một runtime error phá vỡ “sự yên bình” của người dùng. Nó trông như thế này:

  fputs("\n", stderr);

  for (int i = vm.frameCount - 1; i >= 0; i--) {
    CallFrame* frame = &vm.frames[i];
    ObjFunction* function = frame->function;
    size_t instruction = frame->ip - function->chunk.code - 1;
    fprintf(stderr, "[line %d] in ", 
            function->chunk.lines[instruction]);
    if (function->name == NULL) {
      fprintf(stderr, "script\n");
    } else {
      fprintf(stderr, "%s()\n", function->name->chars);
    }
  }

  resetStack();
}

Sau khi in thông báo lỗi, ta duyệt call stack từ trên xuống (function được gọi gần nhất) tới dưới cùng (code top-level). Với mỗi frame, ta tìm số dòng tương ứng với ip hiện tại bên trong function của frame đó. Sau đó, ta in số dòng cùng với tên function.

Ví dụ, nếu bạn chạy chương trình lỗi này:

fun a() { b(); }
fun b() { c(); }
fun c() {
  c("too", "many");
}

a();

Nó sẽ in ra:

Expected 0 arguments but got 2.
[line 4] in c()
[line 2] in b()
[line 1] in a()
[line 7] in script

Trông cũng không tệ lắm, đúng không?

24 . 5 . 4Returning from functions

Chúng ta sắp hoàn thiện rồi. Giờ ta đã có thể gọi hàm, và VM sẽ execute chúng. Nhưng ta vẫn chưa thể return từ chúng. Chúng ta đã có instruction OP_RETURN từ khá lâu, nhưng nó luôn chứa một đoạn code tạm thời chỉ để thoát khỏi vòng lặp bytecode. Giờ là lúc hiện thực nó một cách “đúng nghĩa”.

      case OP_RETURN: {

        Value result = pop();
        vm.frameCount--;
        if (vm.frameCount == 0) {
          pop();
          return INTERPRET_OK;
        }

        vm.stackTop = frame->slots;
        push(result);
        frame = &vm.frames[vm.frameCount - 1];
        break;

      }

Khi một hàm trả về một giá trị, giá trị đó sẽ nằm trên đỉnh stack. Chúng ta sắp loại bỏ toàn bộ “cửa sổ” stack của hàm được gọi, nên ta pop giá trị trả về đó ra và giữ lại. Sau đó, ta loại bỏ CallFrame của hàm vừa trả về. Nếu đó là CallFrame cuối cùng, nghĩa là ta đã execute xong code top-level. Toàn bộ chương trình đã hoàn tất, nên ta pop hàm script chính ra khỏi stack và thoát interpreter.

Ngược lại, nếu vẫn còn frame khác, ta loại bỏ tất cả các slot mà callee đã dùng cho tham số và biến cục bộ. Điều này bao gồm cả các slot mà caller đã dùng để truyền đối số. Giờ khi lời gọi đã xong, caller không cần chúng nữa. Điều này có nghĩa là đỉnh stack sẽ nằm ngay tại vị trí bắt đầu của “cửa sổ” stack của hàm vừa trả về.

Ta push giá trị trả về lại lên stack ở vị trí mới, thấp hơn đó. Sau đó, ta cập nhật con trỏ cache của hàm run() tới frame hiện tại. Giống như khi bắt đầu một lời gọi, ở vòng lặp dispatch bytecode tiếp theo, VM sẽ đọc ip từ frame đó, và việc execute sẽ nhảy trở lại caller, ngay tại vị trí nó dừng, ngay sau instruction OP_CALL.

Lưu ý rằng ở đây ta giả định hàm thực sự trả về một giá trị, nhưng một hàm có thể ngầm trả về bằng cách chạy tới cuối thân hàm:

fun noReturn() {
  print "Do stuff";
  // Không có return ở đây.
}

print noReturn(); // ???

Ta cũng cần xử lý đúng trường hợp này. Ngôn ngữ được định nghĩa là sẽ ngầm trả về nil trong trường hợp đó. Để làm điều này, ta thêm đoạn sau:

static void emitReturn() {

  emitByte(OP_NIL);

  emitByte(OP_RETURN);
}

Compiler sẽ gọi emitReturn() để ghi instruction OP_RETURN ở cuối thân hàm. Giờ, trước đó, nó sẽ phát sinh instruction để push nil lên stack. Và với điều đó, ta đã có lời gọi hàm hoạt động! Chúng thậm chí còn nhận tham số! Trông gần như là ta biết mình đang làm gì vậy.

24 . 6Return Statements

Nếu bạn muốn một hàm trả về thứ gì đó khác với nil ngầm định, bạn cần một câu lệnh return. Hãy làm cho nó hoạt động.

    ifStatement();

  } else if (match(TOKEN_RETURN)) {
    returnStatement();

  } else if (match(TOKEN_WHILE)) {

Khi compiler thấy từ khóa return, nó sẽ đi tới đây:

static void returnStatement() {
  if (match(TOKEN_SEMICOLON)) {
    emitReturn();
  } else {
    expression();
    consume(TOKEN_SEMICOLON, "Expect ';' after return value.");
    emitByte(OP_RETURN);
  }
}

Biểu thức giá trị trả về là tùy chọn, nên parser sẽ tìm token dấu chấm phẩy để xác định xem có giá trị được cung cấp hay không. Nếu không có giá trị trả về, câu lệnh sẽ ngầm trả về nil. Ta hiện thực điều đó bằng cách gọi emitReturn(), hàm này sẽ phát sinh instruction OP_NIL. Ngược lại, ta compile biểu thức giá trị trả về và trả nó bằng instruction OP_RETURN.

Đây chính là instruction OP_RETURN mà ta đã hiện thực — không cần thêm code runtime mới. Điều này khác khá nhiều so với jlox. Ở đó, ta phải dùng exception để “unwind” stack khi một câu lệnh return được execute. Lý do là bạn có thể return từ sâu bên trong các block lồng nhau. Vì jlox duyệt AST một cách đệ quy, điều đó có nghĩa là có hàng loạt lời gọi hàm Java cần phải thoát ra.

Bytecode compiler của chúng ta đã “làm phẳng” tất cả. Ta có đệ quy khi parse, nhưng ở runtime, vòng lặp dispatch bytecode của VM hoàn toàn phẳng. Không có đệ quy nào ở cấp C cả. Vậy nên việc return, ngay cả từ trong các block lồng nhau, cũng đơn giản như return từ cuối thân hàm.

Tuy nhiên, ta vẫn chưa hoàn toàn xong. Câu lệnh return mới này mang tới một lỗi compile mới cần quan tâm. Return hữu ích để thoát khỏi hàm, nhưng top-level của một chương trình Lox cũng là code dạng mệnh lệnh. Bạn không nên return từ đó.

return "What?!";

Chúng ta đã quy định rằng việc có câu lệnh return bên ngoài bất kỳ hàm nào là một lỗi compile, và ta hiện thực điều đó như sau:

static void returnStatement() {

  if (current->type == TYPE_SCRIPT) {
    error("Can't return from top-level code.");
  }

  if (match(TOKEN_SEMICOLON)) {

Đây là một trong những lý do ta thêm enum FunctionType vào compiler.

24 . 7Native Functions

VM của chúng ta đang ngày càng mạnh mẽ hơn. Giờ ta đã có function, lời gọi, tham số, giá trị trả về. Bạn có thể định nghĩa nhiều function khác nhau và cho chúng gọi lẫn nhau theo những cách thú vị. Nhưng, cuối cùng thì, chúng vẫn chưa thực sự làm được gì. Thứ duy nhất mà một chương trình Lox có thể làm cho người dùng thấy, bất kể nó phức tạp đến đâu, là in ra màn hình. Để bổ sung thêm khả năng, ta cần “mở” chúng cho người dùng sử dụng.

Một implementation ngôn ngữ lập trình “vươn ra” và chạm tới thế giới vật chất thông qua native function. Nếu bạn muốn viết chương trình kiểm tra thời gian, đọc input từ người dùng, hoặc truy cập hệ thống file, ta cần thêm các native function — có thể gọi từ Lox nhưng được hiện thực bằng C — để cung cấp các khả năng đó.

Về mặt ngôn ngữ, Lox khá đầy đủ — nó có closures, classes, inheritance, và nhiều thứ thú vị khác. Một lý do khiến nó vẫn mang cảm giác như một ngôn ngữ “đồ chơi” là vì nó gần như không có khả năng native nào. Ta có thể biến nó thành một ngôn ngữ “thực thụ” bằng cách thêm một danh sách dài các khả năng này.

Tuy nhiên, việc “cày” qua một đống thao tác hệ điều hành thực ra không mang lại nhiều giá trị học tập. Khi bạn đã thấy cách liên kết một đoạn code C với Lox, bạn sẽ hiểu nguyên lý. Nhưng bạn vẫn cần thấy một ví dụ, và ngay cả một native function duy nhất cũng đòi hỏi ta phải xây dựng toàn bộ cơ chế để kết nối Lox với C. Vậy nên ta sẽ đi qua quá trình đó và làm hết phần khó. Sau đó, khi xong, ta sẽ thêm một native function nhỏ xíu chỉ để chứng minh nó hoạt động.

Lý do ta cần cơ chế mới là vì, từ góc nhìn của implementation, native function khác với Lox function. Khi được gọi, chúng không push một CallFrame, vì không có bytecode nào để frame đó trỏ tới. Chúng không có chunk bytecode. Thay vào đó, chúng tham chiếu tới một đoạn code C native.

Trong clox, ta xử lý điều này bằng cách định nghĩa native function như một loại object hoàn toàn khác.

} ObjFunction;

typedef Value (*NativeFn)(int argCount, Value* args);

typedef struct {
  Obj obj;
  NativeFn function;
} ObjNative;

struct ObjString {

Cách biểu diễn này đơn giản hơn ObjFunction — chỉ gồm một Obj header và một con trỏ tới hàm C hiện thực hành vi native. Native function nhận số lượng đối số và một con trỏ tới đối số đầu tiên trên stack. Nó truy cập các đối số thông qua con trỏ đó. Khi xong, nó trả về giá trị kết quả.

Như thường lệ, một loại object mới sẽ đi kèm một số “phụ kiện”. Để tạo một ObjNative, ta khai báo một hàm giống như constructor.

ObjFunction* newFunction();

ObjNative* newNative(NativeFn function);

ObjString* takeString(char* chars, int length);

Ta hiện thực nó như sau:

ObjNative* newNative(NativeFn function) {
  ObjNative* native = ALLOCATE_OBJ(ObjNative, OBJ_NATIVE);
  native->function = function;
  return native;
}

Constructor nhận một con trỏ hàm C để “bọc” trong ObjNative. Nó thiết lập header của object và lưu hàm đó. Với header, ta cần một loại object mới.

typedef enum {
  OBJ_FUNCTION,

  OBJ_NATIVE,

  OBJ_STRING,
} ObjType;

VM cũng cần biết cách giải phóng một native function object.

    }

    case OBJ_NATIVE:
      FREE(ObjNative, object);
      break;

    case OBJ_STRING: {

Không có gì nhiều ở đây vì ObjNative không sở hữu thêm vùng nhớ nào khác. Khả năng khác mà mọi object Lox đều hỗ trợ là in ra.

      break;

    case OBJ_NATIVE:
      printf("<native fn>");
      break;

    case OBJ_STRING:

Để hỗ trợ dynamic typing, ta có một macro để kiểm tra xem một value có phải là native function hay không.

#define IS_FUNCTION(value)     isObjType(value, OBJ_FUNCTION)

#define IS_NATIVE(value)       isObjType(value, OBJ_NATIVE)

#define IS_STRING(value)       isObjType(value, OBJ_STRING)

Nếu macro đó trả về true, macro này sẽ trích xuất con trỏ hàm C từ một Value đại diện cho native function:

#define AS_FUNCTION(value)     ((ObjFunction*)AS_OBJ(value))

#define AS_NATIVE(value) \
    (((ObjNative*)AS_OBJ(value))->function)

#define AS_STRING(value)       ((ObjString*)AS_OBJ(value))

Tất cả những thứ “lỉnh kỉnh” này cho phép VM xử lý native function như bất kỳ object nào khác. Bạn có thể lưu chúng vào biến, truyền đi, thậm chí tổ chức tiệc sinh nhật cho chúng, v.v. Tất nhiên, thao tác mà ta thực sự quan tâm là gọi chúng — dùng một native function làm toán hạng bên trái trong một call expression.

Trong callValue(), ta thêm một nhánh xử lý kiểu mới.

      case OBJ_FUNCTION: 
        return call(AS_FUNCTION(callee), argCount);

      case OBJ_NATIVE: {
        NativeFn native = AS_NATIVE(callee);
        Value result = native(argCount, vm.stackTop - argCount);
        vm.stackTop -= argCount + 1;
        push(result);
        return true;
      }

      default:

Nếu object được gọi là native function, ta gọi hàm C đó ngay lập tức. Không cần đụng tới CallFrame hay gì cả. Ta chỉ việc chuyển quyền cho C, lấy kết quả, và đặt nó lại vào stack. Điều này khiến native function nhanh nhất có thể.

Với điều này, người dùng có thể gọi native function, nhưng hiện tại chưa có cái nào để gọi. Nếu không có thứ như foreign function interface, người dùng không thể tự định nghĩa native function. Đó là việc của chúng ta với tư cách là người hiện thực VM. Ta sẽ bắt đầu với một helper để định nghĩa một native function mới và “mở” nó cho chương trình Lox.

static void defineNative(const char* name, NativeFn function) {
  push(OBJ_VAL(copyString(name, (int)strlen(name))));
  push(OBJ_VAL(newNative(function)));
  tableSet(&vm.globals, AS_STRING(vm.stack[0]), vm.stack[1]);
  pop();
  pop();
}

Hàm này nhận một con trỏ tới hàm C và tên mà nó sẽ được biết tới trong Lox. Ta bọc hàm đó trong một ObjNative rồi lưu nó vào một biến global với tên đã cho.

Có lẽ bạn đang thắc mắc vì sao ta push và pop tên và hàm lên stack. Trông hơi kỳ đúng không? Đây là kiểu việc bạn phải để ý khi garbage collection xuất hiện. Cả copyString() và newNative() đều cấp phát bộ nhớ động. Điều đó có nghĩa là khi ta có GC, chúng có thể kích hoạt việc thu gom. Nếu điều đó xảy ra, ta cần đảm bảo bộ thu gom biết rằng ta vẫn chưa xong với tên và ObjFunction để nó không giải phóng chúng. Lưu chúng trên value stack sẽ đảm bảo điều đó.

Nghe có vẻ hơi buồn cười, nhưng sau tất cả đống công việc vừa rồi, chúng ta sẽ chỉ thêm đúng một native function nhỏ.

static Value clockNative(int argCount, Value* args) {
  return NUMBER_VAL((double)clock() / CLOCKS_PER_SEC);
}

Hàm này trả về thời gian đã trôi qua kể từ khi chương trình bắt đầu chạy, tính bằng giây. Nó rất tiện để benchmark các chương trình Lox. Trong Lox, ta sẽ đặt tên nó là clock().

  initTable(&vm.strings);

  defineNative("clock", clockNative);

}

Để dùng được hàm clock() của thư viện chuẩn C, module “vm” cần thêm một include.

#include <string.h>

#include <time.h>

#include "common.h"

Đó là khá nhiều nội dung để xử lý, nhưng chúng ta đã làm được! Hãy gõ đoạn này vào và thử chạy:

fun fib(n) {
  if (n < 2) return n;
  return fib(n - 2) + fib(n - 1);
}

var start = clock();
print fib(35);
print clock() - start;

Chúng ta có thể viết một hàm Fibonacci đệ quy cực kỳ kém hiệu quả. Thậm chí hay hơn, ta có thể đo được chính xác mức độ kém hiệu quả của nó. Tất nhiên, đây không phải là cách thông minh nhất để tính số Fibonacci. Nhưng nó là một cách tốt để “stress test” khả năng hỗ trợ lời gọi hàm của một implementation ngôn ngữ. Trên máy của tôi, chạy đoạn này trong clox nhanh hơn khoảng năm lần so với jlox. Đó là một cải thiện đáng kể.