Monads are valuable tools for handling various concerns in functional programs. In this article we show how domain-specific languages and the Tagless Final pattern can be utilised to build modular monadic programs.

Domain-Specific Languages and Interpreters

Domain-specific languages (DSLs) are a popular approach for modularising functional programs. A DSL is a set of functions which address a particular concern — this can be anything from an interface to a subsystem to cross-cutting concerns like logging. DSLs are usually layered, i.e. high-level DSLs (for expressing business processes) are built on top of lower-level DSLs (for accessing databases or connecting to remote APIs). In functional programming, DSLs are often called algebras, hinting at the concept’s origin in category theory.

If you are familiar with object-oriented programming, you can consider a DSL an analogy to an interface: The DSL defines the capabilities of a software module, without providing a concrete implementation. In functional programming, the implementation of the DSL is called an interpreter. An interpreter implements each function of the DSL.

Monads and Separation of Concerns

As outlined in the blog post Cooking with Monads, monads provide a way of structuring functional programs. In functional programming, we often use monads to explicitly handle certain aspects (“concerns”) of our program without having to express this aspect in the program code itself. Monads allow us to isolate specific concerns from our business logic, which leads to a better separation of concerns in our programs.

Some examples:

The Reader monad allows to pass a context, for instance a configuration, which all computation steps can access.
The State monad passes state information from one call to the next without the need for mutable data structures in our program code.
The Task monad provides a way to deal with concurrency, side effects and potential errors.

Each of these monads support us in relieving the business logic from some of the responsibility of dealing with the respective concerns.

Monadic DSLs and Tagless Final

In Scala, the individual functions of a DSL typically have monadic return values, which has the benefit that programs can be written as for-comprehensions. The Tagless Final pattern provides a way to declare a DSL in a generic way, without specifying a particular monad. Multiple interpreters can exist for a DSL, every one potentially targeting a different monad.

This approach has various benefits:

When writing a program based on Tagless Final DSLs, the target monad of the program can be changed in the future. This way, new features like parallel computation can be introduced without modifying the program itself.
The DSL can be used with different interpreters. A typical use case is providing an alternative interpreter for testing purposes, using a local data store instead of accessing an external system.
Multiple DSLs can be combined in a single for-comprehension by chosing interpreters for the same target monad.

Our Example

In our example code we will model a DSL called authn which provides functions for registering and authenticating users:

def register(email: String @@ EmailAddress, password: String):
    Either[RegistrationError, User]

def authn(email: String @@ EmailAddress, password: String):
    Either[AuthnError, User]

In case you’re wondering, String @@ EmailAddress is a tagged type, denoting that email is a string with the sole purpose of modelling an e-mail address.

You find the source code for the example application on GitHub.

The package structure looks as follows. We are coupling our code based on functional design, meaning that code with common functionality goes in the same package.

ch.becompany
  authn           Authentication functionality
    domain        Authentication domain code
    Dsl           Authentication DSL
  shapelessext    Extensions to the shapeless library
  shared          Shared code
    domain        Shared domain code
  Main.scala      Our main application

To run the example, execute the following command in the console:

sbt run

Modeling DSLs with Tagless Final

In the Tagless Final pattern, a DSL is modelled as a trait with a single type parameter, which has to be a type constructor with arity 1. We will call this type constructor F[_]. At this moment, it's actually not required that F is a monad. Later on, when implementing an interpreter for our DSL, the target monad of the interpreter will take the place of F.

Let’s model our authentication DSL in this style:

package ch.becompany.authn

trait Dsl[F[_]] {

  def register(email: String @@ EmailAddress, password: String):
      F[Either[RegistrationError, User]]

  def authn(email: String @@ EmailAddress, password: String):
      F[Either[AuthnError, User]]

}

We see that the return values of all DSL functions are wrapped in the container F. In the following program, the compiler infers the type parameter F[_] from the return type of the registerAndLogin function.

package ch.becompany

object Main extends App {

  def registerAndLogin[F[_] : Monad](implicit authnDsl: AuthnDsl[F]):
      F[Either[AuthnError, User]] = {

    val email = tag[EmailAddress]("john@doe.com")
    val password = "swordfish"

    for {
      _ <- authnDsl.register(email, password)
      authenticated <- authnDsl.authn(email, password)
    } yield authenticated
  }

}

The function signature ensures that F is a monad (by requiring the existence of an implicit value of the type Monad[F]). Therefore the functions of our DSL can be used in for-comprehensions. Even at this stage, we don't specify a concrete type for F; the registerAndLogin function could actually be part of a higher-level DSL.

Besides the Monad instance, the function requires an additional parameter: An instance for the authentication DSL (also called an interpreter), typed with the common type F. The parameter is declared as implicit to allow automatic resolution by the compiler; we will look into this in detail when we talk about interpreters.

Interpreters

Now that we have defined the syntax of our DSL in the respective trait, we have to implement the semantics. With the Tagless Final technique, this is done in an interpreter. For each DSL, multiple interpreters can exist; each of them targeting a specific type. Interpreters are typically modelled as type classes, so they can be automatically resolved by the compiler when a DSL is used with the respective target type.

In the beginning we will choose a target type which make it easy to test the concepts in a simple, self-contained program. In a real-world scenario, you would probably follow the same approach: Start with providing easy-to-use interpreters for your DSLs which can be utilised in test cases. This approach is comparable to implementing mocks, with the difference that our interpreter is a full-featured implementation of the DSL.

Later on we can proceed to implementing interpreters for more sophisticated target types covering additional concerns like concurrency and side-effects.

Interpreter for the Authentication DSL

We implement the interpreter in the companion object of the Dsl trait, thereby supporting the implicit resolution mechanism of the compiler.

package ch.becompany.authn

trait Dsl[F[_]] {
  …
}

object Dsl {

  type UserRepository = List[User]

  type UserRepositoryState[A] = State[UserRepository, A]

  implicit object StateInterpreter extends Dsl[UserRepositoryState] {

     override def register(email: String @@ EmailAddress, password: String):
         UserRepositoryState[Either[RegistrationError, User]] =
       State { users =>
         if (users.exists(_.email === email))
           (users, RegistrationError("User already exists").asLeft)
         else {
           val user = User(email, password)
           (users :+ user, user.asRight)
         }
       }

     override def authn(email: String @@ EmailAddress, password: String):
         UserRepositoryState[Either[AuthnError, User]] =
       State.inspect(_
         .find(user => user.email === email && user.password === password)
         .toRight(AuthnError("Authentication failed")))
   }

}

We want to store the registered users in a list, so our UserRepository type is a simple list of users:

type UserRepository = List[User]

We will utilise the State monad for passing the user repository from one DSL function call to the next:

type UserRepositoryState[A] = State[UserRepository, A]

Now we define the StateInterpreter, an interpreter for the authentication DSL targeting the UserRepositoryState monad. Note that the object is declared with the implicit modifier, which makes it visible to the compiler when a DSL interpreter for this target type is requested.

implicit object StateInterpreter extends Dsl[UserRepositoryState] {

   override def register(email: String @@ EmailAddress, password: String):
       UserRepositoryState[Either[RegistrationError, User]] =
     State { users =>
       if (users.exists(_.email === email))
         (users, RegistrationError("User already exists").asLeft)
       else {
         val user = User(email, password)
         (users :+ user, user.asRight)
       }
     }

   override def authn(email: String @@ EmailAddress, password: String):
       UserRepositoryState[Either[AuthnError, User]] =
     State.inspect(_
       .find(user => user.email === email && user.password === password)
       .toRight(AuthnError("Authentication failed")))
   }
}

Running the Program

Now that we have provided an interpreter for our DSL, we can execute the registerAndLogin program which we have implemented in our Main application.

package ch.becompany

object Main extends App {

  def registerAndLogin[F[_] : Monad](implicit authnDsl: AuthnDsl[F]):
      F[Either[AuthnError, User]] = {

    val email = tag[EmailAddress]("john@doe.com")
    val password = "swordfish"

    for {
      _ <- authnDsl.register(email, password)
      authenticated <- authnDsl.authn(email, password)
    } yield authenticated
  }

  val userRepositoryState = registerAndLogin[UserRepositoryState]

  val result = userRepositoryState.runEmpty

  val (users, authenticated) = result.value

  println("Authenticated: " + authenticated)
  println("Registered users: " + users)

}

By calling registerAndLogin with the UserRepositoryState type parameter value, we instruct the compiler to resolve the interpreter – declared as the implicit parameter authnDsl – for the UserRepositoryState target monad:

val userRepositoryState = registerAndLogin[UserRepositoryState]

We use the runEmpty method to pass an empty list of users as the initial state:

val result = userRepositoryState.runEmpty

The runEmpty method returns an instance of the Eval monad, whose computation produces a tuple consisting of the final state (in our case the user repository containing all registered users) and the return value of the program (in our case the authentication result). Now we can finally extract these values using the value method of the Eval monad, and print the result:

val (users, authenticated) = result.value
  println("Authenticated: " + authenticated)
  println("Registered users: " + users)
}

The output of our program looks as follows:

Authentiated: Right(User(john@doe.com,swordfish))
Registered users: List(User(john@doe.com,swordfish))

Next Steps: Combining Multiple DSLs

To support combining calls from different DSLs in a for-comprehension, all of these functions must return their values in the same monad.

In many cases it is possible to choose a monad which addresses all required concerns, typically side-effects and error handling. Examples are the Task type from the ScalaZ library or the IO type from the cats-effect library.

But to find a generic approach to deal with this restriction actually proves to be quite challenging. One possible solution is using Free monads, for example the Eff monad; this approach which will be presented in an upcoming article.

Blog

Structuring Functional Programs with Tagless Final

Andreas Jim