First class continuations

[RLake@...]

> > begin name chunk end
> >
> > is an expression (not a statement) in which "name" is locally defined
as a
> > first-class continuation with the restriction that it cannot be used
after
> > the begin block is exited.

> What is a "first class continuation"?

Sorry, that was pretty jargony.

first-class means that it is a real object which can be passed around as a
value.

All programming languages have continuations but few of them make them
explicit.

I don't know if you have ever seen Tom Stoppard's "Rosencrantz and
Guildenstern are Dead", but it expresses the idea pretty well: "every exit
is an entrance somewhere else". At any point in a computer program, there
is something which is going to be done next: that is the continuation.
Generally, the continuation will be done with something (the state of the
current computation). We usually think of this as a return, but we could
think of a return as calling the continuation. (Don´t get stuck on how the
stack works... this is just conceptual. The stack is part of the state.)

So a continuation expresses that concept: it is a function *call* which has
the effect of *returning* somewhere.

Scheme, amongst other languages, has full continuations. But this is
difficult (and inefficient) to implement so it needs to be used with
caution -- one of the oddities with full continuations is that you can
return into a computation several times, and that does create havoc with a
normal stack. A restricted continuation can only be used once, because the
restriction is that it is no longer valid once the block that it is created
by is exited: calling the restricted continuation exits the block, so
that's it.

So you could say that it is a "long return". But it is interesting to note
that almost all returns are "long":

function f(x)
  for k, v in table do
    local x, y
    ...
    if x == y then
      local z
      ...
      if not z then return end
    end
  end
end

The return statement has exited through two blocks with local variable
declarations. That was pretty long. Admittedly, the mechanism I propose
allows even longer returns. :)

In effect, a restricted continuation is simply a stack pointer: calling the
continuation unwinds the stack to that point, pushes its arguments as
results, and life goes on. That's exactly what the return statement does;
the only difference is that in the case of the return statement the
compiler knows where to unwind the stack to, whereas with the continuation,
the interpreter has to get the new stack pointer out of the continuation.

The slightly more difficult part is enforcing the restriction. When a block
that creates a continuation is exited, the continuation has to be zapped.
The usual mechanism is to put block finalisers on the stack; when the stack
is unwound, the finalisers are executed in turn (reverse order, if you
like). This is, for example, how c++ manages to call destructors of
stack-allocated objects, and is a plausible mechanism for c++/java style
exception handling.

As I understand, Lua now does process the stack whilst unwinding it, in
order to deal with closures. So block finalisers should not be complicated
to add, and that deals with the only complication in non-local returns
(except, I suppose, for explaining what they do.)

Some languages make block finalisers explicit, which is also a useful
feature. It is a simple mechanism which can be used to deallocate allocated
resources (close files, for example), or do useful bookkeeping. For
example:

function f(table)
  io.output "logfile"
  for k, v in table do
    if is_what_we_want(k)
      then
        io.write "Processed "..k.."\n"
        table.k = computation(v)
        return v
      end
  end
  return nil
finally
  io.output(io.stdout)
end

The finally clause is unconditionally executed just before the
function-block is exited.

>> However, it can be passed as an argument. That is, name is defined as a
>> function with a variable number of arguments; calling it causes the
begin
>> block to evaluate to those arguments.

>Ah, I think I see! It's like a "return" statement but each instance is
bound
>(using some sort of closure) to the upper block it was created in! Ie, it
is
>a sort of set-jump / long-jump thing (well, more of a long-return, I
>suppose). Is that right?


We have the chance to lift millions out of poverty.  Only one thing is
missing -- you.

Please join the Oxfam trade campaign at http://www.maketradefair.com

Oxfam works with others to find lasting solutions to poverty and suffering.

Oxfam GB is a member of Oxfam International, a company limited by guarantee and registered in England No. 612172.
Registered office: 274 Banbury Road, Oxford OX2 7DZ.
Registered charity No. 202918.

Visit the web site at http://www.oxfam.org.uk