Ponder, if you will, how you call a function:
foo(1, 2, 3)Or, if you prefer a low-level pseudocode (where Px are parameter slots),
P1 = 1 P2 = 2 P3 = 3 invoke fooNo big deal, and pretty straightforward. Yeah you can debate stack vs registers, parameter passing conventions, and stuff like that, but for now... it's irrelevant.
Next, ponder multimethod dispatch. Everything looks identical to the previous example, except that the invoke of the foo sub 'object' looks at the parameters and decides where it needs to go. (Presumably there's a list of sub-functions and their associated parameter lists that gets searched, or something. The exact mechanism is irrelevant here)
Okay, then... think about how we return from that sub. Now, in a 'normal' call/return scheme, the return value (and there's almost always just one) gets stuck in the return register or on the top of the stack, and the next entry on the stack's the return address. We yank out the return address and jump there. When the function/method returns the code that made the call yanks the result out of the return slot, wherever that is, and then keeps on going. Calls and returns are fundamentally different.
In a continuation passing system Things are a little different. The call is the same--fill in the slots and invoke the sub object, passing as one of the parameters the return continuation. The return, though... well, the return looks exactly like the call. That is, source which looks like:
return 12turns into
P1 = 12 invoke ReturnContinuationThis has a number of ramifications. First, it actually simplifies the compiler a bit, since you don't have two 'destination' control cases (function call and return) but just one. That means you can leverage your function call system to make it easy to return multiple values from a function, since the code gen's the same. (The code immediately after a function call is the same as the code at the beginning of a function.
This means you can do:
P1 = 12 P2 = "Foo" P3 = SomeObject invoke ReturnContinuationand return multiple values. If your language supports it, of course.
Now, even a cursory inspection will show that the function call and return continuation invocation are the same thing. What does this mean? Well, of course it means you can do MMD on function returns as well as on function calls.
What use this? Well, if you have a standard error convention you could easily set things up to dispatch to the error routine without having to code up the check -- the compiler can pass in a MMD return continuation. Still, most languages are ill-equipped syntactically to deal with this sort of thing, and annotating the function call itself would get unwieldy. Most languages but... not INTERCAL.
Everyone, I'm sure, is familiar with standard INTERCAL's COME FROM statement, which is the inverse of GOTO. And, I'm sure, everyone's also familiar with Quantum INTERCAL, which allows multiple COME FROM statements for the same label, so your program becomes a quantum superposition of all possible destinations which ultimately collapses (if the system or programmer doesn't first) into a result. Between that, though, there's a middle ground. If you annotate your COME FROM statements to note not only where control comes from but also the conditions in which it does (naming functions, since of course we're all using Functional INTERCAL for the good programming practices it allows) you've an amazing amount of expressive control flow at your fingertips. Cool, huh?
(I suppose you could annotate functions in lesser languages to do the same thing, and treat the function call as if it were a tail call into the annotated function, but that seems kinda wussy in comparison)
Posted by Dan at August 17, 2004 02:58 PM
| TrackBack (3)
So you'r saying it will be really really easy to implement Basic's "On Error goto" too.
Posted by: Struan at August 17, 2004 04:29 PMYep, that'd be easily doable with this, though you'd likely see that done with an exception handler instead.
Posted by: Dan at August 17, 2004 05:21 PMDan~
The whole idea is devilishly cool. If you allow MMD on value and not just type, you could even automagically go to different error handlers for different errors.
How did you ever come to this idea?
Matt
Posted by: Matt Fowles at August 17, 2004 08:50 PMSo delightfully evil. So devilishly beautiful.
Posted by: Aristotle at August 18, 2004 03:11 AMMaybe I'm taking this too seriously, but does this really have much to do with continuations or CPS in the implementation sense, as opposed to the conceptual sense in which continuations may have freed your mind to think about this?
Normally, when you call a function foo, 'foo' is a name for a pre-existing function, or set of functions in the multimethod case. But "ReturnContinuation" is not (necessarily) the same kind of name, depending on the design you have in mind. It would normally be a closure (more or less) constructed at the time of the call (even in e.g. C, where it's just the current stack plus the return address).
Any multi-method dispatch that's done with return continuations would have to involve generating the default return continuation as usual, along with a set of other possible functions that could be invoked by the dispatch mechanism. That set might be based on a naming system (e.g. users might define their own ReturnContinuation functions which would be candidates for dispatch, or specify what the name of the return continuation functions in a given piece of code should be, etc.), or it might be based on some other system, in which case it would be different from the normal function dispatch mechanism.
But there's no particular requirement that a language have any kind of explicitly-implemented continuations to support this, i.e. it could just as easily be done without explicit continuations or CPS in the implementation. It's more about how the compiler constructs the code that's invoked at return time (OK, conceptually that's a return continuation, but we don't have to be talking about CPS).
I think the only thing that continuations give you "for free" here is that once you've implemented continuations with multiple arguments, you've worked around the traditional C-style stack discipline one way or another, and with CPS, that takes care of returning multiple arguments. But that's not a continuation-specific issue either.
Of course, I'm not arguing with the idea of thinking about this stuff in terms of continuations. All I'm really saying is that multimethod-dispatch on return values could just as easily be implemented in Parrot-without-continuations. I'm not sure what that would imply w.r.t. Parrot's ability to host quantum INTERCAL.
Posted by: Anton van Straaten at August 18, 2004 04:07 AMWhile you could do this without an underlying CPS system, it'd be a pretty massive pain in the neck. Besides all the code duplication for MMD (since the call and return versions aren't going to be the same), every return needs to be checked to see if it's a tail call or a true return. Doable, but nasty and I don't think I'd want to be the guy maintaining the compiler to make this all work out right. (There's certainly no need for explicit language-level continuations, but that's all syntax and I don't really care about that. It's the semantics and the implementation architecture I care about. The rest is all just typing)
So, while I could do this if parrot didn't do continuations, I don't think I would. Far too mcuh hassle. Since we're CPS, though, it's essentially free, and free is good. Heck, we wouldn't even pay any cost in the cases where you weren't doing something like this, and I like that just fine too.
Posted by: Dan at August 18, 2004 11:15 AMWhile you could do this without an underlying CPS system, it'd be a pretty massive pain in the neck. Besides all the code duplication for MMD (since the call and return versions aren't going to be the same)
I probably should first have asked the question that I originally alluded to: how is it that you're going to make the call and return versions the same, i.e. how is an actual return continuation going to be added to the set of possible functions to be invoked upon return, and/or how are the other candidates for invocation going to be specified?
When invoking "foo" via MMD, the typical scenario is that there's a dictionary somewhere of previously defined functions named "foo", and the appropriate foo is looked up based on the specified arguments. With return continuations, I don't know how you're planning to get away with the exact same mechanism. For example, the "real" return continuation, generated at the call site, might have to be added to the list of function candidates for the name ReturnContinuation. As I see it, whatever mechanism you use to do this - to turn the actual return continuation into an MMD dispatch - would have an equivalent of similar complexity in the non-CPS case.
every return needs to be checked to see if it's a tail call or a true return
If the CPS-free system supports tail calls, then the MMD for returns could simply involve a jump into a table which could contain either a tail call, or a traditional return. This relates to my point above: the apparent extra level of indirection, relative to the ordinary function call case, might be needed anyway, depending on the specifics of what you have in mind for managing MMD returns.
Since we're CPS, though, it's essentially free, and free is good.
If I'm correct above, then there is that little cost for implementing MMD in the return case. But perhaps you have another fiendishly clever way around this...?
I probably should first have asked the question that I originally alluded to: how is it that you're going to make the call and return versions the same, i.e. how is an actual return continuation going to be added to the set of possible functions to be invoked upon return, and/or how are the other candidates for invocation going to be specified?
Okay, I see the problem here. In the presence of function pointers, closures, and other indirect function access mechanisms, you have to (or at least it seems reasonable to me that you must) defer the MMD lookup for dispatch until actual invocation time, so you might as well either wrap up the code in the invoke function, or delegate invocation to the thing you're invoking.
Parrot does the latter--letting the thing being invoked figure out what to do--and that's what gets stuck in my brain most of the time. It makes invoking a sub, method, closure, coroutine, continuation, or return continuation identical so we don't have to care at all what the thing we're invoking is. (Well, this isn't entirely true, as method calls need to stash the method away somewhere, and we don't usually generate a return continuation to pass into a return continuation we're invoking, but we could do them all the same if we wanted)
There is some overhead you have to deal with because of this, but for us its overhead we're already paying (since there's no compile-time certainty about anything, so we need to do all the MMD checking at runtime) so it's free, which is nice. Dunno if you could get this for free in a system set up for more static languages but, then, in that case you probably wouldn't be able to make a function multiply-dispatched at runtime either. (Whether this is a good or bad thing is a separate issue, and I think I'll leave it alone)
Posted by: Dan at August 18, 2004 01:52 PMRight, so if you "delegate invocation to the thing you're invoking", in CPS-free Parrot that would mean something like: perform the return as usual, but the return-handling code - wherever that is - would dispatch on the returned arguments.
In the CPS case, afaict, that return-handling dispatching code should be roughly equivalent to the code that would need to exist in, or be called from, your return continuations. I think the "overhead [you're] already paying" is really what makes this feature easy or free, and that would exist with or without CPS.
BTW, if anything above sounds as though I'm thinking of a more static case than you are, adjust it until it doesn't. I'm not concerned with making things more static (we have that argument covered over on LtU ;)
Anyway, my point is a really picky one, since if you have tail calls and multi-value return then CPS seems like a sensible way to implement that, so my point is sort of moot. It was just an attempt to delineate issues that I think are theoretically disjoint, i.e.: does MMD on return really benefit from CPS, everything else being equal? In the absence of any really concrete proof-like arguments, to prove that it doesn't, I'd have to implement a CPS-free Parrot with MMD on return, and I'm fairly sure I'm not going to do that. :)
Your picky point is a good one--doing MMD on return values doesn't require CPS. After giving it a bit of thought I could implement it in a more traditional call/return style language assuming tail calls could be done. (And since this'd be implemented way down at the codegen level it's pretty easy to ensure it can)
Having said that, I don't think I'd want to, since it'd be a mess of duplicated code and annoying twiddly bits, but that's a separate matter entirely. (I'm not sure I would've seriously considered this without having moved over to a CPS system for Parrot, so I suppose it's one more crime to heap at the feet of continuations... :)
Posted by: Dan at August 19, 2004 02:39 PMThis is reminiscent of a year-and-a-half old thread on the LL1 Discuss
list:
http://www.ai.mit.edu/~gregs/ll1-discuss-archive-html/msg04650.html
http://www.ai.mit.edu/~gregs/ll1-discuss-archive-html/msg04664.html
http://www.ai.mit.edu/~gregs/ll1-discuss-archive-html/threads.html#04724
I HAVE HAD MY AFRICAN GREY FOR 8 MONTHS NOW SHE IS VERY BRIGHT.BUT DOES NOT TALK YET HER FEATHERS ARE VERY HEALTHY LOOKING. BUT HER TAIL FEATHERS GROW FUNNY. SHE PULLED HALF OF THEM OUT NOW HER TAIL FEATHERS ARE HALF LONG HALF SHORT.WILL THEY EVER GROW BACK PROPERLY.
Posted by: RUTH VAN DUYN at April 14, 2005 01:58 PM