7 ms·

Stack safety for free?

48 points by tekkertje 5y ago

tobz1000 5y ago
This seems like a universal-ish mechanism for queueing your recursive function's calls onto a dynamically resizeable stack (placed in the process's heap). This is pretty cool, but I wouldn't say it's "for free", performance-wise, as demonstrated by the performance figures in the article. Although it certainly makes the transformation cheap, implementation-wise.
Gadiguibou 5y ago
This seems like such an obvious abstraction, that it's hard to believe noone came up with a macro to do this a long time ago. However, that seems like a sign of a good or well explained idea. While, I've never seen something similar being used before, I wouldn't call it revolutionary since it's not really making the function iterative, it's just moving the call stack to the heap. It would still be a very nice convenience for functions that are more elegantly expressed recursively.
lmm 5y ago
Yes, this is a standard technique. It's more or less recovering the trampoline monad via continuations as a universal monad. You can use the same technique to implement other effects as well, if you're working in the kind of crazy language that has continuations but no monads.
gopiandcode 5y ago
I would highly recommend that the author look into continuation-passing-style - the general construction they discover in their blog just seems to be a reinvention of the pretty old observation that we can make any program tail-call recursive if we write it in a CPS form. In fact, in languages like OCaml, it's fairly common to do this transformation to avoid stack overflow (typically paired with a Monad), especially when compiling to JS. The requirement of generators isn't actually needed - you just need first class functions - although, generators and coroutines do allow expressing the code in a slightly more concise way.
- Guvante 5y ago
  Generators and such are designed to avoid manually writing contuation passing style which is generally difficult when you need compound state. Especially since Rust makes manual contuation passing style very complex. Generally function pass around references with lifetimes bound to the execution of the function. While continuation passing style does satisfy the constraints needed the compiler can't deduce that thus requiring unsafe code. Generators being built into the compiler can perform that transformation on your behalf and provide the nicer syntax of not having to write out your state explicitly.
  - wahern 5y ago
    Not having to explicitly pass around your state everywhere when you need to resume one routine after calling another is why stacks were invented in the first place! And then when systems began adding concurrent execution of tasks they added these things called processes and threads. And then later the underlying concepts were identified as continuations, generators and coroutines (in order of language-level usefulness). 20 years ago the new, cool advice was that processes and threads were bad. Today, the new, cool advice is that even stacks are bad and it's better to use promises or explicit CPS even in languages that predominately rely on implicit function call stacks. Yet function call stack semantics work so exceedingly well that the people who dislike them rely on them in ways they can't even appreciate. Ditto for processes/threads. Fortunately there are a few languages where the designers and maintainers have the good sense to understand the original function of those abstractions, their relationship to concurrency, and to carry them forth; such as Java (Project Loom) and OCaml (new async runtime--see "One-shot Algebraic Effects as [Stackful, Asymmetric] Coroutines"). Of course, underneath they use simpler mechanisms (e.g. CPS) to present those abstractions, but the majority of the time that's exactly what you want--the OS and compiler to deal with that crap (mostly low-level, irreducible instrumentation for invoking functions) so you don't have to.
    - Guvante 5y ago
      I feel you aren't being fair here. Stacks are an implementation of being able to resume execution after a unit of work is done. That is what is wanted. Rust has generators and async await which covers the most popular form of them. General generators aren't in only due to Rust having a hardcore backwards compatibility guarantee that other than not having an ABI is one of the strongest out there.
amalcon 5y ago
I'm sort of hesitant to be "that guy", but I've seen this kind of thing be a bit of a trap before. The technique of simulating a stack on the heap is useful in some situations, but it's very misleading to call it a form of safety. It's important to be clear about exactly what this buys you, and what it doesn't buy you. The benefit in a case like this is that you use memory a little more efficiently (since your stack frames contain exactly what you put in them) and you have a larger maximum size (since the heap tends to have more addressable space than the stack). This buys you more recursive depth (and therefore a larger input) before crashing. You can still run out of memory and crash. Arguably on systems like 64-bit Linux this is more dangerous, since the OOM killer is less predictable than stack overflow handling. Of course it is often worth it to be able to handle the input you happen to have on hand, but that's a functional improvement, not a safety improvement. It's no substitute for an algorithm that just uses less memory.
servytor 5y ago
Could this trick be used by ABCL (a Common Lisp implementation on the JVM) to allow for tail-call optimization?
- runevault 5y ago
  Should be able to. Clojure used trampolines for tail recursion at least.
  - servytor 5y ago
    But Clojure uses 'recur' because you cannot modify the stack in the JVM (at least to my knowledge that is the issue with the JVM and TCO).
    - runevault 5y ago
      Right and it uses a trampoline under the hood.
      - pflanze 5y ago
        Since "recur" only allows to recurse to the closest recursion point (a loop or the enclosing function definition), what if it just used JVM's "goto"? Or, if the JVM didn't have a goto, but any kind of iteration construct, used that instead? Then it doesn't have to use a custom stack or allocate anything on the heap.
auggierose 5y ago
I would like to have the option to just mark some functions to run on the heap instead of the stack. Without that option, recursive functions are really useless and cannot be used in the real world.
- nathcd 5y ago
  I mean, if your compiler does TCO and you can make your function tail recursive, it's usable in the real world, right? That's not all recursive functions, but "useless" seems a little extreme. I write plenty of recursive functions in my (real world) job. Sometimes they're not even tail recursive (gasp) when I'm working with small data.
  - auggierose 5y ago
    If I can make my functions easily tail recursive, then I can also just write an iteration.
    - nybble41 5y ago
      Iteration is just a special case of tail recursion.
      - auggierose 5y ago
        And tail recursion a special case of iteration.
        nybble41 5y ago
        No, tail recursion is more general than iteration—it can be used to implement arbitrary control structures, without needing extra constructs such as conditions. (E.g., this is how Smalltalk implements if/then/else with only blocks and methods.)
        auggierose 5y ago
rincewind 5y ago
I want this guy to duke it out with the developers of chicken scheme
The_rationalist 5y ago
Kotlin were the first to introduce the idea in my knowledge https://elizarov.medium.com/deep-recursion-with-coroutines-7c53e15993e3 https://elizarov.medium.com/deep-recursion-with-coroutines-7...
wahern 5y ago
> I demonstrate how to (ab)use generators/coroutines to transform any recursive function into an iterative function with nearly zero code changes. That's not abuse. Reversing consumer/producer calling protocols (i.e. reversing caller/callee relationship) is exactly the fundamental purpose of generators and coroutines. It's a useful insight, nonetheless, for those exploring the fundamental problem and solution space regarding concurrency and, more generally, the reification of execution flow.

48 points by tekkertje 5y ago

This seems like a universal-ish mechanism for queueing your recursive function's calls onto a dynamically resizeable stack (placed in the process's heap). This is pretty cool, but I wouldn't say it's "for free", performance-wise, as demonstrated by the performance figures in the article. Although it certainly makes the transformation cheap, implementation-wise.

Gadiguibou 5y ago

This seems like such an obvious abstraction, that it's hard to believe noone came up with a macro to do this a long time ago. However, that seems like a sign of a good or well explained idea. While, I've never seen something similar being used before, I wouldn't call it revolutionary since it's not really making the function iterative, it's just moving the call stack to the heap. It would still be a very nice convenience for functions that are more elegantly expressed recursively.

lmm 5y ago

Yes, this is a standard technique. It's more or less recovering the trampoline monad via continuations as a universal monad. You can use the same technique to implement other effects as well, if you're working in the kind of crazy language that has continuations but no monads.

gopiandcode 5y ago

I would highly recommend that the author look into continuation-passing-style - the general construction they discover in their blog just seems to be a reinvention of the pretty old observation that we can make any program tail-call recursive if we write it in a CPS form. In fact, in languages like OCaml, it's fairly common to do this transformation to avoid stack overflow (typically paired with a Monad), especially when compiling to JS. The requirement of generators isn't actually needed - you just need first class functions - although, generators and coroutines do allow expressing the code in a slightly more concise way.

Guvante 5y ago
Generators and such are designed to avoid manually writing contuation passing style which is generally difficult when you need compound state. Especially since Rust makes manual contuation passing style very complex. Generally function pass around references with lifetimes bound to the execution of the function. While continuation passing style does satisfy the constraints needed the compiler can't deduce that thus requiring unsafe code. Generators being built into the compiler can perform that transformation on your behalf and provide the nicer syntax of not having to write out your state explicitly.
- wahern 5y ago
  Not having to explicitly pass around your state everywhere when you need to resume one routine after calling another is why stacks were invented in the first place! And then when systems began adding concurrent execution of tasks they added these things called processes and threads. And then later the underlying concepts were identified as continuations, generators and coroutines (in order of language-level usefulness). 20 years ago the new, cool advice was that processes and threads were bad. Today, the new, cool advice is that even stacks are bad and it's better to use promises or explicit CPS even in languages that predominately rely on implicit function call stacks. Yet function call stack semantics work so exceedingly well that the people who dislike them rely on them in ways they can't even appreciate. Ditto for processes/threads. Fortunately there are a few languages where the designers and maintainers have the good sense to understand the original function of those abstractions, their relationship to concurrency, and to carry them forth; such as Java (Project Loom) and OCaml (new async runtime--see "One-shot Algebraic Effects as [Stackful, Asymmetric] Coroutines"). Of course, underneath they use simpler mechanisms (e.g. CPS) to present those abstractions, but the majority of the time that's exactly what you want--the OS and compiler to deal with that crap (mostly low-level, irreducible instrumentation for invoking functions) so you don't have to.
  - Guvante 5y ago
    I feel you aren't being fair here. Stacks are an implementation of being able to resume execution after a unit of work is done. That is what is wanted. Rust has generators and async await which covers the most popular form of them. General generators aren't in only due to Rust having a hardcore backwards compatibility guarantee that other than not having an ABI is one of the strongest out there.

amalcon 5y ago

I'm sort of hesitant to be "that guy", but I've seen this kind of thing be a bit of a trap before. The technique of simulating a stack on the heap is useful in some situations, but it's very misleading to call it a form of safety. It's important to be clear about exactly what this buys you, and what it doesn't buy you. The benefit in a case like this is that you use memory a little more efficiently (since your stack frames contain exactly what you put in them) and you have a larger maximum size (since the heap tends to have more addressable space than the stack). This buys you more recursive depth (and therefore a larger input) before crashing. You can still run out of memory and crash. Arguably on systems like 64-bit Linux this is more dangerous, since the OOM killer is less predictable than stack overflow handling. Of course it is often worth it to be able to handle the input you happen to have on hand, but that's a functional improvement, not a safety improvement. It's no substitute for an algorithm that just uses less memory.

servytor 5y ago

Could this trick be used by ABCL (a Common Lisp implementation on the JVM) to allow for tail-call optimization?

runevault 5y ago
Should be able to. Clojure used trampolines for tail recursion at least.
- servytor 5y ago
  But Clojure uses 'recur' because you cannot modify the stack in the JVM (at least to my knowledge that is the issue with the JVM and TCO).
  - runevault 5y ago
    Right and it uses a trampoline under the hood.
    - pflanze 5y ago
      Since "recur" only allows to recurse to the closest recursion point (a loop or the enclosing function definition), what if it just used JVM's "goto"? Or, if the JVM didn't have a goto, but any kind of iteration construct, used that instead? Then it doesn't have to use a custom stack or allocate anything on the heap.

auggierose 5y ago

I would like to have the option to just mark some functions to run on the heap instead of the stack. Without that option, recursive functions are really useless and cannot be used in the real world.

nathcd 5y ago
I mean, if your compiler does TCO and you can make your function tail recursive, it's usable in the real world, right? That's not all recursive functions, but "useless" seems a little extreme. I write plenty of recursive functions in my (real world) job. Sometimes they're not even tail recursive (gasp) when I'm working with small data.
- auggierose 5y ago
  If I can make my functions easily tail recursive, then I can also just write an iteration.
  - nybble41 5y ago
    Iteration is just a special case of tail recursion.
    - auggierose 5y ago
      And tail recursion a special case of iteration.
      - nybble41 5y ago
        No, tail recursion is more general than iteration—it can be used to implement arbitrary control structures, without needing extra constructs such as conditions. (E.g., this is how Smalltalk implements if/then/else with only blocks and methods.)
        auggierose 5y ago

rincewind 5y ago

I want this guy to duke it out with the developers of chicken scheme

The_rationalist 5y ago

Kotlin were the first to introduce the idea in my knowledge https://elizarov.medium.com/deep-recursion-with-coroutines-7c53e15993e3 https://elizarov.medium.com/deep-recursion-with-coroutines-7...

wahern 5y ago

> I demonstrate how to (ab)use generators/coroutines to transform any recursive function into an iterative function with nearly zero code changes. That's not abuse. Reversing consumer/producer calling protocols (i.e. reversing caller/callee relationship) is exactly the fundamental purpose of generators and coroutines. It's a useful insight, nonetheless, for those exploring the fundamental problem and solution space regarding concurrency and, more generally, the reification of execution flow.