Subject: Re: Prototype kernel continuation-passing for NetBSD
To: Bill Studenmund <wrstuden@netbsd.org>
From: Jesper Louis Andersen <jlouis@mongers.org>
List: tech-kern
Date: 01/29/2004 01:02:41
Quoting Bill Studenmund (wrstuden@netbsd.org):
> Interesting. Do you have any recomended reading for those of us who aren't
> familiar with continuations? :-)
Function as a first class object: functions equal values. You can pass
a function anywhere you would pass a value. You have types of functions
as well as you have types of values and the type system handles
appliances of a given function later on.
Nested functions: functions defined inside other functions.
Closures: A function can always see it's scope from where it is defined,
regardless of where it is applied. Pseudo C:
(void->int) adder(x) /* adder is a function returning a function from
void to integers */
{
int counter = x
void f()
{
return counter++;
}
return f;
}
We can now apply it as:
adderfromfive = adder(5);
adderfromfive() => 5
adderfromfive() => 6
...
The point is that the counter is still live after adder() returns and
you can still access it after adder returns. But since counter were
local it is only that _particular_ f() function that can see it. This
is called a closure.
Technically you normally convert them to ordinary functions in modern
compilers by a closure-conversion step, which in turn eliminates them
for the compiler backend. See A. Appel. ''Modern Compiler Implementation
in {ML, C, Java}''.
The continuation is probably the hardest part to explain, but it is a
very powerful absctraction once you get it. The continuation of a
function is what will happen after the function returns. It is the
environment in which the function is called. Say we have the expression
3 + f() - 7;
Letting (*) stand for the continuation, the continuation of f() is:
3 + (*) - 7;
Languages like Scheme, Standard ML and Haskell has functions which
enables you to pass the _current_ continuation as a function. Normally
labelled call-with-current-continuation or call/cc. In Scheme, when
you call/cc, it expects an escape function. That is, a function of
one argument which when applied with some value which return you to
the continuation location where the call/cc function initially were
invoked with the one argument as the value substituted for the (*).
For the example:
int
g(escaper()) /* g() expects an escape function */
{
if (foobar) {
escape(5);
} else {
return 3;
}
}
...
3 + call/cc(g()) - 7;
Now, if foobar is set, we escape with the value 5 so:
3 + 5 - 7 => 1
On the contrary, if foobar is not set:
3 + 3 - 7 => -1
The powerful thing of this is that the escape function provides every-
thing needed for a callback. Think of call/cc as a way to place a
beacon somewher in the code to which you can always return. setjmp()
and longjmp() comes to mind.
For a maybe better explanation, there are plenty of Computer science
universities with examples of how to explain this to their students.
Just plug in the keywords.
--
j.