Copyright © 2020, Philippe Bastiani.
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.
Λ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.
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.
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
Freeto automatically for comprehend in a stack-safe way. So using this pattern, we avoid stack overflows. Here,stackSafeensures the stack safety overEithermonad.
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
stackSafeextensions for Option, Id, Eval, and so on...
NOTE : the Kotlin's Standard Library with the use of
tailrecmodifier proposes a standard way to implement this simple recursion. However, this technique could be used for recursive functions that are not eligible for thetailrecmodifier.
Let’s imagine that we want to create a DSL to act on a key-value store...
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.
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.
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 :
Ais the type of the content,Shas 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 !
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.
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 anId).
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
mutableMapto 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.
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
interpreteris our parameterized interpreter,MFholds 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)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.
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, thebind()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.
- Λ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
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.
Hi, nice example.
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 ?