Hacker News new | past | comments | ask | show | jobs | submit login

Well, both racket and guile dynamically grows/shrinks the stack. Chicken does not. It turns everything into tail calls and copies the stack when it's full and discards whatever is not in scope (simplified).

Gambit seems to also not grow the stack dynamically, but I could be wrong.




First, I'm talking about the stack in Scheme (the high level language), since that's what we are talking about here (you gave map as an example); whether there's a C stack used underneath somewhere only matters in this context if its size is tied to the stack size available to Scheme programs. Also, some might argue that Scheme needs to implement call/cc and hence "can't use a stack" for storing Scheme call frames as that would not be efficient, which is correct if you tie the word "stack" to implementations as a single array only. A singly linked list can also work as a stack[1]. Since Scheme gives first class access to continuations, the "call stack" is sometimes correspondingly called the "continuation stack" instead, which then makes more sense.

[1] https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Gambit definitely does grow the Scheme continuation stack; if you let it grow infinitely, it increases memory use of the whole process until it swaps or runs into a memory limit set via ulimit -v; in the latter case the Gambit runtime throws an out of memory exception in some situations, or reports an out of memory error and exits the system in others. If the procedure returns, the memory is given back first to the heap and then at some point (if not re-used) to the OS.

With regards to Chicken, as you say, it transforms the code into continuation passing style, allocates every continuation frame first on the C stack and then copies surviving frames into a second zone (it basically uses a generational garbage collector with 2 generations). Each long term continuation frame is essentially allocated on the heap (or whatever it is that the second zone is allocated from). Hence I expect that there is no limit on the size of the continuation stack in Chicken, either.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: