Lua 中的 call/cc - 可能吗? [英] call/cc in Lua - Possible?

问题描述

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

要么是真的，我需要知道怎么做，要么不是真的，该说法需要更正.

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

我想如果 Lua 有 coroutine.clone 函数，我就可以手动实现 call/cc，如 此处.

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

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

编辑 1: 好吧，大家帮帮我，这花了我很长时间，因为我不知道任何 Scheme，但我想出了一些应该可以帮助我们的东西.请看下面的代码.第一个是 Scheme 中的程序，第二个是 Lua 中的相同程序.
希望这能帮到我们.我相信我们非常接近.

PS:这些示例取自 关于 CallCC 的维基百科文章.方案版本

(定义 call/cc call-with-current-continuation);callcc CPS 转换(感谢 freenode.net 上 #scheme 频道的人们)(定义cpscallcc(λ(消费者 k)(让 ((cc (lambda (result) (k 结果))))(消费者cc k))));这是我们将用来显示返回"值的延续(定义主延续(拉姆达(结果)(显示-->")(显示结果)(新队)));定义 f 函数非 CPS(定义(f 返回)(返回 2)3);这些是我过去定义 CPS f 函数的尝试;(定义(cps-f返回k);(k (返回 2)) 3);(定义(cps-f返回k);(k(λ();(返回 2);3)));这就是我想出的 - 我不确定这是否是正确的 CPS 转换，但我相信是这样(定义(cps -f 返回 k)(返回 2)(k 3));调用非 CPS f 函数(显示(f(拉姆达(x)x)))；显示 3(新队);用 call/cc 调用非 CPS f 函数(我不明白这是做什么的)(显示(呼叫/抄送 f))；显示 2(新队);现在调用 f 函数的 CPS 版本(cps-f (lambda (x) x) main-continuation) ;显示 -->3;现在使用 call/cc 的 CPS 版本调用 f 函数的 CPS 版本(cpscallcc cps-f main-continuation) ;显示 -->2 但随后它也显示 -->3 之后 ->我不确定为什么它之后会显示 3，因为它应该只显示 2，就像上面的非 CPS 版本一样

Lua 版本

-- callcc CPS-versioncpscallcc = 函数(消费者，k)本地 cc = 函数(结果)返回 k(result) -- ? 或 k(result)结尾返回消费者(cc, k) -- ? 或返回消费者(cc,k)结尾-- 定义 f 函数非 CPSf = 函数(ret)返回(2)返回 3结尾-- 定义 f 函数 CPS-version(同样，不确定这是否正确)cps_f = 函数(ret，k)返回(2)k(3)结尾-- 调用非 CPS f 函数打印(f(函数(x)返回x结束))-- 我们不能用 callcc 调用非 CPS f 函数，因为-- Lua 没有 callcc，但下面一行显示了正确的预期输出(可能是偶然的)--cpscallcc(f, 打印)-- 现在调用 CPS 版本的 f 函数cps_f( function(x) return x end, print ) -- 显示 3;现在使用 call/cc 的 CPS 版本调用 f 函数的 CPS 版本cpscallcc( cps_f, print) -- 显示 2 然后显示 3 就像 Scheme 版本一样！！- 显然，从 Scheme 到 Lua 的翻译是正确的......

我在 Windows 上使用 DrScheme 和 Lua - 对于任何想要帮助解决这些问题的人来说，这是两个易于下载和安装的工具.

解决方案

根据维基百科的引用，手动实现 call/cc 有两个先决条件:

1. 语言必须支持闭包
2. 您必须以连续传递风格 (CPS) 编写程序

我怀疑你不会喜欢#2.

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

1. 每个函数都必须有一个延续参数
2. 函数必须通过调用其延续来返回

因此，使用 k 作为继续参数的名称，函数将如下所示:

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是非常繁琐的；请参阅详情.

The Wikipedia article on Continuation says:
"In any language which supports closures, it is possible to write programs in continuation passing style and manually implement call/cc."

Either that is true and I need to know how to do it or it is not true and that statement needs to be corrected.

If this is true, please show me how to implement call/cc in Lua because I can't see how.

I think I'd be able to implement call/cc manually if Lua had the coroutine.clone function as explained here.

If closures are not enough to implement call/cc then what else is needed?

The text below is optional reading.
P.S.: Lua has one-shot continuations with its coroutine table. A coroutine.clone function would allow me to clone it to call it multiple times, thus effectively making call/cc possible (unless I misunderstand call/cc). However that cloning function doesn't exist in Lua. Someone on the Lua IRC channel suggested that I use the Pluto library (it implements serialization) to marshal a coroutine, copy it and then unmarshal it and use it again. While that would probably work, I am more interested in the theoretical implementation of call/cc and in finding what is the actual minimum set of features that a language needs to have in order to allow for its manual implementation.

EDIT 1: Ok people, help me out here, this took me a long time because I don't know any Scheme, but I came up with something that should help us out. Please look at the codes below. The first one is a program in Scheme, the second one is the same program but in Lua.
Hopefully this will help us out. I believe we are very close.

P.S.: These examples are taken from the first example on the Wikipedia article on CallCC. Scheme version

(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 version

-- 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...

I'm using DrScheme and Lua for Windows - for anyone that wants to help up out those are two easy to download and install tools that just work.

解决方案

There are two prerequisites to manually implement call/cc per the Wikipedia quote:

1. the language must support closures
2. you must write your program in continuation passing style (CPS)

I suspect you will not like #2.

To write your program in continuation passing style:

1. Every function must take a continuation argument
2. Functions must return by calling their continuation

So, using k as the name of the continuation argument, a function would look like:

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

The toplevel might use print as its continuation, so invoking multiplyadd at top level would look like:

multiplyadd(print, 2, 4, 1)

With that scaffolding we could define call/cc as

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

Note that the above multiplyadd actually cheats since * and + are not in CPS. It is very tedious to add all the operators in CPS form, replace all the Lua library functions with CPS equivalents, and translate/generate all your code to CPS; see details here.

这篇关于Lua 中的 call/cc - 可能吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！