函数

这就是人脑的工作方式—将旧观念组合成新的结构，这些结构会变成新的观念，然后这些新观念又可以用来组合，周而复始，永不停歇，越来越远离每种语言的基础、实质性的图像，这些图像就是语言的土壤。

道格拉斯·霍夫施塔特，我是一个奇怪的循环

本章标志着大量艰苦工作的顶峰。前面的章节虽然各自添加了有用的功能，但每一章也为一个拼图提供了拼图块。我们将把这些拼图块—表达式、语句、变量、控制流和词法作用域—添加几个，并将它们全部组合起来以支持真正的用户定义函数和函数调用。

10 . 1函数调用

你肯定熟悉 C 语言风格的函数调用语法，但语法比你意识到的更微妙。调用通常是针对像这样的命名函数：

average(1, 2);

但是，被调用的函数的名称实际上不是调用语法的组成部分。被调用的东西—被调用方—可以是任何计算结果为函数的表达式。（当然，它必须是一个优先级很高的表达式，但括号可以处理这一点。）例如

getCallback()();

这里有两个调用表达式。第一个括号对的被调用方是 getCallback。但第二个调用的被调用方是整个 getCallback() 表达式。紧跟表达式后的括号表示函数调用。你可以将调用视为一种后缀运算符，从 ( 开始。

这个“运算符”的优先级高于任何其他运算符，甚至包括一元运算符。因此，我们通过让 unary 规则冒泡到新的 call 规则中来将其插入语法中。

unary          → ( "!" | "-" ) unary | call ;
call           → primary ( "(" arguments? ")" )* ;

此规则匹配一个主表达式，后面跟着零个或多个函数调用。如果没有括号，则解析一个裸主表达式。否则，每个调用都由一对括号识别，括号内包含一个可选的参数列表。参数列表语法是

arguments      → expression ( "," expression )* ;

此规则要求至少有一个参数表达式，后面跟着零个或多个其他表达式，每个表达式前面都带有逗号。为了处理零参数调用，call 规则本身认为整个 arguments 产生式是可选的。

我承认，这似乎比你对非常常见的“零个或多个逗号分隔的项目”模式的期望更语法上的尴尬。有一些更复杂的元语法可以更好地处理这个问题，但在我们的 BNF 和我见过的许多语言规范中，它就是如此笨拙。

在我们的语法树生成器中，我们添加一个新节点.

      "Binary   : Expr left, Token operator, Expr right",

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

      "Grouping : Expr expression",

它存储被调用方表达式和参数表达式的列表。它还存储了闭合括号的标记。当我们报告由函数调用引起的运行时错误时，我们将使用该标记的位置。

打开解析器。unary() 以前直接跳到 primary()，更改它以调用，嗯，call()。

      return new Expr.Unary(operator, right);
    }

    return call();

  }

它的定义是

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

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

    return expr;
  }

这里的代码与语法规则并不完全一致。为了使代码更简洁，我移动了一些东西—这是我们使用手工解析器时的优势之一。但它与我们解析中缀运算符的方式大体相似。首先，我们解析一个主表达式，它是调用的“左操作数”。然后，每次遇到 ( 时，我们调用 finishCall() 使用先前解析的表达式作为被调用方来解析调用表达式。返回的表达式将成为新的 expr，我们循环查看结果是否被调用。

解析参数列表的代码在以下辅助函数中

  private Expr finishCall(Expr callee) {
    List<Expr> arguments = new ArrayList<>();
    if (!check(RIGHT_PAREN)) {
      do {
        arguments.add(expression());
      } while (match(COMMA));
    }

    Token paren = consume(RIGHT_PAREN,
                          "Expect ')' after arguments.");

    return new Expr.Call(callee, paren, arguments);
  }

这或多或少是 arguments 语法规则翻译成代码，除了我们还处理零参数情况。我们首先检查下一个标记是否为 )。如果是，我们不会尝试解析任何参数。

否则，我们解析一个表达式，然后查找指示在该表达式后还有另一个参数的逗号。只要在每个表达式后找到逗号，我们就一直这样做。当我们没有找到逗号时，说明参数列表必须已完成，并且我们消耗预期的闭合括号。最后，我们将被调用方和这些参数包装成一个调用 AST 节点。

10 . 1 . 1最大参数计数

现在，解析参数的循环没有界限。如果你想调用一个函数并传递一百万个参数，解析器不会有任何问题。我们是否要限制这一点呢？

其他语言有不同的方法。C 标准规定，一个符合标准的实现必须至少支持 127 个函数参数，但没有规定上限。Java 规范规定，一个方法最多可以接受 255 个参数。

我们用于 Lox 的 Java 解释器并不真正需要一个限制，但拥有一个最大参数数量将简化我们在 第三部分 中的字节码解释器。我们希望我们的两个解释器相互兼容，即使是在像这样奇怪的边缘情况下，所以我们将在 jlox 中添加相同的限制。

      do {

        if (arguments.size() >= 255) {
          error(peek(), "Can't have more than 255 arguments.");
        }

        arguments.add(expression());

注意，这里的代码在遇到太多参数时会报告错误，但不会抛出错误。抛出错误是我们在解析器处于混淆状态且不知道它在语法中的位置时想要执行的操作。但在这里，解析器仍然处于完全有效的状态—它只是发现了太多参数。因此，它报告错误并继续执行。

10 . 1 . 2解释函数调用

我们没有可以调用的函数，所以先开始实现调用似乎很奇怪，但我们会在需要的时候再考虑。首先，我们的解释器需要一个新的导入。

import java.util.ArrayList;

import java.util.List;

像往常一样，解释从为我们的新调用表达式节点添加一个新的访问方法开始。

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

    LoxCallable function = (LoxCallable)callee;
    return function.call(this, arguments);
  }

首先，我们评估被调用方的表达式。通常，这个表达式只是一个标识符，它根据名称查找函数，但它可以是任何东西。然后，我们按顺序评估每个参数表达式，并将结果值存储在一个列表中。

一旦我们准备好了被调用方和参数，剩下的就是执行调用。我们通过将被调用方强制转换为 LoxCallable，然后调用它的 call() 方法来实现这一点。任何可以像函数一样调用的 Lox 对象的 Java 表示形式都将实现此接口。这自然包括用户定义的函数，但也包括类对象，因为类被“调用”以构造新的实例。我们很快也会将其用于另一个目的。

这个新接口并没有太多内容。

package com.craftinginterpreters.lox;

import java.util.List;

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

我们将解释器传入，以防实现 call() 的类需要它。我们还提供给它评估后的参数值的列表。然后，实现者的工作就是返回调用表达式产生的值。

10 . 1 . 3调用类型错误

在我们开始实现 LoxCallable 之前，我们需要使访问方法更健壮。它目前忽略了我们无法假装不会发生的几种错误模式。首先，如果被调用方实际上不是可以调用的东西会发生什么？如果你尝试这样做

"totally not a function"();

字符串在 Lox 中不可调用。Lox 字符串的运行时表示形式是 Java 字符串，所以当我们将它强制转换为 LoxCallable 时，JVM 会抛出 ClassCastException。我们不希望我们的解释器吐出一些令人讨厌的 Java 堆栈跟踪并崩溃。相反，我们需要先自己检查类型。

    }

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

    LoxCallable function = (LoxCallable)callee;

我们仍然抛出异常，但现在我们抛出我们自己的异常类型，解释器知道如何捕获并优雅地报告这种异常。

10 . 1 . 4检查元数

另一个问题与函数的元数有关。元数是用来描述函数或运算符期望的参数数量的专业术语。一元运算符的元数为一，二元运算符的元数为二，等等。对于函数，元数由它声明的参数数量决定。

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

此函数定义了三个参数，a、b 和 c，所以它的元数为三，它期望三个参数。那么，如果你尝试像这样调用它会发生什么

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

不同语言对这个问题采取了不同的方法。当然，大多数静态类型语言在编译时检查这一点，如果参数数量与函数的元数不匹配，则拒绝编译代码。JavaScript 会丢弃你传递的任何额外参数。如果你没有传递足够的参数，它会用魔法值`undefined`（类似于 null 但不完全是）填充缺少的参数。Python 更严格。如果参数列表过短或过长，它会引发运行时错误。

我认为后一种方法更好。传递错误数量的参数几乎总是错误，这正是我在实践中会犯的错误。鉴于此，实现越早提醒我，越好。因此，对于 Lox，我们将采用 Python 的方法。在调用可调用对象之前，我们将检查参数列表的长度是否与可调用对象的元数匹配。

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

这需要在 LoxCallable 接口上添加一个新方法来询问它的元数。

interface LoxCallable {

  int arity();

  Object call(Interpreter interpreter, List<Object> arguments);

我们可以将元数检查推到`call()` 的具体实现中。但是，由于我们将有多个类实现 LoxCallable，这将导致冗余验证分散在几个类中。将其提升到访问方法中让我们在一个地方完成它。

10 . 2原生函数

从理论上讲，我们可以调用函数，但我们还没有函数可以调用。在我们开始使用用户定义的函数之前，现在是时候介绍一个语言实现的重要但常被忽视的方面了———原生函数。这些函数是解释器向用户代码公开的，但它们是在宿主语言（在本例中为 Java）中实现的，而不是在被实现的语言（Lox）中实现的。

有时这些函数被称为基本函数、外部函数或外部函数。由于这些函数可以在用户程序运行时调用，因此它们构成了实现运行时的一部分。许多编程语言书籍都会略过这些函数，因为它们在概念上并不有趣。它们大多是苦力活。

但是，当谈到让你的语言真正擅长做有用的事情时，你的实现提供的原生函数是关键。它们提供了对所有程序都定义的那些基本服务的访问权限。如果你不提供原生函数来访问文件系统，用户将很难编写一个读取并显示文件的程序。

许多语言也允许用户提供自己的原生函数。实现此功能的机制称为外部函数接口（FFI）、原生扩展、原生接口或类似的名称。这些函数很好，因为它们解放了语言实现者，无需提供对底层平台支持的每个功能的访问权限。我们不会为 jlox 定义 FFI，但我们会添加一个原生函数来让你了解它的样子。

10 . 2 . 1计时

当我们进入第三部分并开始研究 Lox 的更高效的实现时，我们将非常关注性能。性能工作需要测量，而测量则意味着基准测试。这些程序用于测量执行解释器某个部分所需的时间。

我们可以测量启动解释器、运行基准测试并退出所需的时间，但这会增加很多开销——JVM 启动时间、操作系统奇淫怪事等等。当然，这些东西很重要，但如果你只是想验证解释器某一部分的优化，你就不希望这些开销掩盖你的结果。

更好的解决方案是让基准测试脚本本身测量代码中两点之间经过的时间。为此，Lox 程序需要能够计时。现在没有办法做到这一点——你无法“从头开始”实现一个有用的时钟，而无需访问计算机上的底层时钟。

因此，我们将添加`clock()`，这是一个原生函数，它返回自某个固定时间点开始经过的秒数。两次连续调用之间的差异告诉你两次调用之间经过的时间。此函数定义在全局作用域中，因此让我们确保解释器可以访问它。

class Interpreter implements Expr.Visitor<Object>,
                             Stmt.Visitor<Void> {

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

  void interpret(List<Stmt> statements) {

解释器中的`environment` 字段在进入和退出局部作用域时会发生变化。它跟踪当前环境。这个新的`globals` 字段保存对最外部全局环境的固定引用。

当我们实例化一个解释器时，我们将原生函数塞到那个全局作用域中。

  private Environment environment = globals;

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

  void interpret(List<Stmt> statements) {

这定义了一个名为“clock”的变量。它的值是一个 Java 匿名类，它实现了 LoxCallable。`clock()` 函数不接受任何参数，因此它的元数为零。`call()` 的实现调用相应的 Java 函数，并将结果转换为以秒为单位的双精度值。

如果我们想添加其他原生函数——从用户那里读取输入、处理文件等等——我们可以将它们分别添加为实现 LoxCallable 的自己的匿名类。但对于本书来说，这一个就足够了。

让我们摆脱函数定义的业务，让我们的用户接管 . . . 

10 . 3函数声明

我们终于可以向我们添加变量时引入的`declaration` 规则添加新的产生式了。函数声明与变量一样，绑定一个新的名称。这意味着它们只允许出现在允许声明的地方。

declaration    → funDecl
               | varDecl
               | statement ;

更新的`declaration` 规则引用了这个新规则

funDecl        → "fun" function ;
function       → IDENTIFIER "(" parameters? ")" block ;

主要的`funDecl` 规则使用单独的辅助规则`function`。函数声明语句是`fun` 关键字后跟实际的函数部分。当我们开始使用类时，我们将重新使用该`function` 规则来声明方法。这些方法看起来与函数声明类似，但没有以fun 开头。

函数本身是名称后跟带括号的参数列表和函数体。函数体始终是一个带大括号的块，使用与块语句相同的语法规则。参数列表使用此规则

parameters     → IDENTIFIER ( "," IDENTIFIER )* ;

它与早期的`arguments` 规则类似，除了每个参数都是一个标识符，而不是一个表达式。对于解析器来说，这需要处理很多新的语法，但生成的 AST 节点 并不太糟糕。

      "Expression : Expr expression",

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

      "If         : Expr condition, Stmt thenBranch," +

函数节点有一个名称、一个参数列表（它们的名称）以及函数体。我们将函数体存储为大括号内包含的一系列语句。

在解析器中，我们将新的声明编织进去。

    try {

      if (match(FUN)) return function("function");

      if (match(VAR)) return varDeclaration();

与其他语句一样，函数由开头的关键字识别。当我们遇到`fun` 时，我们将调用`function`。这对应于`function` 语法规则，因为我们已经匹配并消耗了`fun` 关键字。我们将一步一步地构建该方法，从这里开始

  private Stmt.Function function(String kind) {
    Token name = consume(IDENTIFIER, "Expect " + kind + " name.");
  }

现在，它只消耗函数名称的标识符令牌。你可能想知道那个奇怪的`kind` 参数。就像我们重新使用语法规则一样，我们稍后将重新使用`function()` 方法来解析类内部的方法。当我们这样做时，我们将为`kind` 传递“method”，以便错误消息特定于正在解析的声明类型。

接下来，我们将解析参数列表和围绕它的括号对。

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

  }

这与处理函数调用中的参数的代码类似，只是没有拆分为辅助方法。外部`if` 语句处理零参数的情况，内部`while` 循环解析参数，只要我们找到逗号来分隔它们。结果是每个参数名称的令牌列表。

就像我们在函数调用的参数中所做的那样，我们在解析时验证你是否没有超过函数允许的最大参数数量。

最后，我们将解析函数体并将其全部包装到一个函数节点中。

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

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

  }

请注意，在调用`block()` 之前，我们在此处消耗了函数体开头的`{`。这是因为`block()` 假设大括号令牌已经匹配。在此处消耗它使我们能够在未找到`{` 时报告更精确的错误消息，因为我们知道它是在函数声明的上下文中。

10 . 4函数对象

我们已经解析了一些语法，通常情况下我们已经准备好解释了，但首先我们需要考虑如何用 Java 表示 Lox 函数。我们需要跟踪参数，以便在调用函数时将它们绑定到参数值。当然，我们需要保留函数体的代码，以便我们可以执行它。

Stmt.Function 类基本上就是这样。我们可以直接使用它吗？差不多，但还不完全。我们还需要一个实现 LoxCallable 的类，以便可以调用它。我们不希望解释器运行时阶段渗透到前端的语法类中，所以我们不希望 Stmt.Function 本身实现它。相反，我们用一个新类将其包装起来。

package com.craftinginterpreters.lox;

import java.util.List;

class LoxFunction implements LoxCallable {
  private final Stmt.Function declaration;
  LoxFunction(Stmt.Function declaration) {
    this.declaration = declaration;
  }
}

我们像这样实现 LoxCallable 的 call() 方法

  @Override
  public Object call(Interpreter interpreter,
                     List<Object> arguments) {
    Environment environment = new Environment(interpreter.globals);
    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;
  }

这短短几行代码是我们解释器中最基本、最强大的部分之一。正如我们在 关于语句和 状态 的章节 中看到的，管理命名环境是语言实现的核心部分。函数与之紧密相连。

参数是函数的核心，尤其是函数 封装 其参数的事实—函数外部的其他代码无法看到它们。这意味着每个函数都有自己的环境来存储这些变量。

此外，这个环境必须是动态创建的。每个函数 调用 都拥有自己的环境。否则，递归就会失效。如果同时对同一个函数进行多次调用，那么每次调用都需要它 自己 的环境，即使它们都是对同一个函数的调用。

例如，以下是一种复杂的方法来计数到三

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

count(3);

假设我们在解释器即将在最内层嵌套调用中打印 1 的位置暂停。打印 2 和 3 的外部调用尚未打印其值，因此在内存中一定存在一些环境，这些环境仍然存储着 n 在一个上下文中绑定到 3、在另一个上下文中绑定到 2、在最内层绑定到 1 的事实，例如

这就是为什么我们在每次 调用 时创建一个新环境，而不是在函数 声明 时创建。我们之前看到的 call() 方法就是这么做的。在调用开始时，它会创建一个新环境。然后它会按顺序遍历参数列表和参数列表。对于每对参数，它都会创建一个新的变量，该变量使用参数的名称并将其绑定到参数的值。

所以，对于这样的程序

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

add(1, 2, 3);

在调用 add() 的位置，解释器会创建类似这样的东西

然后 call() 会告诉解释器在这个新的函数本地环境中执行函数体。到目前为止，当前环境是调用函数的环境。现在，我们将从那里传送进入为函数创建的新参数空间。

这就是将数据传递给函数所需的一切。通过在执行函数体时使用不同的环境，对同一个函数使用相同代码的调用可以产生不同的结果。

一旦函数体执行完毕，executeBlock() 就会丢弃该函数本地环境，并恢复之前在调用点激活的环境。最后，call() 返回 null，这会将 nil 返回给调用方。（我们将在以后添加返回值。）

从机制上讲，代码非常简单。遍历几个列表。绑定一些新变量。调用一个方法。但在这里，函数声明的晶莹剔透的 代码 变成了一种活生生的、会呼吸的 调用。这是整本书中最喜欢的代码片段之一。如果您愿意，可以花点时间冥想一下。

完成了？好的。请注意，当我们绑定参数时，我们假设参数列表和参数列表的长度相同。这是安全的，因为 visitCallExpr() 在调用 call() 之前会检查参数个数。它依赖于函数报告其参数个数来执行此操作。

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

这就是我们大多数对象表示。既然我们在这里，不妨实现 toString()。

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

如果用户决定打印函数值，这将提供更好的输出。

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

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

10 . 4 . 1解释函数声明

我们很快就会回来完善 LoxFunction，但这已经足够我们开始使用了。现在我们可以访问函数声明了。

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

这类似于我们解释其他字面表达式的做法。我们取一个函数 语法节点—函数的编译时表示—并将其转换为其运行时表示。在这里，它是一个包装了语法节点的 LoxFunction。

函数声明与其他字面节点的不同之处在于，声明 还 会将结果对象绑定到一个新变量。因此，在创建 LoxFunction 后，我们在当前环境中创建一个新的绑定，并在其中存储对它的引用。

有了它，我们就可以在 Lox 中定义和调用自己的函数。试试看

fun sayHi(first, last) {
  print "Hi, " + first + " " + last + "!";
}

sayHi("Dear", "Reader");

我不知道你怎么样，但对我来说，这看起来像一门名副其实的编程语言。

10 . 5返回语句

我们可以通过传递参数将数据传入函数，但我们没有办法将结果返回 出去。如果 Lox 是一门面向表达式的语言，比如 Ruby 或 Scheme，那么函数体将是一个表达式，其值为函数的隐式结果。但在 Lox 中，函数体是一系列语句，这些语句不会产生值，因此我们需要专门的语法来发出结果。换句话说，就是 return 语句。我相信你已经猜到了语法。

statement      → exprStmt
               | forStmt
               | ifStmt
               | printStmt
               | returnStmt
               | whileStmt
               | block ;

returnStmt     → "return" expression? ";" ;

我们还有一个—实际上是最后一个—在久负盛名的 statement 规则下的产品。一个 return 语句是 return 关键字，后面跟着一个可选的表达式，并以分号结尾。

返回值是可选的，以支持从不返回有用值的函数中提前退出。在静态类型语言中，“void” 函数不返回值，而非 void 函数则返回值。由于 Lox 是动态类型的，因此没有真正的 void 函数。编译器无法阻止你获取对不包含 return 语句的函数的调用的结果值。

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

var result = procedure();
print result; // ?

这意味着每个 Lox 函数都必须返回 一些东西，即使它根本不包含任何 return 语句。我们使用 nil 来实现这一点，这就是为什么 LoxFunction 的 call() 实现最后会返回 null。同样，如果你省略了 return 语句中的值，我们只需将其视为等效于

return nil;

在我们的 AST 生成器中，我们添加了一个 新节点。

      "Print      : Expr expression",

      "Return     : Token keyword, Expr value",

      "Var        : Token name, Expr initializer",

它保留了 return 关键字标记，以便我们可以使用其位置进行错误报告，以及返回的值（如果有）。我们像解析其他语句一样解析它，首先是识别初始关键字。

    if (match(PRINT)) return printStatement();

    if (match(RETURN)) return returnStatement();

    if (match(WHILE)) return whileStatement();

它分支到

  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 关键字后，我们会寻找一个值表达式。由于许多不同的标记都可能开始一个表达式，因此很难判断是否 存在 返回值。相反，我们会检查它是否 不存在。由于分号不能开始一个表达式，因此如果下一个标记是分号，我们就知道一定没有值。

10 . 5 . 1从调用中返回

解释 return 语句很棘手。你可以在函数体的任何地方返回，即使是在其他语句的深层嵌套中。当执行 return 时，解释器需要跳出它当前所在的任何上下文，并使函数调用完成，就像某种扭曲的控制流结构一样。

例如，假设我们正在运行以下程序，并且我们即将执行 return 语句

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

count(1);

Java 调用栈目前看起来大致如下

Interpreter.visitReturnStmt()
Interpreter.visitIfStmt()
Interpreter.executeBlock()
Interpreter.visitBlockStmt()
Interpreter.visitWhileStmt()
Interpreter.executeBlock()
LoxFunction.call()
Interpreter.visitCallExpr()

我们需要从栈顶一直返回到 call()。我不知道你怎么样，但对我来说，这听起来像是异常。当我们执行 return 语句时，我们将使用异常来解开解释器，使其跳过所有包含语句的访问方法，一直返回到开始执行函数体的代码。

我们新 AST 节点的访问方法如下所示

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

    throw new Return(value);
  }

如果我们有返回值，我们就会对其进行求值，否则我们会使用 nil。然后我们取该值，将其包装在一个自定义异常类中，并抛出它。

package com.craftinginterpreters.lox;

class Return extends RuntimeException {
  final Object value;

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

此类使用 Java 要求的附件来包装返回值，以用于运行时异常类。带有这些 null 和 false 参数的奇怪的超级构造函数调用会禁用我们不需要的一些 JVM 机制。由于我们使用自己的异常类来进行 控制流，而不是实际的错误处理，因此我们不需要像堆栈跟踪这样的开销。

我们希望它能一直解开到函数调用开始的地方，即 LoxFunction 中的 call() 方法。

          arguments.get(i));
    }

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

    return null;

我们将对 executeBlock() 的调用包装在一个 try-catch 块中。当它捕获到一个返回异常时，它会取出该值，并将其作为 call() 的返回值。如果它从未捕获到这些异常之一，则意味着函数到达了其函数体的末尾，而没有遇到 return 语句。在这种情况下，它会隐式地返回 nil。

让我们试一试。我们终于有足够的能量来支持这个经典的例子—一个递归函数来计算斐波那契数列

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

这个小程序练习了我们在过去几章中实现的几乎所有语言特性—表达式、算术运算、分支、循环、变量、函数、函数调用、参数绑定和返回。

10 . 6局部函数和闭包

我们的函数功能很全，但还有一个漏洞需要修补。事实上，这是一个很大的漏洞，我们将在 下一章 中花大部分时间来修复它，但我们可以从这里开始。

LoxFunction 的 call() 实现创建了一个新的环境，它会在其中绑定函数的参数。当向你展示这段代码时，我忽略了一个重要的地方：该环境的 父 环境是什么？

现在，它始终是 globals，即顶级的全局环境。这样，如果一个标识符没有在函数体本身中定义，解释器就可以在全局作用域之外查找它。在斐波那契示例中，解释器就是通过这种方式在函数体本身内查找对 fib 的递归调用的—fib 是一个全局变量。

但请记住，在 Lox 中，函数声明可以在任何可以绑定名称的地方任意使用。这包括 Lox 脚本的顶层，也包括块或其他函数的内部。Lox 支持在另一个函数内部定义的局部函数，或者嵌套在块内。

考虑这个经典的例子

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

  return count;
}

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

这里，count() 使用 i，它是在包含函数 makeCounter() 中定义的。makeCounter() 返回对 count() 函数的引用，然后它自己的主体完全执行完毕。

同时，顶层代码调用返回的 count() 函数。这将执行 count() 的主体，它分配并读取 i，即使定义 i 的函数已经退出。

如果你以前从未遇到过支持嵌套函数的语言，这可能看起来很疯狂，但用户确实希望它能工作。唉，如果你现在运行它，你会在调用 counter() 时得到一个未定义变量错误，因为 count() 的主体试图查找 i。这是因为有效的环境链看起来像这样

当我们调用 count()（通过存储在 counter 中的引用）时，我们为函数体创建一个新的空环境。它的父级是全局环境。我们丢失了绑定 i 的 makeCounter() 环境。

让我们回到过去一点。以下是我们在 makeCounter() 的主体中声明 count() 时环境链的样子

因此，在声明函数时，我们可以看到 i。但是，当我们从 makeCounter() 返回并退出其主体时，解释器会丢弃该环境。由于解释器不会保留 count() 周围的环境，因此函数对象本身需要保留它。

这种数据结构称为闭包，因为它“封闭并”保留了声明函数的周围变量。闭包自 Lisp 早期就已存在，语言黑客已经想出各种方法来实现它们。对于 jlox，我们将做最简单的有效方法。在 LoxFunction 中，我们添加一个字段来存储环境。

  private final Stmt.Function declaration;

  private final Environment closure;

  LoxFunction(Stmt.Function declaration) {

我们在构造函数中初始化它。

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

    this.declaration = declaration;

当我们创建 LoxFunction 时，我们捕获当前环境。

  public Void visitFunctionStmt(Stmt.Function stmt) {

    LoxFunction function = new LoxFunction(stmt, environment);

    environment.define(stmt.name.lexeme, function);

这是函数声明时有效的环境，而不是函数调用时有效的环境，这就是我们想要的。它代表函数声明周围的词法作用域。最后，当我们调用函数时，我们使用该环境作为调用的父级，而不是直接转到 globals。

                     List<Object> arguments) {

    Environment environment = new Environment(closure);

    for (int i = 0; i < declaration.params.size(); i++) {

这创建了一个环境链，从函数体开始，经过声明函数的环境，一直延伸到全局范围。运行时环境链与我们想要的源代码的文本嵌套相匹配。调用该函数时的最终结果看起来像这样

现在，正如你所看到的，解释器仍然可以在需要时找到 i，因为它在环境链的中间。现在尝试运行那个 makeCounter() 示例。它工作了！

函数允许我们抽象、重用和组合代码。Lox 比它曾经是的那台基本算术计算器强大得多。唉，在我们急于将闭包塞进去的时候，我们让一小部分动态作用域泄漏到了解释器中。在下一章中，我们将深入探索词法作用域，并堵上这个漏洞。