Skip to main content

第 24 章：调用与函数（Calls and Functions）

原文：Robert Nystrom, Crafting Interpreters, Chapter 24。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。

计算机科学中的任何问题，都能通过再加一层间接性解决。除了间接层次过多的问题。

David Wheeler

本章是个大家伙。函数声明不能调用就没什么用；调用没有可调用对象也不行；仅完成 VM 支持又看不到成果。因此本章一次完成函数对象、函数声明、调用、参数、返回和原生函数。

24.1 函数对象（Function Objects）​

VM 已有保存局部变量与临时值的值栈，却没有调用栈。先从函数表示开始。函数有可执行主体，即字节码；可以把全程序编为一个大 Chunk，再令每个函数指向其中的首指令，类似原生机器码。但字节码 VM 采用更干净的模型：每个函数拥有自己的 Chunk 和元数据：

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

函数是一等 Lox 值，因此包含所有对象共有的 Obj 头。arity 是期望参数数，name 用于可读的运行时错误。object.h 首次依赖 Chunk，需 #include "chunk.h"。构造函数先建立空白对象，随后编译期填充：

ObjFunction* newFunction();

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

为此增加 OBJ_FUNCTION 类型，在 freeObject() 中释放函数拥有的 chunk 后释放对象本身；函数名是 ObjString，由 GC 管理。打印函数时显示其名称，脚本函数没有名称则显示 <script>：

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

#define IS_FUNCTION(value) isObjType(value, OBJ_FUNCTION)
#define AS_FUNCTION(value) ((ObjFunction*)AS_OBJ(value))

24.2 编译为函数对象（Compiling to Function Objects）​

过去编译器始终写入一个 chunk；现在遇到函数声明时，函数体应写入新函数的 chunk，结束后还要回到外层 chunk。顶层脚本也需要放代码，最简单的方式是把它同样放入自动定义的函数：编译器永远在函数体内，VM 永远通过调用函数运行代码，如同整个脚本被隐式 main() 包裹。唯一不同是全局变量的作用域规则。

Compiler 不再直接指向 chunk，而是保存正在构建的函数及其类别：

typedef enum {
  TYPE_FUNCTION,
  TYPE_SCRIPT
} FunctionType;

typedef struct Compiler {
  ObjFunction* function;
  FunctionType type;
  Local locals[UINT8_COUNT];
  int localCount;
  int scopeDepth;
} Compiler;

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

此前把访问 chunk 封装在 currentChunk() 中，如今只改这一处。compile() 初始化一个 TYPE_SCRIPT 编译器，并返回 ObjFunction*；编译失败返回 NULL，防止 VM 执行不完整字节码：

ObjFunction* compile(const char* source) {
  initScanner(source);
  Compiler compiler;
  initCompiler(&compiler, TYPE_SCRIPT);
  /* parse declarations */
  ObjFunction* function = endCompiler();
  return parser.hadError ? NULL : function;
}

24.2.1 编译期创建函数（Creating functions at compile time）​

initCompiler() 分配函数对象，顶层脚本与用户函数都从这里开始。编译期创建运行时对象并不奇怪：函数如字符串和数字字面量一样，连接编译期和运行期；代码、名称、参数数在编译期已固定。闭包捕获运行期变量后，情况会在下一章复杂化。

static void initCompiler(Compiler* compiler, FunctionType type) {
  compiler->function = NULL;
  compiler->type = type;
  compiler->localCount = 0;
  compiler->scopeDepth = 0;
  current = compiler;
  current->function = newFunction();

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

先写 NULL 再分配是为未来 GC 留出的谨慎步骤。编译器隐式占用局部槽位零，并赋予空名字，用户无法引用它；它稍后用于方法接收者。endCompiler() 发出隐式返回、取回函数并用于调试反汇编：

static ObjFunction* endCompiler() {
  emitReturn();
  ObjFunction* function = current->function;
#ifdef DEBUG_PRINT_CODE
  if (!parser.hadError) {
    disassembleChunk(currentChunk(),
      function->name != NULL ? function->name->chars : "<script>");
  }
#endif
  return function;
}

24.3 调用帧（Call Frames）​

函数调用带来两个问题：局部变量如何在多函数间分配，以及函数结束后回到哪里。每个函数永久独占一组槽位类似早期 Fortran 的静态分配，既浪费内存又无法支持递归；jlox 每次调用动态分配环境则太慢。

值栈仍然适用：即使跨调用，后声明的局部变量总会先被丢弃。例如 first() 有 a，调用 second() 后再有 b；second() 的 c、d 总会在 a 之前消失。

执行嵌套调用时局部变量在栈上的变化。

但函数是一等值，编译期无法知道它从哪一个上下文被调用。同一 second() 第一次可从槽位 1 开始，第二次却可能因 b 已存在而从槽位 2 开始。关键在于：绝对栈位置未知，函数内部相对位置恒定。每次调用记录本函数首个槽位，字节码的槽位操作数相对于此基址；运行时将相对槽加到该调用的起始位置。这就是调用帧（frame），其起始指针也称 frame pointer 或 base pointer。

同一函数在不同调用点拥有不同的栈窗口。

24.3.1 分配局部变量（Allocating local variables）​

函数结束时还需回到调用者 OP_CALL 后的指令，即返回地址。递归意味着同一函数可同时有多个返回地址，故它属于调用而不是函数。

24.3.2 返回地址（Return addresses）​

早期不支持递归的 Fortran 曾通过运行时修改函数末尾跳转指令来保存函数的唯一返回地址，颇有天才与疯狂一线之隔的味道。

24.3.3 调用栈（The call stack）​

每个未返回调用要记录局部变量基址和恢复位置，故定义：

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

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

typedef struct {
  CallFrame frames[FRAMES_MAX];
  int frameCount;
  Value stack[STACK_MAX];
  Value* stackTop;
  /* globals, strings, objects */
} VM;

slots 指向值栈中函数可用的第一个槽，并被当作数组。返回地址不放在被调者帧内：调用者保留自己的 ip，返回时继续使用它。调用帧也保存函数指针，以读取 chunk 和常量。

调用帧同样具栈语义，预先分配固定数组比逐次堆分配快；代价是调用深度上限。resetStack() 还要设 vm.frameCount = 0。原有 VM 的 chunk 与 ip 字段被删除，当前帧各自持有它们。

run() 缓存顶部帧指针，既简化代码，也让 C 编译器有机会放入寄存器：

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()])

局部变量和跳转均改为当前帧相对访问：

case OP_GET_LOCAL: {
  uint8_t slot = READ_BYTE();
  push(frame->slots[slot]);
  break;
}
case OP_SET_LOCAL: {
  uint8_t slot = READ_BYTE();
  frame->slots[slot] = peek(0);
  break;
}
case OP_JUMP: frame->ip += READ_SHORT(); break;
case OP_LOOP: frame->ip -= READ_SHORT(); break;

顶层代码也作为函数启动：编译得到函数，压栈（槽位零），创建第一个帧，ip 指向 chunk 首指令、slots 指向 vm.stack。运行时错误则从当前帧计算 ip - code - 1 所对应的行号。

24.4 函数声明（Function Declarations）​

在调用表达式之前，先让 fun 声明产生可调用对象：

static void declaration() {
  if (match(TOKEN_FUN)) {
    funDeclaration();
  } else if (match(TOKEN_VAR)) {
    varDeclaration();
  } else {
    statement();
  }
}

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

函数是一等值，声明本质是在新变量中创建并保存函数；顶层绑定全局，块或其他函数内则绑定局部。变量通常在初始化器结束后才定义，防止初始化器读到未初始化值；函数却可以在自己的函数体中引用自身，因为调用只有定义完成后才会发生。这使局部递归函数可行，因此函数名解析后立即 markInitialized()。该函数要在全局作用域直接返回，因为那里没有局部条目。

function() 编译参数和主体，并将最终 ObjFunction 作为外层函数的常量压栈：

static void function(FunctionType type) {
  Compiler compiler;
  initCompiler(&compiler, type);
  beginScope();
  consume(TOKEN_LEFT_PAREN, "Expect '(' after function name.");
  /* parameters */
  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)));
}

最外层函数作用域不需 endScope()，因为整个 Compiler 已结束。

24.4.1 编译器栈（A stack of compilers）​

每个被编译函数需要独立的局部变量、作用域深度和 chunk；顶层本就视为隐式函数，所以函数声明形成嵌套编译器。新 Compiler 在 C 栈上创建并成为 current，其函数体发出的字节码写入新 chunk；结束时要恢复外层编译器。通过链表实现编译器栈：

typedef struct Compiler {
  struct Compiler* enclosing;
  ObjFunction* function;
  FunctionType type;
  Local locals[UINT8_COUNT];
  int localCount;
  int scopeDepth;
} Compiler;

static void initCompiler(Compiler* compiler, FunctionType type) {
  compiler->enclosing = current;
  /* initialize and set current */
}

static ObjFunction* endCompiler() {
  emitReturn();
  ObjFunction* function = current->function;
  current = current->enclosing;
  return function;
}

结构体定义尚未完成时 C 不能用 typedef 名称引用自身，故字段写作 struct Compiler*。编译器节点无需堆分配，递归下降解析自然把它们串在 C 调用栈上；不过恶意或极深嵌套函数仍可能耗尽 C 栈，健壮编译器应限制嵌套深度。

24.4.2 函数参数（Function parameters）​

参数就是函数最外层词法作用域内的局部变量。复用现有声明逻辑来解析，同时计数 arity；参数没有初始化器，调用时实参会直接落入对应槽位：

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

initCompiler() 紧随函数名之后运行，所以可从 parser.previous 拷贝函数名。必须复制：token 词素指向编译后可释放的源文本，函数对象却活到运行时。

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

现在可以声明甚至打印函数，但尚未能调用。

24.5 函数调用（Function Calls）​

调用表达式可视为中缀左括号：左边高优先级表达式是 callee，括号内是逗号分隔实参。故解析表将 ( 同时作为分组前缀和调用中缀：

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

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

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

每个实参表达式将值留在栈上，OP_CALL 的一字节操作数存实参数，因此最多 255 个。新增 opcode 后开始解释调用。

24.5.1 绑定实参与形参（Binding arguments to parameters）​

对于：

fun sum(a, b, c) { return a + b + c; }
print 4 + sum(5, 6, 7);

执行 OP_CALL 时，栈为函数值和顺序实参：

调用 sum(5, 6, 7) 时的栈。

sum 编译期保留槽位零，再为 a、b、c 分配槽位一、二、三。只需让被调帧窗口从 callee 的槽位开始，实参便自然对齐形参，无需复制：

被调帧窗口中的参数槽与实参对齐。

调用者和被调者窗口可以重叠：

顶层帧与 sum() 帧重叠的栈窗口。

不同 VM/CPU 的调用约定各异；本书方案受 Lua 快速 VM 启发。OP_CALL 由实参数量定位栈顶之下的 callee，成功调用后刷新 run() 的缓存帧：

case OP_CALL: {
  int argCount = READ_BYTE();
  if (!callValue(peek(argCount), argCount)) {
    return INTERPRET_RUNTIME_ERROR;
  }
  frame = &vm.frames[vm.frameCount - 1];
  break;
}

动态语言需拒绝调用数字等不可调用值。callValue() 预留 switch 以容纳将来的类、闭包等可调用对象：

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;
    }
  }
  runtimeError("Can only call functions and classes.");
  return false;
}

call() 验证 arity 和帧容量，再初始化下一帧。-1 计入预留的槽位零，使实参从槽位一开始与形参一致：

static bool call(ObjFunction* function, int argCount) {
  if (argCount != function->arity) {
    runtimeError("Expected %d arguments but got %d.",
                 function->arity, argCount);
    return false;
  }
  if (vm.frameCount == FRAMES_MAX) {
    runtimeError("Stack overflow.");
    return false;
  }
  CallFrame* frame = &vm.frames[vm.frameCount++];
  frame->function = function;
  frame->ip = function->chunk.code;
  frame->slots = vm.stackTop - argCount - 1;
  return true;
}

由 stackTop 与 argCount 计算帧基址。

反汇编器将 OP_CALL 作为一字节操作数指令显示；顶层 interpret() 也改为 push(OBJ_VAL(function)); call(function, 0); return run();。

24.5.2 运行时错误检查（Runtime error checking）​

固定帧数组要求检查栈溢出；arity 元数据检查实参数量。两者都应经 runtimeError() 返回 false，让解释循环以运行时错误退出。

24.5.3 打印栈踪迹（Printing stack traces）​

中止程序能避免 VM 进入未定义状态，却不帮助用户定位问题。调用栈与函数名已经存在，因此运行时错误可从最新帧到脚本帧打印 Lox 级栈踪迹。ip 已指向下一指令，故用 -1 找失败指令：

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

多数语言把最内层、错误实际发生处放在第一行；Python 采用相反顺序，强调“如何到达这里”。例如 a() 调 b() 调 c()，而 c("too", "many") 参数错误时，会依次显示 c()、b()、a() 和 script。

24.5.4 从函数返回（Returning from functions）​

真实的 OP_RETURN 先保存栈顶结果，丢弃当前帧；若这是脚本帧则结束解释，否则把栈顶重置到被调帧窗口起点，压回结果，恢复调用者帧。调用者下一轮从其已保存的 ip 执行，即紧接 OP_CALL 后：

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

返回：保存结果、丢弃帧窗口、在调用者栈压回结果。

函数走到末尾时按语言定义隐式返回 nil，故编译器的 emitReturn() 变为：

static void emitReturn() {
  emitByte(OP_NIL);
  emitByte(OP_RETURN);
}

24.6 return 语句（Return Statements）​

显式 return 可带值，也可只带分号而返回 nil：

static void returnStatement() {
  if (current->type == TYPE_SCRIPT) {
    error("Can't return from top-level code.");
  }
  if (match(TOKEN_SEMICOLON)) {
    emitReturn();
  } else {
    expression();
    consume(TOKEN_SEMICOLON, "Expect ';' after return value.");
    emitByte(OP_RETURN);
  }
}

它复用已有运行时 OP_RETURN。jlox 需要异常穿过递归 AST 访问以退出深层块；字节码编译已把结构摊平，运行时只有扁平分派循环，从任意嵌套块返回与从函数末尾返回一样直接。顶层 return 被规定为编译错误，FunctionType 正是为此区分脚本与函数。

24.7 原生函数（Native Functions）​

现在 Lox 能写复杂函数，却只能打印。语言实现通过原生函数接触时间、输入、文件系统等物质世界：它们能从 Lox 调用，但在 C 中实现。原生调用没有字节码 chunk，不应推入 CallFrame，故使用另一种对象类型：

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

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

原生函数接受实参数与栈中第一个实参的指针，返回一个 Value。增加 OBJ_NATIVE、newNative()、释放逻辑、打印 <native fn> 和转换宏：

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

#define IS_NATIVE(value) isObjType(value, OBJ_NATIVE)
#define AS_NATIVE(value) (((ObjNative*)AS_OBJ(value))->function)

调用原生对象时直接进入 C，得到结果后去掉 callee 与实参并压回结果，因而非常快：

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

VM 实现者用 defineNative() 把 C 函数包装为对象并写进全局表。分配名称和对象时临时压栈，是为未来 GC 触发分配时仍把它们作为根保活：

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

只添加一个原生函数 clock()，返回进程开始以来的秒数，适合基准测试：

#include <time.h>

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

void initVM() {
  /* tables ... */
  defineNative("clock", clockNative);
}

现在可运行递归 Fibonacci 并计时：

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

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

这不是高效 Fibonacci，却很适合压测调用。作者机器上 clox 比 jlox 快约五倍，略慢于 Ruby 2.4.3，并比 Python 3.7 快约三倍，VM 尚有许多简单优化空间。

挑战（Challenges）​

  1. ip 是字节码循环最频繁访问的数据之一。尝试将它存入标为 register 的 C 局部变量，以鼓励编译器放进 CPU 寄存器；在调用和返回时正确同步回帧，并用基准评估复杂度是否值得。
  2. 原生调用快的部分原因是未检查原生函数的实参数；不足参数可能读到未初始化内存。增加原生函数 arity 检查。
  3. 当前原生函数无法报告运行时错误。扩展系统，使 sqrt() 收到字符串等情况能安全报错，并分析这对原生调用性能的影响。
  4. 增加你觉得实用的原生函数，写程序使用它们，并分析它们怎样改变语言的实用性与使用感受。