Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Lisp to C compiler

Name: Anonymous 2014-04-19 17:42

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.

Name: Anonymous 2014-04-19 18:01

Use LLVM IR.

Name: Anonymous 2014-04-19 20:57

>>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.

Name: Anonymous 2014-04-21 2:37

>>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).

Name: Anonymous 2014-04-21 2:50

>>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.

Name: Anonymous 2014-04-21 5:52

>>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.

Name: Anonymous 2014-04-21 8:38

>>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.

Name: Anonymous 2014-04-21 13:42

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

Name: Anonymous 2014-04-21 14:33

>>8

you still require closures to capture environment (i.e. downward funarg problem).

Name: Anonymous 2014-04-21 16:33

>>1
Do it like chicken scheme.

It relies on the C compiler tail-calling functions but it's pretty neat regardless.

Basically, they compile scheme to straightforward CPS'd C code, so no function ever returns, allocate all objects on the stack, and when the stack is blown, copy all live data to the heap.

Name: Anonymous 2014-04-21 16:36

>>10
and when the stack is blown
how can you detect that? and how safe is it? how about portability?

Name: Anonymous 2014-04-21 16:46

>>11

Apparently it works pretty well. Dunno about portability.

It's open source though so you can check it out if you want
http://code.call-cc.org/git/chicken-core.git/

Name: Anonymous 2014-04-21 16:48

>>11
>>12

Actually, it doesn't wait til the stack is blown, they just check if they've hit a limit every so often and GC if necessary.

This pdf covers it pretty well
http://www.call-with-current-continuation.org/scheme-implementation-techniques.pdf

Name: Quotebot 2014-04-21 16:51

Please optimize your quotes, >>13-san.

Name: Anonymous 2014-04-21 19:01

>>14

You mean like this?
>>1,2,3,4,5,6,7,8

Name: Anonymous 2014-04-21 19:23

>>15
No, like this
>>1-8

Name: Anonymous 2014-04-22 1:46

>>10
It relies on the C compiler tail-calling functions
you can't rely on that.

Name: Anonymous 2014-04-22 1:57

>>17
On any modern compiler for a mainstream architecture you pretty much can. If you cared so much about universal portability you wouldn't use Lisp in the first place, right...?

Name: Anonymous 2014-04-22 2:19

>>13

JS has become a processor architecture
lol

Name: Anonymous 2014-04-22 4:57

>>17
With GCC you can.

Name: Anonymous 2014-04-22 7:20

>>7
It becomes a problem when an indefinite amount of objects must be allocated on the stack. Then it can't be considered tail call elimination as indefinite iteration will eventually exhaust the resources of the environment when not every object on the stack is necessarily referenced. In this example every stack allocated object is referenced, but there could be code that doesn't maintain references to every stack allocated object, and trying to optimize it would end up as some undecidable problem.


#include <stdio.h>

struct icons {
int car;
struct icons* cdr;
};

void iota_(int i, int j, struct icons* acc,
void (*ret)(void*, struct icons*), void* ro);

void iota(int i, int j,
void (*ret)(void*, struct icons*), void* ro) {
iota_(i, j, NULL, ret, ro);
}

void iota_(int i, int j, struct icons* acc,
void (*ret)(void*, struct icons*), void* ro) {
if(i > j) {
ret(ro, acc);
} else {
struct icons lis;
lis.car = j;
lis.cdr = acc;
iota_(i, j-1, &lis, ret, ro);
}
}

void sum_(struct icons* lis, int acc,
void (*ret)(void*, int), void* ro);

void sum(struct icons* lis,
void (*ret)(void*, int), void* ro) {
sum_(lis, 0, ret, ro);
}

void sum_(struct icons* lis, int acc,
void (*ret)(void*, int), void* ro) {
if(lis)
sum_(lis->cdr, acc + lis->car, ret, ro);
else
ret(ro, acc);
}

void r1(void* ro, int s) {
printf("%d\n", s);
}

void r2(void* ro, struct icons* lis) {
void (*ret)(void* ro, int s) = ro;
sum(lis, ret, NULL);
}

int main() {
iota(1, 10, r2, r1);
return 0;
}

Name: Anonymous 2014-04-23 10:43

>>20

With GCC you can.
You have Stallman's word on it.

Name: Anonymous 2014-04-23 11:13

>>13

Love the BIBOP allocation. It eliminates most overhead. I.e. create N pools for arrays of size from 1 to N, where N is sizeof(CPU_chacheline). Same for closures - put the code-pointer of each closure at the start each caheline sized block and getting it would be a matter of masking higher bits. Also, it would be a cool idea to reify closures into arrays.

Name: Anonymous 2014-04-23 17:32

>>9,10-
>>8 is exactly how Chicken does it.

Name: Anonymous 2014-04-24 4:10

>>10

when the stack is blown, copy all live data to the heap.
How does runtime know the C/C++ stack frame format? Then again, some arguments are passed in registers (fastcall convention) and function can be inlined, so a simple longjmp would lost it. I know GDB parses it somehow to get stack trace, but only if debugging info is present.

Name: Anonymous 2014-04-25 2:04

>>25

The runtime doesn't need to know the stack format. The idea is fully documented here

http://home.pipeline.com/~hbaker1/CheneyMTA.html

A key point is that since only live objects are traced--i.e., garbage (including the C frames, which are all dead) is not traced--the GC does not have to know the format of a stack frame and can be written in C itself. A Cheney-style scanner must know the format of all tospace objects, but we copy only objects--never C frames. When the GC is done, it creates a new frame to execute its continuation. The GC is called explicitly from the C code after checking whether the stack pointer has reached its preset limit. Although stack-pointer checking in this way may require a few more instructions than if it were done in assembly language, it is still faster than a trampoline call would be.

Name: Anonymous 2014-04-25 5:14

lisp is shit

Name: Anonymous 2014-04-25 5:50

if it ain't lisp, it's crap

Name: Anonymous 2014-04-25 11:58

If both setjmp and tail-calls are unavailable (Java and C#), then one can throw an Exception instead of longjmp and try/catch for setjmp.

Name: Anonymous 2014-04-25 12:01

>>29

Implementation for JavaScript: http://jacob.jkrall.net/js-tco

Name: Anonymous 2014-04-25 12:34

>>29
Try catch blocks do not allow for tail call optimization. Maybe what you are referring to is an elaborate trampoline.

Name: Anonymous 2014-04-25 12:37

>>30
Back to Hacker Reddits, please.

Name: Anonymous 2014-04-25 13:32

>>30

poh my god his websight looks like mac operating systen nien lol that's so retro and hipster XD

Name: Anonymous 2014-04-25 15:35

I feel like making a scheme to x86 compiler, what do you think? Should I do it? I don't know x86...

Name: Anonymous 2014-04-25 17:52

>>34

you will get a lot of experience in process.

Name: Anonymous 2014-04-25 17:55

>>35
I'm having trouble deciding if I will do it or not, it's sort of pointless but I'd feel good if I managed.. but I'd have to work so hard
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode + RSS -