Re: implementing call/cc with only closures, no special forms ?

totally love to moderate a philly-lambda discussion/workshop sometime, where we pick this apart, understand it, and rebuild it better, if this topic is of interest.

On Sat, Mar 31, 2012 at 2:30 AM, Dustin Getz <dustin.getz@gmail.com> wrote:

hi guys,

a month ago I wrote: "i think you might be able to implement call/cc with only closures, but that implies that we can do things like turn third party blocking code into cooperative code per gevent[3] which is absurd, that's a ridiculous statement."

i've mostly got this figured out, i think. my conclusion is that you can indeed implement a continuations-based framework to do this in *any language with closures and tail-call optimisation*. you don't need native continuation support by modifying the interpreter, e.g. python's generators and ruby's callcc!! (this is mind blowing to me.) I'm highly interested if any of you lambda calculus folks can confirm my conclusion, though this seems obviously correct to me now.

recap:
continuations are an idea rooted in lambda-calculus and can thus be implemented with only closures.
you can implement continuations with monads, though I don't think you *must* structure your code like a monad to implement a continuation, concern with syntax was a red herring for me.

the blogger provides a pure python implementation of callcc[1], he happened to use a monad. (I don't understand the monadic implementation yet, but i think monads are tangental to the main point).
the blogger uses clever generator hacks in order to make monads look like they do in these languages, but this is just syntax, you don't need generators to make continuations *possible*.

[1] original article about callcc in python: http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html

lambda calculus continuations use "continuation passing style" which means that the continuation, the thing you will "goto" ("resume execution at") must be a function. you can't resume the middle of a function, you have to structure your functions so you always "resume" at the start of a function. compare this to a native implementation of continuations (callcc in ruby, generators in python) can resume in the middle of a function, but this isn't critical if you structure your code with CPS in mind. note also that native implementations are vulnerable to bugs - ruby's callcc is famous for leaking memory, and google shows gevent has been bitten by memory leaks as well.

tail-call optimisation is required because the last action in callcc is to call the "jump here to resume" function, which would otherwise consume stack. this does mean the stack is less useful for debugging, but this is tangental to my investigation, and anyway we've already thrown stack traces away by choosing to use continuations.

meta point 1: tail call optimization is useful for more than just iteration and lazy seqs. (you don't *need* TCO to implement lazy seqs imperatively.) Guido wrote "TRE only addresses recursion that can easily be replaced by a loop :-)"[2] which is just wrong.

meta point 2: the Hoare Property states: "There are two ways to write code: write code so simple there are obviously no bugs in it, or write code so complex that there are no obvious bugs in it." i believe you can use this technique to build an "obviously correct", *guaranteed not to leak memory* impl of continuations given only two assumptions about the language: 1) correct impl of closures, 2) correct impl of tail call optimization. i think this is huge.

[2] guido on TCO in python (interesting read): http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

i'd be interested in presenting this to the group for explanation and discussion (especially if it turns out i'm wrong), if this is of interest to anyone else. It would certainly ground the CPS whitepaper we read in functional fall.

On Wed, Feb 22, 2012 at 10:04 PM, Dustin Getz <dustin.getz@gmail.com> wrote:
> i think i may have reconciled the problem - he implements callcc and
> continuation-monad without generators, but the actual usage of callcc as
> defined -- `return callcc(self.react)` -- self.react is itself a generator.
> this generator could (i think) be re-implemented with lambdas, but now the
> block passed to call/cc must conform to our interface. which means we can't
> use call/cc with arbitrary code. if i chase down the implications of this, i
> imagine we will end up concluding that, to turn blocking business logic into
> cooperative via low level monkey patches in the style of gevent, would also
> require altering the structure of the business logic itself.
>
>
> On Wed, Feb 22, 2012 at 9:02 PM, Dustin Getz <dustin.getz@gmail.com> wrote:
>>
>> this came up after redsnake last night - I mentioned to someone that I had
>> seen a "lambda" implementation of callcc in python. Which, if that's
>> actually possible, is pretty mind-blowing - because it doesn't require
>> patching the runtime/interpreter !! I'm not quite sure if its possible or
>> how close we can get, but here's the link I was talking about[1]:
>>
>>
>> [1] http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html
>>
>> He implements a few monads in python, including continuation monad. It
>> will take me significant study to understand this code - maybe you guys
>> would be interested in picking this apart at a future meetup - but here's
>> the author's conclusion:
>>
>> So, you can use monads with elegant syntax in any language that has
>> closures and any of the following:
>>
>> do syntax (Haskell, C#)
>> call/cc (Scheme, Ruby)
>> bidirectional generators (Python 2.5, a future _javascript_?)
>> coroutines (Lua, Io)
>>
>> my question is, can you implement continuation-monad with "un-elegant"
>> syntax with *only* closures, skipping the generators? I think maybe you can,
>> because 1) haskell's do-notation is just syntactic sugar over the closures,
>> and 2) you can at least implement one common generator pattern - lazy seqs -
>> in python without generators[2], which got me wondering if you can implement
>> a generalized generator using just lambdas, and now my head is spinning and
>> i'm saying stupid things like "i think you might be able to implement
>> call/cc with only closures" but that implies that we can do things like turn
>> third party blocking code into cooperative code per gevent[3] which is
>> absurd, that's a ridiculous statement. I'm not even making sense anymore, so
>> I'm going to stop writing and click "send" now :)
>>
>> Dustin Getz
>>
>> [2] my implementation of lazy seqs with only
>> closures: https://github.com/dustingetz/sandbox/blob/master/etc/lazy.py
>> [3] lightning talk slides where we use callcc to make third party code
>> cooperative: https://docs.google.com/present/view?id=dv9r8sv_82cn7dngcq
>
>

--
Trevor Lalish-Menagh
trev@trevmex.com
484.868.6150 (mobile)
trevmex (AIM)