Kliesli is not stack-safe on left-associated binds

[djspiewak]

    val unit = Kleisli.pure[Eval, Unit, Unit](())

    val result = (0 until 10000).foldLeft(unit) { (acc, _) =>
      acc.flatMap(_ => unit)
    }

    result <-> unit

This law fails. The reason this law fails is here:

  def flatMap[C](f: B => Kleisli[F, A, C])(implicit F: FlatMap[F]): Kleisli[F, A, C] =
    Kleisli((r: A) => F.flatMap[B, C](run(r))((b: B) => f(b).run(r)))
    //                                ^^^^^^ this bit here!

A chain of right-associated binds will push inside the lambda argument to flatMap, meaning it will be subject to the stack safety of the constituent monad F[_]. A chain of left-associated binds will result in a proportionally long chain of run(r). In order to solve this, we would need to use a similar technique as to what is done in StateT.

[ceedubs]

In years of scalaz usage, the stack unsafety of StateT bit me on a few occasions. But I never ran into the same with Kleisli. I'm curious whether anyone has ever had problems in real-world code because of this.

I think that safety (no runtime surprises) is a major argument for reformulating Kleisli to be stack-safe. I think that consistency with StateT is a minor argument for it. I think that performance and beginner-friendliness are minor arguments against it.

I'm assigning this to @adelbertc and @edmundnoble, who have done a lot of work with monad transformers. I'm also curious whether @johnynek has any thoughts on this.

[edmundnoble]

A chain of right-associated binds will push inside the lambda argument to flatMap, meaning it will be subject to the stack safety of the constituent monad F[_]

I don't believe this is correct, because your constituent monad is Eval and it's still not stack-safe. It is less stack-safe than the constituent monad; the A => F[B] function composition is the issue here. I have a potential quick solution in mind: FreeT[A => ?, F, B] is equivalent to Kleisli[F, A, B] but the former is stack-safe. Should we:

1. Use the StateT trick (which would work out as F[A => F[B]]),
2. Use FreeT[A => ?, F, B],
3. Use a hand-inlined 2 for performance, with custom operations.

To my mind the issue is important enough to merit 3 eventually, but 2 seems like an alright first approximation. I think the StateT trick is deleterious enough to performance to avoid in future.

[johnynek]

I think if we are going to hand inline we need to have benchmarks to show that it is actually faster, personally.

I think if we can implement a tailRecM, which we can for Kleisli, then we should consider recommending (and possibly making some functions to make it easier), when you need a recursive bind on Kleisli (or other monads) to jump into Free and back.

Something like this:

def toFree[A, B, M[_]](k: Kleisli[M, A, B]): Free[Kleisli[M, A, ?], B] =
  Free.lift(k)

def toKleisli[A, B, M[_]](f: Free[Kleisli[M, A, ?], B])(implicit M: Monad[M]): Kleisli[M, A, B] =
  f.runTailRec

which works for any monad (just call lift and runTailRec).

You could even imagine a macro that could possibly replace an expression on one Monad with this lifted-and-runTailRec version.

[adelbertc]

I actually have run into stack-safety issues with Kleisli, at least the Scalaz version, when I was using something like Kleisli with Task to do retries of an IO action. I don't remember what specifically what I was doing though.

[iravid]

I'd be happy to implement this if someone could provide guidance. A cats.effect.Sync instance for ReaderT[IO, E, ?] seems important ecosystem-wise for the 1.0 release.

[kailuowang]

@johnynek If I understand correctly, we could support stack safe left binds for Kleisli without a binary breaking change, if that's the case, this issue probably doesn't need to block RC1 right?

[johnynek]

@kailuowang I don't know a way to make it stack safe. What I propose is that when people need this they lift into Free express the computation there, and then get out. Since Kleisli has a tailRecM, this process is safe. It allows people to pay for safety as needed without having to force everyone to pay.

[kailuowang]

@johnynek sorry I missed your reply. Yeah, that's how I understand it as well. it's sort of a work around, not a change to the Kleisli. Is this idea similar to what is suggested in https://twitter.com/puffnfresh/status/939083836628930560 ?

[alexandru]

Hi all,

Trying to implement Sync[Kleisli[F, R, ?]] in cats-effect, I realized that the correct, non leaky implementation for flatMap would be:

def flatMap[A, B](fa: Kleisli[F, R, A])(f: A => Kleisli[F, R, B]): Kleisli[F, R, B] =
  Kleisli { r =>
    F.suspend(fa.run(r).flatMap(f.andThen(_.run(r))))
  }

This fixes the issue because it introduces a "lazy boundary" before "fa.run(r)", so it suspends evaluation before "fa.run" happens, so a new flatMap no longer has an opportunity to increase the stack size of the previous one.

Now @edmundnoble is telling me that doing this in cats-effect is problematic due to coherence rules, so our Sync instance is no longer coherent. And I can see his point, so we've got the following options:

1. we accept this incoherent Sync instance in cats-effect, or
2. we introduce the logic above in Cats, or
3. we remove the "left associative binds are stack safe" law from cats-effect's Sync

def flatMap[A, B](fa: Kleisli[F, R, A])(f: A => Kleisli[F, R, B]): Kleisli[F, R, B] =
  Kleisli[F, R, B] { r =>
    F.now(r).flatMap(r => fa.run(r).flatMap(f.andThen(_.run(r))))
  }

Note:

• this cannot be fixed in any other way; the only way to make Kleisli safe in this regard is to suspend the execution before the fa.run call
• doing F[A => F[B]] can fix it but only because of the above mentioned fact

Also, we need a solution for the upcoming cats-effect and we need it now, so I'd appreciate your thoughts on points 1, 2 or 3.

---

Btw, above you spoke about the trick of StateT and I believe you're talking about F[S => F[(A, S)]], so you've lifted that in an F[_].

Well, I hate to break it to you, but StateT is not stack safe either for "left associative binds" 🙂
See issue: typelevel/cats-effect#139

This too can be fixed, but I'm not sure you'll like it.

[alexandru]

Update, I now have a PR in Cats for your consideration: #2185

[alexandru]

Related, the issue and fix for IndexedStateT:

• IndexedStateT is stack unsafe for left associative binds #2186
• PR Fix #2186: make IndexedStateT stack safe #2187