title: call/cc in Lua - Possible?
body: <p>The Wikipedia article on <a href="http://en.wikipedia.org/wiki/Continuation" rel="noreferrer">Continuation</a> says:<BR>
  "In any language which supports <strong>closures</strong>, it is possible to write programs in continuation passing style and <strong>manually implement call/cc</strong>."<BR><BR>
  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.<BR><BR>
  If this is true, please show me how to implement call/cc in Lua because I can't see how.<BR><BR>
  I think I'd be able to implement call/cc manually if Lua had the coroutine.clone function as explained <a href="http://lua-users.org/lists/lua-l/2006-01/msg00652.html" rel="noreferrer">here</a>.<BR><BR>
  If closures are not enough to implement call/cc then what else is needed?</p>
  
  <p><strong>The text below is optional reading.</strong><BR>
  <em>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.</em></p>
  
  <p><strong>EDIT 1:</strong> 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. <BR>Hopefully this will help us out. I believe we are <strong>very</strong> close.<BR><BR>
  P.S.: These examples are taken from the first example on <a href="http://en.wikipedia.org/wiki/Call-with-current-continuation" rel="noreferrer">the Wikipedia article on CallCC</a>.
  <B>Scheme version</B></p>
  
  <pre><code>(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 "--&gt; ")
      (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 --&gt; 3
  
  ; now call the CPS version of the f function with the CPS version of call/cc
  (cpscallcc cps-f main-continuation)  ; displays --&gt; 2 but then it also displays --&gt; 3 afterwards -&gt; I'm not sure why it displays the 3 afterwards, as it should only display the 2 just like the non-CPS versions above
  </code></pre>
  
  <p><BR><BR>
  <B>Lua version</B></p>
  
  <pre><code>-- 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...
  </code></pre>
  
  <p><BR><BR>
  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.</p>