Effect.stackSafetyOnRepeatedAttempts is too strong about cats-effect HOT 21 CLOSED

I'm fine rewriting the law to not use foldLeft. But I don't think that will change the stack overflow or the memory issues that some structures have.

from cats-effect.

@djspiewak I've debugged this extensively. If you do loops in terms of flatMap (and not an eager foldLeft), then cats.Eval and the old Monix Task are fine.

The new implementation I have in Monix is fine with this eager foldLeft too.

In general the problem in attempt with that eager foldLeft happens if you capture a stack frame, which happens for this particular operation because the BindSuspend / FlatMap state does not deal with errors. You worked around this by using your AndThen. I worked around this by making the FlatMap state treat errors in the encoding of Task.

from cats-effect.

Btw, as I said, I can fix cats.Eval too. Should I?

from cats-effect.

I'm pretty sure the problem isn't the eagerness of foldLeft, but rather the left vs right associativity of the inner bind. Left associated binds will always be fine with this sort of construction, since flatMap itself gives stack safety. Right associated binds force attempt to care about it as well, which is what the law is stressing.

In either case, I'll look at it later and play with the formulation a bit.

from cats-effect.

Right, well, I'm not sure if this is useful, but in Monix I have this state:

final case class FlatMap[A, B](source: Task[A], f: A => Task[B]) extends Task[B]

My source is not a thunk. In my original attempt implementation I did something similar to this:

FlatMap(
  Suspend(() => source.attempt),
  either => either match {
    case Right(value) => f(value).attempt
    case Left(ex) => Task.now(Left(ex))
  }
)

Well, this fails that test of course. Basically in the implementation I don't have stuff suspended in closures, except for this attempt implementation. In practice, I never experienced problems with it and never had users report problems.

But now with your test, I did a neat trick. I'm basically introducing a new function type:

abstract class Transformation[-A, +R] extends (A => R) { self =>
  final override def apply(a: A): R =
    success(a)

  def success(a: A): R
  def error(e: Throwable): R
}

object Transformation {
  def fold[A, R](fa: A => R, fe: Throwable => R): Transformation[A, R] =
    new Fold(fa, fe)
}

And then in the Task implementation I now have this operation:

  def transformWith[R](fa: A => Task[R], fe: Throwable => Task[R]): Task[R] =
    FlatMap(this, Transformation.fold(fa, fe))

Which means that attempt can now be described like this:

source.transformWith(Task.now(Right(_)), Task.now(Left(_)))

And then in the run-loop implementation I'm doing what the JVM does basically: when an error happens, I unwind the "call stack" until I discover a Transformation, which can then be used to treat the error - if no such Transformation is possible, the error is yielded unaltered.

The cool thing is that my implementation no longer builds intermediary Right(Right(Right(Right(...)))) results, which you tend to have because you keep doing andThen on that source.

from cats-effect.

Ah that's quite cool. I'm curious though as to where these Right(Right(Right(Right values are coming from, because I don't see where that is implied in the implementation.

from cats-effect.

To see it I basically placed println statements in the code. But if you'll take a look at BindSuspend:

case class BindSuspend[E, +A](thunk: AndThen[Unit, IO[E]], f: AndThen[E, IO[A]]) extends IO[A] {
 def attempt: BindSuspend[Either[Throwable, E], Either[Throwable, A]] =
    BindSuspend(thunk.andThen(AndThen(_.attempt)), f.andThen(AndThen(_.attempt)).shortCircuit)
}

So it's a recursive thing and in that foldLeft you end up doing thunk.andThen(AndThen(_.attempt)) repeatedly and you'll end up with something like ...

thunk.andThen(_.attempt)
  .andThen(_.attempt)
  .andThen(_.attempt)
  .andThen(_.attempt)
  .andThen(_.attempt) 
  // .....

And then the right member of this BindSuspend ends up decomposing it, again repeatedly, until you reach the final results you expect.

from cats-effect.

So it's a recursive thing and in that foldLeft you end up doing thunk.andThen(AndThen(_.attempt)) repeatedly and you'll end up with something like ...

Except the chain should look something like the following:

thunk.andThen(_.attempt)
  .andThen(_.attempt).shortCircuit
  .andThen(_.attempt).shortCircuit
  .andThen(_.attempt).shortCircuit
  .andThen(_.attempt).shortCircuit
  // .....

So in theory, it should be decomposed at each stage, avoiding the full construction. I have seen heap issues though with some structures, so what you're saying makes sense, I just can't see how it gets constructed in the first place.

from cats-effect.

To see it I placed a println in Pure like:

  private final case class Pure[+A](a: A) extends IO[A] {
    def attempt = {
      val ref = Pure(Right(a))
      println(s"attempt: $ref")
      ref
    }
  }

And then I came up with a simpler test to debug (was curious to see how it works):

val acc0 = IO(0).attempt.flatMap {
  case Right(x) =>
    println(s"flatMap(0): $x")
    IO.pure(x + 1)
  case Left(ex) =>
    IO.raiseError(ex)
}

val acc1 = acc0.attempt.flatMap {
  case Right(x) =>
    println(s"flatMap(1): $x")
    IO.pure(x + 1)
  case Left(ex) =>
    IO.raiseError(ex)
}

val acc2 = acc1.attempt.flatMap {
  case Right(x) =>
    println(s"flatMap(2): $x")
    IO.pure(x + 1)
  case Left(ex) =>
    IO.raiseError(ex)
}

val acc3 = acc2.attempt.flatMap {
  case Right(x) =>
    println(s"flatMap(3): $x")
    IO.pure(x + 1)
  case Left(ex) =>
    IO.raiseError(ex)
}

This sample prints:

attempt: IO(Right(0))
attempt: IO(Right(Right(0)))
attempt: IO(Right(Right(Right(0))))
attempt: IO(Right(Right(Right(Right(0)))))
flatMap(0): 0
attempt: IO(Right(1))
flatMap(1): 1
attempt: IO(Right(2))
attempt: IO(Right(Right(2)))
flatMap(2): 2
attempt: IO(Right(3))
flatMap(3): 3

from cats-effect.

@alexandru I haven't forgotten about this, btw. I'm still pondering your snippet, since it still doesn't make sense to me. It's concerning though. I would not consider those consequences to be an acceptable tradeoff for the current stack-safety implementation.

from cats-effect.

I see the problem now. The issue is here:

BindSuspend(thunk.andThen(AndThen(_.attempt)), f.andThen(AndThen(_.attempt)).shortCircuit)

Specifically:

thunk.andThen(AndThen(_.attempt))

So the interleaving of flatMap and attempt is irrelevant, since it all associates to the right and every attempt ends up being composed onto the first, building the linear chain, and obviously rebuilding it in increments at each iteration. This in turn generates an enormous amount of garbage on the heap.

IMO, either we need to give up on supporting this use case, or we need a different implementation of attempt. @mpilquist any thoughts?

from cats-effect.

You can do what I did in Monix. So with BindSuspend you could do:

def transformWith[R](fa: A => IO[R], fe: Throwable => IO[R]): IO[R] =
  BindSuspend(thunk, f.andThen(Transformation(fa, fe)))

And then attempt is just:

source.transformWith(a => IO(Right(a)), e => IO(Left(e)))

So that's Transformation <: AndThen. And then in your AndThen implementation you could discriminate on Transformation usage ... so when encountering an error, you traverse your stack until there are no more functions left or until you encounter a Transformation, which then you use to handle the exception.

I can try my hand at a PR if you'd like.

EDITED: fixed mistakes :)

from cats-effect.

I also described this in my comment above: #42 (comment)

from cats-effect.

BTW, going back to my original point, I would relax the law, because it's maybe too much for implementations.

And shouldn't attempt related laws be specified on Sync anyway?
Eval should be able to pass this law too (currently it doesn't).

from cats-effect.

@alexandru The Transformation solution sounds like an appreciably refined version of the current ShortCircuit concept. Basically, you're building around handleErrorWith rather than attempt, which avoids the repeated boxing. PR would definitely be welcome.

I know you described the problem previously. :-) I didn't understand though until I pieced it together myself.

The attempt laws really should be in SyncLaws. I put them on EffectLaws mostly because I was thinking imperatively and felt that I needed runAsync, but really Eq can be the driver there. There's no reason not to move them up.

from cats-effect.

@djspiewak cool, I'll work on a PR for fixing attempt, but I have to get it right, please be patient 😄

from cats-effect.

No rush!

from cats-effect.

OK, I managed to do a PR, let me know what you think: #46

from cats-effect.

Looping back to the topic in the OP, an idea I've been playing with is keeping stackSafetyOnRepeatedAttempts in EffectLaws and not pushing it up into SyncLaws, where it theoretically could live. The idea is that an Effect is a stronger constraint than Sync even above and beyond the need for an asynchronous copoint.

As a sidebar, @alexandru your new AndThen shenanigans fixed a ton of problems I found with derived instances (e.g. Effect[StateT[F, S, ?]] given Effect[F] and Monoid[S]). Very nice.

from cats-effect.

Going to punt on this for now and move ahead with v0.2. We can always remove or weaken laws.

from cats-effect.

Issue is old, closing it in an effort to clear the issue tracker. If this becomes relevant again due to some integration, we'll reopen.

from cats-effect.