search

pithub / elm-compiler-in-elm-ui

UI for the Elm Compiler in Elm
Other
30 stars 1 forks source link

Make functions tail-recursive #1

Closed jfmengels closed 2 weeks ago

jfmengels commented 2 months ago

As you had announced, I quickly ran into stack overflows when running the repl in Chrome/Firefox.

I used the NoUnoptimizedRecursion elm-review rule to tell me recursive functions that are not tail-recursive.

Unfortunately, it reports over 430 errors. From a rough look, I think that the code style in the Elm compiler uses Haskell's laziness quite intensively and that doesn't translate well to the eager Elm runtime. I fixed a few, then focused on the parser and unfortunately could not find quick and easy fixes.

I figured I would at least make a PR with what I found in the meantime.

changlinli commented 2 months ago

As @pithub mentioned, I think the easiest way to fix it is likely via trampolining. It's a transformation that can be mechanically applied everywhere it needs to be. The main downside is that there is a perf hit, but it feels like that might be acceptable.

GordonBGood commented 2 months ago

As @pithub mentioned, I think the easiest way to fix it is likely via trampolining. It's a transformation that can be mechanically applied everywhere it needs to be. The main downside is that there is a perf hit, but it feels like that might be acceptable.

I am in process of doing something as pit has done, but rather use combinational techniques as used by elm/parser (and in fact used code derived from the Advanced version for parsing) which works with Chrome and Firefox. I have completed the Canonicalization phase and am working at converting pit's Type Inference phase to this technique and don't see that there will be stack overflow problems using this technique on this and later phases as it effectively breaks up the stack sections into small chunks and builds to the heap rather than the stack, just as trampolining does.

It may be somewhat faster than trampolining, but is about twice as slow as pit's code when run on Safari; however, I don't see many other choices as it is unlikely that Chrome (and Chromium-based browsers such as the new Microsoft Edge) will adopt optimized tail calls anytime soon.

pithub commented 2 weeks ago

I incorporated this change into a larger sequence of commits (see c1bf03d), so I'll close this pull request. Thank you again, @jfmengels 🙏