A proposal for Effects, handlers, and removal of unnecesary abstractions

arrow_encoding_1_0.kt

/**
 * The following file shows what we are proposing for the Arrow 1.0 Encoding
 * This encoding affects type classes, removing kinds and making polymorphism
 * structural based on `fun interface`
 */
@file:Suppress(
  "FUN_INTERFACE_WITH_SUSPEND_FUNCTION", // fix upcoming in 1.4.x
)

package arrow.prelude

import arrow.continuations.generic.DelimContScope
import arrow.continuations.generic.DelimitedScope
import arrow.continuations.generic.MultiShotDelimContScope
import arrow.core.Either
import arrow.core.Either.Right
import arrow.core.Left

/**
 * Algebras or type-classes are always defined as `fun interface`.
 * They do not extend each other and are composed as functions.
 */
fun interface Plus<A> {
  infix operator fun A.plus(other: A): A
}

/**
 * `fun interface` always require to leave one abstract method and
 * have the advantage that the compiler can provide a class to instantiate them
 * automatically where instances are declared.
 *
 * Additionally `fun interface` matches structurally with members callable references
 * and lambdas of the same shape as the fun interface making it easy to construct instances
 * that are based on existing data type members or extension functions:
 * ```kotlin
 * val x: Eq<List<A>> = Eq(List<A>::equals)
 * ```
 *
 * In the example below we see a new feature of meta where we will be able to extend
 * the semantics of operators and override builtin ones in the local compilation unit.
 *
 * Eq is able to replace user code depending on `==`
 * with meta additional exposed operators so it picks up the user declared instance and replaces
 * the builtin function EQEQ.
 * Same for Order and others not in this example which Kotlin denotes as special operators.
 */
fun interface Eq<A> {
  infix /* operator */ fun A.eqv(other: A): Boolean
}

/**
 * Empty identity for [A]
 */
fun interface Empty<A> {
  fun empty(): A
}

/**
 * An arrow from A to B.
 *
 * Serves the purpose of Just:
 * `Invoke<A, List<A>>`
 *
 * or monad bind:
 * `Invoke<List<A>, A>`
 *
 * or any other arrow transformation
 *
 * This is because in a type system without higher kinded types
 * invoke can not be expressed in contravariant position such as that implementors
 * could provide: <B> List<B> -> B since there is no way to express F<A> -> A where F
 * is seen as a type constructor in which B could be applied.
 *
 * This issue is not a big deal though because in suspension all type classes like
 * Functor, Applicative, Monad and in general all that deal with higher kinded types are not useful
 * in an effect system based on suspended continuations.
 * With suspended functions [invoke] replaces flatMap and all other operators being able to bring:
 * F<A> -> A
 * A -> F<A>
 *
 * Most people don't write polymorphic programs with Arrow based on kinded types but instead use
 * suspension and we are here in this proposal bringing capabilities for polymorphism in general through abstract Effects and their
 * Handlers. I propose we remove most Haskell style type classes and repurpose their useful combinators as
 * algebras and their handlers as demonstrated below which in their initial phase are data type focused.
 *
 * Other libraries like Haskell's `eff` bring effects such as NonDet and Choice that are more general than
 * the data types themselves but all of the data types like Either and others are still very much useful
 * so this hybrid approach and style seems to work for both type class style instances and arbitrary user built
 * effects that are ultimately exposed in public facing apis as computational blocks.
 *
 */
fun interface Invoke<A, B> {
  suspend operator fun A.invoke(): B
}

/**
 * An Effect has access to its delimited scope and can shift
 * out of any operation in the continuation with a value of [F]
 *
 * It has the power of the continuation monad which can subsume and go to all others.
 * Since in Kotlin [Iterable], [List] and most datastructures expose
 * their api as inline functions, they are co-pure and let effects pass through.
 * These data structures like [List] which are stack safe in their impl and have inline apis
 * that let suspension pass through are in fact free monads with the power of suspended delimited continuations.
 */
fun interface Effect<F> {
  fun scope(): DelimitedScope<F>
}

/**
 * A handler implements a set of capabilities for a use case.
 * In this case [EitherEffect] serves the purpose of describing what's available
 * in [either] computational blocks. This declaration is equivalent to a
 * type class instances if we accept the block is how type-classes expose all capabilities.
 * While these blocks are monadic in this implementation all kinds of other specialized
 * handlers are possible.
 */
fun interface EitherEffect<E, A> :
  Effect<Either<E, A>>,
  Eq<Either<E, A>>,
  Invoke<A, Either<E, A>> {

  override fun Either<E, A>.eqv(other: Either<E, A>): Boolean =
    this == other

  override suspend fun A.invoke(): Either<E, A> =
    Right(this)

  /**
   * When we implement monad bind concretely at the edge we have
   * full control on strict single shot data types to get to our value
   * folding the data structure and only shifting in the unhappy path
   */
  suspend operator fun <B> Either<E, B>.invoke(): B =
    fold({ e -> scope().shift { Left(e) } }, { it })
}

/**
 * Computational blocks can be easily be built for any given handler.
 * In this case the [either] block uses [DelimContScope] instead of [MultiShotDelimContScope]
 * because the [Either] data type can hold a single value. For cases like [List]
 * or [Sequence] we would use [MultiShotDelimContScope] so monad bind and other
 * suspended functions can yield control to the block multiple times.
 */
inline fun <E, A> either(crossinline f: suspend EitherEffect<E, *>.() -> A): Either<E, A> =
  DelimContScope.reset { Right(f(EitherEffect { this })) }

/**
 * Handlers remain interfaces all the way so they are always composable
 * in Arrow and by third parties wanting to extend their capabilities.
 *
 * For a third party to extend an arrow handler all required is to extend the handler
 * and provide a new block function like [list], [either] or [listEither]
 *
 * Users can still consume handlers through their exposed functions like [either], [list]
 * and not worry about what's in the internals.
 */
fun interface ListEffect<A> :
  Effect<List<A>>,
  Eq<List<A>>,
  Invoke<A, List<A>>,
  Plus<List<A>>,
  Empty<List<A>> {

  override fun List<A>.plus(other: List<A>): List<A> =
    asIterable() + other

  override fun List<A>.eqv(other: List<A>): Boolean =
    this == other

  override fun empty(): List<A> =
    emptyList()

  override suspend fun A.invoke(): List<A> =
    listOf(this)

  /**
   * This is more or less what all impls of monad bind look
   * for data types that have a flatMap. Since we can now reset / shift with arrow-continuations
   * there is no nasty reflection tricks
   */
  suspend operator fun <B> List<B>.invoke(): B =
    scope().shift { cb -> flatMap { cb(it) } }
}

inline fun <A> list(crossinline f: suspend ListEffect<*>.() -> A): List<A> =
  MultiShotDelimContScope.reset { listOf(f(ListEffect { this })) }

/**
 * Since handlers are made of function composing them with their
 * factories is simple. In the example below we are creating a transformer
 * computational block for `List<Either<E, A>>` and using [either] and [list]
 * to implement 3 layers of monad bind for types:
 * - List<A>
 * - Either<E, A>
 * - List<Either<E, A>>
 */
fun interface ListEitherEffect<E, A> : Effect<List<Either<E, A>>> {
  suspend operator fun <B> List<Either<E, B>>.invoke(): B =
    list<Either<E, B>> { either { this@invoke()() } }()

  suspend operator fun <B> List<B>.invoke(unit: Unit = Unit): B =
    list { this@invoke() }()

  suspend operator fun <B> Either<E, B>.invoke(): B =
    either<E, B> { this@invoke() }()
}

inline fun <E, A> listEither(crossinline block: suspend ListEitherEffect<E, *>.() -> A): List<Either<E, A>> =
  MultiShotDelimContScope.reset { listOf(Right(block(ListEitherEffect { this }))) }

/**
 * User land is extremely simple. Open a computational block of your favorite data type
 * and enjoy the handlers syntax. In this examples we implemented monad bind but
 * everything in here also applies to a la carte handlers where users are free to compose or implement other idioms.
 *
 * Since all blocks are suspended and we have reset / shift power in the internals
 * any kind of DSL can be expressed over any data type inside blocks cooperating with
 * effects, I/O and in general anything that works in suspend functions.
 */
suspend fun listComputationTest(): List<String> =
  list {
    val a = listOf(1, 2, 3)()
    val b = listOf("a", "b", "c")()
    "$a$b"
  }

suspend fun transformerTest(): List<Either<Throwable, Int>> =
  listEither {
    val a = Right(1)()
    val b = Right(1)()
    val c = listOf(Right(1))()
    val d = listOf(1)()
    a + b + c + d
  }