Cats-effect: Cancelation laws presuppose no interruption

[jdegoes]

Currently baked into the assumption of cats-effect is a guarantee that is too strong:

  def runCancelableStartCancelCoherence[A](a: A) = {
    // Cancellation via runCancelable
    val f1 = Pledge[IO, A].flatMap { effect1 =>
      val never = F.cancelable[A](_ => effect1.complete[IO](a))
      F.runCancelable(never)(_ => IO.unit).flatten *> effect1.await[IO]
    }
    // Cancellation via start.flatMap(_.cancel)
    val f2 = Pledge[IO, A].flatMap { effect2 =>
      val never = F.cancelable[A](_ => effect2.complete[IO](a))
      val task = F.start(never).flatMap(_.cancel)
      F.runAsync(task)(_ => IO.unit) *> effect2.await[IO]
    }
    f1 <-> f2
  }

This is basically a guarantee that F does not support interruption, since any F that supports interruption cannot guarantee that in F.start(fa).flatMap(_.cancel), any actions sequenced into fa will ever be run. In Scalaz 8 IO, fa will be forked but potentially interrupted immediately, before it has had a chance to execute even the first operation.

Not only is this law too strong, in the sense it guarantees that F cannot provide interruption, but furthermore, it points to a fundamental conflation of two responsibilities that should be distinct: that of interruption (or "cancellation", if you prefer), and that of finalization.

By requiring that the callback for the cancelable be invoked, it provides for and encourages its use as a finalizer, which is a guarantee separately provided by bracket. Indeed, in this example test, it is used and tested for exactly like a finalizer would be.

The quick fix is to drop laws like this that guarantee non-interruptibility, and I'd propose a larger fix would involve examining cancelation semantics to achieve a truly orthogonal basis.

[alexandru]

We talked about it on Gitter yesterday, I think it was @jmcardon that mentioned it.

Such laws are a problem indeed if we are to support Scalaz's IO or the Monix Task when executed with its autoCancelableRunLoops mode.

[alexandru]

Related Monix issue, kindly signaled by @oleg-py: https://github.com/monix/monix/issues/665

[alexandru]

So, I'm trying to add the cancelation of the yielded F[_] in Iterant and one thing is clear …

Auto-cancelable flatMap loops make things way harder than they should be. I think I will write a blog post about it, but here's the explanation:

---

First to pick the use case I care about — Iterant is a data structure that looks like this:

sealed abstract class Iterant[F, A]

// Like List's Cons
case class Next[F[_], A](elem: A, rest: F[Iterant[F, A]], stop: F[Unit])
  extends Iterant[F, A]

case class Suspend[F[_], A](rest: F[Iterant[F, A]], stop: F[Unit])
  extends Iterant[F, A]

// Like List's Nil
case class Halt[F[_], A](error: Option[Throwable])
  extends Iterant[F, A]

Characteristics:

1. much like a List, the user can follow rest pointers to the next state, rest that is given in F[_]
2. unlike a List we can trigger an "early stop" instead, by following the stop pointer

Therefore lets say that we want to find if some item exists in our Iterant:

def exists[F[_] : Sync, A](p: A => Boolean)(stream: Iterant[F, A]): F[Boolean] =
  stream match {
    case Next(a, rest, stop) =>
      if (p(a)) 
        stop.map(_ => true)
      else 
        rest.map(exists(p))
    case Suspend(rest, _) =>
      rest.map(exists(p))
    case Halt(None) =>
      F.pure(false)
    case Halt(Some(e)) =>
      F.raiseError(e)
  }

As you can see we've got a transformation that goes like this ...

Node 1 => (rest.flatMap) => Node 2 => (rest.flatMap) => Node 3 => (rest.flatMap) => 
  Node 4 => ... => Node X => stop

---

These I believe are facts and somebody please prove me wrong, because we need to decide if we can move forward:

1. you cannot transform the rest links in such a way as to yield an Iterant that has such a flatMap chain safely cancelable; this is because bracket is useless in this case when applied to rest links, because all those brackets will be joined by flatMaps that are auto-cancelable;
   without flatMap being auto-cancelable you could apply bracket on each rest node and say that in case of cancelation, please execute stop
2. the only way to make this work is to apply a bracket to the whole flatMap chain, or in other words, the only place to apply bracket is in def exists above

And this complicates things, a lot ...

We can make the F[Boolean] yielded by exists to be cancelable, however it isn't optimal, because as I tried to explain, cancelation is a concurrent action 😉

For example this naive implementation is broken because it does no synchronization:

def exists[F[_] : Sync, A](p: A => Boolean)(stream: Iterant[F, A]): F[Boolean] = {
  def loop(stopRef: ObjectRef[F[Unit]])(stream: Iterant[F, A]): F[Boolean] =
    stream match {
      case Next(a, rest, stop) =>
        if (p(a)) {
          stopRef.elem = null
          stop.map(_ => true)
        } else {
          stopRef.elem = stop
          rest.map(loop(stopRef))
        }
      case Suspend(rest, _) =>
        stopRef.elem = stop        
        rest.map(loop(stopRef))
      case Halt(None) =>
        stopRef.elem = null
        F.pure(false)
      case Halt(Some(e)) =>
        stopRef.elem = null        
        F.raiseError(e)
    }

  F.suspend {
    // Boxed variable
    val stopRef: ObjectRef[F[Unit]] = new ObjectRef()
    // Applying bracket by using a "stop" reference that gets mutated
    // at each step:
    F.bracket(loop(stopRef)(stream)) {
      case (_, ExitCase.Canceled(_)) if stopRef.elem != null => 
        stopRef.elem
      case _ =>
        F.unit
    }
  }
}

We could make this safer by applying locks, like synchronize blocks to all of our logic, however you can see that this is essentially a no-go, because:

• it increases complexity, ensure that no user will ever write such a function without getting the first version wrong
• it will have performance issues; it's bad enough that IO data types have a performance cost on top of the JVM, we're now forced to use locks as well

The only implementation that's sane actually is to do this thing cooperatively:

def exists[F[_] : Sync, A](p: A => Boolean)(stream: Iterant[F, A]): F[Boolean] = {
  def loop(isCanceled: ObjectRef[Boolean])(stream: Iterant[F, A]): F[Boolean] =
    stream match {
      case Next(a, rest, stop) =>
        // Noticing isCanceled == true, triggering stop cooperatively
        if (isCanceled.elem)
          stop *> F.never
        else if (p(a))
          stop.map(_ => true)
        else
          rest.map(loop(stopRef))

      case Suspend(rest, stop) =>
        if (isCanceled.elem)
          stop *> F.never
        else
          rest.map(loop(stopRef))

      case Halt(error) =>
        if (isCanceled) F.never
        else error.fold(F.pure(false))(F.raiseError)
    }

  F.suspend {
    // Boxed variable
    val isCanceled: ObjectRef[Boolean] = new ObjectRef(false)
    // We have to operate `bracket` on an `uncancelable` value
    F.bracket(F.uncancelable(loop(isCanceled)(stream))) {
      case (_, ExitCase.Canceled(_)) => 
        F.delay(stopRef.elem = true)
      case _ =>
        F.unit
    }
  }
}

But this ensure that the user can never prepare an Iterant that can do safe concurrent cancelation, having to wait on each F[_] before the thing is finally cancelled. So for example the behavior of something like this would be awful:

Iterant[Task].intervalAtFixedRate(10.seconds)

Having to wait seconds in this case before the thing gets released isn't cool at all.

It also (still) has the problem that this complexity is moved to the user, because the user is expected to be able to walk and process an Iterant data structure by himself and thus to understand the intricacies of auto-cancelable bind chains.

---

In case flatMap loops are not cancelable by default, it means that the user can be in charge of cancelation behavior, because the user can describe Iterant values that can be safely canceled in a flatMap loop.

And to prove this point, consider that we can also provide an utility like this:

def makeCancelable[F[_] : Sync, A](stream: Iterant[F, A]): Iterant[F, A] = {
  def prepare(rest: F[Iterant[F, A]], stop: F[Unit]): F[Iterant[F, A]] =
    F.bracket(rest) {
      case ExitCase.Canceled(_) => stop
      case _ => F.unit
    }

  stream match {
    case Next(a, rest, stop) =>
      Next(a, prepare(rest).map(makeCancelable), stop)
    case Suspend(rest, stop) =>
      Suspend(prepare(rest).map(makeCancelable), stop)
    case Halt(_) =>
      stream
  }
}

Notice how sane and easy this is. And no, this is not possible to do with auto-cancelable bind loops.

---

TL;DR — By introducing auto-cancelable bind loops as a possibility in the Concurrent laws, the Iterant data structure as described is no longer possible.

Please prove me wrong, because I'd like to be wrong on this one.

[pchlupacek]

@alexandru if I understand correctly your explanation, this really seems like the deal of interruption which we have to solve in fs2. Essentially we have made an assumption that F is non-cancellable in terms of receiving any stable result after cancellation, but the fs2.Stream is. So we look on cancelling the F only as an 'optimisation' technique, to not have many interrupted F in background. Think of it like every eval frame is sort of racing between being evaluated or cancelled.

To solve the interruption in flatMap of higher structure (Stream) operating on F we are using couple of tricks, like Scope that essentially holds the state _and_ the computation to be run after cancellation happens.

I think your observation seems right, at least I think this is sort of describing what we have observed in fs2.

[jdegoes]

Scalaz 8 bracket makes acquisition and release non-interruptible. Thus, if acquisition succeeds, then release will be invoked — even though it's possible the body will be interrupted. Scalaz 8 also has a combinator for denoting an action as uninterruptible, although it should never be used when bracket is appropriate, and rarely used otherwise, since you cannot prevent interruption in the general case (loss of power, CPU failure, OOME, etc.).

IMO there is no way to make a high-performance, resource safe stream except by compiling down to IO. "On-the-fly" interpretation schemes will fail due to mismatched semantics.

That said I'll take a closer look at this when I get a chance and propose how'd I'd attempt this "interpretive" design in Scalaz 8.

[jdegoes]

My opinion on this matter is that:

1. The current model of cancellation provides the wrong guarantees, conflating finalization with interruption and rendering many otherwise valid implementations of concurrent unlawful.
2. Any assumption of uninterruptability in higher-level libraries like Iterant or FS2, no matter how convenient it may be, is incorrect.
3. The only correct way to implement finalization at a higher-level is to compile it to the lowest level. It may be more work. In general, it's always more work to do the correct thing.

[oleg-py]

@jdegoes

conflating finalization with interruption

We had a chat about this with @edmundnoble on Gitter, and apparently we don't. .cancelable builder is meant only for interruption, whereas Bracket handles finalization.

The only correct way to implement finalization at a higher-level is to compile it to the lowest level

The problem is that we don't have a good common "lowest level". Compiling an fs2.Stream[F, A] to F[_]: Concurrent _has to be different_ from compiling to F[_]: Sync, even if we don't plan to make resulting F[Unit] cancelable.

---

I think we need the following typeclass:

@typeclass trait Interruptible[F[_]] extends FlatMap[F] {
  def doOnInterrupt[A](fa: F[A])(action: F[Unit]): F[A]
  def uncancelable[A](fa: F[A]): F[A]
}

with one law, expressing the guarantee we require:

def uncancelableEliminatesInterruptors[F[_], A, B](fa: F[A], f: A => F[B], action: F[Unit]) =
  fa.doOnInterrupt(action).flatMap(f).uncancelable <-> fa.flatMap(f).uncancelable

And also make

@typeclass trait Sync[F[_]] extends Bracket[F] with Interruptible[F] { ... }

(or, alternatively, add these on Sync directly)

• Stack-like data types that do not support concurrent interruption, such as Coeval, upcoming Exec or () => Future[A] can implement doOnInterrupt and uncancelable as identities returning fa.
• Iterant can implement uncancelable by running the tail to completion and doOnInterrupt as doOnEarlyStop.
• We gain ability to build interruptible actions without stepping into side-effect land, using pure abstractions like MVar. Alternatively, things like MVar themselves can be implemented using Async constraint alone, with uncancelable versions being just an optimization.
• We can compile Iterant using uncancelable without requiring typeclasses too strong or a type-level instanceOf.

/cc @SystemFw, @mpilquist, @alexandru

[alexandru]

@oleg-py so isn't doOnInterrupt basically our bracketCase? Isn't this equivalence always true?

task.doOnInterrupt(f) <-> task.bracketCase(F.pure) { case Cancelled(_) => f; ... }

Also uncancelable doesn't solve the issue with Iterant's encoding.

What we'd need would be something like ensureAutoCancelableLoopsAreOff. But then once we go down that route, it would mean that auto cancelable loops are on by default.

It's an interesting problem to think about.

[oleg-py]

@alexandru I did not find any law specifying what happens if acquire part of bracket is cancelled. I'm surprised it works, actually, since raising an exception in acquire is specified to NOT trigger finalizer (here)

uncancelable is there to solve the issue that Sync[F], as an interface, cannot possibly be safe to work with a type that just happens to have Concurrent[F] instance. With a pure builder that lets you to specify interruption logic.

For Iterant, I would be perfectly fine for now if I couldn't cancel an F[_] mid-flight. Maybe we could get away with having something like uncancelableFlatMap which wouldn't make whole nested F[_] uncancelable, just a single bind.

[alexandru]

@alexandru I did not find any law specifying what happens if acquire part of bracket is cancelled. I'm surprised it works, actually, since raising an exception in acquire is specified to NOT trigger finalizer (here)

That's because if acquire fails, there's nothing to release. But you have a point, the equivalence is more like this:

task.doOnInterrupt(f) <-> 
  IO.pure.bracketCase(_ => task) { case (_, Cancelled(_) | Error(_))  => f; ... }

uncancelable is there to solve the issue that Sync[F], as an interface, cannot possibly be safe to work with a type that just happens to have Concurrent[F] instance. With a pure builder that lets you to specify interruption logic.

Meh, I don't think working with Sync is such a big problem.

Even if the abstraction, and lets talk of Iterant because I love talking about it ... is completely unaware of cancelation capabilities in some operations, you can still build an Iterant that's safe to use and you might actually not want for the thing to be uncancelable. I gave this example in some other issue, but here it is again:

def readLine(in: BufferedReader): IO[String] =
  IO.unit.bracket(_ => IO.cancelBoundary *> IO(in.readLine)) {
    // Some duplication, but it's OK IMO, especially because we might want to do extra
    // synchronization here, versus the normal finalizer described via Iterant ;-)
    case Canceled(_) => IO(in.close()) 
    case _ => IO.unit
  }

// The new bracket for Iterant ;-)
val resource = Iterant[IO].resource {
  IO(new BufferedReader(...))
} { in =>
  IO(in.close())
}

resource.flatMap { in =>
  Iterant.repeatEvalF(readLine).takeWhile(_ != null))
}

The operations described are at this point, all of them, operating with Sync. Is this an unsafe Iterant? No, not within the current model of Cats-Effect. Is this stream cancelable? Yes. Does it need uncancelable? Nope.

For Iterant, I would be perfectly fine for now if I couldn't cancel an F[_] mid-flight. Maybe we could get away with having something like uncancelableFlatMap which wouldn't make whole nested F[_] uncancelable, just a single bind.

Sure, but if Scalaz 8 introduces an uncancelableFlatMap, people could use it to implement our Sync, problem solved 😜 Then we could also implement a cancelableFlatMap on our end and thus be able to implement their type-classes 🙂

---

So the issue right now is that I've got problems to solve with Iterant's encoding. An answer saying that Iterant's encoding is wrong or irrelevant is not good enough.

The solution that we have works and works well. It is true that it doesn't admit Monix's Task auto-cancelable behavior (when opted-in) or Scalaz 8 IO, however a stronger argument has to be made in support of it, instead of "this seems cool" or "Scalaz 8 does it, so we should to".

Iterant works well with the current model and it would break under the auto-cancelable model.
Therefore let me ask another question ...

What solutions are possible under the auto-cancelable model that are not possible under the Cats-Effect model? Can you come up with an encoding of a streaming data type or whatever that wouldn't work under Cats-Effect?

If yes, we can evaluate which is better, if no, then the assumption will be that Cats-Effect is the more useful cancelation model because it can describe more things 😉

[alexandru]

@oleg-py On my way to the hotel room I've been thinking about it and I think your plan isn't bad, except with a small change:

@typeclass trait Interruptible[F[_]] extends FlatMap[F] {

  def uncancelable[A](fa: F[A]): F[A]

  def uncancelableBinds[A](fa: F[A]): F[A]
}

Some notes:

1. we probably need a better name than Interruptible, since Coeval would implement it and it wouldn't be interruptible obviously
2. your doOnInterrupt is subsumed by bracketCase, so there's no need for it, see my sample
3. what I need for Iterant is actually uncancelableBinds, to get the current behavior of IO

[alexandru]

@jdegoes would you be willing to accept, as a compromise lets say, an uncancelableBinds operation that would turn off your behavior on interruption for flatMap chains?

Something that will render only nodes built with the cancelable builder (in your case async I believe) as interruptible?

If we'd have an assurance that this operation exists, we could then modify those laws to work only in the presence of an uncancelableBinds. Problem solved.

[alexandru]

I must mention that this would also benefit Scalaz 8's IO because it makes solutions like Iterant easier to work with, even if you may think there are better ways to handle streaming.

[jdegoes]

We had a chat about this with @edmundnoble on Gitter, and apparently we don't. .cancelable builder is meant only for interruption, whereas Bracket handles finalization.

The law guarantees that in the event of "interruption", the callback passed to cancelable will be invoked. If the callback is not invoked, it fails the test. Providing a guarantee that something will be invoked in the event of interruption is a conflation of interruption and finalization, because the capability to acquire a guarantee of invocation can already be separately provided by finalization.

The problem is that we don't have a good common "lowest level". Compiling an fs2.Stream[F, A] to F[_]: Concurrent has to be different from compiling to F[_]: Sync, even if we don't plan to make resulting F[Unit] cancelable.

This is a problem with the type class hierarchy. As a library author, you should not have to workaround problems with the type class hierarchy. Rather, we should fix the problems with the hierarchy.

See here for my recommendations on a type class hierarchy that does not have these semantic problems.

I did not find any law specifying what happens if acquire part of bracket is cancelled. I'm surprised it works, actually, since raising an exception in acquire is specified to NOT trigger finalizer

This is a semantic problem in the model, which is already addressed by Scalaz 8 IO.

The reason is quite simple: the acquire action consists of n operations op_1, op_2, ..., op_n. You have no way to know when the resource is acquired (i.e. its inner call to socket.connect has completed). It occurs in op_i for some i, followed by other actions that possibly wrap mutable structures or do post-processing. If the acquire IO is interrupted anywhere, then there exists the possibility that even though the IO has not completed, it has already acquired its resource.

Note this problem is confounded by the fact that cancellation could occur between the boundary of acquire and use, and if the implementation is not careful, it may in rare cases succeed in acquiring the resource but fail to release it.

There is only one correct semantic here: acquire cannot be interrupted, and should it complete (even reach the boundary but not execute the next operation), then release must be invoked.

Similarly for release: release must always be uninterruptible. Of course, it can fail due to defect, but cannot fail due to error and must never be interrupted.

IMO there do not exist multiple correct choices here for implementation: there is only one choice that is sane. Any other choice (interruptible acquire, interruptible release, interruption on boundary after acquire without release) will lead to leaking resources.

Sure, but if Scalaz 8 introduces an uncancelableFlatMap, people could use it to implement our Sync, problem solved 😜 Then we could also implement a cancelableFlatMap on our end and thus be able to implement their type-classes 🙂

You can make an action uninterruptible with io.uninterruptibly. However, it's not sufficient to pass the law, unless such a method is added to Concurrent and used by the test in the right way.

would you be willing to accept, as a compromise lets say, an uncancelableBinds operation that would turn off your behavior on interruption for flatMap chains?

Yes. I think this is uninterruptibly, but we need to discuss to make sure.

I also want to offer up the following proposal:

• Make Scalaz IO an independent project (scalaz-io), so that it does not depend on any part of scalaz. It can be used by Cats, Scalaz 7.x, Scalaz 8.x, etc.
• Focus cats-effect on type classes to unify across effect types, ideally modeled after the hierarchy I proposed (which I will work on and donate to the project). Delete any functionality from cats-effect which cannot be expressed solely in terms of the type classes.
• Delete the IO implementation in cats-effect and encourage people to use Monix, Scalaz IO, etc.

The current situation is clearly not sustainable and is leading to duplicate effort with no real benefit (no one can tell me why anyone should use Cats IO over Monix—there is no reason). And I think it's already proven at this point the type class hierarchy is suboptimal—it was a good first effort but can be done better in light of evolving designs in the space, and I think this issue and many others have pointed the way to a better design.

[alexandru]

@jdegoes

would you be willing to accept, as a compromise lets say, an uncancelableBinds operation that would turn off your behavior on interruption for flatMap chains?

Yes. I think this is uninterruptibly, but we need to discuss to make sure.

So I want this sample to work:

IO.unit.flatMap(_ => IO.cancelable(_ => IO(println("Cancelled!")))
  .uncancelableBinds
  .start
  .flatMap(_.cancel)

On evaluation I want it to print Cancelled!, as a guarantee of this being marked with the uncancelableBinds operation. And IO.cancelable I think you named it async.

Could Scalaz's IO provide this behavior? I may be biased, but in Monix's Task implementation, the difference is made by a boolean flag checked by an if on async boundaries, that can be turned on or off.

The law guarantees that in the event of "interruption", the callback passed to cancelable will be invoked. If the callback is not invoked, it fails the test. Providing a guarantee that something will be invoked in the event of interruption is a conflation of interruption and finalization, because the capability to acquire a guarantee of invocation can already be separately provided by finalization.

Here we have different views on what's fundamental, a primitive, and what is not. This is basically like in math where you pick different axioms to build theorems upon.

In the Scalaz 8 IO model you chose bracket as the primitive. In the Cats-Effect model on the other hand, bracket can be derived from the other operations. The cancelable callback that gets called is in charge of interruption and can be used for finalization, but it manages interruption. And you have it too in Scalaz 8, in your own async builder, although you've got a different signature.

But to get back to the point, with Cats-Effect's IO, this is how bracket can be built, not the current implementation, but just for didactic purposes and note we can throw some uncancelable calls in it to make it behave just like Scalaz's one, plus we handle errors in release to still promote the original error, not shown here:

def bracket[A, B](acquire: IO[A])
  (use: A => IO[B])
  (release: (A, ExitCase[Throwable]) => IO[Unit]): IO[B] = {

  acquire.flatMap { a =>
    use(a).onCancelRaiseError(wasCanceled).attempt.flatMap {
      case Right(a) => 
        release(a, Complete).map(_ => a)
      case Left(`wasCanceled`) => 
        release(a, Canceled(None)) *> IO.never
      case Left(e) => 
        release(a, Error(e)) *> IO.raiseError(e)
    }
  }
}

So in our case the primitives are actually the cancelable builder and onCancelRaiseError.

And to make things clear, in this model only cancelable nodes can be canceled, but not the flatMap chains that bind them. This puts the user in control of how cancelation happens and is a more flexible model than just having bracket.

We may agree to disagree on this one, but certainly there are people that find auto-cancelable chains useful, like @oleg-py here who is a big fan 🙂 so let's find a middle ground, lets provide an uncancelableBinds operation, as otherwise I see no way to support both approaches and I really, really want to have both approaches to cancellation.

[jdegoes]

IO.unit.flatMap(_ => IO.cancelable(_ => IO(println("Cancelled!")))
  .uncancelableBinds
  .start
  .flatMap(_.cancel)

You want a guarantee of two things:

1. The cancellation occurs only during IO.cancelable, i.e. _cancellation boundaries_.
2. The canceler will always be invoked should cancellation occur.

This is why I keep saying it conflates two things: it conflates cancellation (1) with finalization (2).

This is not an orthogonal design, because you can imagine a different design which separates (1) from (2). That is, a design which allows you to make actions cancelable, and which also allows you to add finalizers, and from these two capabilities, you can create a combinator to run some action if and only if another action is cancelled (e.g. io.onCancellation(action), to mirror onError).

Could Scalaz's IO provide this behavior? I may be biased, but in Monix's Task implementation, the difference is made by a boolean flag checked by an if on async boundaries, that can be turned on or off.

Yes, it's possible. It would require a change to semantics (always cancel on async boundaries) or the introduction of a cancellation boundary in the algebra.

What is the benefit of this type of cancelation? It is only a wrapper around Ref[Boolean] and checking to see if execution should continue or not. It's possible to define these things simply:

IO.startCancelable { implicit c: Ref[Boolean] => 
  for {
    _ <- IO.unit 
    _ <- IO.cancelBoundary(_ => IO(println("Cancelled!")))
  } yield ()
}.flatMap(_.cancel)

This is user-land cancellation, just disguised. There's no reason to bake it into IO, in my opinion. OTOH, something like interruption, that can and must be baked in, because only the RTS can do it.

We may agree to disagree on this one, but certainly there are people that find auto-cancelable chains useful, like @oleg-py here who is a big fan 🙂 so let's find a middle ground, lets provide an uncancelableBinds operation, as otherwise I see no way to support both approaches and I really, really want to have both approaches to cancellation.

Interruption is proven in Haskell and PureScript, and is in the process of being proven in Scala, and is already supported (in a different way) in Monix (via auto-cancellable run loops). Cancellation, OTOH, is a user-land feature that doesn't need to be baked into an API or type classes.

If we want both options, then perhaps it is best to design the type class for interruption, then with an uninterruptible combinator and user-land cancellation (which is all cats-effect cancellation is, it just hides a bit of boilerplate), users can achieve either semantic: either fine-grained interruption or user-land cancellation.

[oleg-py]

I have to be going soon, but the ideas I have in my head are still quite rough. Sorry if I didn't explain it all well. I'll think this over more thoroughly later, but these are important points:

I want doOnInterrupt as a pure version of .cancelable, which can execute the action concurrently (if possible, based on the data type). So, given Concurrent[F]:

F.never.doOnInterrupt(action).start.flatMap(_.cancel) <-> action.uncancelable

(I don't remember if never is uncancelable or not... I'm assuming it is).

I was wrong about the possible Iterant implementation - it would likely require a cooperation from F.doOnInterrupt too, but it should be possible.

@jdegoes is right about interruption/finalization conflation. I have a feeling that IO.cancelable can be implemented with IO.async, bracket, an IO.cancelBoundary and maybe a Ref. Which would mean the simplest primitive we can have is cancelBoundary - and scalaz has this for free with auto-cancelable binds.

I think uncancelableBinds still overrides too much from Fs provided by user, just like an uncancelable does. In which case expressing a single uncancelable bind is what we want, without overriding stuff deep down the chain. Maybe such bind is not a primitive, again, and can be expressed with a Ref or a Deferred

[edmundnoble]

@oleg-py From what I remember, what we discussed is that if you don't provide cancellation at all through type classes, just bracket, then you can keep cancellation as an implementation detail of bracket.

[alexandru]

@jdegoes is right about interruption/finalization conflation. I have a feeling that IO.cancelable can be implemented with IO.async, bracket, an IO.cancelBoundary and maybe a Ref. Which would mean the simplest primitive we can have is cancelBoundary - and scalaz has this for free with auto-cancelable binds.

First of all, Ref or any other similar type isn't a primitive. If you want to demonstrate something, it cannot include Ref or MVar or Deferred, because doing so introduces a circular dependency. As I already showed, bracket itself is implementable in terms of onCancelRaiseException, so in this model bracket isn't a primitive. You can choose a model in which bracket is the primitive and this is what Scalaz 8 does, but it's not a good argument, because it's like arguing in math which set of axioms is better.

I strongly disagree about interruption/finalization conflation. If you go back to the original IO implementation, in order to describe cancelable things with it that worked in race conditions, people had to describe functions with this signature (where IO[Unit] represents the cancelation token):

IO[(IO[A], IO[Unit])]

Cancelability is nothing more than having the ability to carry that cancelation token around, implicitly (aka without having it infect your whole code-base) and also the ability to do this:

IO[A] => IO[(IO[A], IO[Unit])]

You may recognize this as the signature of start. Here's some facts:

1. this is not finalization, although it can be used for finalization
2. it's safe and it is the simplest possible design that works for cancelation, because other designs require magic(TM) and note that I'm using simple here to mean the opposite of entangled/intertwined and simple usually wins 😉
3. most importantly, this simplicity keeps the spirit of the project alive and I invite you to read Daniel Spiewak's opinions on it here: https://github.com/typelevel/cats-effect/issues/93#issuecomment-349720286

Personally I don't want to debate which model is better, because for the use-cases I care about the Cats-Effect model is better and I want this model to work. So Cats-Effect will not be changed to do auto-cancelable run-loops for as long as my vote on it counts.

I do agree to leave the door open for auto-cancelable run-loops in the type classes, like my uncancelableBinds proposal that I mentioned, but anything beyond that is a tough sell.

N.B. I'm slightly aggressive in tone because I've got a presentation to prepare, haven't finished and only have 1 hour left, plus I feel pressure on not delivering Cats-Effect 1.0.0-RC2, let alone 1.0.0. Sorry about that — you know I appreciate your feedback and work.

[jdegoes]

F.never.doOnInterrupt(action).start.flatMap(_.cancel) <-> action.uncancelable

You don't really want this. 😄 You want finalization:

F.never.ensuring(action).fork.flatMap(_.interrupt) <-> action

EDIT: ensuring is just derived from bracket and involves no new functionality.

This law is already satisfied by Scalaz 8 IO. If you want to know if F.never completed from within your finalizer, you can just use bracket.

No new functionality is needed.

More later. Must cook dinner. 🍔 😄

[oleg-py]

You don't really want this. 😄 You want finalization

I'm pretty sure I don't. I want action to execute ASAP, concurrently, if allowed by F[_]. Finalization cannot be concurrent (or we have a terminology mismatch)

[jdegoes]

I'm pretty sure I don't. I want action to execute ASAP, concurrently, if allowed by F[_]. Finalization cannot be concurrent (or we have a terminology mismatch)

Orthogonality FTW:

F.never.ensuring(action.fork.toUnit).fork.flatMap(_.interrupt) <-> action

Any time we add a new method to a type class we should seriously ask ourselves the question: is the design of our API truly composable and orthogonal? Because every time we need to add something new, it's a sign the design is _not_—and the more we have to add, the stronger the sign.

Instead of bolting on more ad hoc functionality onto a type class, we should holistically rethink the entire design and consider: what are the minimum number of orthogonal primitives necessary to compose the full set of ad hoc use cases?

In my opinion, this is not being done currently in cats-effect, which is why type classes and methods are growing and resulting in an increasingly conflated and complicated design.

The budget should be, say, N type classes with M methods, and the goal should be to spend it so wisely, we do not regret our choices.

[jdegoes]

First of all, Ref or any other similar type isn't a primitive. If you want to demonstrate something, it cannot include Ref or MVar or Deferred, because doing so introduces a circular dependency.

This argument is not compelling to me. Circular dependencies, like mutual recursion or Scalaz 8 IO's interpreter (which is mostly written in IO), can sometimes be incredibly useful ways to build software by reducing repetition.

Ref is more primitive than cancelation. The reason for this is that Ref is nothing more than a variable (with CAS), which is fundamental to effectful computation. However, cancelation does not need to exist and can be layered on top of IO, even using the same API, by building the feature in terms of a more primitive IO and a Ref.

You can choose a model in which bracket is the primitive and this is what Scalaz 8 does, but it's not a good argument, because it's like arguing in math which set of axioms is better.

I agree bracket is not the only choice of primitive.

1. this is not finalization, although it can be used for finalization

The fact that you can use cancelation for finalization indicates a conflation of responsibilities. As a basis for the API, it's non-orthogonal. I have showed to Oleg how you can achieve his desired semantic using an orthogonal basis. Other things being equal (and I think in this case they are), I personally prefer orthogonal bases for functional API design.

1. it's safe and it is the simplest possible design that works for cancelation, because other designs require magic(TM) and note that I'm using simple here to mean the opposite of entangled/intertwined and simple usually wins 😉

Cancelation is user-defined termination condition checking with guarantees of uninterruptibility, similar to the old-school way of writing if (shouldContinue.get) as a way of "cancelling" long-lived tasks.

This functionality can definitely be useful, but only in the absence of interruption (because it represents a subset of the capabilities of interruption), and it can be layered onto a simpler monad without loss of any functionality or even performance, so it's not primitive.

Interruption does not require any magic, and it's already proven itself in other ecosystems.

1. most importantly, this simplicity keeps the spirit of the project alive and I invite you to read Daniel Spiewak's opinions on it here: #93 (comment)

The spirit of the project is already dead as cats effect continues to rapidly acquire half-baked versions of features in Monix Task (e.g. race, par) in a spiral of increasing complexity and size—in addition, of course, to features like fibers, concurrency, and cancellation, which Daniel campaigned against.

The way to revive the spirit of the project is to focus it on type classes only, which a few simple changes will permit. Then users can choose their data type independently of cats-effect.

N.B. I'm slightly aggressive in tone because I've got a presentation to prepare, haven't finished and only have 1 hour left, plus I feel pressure on not delivering Cats-Effect 1.0.0-RC2, let alone 1.0.0. Sorry about that — you know I appreciate your feedback and work.

You are the maintainer of cats-effect at this point. IMO I have zero say in any decision in this project, and you alone get to decide its future, because you are doing the hard work necessary to keep it alive. If you like cancelation the way it is designed now, then keep it.

Personally, I do think you would be free to work much more on Monix Task if the IO data type were removed from cats-effect, and the project refocused on type classes.

But do as you please and I will support you because you are an incredible asset to the Scala community and have improved the way countless companies write Scala. 💪

[oleg-py]

Ok, here's how the things look from my POV:

Things we need to do

• We need to be able to express guarantee of uncancelability given Sync alone. Doing Alternative[Concurrent[F], Sync[F]] in fs2 will break in subtle ways if we go for changes added in #232. So we move one method down the line, and data types get to choose where they are cancelable or not. Bracket might be a good place to start, as this is the first typeclass that introduces a notion of cancellation.

• Add an ability to register a concurrent finalizer and probably require these semantics. It can be added as a law on how Concurrent treats bracket, no extra methods required.

  • Given this change, cancelable would be effectively "demoted" from being a primitive, as we would be able to do something simliar to (shortened for brevity):

def cancelable(f: (Try[A] => Unit) => IO[Unit]): F[A] = {
    F.delay(new ObjectRef[F[A]](F.unit)).bracketCase { ref =>
        F.async(cb => ref.elem = liftIO(f(cb)))
    } {
        case (ref, Cancelled) => ref.elem // now will be executed concurrently :)
        case _ => F.unit
    }
}

cancelable should still remain a builder for the common use-case of wrapping impure libraries.

• Fix lack an ability to write a code parametric in F[_] that would allow cancellation without stepping into impure side. For this, we might want to add a cancelBoundary operation somewhere. Not sure if it can have laws.

Things we need to think about

• Assuming cancelable binds, how do we reformulate the laws such that they still work? Do we really need extra primitive(s) or things can be expressed differently using existing ones (I hope they can?).
• How can we remove "some" of cancelability in places we need things to be uncancelable? For example, maybe we can work with F[F[A]], which would be an uncancelable program that evaluates to a cancelable program.

[alexandru]

@oleg-py so my problem is that making uncancelable available in Sync doesn't fix the problem for Iterant. For one, because in the current Cats-Effect model, we only need uncancelable in very specific instances.

Here we actually have a symptom of introducing auto-cancelable bind loops btw — to write polymorphic code, you now need to infect the whole type class hierarchy with notions of cancelation.

Forget Sync, the actual problem is that a Monad constraint is no longer just a Monad constraint, because now you need to worry about what F[_] might be, so you need to mark portions of code with uncancelable in the event that F[_] doesn't actually behave like a Monad and therefore might break your code.

for {
 r1 <- task1
 r2 <- task2
} yield ()

With a Monad you are guaranteed that task2 executes after a successfully completed task1.
With a auto-cancelable F[_] surely we can work around this with bracket, but it's no longer behaving like a Monad would.

And we cannot write laws in MonadLaws to protect against it either, because Monad isn't aware that auto-cancelable F[_] data types can exist and if you want some laws to protect against this, you basically need MonadPlusUncancelable, which makes no sense.

In Iterant we are describing most operations with Sync only because Sync is the Monad that guarantees laziness and a stack safe flatMap. But we feel the need for doing that only because of Scala's eager evaluation model. If it weren't for that, many operations could have been described only with Monad. Heck, the concat (aka ++) operation could be described with Applicative only.

Auto-cancelable flatMaps are breaking the whole Functor hierarchy 😉

[alexandru]

Also, just to make it clear, I do not buy the conflation / orthogonality argument.

Haskell is a poor prior art for this, we are in uncharted territory, because Haskell basically works with a single IO data type and AFAIK they aren't building many libraries that abstract over the effect type. I only played with Haskell, but besides some existing attempts at producing an "unexceptional IO" type, plus some early bifunctor IO experiments (probably), I haven't seen much on their end.
Solutions in Haskell land are basically specialized for IO and workaround its limitations.

With Monix's Iterant, FS2, Http4s, Doobie and in the Typelevel ecosystem, we might actually have more progress in abstracting over the effect type — I might be awfully wrong of course, but couldn't find much evidence when I looked for prior art (except for some efforts in PureScript's ecosystem).

So personally I do not want to modify the laws as to admit auto-cancelable flatMaps.
I'm only willing to do that, if you can describe an Iterant that's still safe to process with a simple flatMap-based fold.

As mentioned in my comment above, which has concerns that haven't been addressed yet, I want this to work:

def makeCancelable[F[_] : Sync, A](stream: Iterant[F, A])
  (implicit F: Sync[F]): Iterant[F, A] = {

  def prepare(rest: F[Iterant[F, A]], stop: F[Unit]): F[Iterant[F, A]] =
    F.bracket(rest) {
      case ExitCase.Canceled(_) => stop
      case _ => F.unit
    }

  stream match {
    case Next(a, rest, stop) =>
      Next(a, prepare(rest, stop).map(makeCancelable), stop)
    case Suspend(rest, stop) =>
      Suspend(prepare(rest, stop).map(makeCancelable), stop)
    case Halt(_) =>
      stream
  }
}

If this cannot work, remember that we're dealing with polymorphic code, we're dealing with the Functor hierarchy and map and flatMap were also meant for describing such recursive data types and if we can't rely on functors to behave like functors, then we don't have a very useful type class hierarchy.

So if we cannot address this use-case, my vote on this matter will be no, the Cats-Effect type class laws stay as is.

[oleg-py]

@alexandru I took a shower 😃 and it occurred to me that, uh, we can't really describe such flatMap-based folds even if we forgo cancelable binds. In particular, there's a wonderful Sync instance...

import cats._, data._, syntax.all._
import monix.eval._ // RC1
import monix.tail._

type F[A] = OptionT[Coeval, A]

Iterant[F].bracket(1.pure[F])(
  _ => Iterant.liftF[F, Int](OptionT.none[Coeval, Int]),
  _ => OptionT.liftF(Coeval{println("Clean up complete")}))
.completeL
.value() // prints nothing, returns None

[jdegoes]

@oleg-py

My general philosophy here: If you require non-cancelability (or non-interruption) for any segment of code in order to ensure safe release of resources, then in the presence of a defect in this code that terminates execution, you will leak resources and bring servers down. That said, Scalaz 8 has an uninterruptible combinator anyway, but if it's used to "prevent" leaks, it's still subject to these caveats and will not succeed in this goal.

Bracket might be a good place to start, as this is the first typeclass that introduces a notion of cancellation.

Finalization is the most important concept here, and it applies regardless of cancelation or interruption. Any code dealing with resources — which pretty means any effectful code at all — must have the ability to express finalization. This means the base of the hierarchy cannot simply be something like monad error (try / catch), but must include finalization (try / catch / finally).

Once effectful code is designed to rely on finalization for cleanup of resources, then all problems with defects, cancelation, and interruption disappear.

Of course, it's easier to assume code will never be terminated by defect, cancellation, or interruption. That it's easy to write incorrect code is not a reason for writing it.

Add an ability to register a concurrent finalizer and probably require these semantics. It can be added as a law on how Concurrent treats bracket, no extra methods required.

Since one can easily turn a finalizer into a concurrent finalizer with a single call to .fork (/.start), you may not need new functionality.

Given this change, cancelable would be effectively "demoted" from being a primitive, as we would be able to do something simliar to (shortened for brevity):

I think this is a wonderful design goal. 👍

[alexandru]

@oleg-py that issue is a different one and would require a separate discussion.

[jdegoes]

@alexandru

With a Monad you are guaranteed that task2 executes after a successfully completed task1.
With a auto-cancelable F[_] surely we can work around this with bracket, but it's no longer behaving like a Monad would.

This is completely incorrect. Take the following snippet of code:

for {
 r1 <- task1
 r2 <- task2
} yield ()

In neither Haskell nor Scala, Monad does not guarantee that task2 will ever be executed. In fact, there are many ways — beyond interruption and finalization — that it may fail:

1. The monad may have an explicit notion of failure, which means that task1 may fail and shortcircuit task2. Monads with notions of failure do not "break the functor hierarchy" because Monad by itself provides absolutely no guarantee of execution. _Any code relying on a non-existent guarantee is by definition incorrect_.
2. Because neither Haskell nor Scala are total languages, task1 may run forever, which means task2 may never be invoked. In fact, task1 may be polymorphic in the type of value produced by the computation, so you can have compile-time proof that it will never complete.
3. Also because of partiality, any functions — including flatMap, or the lambdas passed to flatMap — may throw exceptions / errors, which will prevent task2 from being executed. This applies whether or not you "catch in map/flatMap". You can auto-catch, but you can't auto-resume.

Treating Monad as a guarantee that every operation in a chain of flatMaps will be executed is completely incorrect, not guaranteed by any laws, and will result in broken code.

And we cannot write laws in MonadLaws to protect against it either, because Monad isn't aware that auto-cancelable F[_] data types can exist and if you want some laws to protect against this, you basically need MonadPlusUncancelable, which makes no sense.

Again, totally false for the above reasons.

Also, just to make it clear, I do not buy the conflation / orthogonality argument.

As far as I can see, everyone who has looked at this design agrees cancelation conflates finalization and cancelation. This is a non-orthogonal design. If you want cancelation (Cats-Effect-style cancellation, not Scalaz 8 interruption), there are ways to achieve it in an orthogonal design, and I am happy to help sketch one out. But the current design is definitely not orthogonal.

if we can't rely on functors to behave like functors, then we don't have a very useful type class hierarchy.

Your understanding of the functor hierarchy is not correct. There are no guarantees of continued execution with Monad, as demonstrated by trivial monads such as Option.

So if we cannot address this use-case, my vote on this matter will be no, the Cats-Effect type class laws stay as is.

I'm good with that. 👍 But please do not say this is because Monad provides a guarantee of continued execution, because this is completely false and will confuse people learning functional programming and reading this thread.

[oleg-py]

@oleg-py that issue is a different one and would require a separate discussion.

I pointed it out because I believe it's the same issue in spirit, and has to do with:

With a Monad you are guaranteed that task2 executes after a successfully completed task1.

Monad is just a computational effect that satisfies 3 laws, and you don't get more guarantees than monad laws. There are monads that have no reasonable notion of "unsuccessful" completion at all: Id, Const[Unit, ?], Eval and NonEmptyList, to name a few.

With Iterant, we assumed that Sync[F] means that F behaves like IO, whereas it is not necessarily so. So in my sample Coeval has an effect of performing synchronous IO and OptionT adds a second one, so now you have a tri-state: Coeval completed with Some(a), in which case flatMap executes, Coeval failed with an exception, in which case handleErrorWith executes, and Coeval completed with None, in which case neither of these happen. We introduced bracket as a primitive because we came to conclusion that it cannot be expressed as a combinator, counterexample by @tpolecat being OptionT-based as well.

With bracket, we have more guarantees than MonadError gives us, so we can safely manage resources even in OptionT[Coeval, ?], which means bracket must be used if we want to achieve resource safety.

In the similar way as OptionT, cancelable binds bring another effect on top of "Concurrent IO" we have in cats.effect.IO, with rules similar to OptionT, except with a grain of nondeterminism.

Let's get to Monix Task that is auto-cancelable - I listed the failing tests in this Monix issue, but note they are all Concurrent tests, so Task with cancelable binds is still a valid Sync!. Or, more generally, there can exist valid Sync instances which don't have that guarantee of execution (so no, it's not solved by removing an option in Monix).

Which means either it is supported in Iterant, or F[_]: Sync required in it is a lie, and you need a constraint that doesn't exist in cats-effect.

---

Since one can easily turn a finalizer into a concurrent finalizer with a single call to .fork (/.start), you may not need new functionality.

My concern was the ability to say, by having only Sync constraint: "Hey F, if you're always synchronous, you can do nothing, but if you just so happen to be concurrent, perform this", whereas with .start I need to limit myself to Concurrent types directly. Granted, it's a bit of a band-aid solution to the fact that we have Concurrent <: Sync, but probably the easiest to implement, so I'd go for this to have 1.0 release sooner and if necessary, reconsider it later.

[alexandru]

@oleg-py

With bracket, we have more guarantees than MonadError gives us, so we can safely manage resources even in OptionT[Coeval, ?], which means bracket must be used if we want to achieve resource safety.

You're missing the forest from the trees. The general culprit in this case is our use of MonadError and in general the fact that handleErrorWith or attempt do not expose OptionT's None or EitherT's Left is a problem that has bitten users before and not just in code that deals with side effects or finalization.

We also have a symptom of this in Effect's instances, because in order to support a generic L in the Effect[EitherT[F, Throwable, ?]] instance, we'd have to convert L to Throwable. Which is something that MonadError should support.

def onLeftRaiseError[A](fa: F[A]): F[A]

If we added something like this on MonadError[F, E], it would solve the problem 😉

[oleg-py]

def onLeftRaiseErrorA: F[A]

Uh-oh, what's that gonna do for plain old Either[String, ?]?

But yeah, if you wanna go this route, call it onCancelRaiseError, push it down to Bracket and treat Left/None as cancelled. Problem solved? 😄

[alexandru]

That was just an off the top of my head solution.

Another solution would be of course to work with bracket. I just tested it, it works, but again, only in the Cats-Effect model.

[alexandru]

Update — investigation is in progress: https://github.com/monix/monix/issues/676

[rossabaker]

This ticket begins with "drop laws like this that guarantee non-interruptibility," but I only see one mentioned by name. Does anyone have a precise list of laws proposed for repeal?

[alexandru]

Some laws under investigation are the ones signaled as failing when Monix Task's autoCancelableRunLoops is active in https://github.com/monix/monix/issues/665:

- Concurrent[Task].concurrent.onCancelRaiseError terminates on cancel
- Concurrent[Task].concurrent.race cancels both
- Concurrent[Task].concurrent.race cancels loser
- Concurrent[Task].concurrent.racePair cancels both
- Concurrent[Task].concurrent.racePair cancels loser
- ConcurrentEffect[Task].concurrentEffect.onCancelRaiseError terminates on cancel
- ConcurrentEffect[Task].concurrentEffect.race cancels both
- ConcurrentEffect[Task].concurrentEffect.race cancels loser
- ConcurrentEffect[Task].concurrentEffect.racePair cancels both
- ConcurrentEffect[Task].concurrentEffect.racePair cancels loser

[jdegoes]

Also: @jmcardon may have more.

The Sz8 backport has instances for cats-effect; but tests are disabled for concurrent / concurrentffect.

[jmcardon]

IIRC basically all of the laws that had to do with cancellation (so the ones @alexandru pointed out) are the ones that failed.

[rossabaker]

237 revises the laws so ConcurrentEffect[monix.eval.Task] passes when its auto-cancelable run loop is enabled.

[alexandru]

Awesome 👏