Explicit TCE

[Tyler Jameson Little]

On Friday, 12 October 2012 at 18:02:57 UTC, bearophile wrote:
> Tyler Jameson Little:
>
>> D could use something like Newsqueak's become keyword. If 
>> you're not familial with Newsqueak, become is just like a 
>> return, except it replaces the stack frame with the function 
>> that it calls.
>
> Are you talking about CPS?
> http://en.wikipedia.org/wiki/Continuation_passing_style

I don't think it would necessitate CPS, but that is a nice side 
effect. I'm thinking more of a recursive function call that may 
or may not return. For example, a process that shovels data 
between two network connections. If the data never stops, the 
function will never return. If there's some kind of a problem, 
then it could return with that error, and be restarted when that 
problem is fixed. All of this could happen with a series of 
function calls that use the same stack.

void handleIncommingData() {
    if (error) {
        // returns directly to manageLongRunningProcess
        return;
    }

    // do something useful

    become longRunningProcess();
}

void longRunningProcess() {
     become handleIncommingData();
}

void manageLongRunningProcess() {
     longRunningProcess();
     // there was a problem, so fix it
     ....

     // try again
     manageLongRunningProcess();
}

Exceptions are not needed, so these can be nothrow functions, and 
this implementation is simpler than some complex while loop, 
while having the same memory footprint.

CPS would make things like imitating javascript's 
setTimeout/setInterval possible. I don't think this is a major 
benefit for D because the parallelism/concurrency support is 
already pretty awesome.

The main benefit is for implementing things like lexical 
analyzers (or tokenizers, whatever), which don't really depend on 
previous states and can emit tokens. This allows for efficient 
representation of recursive problems, that call functions 
circularly (a -> b -> c -> a -> b ...), like a state machine.

I think it just allows an extra level of expressiveness without a 
backwards incompatible change to the language. True, you can 
express this same idea with trampolining, but that isn't as fun:

http://stackoverflow.com/a/489860/538551
http://en.wikipedia.org/wiki/Tail-recursive_function#Through_trampolining

There are still some problems that I think a LISP language would 
make more sense for, and for those problems, it would be great to 
express them in D with my other code.

>> DMD should optimize this already, but explicitly stating 
>> become is a key to the compiler that the user wants this call 
>> to be eliminated.  Then, more interesting things can be 
>> implemented more simply, like a state machine:
>>
>>    void stateA() {
>>        become stateB();
>>    }
>>
>>    void stateB() {
>>        become stateC();
>>    }
>>
>>    void stateC() {
>>        return;
>>    }
>>
>>    void main() {
>>        become stateA();
>>    }
>
> Seems nice.

I'm glad you think so =D

>> I'm not sure how D handles stack sizes, so this may be an 
>> issue as well if stack sizes are determined at runtime.
>
> D doesn't currently support C99 VLAs, but it supports alloca(), 
> so stack frames are sized dynamically. But maybe this is not a 
> big problem for CPS.

Well, dynamic stack frames aren't strictly a bad thing for CPS, 
it just removes the memory use guarantee. There's already a huge 
memory gain from using TCE, I just don't know debugging would be 
done if a function keeps adding to and passing a dynamic array.