# The Evolution of a DSL to Tagless Final

## Introduction

I wrote this article to help others who don’t understand why Final Tagless is important, and to guide in how to reason about a DSL in a way that makes Final Tagless an appropriate solution. I was stuck in a situation when, once I was learning about Final Tagless, I didn’t understand how it should be applied to my projects or if it even could. This article mainly aligns with the process I went through to solve these issues.

Side notes are aimed toward readers familiar with cats and programming with higher kinded types.

If you are more familiar with “Final Tagless Algebra” than “Final Tagless Language,” note that I will be more commonly using the latter, even though the former is more correct.

If you already understand what a DSL is and how to write programs using monad composition, you can skip to An Overview of Final Tagless.

### What is a DSL?

DSL stands for “Domain-Specific Language.” While the literal definition encompasses languages like PostScript, made for printing, and Verilog, made for hardware, a more general and commonly used definition includes any set of operations (Turing-completeness disregarded).

A common example of a DSL is a calculator:

We can very easily perform arbitrary operations with our calculator:

### Monads

A Monad is any sort of data structure or container that defines these two operations:

Various other behaviors can be derived from these definitions:

For example, `List`

is a Monad:

So is `Option`

:

#### The State Monad

The State Monad describes a transformation over some state, `S`

, with a result
of `A`

:

Note that State is a Monad on `A`

, not on `S`

!

To prove that State is a Monad, we can write definitions for `pure`

and
`flatMap`

:

#### Purity and Side Effects

A concept that comes up often in functional programming is that of purity, because it not only helps compilers optimize programs but helps humans understand what certain functions can do.

One part of purity is referential transparency. For example, with

it could be said that `myValue`

is referentially transparent, because it
returns the same value for the same input (similar to the concept of a
mathematical function). However, it could not be said with

that `myValueImpure`

is referentially transparent, because it will return
different values for the same input.

The second part of purity is whether a function causes a side effect. A side effect is any call/function/procedure that changes or requires external state. Examples of side effects are:

- Printing a line
- Reading a file
- Making a web request
- Calling another executable

#### The State Monad as Computation

Let’s create a Monad, `IO`

, that is a `State`

on the `RealWorld`

:

Here, `RealWorld`

is entirely hypothetical, and we will have a hypothetical
“macro” called `impure`

that turns a codeblock which returns `A`

into one which
returns `IO[A]`

. For example:

We also have a hypothetical `IOApp`

that can pass an initial `RealWorld`

to any
`IO`

:

`puts`

, `gets`

, and `run`

are all pure, because for the same `RealWorld`

,
they’ll behave the same way and output the same value!

## An Overview of Final Tagless

Final Tagless is composed of three parts:

- The
`Language[Wrapper[_]]`

- The
`Interpreter <: Language[α]`

- The
`Program[Result]`

Let’s take an example where we can increment numbers:

This language enables two things: lifting a Scala `Int`

into a wrapped `Int`

,
and incrementing a wrapped `Int`

. We can implement this language purely like
so:

We can also create an interpreter that does not calculate anything, but instead records our operations in string form:

Side note: Any

`Language`

where it is possible to implement an interpreter with`Id`

as its`Wrapper`

also has an implementation for any Monad as its`Wrapper`

via`pure`

and`map`

/`flatMap`

/`mapN`

.

Lastly, we can model programs that take arbitrary interpreters:

And construct them like so:

We can easily apply any interpreter to a program:

## The Evolution

Let’s write a simple calculator DSL. The first step to writing a DSL is to handle the simplest case:

This calculator is great, but it can’t output Lisp. Let’s fix that by building another calculator:

Well, we have a calculator that outputs Lisp, but its not very interchangable
with our normal calculator. It takes a lot of effort to interchange them, and
we can put non-numbers into `LispCalculator`

:

### The First Step

The first problem is that calculators don’t share behavior. We want to have the ability to define calculators in a generic way:

We can copy over our old pure calculator, as well as our Lisp calculator:

However, we run into two new problems with generic computation. It’s impossible
to define a return type for `calculate`

that lets the `Calculation`

both
perform arithmetic as well as `show`

, and its impossible for `calculate`

to do
anything in the first place as it doesn’t know how to make values of type `A`

or `S`

:

### The Second Step

The second problem is that that there’s no way to define a generic computation.
We can solve this by making our calculations and calculator taking some sort of
wrapper type that handles arithmetic, `show`

, and any types that may be added
in the future, as well as defining a calculator method to lift arithmetic
values:

This is now a simple Final Tagless DSL! By having the basic goals of generic computation and generic interpretation, we’ve gone from an incredibly basic DSL to a still basic, but incredibly powerful one.

Implementing calculators and calculations is super easy, and in fact we can still copy over most of our other code:

#### Using IO in Calculator

Say we want to run calculations by doing web requests. That’s a side effect, so we need to do it with IO:

The beauty of using IO for this is that it keeps its properties, even when passed through a Tagless DSL:

## Summary

Always start with the most basic version of your DSL. Then try to generify it with a hodge-podge of type variables, then see if you can move that to a wrapper style.

As an exercise, I recommend creating a DSL that handles a simple party game, with interpreters for both evaluating the state of the party game as well as outputting a log of the state changes. For example, Uno might look something along the lines of:

Side note: another good exercise is to take the Calculator code here and make a

`MonadCalculator`

that works for any`M: Monad`

.