[Stackless] For interested - an interlacing compiler for C that allows continuations

Paul Sheer psheer at icon.co.za
Sat Sep 7 20:41:04 CEST 2002


> 
> I have no idea whether this would suffice as a thesis.

sorry, i included the part about PhDs by mistake - of
course this list isn't the place for such a question.

> [...] C-- [...]

ok, interesting. actually never looked at C--

> 
> How far do you think: Would it be possible to pour
> Python through the compiler, with all of its
> recursiveness and all the method hooks in type
> objects, and the compiler would produce efficient
> code?
> I think the answer is yes, silly question.
> Just remove the stack.
> 
> I've been thinking of this for quite some time.
> Changing the C code to become non-recursive was
> no real option. But letting a compiler do that
> for us sounds phantastic!
> 

when I came up with the idea i first tried to create
a parser in python. after rewriting it twice and pulling
my hair out. i went for flex/bison, with a standard
off-the-shelf bison grammer for ansi C.

i mention this because its a more difficult problem
than you first suspect. consider an expression which
contains a function call to a function which contains
a continuation.

a parser would have to understand the FULL C grammer to
work AT ALL.

when you come to passing function pointers around i
think the whole thing breaks down. its probably possible
but i havn't thought of how you would do it.

also, you are looking at a run-time speed deficit of
about half (thumb suck).

personally, my idea was to use the thing as-is rather
than try compile existing code. For example, i intend
to add a couple of new C keywords.

I think you need to see some example input and output
to get the idea here. looking carefully through the
output is quite instructive.


---------------

input:


int func_without_continuation2 (int x, int y) {
    printf ("%d, %d\n", x, y);
    return x + y; }
int func_without_continuation (int x, int y) {
    printf ("%d, %d\n", x, y);
    func_without_continuation2 (x, y);
    return x + y; }
int func_with_continuation (int x, int y) {
    printf ("%d, %d\n", x, y);
    yield ();
    return x + y; }
int func (void) {
    int x = 0;
    while (x < 99) {
	if (x == 4)
	    break;
	if (x == 3)
	    continue;
	yield ();
        x = func_with_continuation (x * 2, x + 16);
	printf ("something");  } }
int test (void) {
    int x = 2;
    func (); }


and output is below. you can see that there are a LOT of little
functions. and even hand optimizing does not help all that much.

best

-paul


----------------output------------

int func_without_continuation2 (struct NAMESPACE *_n, int x, int y)
{
    printf ("%d, %d\n", x, y);
    return x + y;
}


int func_without_continuation (struct NAMESPACE *_n, int x, int y)
{
    printf ("%d, %d\n", x, y);
    func_without_continuation2 (x, y);
    return x + y;
}


FUNCTION *func_with_continuation_CODEPOINT_2 (NAMESPACE_func_with_continuation * _o, **_new_o)
{
    yield (func_with_continuation_CODEPOINT_3);
    return NULL;
}

FUNCTION *func_with_continuation_CODEPOINT_3 (NAMESPACE_func_with_continuation * _o, **_new_o)
{
/* yield() */ ;
    return func_with_continuation_CODEPOINT_4;
}

FUNCTION *func_with_continuation_CODEPOINT_5 (NAMESPACE_func_with_continuation * _o, **_new_o)
{
    printf ("%d, %d\n", (_o->x), (_o->y));
    return func_with_continuation_CODEPOINT_2;
}

FUNCTION *func_with_continuation_CODEPOINT_4 (NAMESPACE_func_with_continuation * _o, **_new_o)
{
    _o->FUNCTION_RESULT = (_o->x) + (_o->y);
    return func_with_continuation_RETURN;
    return func_with_continuation_CODEPOINT_6;
}

FUNCTION *func_with_continuation_CODEPOINT_7 (NAMESPACE_func_with_continuation * _o, **_new_o)
{
    return func_with_continuation_CODEPOINT_5;
}

FUNCTION *func_with_continuation_CODEPOINT_1 (NAMESPACE_func_with_continuation * _o, **_new_o)
{
    return func_with_continuation_CODEPOINT_7;
}

FUNCTION *func_with_continuation_CODEPOINT_6 (NAMESPACE_func_with_continuation * _o, **_new_o)
{
    return func_with_continuation_RETURN;
}

void func_with_continuation_INIT (struct NAMESPACE_func_with_continuation *_o, int x, int y)
{
    _o->x = x;
    _o->y = y;
}

FUNCTION *func_with_continuation_RETURN (struct NAMESPACE_func_with_continuation *_o, void **_new_o)
{
    *_new_o = _o->CALLER_NAMESPACE;
    return _o->CALLER;
}

struct NAMESPACE_func_with_continuation {
    struct NAMESPACE *NAMESPACE;
    function *CALLER;
    int x;
    int y;
    int FUNCTION_RESULT;
};



FUNCTION *func_CODEPOINT_4 (NAMESPACE_func * _o, **_new_o)
{
    yield (func_CODEPOINT_5);
    return NULL;
}

FUNCTION *func_CODEPOINT_5 (NAMESPACE_func * _o, **_new_o)
{
/* yield() */ ;
    return func_CODEPOINT_6;
}

FUNCTION *func_CODEPOINT_7 (NAMESPACE_func * _o, **_new_o)
{
    struct NAMESPACE_func_with_continuation *__p;
    __p = malloc (sizeof (struct NAMESPACE_func_with_continuation));
    _o->FUNCTION_NAMESPACE = (void *) __p;
    func_with_continuation_INIT (__p, (_o->x) * 2, (_o->x) + 16);
    __p->CALLER = func_CODEPOINT_8;
    __p->CALLER_NAMESPACE = _o;
    __p->NAMESPACE = _o->NAMESPACE;
    *_new_o = (void *) __p;
    return func_with_continuation_CODEPOINT_1;
}

FUNCTION *func_CODEPOINT_8 (NAMESPACE_func * _o, **_new_o)
{
    _o->__temp1 = ((struct NAMESPACE_func_with_continuation *) _o->FUNCTION_NAMESPACE)->FUNCTION_RESULT;
    free (_o->FUNCTION_NAMESPACE);
    return func_CODEPOINT_9;
}

FUNCTION *func_CODEPOINT_9 (NAMESPACE_func * _o, **_new_o)
{
    (_o->x) = (_o->__temp1);
    return func_CODEPOINT_10;
}

FUNCTION *func_CODEPOINT_11 (NAMESPACE_func * _o, **_new_o)
{
    if ((_o->x) == 4)
	return func_CODEPOINT_2;	/* break; */
    if ((_o->x) == 3)
	return func_CODEPOINT_3;	/* continue; */
    return func_CODEPOINT_4;
}

FUNCTION *func_CODEPOINT_10 (NAMESPACE_func * _o, **_new_o)
{
    printf ("something");
    return func_CODEPOINT_12;
}

FUNCTION *func_CODEPOINT_6 (NAMESPACE_func * _o, **_new_o)
{
    return func_CODEPOINT_7;
}

FUNCTION *func_CODEPOINT_13 (NAMESPACE_func * _o, **_new_o)
{
    return func_CODEPOINT_11;
}

FUNCTION *func_CODEPOINT_3 (NAMESPACE_func * _o, **_new_o)
{
    return func_CODEPOINT_12;
}

FUNCTION *func_CODEPOINT_12 (NAMESPACE_func * _o, **_new_o)
{
    if ((_o->x) < 99)
	return func_CODEPOINT_13;
    else

	return func_CODEPOINT_2;
}

FUNCTION *func_CODEPOINT_14 (NAMESPACE_func * _o, **_new_o)
{
    int x = 0;
    _o->x = x;
    return func_CODEPOINT_12;
}

FUNCTION *func_CODEPOINT_1 (NAMESPACE_func * _o, **_new_o)
{
    return func_CODEPOINT_14;
}

FUNCTION *func_CODEPOINT_2 (NAMESPACE_func * _o, **_new_o)
{
    return func_RETURN;
}

void func_INIT (struct NAMESPACE_func *_o)
{
}

FUNCTION *func_RETURN (struct NAMESPACE_func *_o, void **_new_o)
{
    *_new_o = _o->CALLER_NAMESPACE;
    return _o->CALLER;
}

struct NAMESPACE_func {
    struct NAMESPACE *NAMESPACE;
    function *CALLER;
    int __temp1;
    int x;
    int FUNCTION_RESULT;
};



FUNCTION *test_CODEPOINT_2 (NAMESPACE_test * _o, **_new_o)
{
    struct NAMESPACE_func *__p;
    __p = malloc (sizeof (struct NAMESPACE_func));
    _o->FUNCTION_NAMESPACE = (void *) __p;
    func_INIT (__p);
    __p->CALLER = test_CODEPOINT_3;
    __p->CALLER_NAMESPACE = _o;
    __p->NAMESPACE = _o->NAMESPACE;
    *_new_o = (void *) __p;
    return func_CODEPOINT_1;
}

FUNCTION *test_CODEPOINT_3 (NAMESPACE_test * _o, **_new_o)
{
    _o->__temp1 = ((struct NAMESPACE_func *) _o->FUNCTION_NAMESPACE)->FUNCTION_RESULT;
    free (_o->FUNCTION_NAMESPACE);
    return test_CODEPOINT_4;
}

FUNCTION *test_CODEPOINT_4 (NAMESPACE_test * _o, **_new_o)
{
/* (_o->__temp1) [result of function call ignored] */ ;
    return test_CODEPOINT_5;
}

FUNCTION *test_CODEPOINT_6 (NAMESPACE_test * _o, **_new_o)
{
    int x = 2;
    _o->x = x;
    return test_CODEPOINT_2;
}

FUNCTION *test_CODEPOINT_1 (NAMESPACE_test * _o, **_new_o)
{
    return test_CODEPOINT_6;
}

FUNCTION *test_CODEPOINT_5 (NAMESPACE_test * _o, **_new_o)
{
    return test_RETURN;
}

void test_INIT (struct NAMESPACE_test *_o)
{
}

FUNCTION *test_RETURN (struct NAMESPACE_test *_o, void **_new_o)
{
    *_new_o = _o->CALLER_NAMESPACE;
    return _o->CALLER;
}

struct NAMESPACE_test {
    struct NAMESPACE *NAMESPACE;
    function *CALLER;
    int __temp1;
    int x;
    int FUNCTION_RESULT;
};




Paul Sheer Consulting IT Services . . Tel . . . +27 (0)21 6869634
Email . . . psheer at icon.co.za . . . . . . Pager . . . 088 0057245
Linux development, cryptography, recruitment,  support,  training
http://www.icon.co.za/~psheer . . . . http://rute.sourceforge.net
L I N U X . . . . . . . . . . . .  The Choice of a GNU Generation



_______________________________________________
Stackless mailing list
Stackless at www.tismer.com
http://www.tismer.com/mailman/listinfo/stackless



More information about the Stackless mailing list