Live data from Hacker News

Writing a Lisp: Continuations

reinvanderwoerd.nl

41–50 of 51 posts

Re: Writing a Lisp: Continuations

#41
post #12

Continuations are strangely underused, as they enables writing long-living processes in a simple way, without having to keep them in running in a thread, or even in memory. Then a real programming language can replace all "business processing" crap languages. Let's say you write a framework that escapes to a continuation whenever the "process" is waiting for Futures or Promises to complete, and returns the thread to…

I would say that cotinuations In the sense of call/cc are overused. You have to look hard for a problem where undelimited continuations are in any way better than delimited ones.

For the vast majority of cases, delimited continuations are faster, use less memory (and makes garbage Collection easier) and are generally easier to reason about.

Re: Writing a Lisp: Continuations

#42

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?

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)

Re: Writing a Lisp: Continuations

#43
post #12

Continuations are strangely underused, as they enables writing long-living processes in a simple way, without having to keep them in running in a thread, or even in memory. Then a real programming language can replace all "business processing" crap languages. Let's say you write a framework that escapes to a continuation whenever the "process" is waiting for Futures or Promises to complete, and returns the thread to…

I have implemented interpreters that support both full and delimited continuations. They are underused for many very good reasons. A continuation makes an implicit state machine. Implicit means anonymous, which means harder to talk about, which means harder to reason about. But there are technical problems too. Continuation based sessions, as used in fringe web frameworks such as Seaside or even Arc's library that po…

> For example, let's say you deploy a new version of your code: What happens to all the in-progress sessions?

This is a problem inherent to long-running processes, no matter the implementation. We had the same problem in our business process engine using jbpm (implemented as an interpreter serializing state to database every step).

Ultimately you have to decide if you bind functions/subroutines/subprocesses/whatever you call them early (so when you call them later and there's a new version - they still use old version), or late - so they are always calling the newest version. And you have to adjust your coding assumptions and the way you update your software to new version basing on that decision.

Neither way is always the correct one.

Re: Writing a Lisp: Continuations

#44

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?

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

Re: Writing a Lisp: Continuations

#45

Earlier quoted context omitted.

Also, delimited continuations are no less general than the regular ones. Regular continuations are also delimited, because they cannot capture control beyond the program's startup function. If we place a prompt at the top of the main function of the program and use that for making delimited continuations, we basically get regular continuations: continuations that can potentially return all the way to the top, just as…

> If we place a prompt at the top of the main function of the program and use that for making delimited continuations, we basically get regular continuations: continuations that can potentially return all the way to the top, just as far as regular continuations. While this is certainly true in theory, in practice it doesn't seem that simple. When you start dealing with already-compiled code (can't apply a macro to it…

"Delimited" in continuations doesn't refer to a non-first-class hack. Delimited continuations are first-class, built-into-the-language objects (unless kludged otherwise, which is true of any continuations). They are just semantically nuanced relative to undelimited continuations in that they allow the program to clamp the future computation to within a specified dynamic contour. When the restarted continuation bubbles out to that boundary, it terminates and returns a value to whomever dispatched the continuation. And of course, it can be called again and again to do the same thing. That's why delimited continuations behave like functions and are composable.

Re: Writing a Lisp: Continuations

#46
post #43

Earlier quoted context omitted.

I have implemented interpreters that support both full and delimited continuations. They are underused for many very good reasons. A continuation makes an implicit state machine. Implicit means anonymous, which means harder to talk about, which means harder to reason about. But there are technical problems too. Continuation based sessions, as used in fringe web frameworks such as Seaside or even Arc's library that po…

> For example, let's say you deploy a new version of your code: What happens to all the in-progress sessions? This is a problem inherent to long-running processes, no matter the implementation. We had the same problem in our business process engine using jbpm (implemented as an interpreter serializing state to database every step). Ultimately you have to decide if you bind functions/subroutines/subprocesses/whatever…

Came to say the exact same thing, all the problems mentioned aren't unique to continuations. I'm not saying this makes a positive argument to use coroutines everywhere, but it's not their fault.

As ajuc mentioned, long-running processes and early/late bound is always a thing. Same with database migrations. Heck, even clients accessing a versioned api (foo.com/api/v1/bar) vs not has the same consideration.

> How long do you wait before invalidating the session and free its resources?

Same decision has to be made for explicit session data like login state and pagination cursors in eg. Facebook's graph API. Continuations are larger and therefore this question may have more weight.

> What resources does a continuation hold on to?

Anything reachable (static and/or dynamic analysis). And if you run your program in a monad (or other restricted, pure manner), then you can control when a function can suspend, like not in the middle of paging a database.

> Does opening a new tab duplicate any held resources by the continuation?

If you live in an immutable world, you get duplication for free with structural sharing. Same goes for an OS loading a shared library once and giving the same pages to multiple programs.

I do agree that having a blob of stuff serialized isn't very nice. Same goes for closures as well. The example I always compare in my head is a functional representation of a set vs. any other data structure.

I toyed around with an interpreter that would let you reflect a closure (same could be applied to continuations) to a program, which is akin to a residual program in partial evaluation. Then you could do whatever you want with the source of the closure/continuation. For the early/late bound question above, you could analyze the reflected continuation and decide exactly which bits you want to rebind before continuing the continuation.

Re: Writing a Lisp: Continuations

#47
post #26
post #12

Continuations are strangely underused, as they enables writing long-living processes in a simple way, without having to keep them in running in a thread, or even in memory. Then a real programming language can replace all "business processing" crap languages. Let's say you write a framework that escapes to a continuation whenever the "process" is waiting for Futures or Promises to complete, and returns the thread to…

If only Brendan Eich had ended up "doing Scheme" in Netscape as he was originally recruited to! ( https://news.ycombinator.com/item?id=2786720 )

Javascript survived (and eventually caught on) not just because it was the "only game in town" for the web, but also because it was familiar.

If Eich indeed had produced a scheme, then it would have been superseded and replaced by another algol-derived language by browser makers soon -- and users would have flocked to that.

Re: Writing a Lisp: Continuations

#48
post #17

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?

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, tho…

Would that be like having a yield statement AND passing a context (e.g. binding a this that represents "current-continuation")?

Re: Writing a Lisp: Continuations

#49
post #47
post #26

Earlier quoted context omitted.

If only Brendan Eich had ended up "doing Scheme" in Netscape as he was originally recruited to! ( https://news.ycombinator.com/item?id=2786720 )

Javascript survived (and eventually caught on) not just because it was the "only game in town" for the web, but also because it was familiar. If Eich indeed had produced a scheme, then it would have been superseded and replaced by another algol-derived language by browser makers soon -- and users would have flocked to that.

If familiarity mattered that much, why wasn't HTML itself replaced by something with curly braces, or CSS by something procedural?

Re: Writing a Lisp: Continuations

#50
post #49
post #47

Earlier quoted context omitted.

Javascript survived (and eventually caught on) not just because it was the "only game in town" for the web, but also because it was familiar. If Eich indeed had produced a scheme, then it would have been superseded and replaced by another algol-derived language by browser makers soon -- and users would have flocked to that.

If familiarity mattered that much, why wasn't HTML itself replaced by something with curly braces, or CSS by something procedural?

Because HTML wasn't a programming language.

Template languages were like that (e.g. SGML) and worse.

Besides, unlike JavaScript it wasn't the product of a single vendor, but a standard, and the basis upon which the web stood from the beginning.

Post reply on HN