4 ms·

I never got the hang of 99% of explanations of call/cc. Very simple explanation: continuations are goto/jumping. Simple explanation: continuations are goto/j

by mafribe 11y ago

I never got the hang of 99% of explanations of call/cc. Very simple explanation: continuations are goto/jumping. Simple explanation: continuations are goto/jumping where a value is passed from the place of jumping to the place being jumped goes to. Explanation: continuations implement goto/jumping where a value is passed to wherever the jump goes to. The call/cc command does three things: (1) create and name a place to jump to, (2) hide this place from the outside, and (3) provide a function that accepts the value passed upon being jumped to. The throw command jumps to the state place and carries the value to be passed in jumping.

sago 11y ago
It's a very simple explanation, which is partly true, but misses the point of what the continuation is. You've described the effect of resuming a continuation, but not the continuation itself. I can store a continuation in a variable, for example, or pass it to a function. I can't do that with goto. It's also not really like a label you might go to, since it isn't the target, but the whole call stack. No offence, but I'll stick with my version, since it describes what is actually happening, and how to implement it.
- mafribe 11y ago
  Well what does 'goto' do when you are jumping non-locally? If you don't save the calling environment, you are trashing the call-stack leading to undefined behaviour. So this is not really even goto, it's a desaster ... That's why the C/C++ equivalent of non-local goto, namely setjmp-longjmp, does indeed save the calling environment. You cannot have non-local goto in a language with a call-stack otherwise. In that sense, the callcc / throw combination is like goto, with the addition that the place you are jumping to (declared in callcc) is hidden from the outside. Likewise exceptions in C++ are a form of non-local jump (albeit dynamically bound, unlike goto and call/cc) and they do clean up the stack. In my drive to give a simple explanation of call/cc, I clearly oversimplified. I should have made it more clear that I'm talking about semantically meaningful non-local goto in a language with a call-stack. Thanks for pointing this out, sorry for the confusion.
  - sago 11y ago
    I wasn't trying to be picky (though the last line of my post came over a bit tetchy, sorry) I was more pointing out that you're capturing what you do with the continuation, but not what the continuation is. The continuation is a data structure. It is the jmp_buf if you want to implement simple continuations as setjmp/longjump. Though I probably wouldn't explain it that way, since most programmers don't have C these days. goto on its own doesn't honor the call stack in C, which is what the setjmp.h is for, and non-local 'goto', so yeah, it is closer to that. Continuations also don't have to use a call-stack (though I totally acknowledge we're outside mainstream programming now). The idea is very general, and very simple: a data structure that a) stores the current FP, and b) can restore that FP when required.
    - mafribe 11y ago
      I think how a continuation is represented is an implementation detail that depends on many things, one of them being the ambient programming language and typing system (which may enforce e.g. linear usage of continuation). But in all cases what you do with a continuation is the same, you define a point in the computation (that's what callcc does) that you can go back to (by executing throw). That's why I like to explain callcc / throw by analogy with goto. Once that behaviour is clear, the question of representation is natural and comprehensible.
      - sago 11y ago
        Can you give an example of a 'linear usage of continuation', that doesn't have the continuation be a data structure (or data type)? I'm curious. The question is genuine, not passive aggressive, I don't understand the distinction you're making there.
        mafribe 11y ago
        This is a very good question. Continuations can be used to explain a wide variety of program control such as calling/returning (procedures), raising/handling (exceptions), jumping/labeling (goto and labels), process switching (coroutines), backtracking (amb and fail), and capturing/invoking first-class continuations (callcc and throw). An example of using the full power of continuations is the notorious argfc function [1]: callcc lambda k.(throw k (lambda x.(throw k lambda y.x))) This is the classic example of calling a function once, but returning twice. The function argfc normalises to a lambda-abstraction, but, as [2] investigates, distinguishes programs by application that are indistinguishable in the absence of continuations: (lambda x.(x 1);(x 2)) argfc = 1 but (lambda x.lambda y.(x 1);(y 2)) argfc argfc = 2 with M;N being the sequential composition of M and N, binding more tightly than lambda-abstraction. As you know, the reason is that continuations carry information about contexts that may be returned (jumped) to later. If we use continuations linearly (i.e. exactly once) or affinely (at most once), such forms pathological behaviour cannot occur, so implementations might be easier. In particular, special cases of continuation use such as function call/return and exception throw/catch do not require such duplication of continuations, so can be implemented much more easily than general continuations. It is the completely unrestricted nature of full callcc/throw that requires the implementation to capture the whole call stack. [1] H. Thielecke, Continuations, functions and jumps. [2] J. G. Riecke, H. Thielecke, Typed Exceptions and Continuations Cannot Macro-Express Each Other.

by mafribe 11y ago

sago 11y ago

It's a very simple explanation, which is partly true, but misses the point of what the continuation is. You've described the effect of resuming a continuation, but not the continuation itself. I can store a continuation in a variable, for example, or pass it to a function. I can't do that with goto. It's also not really like a label you might go to, since it isn't the target, but the whole call stack. No offence, but I'll stick with my version, since it describes what is actually happening, and how to implement it.

mafribe 11y ago
Well what does 'goto' do when you are jumping non-locally? If you don't save the calling environment, you are trashing the call-stack leading to undefined behaviour. So this is not really even goto, it's a desaster ... That's why the C/C++ equivalent of non-local goto, namely setjmp-longjmp, does indeed save the calling environment. You cannot have non-local goto in a language with a call-stack otherwise. In that sense, the callcc / throw combination is like goto, with the addition that the place you are jumping to (declared in callcc) is hidden from the outside. Likewise exceptions in C++ are a form of non-local jump (albeit dynamically bound, unlike goto and call/cc) and they do clean up the stack. In my drive to give a simple explanation of call/cc, I clearly oversimplified. I should have made it more clear that I'm talking about semantically meaningful non-local goto in a language with a call-stack. Thanks for pointing this out, sorry for the confusion.
- sago 11y ago
  I wasn't trying to be picky (though the last line of my post came over a bit tetchy, sorry) I was more pointing out that you're capturing what you do with the continuation, but not what the continuation is. The continuation is a data structure. It is the jmp_buf if you want to implement simple continuations as setjmp/longjump. Though I probably wouldn't explain it that way, since most programmers don't have C these days. goto on its own doesn't honor the call stack in C, which is what the setjmp.h is for, and non-local 'goto', so yeah, it is closer to that. Continuations also don't have to use a call-stack (though I totally acknowledge we're outside mainstream programming now). The idea is very general, and very simple: a data structure that a) stores the current FP, and b) can restore that FP when required.
  - mafribe 11y ago
    I think how a continuation is represented is an implementation detail that depends on many things, one of them being the ambient programming language and typing system (which may enforce e.g. linear usage of continuation). But in all cases what you do with a continuation is the same, you define a point in the computation (that's what callcc does) that you can go back to (by executing throw). That's why I like to explain callcc / throw by analogy with goto. Once that behaviour is clear, the question of representation is natural and comprehensible.
    - sago 11y ago
      Can you give an example of a 'linear usage of continuation', that doesn't have the continuation be a data structure (or data type)? I'm curious. The question is genuine, not passive aggressive, I don't understand the distinction you're making there.
      - mafribe 11y ago
        This is a very good question. Continuations can be used to explain a wide variety of program control such as calling/returning (procedures), raising/handling (exceptions), jumping/labeling (goto and labels), process switching (coroutines), backtracking (amb and fail), and capturing/invoking first-class continuations (callcc and throw). An example of using the full power of continuations is the notorious argfc function [1]: callcc lambda k.(throw k (lambda x.(throw k lambda y.x))) This is the classic example of calling a function once, but returning twice. The function argfc normalises to a lambda-abstraction, but, as [2] investigates, distinguishes programs by application that are indistinguishable in the absence of continuations: (lambda x.(x 1);(x 2)) argfc = 1 but (lambda x.lambda y.(x 1);(y 2)) argfc argfc = 2 with M;N being the sequential composition of M and N, binding more tightly than lambda-abstraction. As you know, the reason is that continuations carry information about contexts that may be returned (jumped) to later. If we use continuations linearly (i.e. exactly once) or affinely (at most once), such forms pathological behaviour cannot occur, so implementations might be easier. In particular, special cases of continuation use such as function call/return and exception throw/catch do not require such duplication of continuations, so can be implemented much more easily than general continuations. It is the completely unrestricted nature of full callcc/throw that requires the implementation to capture the whole call stack. [1] H. Thielecke, Continuations, functions and jumps. [2] J. G. Riecke, H. Thielecke, Typed Exceptions and Continuations Cannot Macro-Express Each Other.