在Lua中拨打电话/抄送-可以吗? [英] call/cc in Lua - Possible?
问题描述
Continuation 上的Wikipedia文章说:
在任何支持 closures 的语言中，都可以以连续传递样式编写程序并手动实现call/cc ."
要么是正确的，我需要知道如何做，要么是不正确的，并且该语句需要更正.
如果是这样，请告诉我如何在Lua中实现call/cc，因为我看不到如何.
我认为，如果Lua具有有关CallCC的Wikipedia文章上的第一个示例.
方案版本
(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...
我正在使用Windows的DrScheme和Lua-对于想要帮助解决这些问题的任何人来说，都是两个易于下载和安装且有效的工具.
要按照Wikipedia报价手动实现call/cc，有两个先决条件:
- 该语言必须支持闭包
- 您必须以连续传递样式(CPS)编写程序
我怀疑您不会喜欢#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
请注意，由于*和+不在CPS中，因此上述multiplyadd实际上是作弊行为.以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:
- the language must support closures
- 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:
- Every function must take a continuation argument
- 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中拨打电话/抄送-可以吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
