Lambda the Ultimate

So you're saying lack of full continuations, even in the presence of exceptions, sigjmp/longjmp, OS-level threads, etc. almost doubles your workload? I'm curious what kind of programming you're doing. For scripting, text-processing, interactive prototyping and simple dynamic and static web pages, I have never felt an urge to reach for continuations. Not once (and yes, I do know what they are and some ways they can be used). The only place I've felt the desire is in writing an NFA regex engine, something few people do, and still fewer *need* to do.

I can understand that full continuations might be interesting to people experimenting with programming languages (not just the trivial "DSLs" that seem to be so popular nowadays), but I don't think those people have ever been Ruby's target audience. And I think for that target audience, and indeed the great bulk of programmers, having a fully-operational alternative to Java/C# on the JVM/CLR is far more important.

===EDIT===
I think I may have been confused. :) I believe I was thinking of closures and not continuations. I think I'll leave this here for now, so that I can be corrected as necessary.
===END===

Caveat: I'm still working on learning all the proper terminology for things, but if I understand correctly, a continuation is when you essentially wrap up the current state into an object that can then be referred to later, right? (that's probably a horrible way of describing it)

Anyway, assuming I understand the term correctly, then the following silly Javascript (using the Prototype library) would be making use of continuations:


function foo( a ) {
var b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var c = 42;
b.each( function(i) { c += i * a; } );
return c;
}


Anyway, my point is (assuming proper understanding on my part), that I find it hard to imagine that you can't find places where continuations are useful in everyday programming. The kind of looping structures above are very common when using the Prototype Javascript library. I admit that if the language had something like a "normal" foreach as in Perl or PHP or whatever, then the above wouldn't be necessary, but that obviously isn't the only use I've seen for them. Another simple example:


function delayedMessage( m ) {
setTimeout( function() { alert(m); }, 10000 );
}


Being able to build constructs like this have been huge timesavers in some of the web apps I've worked on recently resulting in less code. I believe the code reduction comes from not having to manually move around so much state - I can wrap things up in a function object, return that, and then some code later can call it. It allows for far better composition and generality of functions in those (in my experience, frequent) situations where the needs of one function are almost identical to the needs of another except for some small logic in an if-test in the middle someplace.

I think I may have been confused. :) I believe I was thinking of closures and not continuations. I think I'll leave this here for now, so that I can be corrected as necessary.

There is a nice explanation of continuations in Kent Dybvig's Scheme book.

Section VII of Programming Languages: Application and Interpretation is another good introduction.

I can understand that full continuations might be interesting to people experimenting with programming languages (not just the trivial "DSLs" that seem to be so popular nowadays), but I don't think those people have ever been Ruby's target audience.

The problem is that the experimenters are the ones who coax other people into using a new language. I don't think Ruby's popular enough yet that it can afford to lose the early adopters—and that's what's going to happen, because nobody wants to trust their weight to a language that drops features. It doesn't matter whether those features are heavily used; if any applications stop working, the language's reputation will suffer.

The problem is that the experimenters are the ones who coax other people into using a new language.

We're talking about different kinds of "experimenters" here. I agree that PL design innovators draw others, but those others are fellow PL researchers. Look at the rise of ML, Scheme, and Haskell following research at (I believe) Edinborough, Indiana, and Glasgow.

Scripting language popularity, however, is driven by being in the right place at the right time with the right features. Witness Perl's rise as a scripting and CGI programming language when the alternatives were mostly C and shell/awk/sed. For those purposes, perl was clearly better, and enjoyed wide adoption. In this game, it might be the best move for ruby (from a popularity/dominance perspective, whatever that's worth...) to try to become a scripting language portable across the two new VMs that seem to be taking over our world. They're going after programmers like Steve Yegge, who's unsatisfied with Java/C# and has a voice in the broader programmer community, not Simon Peyton-Jones or Dan Friedman, who are advancing programming languages and training new PL researchers.

OK, so I was talking about early adopters. Early adopters draw users, and early adopters generally have enough experience to mistrust languages (applications, OSes, whatever) that remove features.

But my point is weakened if they plan to put it in post-2.0.

In my everyday coding I wanted continuations every time I write something asynchronous.
Examples include

-Communications with server
-Animations
-Flash to desktop communications
-Timers

Consider simple scenario communicating with some server from web-page in AJAX way (the same applies to Flash):

var session = server.login(user, password);
var mailList = server.getMailList(session.id);
for(var i in mailList){
 var mail = mailList[i];
 if(mail.subject.search("Important!")){
   var message = server.getLetter(sesion.id, mail.id);
   saveMessageLocally(message);
 }
}
server.logoff();
message("Done processing");

That code is simple and doesn't seem geeky at all.
But - there is no syncronous communications, only async.
Thanks, I have closures in JS, and this code becomes:

server.login(user, password, function(session){
 server.getMailList(session.id, function(mailList){
   for(var i in mailList){
     var mail = mailList[i];
     if(mail.subject.search("Important!")){
       server.getLetter(sesion.id, mail.id, function(message){
         saveMessagLocally(message);
       })
    }
   }
 server.logoff(function(){
   message("Done processing");
 })
 })
})

Almost the same in shape, but geeky and harder to understand.

Now add proper exception handlers, and it will become even more complicated.

The same about animations, e.g to deal 5 cards one after one the next code should work.

for(var i=0; i<cards.length; i++)
  dealCardWithAnimation(card[i]);

or just

cards.forEach(dealCardWithAnimation);

Simple, nice, clear.
But impossible.

At least I do not find the way how to achieve this without continuations. Maybe that way exists, but for now all I know that this way is continuations. Narrative JS tries to solve this, but with special syntax and special compiler.

So for me continuations are not about geeky code, but exactly the opposite. And if not 50%, then 30 at least are about continuations.

Oops. This comment intentionally left blank.

Would coroutines suffice for these needs or would you need the full call/cc?

sean So you're saying lack of full continuations, even in the presence of exceptions, sigjmp/longjmp, OS-level threads, etc. almost doubles your workload? I'm curious what kind of programming you're doing.

(I don't enjoy talking about myself as much as I used to. But perhaps I asked for it.) I'm not typical. Other folks wouldn't have as much load reduced by continuations unless they do a lot of async programming such as in high volume networking.

As noted on this page by Vassily Gavrilyak, async communications can be simplified by continuations. The semantics of Erlang might be a good for the sorts of apps I've been doing a while now, but the systems are in C++ and I don't get to choose.

My work is the intersection of what's available where I live during some job search time frame, and what interests me. But job availability is the big constraint. For the last six years this has landed me in Linux servers in C++ focusing on scaling and optimization of network communications, with mixed control models using both OS threads and async event dispatchers.

The part of full continuations I want is resuming a green thread after an async event arrives, since the way this gets done in systems I see is often fragile, with occasional exciting impedance mismatches with other threaded parts of the system. Addition of new optimization features has the effect of finding places where old things didn't fit together as well as they might have. Figuring out how to do something right in this context is now often more costly than all memory allocation I ever do (which used to be the big time sink).

Full continuations would only reduce my work load that much because absence of them creates a work load that tends to get routed to me instead of someone else. So it's partly self selection, and not something true for everyone. The work load crops up more when you try to maximize simultaneous server connections and minimize number of OS threads, and then keep adding entropy through change and feature addition.

It would be rather easier to marry together sync and async code, in threads and without threads, if continuations resolved various problems caused after folks paint themselves into corners. (I suspect the source code base to do servers I see would be much smaller, by some factor on the order of say, five, if full continuations were easily leveraged instead.)

Rys -- thanks for the detailed response. I think I understand why continuations might be a big win for you. However for what I do (and, I think, what many others do), the coarse-grained parallelism of OS processes or threads is enough, and the memory protection and encapsulation afforded by the former are enough of a win to make up for some performance limits. And from what I understand, getting full continuations to work without penalizing the performance of the rest of the language is a challenge like getting efficient laziness in Haskell or bare-metal performance in Java. In all these cases you need a "sufficiently smart compiler", which requires significant genius and/or money. For all its hype, I think Ruby has only a handful of VM hackers, and probably not enough to pull this off.

(btw, this is one of the reasons I admire C++ for all its faults: you never pay a performance price for features you don't use. If only this approach could scale smoothly over a broader range...)

The example above seems to me not so much a problem of having continuations but a problem of having first-class functions, i.e. being able to express a function as a literal, and of course enclosing the outer environment in it.

Without continuations one usually has to program the event loop using explicit Continuation Passing Style (CPS). With full language support for continuations one could program in the blocking I/O style while still allowing the behind-the-scenes implementation to be non-blocking. The reason for wanting to do such a thing is usually to avoid the "inversion" of control flow which can happen with CPS-style nonblocking I/O; most people probably find the blocking I/O style easier to follow and it permits one to hide a lot of (essentially irrelevant) state behind a nice abstraction barrier where it belongs.

I gather a number of folks consider continuations to be a really geeky feature that doesn't matter much to anyone in the real world.

Yep. This seems to be true even for persons like Paul Graham who invented continuation based web programming.

FWIW here's a very quick and dirty implementation of continuations and green threads in C++ via Duff's device and trampoline:

#include <stdio.h>

struct Continuation;
typedef Continuation* (*Function)(Continuation* cont);

struct Continuation
{
    Function code;
    int caseLabel;
    // any captured free variables follow..
};

struct Producer : Continuation { int i; };
Producer gProducer;

struct Consumer : Continuation {};
Consumer gConsumer;

enum { kChannel_Empty, kChannel_HaveValue, kChannel_EndOfStream }; 

template <typename T>
struct Channel
{
    int state;
    T value;
};
Channel<int> gChannel;

#define PROCESS_BEGIN                 switch (p->caseLabel) { case 0 : ;
#define PROCESS_YIELD(CONTINUATION)   p->caseLabel = __LINE__; return (CONTINUATION); case __LINE__ : ;
#define PROCESS_END                   } return NULL;

#define SEND(CHANNEL, VALUE, CONTINUATION)          \
    while ((CHANNEL).state == kChannel_HaveValue) { \
        PROCESS_YIELD(CONTINUATION);                \
    }                                               \
    (CHANNEL).value = VALUE;                        \
    (CHANNEL).state = kChannel_HaveValue;

#define ENDOFSTREAM(CHANNEL, CONTINUATION)          \
    while ((CHANNEL).state == kChannel_HaveValue) { \
        PROCESS_YIELD(CONTINUATION);                \
    }                                               \
    (CHANNEL).state = kChannel_EndOfStream;

#define ISENDOFSTREAM(CHANNEL) ((CHANNEL).state == kChannel_EndOfStream)

#define RECV(CHANNEL, CONTINUATION)                 \
    while ((CHANNEL).state == kChannel_Empty)    {  \
        PROCESS_YIELD(CONTINUATION);                \
    }                                               \

Continuation* producerFun(Producer* p)
{
    PROCESS_BEGIN;
    for (p->i = 0; p->i < 100; ++p->i) {
        SEND(gChannel, p->i, &gConsumer);
    }
    ENDOFSTREAM(gChannel, &gConsumer);
    PROCESS_YIELD(&gConsumer);    
    PROCESS_END;
}

Continuation* consumerFun(Consumer* p)
{
    PROCESS_BEGIN;    
    while (true) {
        RECV(gChannel, &gProducer);
        if (ISENDOFSTREAM(gChannel)) break;
        printf("%d\n", gChannel.value);
        gChannel.state = kChannel_Empty;
    }  
    PROCESS_END;
}

int main (int argc, char * const argv[]) 
{
    // initialize
    gProducer.code = (Function)producerFun;
    gProducer.caseLabel = 0;
    gConsumer.code = (Function)consumerFun;
    gConsumer.caseLabel = 0;
    gChannel.state = kChannel_Empty; 

    // run trampoline loop
    Continuation* c = &gConsumer;
    while (c)
        c = (*c->code)(c);
    
    return 0;
}

I've tried to compile your code with MSVC 8.0 and I got the following:

c:\temp\cc\main.cpp(57) : error C2051: case expression not constant
c:\temp\cc\main.cpp(59) : error C2051: case expression not constant
c:\temp\cc\main.cpp(60) : error C2051: case expression not constant
c:\temp\cc\main.cpp(68) : error C2051: case expression not constant

I used gcc. Your compiler is broken. A workaround is here.

...but I am using MSVC++ 2005 and Microsoft does not say the bug exists in that version.

Anyway I will try it with gcc...

EDIT:

I've tried it...it seems like a fancy way to alternate execution of two separate code blocks...cool, but I would not want to use that in projects.

By the way, on a lighter note, why 'real compilers' are not Microsoft ones? :-)

it seems like a fancy way to alternate execution of two separate code blocks

That was just an example of coroutines using continuations. You could put a real thread scheduler in there instead of calling the coroutine directly. I prefer the stackless ways to get continuations in C to those that use setjmp. Yes it is trouble because you have to CPS convert a lot by hand, or use the Duff's device trick.

Trampolines are described here: Trampolined style.    But I first read about them in this paper: Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine Version 2.5 in section 6.2.2.

From your example, threading is co-operative...a 'thread' yields execution to the scheduler which in turn decides 'what to do next'...this thing can not be preemptive, can it?

It needs to periodically perform an operation which can be redirected by a timer signal to switch the context.

In GHC the operation is memory allocation. In my implementation of Kogut it's allocating a stack frame.

The /Zi compiler option (Or "Edit and Continue" mode in the Visual Studio GUI) makes it possible to rebuild a modified function, and link it into a running executable on the fly. Very handy while debugging, but something a bit conceptually foreign to C++, which normally doesn't do runtime code modifications...

Prior to VS2005, __LINE__ were inaccurate if you did this, since changing the source code usually moved lines of code up/down the file even in functions which you didn't otherwise modify. This is the bug report that got linked to, which was 'fixed' in VS2005.

Now (in VS2005), __LINE__ is (only in /Zi mode) a global variable reference, which the toolchain will adjust when it relinks to introduce a modification. So now it stays accurate vs. the source code, but it is no longer constant (since it can, in fact, change when you do an edit and continue). Which means you can't use it for case labels, array sizes, or anything else that have to be compile-time constants. Like this tricky use of it in Duffs device :-)

You can either shut off /Zi mode (which eliminates the problem since line numbers *are* constant if you can't partially recompile at runtime), or you can use __COUNTER__ instead of __LINE__ to generate the unique case labels. __COUNTER__ simply increments each time it's used, without being tied to source line numbers, so edit and continue doesn't mess it up. It's MS-specific, but so is edit&continue...

Apparently, the interpreter is being reimplemented from scratch; they want to write it without continuations, and then put them in later, after 2.0.