[Arrow-kt] For-Comprehension Free Monads in Kotlin

# ArrowFreePrograms.md

For-Comprehension Free Monads in Kotlin - Mini Howto

Copyright © 2020, Philippe Bastiani.
with this restriction: this GIST could be, all or part, updated, copied, diffused for documentary purposes in the Λrrow project.

This GIST is an attempt to describe a repeatable, and automatable, process for building an embedded Domain Specific Language (DSL) with the help of a Free monad.
As material, i'll use Λrrow, the functional companion to Kotlin's Standard Library.

Disclaimer: This GIST assumes that you are roughly familiar with the concept of Free monad.

Source-code compatibility

Λrrow 0.10 (now deprecated)

If you’d like to use Λrrow free monad, you’ll need to add a library dependency for the arrow-free module.

Free Monad - What is it in practice?

One of purposes of the technique presented in this GIST is to separate data from the interpreter that processes that data: A free program is described as a tree free of any interpretation; the choice of the interpretation of the program thus defined may be decided later for its execution.

Abstract syntax trees (AST) are used to describe a Free program. These ASTs are free from any interpretation; and, free to be interpreted in any.

Free Monads allow us to transform, optimize or combine computations.

Free monads also provide a practical way to represent :

• stateful computations as data,
• recursive computations in a stack-safe way.

As we'll see in this GIST, the development of an embedded DSL can be one of the use cases of this technique.

A safe program for free

Let's take a simple recursive program : e.g. the following function calculates a factorial (please ignore integer overflow) :

val eitherMonad = Either.monad<String>()
fun stackSafeEitherProgram(n: Int, acc: Int = 1) : Free<EitherPartialOf<String>, Int>  =
    eitherMonad.fx.stackSafe {
        when {
            n == 1 -> !Right(acc)
            n > 1 -> stackSafeEitherProgram(n-1, acc * n).bind()
            else -> !Left("Invalid number!")
        }
    }

This example uses a for-comprehension; and, an Either as context bound for our computation.

The stackSafe extension:

• is the entry point for monad bindings which enables the for-comprehension,
• returns computations lifting to Free to automatically for comprehend in a stack-safe way. So using this pattern, we avoid stack overflows. Here, stackSafe ensures the stack safety over Either monad.

With the run entry point we can execute our stackSafeEitherProgram :

stackSafeEitherProgram(6).run(eitherMonad).fix().let(::println)
// Right(b=720)
stackSafeEitherProgram(-6).run(eitherMonad).fix().let(::println)
// Left(a=Invalid number!)

NOTE : Λrrow also provides stackSafe extensions for Option, Id, Eval, and so on...

NOTE : the Kotlin's Standard Library with the use of tailrec modifier proposes a standard way to implement this simple recursion. However, this technique could be used for recursive functions that are not eligible for the tailrec modifier.

A Domain Specific Language in 6 steps

Let’s imagine that we want to create a DSL to act on a key-value store...

Which operations do I need to build my program ?

We have the following requirements defined in terms of User Stories:
As an user, ...

• i want to put key-values in a store,
• i want remove key-values from the store,
• i want to retrieve previously stored key-values,
• i want to update key-values previously stored,
• i want to clear the store.

Computation as data - building an Abstract Syntax Tree

We'll use an abstract syntax tree data structure to represent the structure of our Free programs.

We translate our requirements into this abstract grammar:

sealed class KVStoreA<out A> {
  data class Put<A>(val key: String, val value: A) : KVStoreA<Unit>()
  data class Get<A>(val key: String) : KVStoreA<Option<A>>()
  data class Delete(val key: String) : KVStoreA<Unit>()
  object Clear : KVStoreA<Unit>()
}

Our abstract grammar is a set of abstract operations. Where, the sealed's type parameter is the return type of our operations.
Each unit operation is translated into the definition of a separate class/object.

For our DSL:

• We define 4 types of nodes (the put operation is wrapped into Put<T> data class; and so on...),
• The update operation can be defined as a combination of get and put operations... so, we do not need to define a specific data structure for it.

Writing our DSL with the help of a Free Monad

Let's look at the source code of Free. We see that we can lift each element of an abstract grammar into the Free monad with the help of the liftF entry point:

fun <S, A> liftF(fa: Kind<S, A>): Free<S, A> = ...

But wait, what is Kind<S, A> ? In Λrrow Kind<S, A> is an interface to represent the type constructor S<A> where :

• A is the type of the content,
• S has to be the type of the container.

To be elligible to liftF, we should rewrite KVStoreA as follows :

@higherkind
sealed class KVStoreA<out A> : KVStoreAOf<A> {
  ...
  companion objet {} // A companion object is required
}
// GENERATED CODE
// class ForKVStoreA private constructor() { companion object }
// typealias KVStoreAOf<A> = arrow.Kind<ForKVStoreA, A>
// inline fun <A> KVStoreAOf<A>.fix(): KVStoreA<A> = this as KVStoreA<A>

Annotated with @higherkind, KVStoreA becomes a datatype that’s also a type constructor.

Behind the scene, Λrrow emulates Higher Kinded Types in Kotlin; and, generates magic code for us...

Usage of liftF looks like that:

fun <A> put(key: String, value: A) : Free<ForKVStoreA, Unit> = liftF(Put(key, value))
// same pattern for the others operations...

To make it easier to read the code, we create a Free type based on our grammar:

typealias FreeKVStore<A> = Free<ForKVStoreA, A>

Also note, the use of the specialization of the companion object:

@higherkind sealed class KVStoreA<out A> : KVStoreAOf<A> {
  companion object : FreeMonad<ForKVStoreA>
}

Later, this will enable the for-comprehension syntax in fx blocks.

Finally, we can define update as a combination of get and put:

fun <A> update(key: String, f: (A) -> A) : Free<ForKVStoreA, Unit> =
  fx.monad {
    val (vMaybe) = get<A>(key)
    !vMaybe.fold(
      { FreeKVStore.just() },
      { put(key, f(it)) }
    )
    Unit
  }.fix()

At this point, our DSL is ready... And, we have all we need to start writing in our DSL !

Build a program using our DSL

We can easily write our first Free programs. Our programs will use the inherited features from the companion object to get access to binding. Let's use our DSL:

// A single operation
val single = get<Int>("A")

// 2 operations combined with flaMap
val flatmap = put("A", 1).flatMap { get<Int>("A") }

// 3 operations combined into a for-comprehension
val program = KVStoreA.fx.monad {
    !put("A", 1)
    !update<Int>("A") { it * 10 }
    !get<Int>("A")
}.fix()

Here, our 3 programs end with a get operation; and, return a Free<ForKVStoreA, Option<Int>>.

Notice that we are free to start writing our programs without worrying at all about their implementations! The business logic will be injected later when we run our programs.

The Λrrow API proposes the foldMap function to execute Free programs:

fun <M, S, A> Free<S, A>.foldMap(f: FunctionK<S, M>, MM: Monad<M>): Kind<M, A> = ...

This function can be applied to our Free programs... but, this one requires 2 additionals arguments ! The parameter f will be used to inject the interpretation of the DSL. The parameter MM will be used as a monadic container to hold the computations.

Write interpreters

In functional programming, interpreters are about separating the representation of a computation from the way it is run. In the previous paragraph, we wrote programs; but, we were not worried about how it would be interpreted: our programs was free of technical stuffs. i.e we are just expressing how our programs should work using the DSL !

Let's analyze Free<S, A>.foldMap : the f parameter is typed with

interface FunctionK<S, M> {
  operator fun <A> invoke(fa: Kind<S, A>): Kind<M, A>
}

The invoke function transforms a Kind<S, A> into a Kind<M, A> : in others words, this function transforms one type constructor into another one (S<A> ~> M<A>). This kind of transformation is called a natural transformation.

In Λrrow, building an interpreter involves creating an instance of FunctionK.

Hereafter, we interpret our key-value operations in Id:

val idInterpreter : FunctionK<ForKVStoreA, ForId> =
  object : FunctionK<ForKVStoreA, ForId> {
    val kvs = mutableMapOf<String, Any?>()
    override fun <A> invoke(fa: Kind<ForKVStoreA, A>): Id<A> {
      val op = fa.fix()
      return when (op) {
        is KVStoreA.Put<*> -> {
          // business logic...
          kvs[op.key] = op.value
          Id(Unit) // business result in Id
        }
        is KVStoreA.Get<*> -> Id(Option.fromNullable(kvs[op.key]))
        is KVStoreA.Delete -> {
          kvs -= op.key
          Id(Unit)
        }
        is KVStoreA.Clear -> {
          kvs.clear()
          Id(Unit)
        }
      } as Id<A>
    }
  }

For a concrete type A, this interpreter transforms a Kind<ForKVStoreA, A> into a Kind<ForId, A> (aka KVStoreA<A> ~> Id<A>); and, its logic is very simple:

• val op : KVStoreA<A> = fa.fix() downcasts our operation.
• we pattern match against each operation; and, for each of them, we write an effective business logic.
• the result of each operation is to be lifted into an Id.

WARNING : due to a compiler limitation, we must explicitly specify the return type of our implementation (e.g. as Id<A> if we interpret our programs in an Id).

Id is the simplest type container; but, we are not limited to this datatype.
We could easily use other type containers for different behavior:

• Id => Direct computation (Id is just a synonym for A). This implementation requires an internal mutableMap to store the key-values,
• State => to use a purely functional approach to store the operations without any internal map,
• Either => to support failure,
• IO => to support side effects,
• and so on...

We know exactly what kinds of side-effects may happen: If we use the Id datatype, we could expect that no external resources will be involved. If we use the IO datatype some side-effects are expected. And, so on...

Let's imagine a service accessing a remote data source; and, suppose we have a local cache for this data: we could write a single DSL to access the 2 data sources. Then, with the help of 2 interpreters, it will be easy to access the 2 data sources!
Also note that for test purposes, we may also add mocking interpreters.

Execution of our program

Let's look again at the entry point used to run a Free program :

fun <M, S, A> Free<S, A>.foldMap(f: FunctionK<S, M>, MM: Monad<M>): Kind<M, A> = ...

We must ensures the type consistency between FunctionK<ForKVStoreA, F> and Monad<F>: to do that we could add a convenient function to run our programs.

inline fun <F, A> Free<ForKVStoreA, A>.run(
  interpreter: FunctionK<ForKVStoreA, F>, MF: Monad<F>) =
  this.foldMap(interpreter, MF)

This function ensures a type consistency where

• interpreter is our parameterized interpreter,
• MF holds our computations.

Behind the scene, Λrrow unpacks the sequence of scheduled operations; and, it calls our interpreter for each of these operations.

Here, we execute our program with idInterpreter. Then, with the call of value(), we downcast the final result to a concrete value :

val idInterpreter : FunctionK<ForKVStoreA, ForId> = ...

program.run(idInterpreter, Id.monad()).value().let(::println)
// Some(10)

Here, we execute our program with stateInterpreter. Then, with the call of fix().runA(emptyMap<String, Int>()) we downcast the final state; and, we extract the concrete result:

val stateInterpreter : FunctionK<ForKVStoreA, StatePartialOf<Map<String, Any>>> = ...

program.run(stateInterpreter, State().monad()).fix().runA(emptyMap<String, Int>()).let(::println)
// Some(10)

Here, we execute our program with ioInterpreter. Then, with the call of fix().unsafeRunSync() we downcast the result; and, we run its encapsulated effects as impure side effects to get the concrete result :

val ioInterpreter : FunctionK<ForKVStoreA, ForIO> = ...

program.run(ioInterpreter, IO.monad()).fix().unsafeRunSync().let(::println)
// Some(10)

Limitation

In theory, using a free monad allows to compose DSLs.

If we’d like to use two distinct grammars in one program, we'll need to create new datatypes to make them compatible. That is a pain and also not recommended because of the lack of Higher-Kinded Types (HKT) in Kotlin.

This issue with Free in Kotlin in general is that you can't easily mix different grammars; therefore, in state, Free constructs are not really applicable to real-life projects.

Implementation Notes – For-Comprehension

In this GIST, for more readability, we mainly used the ! modifier as comprehension syntax.

Please note that Λrrow provides 3 comprehension syntaxes which can be used in fx blocks:

• .bind() call (e.g. val one = just(1).bind()),
• a basic destructuring syntax (e.g. val (two) = just(one + 1)),
• shortcut syntax with the ! modifier (e.g. val three = !just(one + two)).

IMPORTANT : In some use cases, basic destructuring & ! syntaxes could collide with Kotlin syntax. Therefore, the bind() syntax should be the preferred way to destructure effects.

INFO : In the upcomming major release of Λrrow, the comprehension syntax is changing to property delegates because is the only way to guarantee inline bind does not break reference transparency.

Links

• Λrrow Documentation
• Category Theory for Programmers by Bartosz Milewski - Haskell resource with Kotlin sample code
• Rúnar Bjarnason talk about free monad - Scala resource
• The Book of Monads by Alejandro Serrano Mena - Haskell resource
• Inspired by this article : Scala Cats - Free Monad

Summary

Free constructs make sense if you want to DSL-ize parts of your codebase.

A Free construct:

• translates stateful computations as data,
• allows to run recursive computations in a stack-safe way,
• allows to interpret an algebra in many ways; and, for many purpose.

But, do not forget that mainly due to some limitations, this Λrrow feature is not yet mature enough. The Λrrow Free part is in incubation: refer to this issue to follow the improvements in progress.

kvstoreAlgebra.kt

/**
 * Arrow 0.10
 * Get started with Arrow.
 * How to write a Free DSL - Algebra part.
 */
package gist.arrow.free

import arrow.core.*
import arrow.free.*
import arrow.free.Free.Companion.liftF
import arrow.free.extensions.FreeMonad
import arrow.higherkind

typealias FreeKVStore<A> = Free<ForKVStoreA, A>

/**
 * Algebra for our Key-value store service defined with an abstract/declarative API.
 *
 * Algebras are defined by a sealed class & continuation pattern.
 */
@higherkind
sealed class KVStoreA<out A> : KVStoreAOf<A> {

    // Algebras
    data class Put<A>(val key: String, val value: A) : KVStoreA<Unit>()
    data class Get<A>(val key: String) : KVStoreA<Option<A>>()
    data class Delete(val key: String) : KVStoreA<Unit>()
    object Clear : KVStoreA<Unit>()

    // DSL
    companion object : FreeMonad<ForKVStoreA> {
        
        fun <A> put(key: String, value: A) = liftF(Put(key, value))

        fun <A> get(key: String) = liftF(Get<A>(key))

        fun delete(key: String) = liftF(Delete(key))

        fun clear() = liftF(Clear)

        fun <A> update(key: String, f: (A) -> A) =
            fx.monad {
                val (vMaybe) = get<A>(key)
                !vMaybe.fold(
                    { FreeKVStore.just() }, // ifEmpty
                    { put(key, f(it)) }
                )
                Unit
            }.fix()
    }
}

kvstoreInterpreters.kt

/**
 * Arrow 0.10
 * Get started with Arrow.
 * How to write a Free DSL - Interpreters part.
 */
package gist.arrow.free

import arrow.Kind
import arrow.core.*
import arrow.free.*
import arrow.mtl.State
import arrow.mtl.StatePartialOf
import arrow.typeclasses.Monad

/**
 * Interpret our program in Id
 */
val idInterpreter : FunctionK<ForKVStoreA, ForId> =
    object : FunctionK<ForKVStoreA, ForId> {
        val kvs = mutableMapOf<String, Any?>()
        override fun <A> invoke(fa: Kind<ForKVStoreA, A>): Id<A> {
            val op = fa.fix()
            return when (op) {
                is KVStoreA.Put<*> -> {
                    // business logic...
                    kvs[op.key] = op.value
                    Id(Unit) // business result in Id
                }
                is KVStoreA.Get<*> -> Id(Option.fromNullable(kvs[op.key]))
                is KVStoreA.Delete -> {
                    kvs -= op.key
                    Id(Unit)
                }
                is KVStoreA.Clear -> {
                    kvs.clear()
                    Id(Unit)
                }
            } as Id<A>
        }
    }

/**
 * Interpret our program in State
 */
val stateInterpreter : FunctionK<ForKVStoreA, StatePartialOf<Map<String, Any>>> =
    object : FunctionK<ForKVStoreA, StatePartialOf<Map<String, Any>>> {
        override fun <A> invoke(fa: Kind<ForKVStoreA, A>): State<Map<String, Any>, A> {
            val op = fa.fix()
            return when (op) {
                is KVStoreA.Put<*> -> State { state: Map<String, Any> ->
                    state.k().updated(op.key, op.value as Any) toT Unit
                } // State().modify { it: Map<String, Any?> -> it - op.key + Pair(op.key, op.value) }
                is KVStoreA.Get<*> -> State { state: Map<String, Any> ->
                    state toT state.getOption(op.key).map { it as A }
                } //State().inspect { it : Map<String, Any?> -> Option.fromNullable(it[op.key]) }
                is KVStoreA.Delete -> State { state: Map<String, Any> ->
                    state - op.key toT Unit
                } //State().modify { it - op.key }
                is KVStoreA.Clear -> State { _ : Map<String, Any> ->
                    emptyMap<String, Any>() toT Unit
                } // State().set(emptyMap<String, Any>())
            } as State<Map<String, Any>, A>
        }
    }

/**
 * Interpret our program in IO
 */
val ioInterpreter : FunctionK<ForKVStoreA, ForIO> =
    object : FunctionK<ForKVStoreA, ForIO> {
        val kvs = mutableMapOf<String, Any?>()
        override fun <A> invoke(fa: Kind<ForKVStoreA, A>): IO<A> {
            val op = fa.fix()
            return when (op) {
                is KVStoreA.Put<*> -> IO {
                    kvs[op.key] = op.value
                }
                is KVStoreA.Get<*> -> IO {
                    Option.fromNullable(kvs[op.key])
                }
                is KVStoreA.Delete -> IO {
                    kvs -= op.key
                }
                is KVStoreA.Clear -> IO {
                    kvs.clear()
                }
            } as IO<A>
        }
    }

/**
 *  Convenient function to execute our programs
 */
inline fun <F, A> Free<ForKVStoreA, A>.run(
    interpreter: FunctionK<ForKVStoreA, F>, MF: Monad<F>) =
    this.foldMap(interpreter, MF)

Hi, nice example.

This issue with Free in Kotlin in general is that you can't easily mix different grammars; therefore, in state, Free constructs are not really applicable to real-life projects.

By this you mean, that the inability to combine grammars makes them not useful for real-life projects, or do you also mean using a single grammar (e.g. this KVStore) is currently not recomended for real-lif projects ?

I mean that in a real program, you will quickly run into the need to define more than one algebra. And, Arrow is not suitable for combining these algebras with a Free monad. It is doable with the help of coproducts, but :

• the performance will degradle into the interpreter due to the use of nested structures containing the algebras (Coproducts are not union types in Arrow 0.10)
• Arrow does not provide the full machinery to partially inject algebras in a free monad.

Thx for your feedback

Ok, thx for clarification. Now that Union types are announced (see Chicago Kotlin Usergroup's presentation from Raul), it will be interesting how soon this issue with Free will be improved.
But I have another question: say I want to create some datastructure (List, Traversable, ...) containing the 'instructions' from my Free algebra instead of sequencing them in the (MonadSyntax is it?) block (the argument to fx function).
..similar to mapM with IO in Haskell.

Is this possible with Free / Fx ?

What I want to achieve is, building a program with the algebra programatically with a Kotlin DSL for example, which then gets interpreted by the handler.

But pulling the instructions out of the monadic context probably defeats the purpose in the example of KVStore, because instructions return values that are used by other instructions.. this can't be done if instructions are separate elements in a List.

I don't understand what you mean : the purpose of the AST is to represent programs as trees of computations; and, Free monads allows to interpret this representation.
Of course, you could have independent computations executed in sequence. But, for this use case, it may be better to use parMapN/parTraverse/parSequence (see https://arrow-kt.io/docs/0.10/fx/async/).