continuations, was Re: Google Summer of Code 2011

[Tony Finch <dot@...>]

On Tue, 22 Feb 2011, steve donovan wrote:
>
> I've tried to understand Scheme continuations, but so far this brain
> has refused to make the jump.
>
> What would be a hypothetical example in Lua syntax?

The first thing to note is that coroutines are equivalent to one-shot
continuations, so a lot of the fun you can have with continuations can
also be had with coroutines. But full continuations can get you into an
enormous tangle, and they have weird performance implications, so they
are probably not of much benefit to Lua.

The way I like to think of continuations is as follows.

Think of a tail call, which is effectively the same as a goto which
replaces the current function call with another - as opposed to a normal
call which nests. Now imagine that return is a function which goes back to
the invoking frame instead of creating a new stack frame or replacing the
current one. Something like:

  function foo1(arg1, arg2)
     -- code code code
     return res1, res2, res3
  end

  -->

  function foo2(ret, arg1, arg2)
     -- code code code
     ret(res1, res2, res3)
  end

I've written the return function as a parameter - it's a bit like the
return address passed to a machine code function. This return function is
your continuation: when you call it the rest of the program continues.

So in the calling function,

   a,b,c = foo1(d,e)

is like

   a,b,c = call_cc(foo2,d,e)

It gets harder to imagine what is going on when you do fun things with
continuations like storing them in data structures or returning them up
the stack.

A one-shot continuation is a continuation that can only be invoked once.
As well as coroutines you can use them to implement exceptions. Here's a
coroutine library implemented using call_cc.

  local running

  function coroutine.resume(t, ...)
    function go(cont, ...)
      local f = t.resume
      t.resume = nil
      t.yield = cont
      t.caller = running
      running = t
      return f(...)
    end
    return call_cc(go, ...)
  end

  function coroutine.yield(...)
    function go(cont, ...)
      local t = running
      local f = t.yield
      t.yield = nil
      t.resume = cont
      running = t.caller
      return f(...)
    end
    return call_cc(go, ...)
  end

  function coroutine.create(f)
    return { resume = f }
  end

The weird performance implications caused by first-class continuations are
the need for a garbage-collected stack, or an expensive stack-copy
operation when a continuation is used in a difficult manner.

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
Viking: Southeasterly 7 to severe gale 9, perhaps storm 10 later. Very rough,
becoming high in north. Rain or snow. Moderate, occasionally poor.