7

我用 C# 编写了一个小型 Scheme 解释器，并意识到我实现它的方式很容易添加对正确延续的支持。

所以我添加了它们......但想“证明”我添加它们的方式是正确的。

然而，我的 Scheme 解释器不支持“变异”状态——一切都是不可变的。

所以很容易编写一个单元测试来暴露“向上”的延续：

AssertEqual(Eval("(call/cc (lambda (k) (+ 56 (k 3))))"), 3);

但是，我还想编写一个单元测试来证明如果延续“转义”，那么它仍然有效：

AssertEqual(Eval("(call/cc (lambda (k) k))", <some continuation>);

但是，当然，上面只是测试“我得到了一个延续”......并不是说它实际上是一个有效的延续。

然而，我能找到的所有示例最终总是使用“set！”。来证明逃脱的延续。

什么是最简单的方案示例，它演示了在不依赖突变的情况下对向后延续的适当支持？

没有突变的向后延续有什么用吗？我开始怀疑它们不是，因为您只能使用它再次执行完全相同的计算……如果没有副作用，这将毫无意义。这就是 Haskell 没有延续的原因吗？

4

4 回答 4

8

我不知道这是否是最简单的，但这里有一个使用向后延续而不调用set!或类似的示例：

(apply
  (lambda (k i) (if (> i 5) i (k (list k (* 2 i)))))
  (call/cc (lambda (k) (list k 1))))

这应该评估为8。

更有趣的是：

(apply
  (lambda (k i n) (if (= i 0) n (k (list k (- i 1) (* i n)))))
  (call/cc (lambda (k) (list k 6 1))))

计算6!（也就是说，它应该评估为720）。

您甚至可以使用以下方法做同样的事情let*：

(let* ((ka (call/cc (lambda (k) `(,k 1)))) (k (car ka)) (a (cadr ka)))
      (if (< a 5) (k `(,k ,(* 2 a))) a))

（伙计，stackoverflow 的语法突出显示在方案上大量失败。）

于 2009-06-11T22:03:32.603 回答
2

我认为你是对的——没有突变，向后延续没有向前延续做不到的事情。

于 2009-06-11T21:39:39.027 回答
0

这是我想出的最好的：

AssertEqual(Eval("((call/cc (lambda (k) k)) (lambda (x) 5))", 5);

并不奇怪，但它是一个向后的延续，然后我用我希望调用的实际函数“调用”它，一个返回数字 5 的函数。

啊，我也想出了一个很好的单元测试用例：

AssertEqual(Eval("((call/cc call/cc) (lambda (x) 5))", 5);

我同意 Jacob B 的观点——我认为如果没有可变状态，它不会那么有用……但仍然会对反例感兴趣。

于 2009-06-11T22:05:24.440 回答
0

功能线程：

您可以使用递归循环来更新状态而不会发生突变。包括要调用的下一个延续的状态。现在这比给出的其他示例更复杂，但您真正需要的只是thread-1andmain循环。另一个线程和“更新”函数表明延续可以用于一个简单的例子。此外，为了使这个示例正常工作，您需要一个名为 let 的实现。这可以翻译成用define 语句制作的等价形式。

例子：

(let* ((update (lambda (data) data))                ;is identity to keep simple for example
       (thread-1                                    
         (lambda (cc)                               ;cc is the calling continuation
           (let loop ((cc cc)(state 0))
             (printf "--doing stuff       state:~A~N" state)
             (loop (call/cc cc)(+ state 1)))))      ;this is where the exit hapens
       (thread-2
         (lambda (data)                             ;returns the procedure to be used as 
           (lambda (cc)                             ;thread with data bound
             (let loop ((cc cc)(data data)(state 0))
               (printf "--doing other stuff state:~A~N" state)
               (loop (call/cc cc)(update data)(+ state 1)))))))
  (let main ((cur thread-1)(idle (thread-2 '()))(state 0))
    (printf "doing main stuff    state:~A~N" state)
    (if (< state 6)
        (main (call/cc idle) cur (+ state 1)))))

哪个输出

doing main stuff    state:0
--doing other stuff state:0
doing main stuff    state:1
--doing stuff       state:0
doing main stuff    state:2
--doing other stuff state:1
doing main stuff    state:3
--doing stuff       state:1
doing main stuff    state:4
--doing other stuff state:2
doing main stuff    state:5
--doing stuff       state:2
doing main stuff    state:6
于 2016-04-24T01:23:44.983 回答