call/cc in Lua - Possible?

Question

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.

Answer 1

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.