Copyright © 2020, Philippe Bastiani.
These are additional notes to this GIST : For-Comprehension Free Monads in Kotlin - Mini Howto.
Disclaimer: This GIST assumes that you are roughly familiar with the concept of Free monad.
Λ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.
Let’s imagine we are developing a console program, which needs to read input from the console, and write output to the console.
We could implement a DSL offering the following two entry points:
tellto write output to the console,askto read input from the console.
With this DSL it becomes easy to write our program. E.g. this program asks you for your name, then prints out “Hello” followed by your name.
tell("What is your name?")
val input = ask()
tell("Hello $input")As additional requirements, we want
- to have a way to work with Free Monad,
- to enable the fx/comprehension syntax of Λrrow.
Basically, a Free Monad is functional data structure where we represent stateful computations as data.
In Λrrow, Monad Comprehensions add facilities to describe a sequence of actions in a monadic context.
The core idea of Free monads is to represent stateful computations as data, and run them.
The Free monads also offer the possibility of clearly separating the declaration of computations from their interpretations.
The monadic behaviour of Free monads gives us a pure way to represent, manipulate and compose computations. A Free program will be the result of this combinaison.
We can get a Free monad from any algebra without any assumption about it.
And, a Free program can be declared as an Abstract Syntax Tree (AST).
In other words, a Free program can be represented like a tree where each node is the declaration of a computation. And, where each computation is declared devoided of any interpretation.
Λrrow provides several optimizations that result in a stack-safety for programs using Free.
The development of an embedded DSL (domain-specific language) is one of the use cases of this monad.
In practice, the development of a Free program is done in three steps :
- we build an algebra describing our logic domain.
- we declare programs with this algebra (at this point the programs are not executable). The program thus built is injected into a Free monad.
- finally, we launch the execution on demand our program.
NOTE: a Free program can be executed one or several times with separate interpreters. Regarding the Free monad, the interpreter, and, the computation context are parameters to be provided when the programs are to be executed.
Let's look at the source code of Free in Λrrow. Free monads are declared as Higher Kinded Type (HKT):
@higherkind sealed class Free<S, out A> {}
data class Pure<S, out A>(val a: A) : Free<S, A>()
data class FlatMapped<S, out A, C>(val c: Free<S, C>, val fm: (C) -> Free<S, A>) : Free<S, A>()
data class Suspend<S, out A>(val a: Kind<S, A>) : Free<S, A>()In short:
Suspendretains a step of a computation that you want to execute later,Purejust contains a value to be returned,FlatMappeddefines a way to continu the computation.
NOTE: Λrrow provides convenient methods to act on the Free monad... And, you should never directly act on
Pure,FlatMapped&Suspend:
TheliftFmethod gives us the possibility to inject a computation into the Free monad.
Theroll,deferand other derived methods fromflatmapallow us to chain computations.
INFO: Λrrow represents the concept of type constructors using higher kinds.
Kind<S, A>is an interface to represent the type S<A> (feature not supported by the Kotlin compiler whereS&Aare two parametric types):
Sis the type of the container.Ais the type of the content,
So basically, a Free program is a monadic combinaison of Free<S, ?> nodes, where S is any algebra.
Let’s take a look at our Console DSL: we start by building our algebra...
ConsoleF will be our user defined structure describing the I/O events; and, it should be declared as type constructor as follows:
@higherkind
sealed class ConsoleF<A> : ConsoleFOf<A> {
companion object : FreeMonad<ForConsoleF> {
fun ask() : Free<ForConsoleF, String> = TODO()
fun tell(str: String) : Free<ForConsoleF, Unit> = TODO()
}
}The ConsoleF<A> sealed class should
- be annotated with
@higherkind, - extend
ConsoleFOf<A>(see below: this is the Λrrow Kind type), - provide a
companion object.
Behind the scene, Λrrow generates magic code for us to emulate Higher Kinded Types :
class ForConsoleF private constructor() { companion object }
typealias ConsoleFOf<A> = arrow.Kind<ForConsoleF, A>
typealias ConsoleFKindedJ<A> = io.kindedj.Hk<ForConsoleF, A>
inline fun <A> ConsoleFOf<A>.fix(): ConsoleF<A> = this as ConsoleF<A>NOTE: for a given concrete type
A, we get the specific implementationConsoleF<A>from an abstractKind<ForConsoleF, A>simply invoking thefix()method (i.e.Kind<F, A>.fix()->F<A>).
We retrieve the entry points previously used in the imperative code.
But here, ask & tell are smart constructors returning instances of Free.
NOTE:
FreeMonadin the declaration of the companion object will allow us to work in a monadic style with our DSL.
Hereafter, is an example of chaining 3 actions:
ConsoleF.tell("What is your name?")
.flatMap { ConsoleF.ask() }
.flatMap { input : String -> ConsoleF.tell("Hello $input") }Note that for the moment, ConsoleF<A> is an empty shell. In particular, we will have to define the elements of our algebra.
There are several ways to define our algebra. For example:
// A GADT as algebra
@higherkind
sealed class ConsoleF<A> : ConsoleFOf<A> {
data class Tell(val str: String) : ConsoleF<Unit>() // A String as input / an Unit as output.
...
companion object : FreeMonad<ForConsoleF> {
fun tell(str: String) : Free<ForConsoleF, Unit> = Free.liftF(Tell(str))
...
}
}or
// A simple ADT as algebra
@higherkind
sealed class ConsoleF<A> : ConsoleFOf<A> {
data class Tell<A>(val str: String, val cont: (Unit) -> A) : ConsoleF<A>() // A String as input / an Unit as output.
...
companion object : FreeMonad<ForConsoleF> {
fun tell(str: String) : Free<ForConsoleF, Unit> = Free.liftF(Tell(str, ::identity))
...
}
}The elements of our algebra are declared as sealed's subtypes (e.g. here Tell). In the two cases:
Telldata class is associated to atellcommand.Free#liftFmethod is used to inject anyConsoleF<?>(i.e. aKind<ForConsoleF, ?>) into the Free monad.
But note, we used 2 different ways to declare the inputs / outputs of our actions.
Later in this GIST, we will propose two complete implementations based on ADT / GADT.
Finally, our Free program will be executed, in a stack-safe way. This can be easily done using the Free#foldMap method:
fun <M, S, A> Free<S, A>.foldMap(f: FunctionK<S, M>, MM: Monad<M>): Kind<M, A> = ...Internally, Free#foldMap recursively traverses / interprets the steps of our program :
- The parameter
fwill be used to inject an interpretation of the DSL grammar. - The parameter
MMwill be used as a monadic container to hold the computations.
The FunctionK#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.
For example, if we use a FunctionK<ForConsoleF, ForIO> aka a ConsoleF<A> ~> IO<A> as interpreter we should get a IO<?> as result of our program.
The core idea of Monad Comprehensions is to combine imperative code with monadic style.
Λrrow provides a lightweight Monad Comprehension syntax; and, working with our DSL will be a lot nicer.
Let's resume our imperative program :
tell("What is your name?")
val input = ask()
tell("Hello $input")We have seen that we can represent this program in monadic manner:
ConsoleF.tell("What is your name?")
.flatMap { ConsoleF.ask() }
.flatMap { input : String -> ConsoleF.tell("Hello $input") }NOTE: the companion object of
ConsoleF<A>has been defined as aFreeMonadinstance. This enables the Monad Comprehension syntax.
So, we could rewrite our program as follows:
ConsoleF.fx.monad {
tell("What is your name?").bind()
val input = ask().bind()
tell("Hello $input").bind()
}.fix()Great, we write a sequential chain of actions in a single fx block !
When executed :
- the
bind()calls execute/unwrap effects locally (i.e. in the context of the overlyingfxblock). - the final
fix()call gives us a concrete implementationFree<ForConsoleF, Unit>.
Behind the scene, Λrrow unstacks/chains the sequence 'tell -> ask -> tell' of our program.
INFO: internally, the Kotlin Coroutines are used.
INFO: Λrrow provides 3 syntaxes which can be used in fx blocks:
- a basic destructuring syntax (e.g.
val (one) = just(1)),- shortcut syntax with the ! modifier (e.g.
val two = !just(one + 1)),bind()call (e.g.val three = just(one + two).bind()).But, please note that the bind() syntax should be the preferred way.
Let's build our algebra using the method exposed in this GIST.
Here is a possible encoding for our typed DSL:
@higherkind
sealed class ConsoleF<A> : ConsoleFOf<A> {
object Ask : ConsoleF<String>()
data class Tell(val str: String) : ConsoleF<Unit>()
companion object : FreeMonad<ForConsoleF> {
fun ask() = Free.liftF(Ask)
fun tell(str: String) = Free.liftF(Tell(str))
}
}We define ConsoleF<A> as a Generalized algebraic data type (GADT); and, each sealed's subtype is lifted into a Free monad.
For each basic element of DSL grammar
- we translate the main actions into sealed's subtypes,
- we explicitly write down the types of the constructors:
- the input parameters are defined in the constructors,
- the output types is provided as parameters of the sealed's subtype.
We've added some smart constructors (ask & tell) thanks to the convenient Free#liftF method.
Note : in the companion object, we could also define additional entries by combining ask & tell. For example:
fun askName() = tell("What is your name?").flatMap { ask() }Finally, we can implement interpreters for our algebra; and, execute our Free program:
prog.foldMap(
object : FunctionK<ForConsoleF, ForIO> {
override fun <A> invoke(fa: Kind<ForConsoleF, A>): IO<A> = when (val op = fa.fix()) {
is ConsoleF.Ask -> IO {
readLine()!! // business logic
}
is ConsoleF.Tell -> IO {
println(op.str) // business logic
}
} as IO<A> // this cast is required !
},
IO.monad()
).fix().unsafeRunSync()Here, we choose to execute our computations in an IO context :
- The
FunctionK<ForConsoleF, ForIO>object is our IO interpreter, - Each business logic is encoded into an
IO. - The call of
Free<ForConsoleF, Unit>#.foldMap(...).fix()returns a concrete result embedded into anIO. And, we can unwrap this result with theIO#unsafeRunSyncmethod.
A drawback of this solution is that the Kotlin compiler fails to properly infer the return of the
invokemethod... So, we must explicitly specify the return type of our implementation (as IO<A>).
To remove the type checking issue, Jannis proposes the following encoding.
First at all, we define ConsoleF as a simple Abstract data type:
@higherkind
sealed class ConsoleF<A> : ConsoleFOf<A> {
data class Ask<A>(val cont: (String) -> A) : ConsoleF<A>()
data class Tell<A>(val str: String, val cont: (Unit) -> A) : ConsoleF<A>()
companion object : FreeMonad<ForConsoleF> {
fun ask() = Free.liftF(Ask(::identity))
fun tell(str: String) = Free.liftF(Tell(str, ::identity))
}
}We keep the definition the parameterized sealed class ConsoleF<A>. But,
- the sealed's subtypes do not depend on the return type of the encoded element.
- the return types of the encoded elements are injected in the type constructors.
See below : The cont function will be used in the interpreter to propagate the result of our operations
(here, the so called Continuation-passing style is used).
So, a simple ::identity function is useful here !
Finally, we can implement interpreters for our algebra; and, execute our Free program:
prog.foldMap(
object : FunctionK<ForConsoleF, ForIO> {
override fun <A> invoke(fa: Kind<ForConsoleF, A>): IO<A> = when (val op = fa.fix()) {
is ConsoleF.Ask -> IO {
readLine()!!
}.map(op.cont) // continuation of the computation...
is ConsoleF.Tell -> IO {
println(op.str)
}.map(op.cont) // continuation of the computation...
} // No cast here !
},
IO.monad()
).fix().unsafeRunSync()The interpreter is similar to the previous one. but:
- additional mapping are required to embed the results into
IO. - the Kotlin compiler succeeds in inferring the return of the
invokemethod.
This implementation adds type safety.
A drawback of this solution is that the one requires additional boilerplate.
In this GIST we've proposed two approaches for coding a Free DSL:
- The first one uses a classic GADT, and due to a limitation of the Kotlin compiler does not provide full type checking.
- The second one with a simple ADT adds type safety but is more verbose.
In all cases, the main issue with Free in Kotlin is that you can't easily mix different grammars; therefore, in state, Free constructs are not really applicable to real-life projects.