I copied your Ellie locally and compiled with elm make src/Main.elm. Sometimes its helpful to see the compiled code to figure out where things are not tail recursive. For the Forward case I get:
case 'Forward':
var _n1 = steps.a;
var rest = steps.b;
var nextStep = A2(
author$project$Main$translate,
initialPosition,
A2(
author$project$Main$rotate,
{x: stepSize, y: 0},
orientation));
return A2(
elm$core$List$cons,
nextStep,
A4(author$project$Main$turtleStepsToPointsHelper, nextStep, orientation, stepSize, rest));
Elm is definitely not as advanced as Haskell is when it comes to detecing that things can be tail recursive. One thing to note is that |> and <| seem like they should be eliminated as syntactic sugar, but in fact get turned into function calls, and can often prevent tail recursion. (That does not seem to be the case this time).
I think what is missing is that Elm does not have the tail recursion modulo cons optimisation:
I think instead of consing on nextStep, can it simply be added into the result list of turtleStepsToPointsHelper? Then have a pass at the end to extract them all into a list? The details are a little hazy and I am being called to lunch, but something like that may work…
Hey @dandrake! This topic can be tricky without a good intro to stack usage, so check out this explanation of “tail call elimination” to learn why the current code is causing issues in the browser:
It outlines the rewrite technique needed in this case (pass the result list as an argument and reverse it at the end if order is important) that is common in Elm, OCaml, Haskell, Lisp, etc. The larger idea is to turn stack allocations into heap allocations, that way the size of the stack is never a problem for the code.
That resource is just a draft, but I hope it’s helpful nonetheless. And I’m sure someone on here can take it from there in terms of suggesting the specific rewrite for your case!
Aside: It would be cool to have a special error message for this case. If you have time and interest, please add an issue here with this program and the title “better guidance for stack overflows”. I imagine that it might be somewhat frail to detect the exact JS errors for stack overflows across all browsers, but I would love to show a link about tail call elimination at that exact time!
Note: JS is likely to have different stack characteristics than Haskell or OCaml. Maybe stack frames are bigger, maybe the allowed depth is smaller, etc. So the size limit may be reached at different depths in each case. (Laziness in Haskell can also end up putting more things in the heap, which is a complex tradeoff of its own. Sometimes you really want something to be allocated on the stack, thereby making GC pauses less frequent!)
Thanks @rupert! That was the trick. I was a bit confused about your earlier comment about " instead of consing on nextStep , can it simply be added into the result list of turtleStepsToPointsHelper" and I didn’t know exactly how to set that up. Thanks for the example code showing how easy it is.
@evancz, I will add an issue. And thank you for the link – I have some basic understanding of all the stack and heap allocation stuff, and tail call elimination – but it gets confusing for me because when I look an at pure Elm – such as the code I shared above – I think at one conceptual level (a very pure, functional programming level), but to get this code to work, you have to think at a different conceptual level, one closer to the operating system and the gory details of memory management.
I also wrote a static analysis rule using elm-review that detects (tail-call) unoptimized recursive functions, which can be helpful to detect these ahead of time. I do want to note that not all functions are worth optimizing this way (in some cases, you’re unlikely to ever hit the maximum call stack size), but it’s useful to have a way of detecting this.
Is ‘tail call modulo cons’ implemented in elm-optimize-level-2? I saw some comments around that in the thread linked below. Not sure if level-2 would be a convenient place to implement that, maybe needs to be in the compiler.
I’d like to add that when I first saw the Elm website saying that Elm is “delightful” I was a bit skeptical – but now I agree! I also love the compiler error messages. They are super friendly and helpful. And the help here was fast and, uh, helpful. Thanks.
It is not no. But I have been wondering for a while on how to improve performance of custom list functions that create lists the way OP also did (or rather, do it in the suggested ways because of the stack overflow), and I thank you for letting me know about this thread (I think I somehow missed it back then, or it didn’t register with me), which may give me the piece I was missing. I’m interested in looking into this. I’m not great with scientific literature but I at least have something to read and know the terms in order to look for more.