Stack safety bug

[beezee]

Apologies, I haven't confirmed this myself but it looks credible.

Would love to know if this is easily addressable since I'm getting ready to put QIO in place as the main evaluation context in a fairly large application, with one primary driver being stack safety.

From this discussion thread - https://functionalprogramming.slack.com/archives/C7BBY9A95/p1604439126428300?thread_ts=1603574914.302900&cid=C7BBY9A95

it appears the following code would blow the call stack

it('should be stack safe - recursion case', () => {
  function a(n: number): any {
    if (n === 1) {
      return QIO.resolve(1)
    }
    return QIO.resolve({}).chain(() => a(n - 1))
  }
 defaultRuntime().unsafeExecutePromise(a(100000))
})

[tusharmath]

Yup this is a bug.

[mikearnaldi]

@tusharmath it is generated by the eager optimization of pure values introduced to improve perf of sync cases that basically skip the driver altogether:
https://github.com/tusharmath/qio/blob/master/packages/core/lib/main/QIO.ts#L103

I ended up removing it too a while ago

[beezee]

To help me understand the scope of the issue @tusharmath @mikearnaldi - is this only when used in recursive functions, or is it possible to blow the stack say by traversing a large enough collection?

[mikearnaldi]

@beezee traverse should not trigger that case, folding would

[beezee]

Thanks @mikearnaldi - so applicative is stack safe, and monad is not? This means that normal use of the monadic context will blow the stack in a large enough composition of kleisli arrows?

[mikearnaldi]

@beezee the problem is where it forms recursion per se Monad is not unsafe as doing 100.000 .chain in a while loop is perfectly safe but basically sync map & chain are not suspended and eagerly evaluated so if you get in a situation like a.chain(() => b.chain((c) => ...)) you will end up with a growing stack. The fix is pretty easy, just removing the eager evaluation will solve the problem, QIO has a driver that does trampolining so if the op becomes suspended the bug simply goes away.

[beezee]

Got it thank you