Proposal: Continual (type class?)

[alexandru]

Given the ongoing saga with #192, here's a summary of the problem:

1. The LazyList sample: https://gist.github.com/alexandru/b970186208d1c1378c903d43588bd6a7
2. Comparison of bracket with mutexes: Proposal: Continual (type class?) #242

So I propose the following addition ...

trait Bracket[F[_], E] {

  /**
   * Ensures that any binds (flatMaps) describing `F[A]` are not cancelable, changing
   * its evaluation model.
   * 
   * Example:
   * {{{
   *   for {
   *     _ <- F.unit.bracketCase(_ => task1) { case (_, Cancelled(_)) => release1 }
   *     _ <- F.unit.bracketCase(_ => task2) { case (_, Cancelled(_)) => release2 }
   *   } yield ()
   * }}}
   * 
   * When evaluated under `continual`, under cancelation, the user gets a guarantee that
   * either `release1` or `release2` will get evaluated and so that interruption cannot happen
   * in between the two tasks.
   * 
   * This is unlike [[uncancelable]], providing a weaker guarantee, but that changes the 
   * evaluation model such that interruption logic can be distributed among multiple "nodes"
   * in the bind chain.
   */
  def continual[A](fa: F[A]): F[A]
}

Also as an alternative, we could describe a separate type class that would work as a marker:

@typeclass trait Continual[F[_]] {
  // Using composition, b/c it needs to be optional and inheritance 
  // would ruin our hierarchy
  val monad: Monad[F]

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

And then in signatures this would be relevant for folds:

def completeL[F[_] : Sync : Continual, A](stream: Iterant[F, A]): F[Unit]

UPDATE at 2018-05-25 10:49: So given this:

val task1 = F.bracket(acquire1)(use1)(release1)
val task2 = F.bracket(acquire2)(use2)(release2)

task1.flatMap(_ => task2)

Within the continual model you get a guarantee that if task1 has completed successfully, then task2 and thus release2 will get evaluated, no matter what. task2 can still get cancelled while being evaluated, however you cannot get an interruption that happens in between task1 or task2.

The Concurrent laws wouldn't be unlike what we have now:

val lh = for {
  ref <- Deferred[F]
  fiber <-F.unit.flatMap(_ => F.bracket(F.unit)(_ => task)(ref.complete)).start
  _ <- fiber.cancel
  _ <- ref.get
} yield ()

lh.continual <-> F.unit

Basically under the auto-cancelable binds model, this should fail, but continual would make it succeed. And we need it at least on Sync because for implementations like Monix's Coeval or cats.effect.IO it can just be the identity function, as they already are "continual".

For Monix's Task on the other hand this operation would involve task.executeWithOptions(_.disableAutoCancelableRunLoops), which would work fine.

Motivation

Copy-pasted:

Changing these laws is in fact the biggest breaking change we've ever made, invalidating the MonixIterant encoding, something that no version managed to do ever since Cats-Effect was created. And if Iterant breaks, then so can other code, also invalidating the original philosophy of the project, which shouldn't be taken lightly.

Auto-cancelable bind loops are not optional. Once in, it changes what polymorphic code can do. In particular code that works for non-async abstractions, like Eval, Coeval or a future SyncIO will be invalid. Again, see Iterant.

It is also clear to me though that auto-cancelable bind loops should be considered the default in the type class hierarchy, because code described for auto-cancelable bind loops tends to work for code described without.

With this change, code still breaks, however at least it provides a way forward for projects that want to use this model.

UPDATE at 2018-05-25 10:49: Also commented below:

The role of the type classes is to support other implementations. We don't want just cats.effect.IO, or just scalaz.effect.IO or just monix.eval.Task. We want all of those and more, which is why I personally was open to support Scalaz's new IO, hence all this pain.

But to be more concrete, Monix, Cats and Scalaz do not have the only implementations of IO on top of the JVM. There are other implementations that may end up supporting our type classes. For example the entire ReactiveX ecosystem (e.g. RxJava, RxJS, etc), which have been doing their own thing. RxJava for example has Single which is an IO monad, well not sure if it passes our laws, but if it has a stack safe flatMap then we should support it.

And I can tell you that Single's cancelation model is that of the current Cats-Effect, much like the rest of ReactiveX. Which is significant because ReactiveX is massively popular, more popular than Akka, Cats and Scalaz combined, and I know that Kotlin's Arrow for example is providing type class instances for them.

[alexandru]

Must say that a problem is that I'm the only one currently campaigning for this or with an understanding that auto-cancelable binds fundamentally changes the behavior of polymorphic code and rendering certain techniques impossible.

One one hand, if I have such a hard time explaining this to the other contributors, it might get really confusing for users and that's a big problem.

On the hand I feel like I'm losing my mind. I can't be the only one noticing the huge difference and breakage.

[rossabaker]

In the first example, MonadBracket is Bracket, not a new type class?

This would coexist with #237, so auto-cancel run loops could be lawful Concurrent?

[jdegoes]

This type class seems to exist so that Iterant can assume (or obtain) guarantees of non-interruption, so that it does not have to use bracket for resource management.

Yet bracket exists for resource management. In fact, it must be used for resource management. Any effectful code which acquires resources and does not use bracket is incorrect.

Rather than modifying cats-effect type classes because of bugs in downstream libraries, doesn't it make more sense to fix those bugs?

[alexandru]

@rossabaker

In the first example, MonadBracket is Bracket, not a new type class?

Yes. Made a mistake.

This would coexist with #237, so auto-cancel run loops could be lawful Concurrent?

Yes. What this would do is to turn auto-cancelable run loops off (or in case of our IO implementation or in case of a future SyncIO or Coeval, this would just return the source since there's nothing to disable).

And it would also re-add the laws that we are changing. So the current laws that are failing in Concurrent would still be in effect when a continual call is involved.

Also important to mention:

• if we add it in Bracket, we're forcing Scalaz's IO and other implementations to implement the behavior
• a separate type class would be optional, but would complicate the signatures I guess

[alexandru]

@jdegoes these are only bugs if you follow the world view that only your solution is the correct one.

It cannot be a bug if the behavior was well defined from the beginning, even before Scalaz 8's IO existed.

Also, I would prefer if we wouldn't start a debate on 3 or 4 separate threads.

[jdegoes]

Is MonadBracket the way users write code which safely releases acquired resources?

1. If Yes: Then downstream libraries that do not use MonadBracket, but expect to safely release acquired resources, are buggy and must be fixed.
2. If No: Then MonadBracket is neither necessary nor sufficient for resource safety, and should be deleted from cats-effect.

In my opinion, consistency mandates either (1) or (2). I believe (1) is correct, but I think (2) is consistent as well (if not desirable, IMO).

[alexandru]

Neither of those claims is true, because in fact there's an option 3 ...

Going to point yet again to my sample at #192 (comment) — and in particular the makeCancelable function, which relies on the current model, but that does rely on bracket as well.

[alexandru]

I've also added that sample in my summary here: https://gist.github.com/alexandru/b970186208d1c1378c903d43588bd6a7

[jdegoes]

Option 3 is not a good option, in my opinion.

Option 3 suggests a library user who does not wish to use bracket for resource safety, because it's too much effort, can achieve it through a separate route: namely, writing their code under the assumption that "binds won't be interrupted" if they call a poorly-specified continual combinator.

This alternate pathway to achieving "resource safety" exists solely because of a bug in Iterant: namely, the fact that it assumes resource safety without using bracket.

Note that it is impossible to implement continual for monad transformers like OptionT and EitherT, since the very feature they add is "bind interruption". Worse, even if you specify that continual cannot "interrupt binds", this does not imply resource safety for reasons I've written about in #192.

For example, IO(???) placed between two operations, causes termination of the fiber, or at least stack unwinding to the closest attempt, which means that even for monads which can implement continual, you have zero guarantee of resource safety if the code is not written to use bracket. Only bracket can provide resource safety in these cases and others.

Note also that interruptible binds are by no means the only way to provide interruption. For example, Scalaz 8 IO will interrupt async operations that have not completed, even if they have no canceler, by discarding their results upon completion; which allows, among other things, a law stating that never can be interrupted. This is not "bind interruption", it's "async interruption". One can imagine numerous other kinds of interruption, such as forcibly calling Thread.interrupt for blocking sync code, which will terminate fibers and leak resources not acquired through bracket, even with continual.

The fact that Option 3 does not actually provide any guarantee of resource safety (in fact, it's guaranteed that code using continual will leak resources in many cases), it's ad hoc and targeting a specific bug in Iterant, it is incompatible with common monad transformers, and it has only considered a single type of interruption (binds), means that—in my opinion—it is not a good option.

[alexandru]

Option 3 suggests a library user who does not wish to use bracket for resource safety, because it's too much effort

John, now you're doing user profiling, invoking laziness. That's not a good argument.

There is an Option 3 and Cats-Effect's IO is in fact not the only one with this cancelation model and I'm not speaking of Monix. So first of all, such a decision (i.e. to base all resource release on bracket) is restricting the polymorphic code that users can write or the types that implement these type classes.

Note that it is impossible to implement continual for monad transformers like OptionT and EitherT, since the very feature they add is "bind interruption".

Not really the same thing, plus this is why we are talking of Option 3 — because you can still work with bracket where it makes sense.

forcibly calling Thread.interrupt for blocking sync code, which will terminate fibers and leak resources not acquired through bracket, even with continual

I've been looking at handling InterruptedException actually and somehow I doubt that you're dealing with it correctly in Scalaz. Also a user the other day asked me why doesn't bracket call release after he killed the thread pool underneath it in use.

You're attributing too many qualities to bracket to be honest.

[jdegoes]

There is no way to write resource safe code without bracket (or something equivalent) and any attempt at providing ad hoc workarounds like this will fail to achieve the intended goal and lead to numerous other problems as specified above.

Well, I've said my 2 cents, I don't really have anything more to say on this issue.

I've been looking at handling InterruptedException actually and somehow I doubt that you're dealing with it correctly in Scalaz.

InterruptedException should terminate the fiber and cleanup resources, like any exceptions thrown from pure code. However, there's no test case for this, something I do intend to rectify shortly.

[alexandru]

Well, I've said my 2 cents, I don't really have anything more to say on this issue.

Right, I think we've already said everything in #192.

[rossabaker]

I have an open PR that proposes breaking changes the laws, but I don't find it fair or constructive to call constructs that pass the currently published laws as a "bug." We should be able to discuss the ramifications of these alternative designs without denigrating the work that was lawful when written.

[jdegoes]

@rossabaker

Take your pick: Either it’s a bug to assume resource safety without MonadBracket, or MonadBracket is not useful. See my original comment on the issue.

If the former, the (broken) laws reflect a latent contradiction between the intent of the MonadBracket type class and assumptions made elsewhere. i.e. both laws and downstream software are defective with respect to the intent of MonadBracket.

These things happen. Especially with complex hierarchies and when pushing new ground in abstracting over effect types. There’s no need to make a big deal of them or take them personally.

Identification of bugs (if indeed that’s what this behavior is) is not denigration. Alex suggested Scalaz has a bug with respect to InterruptedException, which is not denigration but extremely useful information that can be used to improve the quality of software.

[alexandru]

@jdegoes

Take your pick: Either it’s a bug to assume resource safety without MonadBracket, or MonadBracket is not useful.

We have to agree to disagree here.

Note that my proposal is not changing Scalaz, but to find a way to keep supporting the current evaluation model while fixing the laws to allow for Scalaz's model and Continual is the best I could come up with.

Note that the role of the type classes is to support other implementations. We don't want just cats.effect.IO, or just scalaz.effect.IO or just monix.eval.Task. We want all of those and more, which is why I personally was open to support Scalaz's new IO, hence all this pain.

But to be more concrete, Monix, Cats and Scalaz do not have the only implementations of IO on top of the JVM. There are other implementations that may end up supporting our type classes. For example the entire ReactiveX ecosystem (e.g. RxJava, RxJS, etc), which have been doing their own thing. RxJava for example has Single which is an IO monad, well not sure if it passes our laws, but if it has a stack safe flatMap then we should support it.

And I can tell you that Single's cancelation model is that of the current Cats-Effect, much like the rest of ReactiveX. Which is significant because ReactiveX is massively popular, more popular than Akka, Cats and Scalaz combined, and I know that Kotlin's Arrow for example is providing type class instances for them.

Also replied to @pchlupacek on another thread with another explanation of the difference, made another gist:

https://gist.github.com/alexandru/a23790f4da9ec46f9eee722416e20cd7

Note how we still rely on bracket, except that you can then rely on composing two brackets referring to an outer resource.

[SystemFw]

Re: the latest gist.

You are stumbling into the exact problem fs2 solves with Scopes, and more generally in Haskell/literature with RegionT/ResourceT/Managed.
Yes, locks don't compose, but the answer to that imho is not demanding more guarantees from your memory model, but building an abstraction over them that does compose (this is what STM does, for example).
And similarly, the answer to this problem imho is not assuming that binds can't be cancelled, but rather build an abstraction that can express the concept of a region of composed brackets (Scope/ ResourceT / CrazySuperFastMonixOne :) )

[alexandru]

You are stumbling into the exact problem fs2 solves with Scopes, and more generally in Haskell/literature with RegionT/ResourceT/Managed.

Yes, and @oleg-py and myself are investigating an alternative encoding.

Yes, locks don't compose, but the answer to that imho is not demanding more guarantees from your memory model, but building an abstraction over them that does compose (this is what STM does, for example).

Actually the right answer is to avoid synchronization altogether. STM is great when you're forced to do synchronization, but STM is terrible too: it's unpredictable, it has awful performance and you cannot escape Amdahl's law.

Sometimes the best way to solve a problem is to eliminate it, instead of ending up into a hammer / nails loophole.

I wouldn't have a problem with switching to this model entirely if this model simplified things. But it doesn't. I can see plenty of examples that are now more complicated. As examples:

• we now have to work with shared state, aka Ref / Deferred in certain instances. We did not have a need for that, but now if we switch to a bracket-aware encoding, we do. You're working a lot with such shared state in FS2 too, so how many of those instances would be unneeded without your scopes?
• the interpreters (aka folds) now need to maintain a stack, because you can no longer concatenate two streams without a node in your ADT like Concat(lh, rh) — which is natural, because usage of bracket now necessarily implies usage of a stack (even if we are talking about the monadic stack, e.g. task1 >> task2), the data structure being no longer a simple linked list but a tree (e.g. it's no longer a "tail recursive" data structure so to speak)
• Witness the Move uncancelable down to Bracket. Add laws specifying interaction. #241 PR which proposes an ensuring(task)(release) utility, as a shorthand for F.bracket(F.unit)(_ => task)(_ => release); nobody questioned however that any calls like that are probably broken in the proposed auto-cancelable model, see my comment

When seeing such added complexity, I do have to wonder, how can this be the right answer?

And because this behavior is not something that can be witnessed by usage of cats.effect.IO, or Monix Task (without enabling autoCancelable behavior) or by Coeval or by the old Scalaz 7 IO and Task, what this means is that code using those cannot be simply be converted to F[_].

Now if we all agree that this model is the right own, screw other opinions, I'm fine with that — we'll go through a painful transition in Monix and be done with it.

[SystemFw]

Note that we needed Scopes way before any discussion on cancellable binds was started. Streaming + resource safety + concurrency broke in a million different ways otherwise, and my feeling is that Iterant will move to a similar model eventually, just like scalaz-stream/fs2 did, regardless of cancellable binds or not.

I also don't see how this problem can be ignored: right now I can write polymorphic code in Iterant that breaks if a Monix option is enabled. Even if you decide to go with Continual, can I not still break things just by flicking autoCancelable on?

As for ensuring, I don't think that it's broken because of cancelable binds, the broken behaviour is assuming safety for things outside bracket (and releasing things allocated in another bracket call is just another example of that).

That being said, I don't want to force the issue, these are just my opinions, so I'm keen to hear what the others think 😃

[alexandru]

I also don't see how this problem can be ignored: right now I can write polymorphic code in Iterant that breaks if a Monix option is enabled

You're right about that one, I've been simply deferring the issue. The proposal in this issue would make it safe though, without excluding Scalaz or Monix's auto-cancelable option, being an add-on and it's better than what I had 3 months ago.

We don't have to rush into pushing it that badly. Thinking today with a clearer head, we could even release it post 1.0, plus I really want this decision to be taken for the right reasons and not because my own code breaks.

Therefore we could proceed with a release without Continual. I'll cope with it.

[jdegoes]

Note that the role of the type classes is to support other implementations. We don't want just cats.effect.IO, or just scalaz.effect.IO or just monix.eval.Task. We want all of those and more, which is why I personally was open to support Scalaz's new IO, hence all this pain.

Please do not change anything just for Scalaz IO. I think changes to this project should be done for the right reasons—i.e. they promote the development of correct software. I also think that supporting unprincipled and lawless effect types, or those that promote the development of incorrect software, is not a net positive and the project should not aim to sacrifice principles to gain inclusivity.

Note how we still rely on bracket, except that you can then rely on composing two brackets referring to an outer resource.

This already works and composes without issue.

val task1 = F.bracket(acquire1)(use1)(release1)
val task2 = F.bracket(acquire2)(use2)(release2)
val task3 = task1 *> task2

In this example, task1, task2, and task2 can all be interrupted in certain places (in use1 and use2, and between task1 and task2 for task3), and all resources will be safely released.

In order to contrive an example that does not "work", you need task1 to leak a resource that is subsequently used in task2.

For example, the following code:

val task1 = F.bracket(acquire1)(resource1 => use1(resource1) *> F.point(resource1))(release1)
val task2 = task1.flatMap(resource1 => 
  F.bracket(acquire2)(resource2 => use1(resource1) *> use2)(release2)

In this example, resource1 escapes its scope. Because it has been released by release1, this means that the resource will likely be invalid, and its use in task2 will lead to runtime errors.

This problem can be solved with type tricks, although whether or not the added encoding cost is worth the increase in safety is worth discussing.

Now, if you need to use resource1 and resource2 together, then you cannot merely leak resource1 from within task1. In this case, you must nest the brackets:

F.bracket(acquire1)(release1) { resource1 =>
  F.bracket(acquire2)(release2) { resource2 => 
    // Now can safely use `resource1` and `resource2`
  }
}

If both of these require access to an outer resource, that too can be described safely through nested brackets:

F.bracket(acquire0)(release0) { resource0 =>
  F.bracket(acquire1(resource0))(release1) { resource1 =>
    F.bracket(acquire2(resource0))(release2) { resource2 => 
      // Now can safely use `resource1` and `resource2`
    }
  }
}

All these (non-leaky) compositions have guarantees that they can be interrupted at any point, or fail due to defect or catastrophic error, and all acquired resources will be released. You can even do opt-in, early resource release, if the inner task decides it is done with resource1 (after it has acquired resource2), and wishes to release it prematurely.

Assuming you are not leaking resources outside bracket—which results not in leaked resources, but in runtime errors due to using invalid resources—then bracket offers enough compositional power to use any number of resources in any combination.

That doesn't mean it's always easy to use bracket like this—it is no easier than using try / finally or defer. Iterant, FS2, and others demonstrate that aligning a higher-level model of resource management onto bracket is not straightforward; you need to compile from one model to another, which requires carrying around extra state.

In order to understand the root of the problem, you must understand IO as a chain of nested operations:

op1 -> (op2 -> (op3 -> (op4 -> (op5 -> (... -> opn...)))))

Bracket lets you acquire and release resources around any choice of parentheses. We have to perform state management and have a separate compilation process if we want to acquire and release resources around any other combinations (for example, around just op2 -> op3).

Witness the #241 PR which proposes an ensuring(task)(release)

The meaning of F.ensuring(task)(release) in Scalaz 8 is that release is guaranteed to be run if and only if task begins execution (with no guarantee that any certain number of operations in task have been executed—it's nondeterministic). It should not be used where bracket is appropriate, but it can be useful sometimes to spy on a task.

When seeing such added complexity, I do have to wonder, how can this be the right answer?

It is simple in this way: if the code uses bracket for all resource acquisition and release, then it is resource safe, to the maximum extent possible (obviously a bug in release can affect its ability to actually perform a release). If it does not, then it is not resource safe.

It is not simple in that using bracket is nontrivial with higher-level resource management models.

This example demonstrates that resource safety cannot be achieved with continual.

continual(
  F.bracket(acquire1)(use1)(release1) *> 
  F.point(throw new Error("")) *> 
  F.bracket(acquire2)(use2)(release2)
)

If the code was relying on release2 to be invoked if release1 was invoked, in order to achieve resource safety, then this trivial example demonstrates the assumption is completely incorrect.

It is not only monad transformers for which continual does not work—it's any type of failure or non-termination between such bracket pairs.

Thinking today with a clearer head, we could even release it post 1.0, plus I really want this decision to be taken for the right reasons and not because my own code breaks.

👏

You have my highest respect for being so objective about this issue, and I want to make it clear that although I think the current laws are broken and lead to resource unsafe code (such as Iterant), in direct contradiction with the existence and intent of MonadBracket, I greatly admire the work you do for the Scala community—the depth of work you have contributed, its high performance, and its unrelenting focus on the real world issues that professional programmers have.

[mpilquist]

@jdegoes Can you chime in on the proposed changes to the laws? Specifically #237?

[alexandru]

Closing this, as at the moment I'm no longer interested in the proposal.