[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