On Sat, 2006-01-07 at 03:19 +0100, Nicolas Cannasse wrote:
> There is not yet call/cc in Neko.
I know .. my comment is about overall design.
> I don't have big knowledge of it (just through the iterator/yield python
> statement) so I'm still thinking about how it should work in Neko, in
> terms of both API/Language constructs and implementation. If you have
> suggestions I'm open.
The Felix technique is OK. I present it with some sugar making
it look more ML like:
let g i E = if i = 0 then E 0 else 1/i in
exception X a = printf "Divide by %d " a in
printf "%d" (g 1 X)
The implementation is:
begin
let X a = printf "Divide by %d "; goto error in
printf "%d" (g 1 X);
return;
error:
return;
end
This requires a non-local goto. This can be implemented
with .. hehe .. an exception. The difference is the target
must be known.
This is also call/cc with a constraint. What I have
done is split up the original code into TWO continuations.
The second continuation is introduced by a return ending
the first one, followed by a label starting the second one.
The code in g() can call the current continuation by
saying 'return'. It can call the error continuation
by invoking it explicitly .. thats the closure X.
In fact X is an ordinary function with an abnormal
return .. it executes a different 'rest of the program'
than a plain 'return' would.
The funny thing about continuation passing is that it is
the ONLY way to transfer control anyhow. Neko can already
do it for that reason -- there isn't any other way.
Every CPU can do it -- the return instruction is precisely
the 'throw' of continuation invocation, and the subroutine
call pushing the callers return address is nothing more than
passing the current continuation.
So basically, goto IS precisely call/cc in a restricted machine
model. All you need is goto and you have everything :)
[Well you need a bit more but not much .. Turing machine etc .. :]
The Felix code for the above is ugly and error prone due
to lack of syntactic sugar:
proc g(x:int, error: int -> void) {
if x == 0 do error x; // execute passed error handler
else return 1/x;
done;
}
proc f() {
proc error (x:int) { print "Divide by "; print x; goto bug; }
val k = g 1 error;
print k;
return;
bug:>
return;
}
The important thing is that inside g, you can invoke the procedure
error, which executes its body IN THE CONTEXT OF f since it is
a closure .. and then does an abnormal exit by jumping
to code in f. The code before 'bug' is the first continuation,
the code after 'bug' is the second one. Therefore the procedure
f has two continuations, and one (the bug one) is passed into g
via the closure of error. Note the error handler here accepts
an argument .. note it has to be correctly typed. And note
that it is impossible to throw an error which isn't caught!
In this particular case, whether or not there is an error
inside g, f returns having printed the result of the division.
In general call/cc the program can diverge to two distinct
paths .. this would be done here by passing, in turn,
an alternate continuation into f which might be invoked
after 'bug' instead of it doing a normal return.
The point here is not that this is better than exceptions:
the point is that this IS call/cc. It is nothing more
than being able to do a goto because continuation passing
style is nothing more than ending every function with
a goto. Its just that you can explicitly pass address
to goto into a function and CHOOSE how to terminate:
usually one jumps to the first address passed which
by convention is the point in the calling code which
'continues on'. Subroutine call instructions enshrine
that idea .. but its just a special case of passing
a set of alternate continuations.
BTW: the principal advantage of continuations is not
some weird special case error handling but ultra high
performance user space microthreading.
In this model you have millions of suspended continuations
and use some kind of scheduler to 'continue' one of them
for a while, then continue another one. Since each
continuation is just 'the rest of the thread' you are
effectively interleaving millions of threads.
This is precisely what OS threading does .. but it is extremely
slow and heavyweight because the 'rest of the thread' can
be any point in the code, and, worse, the threads might
run concurrently on a multi-processor. Provided you don't
need fairness or concurrency, micro-threads provide what
programmers *really* need when they use threads --
control inversion.
The beauty of continuation passing is that it is control neutral.
Unlike the master/slave relationship subroutine calling enforces,
continuations just use 'goto' to jump to the next code to execute.
You can 'goto' your callers return address if you want, but equally
you can 'goto' anywhere else.
BTW: by 'goto' I mean a goto that can accept an argument,
unlike C gotos which require a fixed, local, label.
GNU C allows this:
label: ...
void *v = &label;
..
goto *v;
Unfortunately gcc is a very bad C compiler and cannot
compile large functions. This leaves one with the problem
that you cannot just goto a label in another function
and expect it to work (since the arguments on the stack
would be all wrong). The workaround which C allows is
just to define one single large function and manage
the stack manually .. but this workaround fails with gcc
because the compiler is so poor.
This leaves language designers without a portable target
language and is a major impedient to designing a new
executable (fully compiled) language. C-- might solve
this problem, if it ever got enough back ends to be
practical.
MLton and Felix use a weird assembler label
trick developed by Fergus Henderson for Mercury,
to work around this (which turns out not to work so well
on newer gcc versions). Haskell uses a perl script to
known as the evil mangler, to rewrite generated assembler
source files. Ocaml gives up entirely and has its own
back end native code generator.
Unfortunately, any system .. including Neko and any other
VM .. which wishes to allow extensions to the API which call
C, and which also wishes to allow callbacks into the VM ..
is affected by this problem. The C stack gets in the way
of neutral control transfer. So even if it is implemented
in the Neko VM .. it will never work properly with C extensions
that need to callback into the VM.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
---
Neko : One VM to run them all
