What Does "With Continuation" Mean? (2020)

https://forum.snap.berkeley.edu/t/what-does-with-continuation-mean/1518/2

by d4nyll • 2 years ago

107 58 2 years ago

forum.snap.berkeley.edu

tmoertel• 2 years ago

Here's Oleg's great explanation of continuations in terms most programmers already understand: https://blog.moertel.com/posts/2008-05-05-olegs-great-way-of...

arsdragonfly• 2 years ago

call/cc is undelimited.

jedberg• 2 years ago

I'm just happy to see Professor Harvey still participating in the forums. He taught me SICP in Scheme 27 years ago and it is still some of the most important computer science I ever learned.

vegashacker• 2 years ago

Same! (CS 61A Fall Semester 1996) And I agree!

kccqzy2• 2 years ago

I'm glad that this explanation involves a comparison with goto especially with a discussion of "goto considered harmful". But IMO excessively using continuations results in the same kind of spaghetti code as code that excessively uses goto. Delimited continuations, on the other hand, essentially places a restriction on where the continuation can return to. The analogy with using goto is that the target of the goto has to be within a well specified block of code. This restriction gets rid of the temptation by programmers to take shortcuts and write overly clever but unmaintainable code.

nerdponx2• 2 years ago

Does any language other than Common Lisp provide a "delimited goto"?

kccqzy2• 2 years ago

For many languages, "delimited goto" is approximated by the language's exception mechanism. You can raise an exception pretty much anywhere you want including in totally different functions many stack frames deep, and the control transfers to the closest catch handler.

Personally I'm not a fan because even the name "exception" carries some baggage. Many people think it should only be reserved for exceptional situations, not expected control flow, and some languages have penalties in performance when using them. That's why they tend not be used for vanilla control flow.

kazinator6• 2 years ago

Simply using simple tail calls is goto-like spaghetti code.

Any if/goto program graph or flowchart can be turned into tail calls that have the same shape. For each node in the goto graph, we can have a tail-called function, 1:1.

joe_the_user• 2 years ago

Required reference "Objects the poor man's Closures[continuations]" [1]. Well, the links actually say "Closures And Objects Are Equivalent", which is the point. But I'd offer a deeper point - continuations/closures are rightly considered one of the hardest things most programmers ever encounter while objects are things most programmers deal with daily. Sure, that means use continuations if you want to look like a bad ass but use objects if you want a project to succeed.

[1]http://wiki.c2.com/?ClosuresAndObjectsAreEquivalent

canjobear2• 2 years ago

Continuations aren't equivalent to closures.

cryptonector9• 2 years ago

Continuations are closures. Closures aren't continuations. Though one can build continuations out of closures by converting code into continuation passing style, which makes continuations explicit, and then `call/cc` is trivial, since all it does is pass (to its function argument) its [now-explicit, after CPS conversion] continuation, thus reifying it.

ChrisArchitect• 2 years ago

(2020)

canjobear2• 2 years ago

I took a Scheme programming class where we did tons of stuff with continuations. I got obsessed and wrote all kinds of weird code. I even started using continuation passing style in Python. It was a dark time. Looking back, none of that code makes any sense at all.

When I think back to my days of mucking around with call/cc my main emotion is relief that I’ve forgotten how it works. It’s a load off my mind

neilv2• 2 years ago

In case first-class continuations scare anyone away from Scheme: you probably will never use it directly in practice, unless you're doing something very unusual that happens to really need it.

For example, say you have a really hairy AI search algorithm, capturing a continuation happens to make backtracking easier.

Or you're implementing another language or DSL in Scheme, and you use first-class continuations to implement some control structure semantics exactly how you want them to be.

I think the closest I've used, in writing maybe a hundred modules, is an escape procedure (like a premature `return` statement in many other languages, which you generally avoid in idiomatic Scheme).

jfoutz• 2 years ago

I’m having trouble recalling, call cc just fixes the stack, right? If you mess with the heap, that sticks around?

The backtracking example is a good one. I vaguely remember needing to be careful about global state, or visible in a given context. It’s not awful, but a little tricky.

cryptonector9• 2 years ago

For me it's the opposite: I can't forget how it works, I don't want to forget how it works, and I marvel at the beauty of it all.

When I was in school I carried one of Guy Steele's (I think, if I remember correctly) articles about continuations in my back pocket for a year, breaking it out when I was bored, until I got it.

eru3• 2 years ago

Continuation passing style is mostly a good tool for writers of compilers, and perhaps interpreters.

It's very, very similar to single-static-assignment (SSA) style that will be more familiar to people coming from imperative languages.

lupire2• 2 years ago

How is it similar?

neilv2• 2 years ago

I don't know whether it helps, but here's another explanation that doesn't involve a visual programming language:

First, imagine that procedures (or functions) are first-class values, like in some languages are called "anonymous functions", "closures", "lambdas", etc.

Now imagine that every procedure call is effectively a goto with arguments... and the familiar part about being able to return from that procedure, to its calling point, is implemented by an implicit additional value created at calling time... which is a "continuation" procedure with argument(s) that you call to return the value(s) from the other procedure.

To make it first-class continuations, imagine that "continuation" procedure value you call to return the value(s) from another procedure... can be made accessible to the program as a first-class value. Which means you can store it in a variable or data structure like any other value. And you can call that "continuation" procedure value multiple times -- returning to that dynamic state of the calling context in the program many times.

It's one of those things that application code almost never uses directly, but that could be super useful and simplifying in the implementation of another programming language, or carefully controlled in particular libraries (e.g., you wanted to make a stateful Web backend library or DSL that made it really easy to express the logic for some kind of interaction tree responding to multiple steps of form input).

Someone• 2 years ago

An alternative way to look at for C/C++/pascal/… programmers it is by looking at the return keyword not as a keyword, but as an implicit argument that’s a pointer to a function. Imagine this would work:

   global fooBack
   global barBack
   main() {
     print foo()
   }
   foo() {
     fooback = return
     bar()
     return “foo”
   }
   bar() {
     barBack = return
     if randomBool
       fooBack(“bar”)
     else
       return “bar”
   }

and that, 50% of the time, woud print “bar”.

In a C-like system with a call stack, that would give you a nicer setjmp (still with quite a few limitations). Systems with true continuations would allow code to call ‘up the stack’ for example if main were to call barBack in the scenario above. That wouldn’t work in C as bar’s stack frame wouldn’t exist anymore.

HexDecOctBin2• 2 years ago

This is great, I finally understand how continuations work (since I now see how they might be implemented in the runtime). Thanks!

Could you provide a similar example of what delimited continuations are?

plagiarist2• 2 years ago

I think `bar` being able to return from `foo` has little difference to throwing exceptions in various OOP languages. But the C-style paradigm makes it more confusing for different scenarios, like as you describe with calling the deeper "return" from main.

TruffleLabs• 2 years ago

Call/cc !

carterschonwald2• 2 years ago

So there’s a funny thing this doesn’t touch on: the semantics of call/cc is genuinely confusing to understand! There’s a related construct that’s much more legible and has a much easier to understand: call with delimited continuation!

Oleg K wrote a very articulate piece about this some long time ago https://okmij.org/ftp/continuations/against-callcc.html

cryptonector9• 2 years ago

I think of `call/cc` as a parlor trick that helps introduce the concept of continuations more generally.

Threads and co-routines are on the heavy-weight end of the concurrent programming techniques spectrum because they require stacks -possibly large, with guard pages and all- and encourage smearing application state onto that stack, increasing cache pressure.

Continuation passing style (CPS) is on the light-weight end because it encourages the programmer to make application state explicit and compact rather than smearing it on a stack. Callback hell is hand-coded continuation passing style (CPS). Async/await is a compromise that gets one close to the light weight of continuations.

To understand all of that one has to understand the concept of continuations. In computer science, the cheap parlor trick that is `call/cc` is helpful in introducing the concept of continuations to students. After all, `call/cc` is shocking when one first sees it, and the curious will want to understand it.

xg15• 2 years ago

I think now I get why I find Python's async/await semantics (asyncio) so much more convoluted than Javascript's.

Javascript starts with simple callbacks. Those indeed have no stack, only a shallow list of local variables as state. Then async/await is modelled as a relatively straightforward syntactic sugar on top of that: An await call is still just a callback behind the scenes; if one async function awaits another async function, you get something that looks like a stack, but is really just a chain of callbacks.

In contrast, Python starts with coroutines, which do have a stack, then models async/await by surrounding them with a scheduling runtime. Unfortunately, for async code to be useful, you still need support for callbacks, so you end up with both: an await call represents a mix of suspended coroutine stacks and callback chains, which can be much more complicated to reason about.

eru3• 2 years ago

Approximately everything by Oleg is great!

We half-jokingly considered renaming our Sydney Computer Science Paper Club to 'Oleg Fan Club'.

carterschonwald2• 2 years ago

Hehe fun!

Yeah, delimited continuations have much saner semantics than undelimited ones. Partly because they’re always well defined

nerdponx2• 2 years ago

Is there any resource that explains the different varieties of the limited continuations in a way that doesn't require an advanced theoretical CS degree? I see that Racket has both prompt/control and shift/reset but I've never been able to make sense of how they differ, if at all

kazinator6• 2 years ago

Delimited continuations are in fact harder to understand, because resumed delimited continuations hit an arbitrarily set brick wall, at which point they return like functions: the value which bubbles out of that brick wall is the return value. Thus they don't represent the true future of the computation. The true future of the computation will not hit a prompt and then stop dead, returning a value to the point where it was resumed. It's like a future ... on a yo-yo string. This is an extra feature. By adding code around full blown continuations, we can get delimited ones and so to understand that we have to understand full blown continuations, and that extra code.

Once you get it, you get it. You then understand that it's better for the continuation not to continue into an indefinite future, and easier to reason about when you know that it's going to stop at a certain enclosing contour, and you will have access to the value bubbling out of there.

Once you already understand it, it's very easy to explain it to yourself.

cryptonector9• 2 years ago

The easiest way to think about continuations is to consider them a generalization of function returns. The continuation of a C function f() is the return address and the saved frame pointer of the calling function -- and that looks a lot like a closure, and that's because it is, except that a) you can only pass that closure one argument in C: the return value, and b) you actually can't get a value for this closure in C, and c) there's no closures as such in C anyways :)

[And what is a closure? It's a tuple of {function body pointer, data pointer}, and "callbacks" in C often look just like that, but not as a singular value combining the two parts but as two separate values. In better languages a function is indistinguishable from a closure.]

Anywhere that you see `call/cc` you can think of it as making a first-class function value (a closure) of the current location (which would be the return address of the call to `call/cc`) and then passing that closure to the function given as an argument to `call/cc`. After you parse that sentence you'll realize that's a bit crazy: how does one make a function out of... a function's return address (and saved frame pointer)? The answer is: reify that {return address, saved frame pointer} as a closure. ('Reify' means, roughly, to make a hidden thing not hidden.)

Still, it must seem crazy. Yet it's not that crazy, certainly not if you make it so you can only call it once, and only if `call/cc` hasn't returned yet. What's crazy is that in Scheme this continuation can be called repeatedly, so how? Here's one way to do it: replace the stack with allocating function call frames on the heap!, which in a language with a GC means that all those function call frames remain alive as long as closures (which a continuation is) refer to them. (Another way to do it is with copying stacks.)

One can easily (for some value of "easily") implement a language that has `call/cc` in a language that doesn't but which has a) closures, b) a powerful macro system / AST / homoiconicity. All one has to do is take a program, apply continuation passing style (CPS) conversion to it (a fairly straightforward transformation where the result is unreadable for most humans), which automatically causes all function call frames to be captured in closures (thus put on the heap), but also automatically makes continuations explicit values (closures). The `call/cc` is a trivial function that passes its now-explicit continuation argument to the function that `call/cc` is given to call.

Allocating function call frames on the heap is a performance disaster. And that's where delimited continuations come in: the goal being to allocate function call frames on mini stacks.

`call/cc` is really a bit of a parlor trick, and a very nifty one at that, but continuations are a very important concept that comes up all over the place, and one that computer scientists and software engineers ought to be at least conversant with.

JonChesterfield3• 2 years ago

Simpler still is to recognise that "call a function" and "return from a function" are different syntax over the same thing. They both mean "jump to somewhere with a convention about where to find state".

If you replace "call a function" with goto, and replace "return from a function" with goto, then it becomes immediately obvious that "continuation" is a name for where you're going to jump to next. It only looks complicated from the context of calls/returns/stacks.

Confusing call and return for different things is unfortunate but popular. It gives rise to things like four registers available for passing arguments and one available for returning a result, when the calling convention really should be symmetric.

"Continuation passing style" is what all function calls use - x86 writes the address of the continuation to the stack, more sensible ISA's pass it in a specific register - modulo language syntax that somewhat obfuscates control flow.

cryptonector9• 2 years ago

Simpler still is to recognise that "call a function" and "return from a function" are different syntax over the same thing. They both mean "jump to somewhere with a convention about where to find state".

That's pretty much what I was saying, but pithier and better stated, so thank you.

If you replace "call a function" with goto, and replace "return from a function" with goto, then it becomes immediately obvious that "continuation" is a name for where you're going to jump to next. It only looks complicated from the context of calls/returns/stacks.

Yes, thus "lambda is the ultimate GOTO".

Confusing call and return for different things is unfortunate but popular. It gives rise to things like four registers available for passing arguments and one available for returning a result, when the calling convention really should be symmetric.

It's a convenient abstraction for Algol family languages.

There is a difference between function call and function return in those languages: a call pushes a frame on the stack, and a return pops a frame off the stack, but both otherwise look very similar under the covers.

In CPS the "pop a frame off the stack" part doesn't happen, but instead you get tail-call optimization (TCO) to avoid the stack blowing up with calls to functions that never return (and which anyways maybe store their real call frames on the heap to boot, thus wasting all that stack space for nothing).

kazinator6• 2 years ago

like four registers available for passing arguments and one available for returning a result, when the calling convention really should be symmetric

The symmetry implies the support for multiple return values.

If the language model has single return values, then continuations take one parameter. Lots of historic papers about continuations model them that way.

Multiple values are tricky. 100% symmetry is never achieved with those things. The problem is that in many contexts, an expression is expected to produce one value. We usually want (foo (bar) (baz)) to call foo with two arguments even if bar and baz return two or more values. There may be times when we want to inerpolate all the values, or some of them, into the argument space, so we need some syntax to distinguish those situations. But if (foo (bar) (baz)) just takes one value from each function, then that means that the primary value is more of a first class citizen than the additional values. There is something special about it.

We can also go the other way: declare that functions should not only return exactly one value, but only take exactly one argument. That is also symmetric! Then currying can be used to combine functions in order to simulate multiple arguments.

kazinator6• 2 years ago

Henry Baker showed that call/cc doesn't require a spaghetti stack with dynamically allocated frames. All you need is one linear stack, and never return.

Richard Stallman made similar observations in Phantom Stacks. If You Look to Hard They Aren't There.

Chicken Scheme, based on C, implements Baker's idea. Chicken Scheme's C functions never return. They take a continuation argument, and just call that instead of returning. So every logical function return is actually a new C funtion call. These all happen on the same stack, so it grows and grows. All allocations are off the stack, including lambda environments, and other objects like dynamic strings. When the stack reaches a certain limit, it is rewound back to the top, like a treadmill. During this rewinding phase, all objects allocated from the stack which are still reachable are moved to the heap.

Thus the combination of the CPS strategy (all returns are continuation invocations) and the linear stack with rewinding obviates the need for dynamically allocated frames.

cryptonector9• 2 years ago

I'm aware of this work, especially Chicken Scheme, but Chicken scheme basically combines the stack and the heap + compacting GC, so it's a reach to say that Chicken Scheme doesn't allocate frames on the heap... If you have to GC frames, then they are as-if on the heap. Same thing for related variants.

You can also just allocate all frames on the stack and use stack copying for `call/cc` -- this involves... a heap of stack copies :laugh: so I think I'm henceforth going to say that `call/cc` continuations always require heap allocations :)

jillesvangurp• 2 years ago

Continuations are also the backbone of co-routines in Kotlin and has first class support. One nice feature of the coroutines framework is that they made it really easy to adapt existing asynchronous frameworks in Java (there are many) and on other platforms. The list of supported frameworks includes things like reactive Java, vert.x, spring webflux, Java Futures. And that's just the JVM. If you are using kotlin-js in the browser or on node.js, promises and async/await are covered too. And on IOS, coroutines also do the right thing with e.g. garbage collection and other mechanisms in IOS.

Most of this stuff is supported via extension functions. But for asynchronous things that aren't supported it's really easy to adapt them yourself with the suspendCancellableCoroutine function. This is a suspending function that takes a function with a continuation as the parameter. Inside the function you do whatever needs doing and handle your callbacks, futures, awaits, or whatever and call continuation.resume, continuation.resumeWithException, or continuation.invokeOnCancellation as needed (which sadly is not a feature every async framework or language supports).

With a few small extension functions you can pretend most things are nice kotlin suspend functions and not deal with the spaghetti code typically needed otherwise. E.g. Spring Flux is an absolute PITA in Java because of this and essentially effortless in Kotlin. Your code looks like normal kotlin code. Nothing special about it. All the flux madness is shoveled under the carpet.

In the same way the new virtual threads in Java are supported trivially because all of that is exposed via the existing Theading and Threadpool APIs. So, you can just dispatch your co-routine asyncs and launches as virtual threads via a dispatcher that you create with a little extension function on Threadpool. Most of this stuff "just works" out of the box. There's a lot of confusion on this topic in the Java community. For Kotlin this is just yet another way to do async stuff that joins a long list of existing other ways. It has its pros and cons for different use cases and is there if you need it. No big deal but very nice to have around. I've not found any use for it yet and we're on Spring Boot and java 21. We already have everything asynchronous and non blocking.

pnut• 2 years ago

If I ever start writing statements like "Part the first", please take me out back and put us all out of that misery.

kazinator6• 2 years ago

yield based on delimited continuations in TXR Lisp, showing that unwind-protect works:

  (defun grandkid ()
    (unwind-protect
      (yield-from parent 'in-grandkid)
      (put-line "returning from grandkid")))
 
  (defun kid ()
    (unwind-protect
      (progn
        (yield-from parent 'in-kid)
        (grandkid))
      (put-line "returning from kid")))

  (defun parent ()
    (unwind-protect
      (progn
        (yield-from parent 'in-parent)
        (kid))
      (put-line "returning from parent")))

  (let ((fn (obtain (parent))))
    (prinl 'a)
    (prinl (call fn))
    (prinl 'b)
    (prinl (call fn))
    (prinl 'c)
    (prinl (call fn))
    (prinl 'd)
    (prinl (call fn))
    (prinl 'e))

Run:

  $ txr cont.tl 
  a
  in-parent
  b
  in-kid
  c
  in-grandkid
  d
  returning from grandkid
  returning from kid
  returning from parent
  nil
  e

Each yield captures a new delimited continuation up to the parent prompt. Each (call fn) dispatches a new continuation to continue on to the next yield, or termination.

So with all this back-and-forth re-entry, why do the unwind-protects just go off once? Because of a mechanism that I call "absconding": the answer to the dynamic wind problem.

Absconding is a way of performing a non-local dynamic control transfer without triggering unwinding. It's much like the way, say, the C longjmp is unaware of C++ destructors: the longjmp absconds past them.

With absconding we can get out of the scope where we have resumed a continuation without disturbing the scoped resources which that context needs. Then with the continuation we captured, we can go back there. Everything dynamic is intact. Dynamically scoped variables, established exception handlers, you name it.

The regular function returns are not absconding so they trigger the unwind-protect in the normal way.

absconding is an elephant gun, that should only be used in the implementation of primitives like obtain/yield.

15 second tutorial:

Cleanup yes:

  1> (block foo (unwind-protect (return-from foo 42) (prinl 'cleanup)))
  cleanup
  42

Cleanup no:

  2> (block foo (unwind-protect (sys:abscond-from foo 42) (prinl 'cleanup)))
  42

That's all there is to absconding. yield-from uses it. It captures a new continuation, packages it up and absconds to the prompt, where that is unpacked, the new continuation updated in place of the old so that fn will next dispatch that new one.

What Does "With Continuation" Mean? (2020)

Related Stories