ansaurus

Question

Answer 1

+9 A:

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.

Roberto Ierusalimschy 2010-05-13 16:04:12

First of all, it's an honor to have you reply to my question. I am completely in love with your language, for many many reasons (small core, C integration, very consistent grammar, real closures, first class functions, etc).Now on to the answer: that PS clarifies a lot. Would it be impolite if I asked for an example implementation of call/cc in Lua being that Lua allows for both closures and tail-call optimization? :)

Pessimist 2010-05-13 16:25:19

I agree with Norman Ramsey's reply below. I guess a better question would be, are there any plans of implementing first-class continuations and thus callcc in Lua? ;)

Pessimist 2010-05-14 06:30:09

Wow! Mr. Ierusalimschy, welcome to the StackOverflow!

Alexander Gladysh 2010-05-14 08:15:46

Please see EDIT 1 above.

Pessimist 2010-05-14 14:50:57

@Roberto: Good point. I've edited Wikipedia to clarify on proper tail calls. The article on "tail recursion" is appalling...

Norman Ramsey 2010-05-14 23:48:36

Answer 2

+6 A:

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.

Doug Currie 2010-05-13 16:28:08

Wow, you got me really close to understanding this. Can you expand on the definition for the callcc function? Especially by explaining the part that allows it to remember save/remember all the state like Scheme's call/cc does.

Pessimist 2010-05-13 16:37:03

I guess I'm having trouble how one would use this callcc function - in Scheme you have to set a place for call/cc to jump to, but in CPS you don't... this is throwing me off I think.

Pessimist 2010-05-13 16:43:45

Since k is the closure that callcc will return to, passing it to its argument f accomplishes call/cc's job [I just edited my definition above since I forgot to return properly]. It is trivial when the program is in CPS because the continuation is always available; in Scheme its hidden, and call/cc's job is harder (at the language level, the implementation may be just as trivial in the compiler) since it has to "reify" the continuation.

Doug Currie 2010-05-13 17:25:45

Ok, now is that callcc definition of yours equivalent to Scheme's? Meaning, is that the function that captures the continuation so I can invoke it later? I've always thought that the name "callcc" was misleading (at least for the way it's used in Scheme).

Pessimist 2010-05-14 00:42:53

Yes, the callcc is equivalent to Scheme's with the exception that the continuation is as explicit argument (since the program is in CPS) rather than an implicit argument (since Scheme uses direct style).

Doug Currie 2010-05-14 02:14:46

is callcc really "return k(f(k))" or is it "return f(k(k))" ? I can't find any references to the former, but I found a few references to the latter: Kalani's comment here: http://blog.lab49.com/archives/893 and the second PDF link ("principles of programming languages") on the google result page that you get when looking for "callcc f k" (with the quotes).

Pessimist 2010-05-18 15:43:13

please substitute the above "or is it return f(k(k)) ?" for this text:or is it (haskell notation now) "callcc f k = (f k) k" (same as "callcc f k = f k k") ?

Pessimist 2010-05-18 16:00:39

@Pessimist, yes, the function f needs both a continuation and an argument; I was thinking in a hybrid of direct and CPS (probably because I was using non-CPS operators in the multiplyadd example). So it should be "return f(k,k)" -- I've edited my answer. Of course all of this is convention. Any function in CPS can get its continuation from its first argument, so callcc is redundant/unnecessary.

Doug Currie 2010-05-18 17:02:46

Answer 3

+3 A:

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.

Norman Ramsey 2010-05-13 21:27:49

You might not want to write entire applications using CPS, but it's entirely practical to implement individual algorithms to solve subproblems this way.

2010-05-18 17:06:12

Answer 4

+2 A:

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.

Roberto Ierusalimschy 2010-05-14 16:56:09

I can understand that. Any plans for a coroutine.clone, then, like the one implemented by Mike Pall on the link in my original post?

Pessimist 2010-05-15 00:08:58

For a working example of callcc in Lua, using a modified Lua that implements coroutine.clone, see this: http://github.com/torus/lua-call-cc/blob/master/callcc.lua . I'll be trying it out shortly. :)

Pessimist 2010-05-15 16:37:14

ansaurus

tags:

views:

answers:

call/cc in Lua - Possible?

related questions