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.

Answer 2

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.

Answer 3

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.

Answer 4

The key phrase is

It is possible to implement programs in continuation-passing style

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

• As a theoretical idea for studying language features, especially control operators
• As a pass in a compiler that uses CPS as an intermediate language

You don't want to go anywhere near doing CPS transforms on Lua code, especially not by hand.

Answer 5

it's possible: TypeScript-to-Lua Compiler https://github.com/roblox-ts/roblox-ts + call-cc in JS https://github.com/zaoqi/callcc.js/blob/master/callcc.js

Answer 6

Here's my cps-convert in scheme, just pass it every function you want to convert.

(define (cps-convert function . functions)
  # Since "help" is called at 2 different places...
  (define (help) (error "syntax: (cps-convert f1 f2 ...)"))
  # Single function converter
  (define (convert func)
    # "name" contains the function's name prefixed with "cps-"
    (let ([name (string->symbol
                          (string-append "cps-" (symbol->string func)))])
      # Dirty hack to define "cps-*" in the global environment
     `(eval '(begin
                   # Necessary to prevent the function from being evaluated
                   (define ,name #f)
                                # Magic
                   (set! ,name (lambda (k . args) (k (func args)))))
                 # Global environment
                 (interaction-environment))))
  # Prerequisite... Call help if condition not met
  (if (symbol? function)
      # function is a symbol
      (cond
        # If there is only one function to convert
        [(null? functions) (convert function)]
        # Else ensure every other "functions" are symbols and convert each
        [(every symbol? functions) (apply convert function functions)]
        # Oops! Condition not met!
        [else (help)])
      # Else clause from previous "if"
      (help)))