跳到主要内容

第 10 章：函数（Functions）

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

无论计算机如何工作，它总有一个函数在调用另一个函数，直到没什么可调用为止。

Donald Knuth

原书插图：Lambda 谜题。

函数将代码命名、组合和复用；递归又让有限代码表达无界计算。本章把既有的表达式、语句、变量、控制流和词法作用域拼合起来，为 Lox 实现可调用值、原生 clock()、用户函数、参数、局部环境与返回语句。

10.1 函数调用（Function Calls）​

调用的优先级高于一元运算符，并且可以链式出现。被调用者（callee）不是函数名，而是任意求值为函数的高优先级表达式，例如 getCallback()()；调用可视作以 ( 开始的后缀运算符：

average(1, 2);
getCallback()();
unary -> ( "!" | "-" ) unary | call ;
call  -> primary ( "(" arguments? ")" )* ;
arguments -> expression ( "," expression )* ;

连续调用也支持 fn(1)(2)(3) 形式；在 ML 系语言中，这常对应柯里化（currying）：每层函数接受一个参数并返回下一个函数。零参数调用由 call 规则中可选的 arguments 处理。

AST 增加：

"Call : Expr callee, Token paren, List<Expr> arguments"

解析器先解析 primary，再在循环中消费任意多组调用括号：

private Expr call() {
  Expr expr = primary();

  while (true) {
    if (match(LEFT_PAREN)) {
      expr = finishCall(expr);
    } else {
      break;
    }
  }
  return expr;
}

private Expr finishCall(Expr callee) {
  List<Expr> arguments = new ArrayList<>();
  if (!check(RIGHT_PAREN)) {
    do {
      if (arguments.size() >= 255) {
        error(peek(), "Can't have more than 255 arguments.");
      }
      arguments.add(expression());
    } while (match(COMMA));
  }

  Token paren = consume(RIGHT_PAREN, "Expect ')' after arguments.");
  return new Expr.Call(callee, paren, arguments);
}

10.1.1 参数数量上限（Maximum Argument Counts）​

255 不是语言本质限制，而是为后续字节码实现保留的上限；在 Java 树遍历解释器中可以更多，但保持两个实现的语言一致更有价值。超过上限仅报告错误而不立刻抛出解析异常，仍会继续读取参数，以维持同步。

10.1.2 解释函数调用（Interpreting Function Calls）​

Lox 中函数是一等值，且未来类也可调用。定义统一接口：

package com.craftinginterpreters.lox;

import java.util.List;

interface LoxCallable {
  int arity();
  Object call(Interpreter interpreter, List<Object> arguments);
}

arity() 给出参数个数，call() 执行调用。解释调用时先求值被调用表达式，再从左到右求值参数：

@Override
public Object visitCallExpr(Expr.Call expr) {
  Object callee = evaluate(expr.callee);

  List<Object> arguments = new ArrayList<>();
  for (Expr argument : expr.arguments) {
    arguments.add(evaluate(argument));
  }

  if (!(callee instanceof LoxCallable)) {
    throw new RuntimeError(expr.paren,
        "Can only call functions and classes.");
  }

  LoxCallable function = (LoxCallable) callee;
  if (arguments.size() != function.arity()) {
    throw new RuntimeError(expr.paren, "Expected " +
        function.arity() + " arguments but got " + arguments.size() + ".");
  }

  return function.call(this, arguments);
}

10.1.3 调用类型错误（Call Type Errors）​

先检查可调用性。因为 Lox 动态类型，调用目标可能由运行时计算得到；把类型检查放在 call() 之前，也避免把普通数值或字符串误转为 LoxCallable。

例如，下面的代码会产生运行时错误：

"totally not a function"();

10.1.4 检查元数（Checking Arity）​

再检查元数（arity），即函数形参数量是否等于实参数量。这同样只能在运行时检查，因为调用目标与传入参数都可能动态产生。

fun add(a, b, c) {
  print a + b + c;
}

add(1, 2, 3, 4); // Too many.
add(1, 2);       // Too few.

10.2 原生函数（Native Functions）​

原书插图：从宿主语言视角看外来函数。

语言通常需要少量由宿主实现的基础能力。Lox 标准库从 clock() 开始，它返回 Unix 纪元以来的秒数：

Interpreter() {
  globals.define("clock", new LoxCallable() {
    @Override
    public int arity() { return 0; }

    @Override
    public Object call(Interpreter interpreter, List<Object> arguments) {
      return (double) System.currentTimeMillis() / 1000.0;
    }

    @Override
    public String toString() { return "<native fn>"; }
  });
}

解释器把环境字段改为持久的全局环境：

final Environment globals = new Environment();
private Environment environment = globals;

原生函数显示了语言实现的边界：Lox 代码通过统一 LoxCallable 接口调用它，而实现细节仍在 Java 中。

10.2.1 报时（Telling Time）​

clock() 是有意选择的极小原生接口：它足以写性能计时程序，又不会在本章过早引入完整标准库。原生函数定义在 globals 中，解释器切换局部块时也始终保留这份全局环境。

10.3 函数声明（Function Declarations）​

Lox 函数语法：

fun makeCounter() {
  print "counter";
}

文法：

declaration  -> funDecl | varDecl | statement ;
funDecl      -> "fun" function ;
function     -> IDENTIFIER "(" parameters? ")" block ;
parameters   -> IDENTIFIER ( "," IDENTIFIER )* ;

AST 增加：

"Function : Token name, List<Token> params, List<Stmt> body"

解析函数声明：

private Stmt function(String kind) {
  Token name = consume(IDENTIFIER, "Expect " + kind + " name.");
  consume(LEFT_PAREN, "Expect '(' after " + kind + " name.");
  List<Token> parameters = new ArrayList<>();

  if (!check(RIGHT_PAREN)) {
    do {
      if (parameters.size() >= 255) {
        error(peek(), "Can't have more than 255 parameters.");
      }
      parameters.add(consume(IDENTIFIER, "Expect parameter name."));
    } while (match(COMMA));
  }

  consume(RIGHT_PAREN, "Expect ')' after parameters.");
  consume(LEFT_BRACE, "Expect '{' before " + kind + " body.");
  List<Stmt> body = block();
  return new Stmt.Function(name, parameters, body);
}

private Stmt declaration() {
  try {
    if (match(FUN)) return function("function");
    if (match(VAR)) return varDeclaration();
    return statement();
  } catch (ParseError error) {
    synchronize();
    return null;
  }
}

函数体复用已有块解析；function(String kind) 这个通用函数也会在以后解析方法时复用。参数和实参同样限制为 255 个，为的是与 clox 一致；函数名、参数列表和函数体的花括号都由 consume() 精确诊断。

10.4 函数对象（Function Objects）​

函数声明在 AST 中只是语法。执行到它时，需要创建可调用运行时对象。LoxFunction 保存声明：

package com.craftinginterpreters.lox;

import java.util.List;

class LoxFunction implements LoxCallable {
  private final Stmt.Function declaration;
  private final Environment closure;

  LoxFunction(Stmt.Function declaration, Environment closure) {
    this.declaration = declaration;
    this.closure = closure;
  }

  @Override
  public int arity() {
    return declaration.params.size();
  }

  @Override
  public Object call(Interpreter interpreter, List<Object> arguments) {
    Environment environment = new Environment(closure);
    for (int i = 0; i < declaration.params.size(); i++) {
      environment.define(declaration.params.get(i).lexeme, arguments.get(i));
    }

    interpreter.executeBlock(declaration.body, environment);
    return null;
  }

  @Override
  public String toString() {
    return "<fn " + declaration.name.lexeme + ">";
  }
}

函数调用创建新环境，把实参绑定到形参，再在其中执行函数体。每次调用都创建独立环境，因此递归和重入可正确工作。toString() 以 <fn name> 显示用户函数，便于 REPL 和诊断展示。

原书插图：递归调用各自拥有独立环境。

原书插图：实参与形参的绑定。

10.4.1 解释函数声明（Interpreting Function Declarations）​

声明语句执行时创建对象并把它绑定到当前环境：

@Override
public Void visitFunctionStmt(Stmt.Function stmt) {
  LoxFunction function = new LoxFunction(stmt, environment);
  environment.define(stmt.name.lexeme, function);
  return null;
}

目前函数对象还不能正确保留局部声明环境；本节先把声明绑定到当前环境。下一节加入捕获环境，使局部函数在离开定义块后仍能读取所捕获的变量，这就是闭包的基本机制。第 11 章会加入静态解析，使解释器能在嵌套作用域中精确、高效地定位这些变量。

函数是普通一等值，既能递归调用，也能像其他值那样打印：

fun count(n) {
  if (n > 1) count(n - 1);
  print n;
}

count(3);
fun add(a, b) {
  print a + b;
}

print add; // "<fn add>".

10.5 return 语句（Return Statements）​

函数默认返回 nil；return 可提前退出并携带值：

fun add(a, b) {
  return a + b;
}

没有显式 return 的函数结果为 nil，等价于执行 return nil;：

fun procedure() {
  print "don't return anything";
}

var result = procedure();
print result; // nil.

语法与 AST：

statement -> "return" expression? ";" | ... ;
"Return : Token keyword, Expr value"
private Stmt returnStatement() {
  Token keyword = previous();
  Expr value = null;
  if (!check(SEMICOLON)) value = expression();
  consume(SEMICOLON, "Expect ';' after return value.");
  return new Stmt.Return(keyword, value);
}

return 必须跳出任意深度的块与语句执行，不适合把信号逐层作为普通返回值传递。解析时，分号不能开始表达式，因此通过“下一个记号是否为分号”判断返回值是否缺省。使用轻量异常完成非局部控制流：

class Return extends RuntimeException {
  final Object value;

  Return(Object value) {
    super(null, null, false, false);
    this.value = value;
  }
}

解释 return 时抛出它：

@Override
public Void visitReturnStmt(Stmt.Return stmt) {
  Object value = null;
  if (stmt.value != null) value = evaluate(stmt.value);
  throw new Return(value);
}

LoxFunction.call() 捕获异常，转换为函数调用结果：

try {
  interpreter.executeBlock(declaration.body, environment);
} catch (Return returnValue) {
  return returnValue.value;
}
return null;

禁用异常栈追踪使它成为高效的控制流工具，而不是需要给用户显示的错误。在递归的树遍历解释器里，异常能直接展开 Java 调用栈；这并非一般业务代码中推荐的控制流手法，却很适合这里。

return 会越过中间的 if、循环和块，直接到达当前函数调用的边界：

fun count(n) {
  while (n < 100) {
    if (n == 3) return n;
    print n;
    n = n + 1;
  }
}

count(1);

10.6 局部函数与闭包（Local Functions and Closures）​

函数声明属于 declaration，不是仅限顶层的构造，因此允许写在任意块中：

{
  fun local() {
    print "I'm local.";
  }
  local();
}

函数对象会记住其声明时环境，而非仅知道全局环境。因此从函数返回局部函数仍可保留对外围变量的访问；这就是闭包。闭包一词同样由 Peter J. Landin 提出，意为函数“闭合”并保留其声明位置周围的变量。第 11 章会用解析器精确记录变量绑定位置，避免在运行时反复沿环境链搜索，并修补当前实现中残留的一点动态作用域漏洞。

递归斐波那契是调用性能的常见微基准：

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

for (var i = 0; i < 20; i = i + 1) {
  print fib(i);
}

闭包的典型形态是返回一个捕获局部变量的函数：

fun makeCounter() {
  var i = 0;
  fun count() {
    i = i + 1;
    print i;
  }

  return count;
}

var counter = makeCounter();
counter(); // "1".
counter(); // "2".

原书插图：count() 函数体到全局作用域的环境链。

原书插图：makeCounter() 函数体内的环境链。

原书插图：闭包捕获环境后的链。

挑战（Challenges）​

  1. Lox 在每次调用时检查实参与形参数量，Smalltalk 实现为何没有这项运行时成本？
  2. 为 Lox 加入匿名函数（lambda）表达式，使 thrice(fun (a) { print a; }); 可用；并处理匿名函数作为表达式语句时的歧义，如 fun () {};。
  3. 函数形参和函数体中的局部变量属于同一个作用域还是内外两层作用域？Lox 当前如何处理？与其他语言比较，并说明你认为应采用什么语义。