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

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-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
Newer Posts
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 -