Cats-effect: Change F.start(F.unit).flatMap(_.join) to always fork

[alexandru]

This is a suggestion, after talking with @mpilquist:

F.start(F.unit).flatMap(_.join)

We think this should be equivalent with a shift. However currently the cats.effect.IO and the monix.eval.Task do not guarantee this, because if the fiber executes fast enough, then _.join and its bind continuation will execute on the current thread, so no fork will actually happen for practical purposes.

N.B. F.start (for cats.effect.IO and monix.eval.Task at least) already guarantees a fork. So forking join a second time isn't necessarily optimal, but in the actual implementation I played around and we can make it optimal:

1. if the fiber is already done, then we can fork
2. if the fiber isn't done and the callback is registered, then that fork already happened, so no need to do it a second time ... this is a subtle point, because it depends on whom calls the callback, the fiber or the main thread

The advantage is that we could then define shift in terms of start ... and we could add shift to Concurrent in Cats-Effect 2.0.

The truth is I don't know if this is the right thing to do™ and I'm interested in the input of @jdegoes.

[jdegoes]

Just to be certain I understand, you want join to be resumed asynchronously on the thread pool, resulting in a total of two submissions to the thread pool: the initial start, and then the subsequent join?

First off, I think it's absolutely critical that start always, in 100% of cases submit to the thread pool (it's not possible to reason about start without this guarantee). So 👍 on the current behavior of guaranteeing a fork.

Second, I think the above requirement on join might be over constrained: what you really want (I assume?) is to guarantee that joining doesn't increase the stack frame, as it would if implemented via a callback that is invoked synchronously in the event the fiber has completed. If so, then while "fork on join" satisfies that requirement, it's not the only way, and it would be unfortunate to mandate the forking behavior for the performance reasons you mention.

That said, I do think F.start(F.unit).flatMap(_.join) should be "equivalent" to shift (that is, it yields control back to the runtime and starts execution on a fresh stack frame). But I think you get this equivalence from the initial submission to the thread pool, combined with the guarantee you're not increasing the stack frame via a synchronously invoked callback.

[alexandru]

Just to be certain I understand, you want join to be resumed asynchronously on the thread pool, resulting in a total of two submissions to the thread pool: the initial start, and then the subsequent join?

Yes, but if and only if the fiber has finished already. Otherwise, if the fiber is still active when join's callback is registered, the total number of thread-pool submissions is going to be 1.

That said, I do think F.start(F.unit).flatMap(_.join) should be "equivalent" to shift (that is, it yields control back to the runtime and starts execution on a fresh stack frame). But I think you get this equivalence from the initial submission to the thread pool, combined with the guarantee you're not increasing the stack frame via a synchronously invoked callback.

It's not equivalent with a shift and the stack depth isn't the only problem. Note we have the guarantee that async tasks don't increase the stack-frame all over the place, via an internal trampoline, however that trampoline isn't enough in some cases.

The problem we are trying to solve is not stack safety, but rather ensuring that execution happens on a certain thread-pool. And shift guarantees that its bind continuation will happen on a configured thread pool.

So lets say that we have this:

val readFile = blockingIO.shift *> IO {
  blocking(unsafeRead(file))
}

// Ensure that execution "returns" to the default thread-pool
readFile <* global.shift

Unfortunately this doesn't work with F.start(F.unit).flatMap(_.join). I did a quick test and in about 20% of cases execution fails to return to the configured thread-pool, simply because the fiber executes fast enough.

[jdegoes]

So do you want:

a. The guarantee that join will always return to the thread pool of the fiber that performs the join; OR,
b. The guarantee that join will always return to the thread pool of the fiber that performed the start.

The test you wrote seems to test for b. Which may be a problem (compared to a).

[mpilquist]

Here's what I really need -- given val fa = F.async[Unit] { cb => new Thread(() => cb(()).start } I need a way to ensure subsequent binds execute on the "default" thread pool of the effect type and not on the newly created thread.

I can do this now with ContextShift[F] but I want to do it with only Concurrent[F] or weaker.

[alexandru]

I think what I'd like is a guarantee that calling fiber.join.flatMap(bind) implies a real async boundary before bind gets evaluated, on the "default" thread-pool.

What the "default" thread-pool is can be an implementation detail:

1. it could be the thread-pool of the ContextShift value you have
2. it could be the fiber's thread-pool, the one that called fiber.join (your a.)
3. it could be the fiber's thread-pool that called start (your b.)
4. etc.

But execution should involve sending a Runnable in that thread-pool, if we want behavior similar with shift. This is because a trampoline only solves stack safety, but not fairness. You need an actual submission in a real thread-pool to get fairness.

So the discussion would be ... can we add shift to Concurrent and can we describe it via start?

For a Cats-Effect 2.0 this would be great because we could add shift in terms of start and not worry that Concurrent is getting too big.

[alexandru]

Again, I do not know if this is the right thing to do.

The strong argument for it is that at first we all assumed that task.start.flatMap(_join) will behave like shift, but it doesn't, not without modifications to guarantee that a join will always fork.

[jdegoes]

@mpilquist

Here's what I really need -- given val fa = F.async[Unit] { cb => new Thread(() => cb(()).start } I need a way to ensure subsequent binds execute on the "default" thread pool of the effect type and not on the newly created thread.

When I've needed this, I've used the following pattern:

def sticky[E, A](fa: IO[E, A]): IO[E, A] = 
  for {
    p <- Promise.make[E, A]
    _ <- fa.fork.flatMap(_.observe.flatMap(p.done(_)))
    v <- p.get
  } yield v

which works because the completion of the promise will necessarily be forked onto the default thread pool.

Though I'm not sure this solves the problem so much as pushes it to Promise / Deferred. But if Deferred only requires Concurrent, maybe that's sufficient.

(I think also asyncF should provide that guarantee always.)

@alexandru @mpilquist

I think what I'd like is a guarantee that calling fiber.join.flatMap(bind) implies a real async boundary before bind gets evaluated, on the "default" thread-pool.

In my view, the fact that it's very hard to describe what is desired here ("default" thread pool?) is a sign of a design problem: specifically, a design including both shift and async has poorly-defined semantics.

Where ZIO is going, and what I would prefer for next-gen cats-effect, is a combination of two things:

1. The ability to find out where a fiber is running.
2. The ability to lock an IO to a specific location.

In contrast to shift, these primitives have well-defined semantics with async: use of async in an unlocked IO will not provide guarantees about where the computation resumes (although the location is discoverable); whereas, use of async in a locked IO will provide strong guarantees about where the computation resumes.

Unlocked IO will have higher performance and will be the default for most code; but locked IO, while slower, provide strong guarantees that are essential to proper thread pool management.

In my view, these are essential aspects of Concurrent and do not and should not require ConcurrentEffect.

If fiber.join.flatMap(bind) is merely changed to require an async boundary, I'd regard it as a patch-fix—a workaround that will have some desirable properties, but some other undesirable properties, and which doesn't directly address the root problem. Which may be ok for a patch-fix. But if cats-effect 2.0 is seriously coming out in Q1 2019, it may be better to rethink shift and see if there's something better there that can solve this problem and others.

[mpilquist]

@jdegoes I think that pattern would fail with the current 1.x Deferred b/c there's no async boundary inserted by the Deferred. Not certain about that though.

The locked/unlocked idea is interesting -- will think about this. Interested to see more.

In my view, these are essential aspects of Concurrent and do not and should not require ConcurrentEffect.

I'd really love for Effect and ConcurrentEffect to be gone or at least absolute last resort for things like bindings to Java APIs. I spent a lot of time recently trying to get FS2's interop for Java's InputStream to depend only on Concurrent[F] instead of ConcurrentEffect[F] but the best I could do is depend on Concurrent[F] and Concurrent[IO] utilizing LiftIO[F] from Concurrent[F].

I don't think 2019Q1 is reasonable for cats-effect 2 FWIW. Maybe last day of March but not January or February. ;)

[jdegoes]

I think that pattern would fail with the current 1.x Deferred b/c there's no async boundary inserted by the Deferred. Not certain about that though.

Post @alexandru's pull request, Deferred will use start like ZIO and should begin working.

I'd really love for Effect and ConcurrentEffect to be gone or at least absolute last resort for things like bindings to Java APIs.

👍

[alexandru]

Where ZIO is going, and what I would prefer for next-gen cats-effect, is a combination of two things:

• The ability to find out where a fiber is running.
• The ability to lock an IO to a specific location.

Monix has the notion of a "default" thread pool that can be overridden for a certain task. Along with its auto-forking behavior for fairness, this is why the ContextShift.executeOn happened. And for converting Scala API, it also has the ability to inject the required ExecutionContext.

Made a video about it 🙂 https://monix.io/blog/2018/11/08/tutorial-future-to-task.html

I don't think that having the ability to find out where a fiber is running is useful. That's an implementation leak. The litmus test for me is always JavaScript. If something doesn't make sense for JavaScript, then it doesn't make sense at all. And dealing with ExecutionContext on top of JavaScript makes some sense, exposing what is essentially setTimeout(0) (or setImmediate), but it's not enough to turn it into a central piece of the API.

This litmus test is also why we don't have any blocking utility for marking tasks that do blocking I/O. If it's not relevant for JavaScript, it's not getting in.

[alexandru]

Some random thoughts on shift:

I think it's a pretty fundamental operation, available basically on all platforms. We might have use cases that might be better served by other operations, like start, but shift has to be provided by the API.

I would say that we need shift in Concurrent, however this means that Concurrent[F] has to be restricted by the availability of a ContextShift[F] or the availability of an ExecutionContext, for data types that don't have an injected ExecutionContext in their implementation or equivalent (like Monix's Task does). And this makes such instances to not be very clean.

Our Concurrent[IO] instance is already restricted by the availability of a ContextShift[IO]. However the forking behavior of start is not by law and adding shift to Concurrent would make it official.

And another thing is that these type classes are becoming fat if we keep adding operations.
Adding a ContextShift restriction to a function after the fact is a pain in the ass due to binary compatibility, however having some granularity in the type class design is very desirable. It's basically the essence of restricted parametric polymorphism, as in "only depend on what you need", which makes the functions more generic.

In other words we should add shift to Concurrent only if it can be described in terms of the available operations. Like start. If we cannot find reasonable arguments for why start follow by a join should behave like shift, then I don't think we can add it to Concurrent.

Btw, fiber.join is basically like Deferred.get or Semaphore.acquire. These do not fork on the happy path. So unfortunately I don't think we can make fiber.join to guarantee a fork, unless we change those too, to make it as a general rule.

[mpilquist]

Instead of making ContextShift[IO] depend on an ExecutionContext, we could move the ExecutionContext requirement to the unsafeRun* methods.

[SystemFw]

yes, this is indeed the whole "RTS" idea, which I think is preferable.
I also think basing Concurrent on start and shift is a good idea, since they are "fork" and "yield" to the runtime.

[jdegoes]

I don't think that having the ability to find out where a fiber is running is useful.

Sure it is. It's useful if you want to run one computation wherever another computation is running.

That's an implementation leak. The litmus test for me is always JavaScript. If something doesn't make sense for JavaScript, then it doesn't make sense at all.

Since "almost no one" uses Scala.js, and since Javascript is the only single-threaded runtime in existence, I don't think this is a good standard.

Moreover, a distinction must be made between:

• Concepts that have degenerate implementations or analogues in Javascript;
• Concepts that have no valid implementations or analogues in Javascript.

The concept of "synchronous effect", i.e. a synchronous only effect that has no asynchronous regions in it, is one that has an analogue in Javascript. The concept of "location" (compute resource) is one that has a degenerate analogue in Javascript (i.e. there is a single location). On the other hand, the concept of "blocking evaluation" is one that has no valid implementation in Javascript.

Degeneration implementations or analogues are fine; invalid ones are not (or rather should be pushed to optional type classes not provided by a Javascript runtime).

This litmus test is also why we don't have any blocking utility for marking tasks that do blocking I/O. If it's not relevant for JavaScript, it's not getting in.

Blocking IO and synchronous IO are one and the same concept, seen from different perspectives. In my opinion, Cats Effect 2.0 should encourage the use of SyncIO for blocking / synchronous IO, and allow runtimes to special-case lifting of synchronous IO into asynchronous IO (e.g. by using a blocking thread pool for the JVM).

I think it's a pretty fundamental operation, available basically on all platforms. We might have use cases that might be better served by other operations, like start, but shift has to be provided by the API.

I'd prefer start and sleep, with sleep guaranteed to execute the continuation on an initially empty stack frame, with execution on a different thread pool provided by distinct operation. I'll provide a concrete proposal shortly.

yes, this is indeed the whole "RTS" idea, which I think is preferable.

Yes please. Also please no more implicits anywhere, ever, unless they're type class instances.

[alexandru]

@mpilquist

Instead of making ContextShift[IO] depend on an ExecutionContext, we could move the ExecutionContext requirement to the unsafeRun* methods.

You mean how we do it in Monix Task?

The problem is that it's complicated. You don't need just an ExecutionContext, you need a Scheduler. In Monix we can describe one due to having monix.execution, a sub-project dedicated to low-level, impure abstractions. Adding one in Cats-Effect isn't feasible.

@SystemFw

yes, this is indeed the whole "RTS" idea, which I think is preferable.

The "RTS" is a very vague idea, of which we talked about before ... what is a "RTS" anyway? We aren't in Haskell and in Haskell you cannot implement the RTS by yourself.

I basically want to avoid using "RTS" as a name for as much as possible.

@jdegoes

Since "almost no one" uses Scala.js, and since Javascript is the only single-threaded runtime in existence, I don't think this is a good standard.

Not true:

• Monix and even Cats-Effect has plenty of important Scala.js users
• one other popular (in the FP community) and single-threaded runtime is OCaml
  
  
  
  • even if counting is relevant, JavaScript is at this point probably more popular than all other languages combined
  
  

Also single-threading is not the only issue. The issue is actually M:N threading and you can find a lot of such runtimes in the wild, including Haskell and Go.

And I'm making these assertions:

1. with both "1:1" or "M:N" multi-threading, the notion of where an I/O is executed or the notion of thread-pools for that matter ... become entirely irrelevant
2. Java's notion of thread-pool is old and low-level, its direct competition .NET uses a single thread-pool, also making where irrelevant

Of course, Java has thread-pools (plural) and we have to cope with it. It does have advantages, like being able to select ForkJoinPool instead of CachedExecutorService for certain tasks and split your workload. But in the future this may change for Java too, the JVM can evolve to an M:N model and Oracle is not shy on deprecating things, they just deprecated Unsafe, which breaks half the ecosystem at least.

You can expose whatever you want in ZIO, but the type classes themselves have to be thread-pool agnostic. Because Scala can and should transcend the JVM and we need type classes that outlast such concerns.

Blocking IO and synchronous IO are one and the same concept, seen from different perspectives

I kind of disagree and I think we shouldn't mix up the terms.

"Blocking" is related to "synchronous" in the same way as "multi-threaded" is related to "asynchronous". Related, but not the same.

[SystemFw]

@jdegoes

I'd prefer start and sleep

My initial proposal was indeed adding sleep to Concurrent rather than shift, but having Timer lets us have a test timer implementation, which ended up being really useful for deterministic tests.

Also please no more implicits anywhere, ever, unless they're type class instances.

I broadly agree with no more implicit _instances_ unless they are typeclass instances, but I'm ok with passing e.g Timer implicitly, in what I call _implicit call sites_. It's not very different from having an typeclass implemented for a newtype over Kleisli, and using runNewType

[SystemFw]

@alexandru

You don't need just an ExecutionContext, you need a Scheduler. In Monix we can describe one due to having monix.execution, a sub-project dedicated to low-level, impure abstractions. Adding one in Cats-Effect isn't feasible.

I'm not sure I agree here, we already have Timer and ContextShift to represent those things

The "RTS" is a very vague idea, of which we talked about before ... what is a "RTS" anyway? We aren't in Haskell and in Haskell you cannot implement the RTS by yourself. I basically want to avoid using "RTS" as a name for as much as possible.

That's the reason I put it in quotes and I don't care about naming at all. By "RTS" I just mean the idea of passing whatever is required by the implementation as explicit arguments to the running methods, rather than baking them in the typeclass instance. For example, we could have IO.unsafeRun* take a ContextShift and a Timer, and so on.

EDIT:

Also note that we're not as far from this idea as we once were. ContextShift explicitly mentions "the runtime" or "the execution environment", and we provide one "explicitly" by not having an instance of ContextShift, but providing one through IOApp

[alexandru]

@SystemFw

For example, we could have IO.unsafeRun* take a ContextShift and a Timer, and so on

Interesting, I guess we could do that.

But Michael was saying that he wants ContextShift[IO] itself to no longer depend on ExecutionContext, so we've got a problem, since somebody has to depend on ExecutionContext 🙂

I guess if we feed ContextShift[IO] in unsafeRun, the we can have shift in Concurrent or Async.

[alexandru]

Btw, I resisted this idea, that cats.effect.IO should take something in its unsafeRun, because it affords a lighter runtime. But I guess for actual usage you need a ContextShift[IO] for its Concurrent instance anyway, so we haven't gained that much.

[SystemFw]

But Michael was saying that he wants ContextShift[IO] itself to no longer depend on ExecutionContext

Well, I think that's because now ContextShift is required to be implicit for Concurrent to work, whereas with this suggestion it would become a datatype, at which point a constructor that takes EC (or a newSingleThreadedCtxShift, newFixedThreadCtxShift etc. won't be a problem).

But I guess for actual usage you need a ContextShift[IO] for its Concurrent instance anyway, so we haven't gained that much.

yes, at this point even my playgrounds are based on IOApp, so we're there already, just in a slightly clumsy way.

[mpilquist]

I didn't mean to make any claims/requests w.r.t. the ContextShift[IO] instance. I suspect that in 2.0, we won't need a ContextShift[IO] instance for most use cases due to the strong Concurrent[IO] instance. We'd only explicitly need a ContextShift[IO] if we were using evalOn, and I'm not sure if even that will exist in 2.0.

Edit: what Fabio just said. :)

[SystemFw]

And btw, that would also allow sleep in Concurrent (my initial idea and what @jdegoes seems to prefer as well), without compromising the ability to run things deterministically in tests.

[alexandru]

Guys, one tenet of restricted parametric polymorphism is to use only what you need, so some granularity is preferred.

We cannot have a fat Concurrent, or otherwise it will stop to be generic enough and people will start reinventing it. And Concurrent is already overweight.

But I guess this is another issue.

[mpilquist]

Yeah -- I think Concurrent changes to no longer extend Sync or Async though. :)

[SystemFw]

We cannot have a fat Concurrent, or otherwise it will stop to be generic enough and people will start reinventing it. And Concurrent is already overweight.

I was expecting this, so I just want to say this one thing :)

I think of Concurrent as a typeclass with two operations: forking from the "runtime", and yielding to the runtime. That's start and sleep, or start and shift (almost equivalent given shift == sleep(0), so I'd prefer sleep).

Every other operation can be implemented with those, and the only reason to not do so is performance.
In fact, I'd be even tempted to provide default implementations for cancelable , race and so on as a sort of "denotational semantics" (reactive-banana uses this idea), and override the actual operations in the internals of each implementation (so, in Concurrent[IO], Concurrent[Task] and so on). That's because unlike in cats, the number of places implementing cats-effect typeclasses will never be that big, and mostly done by experts that know they need to e.g. override race for perf.

So in that sense, Concurrent is not fat in the same way Monad is not, even though you have many many ops based on just Monad (whileM, ifM and so on).

---

I also like the idea of Concurrent not extending Sync and being a true algebra over concurrency. This would be easier if we're not bound by inheritance, and it comes with mainly two problems:

• Expressing laws requires Sycn/Async: so does ap == <*> for Monad/Applicative, yet they dont' extend Sync
• We need typeclasses over the creation of concurrency primitives (like Ref or Deferred), or you'll pick up a Sync constraint anyway: these aren't essential, and can be provided outside of cats-effect core, or by users, or even not at all (and you degrade to the current situation, with F[_]: Sync: Concurrent. However @mpilquist note that this problem will have consequences for fs2 (e.g. imagine the signature of parJoin)

[alexandru]

Too many issues being discussed at the same time 🙂

[alexandru]

This is like a fork of the Cats-Effect 2.0 discussion 🙂

[jdegoes]

My initial proposal was indeed adding sleep to Concurrent rather than shift, but having Timer lets us have a test timer implementation, which ended up being really useful for deterministic tests.

It's better to push test timer logic into F rather than clutter the hierarchy. After all, even with no support from the runtime, one could already test Concurrent by providing a custom instance for a newtype around IO with a test implementation of sleep (and this is how one would do it for any effect, not just sleeping); therefore, a separate means of doing exactly the same thing is extraneous and unnecessarily complicates the design.

I broadly agree with no more implicit instances unless they are typeclass instances, but I'm ok with passing e.g Timer implicitly, in what I call implicit call sites.

In my opinion, this is implicit abuse; Timer itself has no reason to exist (see above). Also from hanging around cats-effect Gitter, I'd say all these implicits are extremely confusing to new users (what they are, how to get them, why they are needed, etc.).

By "RTS" I just mean the idea of passing whatever is required by the implementation as explicit arguments to the running methods, rather than baking them in the typeclass instance.

YES. 🙏

You can expose whatever you want in ZIO, but the type classes themselves have to be thread-pool agnostic.

That's a strawman, though, since I've never suggested exposing a Java thread pool. 😉

I kind of disagree and I think we shouldn't mix up the terms.

It's not mixing up terms. Even doing _literally no IO_, it's possible to clog an async thread pool by using F.delay((0 to Int.MaxValue).foreach(_ => ())), which will have as catastrophic effects for the runtime as doing blocking IO.

There is no useful distinction between blocking IO and synchronous IO that takes a long time to return, and no way they should be treated differently by the runtime system.

Yeah -- I think Concurrent changes to no longer extend Sync or Async though. :)

YES. 🙏

The introduction of Sync or Async destroys parametric reasoning because these type classes are so powerful, there are no real constraints on the underlying code. Sync and Async should be leaves of the hierarchy.

In fact, I'd be even tempted to provide default implementations for cancelable , race and so on as a sort of "denotational semantics" (reactive-banana uses this idea)

👍

Expressing laws requires Sycn/Async: so does ap == <*> for Monad/Applicative, yet they dont' extend Sync

Laws can introduce their own dependencies (e.g. a way of comparing F[A] with F[A]), like in testz, so this is no real impediment to ditching Sync / Async for Concurrent.

We need typeclasses over the creation of concurrency primitives (like Ref or Deferred)

I think all you need is Ref if you have asyncF (which is already pure and could appear early in a type class hierarchy). Then you can implement Deferred in a pure fashion. Everything else can be derived from those two.

[SystemFw]

I think all you need is Ref if you have asyncF (which is already pure and could appear early in a type class hierarchy). Then you can implement Deferred in a pure fashion. Everything else can be derived from those two.

You definitely don't need to convince _me_ of that :joy:
But that being said, in principle I like the idea of giving other people the possibility of creating their own concurrency scheme. In addition to that, it might be desirable to create concurrency primitives from scratch rather than using Ref, if they're on the hot path.

EDIT:
fs2.Promise was pure, than the original version in cats-effect couldn't be due to the early cancelation design, now it can be pure again, but we might want to keep it as is for perf

[jdegoes]

But that being said, in principle I like the idea of giving other people the possibility of creating their own concurrency scheme.

Possibly then we could have newRef and newDeferred in the type class hierarchy, with default implementation for newDeferred which is pure, requiring only that a data type provide a Ref, but allowing an implementation to provide a higher-performance implementation.

[SystemFw]

Possibly then we could have newRef and newDeferred in the type class hierarchy

Yes but this makes this concurrency scheme "blessed" so if you wanted one based on MVar you might be out of luck. Anyway, we can potentially provide those things outside of the main hierarchy (it might mean that fs2 needs a new typeclass which is not very desirable, but I guess it's a worthy tradeoff), something like

trait Fs2Scheme[F[_]] {
   def concurrent: Concurrent[F]
   def ref[A](a: A): Ref[F, A]
   def deferred[A]: Deferred[F, A]
}

which would be enough for us. But anyway, we're going atrociously off topic ;)

[alexandru]

We need typeclasses over the creation of concurrency primitives (like Ref or Deferred)

I think all you need is Ref if you have asyncF (which is already pure and could appear early in a type class hierarchy). Then you can implement Deferred in a pure fashion. Everything else can be derived from those two.

The idea of building everything on top of concurrency primitives like Ref and MVar comes from Haskell. There people need it because they are real primitives, in the sense that you can't implement them from scratch.

The idea of expressing Task in terms of IO + MVar is also old in the Scalaz community, proposed originally (from what I remember) by Brian McKenna.

I'm very much against it and it's a red herring.

[alexandru]

Also, you're keeping me from going to sleep 🙂

[SystemFw]

I don't think the proposal is that extreme at all.

We need typeclasses over the creation of concurrency primitives (like Ref or Deferred)

All I'm saying here is that even when (if) Concurrent doesn't extend Sync/Async, you'll pick that constraint in most combinators as soon as you need to create a Ref/Deferred, unless you typeclass their creation as well.
Nothing changes in the implementation of F, and as I said this "concurrency scheme" typeclasses dont' have to be central to the design of cats-effect, they can be provided elsewhere, and you can recover the current situation simply by F[_]: Concurrent: Sync

Also, you're keeping me from going to sleep

implicitly[Pun[Timer]]

[jdegoes]

Anyway, we can potentially provide those things outside of the main hierarchy

I _love_ this idea.

I think these type classes belong in cats-concurrency, with default instances provided for Sync / Async - capable effects.

Why?

• First off, it helps solve the problems associated with removing Sync / Async from Concurrent, _which is an extremely important goal for cats-effect 2.0_.
• Second, it allows the major effect systems to provide _their own_ implementations of Ref / Deferred. For example, ZIO has Promise that supports features that wouldn't make sense in a monofunctor IO (for example, failing a promise, since you can represent an infallible promise with Promise[Nothing, A]); and which hooks into the runtime system in a way that Deferred cannot.

Then look at FS2: it would require cats-concurrency but ZIO could provide instances for HasRef or HasDeferred which implement the traits using ZIO's own data types, rather than the default implementations provided by cats-concurrency. Moreover, one could, in theory, provide pure versions of Ref and Deferred on top of State-capable monad, which might be useful for testing purposes.

[alexandru]

@SystemFw your rationale for wanting typeclasses for creating Ref/Deferred is good 👍

[alexandru]

Back to Concurrent, when you initially proposed that Concurrent should no longer extend Sync, I thought you meant that we should use composition instead of inheritance. Now we're taking about Concurrent not having a Sync restriction at all.

@SystemFw can you describe why that's desirable?

For that matter, what instances of Concurrent will we have that aren't Sync?

@jdegoes you mentioned that laws can have a restriction without the type class itself having it. That's fine, but please explain how it's any useful ...

1. If the type also has a Sync instance, then Concurrent could depend on Sync without issues
2. If the type doesn't have a Sync instance, it means that the Concurrent instance is invalid because it's unlawful

I am aware of the issues caused by MonadPlusMagic typeclasses modeled via inheritance. But I thought we were talking about specifying that restriction via composition instead.

So what problem are we solving?

[SystemFw]

@alexandru I'm quite busy all day but I will write something down tonight

[SystemFw]

So (sorry for the delay), first things first:

For that matter, what instances of Concurrent will we have that aren't Sync?

This is not the angle I'm coming from. Even though it's possible to have concurrency for non-sync things, I don't expect it to be particularly useful. So for the remainder of this, we can safely assume that types that areConcurrent instances will also be able to suspend effects.
I still think that decoupling Sync and Concurrent has value.

Imagine you have built some domain algebras in your app, like these two random examples.

trait DB[F[_]] {
  def query[A: Format]: F[A]
  def insert[A: Format](a: A): F[Unit]
}

trait Log[F[_]] {
   def info(s: String): F[Unit]
   def debug(s: String): F[Unit]
}

The reason I like using those is not really to be able to vary the F type (99% of the time it's going to be IO both in code and in tests), but rather the fact that they allow me to build a language in which the problem I need to solve is easy. One of the ways in which they do that is by aiding reasoning, when you see :

def foo[F[_]: Db: Log]: F[Unit]

you have a clearer idea of what sort of things can happen compared to fooIO: IO[Unit]: even though foo is ultimately instantiated to IO, inside that function we can be more parametric using algebras.

Now, imagine we have a few programs like foo that we assemble by describing our control flow in terms of library provided typeclasses. The most common example of this would be using Monad for sequential control flow, and note how with def bar[F[_]: Db: Monad], we still retain the parametricity described above, and we only introduce a way of combining smaller programs into bigger ones.

However, let's assume that the control flow we need is concurrent, which means def bar[F[_]: Db: Concurrent]. Things have changed in this case, because the fact that Concurrent extends Sync/Async means I can use it to embed any code with F.delay, and I've lost the enhanced parametricity that Db gave me.

Detaching Concurrent from Sync solves this issue, while still making it fairly easy for users that don't care to recover the current situation with 'F[_]: Concurrent: Sync. This is also part of the reason why I mentioned the typeclasses for Ref/Deferred, otherwise creating them will incur the same problem: you only wanted a concurrent control flow combinator (typically based around start + Ref + Deferred as the basic building blocks), and you're stuck with the superpower of suspending arbitrary side effects. This is quite a common situation in the fs2 api (parJoin, concurrently and countless others).

Now, Concurrent still probably won't be entirely detached from the hierarchy (it needs bracket to have sane concurrency), but doesn't need to extend Sync (or have it as a member). Moving away from inheritance in the main hierarchy will allow us to explore this and other ideas more easily, I would think.

TL;DR: I'd like Concurrent to be a typeclass for control flow, like Monad, and not one for FFI, like Sync.

[alexandru]

@SystemFw when you're thinking of Concurrent in the above post, you're thinking of start.

I on the other hand also have the cancelable builder in mind, which is derived from asyncF, async and bracketCase.

Concurrent is also the type class that by law describes data types that can be cancelled. Up until Concurrent we can use bracketCase for acting on cancellation, but it is only Concurrent that forces the behavior on implemented instances.

I understand the reasoning for wanting a start that's not related to FFI, but cancelable is FFI, just like async and asyncF before it.

The other problem is that Sync isn't about just suspending side effects. It's also about having stack-safe map and flatMap implementations. If you ignore that and specify Monad as a restriction in say FS2's Stream, if the code relies on recursive map / flatMap calls then that code is broken.

My proposal is for the current type classes to stay as is. Cats-Effect 1.0.0 is already popular and we cannot torpedo the ecosystem. In software development sane evolution trumps revolution each time.

That said, I am open to:

1. introducing composition instead of inheritance, but only as long as we don't advise people to do F[_]: Sync: Concurrent, because that only makes sense in the context of the current Scala language
2. extracting the needed functionality in other type classes.

In other words we can have:

1. a type class for stack-safe map and flatMap, but without the delay
2. a type class for start

If you think about it, this will effectively provide an alternative type class hierarchy without the FFI.

[SystemFw]

a type class for stack-safe map and flatMap, but without the delay

1. Btw I don't know if you're aware, but we already have one in cats: StackSafeMonad
2. That's an interesting alternative, as I said an

trait Fs2Scheme[F[_]] {
   def start ...
   def deferred
   def ref
   possibly def race
 }

Would be good for me, but I'm keen to hear what others think.

---

f you ignore that and specify Monad as a restriction in say FS2's Stream, if the code relies on recursive map / flatMap calls then that code is broken.

Actually that's the case for Iterant, but not for Stream, because we have the FreeC flatMap, so we only need a restriction on the compile methods, but yeah I see what you mean.

---

The other thing is that cancelable position is weird: it's in Concurrent but can be implemented with Async, although I guess the point is the guarantee in the laws, but then again I wonder if it's not another case of <*> == ap. Maybe not though.

---

but cancelable is FFI, just like async and asyncF before it.

I'm actually also not sure about asyncF being FFI (async, sure).

[alexandru]

cats.StackSafeMonad is basically lawless and has imo a horrible name 🙂

Sync has very strong laws, which we need — we not only ask for flatMap to be stack safe, we ask that of map too. Plus it's restricted by MonadError and Bracket. I think I'd like another type class for this one too.

The other thing is that cancelable position is weird: it's in Concurrent but can be implemented with Async, although I guess the point is the guarantee in the laws, but then again I wonder if it's not another case of <> == ap. Maybe not though.*

Indeed, you can express cancelable with just Async and I already did that in Monix.

I'm actually not opposed to moving cancelable to Async, now that I think of it. Not sure if we can express some equivalence with bracketCase but we can try.

Because if we have laws about actual cancellation, they'll be in relation with start and bracketCase. I think they already are.

[SystemFw]

and has imo a horrible name

Can't argue with that. But yeah this deserves more thought.

I'm actually not opposed to moving cancelable to Async,

If we do that (which I think is a good idea regardless), then the arguments for changing Concurrent become stronger imho. We need to basically discuss concerns of stability, and whether Concurrent: Sync is as bad as you think or not.

[alexandru]

We need to basically discuss ... Concurrent: Sync is as bad as you think or not.

Well, if we go through all this trouble, I'm wondering if it's a good idea or not to allow users to exclude the FFI completely and Sync is about delay too.

And when working with Concurrent, you still need bracket and a stack-safe flatMap and that F[_] described by Concurrent will surely have both.

So what can we do for more granularity here ... although TBH I'm not sure it is worth it, but it really depends on how the API evolves regarding the parameterization of the error type in the type classes.

[alexandru]

Therefore yeah, I'm starting to see your point 😄

[jdegoes]

I'm glad to see we're arriving at consensus for pushing Sync / Async to the bottom and ripping it out of Concurrent.

Would be good for me, but I'm keen to hear what others think.

I'm keen to have creation of these structures inside a type class so effect libraries can supply their own versions, and so we can pull more non-primitive functionality out of the type classes themselves (which Ref and Deferred allow you to do).

I'm actually not opposed to moving cancelable to Async, now that I think of it.

We can actually delete cancelable from the type class hierarchy and add it as just an ordinary helper method.

It's not primitive and can be implemented using bracketCase:

def bracketCase[A, B](acquire: F[A])(use: A => F[B])(release: (A, ExitCase[E]) => F[Unit]): F[B]

The release inspects to see if use was interrupted, and if so, it runs the cancel token. (If you want to be ultra precise about boundaries you need a Ref or equivalent.)

[SystemFw]

It's not primitive and can be implemented using bracketCase:

We already have a default implementation (safe as well, with AtomicReference). In cats-effect I'm a bit wary of removing things from typeclasses, because the potential for instance-specific optimisations can be high. E.g. think of race and co.

[alexandru]

Indeed, we already have a default implementation in place.

The reason for why I want cancelable and also cancelableF is due to potential for optimization. cancelable maps 1:1 to Java-ish APIs that expose async actions that can be cancelled and indeed, its implementation is more performant in both cats.effect.IO and monix.eval.Task.

[jdegoes]

We already have a default implementation (safe as well, with AtomicReference).

Although once we lose Sync from Concurrent, we won't be able to do that without additional constraints on F[_] (e.g. HasRef).

In cats-effect I'm a bit wary of removing things from typeclasses, because the potential for instance-specific optimisations can be high. E.g. think of race and co.

Then perhaps we need a "dumping ground" type class for things which are clearly not primitive, but which can benefit from instance-specific acceleration.

Although in ZIO we removed race as a primitive and everything is built on fibers now.

[alexandru]

@jdegoes

Although once we lose Sync from Concurrent, we won't be able to do that without additional constraints on F[_] (e.g. HasRef).

What we are talking right now is to move cancelable to Async, which will continue having async and asyncF, which are FFI functions.

[alexandru]

You know what I also want to expose somewhere?

parMap2

We have Parallel, but I don't like it, due to introducing a type parameter that we don't need. And we can express parMap2 via start and let implementations optimize it.

[SystemFw]

We have Parallel, but I don't like it, due to introducing a type parameter that we don't need

Note that this is changing in cats 2.0, to be a type member like in https://github.com/ChristopherDavenport/cats-par , which means users can ask for F[_]: Parallel[F] and avoid the extra type param.

[djspiewak]

This issue went rapidly off the rails into cats-effect 3 land. It's an interesting discussion, but I'd rather consolidate for organizational purposes. Closing.