Instantly share code, notes, and snippets.

# PhBastiani/# ArrowFreePrograms.md

Last active February 5, 2024 02:59
Show Gist options
• Save PhBastiani/26d8734ff33001cb0304df337ea936a1 to your computer and use it in GitHub Desktop.
[Arrow-kt] For-Comprehension Free Monads in Kotlin

# For-Comprehension Free Monads in Kotlin - Mini Howto

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.

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>  =
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)
// 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 ?

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> {
}```

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> =
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
!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<*> -> {
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> = ...

// 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>>> = ...

// 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> = ...

// 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.

## 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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /** * 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 = object : FunctionK { val kvs = mutableMapOf() override fun invoke(fa: Kind): Id { 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 } } /** * Interpret our program in State */ val stateInterpreter : FunctionK>> = object : FunctionK>> { override fun invoke(fa: Kind): State, A> { val op = fa.fix() return when (op) { is KVStoreA.Put<*> -> State { state: Map -> state.k().updated(op.key, op.value as Any) toT Unit } // State().modify { it: Map -> it - op.key + Pair(op.key, op.value) } is KVStoreA.Get<*> -> State { state: Map -> state toT state.getOption(op.key).map { it as A } } //State().inspect { it : Map -> Option.fromNullable(it[op.key]) } is KVStoreA.Delete -> State { state: Map -> state - op.key toT Unit } //State().modify { it - op.key } is KVStoreA.Clear -> State { _ : Map -> emptyMap() toT Unit } // State().set(emptyMap()) } as State, A> } } /** * Interpret our program in IO */ val ioInterpreter : FunctionK = object : FunctionK { val kvs = mutableMapOf() override fun invoke(fa: Kind): IO { 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 } } /** * Convenient function to execute our programs */ inline fun Free.run( interpreter: FunctionK, MF: Monad) = this.foldMap(interpreter, MF)

### clojj commented May 26, 2020

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.

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.

### PhBastiani commented Jun 2, 2020

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/).