4 ms·
One question I almost never see addressed with monads is the question of the stack. The stack is not endless, and may actually be quite small on some devices. H
by ainar-g 8y ago
One question I almost never see addressed with monads is the question of the
stack. The stack is not endless, and may actually be quite small on some
devices. How is that fact reconciled with the fact that do-notation is
essentially
doStuff >>= (\a ->
doMoreStuff >>= (\b ->
doEvenMoreStuff >>= (\c ->
-- Ad nauseam.
)
)
)
Depending on the data being transferred, that looks like a lot of stack to me.
- _hardwaregeek 8y agoCouldn't you apply standard tail call optimization and turn it into a trampoline?
- ainar-g 8y agoThat 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 agoRust does not currently guarantee TCO, though llvm may choose to do it if it wishes.
- eslaught 8y agoThere 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 agoDidn'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 agoTCO 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 agoYou 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 agoOr 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.
- clhodapp 8y agoYour concern isn't completely unwarranted but in practice things generally turn out fine. Each time you hit a >>=, you are conceptually yielding control to the monadic datatype. You pass it a function, which captures some closure, which your compiler presumably optimizes to save off only the data that you may need if your function gets invoked (though over-capturing definitely can happen). Really it's a reference to the closure and maybe the function that end up sitting on the stack. The monadic datatype itself is responsible for making sure you don't create too many frames. There are different approaches they can take to accomplish this, including everything from trampolining to iterating with tail calls to imperative loops. It does occasionally happen that some datatype simply shirks its responsibility to be stack-safe. Anyway, overall, there are solutions to avoid blowing up the stack, and they generally get implemented, but occasionally it does become an issue.