4 ms·

The hackyness/speed issues aside: When compiling/transpiling/whatever between languages, I have found that relying on regular procedure calls and TCO is genera

by bjoli 9y ago

The hackyness/speed issues aside: When compiling/transpiling/whatever between languages, I have found that relying on regular procedure calls and TCO is generally a lot simpler than having to force the looping facility of one language into the semantics of another language. The only one I can actually imagine porting other loops to is the common lisp loop macro, but that is probably the most flexible looping facility known to man. Edit: and oh, cool thing: racket and guile has expanding stacks and doesn't have a recursion limit other than the whole memory of the computer. This is pretty handy when implementing something like map, since you can write a non-tail-recursive procedure so that you don't have to reverse the list at the end.

pflanze 9y ago
With regards to stacks that can use all of the memory: Gambit and AFAIK Chicken behave that way, too. This is one of the reasons I chose Scheme over OCaml (and Haskell) over a decade ago when looking for a new language to move to.
- wyager 9y ago
  Haskell does not have a recursion limit. You can freely use as much memory as you want via recursion. It doesn’t even really have a stack in the traditional sense. The STG machine does use a stack for evaluation, but it’s often completely different from what you might expect if function calls in Haskell actually necessarily corresponded to C-style functions. There is a default limit to the physical stack size, but it’s something like 512MB and you can change it with a command line flag. https://wiki.haskell.org/Stack_overflow https://wiki.haskell.org/Stack_overflow
- zielmicha 9y ago
  Even Python doesn't need to have stack limit - just make sure C stack is large enough (e.g. using ulimit or pthread_attr_setstacksize) and use `sys.setrecursionlimit(1000000000)`.
  - pflanze 9y ago
    Making the C stack large enough is not solving it on 32 bit architectures with enough physical RAM that you can't/don't want to waste address space. And on 64 bit architectures address space isn't a problem, but the memory from a temporary large stack can't be re-used without swapping the old stack contents out which is slow.
  - bagels 9y ago
    Yes, you could make the stack larger, or, you could avoid needing to keep a gigantic useless stack in memory with this technique in the first place.
- bjoli 9y ago
  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.
  - pflanze 9y ago
    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) 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.
deckard1 9y ago
> racket and guile has expanding stacks and doesn't have a recursion limit other than the whole memory of the computer I'm not familiar with how these two in particular work internally, but this may actually be more a side effect related to the implementation of call/cc than recursion. A popular technique is to truncate the stack when a continuation is captured. So you obviously need a stack that can expand.
- bjoli 9y ago
  It was not by accident, but it might have something to do with the delimited continuations implemented for guile 2.2
iitalics 9y ago
To add onto the point about expanding stacks: What's especially nice about this feature is that it means that you don't need to tune your algorithms to be tail recursive when they could be expressed more clearly as non-tail recursion. Functions like map would actually be less efficient on average if it was tail recursive because you would need to re-iterate the list to reverse it.
- bjoli 9y ago
  With guile and Racket, a non-linear reverse! at the end of a map is as fast as doing a non-tail-recursive map. There are trade-offs for both. The TCO'd map is a lot faster to restore when using continuations, but is not multi-shot continuation safe.

by bjoli 9y ago

pflanze 9y ago

With regards to stacks that can use all of the memory: Gambit and AFAIK Chicken behave that way, too. This is one of the reasons I chose Scheme over OCaml (and Haskell) over a decade ago when looking for a new language to move to.

wyager 9y ago
Haskell does not have a recursion limit. You can freely use as much memory as you want via recursion. It doesn’t even really have a stack in the traditional sense. The STG machine does use a stack for evaluation, but it’s often completely different from what you might expect if function calls in Haskell actually necessarily corresponded to C-style functions. There is a default limit to the physical stack size, but it’s something like 512MB and you can change it with a command line flag. https://wiki.haskell.org/Stack_overflow https://wiki.haskell.org/Stack_overflow
zielmicha 9y ago
Even Python doesn't need to have stack limit - just make sure C stack is large enough (e.g. using ulimit or pthread_attr_setstacksize) and use `sys.setrecursionlimit(1000000000)`.
- pflanze 9y ago
  Making the C stack large enough is not solving it on 32 bit architectures with enough physical RAM that you can't/don't want to waste address space. And on 64 bit architectures address space isn't a problem, but the memory from a temporary large stack can't be re-used without swapping the old stack contents out which is slow.
- bagels 9y ago
  Yes, you could make the stack larger, or, you could avoid needing to keep a gigantic useless stack in memory with this technique in the first place.
bjoli 9y ago
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.
- pflanze 9y ago
  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) 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.

deckard1 9y ago

> racket and guile has expanding stacks and doesn't have a recursion limit other than the whole memory of the computer I'm not familiar with how these two in particular work internally, but this may actually be more a side effect related to the implementation of call/cc than recursion. A popular technique is to truncate the stack when a continuation is captured. So you obviously need a stack that can expand.

bjoli 9y ago
It was not by accident, but it might have something to do with the delimited continuations implemented for guile 2.2

iitalics 9y ago

To add onto the point about expanding stacks: What's especially nice about this feature is that it means that you don't need to tune your algorithms to be tail recursive when they could be expressed more clearly as non-tail recursion. Functions like map would actually be less efficient on average if it was tail recursive because you would need to re-iterate the list to reverse it.

bjoli 9y ago
With guile and Racket, a non-linear reverse! at the end of a map is as fast as doing a non-tail-recursive map. There are trade-offs for both. The TCO'd map is a lot faster to restore when using continuations, but is not multi-shot continuation safe.