Cats-effect: Allocated: New Typeclass Below Concurrent

[djspiewak]

This one is a lot more annoying than MonadCancel, tbh. What I'm proposing would sit under Concurrent and adjacent to Temporal, with Async deriving from both. The core of this typeclass would simply be the ability to create a Ref and/or Deferred. Part of the thought process here is the fact that Ref and Deferred as so incredibly widely needed, and the only way to get them in the present hierarchy is to have an Async. This undermines one of the design goals of the hierarchy, which was allowing people to use safer classes (like Concurrent) which cannot capture side-effects. Additionally, there are examples of datatypes which trivially can implement Ref and Deferred but which cannot form an Async (e.g. PureConc).

Now, to be clear, I do think that much of the code which today relies on Ref and Deferred can probably be rewritten without loss of performance or clarity to use Concurrent. That isn't possible for all cases though (or possibly even most), and the rewriting is not always obvious. This is part of what drives the motivation for this proposed class.

The biggest problem with this sort of typeclass, aside from the fact that it introduces mutation directly into the kernel, is the fact that it's incredibly challenging to talk about laws and ensure that implementations are actually correct. We would need to sufficiently constrain implementations to a very tightly defined set of semantics, otherwise it is very likely that users of this typeclass (mostly middleware frameworks) would end up inadvertently assuming Cats Effect semantics, which effectively would turn this into a false abstraction. We would need to be very careful about this.

[djspiewak]

Ongoing discussion: https://gitter.im/typelevel/cats-effect-dev?at=5f21855e27799668010c2b12

[djspiewak]

The conclusion here seems to be incoherent "maker" typeclasses on the companions (e.g. Ref.Mk, Semaphore.Mk, etc), rather than trying to stuff something into the hierarchy. This also allows Ref etc to remain in the concurrent module.

[djspiewak]

Restoring this. Some context: https://gitter.im/typelevel/cats-effect-dev?at=5f3c11c3ef8d4e243b482298

Tldr Mk isn't working. Let's try Allocate.

[RaasAhsan]

Some food for thought: from the perspective that Allocated gives you a means by which you can safely allocate and mutate state in F, does it make sense to give Sync a means to do this as well? Obviously for Ref, there would be no concurrency so it would always be safe (it's analogous to a stack-local var), but I imagine it's not going to be very useful to begin with. Deferred doesn't really make sense with Sync, and separating Ref and Deferred anymore would start to make things kind of messy.

To reverse your question of "is concurrency fundamentally tied to mutation?", is mutation fundamentally tied to concurrency? My gut feeling says no, but I'm not sure if that's actually useful.

[djspiewak]

This is an interesting point. Technically, Allocated doesn't need to live under Concurrent at all, though it definitely gets weird if we include Deferred. I guess we can split the Deferred typeclass and the Ref one.

[RaasAhsan]

I've been warming up to this idea more. Right now, kernel is effectively a specification for an abstract computer or language that is capable of computing/evaluation. The FFI (delay, blocking, async, etc.) allows us to lift the result of native Scala computations into that computer. With Allocated, the computer begins to hold a memory capable of manipulating state. Users of the API should theoretically be able to write programs against that specification, touching the native language only infrequently.

It's worth pointing out that the Ref and Deferred traits need to be migrated to kernel, possibly leaving the provided implementations in concurrent, which leaves it almost barren :D We also need to figure what to do with MVar.

[djspiewak]

So thinking about laws here…

Ref and Deferred both have the same problem: their behavior can only be correctly defined with respect to an environment. Think about the ref context you need if you want to formalize evaluation semantics for the lambda calculus with mutable refs. What we really want to say is something like this:

(r -> x) in Γ
---------------- E-Get
Γ |- get r -> x


----------------------------------- E-Set
Γ ∪ { r -> x } |- set r x -> unit

So, I think we can actually do that. For example:

def sharedRefGet[A](env: Env[Ref[A]]) =
  env |- {
    case (r, a) => r.get <-> pure(a)
  }

def sharedRefSet[A](env: Env[Ref[A]], a: A) =
  env |- {
    case (r, _) => r.set(a) <-> (env(r) = a)
  }

def sharedDeferredGet[A](env: Env[Deferred[A]]) =
  env |- {
    case (d, None) => d.get <-> never
    case (d, Some(a)) => d.get <-> pure(a)
  }

def sharedDeferredSet[A](env: Env[Deferred[A]], a: A) =
  env |- {
    case (d, None) => d.set(a) <-> (env(d) = a)
    case (d, Some(_)) => d.set(a) <-> env
  }

This sort of a thing, perhaps with slightly revised syntax. You get the idea though! We can then write an Arbitrary[Env[Ref[A]]] and Arbitrary[Env[Deferred[A]]]. Remember we have full control over the <-> syntax, and lifting it into the environment in this fashion using the |- method gives us the ability to control how all of this gets turned into a Prop.

[SystemFw]

Something to keep in mind: what are we going to do with the Mk.In[F, G] constructors?

[djspiewak]

Something to keep in mind: what are we going to do with the Mk.In[F, G] constructors?

Burn them with fire. :-)

Okay, I'm willing to be talked down from that position, but… not too willing. I haven't seen a single use-case for the in constructors which doesn't ultimately boil down to "a way to convince one's conscience that unsafeRunSync() is fine".

[SystemFw]

I don't have one, but I remember that when they were introduced, the reason wasn't unsafeRunSync + SyncIO, it was more like F vs Kleisli[F or something like that. http4s has a bunch of two params things these days so maybe @rossabaker or @ChristopherDavenport can weigh in

[LukaJCB]

We can recreate those constructors using mapK, no?

[SystemFw]

Ok, the issue I was remembering was this one https://github.com/typelevel/cats-effect/issues/373
and that can be resolved with mapK

There's a longer discussion here https://github.com/typelevel/cats-effect/pull/388 which mentions scala.js, I haven't reread it all yet

[SystemFw]

Fwiw, it they can be eliminated, I'm all for it

[SystemFw]

Also I'm going to drop it here out of context, Allocated should be renamed to Concurrent, and Concurrent to Spawn or Fork

[RaasAhsan]

@SystemFw I'm not against Concurrent as a replacement for Allocated, but any concerns with migration friction? It reminds me of the ExitCode and IOApp discussions we had, but this is potentially more confusing since what the name is actually referring to is changing.

[SystemFw]

It's actually beneficial for migration because I suspect that 90% of the code requiring ce2.Concurrent will require Allocated now. Worst case scenario will be things being over constrained to what I think is an innocuous extent.

[djspiewak]

Also I'm going to drop it here out of context, Allocated should be renamed to Concurrent, and Concurrent to Spawn or Fork

I don't have any particular objections to this; I agree that having Ref and Deferred is a lot closer to what most people need when they ask for concurrency. I don't like Spawn or Fork as names, but that's something that can be iterated on. I don't like Allocate either. :-P

[SystemFw]

Just got hit by ambiguous implicits when using Alloc: TemporalThrow. Major problem for users imho.

[djspiewak]

Fabio's about to drop the wisdom bomb, but… my preferred option here is to linearize and rename the hierarchy. Thus: MonadCancel >: Spawn >: Concurrent >: Temporal >: Async >: Effect (the Clock and Sync stuff stays the same). In other words, we rename old Concurrent to Spawn, then rename Allocate/Shared/whatever to Concurrent and move Temporal under it, rather than treating it as a sibling.

[SystemFw]

More discussion here https://gitter.im/typelevel/cats-effect-dev?at=5f497b29dfaaed4ef5171846

I think Daniel's message just now is probably the compromise we will pick. Just to outline the options that were discussed (I'm going to use the old names):

• Creating a new typeclass under current Concurrent and Allocate. Requires thinking of yet another name, and still exposes users to problems
• Linearise. Concurrent :> Allocate :> Temporal. Fixes the issue without complicating the hierarchy. Negatives: Temporal below Allocate is just a matter of convenience, because there is really no formal justification, they are siblings conceptually
• Merge Allocate and Concurrent (my preferred choice, at least initially). Keeps the hierarchy small, one typeclass to encapsulate real world concurrency. Negatives: conflates simple DAG concurrency (Concurrent) with general concurrent flow.
• Use scato encoding to avoid the ambiguity. No one likes it :)

[djspiewak]

Use scato encoding to avoid the ambiguity. No one likes it :)

I mean, I would imagine that Alöis does. :-)

[SystemFw]

ahahah fair. Tbh I like it too, just not the split in half with cats

[djspiewak]

I would like it more if the disambiguation lattice were open rather than closed. Now I'm leading us off-topic though. :-)