Exploring Tagless Final pattern for extensive and readable Scala code

In this post, I will try to share with you all a functional pattern I stumbled upon recently – Tagless Final. This pattern tries to address a vital problem for every software engineer: how to make sure the programs we write are correct?

I will try to explain how Tagless Final works and how it can be applied in practice while keeping things down to earth and as practical as possible. Of course, I didn’t invent it from scratch, but I would like to share what I’ve learned and maybe popularize this solution.

Kudos to Oleg Kiselyov for describing the pattern in depth and John De Goes for inspiring me to write this post.

Let’s get started.

Introducing Tagless Final

Tagless Final allows you to build a subset of the host language which is sound, typesafe, and predictable. When designed properly this subset makes it easy to write correct programs and hard to write incorrect ones. In fact, invalid states can’t be expressed at all! Later, the solution written in the hosted language is safely run to return the value to the hosting language.

For us, Scala will be our hosting language, but the pattern also applies to other ecosystems. Tagless Final can be seen as a composite pattern, it builds on top of or is inspired by many other patterns like type classes or Free monads. So you might spot some similarities.
On a conceptual level, our Scala implementation has 3 distinct parts:

• Language, that defines a subset of operations that the hosted language allows
• Bridges, helpers that express Scala values and business logic in the Language
• Interpreters, dual to Bridges run logic expressed as the Language and get the final value (This is not the official lingo, but I will be using this naming here to make explanations simpler.)

Let’s explore this with a simple example – basic math. You can find the whole code in the repo.

Language

Language is the heart of our DSL. It defines what can we do with the hosted language.

https://gist.github.com/anonymous/e7b8eb86988cb6217a1804f26a965591

Above we defined a few basic operations. The trait type definitely caught your eye. The Language is parameterized by a Wrapper type which itself has an internal type. Both type parameters will be useful for us later. Wrapper will allow us to change the “package” on which we operate, while the type of the Wrapper makes sure our API is typesafe.

Consider:

https://gist.github.com/anonymous/35b454f573225ee2d6c55ec0129e214b

These methods are called with or return Wrapper[String] in contrast to those above. The consequence is that you cannot call toUpper on an Int, which makes the API much harder to use incorrectly. In fact, to combine those two methods sets we would need a method to covert between the types, as the one below:

https://gist.github.com/anonymous/985ab776eebb02b0ba1578ce2e3d03a9

Fairly standard stuff: one method to create  Wrapper[X] values and a set of operations on those values.

Bridges

Having a Language in place, we now need to “bridge” the gap between the hosting language (Scala) and our hosted language. Here we will build an interface for a generic bridge to do just that:

https://gist.github.com/anonymous/daf384041077b575bcd8c5318afb4991

As you can see it takes an implicit Language to build expressions and after calling apply returns a result wrapped in the desired Wrapper class. Although he trait might seem confusing, taking a look at some examples hopefully will clear things up:

https://gist.github.com/anonymous/229bee5c8eda4c88feda1849d6900566

Our bridges are really simple. They take a single Scala value number: Int and convert it into an expression in our language. Since we are operating only on given L we cannot represent incorrect logic, like incrementing a String. This approach for bridges is “fine-grained” – we build only simple expressions. But can easily combine those simple expressions into bigger ones:

https://gist.github.com/anonymous/70b31e2c5a9f525ec8e3b4cc9b70e996

or just follow a “coarse grained” approach where we express bigger algorithms straight away

https://gist.github.com/anonymous/025fda3c45603a5c18c88bed625daede

Interpreters

We have defined what our meta-language can do. We expressed our problems in the language. Now it’s time to make it run. For instance with an interpreter like this:

https://gist.github.com/anonymous/20a5de1c0c2d569251cad332e91cd693

First, we need to define a Wrapper for us. Here we don’t need anything fancy so we will just operate on plain values. Our NoWrap will literally default to the type it was parameterized with. After this is done, we simply need to implement our interface. Nothing fancy here.

Note: As David Barri pointed out in his comment below. The NoWrap/Id type aliases might be tricky to use in production code, due to their eager evaluation and other concerns. Here we stick to it only for simplicity.

Having all 3 items in place we can run them together:

https://gist.github.com/anonymous/d0b73f9d823737d47a706b25dbe51014

Simple enough, but why should we bother with the Wrappers in the first place? If you ever played with Free monads you probably know why – to build multiple, specialized interpreters. To give you an example, let’s build another one. This time we will build a utility interpreter that will be helpful in later stages. The new interpreter will pretty-print our math expressions in a Lisp-like syntax, so we can easily spot mistakes in our code.

https://gist.github.com/anonymous/5accc12d5d05594adc086716fbb2258c

https://gist.github.com/anonymous/cab668011f9180c1a8d722f00d80e2d9

So far, so good. To reiterate: we defined the possible operations in a form of a Language trait, we defined helpers to convert Scala values into expressions using Language, we implemented our meta-language and run the code. Every element above is just plain Scala, but thanks to the way it is composed we achieve a few nice properties.

Benefits

Extensibility

You are probably familiar with the expression problem, one of the classical concepts in computer science. Long story short: having an interface and a set of implementations of that interface, we want to be able to easily add operations to the interface and new interface implementations.

Ideally, because usually, OOP makes it hard to add interface methods but easy to add implementations. In FP, on the other hand, it’s easy to add new methods, but harder to add implementations.

This is a big deal for every programmer, even though we might not think about it every day. No useful software is static – written once and left unchanged for years. Our software needs to evolve, hence extensibility is an important factor when picking patterns.

Tagless Final finds itself closer to the FP part of the extensibility spectrum. Which is ok in this case. We have tools to easily and safely modify our Language, which (I presume) is the more common operation. Creating interpreters might be harder, I agree, but the cool thing is that you don’t always need to update them. Your change can be made in a non-breaking way (or at least keeping the damage to a minimum).

To explain how this works, let’s go back to the example from before. We had one math operation – add, but let’s say we wanted another one called multiply. We could just go and add the new method to Language. That would be really simple, but unfortunately also caused a ripple effect throughout the system as you would have to update every interpreter that uses the language. Not good. So let’s do something else instead.

https://gist.github.com/anonymous/db9f98a333ac343e865516f92ecad419

Conceptually what we did is we created a child language, which has the whole API of it’s parent, but also few new things. From this point on we can just do the same things we did for the parent.

Define a bridge:

https://gist.github.com/anonymous/0a9902942ba058aa545503b642af30ab

Build an interface:

https://gist.github.com/anonymous/83a7348a8f359db6cfb0ad79009c53c1

As you can see it required a bit of writing (could be less if we delegated/inherited in interpretWithMul the definition). But the good part is that at no point we had to touch the older part – it runs as it did before.

Composability

Another interesting property that emerges from this pattern is composability. The ability to combine small parts into bigger, more powerful entities with new properties.

Let’s discuss it in a simple example. Using our original language we were able to express logic like this:

https://gist.github.com/anonymous/a4f11b10bf8f966d8ae9d56f5dc9194d

The code compiles just fine, but there’s something we could do better – performance. 10 + (((0 + 1)+1)+1) is not the optimal form for this operation. 10 + (0 + 3) or simply 10 + 3 would be much simpler and more performant.

Of course here the difference is not huge, but if our language would be doing API calls or DB queries the differences would be much bigger. Conceptually we would like to simplify our expression into a more convenient form. Here we will do that naively for one case – flattening many nested inccalls into a single add.

But how to do that? The tagless final approach brings us 3 “moving parts”: Language, Bridge, and Interpreter. We cannot add this optimization to the Language itself, as this could mean that our DSL would be in constant flux. And, as we mentioned above, we would prefer not to touch the once-defined language.

Adding the optimization into bridges is plausible, but unfortunately, at call time they don’t know much about the shape we are building. Even worse, users of our language can build their own bridges which makes distributing the improved version harder. We are left with just one place – an interpreter. We will have to figure something out, so our end users will be able to opt-in to the optimization easily when they find it helpful.

One interesting solution to this problem is interpreter composability. To recap: the idea of interpreters is that they take expressions in our custom language and turn that into plain Scala values. So, if we would write a specific interpreter that takes an expression, and turns it into plain Scala, but that result would happen to be a bridge, then we could interpret his output later on.

In short: instead of interpreting into (say) a Scala Int, we will interpret into a rewritten interpretation.

https://gist.github.com/anonymous/94d63f7f7aeff04180a30bca48d3199e

Of course, the code is very simplistic, but you get the idea. During the interpretation process, we can collect more detailed information about the expression and make decisions based on that.

Here’s the output:

https://gist.github.com/anonymous/dcca26fd8db396c29c9d18ab018f536e

As you can see the expression has been rewritten into a different form. Later, this new form can be interpreted as usual.

Real-life example

Having explained the pattern, let’s build something that solves a more typical problem. Our toy example will use Slick to make simple queries to the database.

We will start from the language, where we will define some basic operations on our Person case class, together with some helper classes to pass data around and make the API more typesafe.

https://gist.github.com/anonymous/09087dc2952ac20eb71fc711a886bc41

Then we follow the routine that gets us into the Slick interpreter

https://gist.github.com/anonymous/d0f868d3c7d74efe9ad1c0ce245304f2

Our interpreter doesn’t do anything fancy – it keeps the table definitions internally, then between calls state is accumulated in a form of QueryObj being passed around. When we reach the final point – run, the query is being executed to retrieve the data.

https://gist.github.com/anonymous/47950508844fe8791e331f479a06347d

And tada, we used Tagless Final with Slick.

Summary

And that’s it. We applied the pattern in Scala. Wrote a code that can be extended and composed with ease.

I hope this post inspired you to take a look at Tagless Final on your own, the same way I was inspired. Thanks for the time and keep on hacking!

Links

• Quark: A Purely-Functional Scala DSL for Data Processing & Analytics
• Typed Tagless Final Interpreters
• From Object Algebras to Finally Tagless Interpreters
• Introduction to Tagless final

Do you like this post? Want to stay updated? Follow us on Twitter or subscribe to our Feed.

See also

• Overview of free monad in cats
• def hello = macro world
• When old-school developer goes freestyle
• Build your own Kafka in ZIO – Queues & Fibers
• Learning Scala macros with Each Library