4 ms·

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

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.

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.