[sillysaurus3]

I'm trying to add call/cc to node, or to lua.

Recap: call/cc is the ability to save the current state of a running thread, then revert to that state at a later point in time. In other words, at any point in your program, you can say "Save the current stack." It's saved as a function. Later, whenever you call that function, the current stack is thrown out, and replaced with the saved stack.

This is very useful for a number of reasons. It's also a very rare feature to have in your language.

Neither node nor lua has support for this. The closest I've found is a Lua extension which adds coroutine.clone(). In principle, this is the solution. In practice, it has a number of limitations, such as restrictions on when you're allowed to call coroutine.clone(). (For example, if your stack looks like Lua -> C -> Lua, then it won't work.)

I tried to channel my inner Mike Pall and solve this problem once and for all, but I'm not Mike Pall, and this is really hard. I was hoping you might know of any possible solution which is (a) practical, (b) cross-platform, and (c) works in all cases.

Why post this here? Because this post happens to attract exactly the kind of people that might know a way forward. There must be a way. Apologies for the off-topic comment.

[kenOfYugen]

James Long is currently playing with call/cc in JavaScript [1].

He mentioned a paper titled "Exceptional Continuations in JavaScript" [2], that describes the method he used in his implementation.

Maybe you should get in touch?

[1] https://twitter.com/jlongster/status/726259468405751808

[2] http://www.schemeworkshop.org/2007/procPaper4.pdf

[sitkack]

I assume you have read http://okmij.org/ftp/continuations/against-callcc.html

[haberman]

> if your stack looks like Lua -> C -> Lua, then it won't work.

I don't think you can safely solve this in the general case. There is a key problem I don't think you can work around.

Say your stack looks like C(1) -> Lua -> C -> Lua. The outermost C frames might not know anything about Lua (they just use some library that uses Lua as a library). Say you try to take a snapshot of this stack to create a continuation. You probably just want to snapshot the Lua -> C -> Lua part, since that is the portion of the stack representing the execution of the Lua program.

Now say all these frames return. Then the main program calls Lua again, through through a slightly different code-path, and now you have C(2) -> Lua. Say the embedded Lua program decides to resume the continuation.

Now keep in mind that the C stack is not position-independent. The C stack can contain pointers to the C stack, so when you resume, you need your resumed stack to live at exactly the same address as last time it ran. But what if C(1) and C(2) are not exactly the same size? What if we called one extra function before calling Lua the second time? It is impossible to copy the continuation's C stack back into its original position. So it's impossible to resume the continuation.

You could try to snapshot the entire C stack to get around this, including the outermost C frames. But this would be most unexpected for the C program that is using the Lua interpreter. Lua is supposed to just be a regular C library: you call a function, it does things, and then returns. It wouldn't be acceptable that calling a Lua interpreter function like lua_call() backs your entire C program to a previous state just because the embedded Lua program used a fancy feature called continuations!

There are many other things that would make this tricky at best to get working, but I think the problem above really tanks the idea completely.

[sillysaurus3]

But what if C(1) and C(2) are not exactly the same size?

Say you want to resume continuation K, which has a stack of some size N.

The current thread has a stack of size M. If M >= N, everything is fine: you can safely overwrite the current stack with K's stack.

If M < N, recurse until M >= N.

You could try to snapshot the entire C stack to get around this, including the outermost C frames.

Indeed! This is a solution.

It wouldn't be acceptable...

I like doing unacceptable things in my programs. It's the best part of programming, really.

There are a lot of solid arguments against call/cc. I think the most persuasive argument in favor of call/cc is that you become more powerful. Whatever metric you use to measure power, call/cc will improve it: Smaller code, less time spent writing code, and you can even write algorithms that you otherwise would not be able to.

Personally, I want call/cc in order to be able to use choose and fail. It's the ability to write programs that are guaranteed to never call fail(). pg explains it well:

"For example, this is a perfectly legitimate nondeterministic algorithm for discovering whether you have a known ancestor called Igor:

  Function Ig(n)
    if name(n) = ‘Igor’
      return n
    if parents(n)
      return Ig(choose(parents(n)))
    fail

The fail operator is used to influence the value returned by choose. If we ever encounter a fail, choose would have chosen incorrectly. By definition choose guesses correctly."

Call/cc makes this possible. There are a lot of fun things to do. The last few chapters of On Lisp show some particularly interesting sketches.

[haberman]

> Say you want to resume continuation K, which has a stack of some size N.

The size of the continuation's stack doesn't matter for the problem I described, it's the size of the stack "underneath" your continuation that matters (ie. C(1) and C(2) above).

If C(2) > C(1) there is no way to shrink C(2) such that the continuation's stack can be copied into the right place.

> I like doing unacceptable things in my programs. It's the best part of programming, really.

What you do in your programs is up to you! But nobody else is going to use a C library that messes with the execution state of its callers (unless that is the point of the library, which it isn't with Lua).

[sillysaurus3]

I don't understand, but I'd like to.

To create a continuation, we need to copy the entire stack, by definition. But "the stack" is just an array of bytes. It's all the bytes between the current stack pointer and the "root" stack frame. So to create a continuation, copy these bytes and stash them somewhere, then set up a longjmp target to the current instruction.

To apply a continuation, i.e. to restore the stack, we overwrite the current stack starting from the root frame. Then we longjmp to where the continuation was originally created.

It seems like this scheme should work in any situation, but perhaps I'm missing something?

loeg pointed out getcontext(3) / setcontext(3), which seems promising. It looks like a standard way to sidestep all of this bookkeeping. It appears to be a high-level interface to the operations described above.

Lua is just a language, though. It's not "for" anything in particular.

[haberman]

The Lua implementation is a C library. You invoke it by calling C functions like lua_call().

Imagine you have a C program like this:

    #include <fancylib.h>

    int main() {
      for (int i = 0; i < 10; i++) {
        printf("val[%d] = %d\n", i, fancylib_calculate(i));
      }
      fancylib_cleanup();
    }

Now imagine that internally, fancylib uses Lua. So fancylib_calculate() calls lua_call().

Now imagine that the Lua function run by fancylib decides to use continuations. When you call fancylib_calculate(0), it creates a continuation. And when you call fancylib_calculate(1), it decides to call the continuation.

If you restore the entire C stack to resume the Lua continuation, it will reset the loop in main() to i=0! Your program might end up printing val[0] over and over, in an infinite loop. This would be extremely surprising to you as the author of main(), because you were just trying to write a normal old for() loop. The Lua continuation should just restore the Lua-related stack, not the stack of the functions calling Lua!

[sillysaurus3]

If you restore the entire C stack to resume the Lua continuation, it will reset the loop in main() to i=0!

That's the point of continuations, though. That's a feature, not a bug. When you create a continuation, you're saying "whatever happens after this, allow me to do it again at some later time." If the calling library happened to be in a loop, then the goal is to serialize that loop so that it can be invoked again, at a later point.

If you keep applying the continuation in a loop, then you'll get an infinite loop. But if you invoke the continuation once, (and if subsequent calls to fancylib_calculate() don't), then you'll get the ability to print

  val[0] = 42
  val[1] = 99
  ...
  val[9] = 7

on demand. By invoking the continuation, you cause the loop to happen again.

In fact, you gain the ability to prevent the program from terminating, in a controlled fashion. Since you have access to the continuation, you can choose to invoke it on the 10th call to fancylib_calculate(), up to 3 times in a row. That would produce output like:

  val[0] = 42
  val[1] = 99
  ...
  val[9] = 7
  val[0] = 42
  val[1] = 99
  ...
  val[9] = 7
  val[0] = 42
  val[1] = 99
  ...
  val[9] = 7

then the program would exit.

Does that make sense? Apologies if we're talking past each other. I appreciate the patience.

[daurnimator]

When using lua_pcall (in 5.2 and above) you can provide a continuation function. Would that solve the dilemma?

[im3w1l]

What about references to resources not on the stack? Heap pointers, file descriptors?

[aktau]

I'm sure you aware you can implement call/1cc with Lua's coroutines: http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf. But maybe you want the full power of call/cc :).

[to3m]

If you want to actually clone the stack, you're probably stuck.

If you want to use this to do something that takes multiple invocations of lua_resume to complete without the calling Lua code being aware, you might be able to use lua_yieldk.

[loeg]

getcontext(3) / setcontext(3). Not standard, but exists in both Linux and FreeBSD.