如何在方案中使用延续? [英] How to use continuations in scheme?

问题描述

我正在尝试了解Scheme中的call/cc运算符.我打算在我的JavaScript Lisp中实现这一点.这是我的简单代码:

I'm trying to understand call/cc operator in Scheme. I'm planing of implementing this in my JavaScript lisp. This is my simple code:

(letrec ((x 0)
         (f (lambda (r)
                (set! x r)
                (display (r 20))
                (display "10"))))
   (display (call/cc f))
   (x "30"))

我很坚决地应该先打印20，然后再打印30，然后再打印10.但是它会产生无限循环(继续打印30).该代码应如何显示3个值，调用3次显示?

I tough that it should print 20 then 30 then 10. But it create infinite loop (it keep printing 30). How this code should look like to display 3 values, call display 3 times?

是否有可能创建不消耗连续堆栈的循环?

Should it be possible to create loops that don't consume stack with continuations?

我在堆栈溢出上找到了一些示例，但这根本不起作用:

I've found some example on stack overflow but this one don't work at all:

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

它冻结了具有100％CPU的guile解释器，看起来它正在等待输入.

it freezes the guile interpreter with 100% CPU and it look it waiting for input.

推荐答案

您是否通过Lisp实现将用户代码转换为连续传递样式?在这种情况下，很容易感到不快. call/cc是这个:

Does you lisp implementation transform user code to continuation passing style? In that case it is easy peasy. call/cc is this:

(define (call/cc& f& continuation)
  (define (exit& value actual-continuation)
    (continuation value))
  (f& exit& continuation))

看看您的第一个代码，我想它变成了这样的东西:

Looking at your first code I think it becomes something like this:

((lambda (x k)
   ((lambda (f k)
      (call/cc& f (lambda (v) ; continuation a
                    (display& v (lambda (_) ; continuation b
                                  (x "30" k))))))
    (lambda (r k)
      (set!& x r (lambda (_) ; continuation c
                   (r 20 (lambda (v) ; continuation d
                           (display& v (lambda (_) ; continuation e
                                         (display& "10" k))))))))
    k)
   0
   halt)

这是怎么回事:

• 我们制作x和f
• call/cc&调用f
• x设置为r(续a)
• r以20作为值被调用
• continuation c被忽略，取而代之的是a继续为20
• 显示20，然后调用延续b
• b用<30>调用x
• 连续性k被忽略，取而代之的是连续性30.
• 显示30，然后调用延续b
• 转到"b呼叫"c1>"，其中"30"排成三行并继续

• We make x and f
• call/cc& calls f
• x is set to r (continuation a)
• r gets called with 20 as value
• continuation c is ignore, instead continuation a is called with 20
• 20 gets displayed, then continuation b gets called
• b calls x with "30"
• continuation k is ignored, instead continuation a is called with 30
• 30 gets displayed, then continuation b gets called
• go to "b calls x with "30" 3 lines up and continue

因此，打印"20"，然后永远显示"30"对于此代码来说是正确的结果.重要的是要注意，它会从不显示"10"，因为它调用了r并传递了延续，但是却绕过了call/cc原始延续，即延续a.

So print "20", then "30" forever seems to be the correct result for this code. It's important to notice that it will never display "10" since it calls r and passes the continuation but it gets circumvented to call/cc original continution which is continuation a.

关于实现.在所有Scheme实现都将代码转换为连续传递样式之前是很普遍的，但如今，仅执行所需的部分已变得更为普遍.例如. Ikarus不会执行CPS，但要使call/cc正常工作，需要执行此操作，直到下一个继续提示.

As for implementations. Before it was quite common for all Scheme implementations to just transform the code to continuation passing style, but today it's more common to only do the parts which are required. Eg. Ikarus does not do CPS, but in order for call/cc to work it needs to do it until the next continuation prompt.

开始时最好不带突变地查看call/cc.例如.

It's probably better to look at call/cc without mutation in the beginning. eg.

(+ 2 (call/cc (lambda (exit)
                (+ 3 (* 5 (exit 11))))))

现在变成:

(call/cc& (lambda (exit k)
            (exit 11 (lambda (v)
                       (*& 5 v (lambda (v)
                                 (+& 3 v k))))))
          (lambda (v)
            (+& 2 v repl-display)))

现在我们知道exit被调用了，因此整个事情变成了:

Now we know exit gets called and thus this whole thing turns into:

((lambda (v) (+& 2 v repl-display)) 11)

哪个显示13.现在将延续作为最后一个论点在纸面上看起来不错.在要支持varargs的实现中，最好将延续性作为第一个参数.

Which displays 13. Now having the continuation as last argument looks good on paper. In an implementation that wants to support varargs it's probably best that the continuation is the first argument.

所有延续都是尾调用，因此堆栈永远不会增长.实际上，如果使用了完整的CPS，则您永远都不必返回.在程序停止之前，所有有趣的事情总是传递给下一个调用.

All continuations are tail calls and thus the stack is never grown. In fact if full CPS is used you never have to return ever. Everything interesting is always passed to the next call until the program halts.

这篇关于如何在方案中使用延续?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！