没有显式突变的方案中向后延续的最简单示例

Question

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

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

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

因此，编写一个单元测试来公开“向上”延续非常容易：

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

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

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

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

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

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

向后延续在没有变异的情况下有什么用吗？ 我开始怀疑它们不是，因为你只能用它来再次执行完全相同的计算......如果没有副作用，这是没有意义的。 这就是 Haskell 没有延续的原因吗？

Answer 1

我不知道这是否是最简单的，但这里有一个使用向后延续的示例，无需调用 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 的语法高亮在方案上严重失败。）

Answer 2

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

Answer 3

这是我想出的最好的：

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

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

啊，我也想到了以此作为一个很好的单元测试用例：

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

我同意 Jacob B - 我认为如果没有可变状态它就没那么有用......但仍然对反例感兴趣。

Answer 4

函数线程：

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

示例：

(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