Lisp to C compiler

Hi! It is me again!

I've found that continuations in C/C++ doesn't require tail-call optimization on the part of the compiler. You can just do setjmp and longjmp when stack gets close to full. This means you can't do stack allocation, but you should allocate everything on heap anyway.

Use LLVM IR.

>>1
tail call optimization and stack allocation don't mix so well. In general you can only always use stack allocation when the stack is actually the heap and is compacted after reaching its full size.

>>3
I hope you mena continuations and stack allocations don't mix well. You can always optimize tail recursion to a jump with no stack operations whatsoever.

Using setjmp/longjmp to implement continuations doesn't work if you need to transfer control to functions that've not already been invoked (and thus doesn't have a frame already on the stack somewhere).

>>4
neyaaa, it's actually moar difficult. It depends on the working definition of tail call optimization. This becomes less clear when exotic function call stacks are used. But consider the following le c program.


struct bar {
int x;
int y;
};

int foo(struct bar* m) {
struct bar n;
if (m->x == 0) {
return m->y;
} else if (m->y % 2 == 0) {
m->y += m->x;
m->x--;
return foo(m);
} else {
n.x = m->x - m->y - 1;
n.y = m->x + m->y + 1;
return foo(&n);
}
}


In each of these tail calls, when can n be deallocated from the stack and when can it not? In order to perform a proper tail call, no pointers to stack allocated items in the scope can escape. In this example some analysis can rule out the cases, but with more complex code it becomes harder to trace. If the object can't be deallocated from the stack in a tail call, it can't be considered tail call optimization because with enough iteration the stack will le overflow.

>>5
I don't see the problem. In that example you can trivially keep a single copy of n on the stack always and as long as you're careful about aliasing it will work just fine. It's not a problem for pointers to stack allocated data to escape here since by definition an optimized tail call doesn't modify the layout of the stack.

>>4
one uses longjmp to reset the stack pointer on SIGSEGV. Basically, you setjmp in main, start your code, catch SIGSEGV and longjmp back to main(). SIGSEGV happens only when you call function, so main() would just recall the latest function.

Look up lambda lifting and read this http://home.pipeline.com/~hbaker1/CheneyMTA.html