continuations, was Re: Google Summer of Code 2011
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: continuations, was Re: Google Summer of Code 2011
- From: Tony Finch <dot@...>
- Date: 2011年2月22日 19:28:10 +0000
On 2011年2月22日, 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.