时间戳

首页 > 解决方案 > 如何在 CPS 中编写 `(if (null?x​​) (quote ()) (cdr x))`？

scheme - 如何在 CPS 中编写 `(if (null?x​​) (quote ()) (cdr x))`？

问题描述

方案编程语言说

因此，在任何表达式的求值过程中的任何时候，都有一个延续准备完成，或者至少继续，从那个点开始计算。让我们假设x具有值(a b c)。我们可以在评估的过程中隔离六个延续(if (null? x) (quote ()) (cdr x))——等待的延续

  1. 的值(if (null? x) (quote ()) (cdr x))，
  2. 的值(null? x)，
  3. 的值null?，
  4. 的值x，
  5. 的值cdr，和
  6. x（再次） 的价值。

的继续(cdr x)没有列出，因为它与等待的相同(if (null? x) (quote ()) (cdr x))。

我想知道如何(if (null? x) (quote ()) (cdr x))在CPS中编写？

只能在 CPS 中重写过程调用吗？

标签： schemecontinuationscontinuation-passing

解决方案

挑战(if (null? x) (quote ()) (cdr x))在于它真的什么也没做。例如。如果我把它放在一个 R6RS 程序中并运行它，什么都不会发生。因此我建议我们写它：

(display (if (null? x) (quote ()) (cdr x)))

并假设这是除x已定义之外的整个程序。现在if需要知道 的值(null? x)来确定它是结果还是替代。例如。

(null?& x
        continuation)

延续需要确定它是否为真并执行以下两个延续之一：

(null?& x
        (lambda (xn)
          (if& xn
               continuation-consequent
               continuation-alternative)))

如果xn为真，则应显示继续'()，但如果不是，则应显示以下cdr内容x：

(null?& x
        (lambda (xn) ; 201
          (if& xn
               (lambda () ; 202 
                 (display& '() halt)
               (lambda () ; 203 
                 (cdr& x (lambda (cdrx) ; 204
                           (display& cdrx halt)))))))

halt停止程序。现在让我们想象一下我们将其翻译为 Algol，例如。JS。我将切换顺序，以便继续始终是第一个参数。所有的过程都只是得到一个数字 id，所以实现语言根本不需要过程。

const undef = "BaNaNa";
const x = [1, 2, 3]; // change this
const stack = [200];
main:
  while (true) {
    const cont = stack.pop();
    const cont2 = cont < 200 ? stack.pop() : undef;
    switch (cont) {
      case 1: // null?&
        stack.push(stack.pop().length === 0, cont2);
        break;
      case 2: // display&
        console.log(stack.pop());
        stack.push(undef, cont2);
        break;
      case 3: // cdr&
        stack.push(stack.pop().splice(1), cont2);
        break;
      case 4: // if&
        const cont3 = stack.pop();
        if (stack.pop()) {
          stack.push(cont2);
        } else {
          stack.push(cont3);
        }
        break;
        // continuations
      case 200:
        stack.push(x, 201, 1);
        break;
      case 201:
        stack.push(203, 202, 4);
        break;
      case 202:
        stack.push([], 1337, 2);
        break;
      case 203:
        stack.push(x, 204, 3);
        break;
      case 204:
        stack.push(1337, 2);
        break;
        // halt     
      case 1337:
        break main;
    }
  }

现在我们确实错过了用户指定的过程和闭包约定，这两者都会使这个示例稍微复杂一些。有一些缺失的类型检查一个正确的方案会完成，我使用数组而不是真正的对。

推荐阅读