4 ms·

Couldn't you apply standard tail call optimization and turn it into a trampoline?

ainar-g 8y ago
That is assuming that your compiler knows about such optimisations and can apply them in non-recursive situations. As far as I know, Go doesn't apply tail-call optimisation. Haskell probably does. Not sure about Rust. Either way, depending on the compiler making one particular optimisation just so that your code works seems rather fragile to me.
- steveklabnik 8y ago
  Rust does not currently guarantee TCO, though llvm may choose to do it if it wishes.
- eslaught 8y ago
  There are languages where TCO is defined as part of the language spec, specifically to give programmers permission to write this sort of code. Some Lisps (Scheme, I think) and Lua work this way. TCO is a relatively well-understood optimization that isn't prone to being brittle the way e.g. auto-parallelizers or auto-vectorizers can be. So it's less fragile than you'd think.
  - ainar-g 8y ago
    Didn't know about Lua[1], thanks! Although I think I would prefer an explicit syntax, like Tcl's “tailcall”[2], Perl's “goto &sub”[3], or “become”[4], with the compiler checking that this is actually a tail-call. [1]: https://www.lua.org/pil/6.3.html https://www.lua.org/pil/6.3.html [2]: https://wiki.tcl-lang.org/page/tailcall https://wiki.tcl-lang.org/page/tailcall [3]: https://perldoc.perl.org/functions/goto.html https://perldoc.perl.org/functions/goto.html [4]: Which was used in a C-family language I can't remember.
    - steveklabnik 8y ago
      ("become" is reserved in Rust for this exact possible future, maybe that's what you're thinking of.)
  - eridius 8y ago
    TCO is a lot easier to do in a garbage-collected language. In particular, with Rust, having any live stack value that conforms to Drop will break the ability to do tail-calls.
    - 0815test 8y ago
      You could have a trait similar to Copy that forces Drop to be a no-op, and require live values that don't conform to it to be moved into any `become`.
      - eridius 8y ago
        Or just skip the trait and require there to be nothing live on the stack that conforms to Drop after a `become`. In fact, the main reason to have a keyword like `become` is to signal to the compiler to do this kind of analysis, because it's so easy to accidentally break the ability to do TCO when you can't lean on a GC to clean things up later.

That is assuming that your compiler knows about such optimisations and can apply them in non-recursive situations. As far as I know, Go doesn't apply tail-call optimisation. Haskell probably does. Not sure about Rust. Either way, depending on the compiler making one particular optimisation just so that your code works seems rather fragile to me.

steveklabnik 8y ago
Rust does not currently guarantee TCO, though llvm may choose to do it if it wishes.
eslaught 8y ago
There are languages where TCO is defined as part of the language spec, specifically to give programmers permission to write this sort of code. Some Lisps (Scheme, I think) and Lua work this way. TCO is a relatively well-understood optimization that isn't prone to being brittle the way e.g. auto-parallelizers or auto-vectorizers can be. So it's less fragile than you'd think.
- ainar-g 8y ago
  Didn't know about Lua[1], thanks! Although I think I would prefer an explicit syntax, like Tcl's “tailcall”[2], Perl's “goto &sub”[3], or “become”[4], with the compiler checking that this is actually a tail-call. [1]: https://www.lua.org/pil/6.3.html https://www.lua.org/pil/6.3.html [2]: https://wiki.tcl-lang.org/page/tailcall https://wiki.tcl-lang.org/page/tailcall [3]: https://perldoc.perl.org/functions/goto.html https://perldoc.perl.org/functions/goto.html [4]: Which was used in a C-family language I can't remember.
  - steveklabnik 8y ago
    ("become" is reserved in Rust for this exact possible future, maybe that's what you're thinking of.)
- eridius 8y ago
  TCO is a lot easier to do in a garbage-collected language. In particular, with Rust, having any live stack value that conforms to Drop will break the ability to do tail-calls.
  - 0815test 8y ago
    You could have a trait similar to Copy that forces Drop to be a no-op, and require live values that don't conform to it to be moved into any `become`.
    - eridius 8y ago
      Or just skip the trait and require there to be nothing live on the stack that conforms to Drop after a `become`. In fact, the main reason to have a keyword like `become` is to signal to the compiler to do this kind of analysis, because it's so easy to accidentally break the ability to do TCO when you can't lean on a GC to clean things up later.