undefined | Better HN

0 pointssillysaurus310y ago0 comments

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.

0 comments

haberman10y ago

> 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).

sillysaurus3OP10y ago

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.

haberman10y ago

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!

2 more replies

im3w1l10y ago

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

j / k navigate · click thread line to collapse

0 comments

haberman10y ago

> 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.

sillysaurus3OP10y ago

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

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?

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

haberman10y ago

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().

2 more replies

im3w1l10y ago

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

j / k navigate · click thread line to collapse