Hacker News Reader

Comment by canjobear | Hacker News Reader

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

View on HN

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

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.

There isn't necessarily a stack with call/cc, the model is that activation frames are heap allocated[1] and can be arbitrary composed. Normally they would be GC collected when a function returns, but call/cc exposes the caller activation frame (+ a function representing the rest of the caller function body) as a first call object, that once captured prevents it from being garbage collected. The stack is recovered by realizing that activation frames have a reference to the calling function activation frame (which is passed to every function as an implicit parameter).

Also an activation frame per se is immutable, but not the objects referenced by it, so all modifications are preserved when invoking a continuation.

[1] this is just a model, in practice there are many ways to implement this that optimize for the common FIFO allocation discipline.

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.

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 <- foo %0 %1
    ...

is effectively equivalent to

    (foo %0 %1 (lambda (%2)
      ...)

Phis are sorta modeled inversely:

    %1:
        %2 <- const 0
        br %5
    %3:
        %4 <- const 1
        br %5
    %5:
        %6 <- phi [%1 -> %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

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

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

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

Reply on news.ycombinator.com