I have recently learned how Elm uses tail call elimination to keep the stack size low in a recursive function. However, it has made me curious on what’s considered a recursive function, and how the Elm compiler deals with different scenarios.
How many levels deep does it go?
For example, suppose I run the following function:
f >> g
According to the definition of composeR, this should only go 2 levels deep: the composeR runs f x and then pipes the output to g. However, what happens in the following scenario?
f >> g >> h
I can imagine that the compiler makes an optimization here to run the three items consecutively, but I’m not entirely convinced that it stays that way if we obscure the operation with brackets. For example, I could see how the following example would already need to go quite deep to get the result needed.
f1 >> (f2 >> (f3 >> (f4 >> (f5 >> f6))))
Safe recursion - but is it, really?
I am implementing micahhahn/elm-safe-recursion in my project to ensure that the Elm compiler does in fact execute tail call elimination. However, the library ensures tail call elimination by using a recurseThen function where you pass in two variables:
The new value to recurse on, if any.
A function on how to generate an answer, given the recursed output.
While looking through the library’s source code, it seems that the final answer is generated by piping (>>) all the answers together. However, if that doesn’t get tail-call eliminated for some reason, we would in theory still be at the same issue, requiring a recursion of similar depth to get the answer after all.
Why I’m asking this
I would like to learn about recursion depth optimizations, but I am mostly interested in knowing for sure whether the previously mentioned library is safe to use, or whether I’m better off writing my own recursion functions where I pass an actual value into the recursion rather than a function to update the recursion.
it has made me curious on what’s considered a recursive function, and how the Elm compiler deals with different scenarios.
For the performance it provides to the resulting Elm code, the Elm compiler applies surprisingly few optimizations. Tail call eliminations is one of them. I explain when and how they work exactly in this blog post, which is accompanied by an elm-review rule called NoUnoptimizedRecursion which you can use to detect when a function is not tail call optimized.
f >> g >> h
I can imagine that the compiler makes an optimization here to run the three items consecutively, but I’m not entirely convinced that it stays that way if we obscure the operation with brackets.
The compiler doesn’t optimize function composition (neither >> nor <<), as you can see in this benchmark (see results).
I made a PR to have elm-optimize-level-2 optimize it though, which IIRC should work regardless of the number of brackets.
I am mostly interested in knowing for sure whether the previously mentioned library is safe to use, or whether I’m better off writing my own recursion functions where I pass an actual value into the recursion rather than a function to update the recursion.
I imagine it is safe, but I haven’t tried it in practice. I think that in general, writing recursive functions yourself would be better, as it gives you a lot of control over what to do and when/how to end recursion (for instance, List.foldl imposes can’t be interrupted eagerly) as well as having the least overhead.
The package you pointed at takes the example of recursion in a binary tree, which is tricky to do nicely natively in Elm, so maybe it is a good solution for that kind of situations.
I would like to learn about recursion depth optimizations
I wrote about implementing “Tail Recursion Modulo Cons” in Elm, which I think is an interesting evolution. Apart from that, I’m not sure what exactly exists outside of Elm. Some languages (Ocaml IIRC) have “mutually-recursive-functions” (where function A calls B and B calls A, and this gets tail-call optimized), and that’s where my knowledge ends.
