StackOverflow with Fable but not with fsc in release

[TysonMN]

Description

Consider PR hedgehogqa/fsharp-hedgehog#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 via npm.

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 using npm.

Related information

• Fable version
  • 3.1.1
• Operating system
  • Microsoft Windows Server 2019
  • 10.0.17763
  • Datacenter
• Node
  • 14.15.4
  • x64

[alfonsogarciacaro]

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.

[ncave]

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:

• Accumulate function parameters in a wrapper.
• Explicit tail calls: fext.js (can also handle mutual recursion).

[TysonMN]

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)?

[ncave]

@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.