Re: Function Fall Next Paper: Continuation, functions and jumps

On Tue, Oct 11, 2011 at 11:07 AM, Ben Karel <eschew@gmail.com> wrote:

On Fri, Oct 7, 2011 at 10:35 AM, Kyle R. Burton <kyle.burton@gmail.com> wrote:

> Our next paper is Continuation, functions and jumps
> (http://www.cs.bham.ac.uk/~hxt/research/Logiccolumn8.pdf) and we will
> be discussing it on Wednesday, 10/19/2011, at 6:30 pm on the 45th
> floor of the Comcast Center. Food, as always, will be provided by
> Comcast Interactive Media.

I see the paper mentions both Lambda Calculus and Pi Calculus. I've
actually already read through the paper while skipping those equations
- does anyone have a recommended resource that's an introduction to
Lambda or Pi Calculus? So it'd be possible for a drop-out like me to
read the paper in it's full academic glory?

> I am really looking forward to learning all about continuations!

Interesting that the paper only goes so far in describing
continuations - it almost describes them as a curiosity w/o any reason
as to why you'd want to consider them [1] or, even better, use them.
It also only really describes them in terms of CPS, which is a good
way (IMO) to get a base understanding of them, but misses some of what
comes with full continuation support.

I definitely agree. CPS translation in compilers isn't so much of a sister technique to callcc, it's more of a cousin. There are many applications for continuations: coroutines/generators, backtracking search, exceptions, C-style break/continue, web frameworks, spaghetti stacks for fork/join parallel programming... A language with continuations can provide those features as libraries rather than built-in primitives, and theoreticians certainly prefer to formalize one mechanism rather than N different features.

In practice, many (most?) of those techniques end up being implemented in a more restricted/specialized way, for reasons of efficiency or philosophy. For example, since the entire point of Prolog is to make backtracking search a fundamental part of the language itself, there's no benefit to be gained by having backtracking in a library, and there's certainly speed to be lost. But for the designer of a general-purpose language, continuations means never having to say you're sorry (for not including feature X)...

It's going to be an interesting discussion, that's for sure :) I've
had a very long and difficult journey trying to wrap my mind around
continuations and I'm not convinced I really get them. There are
terms that I'm not convinced I fully understand the difference
between: CPS (Continuation Passing Style); Delimited Continuations
(supported in Common Lisp, which can not support 'full'
continuations); and 'full' continuations (which are supported by
Scheme). I'm not sure where Ruby's continuations fall here.

Continuations are a deep topic, I'm still wrapping my head around 'em.

CPS is just a style of writing programs where code "returns" by calling a continuation it was given. You can write code in CPS even if you don't have continuations as a language feature, by using first-class functions in place of continuations. CPS is interesting in practice because it's a pretty decent way of doing (part of) a compiler, and it's interesting in theory because it's a (relatively) simple way of taking a powerful feature (continuations) and encoding it an using already-well-understood feature -- first-class functions.

By slightly restricting how continuations can be used, you wind up with an extremely close analogy between continuations and basic blocks of control flow graphs, which makes it trivial to generate assembly from a CPS program. Being able to keep one syntax all the way from source to assembly makes it much easier to debug a compiler, because the output of each stage of the compiler is a valid program in the source language itself! I'd definitely recommend Guy Steele's original Lambda papers <http://library.readscheme.org/page1.html> and/or PreScheme for more insights.

The motivation for delimited continuations was to make continuations interact better with the REPL in Scheme. The current continuation of code running in the REPL includes the prompt for the REPL itself! Probably not what was expected or desired. Delimited continuations, one-shot continuations, and coroutines are all closely related. They're generally cheaper to implement than full continuations, but IIRC backtracking is trickier to do right with 'em.

Here's to hoping y'all will help me improve my knowledge on this.

Kyle

[1] Continuation Based Web Frameworks are one argument for
continuations. For me to get the 'why' of this, I think it is
important to understand IoC and how it changes how you have to write
your code (vs sequential code - like a command line program) and how
computation progresses through your program:

http://en.wikipedia.org/wiki/Inversion_of_control

The thesis for the continuation based web frameworks (Seaside,
Uncommon Web, Weblocks, ...) then is that they allow you to
're-invert' the IoC and start writing (what looks like) simple
sequential code again:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.2753&rep=rep1&type=pdf

There are other uses for Continuations - but they're often described
as a tool that allows you to invent/create your own control structures
(like: for, while, catch, throw, etc), including ones that allow a
non-linear flow to be written as if it was...

--
Twitter: @kyleburton
Blog: http://asymmetrical-view.com/
Fun: http://snapclean.me/