deriving-task.md

Consider a value of the following type:

type Thunk[A] = () => A

This value represents a thunk of A. Any general effect type, F[_], in Scala must define a function of the following type:

val suspend: (() => A) => F[A]

This is necessary due to the fact that Scala allows for uncontrolled effects. Thus, any practical general effect type must provide a mechanism for lifting an uncontrolled effect which produces a value of type A into a referentially-transparent value of type F[A]. This suspend constructor is capable of handling all sequential, blocking effects.

Asequential, non-blocking effects cannot be handled through such a construction. To devise a constructor which suffices, we apply the CPS transformation to the Thunk type, yielding the following:

type CPSThunk[A] = (A => Unit) => Unit

This is simply a different encoding of Thunk, though with some lightened restrictions that cannot be enforced due to Scala's lack of linear types (namely, we cannot enforce at the type level that the parameter is only invoked once). In an ideal world, we would actually convert Thunk to static signal-assignment form, but this is not possible. Nevertheless, the isomorphism is clear and well established (Steele, 1975).

Note that we can loosen the unsafety of this construct slightly without having any impact on its applicability:

type SafeCPSThunk[F[_], A] = (A => Unit) => F[Unit]

The above is also valid, though essentially no expressivity is lost or gained here. As a reminder, this is an impure type designed to capture uncontrolled effects, just as Thunk is.

Thus, any practical general effect type in Scala which wishes to support asquential, non-blocking effects must provide a constructor which has a CPS analogue to suspend. Namely:

val async: ((A => Unit) => Unit) => F[A]

This is the direct analogue to suspend, save that the value is a CPSThunk rather than merely a Thunk. As mentioned above, it is fine to use SafeCPSThunk here.

If we formalize this further into a typeclass, we arrive at the following:

trait EffectFFI[F[_]] extends Monad[F] {
  def suspend[A](thunk: => A): F[A]
  def async[A](body: (A => Unit) => Unit): F[A]

  @deprecated("don't ever call this")
  def unsafePerformSync[A](fa: F[A]): A
  @deprecated("don't ever call this")
  def unsafePerformAsync[A](fa: F[A])(cb: A => Unit): Unit
}

While suspend and async form our introduction rules by way of FFI from unconstrained "bare" effects, unsafePerformSync forms the elimination rule to an unconstrained bare effect. To be precise, this effect is sequential. The analogous elimination rule for asequential bare effects is unsafePerformAsync. The following laws hold:

suspend(unsafePerformSync(fa)) === fa
async(unsafePerformAsync(fa)) === fa

Preempting Objections

Please note that the following is not a valid encoding of a CPS thunk:

type SafeCPSThunk[F[_], A] = (A => F[Unit]) => F[Unit]

The problem here is that any async constructor which is implemented with this type will be useless without calling one of the unsafe elimination rules! For example, consider safely wrapping the asequential effect representing an NIO callback:

// imagine the following signature for async
val async: ((A => F[Unit]) => F[Unit]) => F[A]

val fb: F[ByteBuffer] = async { cb =>
  suspend {
    channel.read(new Callback {
      def bytesReceived(buf: ByteBuffer): Unit = {
        cb(buf)   // => F[Unit]
        // what do we do now???!!!
      }
    })
  }
}

The only thing that can be done on the marked line is unsafePerformSync, which is clearly wrong and deeply unsatisfying. It also doesn't make any sense that suspend can wrap a bare unconstrained sequential effect without any calls to unsafe, while async has no analogue.

Thus, the type returned from the callback must be Unit.