5 ms·

Unwind-protect vs. Continuations (2003)

39 points by pera 9y ago

dietrichepp 9y ago
Call/cc is powerful and simple in the sense that goto is powerful and simple. It’s possible to implement other control structures with call/cc or goto, but when you combine them it becomes difficult to reason about the program. Many years ago I was working on my own Scheme implementation. This kind of project is mostly easy, but I stopped working on it as soon as I started implementing mapcar. I just didn’t want to deal with it, and all the dirty effects of call/cc.
- convolvatron 9y ago
  maybe you insisted on using a call stack? if you don't care about the difficult to quantify performance delta just use heap allocated activation records - it all falls out pretty easily. the one thing I would never want to implement is hygenic macros, but if you steal a reference version most of the special forms get boiled away.
  - dietrichepp 9y ago
    The problem I’m referring to has nothing to do with the call stack, it’s actually a problem of semantics. “It all falls out pretty easily” does not match my experiences at all. Heap allocated, garbage collected activation records were my expectation going in. If the function passed to call/cc returns multiple times, you have to return a full result multiple times. This means something like constructing a reversed list of the results and returning a reversed copy of that list. It was at that point I realized I had no desire to work with a language that had call/cc, and I was sorely disappointed when the Scheme committee decided not to publish a Scheme subset without it. Call/cc is like dynamite. Powerful, but all the precautions you have to go through in order to use it safely negate the benefits.
    - convolvatron 9y ago
      oh wait, did you evert the expressions (turn inside out) so that each function gets passed a continuation (a function to call with the return value)? then each of the multiple returns is just another call to this implicit continuation. just saying - not trying to defend RNRS, I think they kinda wandered off into the wilderness. its also kind of sad that high level language designs get wrapped around these kinds of implementation issues when ostensibly they are abstractions well above the fray.
      - dietrichepp 9y ago
        Not really familiar with the terminology here—I don’t know what it means to “evert” an expression. Using CPS or something else doesn’t matter here because this is not a compiler issue, this is a problem with the library that stems from the language definition itself. Calling a continuation multiple times works as expected if the continuation is pure. For example, consider the following map implementation for one list: (define (map f x) (if (null? x) () (cons (f (car x)) (map f (cdr x))))) This works but creates a number of active activation records equal to the list length, which is not ideal. Attempts to optimize this are confounded by the fact that f may return multiple times—not that it’s impossible to optimize, just that multiple returns make optimization more difficult. Then consider the case for, e.g., vector-map, where the most obvious implementation does not handle multiple returns correctly in the first place, even before you optimize it. This is why I became so disinterested in Scheme.
        pflanze 9y ago
        Why didn't you conclude instead that first-class (or just multi-shot) continuations are still an experimental feature in Scheme, and that the important part is to warn users of that fact ("use at your own risk, because .. undefined ..")? Have you moved to Common Lisp instead? Edit: I agree that call/cc is pretty nasty; but at least as a debugging (and sometimes hacking) tool it can also be very useful. As a user you can always refrain from using it in regular code. Or decide to use it anyway and suffer from non-portability. So in a sense, the Scheme subset without call/cc is already there, just refrain from using call/cc or any library that uses it? (To be fair, this might be one of the reasons that impedes the growth of portable libraries, but I haven't followed the latest developments of the standardization efforts, and whether things around it are better defined now.) Edit 2: I should also note that there are Scheme implementations that implement activation records more efficiently (in some form that's closer to an array based stack, e.g. segmented stacks or a sort of delayed segmentation approach that Gambit takes), in which case the direct recursive implementation of map that you have shown is more efficient than iteration and then reversal. (And aside of being the straight-forward way to write map, this variant is also easily made into a streaming variant by just adding one |delay| into it (and a |force| for the list argument if |car| and |cdr| don't do that).) One thing I haven't pondered is how call/cc interacts with deforestation like implemented in Haskell, I have to go and experiment with that.
discardable_dan 9y ago
While I don't have a definitive formulation in mind, this seems like exactly the sort of problem that can be solved with delimited continuations by 'augmenting' any outer continuation with a code to perform the file-pointer closing. That said, I'm not certain demanding these operations use `unwind-protect` is desirable. Several dialects of Scheme use continuations for multithreading, and forcing the program to close a file handle before context-switching also seems like incorrect behavior: if I ever end up back in the file-reading context, it sure would be nice if that file was still open. The author proposes that we should indicate if we intend to do this in each continuation case (either at `call/cc` or continuation invocation time), which seems annoying and cumbersome. The alternative, then, which the author seems to ignore, is to trust the garbage collector to do the correct thing. Luckily, any BiBoP mark-and-sweep collector for Scheme [0] will almost certainly handle this situation when the file handle is out of scope (by correctly closing handles during the compacting step). 0. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4490 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4...
bjoli 9y ago
Unwind protect doesn't work when you have multi-shot continuations. The question is whether you should have multi-shot continuations. I would say yes (but delimited since they are easier to reason about and superior in every way). We could bolt on a simpler exit facility on top of call/cc with support for proper unwind protect, but it would not bring much compared to a simple macro hiding the ugly parts of dynamic wind (and of course: making sure to only use continuations once... ).
kazinator 9y ago
In TXR Lisp, I came up with a way to get (delimited) continuations to play along with unwind-protect and exceptions. The key is to regard continuations as time slices of green threads. Now in a thread, we (of course!) do not dispose of the local resources just because we have context switched to another thread! So I decided to try the same thing with continuations, and it works fairly well. I augmented the language run-time with a non-unwinding dynamic escape operator. I call the non-unwinding form of escape "absconding". The operator is abscond-from, contrasting with return-from. Using absconding, we can yield a continuation out of some contour without bailing the local resources, and then use the continuation to come back in. (This is not unlike a context switch out of and back to a thread.) All the normal call and return mechanisms in the code that we are suspending and resuming with continuations perform normal unwinding. http://nongnu.org/txr/txr-manpage.html#N-01C4E6B4 http://nongnu.org/txr/txr-manpage.html#N-01C4E6B4 It's a Solved Problem, as far as I'm concerned.
orthecreedence 9y ago
I wrote cl-async. I really missed continuations because any synchronous code that wants to use async basically has to be rewritten all the way up to accept async. This can be somewhat alleviated with promises, but it's still a rewrite no matter how you slice it. Continuations would have solved this completely by allowing first-class green threads or coroutines or whatever the hell you want to call them. There's cl-cont, which is a horribly hacky syntax macro that converts all your code to CPS and, as I remember it, kind of sidesteps proper error handling altogether. So, you can argue over which is better for error handling all you want, but I would have strangled a dolphin to have continuations/coroutines back when I was building out the async ecosystem stuff.

39 points by pera 9y ago

Call/cc is powerful and simple in the sense that goto is powerful and simple. It’s possible to implement other control structures with call/cc or goto, but when you combine them it becomes difficult to reason about the program. Many years ago I was working on my own Scheme implementation. This kind of project is mostly easy, but I stopped working on it as soon as I started implementing mapcar. I just didn’t want to deal with it, and all the dirty effects of call/cc.

convolvatron 9y ago
maybe you insisted on using a call stack? if you don't care about the difficult to quantify performance delta just use heap allocated activation records - it all falls out pretty easily. the one thing I would never want to implement is hygenic macros, but if you steal a reference version most of the special forms get boiled away.
- dietrichepp 9y ago
  The problem I’m referring to has nothing to do with the call stack, it’s actually a problem of semantics. “It all falls out pretty easily” does not match my experiences at all. Heap allocated, garbage collected activation records were my expectation going in. If the function passed to call/cc returns multiple times, you have to return a full result multiple times. This means something like constructing a reversed list of the results and returning a reversed copy of that list. It was at that point I realized I had no desire to work with a language that had call/cc, and I was sorely disappointed when the Scheme committee decided not to publish a Scheme subset without it. Call/cc is like dynamite. Powerful, but all the precautions you have to go through in order to use it safely negate the benefits.
  - convolvatron 9y ago
    oh wait, did you evert the expressions (turn inside out) so that each function gets passed a continuation (a function to call with the return value)? then each of the multiple returns is just another call to this implicit continuation. just saying - not trying to defend RNRS, I think they kinda wandered off into the wilderness. its also kind of sad that high level language designs get wrapped around these kinds of implementation issues when ostensibly they are abstractions well above the fray.
    - dietrichepp 9y ago
      Not really familiar with the terminology here—I don’t know what it means to “evert” an expression. Using CPS or something else doesn’t matter here because this is not a compiler issue, this is a problem with the library that stems from the language definition itself. Calling a continuation multiple times works as expected if the continuation is pure. For example, consider the following map implementation for one list: (define (map f x) (if (null? x) () (cons (f (car x)) (map f (cdr x))))) This works but creates a number of active activation records equal to the list length, which is not ideal. Attempts to optimize this are confounded by the fact that f may return multiple times—not that it’s impossible to optimize, just that multiple returns make optimization more difficult. Then consider the case for, e.g., vector-map, where the most obvious implementation does not handle multiple returns correctly in the first place, even before you optimize it. This is why I became so disinterested in Scheme.
      - pflanze 9y ago
        Why didn't you conclude instead that first-class (or just multi-shot) continuations are still an experimental feature in Scheme, and that the important part is to warn users of that fact ("use at your own risk, because .. undefined ..")? Have you moved to Common Lisp instead? Edit: I agree that call/cc is pretty nasty; but at least as a debugging (and sometimes hacking) tool it can also be very useful. As a user you can always refrain from using it in regular code. Or decide to use it anyway and suffer from non-portability. So in a sense, the Scheme subset without call/cc is already there, just refrain from using call/cc or any library that uses it? (To be fair, this might be one of the reasons that impedes the growth of portable libraries, but I haven't followed the latest developments of the standardization efforts, and whether things around it are better defined now.) Edit 2: I should also note that there are Scheme implementations that implement activation records more efficiently (in some form that's closer to an array based stack, e.g. segmented stacks or a sort of delayed segmentation approach that Gambit takes), in which case the direct recursive implementation of map that you have shown is more efficient than iteration and then reversal. (And aside of being the straight-forward way to write map, this variant is also easily made into a streaming variant by just adding one |delay| into it (and a |force| for the list argument if |car| and |cdr| don't do that).) One thing I haven't pondered is how call/cc interacts with deforestation like implemented in Haskell, I have to go and experiment with that.

discardable_dan 9y ago

While I don't have a definitive formulation in mind, this seems like exactly the sort of problem that can be solved with delimited continuations by 'augmenting' any outer continuation with a code to perform the file-pointer closing. That said, I'm not certain demanding these operations use `unwind-protect` is desirable. Several dialects of Scheme use continuations for multithreading, and forcing the program to close a file handle before context-switching also seems like incorrect behavior: if I ever end up back in the file-reading context, it sure would be nice if that file was still open. The author proposes that we should indicate if we intend to do this in each continuation case (either at `call/cc` or continuation invocation time), which seems annoying and cumbersome. The alternative, then, which the author seems to ignore, is to trust the garbage collector to do the correct thing. Luckily, any BiBoP mark-and-sweep collector for Scheme [0] will almost certainly handle this situation when the file handle is out of scope (by correctly closing handles during the compacting step). 0. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4490 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4...

bjoli 9y ago

Unwind protect doesn't work when you have multi-shot continuations. The question is whether you should have multi-shot continuations. I would say yes (but delimited since they are easier to reason about and superior in every way). We could bolt on a simpler exit facility on top of call/cc with support for proper unwind protect, but it would not bring much compared to a simple macro hiding the ugly parts of dynamic wind (and of course: making sure to only use continuations once... ).

kazinator 9y ago

In TXR Lisp, I came up with a way to get (delimited) continuations to play along with unwind-protect and exceptions. The key is to regard continuations as time slices of green threads. Now in a thread, we (of course!) do not dispose of the local resources just because we have context switched to another thread! So I decided to try the same thing with continuations, and it works fairly well. I augmented the language run-time with a non-unwinding dynamic escape operator. I call the non-unwinding form of escape "absconding". The operator is abscond-from, contrasting with return-from. Using absconding, we can yield a continuation out of some contour without bailing the local resources, and then use the continuation to come back in. (This is not unlike a context switch out of and back to a thread.) All the normal call and return mechanisms in the code that we are suspending and resuming with continuations perform normal unwinding. http://nongnu.org/txr/txr-manpage.html#N-01C4E6B4 http://nongnu.org/txr/txr-manpage.html#N-01C4E6B4 It's a Solved Problem, as far as I'm concerned.

orthecreedence 9y ago

I wrote cl-async. I really missed continuations because any synchronous code that wants to use async basically has to be rewritten all the way up to accept async. This can be somewhat alleviated with promises, but it's still a rewrite no matter how you slice it. Continuations would have solved this completely by allowing first-class green threads or coroutines or whatever the hell you want to call them. There's cl-cont, which is a horribly hacky syntax macro that converts all your code to CPS and, as I remember it, kind of sidesteps proper error handling altogether. So, you can argue over which is better for error handling all you want, but I would have strangled a dolphin to have continuations/coroutines back when I was building out the async ecosystem stuff.