JavaScript 中的代数效应（第一部分）——延续和控制转移

2025-06-07

JavaScript 中的代数效应（第一部分）——延续和控制转移

这是关于代数效应和处理程序的系列文章的第一篇。

有两种方法可以解决这个问题：

  • 外延：用数学/范畴论中的含义解释代数效应
  • 操作性：通过展示代数效应在选定的运行环境下如何运作来解释代数效应的机制

这两种方法都很有价值，并能就该主题提供不同的见解。然而，并非每个人（包括我）都具备掌握范畴论和泛代数概念的先决条件。另一方面，即使操作性方法不能提供完整的图景，但更广泛的程序员群体也能理解。

因此，我们将走操作路线。我们将通过一系列示例逐步构建对所介绍概念的直观理解。在本系列的最后，我们将基于 JavaScript 生成器实现代数效果。

由于这是一个很长的话题，我们将其分为 4 个部分：

直接传球风格 vs 连续传球风格

在本部分中，我们将围绕一个小型函数式语言的简单解释器示例来构建我们的概念。该语言将支持数字、加法以及调用返回其他表达式的函数。

我们将使用以下函数来构建传递给解释器的 AST（抽象语法树）：

function fun(param, body) {
  return { type: "fun", param, body };
}

function call(funExp, argExp) {
  return { type: "call", funExp, argExp };
}

function add(exp1, exp2) {
  return { type: "add", exp1, exp2 };
}

// example
const doubleFun = fun("x", add("x", "x"));
program = call(doubleFun, 10);

解释器接受如上所示的 AST 并返回最终值。最终值反映了原子表达式，它们不需要进一步求值（此处为数字或fun），并且是目标语言（此处为 JavaScript）的对象。我们将按原样表示数字，并fun使用 JavaScript 函数表示表达式。

为了执行一个程序，解释器除了程序抽象语法树 (AST) 之外，还需要一个将变量名映射到其值的环境。我们将使用一个普通的 JavaScript 对象来表示该环境。

以下是解释器的可能实现：

function evaluate(exp, env) {
  if (typeof exp === "number") {
    return exp;
  }
  if (typeof exp === "string") {
    return env[exp];
  }
  if (exp.type === "add") {
    return evaluate(exp.exp1, env) + evaluate(exp.exp2, env);
  }
  if (exp.type === "fun") {
    return function(value) {
      const funEnv = { ...env, [exp.param]: value };
      return evaluate(exp.body, funEnv);
    };
  }
  if (exp.type === "call") {
    const funValue = evaluate(exp.funExp, env);
    const argValue = evaluate(exp.argExp, env);
    return funValue(argValue);
  }
}

evaluate(program);
// => 20

工作原理如下evaluate：

  • 简单数字按原样返回
  • 变量从当前环境中解析。我们暂时不处理未知变量
  • 加法递归地计算其操作数并返回计算结果的总和
  • 对于function 的情况，我们返回一个 JavaScript 函数，该函数将被调用并传入最终值（其他求值的结果）。调用时，该函数将构建一个新的环境，其中参数fun与提供的值绑定，然后fun在这个新环境中求值。
  • 这种call情况类似于add我们递归地评估函数和参数表达式，然后将函数值应用于参数值

evaluate被称为以直接风格编写。这并不是解释器特有的。直接风格的程序仅仅意味着函数通过return语句传递其结果。例如，这个简单的函数也是直接风格的：

function add(x, y) {
  return x + y;
}

相比之下，在连续传球风格（CPS）中：

  1. 该函数接受回调作为附加参数
  2. 该函数永远不会返回其结果。它始终使用回调来传达其结果
  3. 与你的想法相反。它最初与异步 Node.js 函数无关

例如，转换为CPS，前面的函数就变成：

function add(x, y, next) {
  const result = x + y;
  return next(result);
}

提供的回调也称为延续 (continuation)，因为它指定了程序下一步要执行的操作。当 CPS 函数终止时，它会将结果抛出到延续 (continuation) 中。

建议：作为一个快速练习，尝试将解释器转换为 CPS 格式。首先将延续参数添加到 的签名中evaluate。

解决方案：

function evaluate(exp, env, next) {
  if (typeof exp === "number") {
    return next(exp);
  }
  if (typeof exp === "string") {
    return next(env[exp]);
  }
  if (exp.type === "add") {
    return evaluate(exp.exp1, env, function addCont1(val1) {
      return evaluate(exp.exp2, env, function addCont2(val2) {
        return next(val1 + val2);
      });
    });
  }
  if (exp.type === "fun") {
    // notice the function value becomes a CPS itself
    const closure = function(value, next) {
      const funEnv = { ...env, [exp.param]: value };
      return evaluate(exp.body, funEnv, next);
    };
    return next(closure);
  }
  if (exp.type === "call") {
    return evaluate(exp.funExp, env, function callCont1(funValue) {
      return evaluate(exp.argExp, env, function callCont2(argValue) {
        return funValue(argValue, next);
      });
    });
  }
}

function run(program) {
  return evaluate(program, {}, x => x);
}

需要注意的是：

  1. 每个return语句要么调用延续函数，要么调用另一个 CPS 函数
  2. 所有这些调用都处于尾部调用位置
  3. add当需要求值多个表达式（和多个case）时，call我们会通过提供中间延续（continuation）来链接这些求值，中间延续会捕获中间结果。当链接终止时，我们会将结果抛给主延续（main continuation）。
  4. 直接风格让生活更美好

在这个阶段，程序已经很难读懂了。所以你可能会问

为什么我们要以这种风格编写程序？

简而言之：你不需要。但这并不意味着 CPS 毫无用处。

有多种原因使得 CPS 有用甚至更受欢迎，但并非所有原因都适用于 JavaScript（在其当前状态下）。

  1. 首先也是最重要的就是控制。在直接调用版本中，调用者控制下一步做什么，延续函数是隐式的，对我们隐藏。然而，在 CPS 版本中，延续函数是显式的，并作为参数传递，被调用者可以通过调用延续函数来决定下一步做什么。正如我们将在下一节中看到的那样，CPS 可以用来实现各种直接调用版本无法实现的控制流。

  2. 其次，所有函数调用在 CPS 中都处于尾调用位置。尾调用不需要增加调用栈（下一节将解释）。由于尾调用之后没有任何操作，因此在执行尾调用之前无需保存执行上下文。编译器可以通过直接用被调用函数的执行上下文替换当前执行上下文（而不是将其压入当前执行上下文之上）来优化这些尾调用。这个过程被称为尾调用消除，并被函数式编译器广泛利用。遗憾的是，尽管尾调用消除是 ECMAScript 规范的一部分，但当前的 JavaScript 引擎并非都实现了它。

  3. 当然，最重要的是 JavaScript 单线程特性所要求的异步性。如果我们使用直接函数来执行远程请求，就必须暂停唯一的线程，直到请求完成，从而阻塞当前语句的进程，并在此期间阻止任何其他交互。CPS 提供了一种便捷高效的fork工作方式，使当前代码可以继续执行并处理其他交互。事​​实上，人们可能会认为这是在 JavaScript 中使用这种风格的唯一实际原因。

  4. 最后，CPS 功能强大，但并非旨在供人类直接使用。它更适合编译器或解释器。我们的大脑更适应结构化的直接风格。因此，虽然我们自己不会用 CPS 编写代码，但它仍然是解释器在后台使用的强大工具。在接下来的文章中，我们将了解如何在后台利用 CPS 的强大功能来呈现更强大的直接风格 API。

就我们的目的而言，原因 1、3 和 4 都适用。我们需要对代码进行更灵活的控制，并且需要在恢复直接风格的同时处理异步问题。

目前，JavaScript 中的惯用解决方案是使用 async/await，这实际上给了我们 3 和 4，但没有 1。我们对控制流没有足够的控制权。

什么是控制流？

控制流是命令式程序中各个语句、指令或函数调用的执行或评估的顺序（维基百科）。

默认情况下，在像 JavaScript 这样的命令式语言中，语句是按顺序执行的（在 CPU 级别，除非执行控制转移指令，否则指令指针会自动递增）。但 JavaScript 也提供了一些控制运算符来改变这种行为。例如，当我们break在循环内部时，控制会跳转到循环块之后的第一条指令。类似地，if如果条件为 false，则可能会跳过整个循环块。所有这些都是局部控制转移的例子，即发生在同一函数内部的跳转。

函数调用是一种重要的控制传输机制。它的工作原理得益于一种称为调用堆栈的数据结构。这个简短的视频很好地解释了该机制（附言：值得一看）。

注意，在视频中，调用者如何压入指向被调用者返回后下一条指令的返回地址。这看起来非常类似于我们将延续性作为附加参数提供给 CPS 函数的方式。然而，使用调用堆栈时，我们对这个延续性没有任何控制权。当函数终止时，控制权会自动交还给调用者。在 CPS 中，我们拥有这种控制权，因为延续性被具体化为一个普通函数。

这并不意味着我们在 CPS 模式下不使用调用堆栈。CPS 调用仍然使用调用堆栈，但不依赖它进行控制转移（这就是我们永不返回的原因）。这意味着调用堆栈会随着每一步而增长。对于支持尾调用优化的编译器来说，这不会有问题（因为 CPS 调用始终位于尾部），但如果我们的进程中很大一部分是同步的（例如大量的递归调用），那么在像 JavaScript 这样的语言中，这种情况可能会出现。但由于我们在这里主要使用 CPS 来处理异步调用，因此不存在这个问题。

异常是一种常见的非本地控制转移形式。抛出异常的函数可能会导致控制跳转到调用层次结构中较上层的另一个函数。

function main() {
  try {
    // ...
    child1();
    // ...
  } catch (something) {
    console.log(something);
  }
}

function child1() {
  // ...
  child2();
  workAfterChild2();
}

function child2() {
  // ...
  throw something;
  //...
}

throw绕过中间函数调用以到达最近的处理程序。当我们到达该catch子句时，所有中间堆栈帧都会被自动丢弃。在上面的例子中，workAfterChild2()中间调用中的剩余部分child1被跳过。由于这由编译器隐式管理，我们无法恢复跳过的工作。稍后讨论代数效应时，我们将再次讨论这种机制。

为了说明 CPS 如何实现其他控制流，我们将在解释器中添加错误处理，而不依赖于原生的 JavaScript 异常。诀窍在于，在正常的完成延续过程中，提供另一个绕过下一步并中止整个计算的延续。

function evaluate(exp, env, abort, next) {
  if (typeof exp === "number") {
    return next(exp);
  }
  if (typeof exp === "string") {
    if (!env.hasOwnProperty(exp)) {
      return abort(`Unkown variable ${exp}!`);
    }
    return next(env[exp]);
  }
  if (exp.type === "add") {
    return evaluate(exp.exp1, env, abort, function cont1(val1) {
      if (typeof val1 != "number") {
        return abort("add called with a non numeric value");
      }
      return evaluate(exp.exp2, env, abort, function cont2(val2) {
        if (typeof val2 != "number") {
          return abort("add called with a non numeric value");
        }
        return next(val1 + val2);
      });
    });
  }
  if (exp.type === "fun") {
    // notice the function value becomes a CPS itself
    const closure = function(value, abort, next) {
      const funEnv = { ...env, [exp.param]: value };
      return evaluate(exp.body, funEnv, abort, next);
    };
    return next(closure);
  }
  if (exp.type === "call") {
    return evaluate(exp.funExp, env, abort, function cont1(funValue) {
      if (typeof funValue != "function") {
        return abort("trying to call a non function");
      }
      return evaluate(exp.argExp, env, abort, function cont2(argValue) {
        return funValue(argValue, abort, next);
      });
    });
  }
}

function run(program) {
  return evaluate(program, {}, console.error, x => x);
}

run(add("x", 3), 10);
// => Unkown variable x!

run(call(5, 3), 10);
// => 5 is not a function

我们将通过添加一项功能来结束本部分，该功能将让您提前体验捕获的延续性：escape操作符。

要了解其escape工作原理，请考虑以下示例：

// ie: (x => x + x)(3 + 4)
call(fun("x", add("x", "x")), add(3, 4));

其计算结果为14。如果我们将其包装在escape运算符中，如下所示

// escape (eject) in (x => x + x)(3 + eject(4))
escape(
  "eject", // name of the eject function
  call(fun("x", add("x", "x")), add(3, call("eject", 4)))
);

我们4反而得到了，因为eject函数用提供的值中止了整个表达式。

以下是我们需要添加的代码。实现过程出奇地简短：

function escape(eject, exp) {
  return { type: "escape", eject, exp };
}

function evaluate(exp, env, abort, next) {
  //...
  if (exp.type === "escape") {
    const escapeEnv = { ...env, [exp.eject]: next };
    return evaluate(exp.exp, escapeEnv, abort, next);
  }
}

run(escape("eject", call(fun("x", add("x", "x")), add(3, call("eject", 4)))));
// => 4

我们需要做的就是将参数绑定eject到转义表达式的当前延续。

结论

第一部分的主要内容：

  1. 直接方式依赖调用堆栈进行控制转移
  2. 在直接调用方式中，函数之间的控制转移是隐式的，对我们隐藏。函数必须始终返回其直接调用者。
  3. 您可以使用异常来进行非本地控制转移
  4. CPS 函数永远不会返回结果。它们会接受额外的回调参数，用于表示当前代码的延续。
  5. 在 CPS 中，控制转移不依赖于调用堆栈。它通过提供的延续功能明确实现。
  6. CPS 可以模拟本地和非本地控制传输，但是……
  7. CPS 不是供人类使用的东西，手写的 CPS 代码很快就会变得不可读
  8. 请务必阅读上一句

下一部分我们将看到如何使用生成器来执行以下操作：

  • 恢复直接风格
  • 在需要时捕获延续
  • 未限定延续和限定延续之间的区别

感谢您的耐心阅读！

文章来源：https://dev.to/yelouafi/algebraic-effects-in-javascript-part-1---continuations-and-control-transfer-3g88
Devto 翻译
PREV
逼真的红色开关（纯 CSS）
NEXT
为建筑而战