3

我需要一些关于我应该如何在 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!`

在评估延续的表达式时是否需要创建堆栈?我怎样才能做到这一点?我以为我以某种方式创建Continuation了一个类,该类将处于两种模式中about 而不是评估调用延续的表达式之前的代码,例如:

(* 10 (cont 2))

(* 10 x)需要被忽略

我也不确定我应该如何着手和创建call/cc函数。它是否应该返回一些中间数据结构,并将其参数存储在该数据结构中,以便可以通过继续评估来调用它?

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

如果 eval 找到 CallCC 的实例,它会继续(不确定如何)使用

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

你会这样做吗?所以通常我的问题是关于堆栈的。是否需要继续?如果需要,那么应该如何创建它?

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

4

2 回答 2

4

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

如果您使用自己的显式堆栈,则可以将其变成“意大利面条堆栈”以供继续使用。“意大利面条堆栈”与词汇环境的常见表示非常相似。它包含指向父框架的框架。捕获延续相当于保留指向此类帧的指针和一些代码。恢复延续或多或少意味着将堆栈恢复到该帧,并在代码中执行到该点。该语言的解释器不会递归。当解释语言嵌套或递归时,解释器迭代并只是推送和弹出显式堆栈以跟踪状态。

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

如果一种语言被编译为 CPS(延续传递风格),那么延续是免费的。每个函数都有一个隐含的隐藏参数:它收到的延续。返回的函数被编译成对该延续的调用。如果函数中的代码块需要计算当前的延续,它只需要与传入的延续(本地部分返回时发生的未来计算)组成一个小的局部计算未来(可以表示为 lambda)。Henry Baker 基于以下观察写了一篇论文:在 CPS 下,由于没有函数返回(返回编译为对延续的尾调用),因此永远不会重新访问旧的堆栈帧。可以只允许堆栈增长,当达到限制时,可以“倒回”回到顶部。小鸡计划实现了这一概念;如果您对延续感兴趣,则值得研究。Chicken Scheme 编译为使用常规 C 堆栈的 C 代码。但是,生成的函数永远不会返回:它们通过调用延续来模拟返回,因此堆栈会增长。更令人着迷的是,我们通常理解为动态材料的对象也是从堆栈中分配的。由于没有任何返回,因此这些对象是安全的。每当达到某个堆栈限制时,堆栈上所有仍处于活动状态的对象都将移动到堆中,并将堆栈指针倒回到顶部。他们通过调用延续来模拟返回,因此堆栈会增长。更令人着迷的是,我们通常理解为动态材料的对象也是从堆栈中分配的。由于没有任何返回,因此这些对象是安全的。每当达到某个堆栈限制时,堆栈上所有仍处于活动状态的对象都将移动到堆中,并将堆栈指针倒回到顶部。他们通过调用延续来模拟返回,因此堆栈会增长。更令人着迷的是,我们通常理解为动态材料的对象也是从堆栈中分配的。由于没有任何返回,因此这些对象是安全的。每当达到某个堆栈限制时,堆栈上所有仍处于活动状态的对象都将移动到堆中,并将堆栈指针倒回到顶部。

于 2019-06-06T17:17:15.550 回答
2

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

现在第一个参数mul_k是一个延续。没什么可怕的,除了一点点想法。你再也不会真正返回任何东西了。每个“返回”都只是传递给它的延续,它总是一个尾调用。

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

这是一个小例子:

(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调用c1get (result, _) => c1(result)asexample
  • displayprints example,延续,将其未定义的返回值传递给它的延续c2
  • isPorcedureonexample并且它是一个延续它true作为result延续传递c3
  • true它称为example(10, kTopLevel)which 成为c1(10), 因此10作为例子
  • display打印示例, the number10 , passes its underfined return value to its continuationc2`
  • isProcedure 关于延续的example通行证falseresultc3
  • false它召唤TopLevel("dome")
  • TopLevel 打印“完成”

如你看到的。call/cc只要在执行将代码转换为 CPS 就很容易了。JavaScript 很好地支持 CPS。

为了帮助如何将代码转换为 CPS,Matt Might在他的文章中做了无数次。在该列表中寻找延续。他甚至用JavaScript做到了。

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

于 2019-06-07T21:01:34.713 回答