Structuring Functional Programs with Tagless Final
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.
Readermonad allows to pass a context, for instance a configuration, which all computation steps can access.
Statemonad passes state information from one call to the next without the need for mutable data structures in our program code.
Taskmonad 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.
In our example code we will model a DSL called
authn which provides functions for registering and authenticating users:
In case you’re wondering,
String @@ EmailAddress is a tagged type, denoting that
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.
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:
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
Let’s model our authentication DSL in this style:
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
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
registerAndLogin function could actually be part of a higher-level DSL.
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.
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.
We want to store the registered users in a list, so our
UserRepository type is a simple list of users:
We will utilise the
State monad for passing the user repository from one DSL function call to the next:
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.
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
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:
We use the
runEmpty method to pass an empty list of users as the initial state:
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:
The output of our program looks as follows:
Registered users: List(User(firstname.lastname@example.org,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.
- Optimizing Tagless Final — Saying farewell to Free from the Typelevel blog
- Exploring Tagless Final pattern for extensive and readable Scala code from the scalac team blog
- Free and tagless compared — how not to commit to a monad too early by Adam Warski
- Introduction to Tagless final from the Beyond the Lines blog
Thank you very much for reading! Please leave your comments below, and don’t hesitate to contact me at email@example.com if you have further questions.