第 9 章：控制流（Control Flow）

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

图灵机能做的任何事，其他能做到同样事情的机器也能做到。

Alan Turing

变量让程序有状态，控制流让程序能根据状态选择路径、重复执行。加入条件、逻辑运算与循环后，Lox 成为图灵完备语言：从计算能力的角度，它能表达任何可计算过程。

9.1 图灵机（简述）（Turing Machines, Briefly）

二十世纪早期，数学基础危机促使人们追问什么是可计算函数。图灵与 Church 分别提出了图灵机和 lambda 演算这两种等价的极小模型；前者以无限纸带保存符号，读写头读取或修改当前格，有限状态机依据状态和符号移动并改变状态。其看似简单，却能模拟任何通用计算机。

这场危机与自指悖论有关。Russell 的集合 R 被定义为“所有不包含自身的集合组成的集合”，那么 R 是否包含自身？无论回答是或否都会矛盾。后来 Church 和 Turing 证明，并非每个看似良好提出的问题都有可计算的通用答案；例如不存在一个能判定任意程序是否最终停止的程序。

Lox 不像图灵机，但只要能执行算术、进行少量控制流并使用理论上任意多的内存，就具备同等计算表达力。变量提供状态，if 提供条件分支，循环提供重复；字符串已经可以存储任意长内容，只是还不能按位置访问它。因此本章的功能并非普通便利，而是跨越了重要理论门槛。

9.2 条件执行（Conditional Execution）

控制流可粗分为两类：条件（分支）控制流跳过一段代码，循环控制流跳回去再次执行代码。C 系语言通常有 if 和三元 ?:，前者选择语句，后者选择表达式；Lox 为保持简单仅实现 if。if 的文法与 AST：

statement -> "if" "(" expression ")" statement
           ( "else" statement )?
           | ... ;

defineAst(outputDir, "Stmt", Arrays.asList(
    // 既有节点省略。
    "If : Expr condition, Stmt thenBranch, Stmt elseBranch"
));

解析 if：

private Stmt ifStatement() {
  consume(LEFT_PAREN, "Expect '(' after 'if'.");
  Expr condition = expression();
  consume(RIGHT_PAREN, "Expect ')' after if condition.");

  Stmt thenBranch = statement();
  Stmt elseBranch = null;
  if (match(ELSE)) {
    elseBranch = statement();
  }

  return new Stmt.If(condition, thenBranch, elseBranch);
}

在 statement() 开头加入：

if (match(IF)) return ifStatement();

解释器根据 Lox 的真值规则执行其中一个分支：

@Override
public Void visitIfStmt(Stmt.If stmt) {
  if (isTruthy(evaluate(stmt.condition))) {
    execute(stmt.thenBranch);
  } else if (stmt.elseBranch != null) {
    execute(stmt.elseBranch);
  }
  return null;
}

悬挂 else 是经典语法问题：else 总与最近的、尚未匹配 else 的 if 结合。递归下降中，内层 ifStatement() 会先消费它，因此自然得到这一通行规则。若想让外层 if 获得 else，就必须用块显式分组。

例如下列语句会把 else 绑定到内层 if，而不是外层：

if (first) if (second) whenTrue(); else whenFalse();

9.3 逻辑运算符（Logical Operators）

第 3 章定义了 and 与 or，现在实现其短路语义。它们优先级低于相等比较、高于赋值；AST 新增：

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

文法在赋值与相等比较之间加入两个层次：

expression -> assignment ;
assignment -> IDENTIFIER "=" assignment | logic_or ;
logic_or   -> logic_and ( "or" logic_and )* ;
logic_and  -> equality ( "and" equality )* ;

解析函数与二元表达式相似：

private Expr or() {
  Expr expr = and();

  while (match(OR)) {
    Token operator = previous();
    Expr right = and();
    expr = new Expr.Logical(expr, operator, right);
  }
  return expr;
}

private Expr and() {
  Expr expr = equality();

  while (match(AND)) {
    Token operator = previous();
    Expr right = equality();
    expr = new Expr.Logical(expr, operator, right);
  }
  return expr;
}

assignment() 的基础规则改为 or()。解释时不可先计算两个操作数，否则会失去短路：

@Override
public Object visitLogicalExpr(Expr.Logical expr) {
  Object left = evaluate(expr.left);

  if (expr.operator.type == OR) {
    if (isTruthy(left)) return left;
  } else {
    if (!isTruthy(left)) return left;
  }

  return evaluate(expr.right);
}

or 的左值为真时立即返回左值，and 的左值为假时立即返回左值；否则才计算右侧。注意返回的不是强制转换后的布尔值，而是原始操作数："yes" or "no" 的结果是 "yes"。这种行为方便表达默认值和条件选择。

短路不仅影响结果，也避免不必要的副作用：

false and sideEffect();

这里 sideEffect() 不会执行。or 也会返回实际操作数：

print "hi" or 2; // "hi".
print nil or "yes"; // "yes".

9.4 while 循环（While Loops）

while 的文法、AST 与解析：

statement -> "while" "(" expression ")" statement | ... ;

"While : Expr condition, Stmt body"

private Stmt whileStatement() {
  consume(LEFT_PAREN, "Expect '(' after 'while'.");
  Expr condition = expression();
  consume(RIGHT_PAREN, "Expect ')' after condition.");
  Stmt body = statement();

  return new Stmt.While(condition, body);
}

解释器每轮重新计算条件：

@Override
public Void visitWhileStmt(Stmt.While stmt) {
  while (isTruthy(evaluate(stmt.condition))) {
    execute(stmt.body);
  }
  return null;
}

循环让程序运行时间不再严格受源代码长度限制。Lox 暂时只有 C 风格 while；更高级的 foreach、增强 for 或基于迭代协议的循环，要等到对象和方法出现后才适合引入。例如：

var a = 1;
while (a < 10) {
  print a;
  a = a + 1;
}

9.5 for 循环（For Loops）

Lox 的 for 语法很熟悉：

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

完整文法：

forStmt -> "for" "(" ( varDecl | exprStmt | ";" )
           expression? ";"
           expression? ")" statement ;

for 的初始化、条件、增量均可缺省。初始化仅执行一次，可以是变量声明或表达式；条件在每一轮开始时判断；增量在循环体之后执行，其结果被丢弃；带初始化器的循环变量只在该 for 的其余部分和循环体内可见。解析器不需要为它生成专用 AST 节点，而是把它脱糖（desugar）为已有节点：

private Stmt forStatement() {
  consume(LEFT_PAREN, "Expect '(' after 'for'.");

  Stmt initializer;
  if (match(SEMICOLON)) {
    initializer = null;
  } else if (match(VAR)) {
    initializer = varDeclaration();
  } else {
    initializer = expressionStatement();
  }

  Expr condition = null;
  if (!check(SEMICOLON)) {
    condition = expression();
  }
  consume(SEMICOLON, "Expect ';' after loop condition.");

  Expr increment = null;
  if (!check(RIGHT_PAREN)) {
    increment = expression();
  }
  consume(RIGHT_PAREN, "Expect ')' after for clauses.");

  Stmt body = statement();

  if (increment != null) {
    body = new Stmt.Block(Arrays.asList(
        body,
        new Stmt.Expression(increment)));
  }

  if (condition == null) condition = new Expr.Literal(true);
  body = new Stmt.While(condition, body);

  if (initializer != null) {
    body = new Stmt.Block(Arrays.asList(initializer, body));
  }

  return body;
}

一个 for：

for (initializer; condition; increment) body;

最终等价于：

{
  initializer;
  while (condition) {
    body;
    increment;
  }
}

条件缺省时变为 true，形成无限循环。用块包住初始化器还能确保循环变量只在该 for 的作用域内可见。

本章的完整示例用 for 打印斐波那契序列；脱糖后仍保持相同的初始化、条件、更新顺序：

var a = 0;
var temp;

for (var b = 1; a < 10000; b = temp + b) {
  print a;
  temp = a;
  a = b;
}

9.5.1 脱糖（Desugaring）

语法糖是让程序员写得更方便、但可翻译为已有更基础构造的语法。这个说法由 Peter J. Landin 在 1964 年提出，用来形容 ALGOL 等语言加在 lambda 演算之上的便利表达式形式。for 只是 while、块和表达式语句的表层写法，因此没有必要让解释器专门实现 visitForStmt()。

脱糖将复杂性放在解析器，令解释器保持小而正交。它也是语言实现中常见的策略：许多表面特性都可在某个早期阶段归约为较小的核心语言。但脱糖必须谨慎保持语义，例如本例中增量必须在每次循环主体后执行，初始化器的作用域也必须正确。

挑战（Challenges）

1. 在一等函数和动态分派完成后，如何只用它们实现条件执行？举出采用此技术的语言。
2. 同样只用这些工具实现循环需要解释器具备哪项关键优化？为什么需要它？举出使用这种迭代方式的语言。
3. 为 break 添加支持。其语法是 break;；循环外使用应为语法错误，运行时必须跳到最近外层循环的末尾，即使中间嵌有块或 if。

设计笔记：一勺勺语法糖（Spoonfuls of Syntactic Sugar）

语言设计必须决定往文法里加多少糖：一端是 Lisp、Forth、Smalltalk 一类极小语法，它们依赖强大的核心与库来表达特性；接近它们的是 C、Lua、Go，重视简单清晰；中间有 Java、C#、Python；另一端则是 Ruby、C++、Perl、D 等拥有大量表面语法的语言。

语言往往随时间变甜：新语法容易取悦用户，也较少破坏旧程序；可一旦加入便很难删除。语法糖在语言理论圈名声不佳并非没有理由，设计不良的特性会增加认知负担，却没有足够表达力作为回报。克制能防止语言膨胀。

但程序员长期生活在所选语言中，少量便利确实能提高舒适度和效率。语法糖不是“无用的花哨”，for 正是把初始化、测试和更新放进读者熟悉的紧凑结构中。没有通用配方，适当的甜度取决于语言设计者的品味。