Open TysonMN opened 3 years ago
Hi @TysonMN, thanks for the report! It's great you're working to support Fable with Hedgehog, I'd love to see this library in Fable projects. It'd be great if you could isolate a case that fails only with Fable, but please note that unfortunately tail-call optimization is not as advanced as in .NET so it may be not possible to fix those cases. First, as far as I know, JS engines haven't implemented tail-call optimization natively yet, so we're restricted to the cases that can be converted to a while loop at compile time.
Also, we don't have support for tail-call optimization with mutually recursive functions atm, sometimes you can resolve this by inlining. At some point, Tomas Petricek had a draft to support this so it may be possible, but I'm not sure how much work would entail.
As @alfonsogarciacaro said, most JS engines unfortunately have not implemented TCO yet. There are some JS workarounds that vary in performance, but Fable is not using any of them:
Thanks for the information and links.
Yes, my understanding was that one should not typically expect TCO from Fable or the downstream JS compilers.
What about Fable's trampoline? Would you recommend that we use a similar trampoline in our code to avoid overflowing the stack?
That seems like a great idea and abstraction. We might be able to make use of it in F#-Hedgehog even for some cases that are overflowing when using the fsc.
[...] we're restricted to the cases that can be converted to a while loop at compile time.
Are you saying that Fable is typically able to compile a recursive function into a loop (so support by downstream JS compilers is not needed)?
@TysonMN Trampolines may work but have some performance cost, which may or may not be acceptable to you.
Yes, Fable is able to optimize (rewrite into a loop) some self-referencing tail-recursive functions. But not in the more general case of mutually recursive functions, or continuation passing style.
Description
Consider PR https://github.com/hedgehogqa/fsharp-hedgehog/pull/314. Our tests pass when using the standard F# complier (fsc) when the configuration is
Release
, which means the compiler will perform tail call elimination/optimization. The same test fails when compiled with Fable and executed vianpm
.Repro code
Here is a link to one of the specific tests that fails for Fable+
npm
but passes with fsc.Expected result
All tests, including that one, pass. For example, see these logs from our GitHub Action and executed those tests compiled with the fsc.
Actual results
Some tests, including that one, fail due to a
StackOverflow
. See these logs from our GitHub Action that executed that test compiled with Fable usingnpm
.Related information