如何用 JavaScript 这样的动态语言实现延续？

Question

我需要一些技巧，我应该如何着手并在 JavaScript 中实现嘴唇的延续（我的 lisp 几乎就像方案，除了没有延续和 TOC）。

这是我的评估函数：

function getFunctionArgs(rest, { env, dynamic_scope, error }) {
    var args = [];
    var node = rest;
    markCycles(node);
    while (true) {
        if (node instanceof Pair && !isEmptyList(node)) {
            var arg = evaluate(node.car, { env, dynamic_scope, error });
            if (dynamic_scope) {
                arg = unpromise(arg, arg => {
                    if (typeof arg === 'function' && isNativeFunction(arg)) {
                        return arg.bind(dynamic_scope);
                    }
                    return arg;
                });
            }
            args.push(arg);
            if (node.haveCycles('cdr')) {
                break;
            }
            node = node.cdr;
        } else {
            break;
        }
    }
    return resolvePromises(args);
}
// -------------------------------------------------------------------------
function evaluateMacro(macro, code, eval_args) {
    if (code instanceof Pair) {
        //code = code.clone();
    }
    var value = macro.invoke(code, eval_args);
    return unpromise(resolvePromises(value), function ret(value) {
        if (value && value.data || !value || selfEvaluated(value)) {
            return value;
        } else {
            return quote(evaluate(value, eval_args));
        }
    });
}
// -------------------------------------------------------------------------
function evaluate(code, { env, dynamic_scope, error = () => {} } = {}) {
    try {
        if (dynamic_scope === true) {
            env = dynamic_scope = env || global_env;
        } else if (env === true) {
            env = dynamic_scope = global_env;
        } else {
            env = env || global_env;
        }
        var eval_args = { env, dynamic_scope, error };
        var value;
        if (isNull(code)) {
            return code;
        }
        if (isEmptyList(code)) {
            return emptyList();
        }
        if (code instanceof Symbol) {
            return env.get(code, { weak: true });
        }
        var first = code.car;
        var rest = code.cdr;
        if (first instanceof Pair) {
            value = resolvePromises(evaluate(first, eval_args));
            if (isPromise(value)) {
                return value.then((value) => {
                    return evaluate(new Pair(value, code.cdr), eval_args);
                });
                // else is later in code
            } else if (typeof value !== 'function') {
                throw new Error(
                    type(value) + ' ' + env.get('string')(value) +
                        ' is not a function while evaluating ' + code.toString()
                );
            }
        }
        if (first instanceof Symbol) {
            value = env.get(first, { weak: true });
            if (value instanceof Macro) {
                var ret = evaluateMacro(value, rest, eval_args);
                return unpromise(ret, result => {
                    if (result instanceof Pair) {
                        return result.markCycles();
                    }
                    return result;
                });
            } else if (typeof value !== 'function') {
                if (value) {
                    var msg = `${type(value)} \`${value}' is not a function`;
                    throw new Error(msg);
                }
                throw new Error(`Unknown function \`${first.name}'`);
            }
        } else if (typeof first === 'function') {
            value = first;
        }
        if (typeof value === 'function') {
            var args = getFunctionArgs(rest, eval_args);
            return unpromise(args, function(args) {
                var scope = dynamic_scope || env;
                var result = resolvePromises(value.apply(scope, args));
                return unpromise(result, (result) => {
                    if (result instanceof Pair) {
                        return quote(result.markCycles());
                    }
                    return result;
                }, error);
            });
        } else if (code instanceof Symbol) {
            value = env.get(code);
            if (value === 'undefined') {
                throw new Error('Unbound variable `' + code.name + '\'');
            }
            return value;
        } else if (code instanceof Pair) {
            value = first && first.toString();
            throw new Error(`${type(first)} ${value} is not a function`);
        } else {
            return code;
        }
    } catch (e) {
        error && error(e, code);
    }
}

备注：

// unpromise and resolvePromises is just used ot unwrap any promise
// inside list and return new promise for whole expression if found
// any promise and not found it just return value as is
// markCycles is used to prevent of recursive printing of list cycles
// if you create graph cycles using `set-cdr!` or `set-car!`

在为延续计算表达式时是否需要创建堆栈？我怎样才能做到这一点？我以为我以某种方式创建了 class Continuation 它将处于两种模式，一种是在可以像宏一样调用时填充，另一种是等待通过评估需要执行的代码来填充，我我也不确定我应该如何着手而不是评估调用延续的表达式之前的代码，例如：

(* 10 (cont 2))

(* 10 x)需要忽略

我也不确定我应该如何着手创建 call/cc 作为函数。它是否应该 return 一些中间数据结构及其参数存储在该数据结构中以便可以通过继续评估调用它？

'call/cc': function(lambda) {
   return new CallCC(lambda);
}

如果 eval 找到 CallCC 的实例，它会继续（还不确定如何）使用

if (value instanceof CallCC) {
   value.call(new Continuation(stack));
}

你会这样做吗？所以通常我的问题是关于堆栈的。是否需要延续？如果需要，应该如何创建？

我发现这篇文章 Writing a Lisp: Continuations 展示了如何实现延续，但很难理解，因为它在 Haskell 中。

Answer 1

在解释器中实现延续的一种方法是让解释器使用它自己的显式堆栈来进行函数 calling/returning 和参数传递。如果您使用宿主语言的堆栈，而该语言没有延续，那么事情就很困难了。

如果您使用自己的显式堆栈，您可以将它变成一个 "spaghetti stack" 用于延续。 "spaghetti stack" 与词法环境的常见表示非常相似。它包含指向父框架的框架。捕获延续相当于保留指向此类框架的指针和一些代码。恢复延续意味着，或多或少，将堆栈恢复到该帧，并将执行恢复到代码中的那个点。该语言的解释器不会递归。当解释型语言嵌套或递归时，解释器迭代并仅压入和弹出显式堆栈以跟踪状态。

另一种方法是使用线性堆栈，但在进行延续时复制它。要恢复延续，您可以从复制的快照中恢复整个堆栈。这对于定界的延续很有用，它可以避免复制整个堆栈，而只复制它的定界部分（并将其恢复到现有堆栈的顶部，而不是通过替换）。我已经在使用底层 C 堆栈的语言中实现了定界延续。 C 堆栈的一部分被 memcpy-d 输出到堆上的对象中。当继续恢复时，保存的堆栈段将在当前堆栈的顶部爆炸。当然，必须调整指针，因为该段现在位于不同的地址，并且必须连接 "dangling cabling" 以将该堆栈段正确地集成到堆栈中。

如果一种语言被编译为 CPS（延续传递样式），那么延续会免费弹出。每个函数都有一个隐含的隐藏参数：它收到的延续。函数 returning 被编译成对此延续的调用。如果函数中的代码块需要计算当前延续，它只需将一个小的本地计算未来（表示为 lambda）与传入的延续（当本地部分 return 时发生的未来计算）组成秒）。 Henry Baker 基于以下观察写了一篇论文，即在 CPS 下，由于没有函数曾经 returns（returns 编译到对延续的尾调用），所以永远不会重新访问旧的堆栈帧。堆栈可以刚好任其增长，当达到一个极限时，可以"rewound"回顶。 Chicken Scheme 实现了这个概念；如果您对延续感兴趣，那么值得研究一下。 Chicken Scheme 编译成使用常规 C 堆栈的 C 代码。但是，生成的函数从不 return：它们通过调用延续来模拟 returning，因此堆栈会增长。更令人着迷的是，我们通常理解为动态 material 的对象也是从堆栈中分配的。由于没有 returns，这些对象是安全的。每当达到某个堆栈限制时，堆栈上所有仍然存在的对象都会被移动到堆中，并且堆栈指针会倒回到顶部。

Answer 2

首先。所有语言都有延续。当您执行 7 + n * 5 时，JavaScript 将其重新排序为 mul_k(n, 5, (_v) => (add _v 7 k)，其中 k 是一个函数，它执行该表达式之后发生的所有事情。

现在 mul_k 的第一个参数是一个延续。除了一点点思考之外，没什么可怕的。你再也不会 return 任何东西了。每个 "return" 都只是传递给它的延续，它总是一个尾调用。

本身不是尾递归的递归函数将在每一步产生一个新的闭包并嵌套下一步。这些存储在堆上，因此非尾递归函数变成尾调用，并创建了很多嵌套闭包。

这是一个小例子：

(define (get-c) (call/cc (lambda (cont) cont)))

(let ((example (get-c)))
  (displayln example)
  (if (procedure? example)
      (example 10)
      "done"))

让我们想象一下这就是整个程序。让我们把它写到 JavaScript。

// simple CPS version of displayln
const displayln = (arg, k) k(console.log(arg));

// simple CPS version of procedure?
const isProcedure = (arg, k) k(arg instanceOf Function);

// Simple CPS version of call/cc
const callCC = (userFun, callCCK) 
  => userFun((result, actualK) => callCCK(result), callCCK);

// simple top level continutation. Not a CPS function.
const kTopLevel = console.log;

// the user function get-c transformed into CPS
const getC = getCK => callCC((cont, k) => k(cont), getCK);

// the let code transformed into CPS
getC((example) => // c1
  displayln(example, (_undefined) => // c2 
    isProcedure(example, (result) => // c3
      result ? example(10, kTopLevel) : kTopLevel("done"))

这是正在发生的事情：

getC 获取整个延续 (c1) 并调用 callCC
callCC 调用 c1 获取 (result, _) => c1(result) 作为 example
display 打印 example，继续，将其未定义的 return 值传递给它的继续 c2
isPorcedure 在 example 上，它是一个延续，它将 true 作为 result 传递给延续 c3
成为true它调用example(10, kTopLevel)变成c1(10)，因此10例如
display 打印 èexample, the number10, passes its underfined return value to its continuationc2`
isProcedure on example 将 false 作为 result 传递给继续 c3
作为 false 它调用 TopLevel("dome")
TopLevel 打印 "done"

如你所见。 call/cc 很简单，只要在执行之前将代码转换为 CPS 。 JavaScript 很好地支持 CPS。

Matt Might 已完成如何将代码转换为 CPS 的帮助 countless times in his essays. Look for continuations in that list. He has even done it in JavaScript。

现在，如果您的实现需要被解释，您可以在 Scheme 中进行相同的转换并解释它而不是用户代码。如果你有持续障碍，你只需要从 call/cc 到障碍的 CPS。

Answer 3

同步call/cc

callcc 可以使用 try-catch 以直接方式实现。重要的一点是延续必须“装箱” return 值并在 catch 中“拆箱”它以避免吞下真正的错误 -

const callcc = f => {
  class Box { constructor(v) { this.unbox = v } }
  try { return f(value => { throw new Box(value) }) }
  catch (e) { if (e instanceof Box) return e.unbox; throw e  }
}

console.log(5 + callcc(exit => 10 * 3))
console.log(5 + callcc(exit => 10 * exit(3)))
console.log(5 + callcc(exit => { exit(10); return 3 }))
console.log(5 + callcc(exit => { exit(10); throw Error("test failed") }))

try {
  console.log(5 + callcc(exit => { throw Error("test passed!") }))
}
catch (e) {
  console.error(e)
}

.as-console-wrapper { min-height: 100%; top: 0; }

35                     ✅ 5 + 10 * 3
8                      ✅ 5 + 3
15                     ✅ 5 + 10
15                     ✅ 5 + 10
Error: test passed!    ✅ Errors are not swallowed

callcc 最初是在 this Q&A 中实现的。继续阅读以获取更多信息和示例。

如何用 JavaScript 这样的动态语言实现延续？

How to implement continuations in dynamic language like JavaScript?

javascript

scheme

lisp

continuations

callcc