Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What Does "With Continuation" Mean? (2020)

forum.snap.berkeley.edu

Post reply on HN
Print view View original

41–50 of 60 posts

Re: What Does "With Continuation" Mean? (2020)

#41

Post by lupire »

JonChesterfield wrote: post #36
carterschonwald wrote: post #30

Earlier quoted context omitted.

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

I like the notation "limited continuations" more than "undelimited". Drops the double negative and provides a pejorative element. Call/cc still has a delimiter, it's just some second class thing above the scope of the current program that you can't do much with which thwarts composition. Let the programmer specify where the delimiter is and you get a less limited construct.

"undelimited" is not a double negative. "Delimited" means "limited by an explicit boundary."

Introducing a different concept with the same word "limited" is confusing.

"specifiable continuations" may be a clearer way to make a positive connotation.

Re: What Does "With Continuation" Mean? (2020)

#42

Post by cobbal »

lupire wrote: post #40
eru wrote: post #21

Earlier quoted context omitted.

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.

How is it similar?

Variables are written once, and data flow is made explicit.

Re: What Does "With Continuation" Mean? (2020)

#43

Post by remexre »

lupire wrote: post #40
eru wrote: post #21

Earlier quoted context omitted.

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.

How is it similar?

For straight-line code, something like

    %2
is effectively equivalent to

    (foo %0 %1 (lambda (%2)
      ...)
Phis are sorta modeled inversely:

    %1:
        %2  %2, %3 -> %4]
        ...
becomes:

    (letrec ((%1 () (const 0 (lambda (%2) (%5 %2))))
             (%3 () (const 1 (lambda (%4) (%5 %4))))
      (%5 (%6) ...))
      ...)
The nice thing on paper about both of these is that you've broken every computation down into nice nameable bits; if you want to do some analysis (e.g. abstract interpretation) over the programs, you can store intermediate results as a map from names (like %4) to values.

The traditional downside of CPS is that requiring lambdas be nested in order for things to be in scope can make some program transformations require "reshuffling" terms around in a way SSA doesn't require.

The "cps soup" [0] approach used in Guile fixes this, but your terms look like they violate lexical scoping rules!

[0]: https://wingolog.org/archives/2015/07/27/cps-soup

Re: What Does "With Continuation" Mean? (2020)

#44

Post by trealira »

lupire wrote: post #40
eru wrote: post #21

Earlier quoted context omitted.

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.

How is it similar?

There's a short paper that shows how they're similar (PDF warning):

https://www.cs.princeton.edu/~appel/papers/ssafun.pdf

Re: What Does "With Continuation" Mean? (2020)

#45

Post by nerdponx »

carterschonwald wrote: post #14

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

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

Re: What Does "With Continuation" Mean? (2020)

#46

Post by nerdponx »

kccqzy wrote: post #4

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 ha…

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

Re: What Does "With Continuation" Mean? (2020)

#47

Post by plagiarist »

HexDecOctBin wrote: post #35
plagiarist wrote: post #34

Earlier quoted context omitted.

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.

I'm not an expert, but I think the difference is that in exceptions, stack in unwound; while in continuations, all stack frame hang around in a sea of stack frames waiting to be garbage collected when no one holds a reference to them anymore. This would imply that you can jump into the same stack frame multiple times, or do other weird things.

Sure, but then the context of the C family of languages hinders any comprehension of these different styles of use.

Re: What Does "With Continuation" Mean? (2020)

#48

Post by cryptonector »

sillysaurusx wrote: post #20
cryptonector wrote: post #18

Earlier quoted context omitted.

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.

Ehh. I think it makes it a lot harder to understand what a continuation is if you say they’re closures. Continuations capture the stack. Closures capture variables.

> Continuations capture the stack.

Yes, but if you take 'stack' too literally here then you'll think that `call/cc` copies the stack, when maybe it really doesn't.

> Closures capture variables.

Variables, yes, including the return address of the frame in which those variables are if that return address is make explicit (e.g., because of CPS conversion).

And now you can see that closures can be continuations if they implicitly capture the stack.

Re: What Does "With Continuation" Mean? (2020)

#49

Post by cryptonector »

JonChesterfield wrote: post #37
cryptonector wrote: post #15

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…

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 comp…

> 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).

Re: What Does "With Continuation" Mean? (2020)

#50

Post by cryptonector »

xg15 wrote: post #33
cryptonector wrote: post #19

Earlier quoted context omitted.

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 e…

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 a…

Continuations (which can be just closures following CPS conversion) can be used to construct co-routines, and so if you start with co-routines instead...

But callbacks and callback-based async/await force you to compress application state better, so you will get better performance out of that. No need for `call/cc` style continuations, just light-weight continuations, but this is mainly a mirage because in the callback model you do in fact have continuations, it's just that the continuation is only ever "the next step in processing this thing" rather than "the whole stack".

That is, with hand-coded CPS you get a very shallow stack to capture in continuations, so the continuations are very cheap.

Post reply on HN