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.