[arrow-kt] Free programs in Kotlin. Additional notes.

# ArrowFreePrograms.md

Free programs in Kotlin - GADT & ADT Alternatives

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.

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.

A console typed DSL

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:

• tell to write output to the console,
• ask to 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 Λrrow Free Monad

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 :

1. we build an algebra describing our logic domain.
2. we declare programs with this algebra (at this point the programs are not executable). The program thus built is injected into a Free monad.
3. 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:

• Suspend retains a step of a computation that you want to execute later,
• Pure just contains a value to be returned,
• FlatMapped defines 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 :
The liftF method gives us the possibility to inject a computation into the Free monad.
The roll, defer and other derived methods from flatmap allow 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 where S & A are two parametric types):

• S is the type of the container.
• A is 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 implementation ConsoleF<A> from an abstract Kind<ForConsoleF, A> simply invoking the fix() 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: FreeMonad in 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:

• Tell data class is associated to a tell command.
• Free#liftF method is used to inject any ConsoleF<?> (i.e. a Kind<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 f will be used to inject an interpretation of the DSL grammar.
• The parameter MM will 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 Λrrow Monad Comprehension

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 a FreeMonad instance. 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 overlying fx block).
• the final fix() call gives us a concrete implementation Free<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.

Full implementation - The GADT 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 an IO. And, we can unwrap this result with the IO#unsafeRunSync method.

A drawback of this solution is that the Kotlin compiler fails to properly infer the return of the invoke method... So, we must explicitly specify the return type of our implementation (as IO<A>).

Full implementation - A Kotlin type safe way

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 invoke method.

This implementation adds type safety.

A drawback of this solution is that the one requires additional boilerplate.

Summary

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.

ArrowFreeProgram_adt.kt

/**
 * Arrow 0.10
 * A Free programs without GADT.
 */
package gist.arrow.free

import arrow.Kind
import arrow.core.FunctionK
import arrow.core.identity
import arrow.free.Free
import arrow.free.extensions.FreeMonad
import arrow.free.fix
import arrow.free.foldMap
import arrow.fx.ForIO
import arrow.fx.IO
import arrow.fx.extensions.io.monad.monad
import arrow.fx.fix
import arrow.higherkind
import gist.arrow.free.ConsoleF.Companion.ask
import gist.arrow.free.ConsoleF.Companion.tell

/**
 * DSL : actions together with a continuation pattern.
 */
@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>()

    /**
     * Inherit from FreeMonad to make life easier later
     */
    companion object : FreeMonad<ForConsoleF> {
        /**
         * Smart constructors to make life easier
         */
        fun ask() = Free.liftF(Ask(::identity))
        fun tell(str: String) = Free.liftF(Tell(str, ::identity))
    }
}

/**
 * Our program using the inherited features from the companion object to get access to binding
 */
val prog = ConsoleF.fx.monad {
    tell("What is your name?").bind()
    val input = ask().bind()
    tell("Hello $input").bind()
}.fix()

fun main() {
    /**
     * Interpret our program in IO
     */
    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()
}

ArrowFreeProgram_gadt.kt

/**
 * Arrow 0.10
 * A Free programs with the help of a GADT.
 */
package gist.arrow.free

import arrow.Kind
import arrow.core.FunctionK
import arrow.free.Free
import arrow.free.extensions.FreeMonad
import arrow.free.fix
import arrow.free.foldMap
import arrow.fx.ForIO
import arrow.fx.IO
import arrow.fx.extensions.io.monad.monad
import arrow.fx.fix
import arrow.higherkind
import gist.arrow.free.ConsoleF.Companion.ask
import gist.arrow.free.ConsoleF.Companion.tell

/**
 * DSL : actions together with a GADT.
 */
@higherkind
sealed class ConsoleF<A> : ConsoleFOf<A> {
    object Ask : ConsoleF<String>()
    data class Tell(val str: String) : ConsoleF<Unit>()

    /**
     * Inherit from FreeMonad to make life easier later
     */
    companion object : FreeMonad<ForConsoleF> {
        /**
         * Smart constructors to make life easier
         */
        fun ask() = Free.liftF(Ask)
        fun tell(str: String) = Free.liftF(Tell(str))
    }
}

/**
 * Our program using the inherited features from the companion object to get access to binding
 */
val prog = ConsoleF.fx.monad {
    tell("What is your name ?").bind()
    val input = ask().bind()
    tell("tell $input").bind()
}.fix()

fun main() {
    /**
     * Interpret our program in IO
     */
    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()!!
                }
                is ConsoleF.Tell -> IO {
                    println(op.str)
                }
            }  as IO<A> // this cast is required !
        },
        IO.monad()
    ).fix().unsafeRunSync()
}