4 ms·

I remember trying to learn continuations during my CS degree, and evidently even today I still don't understand them. The examples don't seem to help either – h

I remember trying to learn continuations during my CS degree, and evidently even today I still don't understand them. The examples don't seem to help either – how exactly does the control flow function?

kmill 9y ago
You know how in Python the "yield" statement is actually an expression and can be sent values using "next"? Imagine there is a special "yield" called "call-with-current-continuation" that can be used anywhere (not just in generators) which bundles everything up and makes a generator-like thing called a "continuation." This continuation object can be called later on, like using "next" in Python. Unlike generators, though, continuations can usually be resumed repeatedly, always resuming at the same point where the call-with-current-continuation expression was. A weird thing is that call-with-current-continuation doesn't yield back to something; it yields to the function given to call-with-current-continuation.
- coldtea 9y ago
  Would that be like having a yield statement AND passing a context (e.g. binding a this that represents "current-continuation")?
  - kmill 9y ago
    Here are two examples in Python syntax, assuming "yield" is no longer a keyword. def f(): def receiver(yield): yield(2) # yield jumps out of the 'receiver' function and never returns print("This never prints") x = callcc(receiver) return x+1 print(f()) # f returns 2+1 # backtracks stores (continuation,[values]) pairs. Whenever a computation fails, we pull out another # value from the list and feed it to the continuation. The idea is to perform a depth-first search. backtracks = [] def fail(): """Aborts the current continuation and backtracks to another alternative stored in backtracks.""" if not backtracks: raise Exception('amb ran out of alternatives') yield, alternatives = backtracks.pop() alt = alternatives.pop() if alternatives: # this continuation still has alternatives, so put them back on the list in case of a future 'fail' backtracks.push((yield, alternatives)) yield(alt) def amb(*alternatives): """The "ambivalent operator." The arguments to amb are alternatives, and the return value of amb is an alternative which makes the future computation not fail.""" if not alternatives: fail() def receiver(yield): backtracks.append((yield, alternatives)) fail() return callcc(receiver) def expect(b): if not b: fail() def test_amb(): """Let's find a Pythagorean triple.""" x = amb(*range(1,100)) y = amb(*range(1,100)) z = amb(*range(1,100)) expect(x**2 + y**2 == z**2) return (x,y,z) # We can print out all the Pythagorean triples. trip = test_amb() print("(x,y,z)=(%s,%s,%s)" % trip) fail() # fail every time so it keeps backtracking, but the side effect of printing out remains
ehaliewicz2 9y ago
I think a good way to understand how they work is by implementing a simple Scheme interpreter that explicitly passes around the continuations of the guest language. This page helped me quite a bit a few years ago http://blog.theincredibleholk.org/blog/2013/11/27/continuation-passing-style-interpreters/ http://blog.theincredibleholk.org/blog/2013/11/27/continuati...
abecedarius 9y ago
Do you know setjmp/longjmp in C? It's like that, except you can longjmp to the same target more than once, because Scheme's equivalent of "stack frames" are on the garbage-collected heap instead of "the stack". (The implementation may be fancier, but that's the easiest way to do it.)
ufo 9y ago
Im fond of the operating system analogies: one-shot continuations are like suspended processes. The OS saves all the program state to memory (including call stack and current registers) and switches to a different line of execution. Later, it can go back to the original process and resume from where you paused. You find something like this under many names (coroutines, generators, async, etc) and it is very useful for writing cooperative code. Multishot continuations are kind of like forks (but without the parallelism). You can save the program state and make copies of it so later on you can backtrack to the point of the fork if you want. With this you can do things like logic programming or define your own exception handling mechanism. However, this is hard to implement and is confusing of you mix with mutable state so very few languages have this feature... BTW, one of the hard parts of understanding lisp continuations is that the api is "call with current continuation" (pass the continuation as a function arg) instead of "get current continuation" (which would return the continuation)
Tarean 9y ago
I usually like to think of delimited continuations from the inside. First a haskell example because there I can heap on syntax sugar: do x <- foo y <- bar (x+1) baz (x*y) let's look at bar: bar x = Cont (\fr -> ...) Or without the type wrapper: bar x fr = ... x represents the environment - all variables that are in scope and can be used to compute the next step. They represent everything that came before bar. fr are all continuations that come after us, reified as a function. We can use the type of bar bar :: env -> (next-> result) -> result to find ways to use continuations. Time for type tetris! Easiest way to get a result value is to calculate a next value from env. But we can do much more fun things as well, like implementing control jumps. Lets look at how we can implement this jumping: jumpCont env _ignoredRestOfBlock = jumpTarget (...env) We ignore the function that represents the rest of our current block and use something else instead. Now we just have to figure out what 'something else' might be: callCC comnputeInnerBlock = \_ignoredEnv jumpTarget -> comnputeInnerBlock jumpCont where jumpCont env _ignoredRestOfBlock = jumpTarget env So we have two streams of control - the one callCC is part of and one nested within callCC. If we call jumpCont we ignore the rest of the nested block and continue with the callCC control stream, exiting the current block: callCC $ \exitBlock -> do x <- foo when (x < 3) exitBlock y <- bar (x+1) -- <- here until the rest of the callCC block would be _ignoredRestOfBlock lift $ print (x*y) ... -- <- this is jumpTarget, the point callCC would jump to So if normal functions take the result of what came before as an argument and compute a new result, continuations take the result of what came before and a function that represents the rest of the computation and compute a new result. You can think of this function as created for you by some compiler magic.

kmill 9y ago

You know how in Python the "yield" statement is actually an expression and can be sent values using "next"? Imagine there is a special "yield" called "call-with-current-continuation" that can be used anywhere (not just in generators) which bundles everything up and makes a generator-like thing called a "continuation." This continuation object can be called later on, like using "next" in Python. Unlike generators, though, continuations can usually be resumed repeatedly, always resuming at the same point where the call-with-current-continuation expression was. A weird thing is that call-with-current-continuation doesn't yield back to something; it yields to the function given to call-with-current-continuation.

coldtea 9y ago
Would that be like having a yield statement AND passing a context (e.g. binding a this that represents "current-continuation")?
- kmill 9y ago
  Here are two examples in Python syntax, assuming "yield" is no longer a keyword. def f(): def receiver(yield): yield(2) # yield jumps out of the 'receiver' function and never returns print("This never prints") x = callcc(receiver) return x+1 print(f()) # f returns 2+1 # backtracks stores (continuation,[values]) pairs. Whenever a computation fails, we pull out another # value from the list and feed it to the continuation. The idea is to perform a depth-first search. backtracks = [] def fail(): """Aborts the current continuation and backtracks to another alternative stored in backtracks.""" if not backtracks: raise Exception('amb ran out of alternatives') yield, alternatives = backtracks.pop() alt = alternatives.pop() if alternatives: # this continuation still has alternatives, so put them back on the list in case of a future 'fail' backtracks.push((yield, alternatives)) yield(alt) def amb(*alternatives): """The "ambivalent operator." The arguments to amb are alternatives, and the return value of amb is an alternative which makes the future computation not fail.""" if not alternatives: fail() def receiver(yield): backtracks.append((yield, alternatives)) fail() return callcc(receiver) def expect(b): if not b: fail() def test_amb(): """Let's find a Pythagorean triple.""" x = amb(*range(1,100)) y = amb(*range(1,100)) z = amb(*range(1,100)) expect(x**2 + y**2 == z**2) return (x,y,z) # We can print out all the Pythagorean triples. trip = test_amb() print("(x,y,z)=(%s,%s,%s)" % trip) fail() # fail every time so it keeps backtracking, but the side effect of printing out remains

ehaliewicz2 9y ago

I think a good way to understand how they work is by implementing a simple Scheme interpreter that explicitly passes around the continuations of the guest language. This page helped me quite a bit a few years ago http://blog.theincredibleholk.org/blog/2013/11/27/continuation-passing-style-interpreters/ http://blog.theincredibleholk.org/blog/2013/11/27/continuati...

abecedarius 9y ago

Do you know setjmp/longjmp in C? It's like that, except you can longjmp to the same target more than once, because Scheme's equivalent of "stack frames" are on the garbage-collected heap instead of "the stack". (The implementation may be fancier, but that's the easiest way to do it.)

ufo 9y ago

Im fond of the operating system analogies: one-shot continuations are like suspended processes. The OS saves all the program state to memory (including call stack and current registers) and switches to a different line of execution. Later, it can go back to the original process and resume from where you paused. You find something like this under many names (coroutines, generators, async, etc) and it is very useful for writing cooperative code. Multishot continuations are kind of like forks (but without the parallelism). You can save the program state and make copies of it so later on you can backtrack to the point of the fork if you want. With this you can do things like logic programming or define your own exception handling mechanism. However, this is hard to implement and is confusing of you mix with mutable state so very few languages have this feature... BTW, one of the hard parts of understanding lisp continuations is that the api is "call with current continuation" (pass the continuation as a function arg) instead of "get current continuation" (which would return the continuation)

Tarean 9y ago

I usually like to think of delimited continuations from the inside. First a haskell example because there I can heap on syntax sugar: do x <- foo y <- bar (x+1) baz (x*y) let's look at bar: bar x = Cont (\fr -> ...) Or without the type wrapper: bar x fr = ... x represents the environment - all variables that are in scope and can be used to compute the next step. They represent everything that came before bar. fr are all continuations that come after us, reified as a function. We can use the type of bar bar :: env -> (next-> result) -> result to find ways to use continuations. Time for type tetris! Easiest way to get a result value is to calculate a next value from env. But we can do much more fun things as well, like implementing control jumps. Lets look at how we can implement this jumping: jumpCont env _ignoredRestOfBlock = jumpTarget (...env) We ignore the function that represents the rest of our current block and use something else instead. Now we just have to figure out what 'something else' might be: callCC comnputeInnerBlock = \_ignoredEnv jumpTarget -> comnputeInnerBlock jumpCont where jumpCont env _ignoredRestOfBlock = jumpTarget env So we have two streams of control - the one callCC is part of and one nested within callCC. If we call jumpCont we ignore the rest of the nested block and continue with the callCC control stream, exiting the current block: callCC $ \exitBlock -> do x <- foo when (x < 3) exitBlock y <- bar (x+1) -- <- here until the rest of the callCC block would be _ignoredRestOfBlock lift $ print (x*y) ... -- <- this is jumpTarget, the point callCC would jump to So if normal functions take the result of what came before as an argument and compute a new result, continuations take the result of what came before and a function that represents the rest of the computation and compute a new result. You can think of this function as created for you by some compiler magic.