呼叫/ cc在Lua - 可能吗？

Question

关于Continuation的维基百科文章说:
"在任何支持闭包的语言中,都可以用连续传递方式编写程序并手动实现call/cc."

这是真的,我需要知道如何做或不是真的,这个陈述需要纠正.

如果这是真的,请告诉我如何在Lua中实现call/cc,因为我看不清楚如何.

我想我能够实现来电/立方厘米,如果手动Lua中有coroutine.clone功能解释在这里.

如果闭包不足以实现call/cc那么还需要什么呢？

以下文字是可选阅读.
PS:Lua与其协程表一次性延续.一个coroutine.clone函数允许我克隆它多次调用它,从而有效地使call/cc成为可能(除非我误解了call/cc).但是Lua中不存在克隆功能.Lua IRC频道上的某个人建议我使用Pluto库(它实现序列化)来编组协程,复制它然后解组它并再次使用它.虽然这可能会奏效,但我更感兴趣的是call/cc的理论实现,以及查找语言需要具有的实际最小特征集以便允许其手动实现.

编辑1:好的人,帮我在这里,这花了我很长时间,因为我不知道任何计划,但我想出了一些应该帮助我们的东西.请看下面的代码.第一个是Scheme中的程序,第二个是相同的程序,但在Lua中.
希望这会帮助我们.我相信我们非常接近.

PS:这些例子来自关于CallCC的维基百科文章的第一个例子. 方案版

(define call/cc call-with-current-continuation)

; callcc CPS-transformed (thanks to the people from the #scheme channel at freenode.net)
(define cpscallcc
  (lambda (consumer k)
    (let ((cc (lambda (result) (k result))))
      (consumer cc k))))

; this is the continuation we will use to display the "returned" values
(define main-continuation
  (lambda (result)
    (display "--> ")
    (display result)
    (newline)))

; define f function non-CPS
(define (f return)
  (return 2)
  3)

; these are my past attempts at defining a CPS f function
;(define (cps-f return k)
;  (k (return 2)) 3)
;(define (cps-f return k)
;  (k (lambda ()
;       (return 2)
;       3)))

; this is what I came up with - I'm not sure if this is correctly CPS-transformed but I     believe so
(define (cps-f return k)
  (return 2)
  (k 3))

; call the non-CPS f function
(display (f (lambda (x) x))) ; displays 3
(newline)

; call the non-CPS f function with call/cc (I don't understand what this does)
(display (call/cc f)) ; displays 2
(newline)

; now call the CPS version of the f function
(cps-f (lambda (x) x) main-continuation)  ; displays --> 3

; now call the CPS version of the f function with the CPS version of call/cc
(cpscallcc cps-f main-continuation)  ; displays --> 2 but then it also displays --> 3 afterwards -> I'm not sure why it displays the 3 afterwards, as it should only display the 2 just like the non-CPS versions above

Lua版

-- callcc CPS-version
cpscallcc = function(consumer, k)
    local cc = function(result)
        return k(result)  -- ?or k(result)
    end
    return consumer(cc, k)  -- ?or return consumer(cc,k)
end

-- define f function non-CPS
f = function(ret)
    ret(2)
    return 3
end

-- define f function CPS-version (again, not sure this is correct)
cps_f = function(ret, k)
    ret(2)
    k(3)
end

-- call the non-CPS f function
print(f(function(x) return x end))

-- we cant call the non-CPS f function with callcc because
-- Lua doesnt have callcc, but the line below displays the correct expected output (maybe by accident)
--cpscallcc(f, print)

-- now call the CPS version of the f function
cps_f( function(x) return x end, print )  -- displays 3

; now call the CPS version of the f function with the CPS version of call/cc
cpscallcc( cps_f, print) -- displays 2 and then 3 just like the Scheme version!!
-- so apparently the translation from Scheme to Lua is correct...

我正在使用DrScheme和Lua for Windows - 对于任何想要帮助它们的人来说,这两个是易于下载和安装的工具.

Answer 1

根据Wikipedia引用手动实现call/cc有两个先决条件:

1. 语言必须支持闭包
2. 你必须用延续传递方式(CPS)编写你的程序

我怀疑你不会喜欢#2.

以延续传递方式编写程序:

1. 每个函数都必须采用延续参数
2. 函数必须通过调用它们的继续来返回

因此,使用kcontinuation参数的名称,函数将如下所示:

function multiplyadd(k, x, y, z) return k(x * y + z) end

顶层可能会print用作它的延续,因此multiplyadd在顶层调用看起来像:

multiplyadd(print, 2, 4, 1)

使用该脚手架,我们可以将call/cc定义为

function callcc(k,f) return f(k,k) end

需要注意的是,上述multiplyadd因为实际上骗子*并+没有在CPS.以CPS形式添加所有运算符,用CPS等价物替换所有Lua库函数,并将所有代码转换/生成到CPS是非常繁琐的; 看这里的细节.

Answer 2

我猜你忘记了以延续传递方式编写程序的部分.一旦你这样做,call/cc是微不足道的(用Lua或任何其他语言),因为continuation将是所有函数的显式参数(包括call/cc).

PS:除了闭包之外,你还需要适当的尾调用以延续传递方式编程.

Answer 3

回答有关Lua电话/ cc计划的问题:Lua没有打电话/ cc的计划.捕获延续要么过于昂贵,要么需要一些代码分析,远远超出Lua编译器的功能.还有一个问题是Lua延续可能包含C中的部分.

但是,使用协同程序,我们已经可以在Lua中实现call/cc1(一次性连续).这对于延续的许多用途来说已经足够了.