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.
Answering the question about plans for call/cc in Lua: There are no plans for call/cc in Lua. Capturing a continuation is either too expensive or require some code analsis well beyond what the Lua compiler can do. There is also the problem that Lua continuations may include parts in C.
With coroutines, however, we can already implement call/cc1 in Lua (one-shot continuations). That is good enough for many uses of continuations.
I guess you forgot the part about writing your program in continuation passing style. Once you do that, call/cc is trivial (in Lua or in any other language), as the continuation will be an explicit parameter to all functions (call/cc included).
PS: besides closures, you also need proper tail calls to program in continuation passing style.
There are two prerequisites to manually implement call/cc per the Wikipedia quote:
I suspect you will not like #2.
To write your program in continuation passing style:
So, using
k
as the name of the continuation argument, a function would look like:The toplevel might use
print
as its continuation, so invokingmultiplyadd
at top level would look like:With that scaffolding we could define call/cc as
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.Here's my cps-convert in scheme, just pass it every function you want to convert.
The key phrase is
(Emphasis mine.) You do this by taking regular "direct-style" programs and converting them to continuation-passing style (CPS) by a program transformation called the CPS transform. The key is that the CPS transform of
call/cc
is a simple function.This is not practical for programmers. The CPS transform has two uses:
You don't want to go anywhere near doing CPS transforms on Lua code, especially not by hand.