博客

Revisiting Tagless Final Interpreters

Tageless Final interpreters are an alternative to the traditional Algebraic Data Type (and generalized ADT) based implementation of the interpreter pattern. This document presents the Tageless Final approach with Scala, and shows how Dotty with it’s recently added implicits functions makes the approach even more appealing. All examples are direct translations of their Haskell version presented in the

Typed Tagless Final Interpreters: Lecture Notes

(section 2).

The interpreter pattern has recently received a lot of attention in the Scala community. A lot of efforts have been invested in trying to address the biggest shortcomings of ADT/GADT based solutions: extensibility. One can first look at cats’


Inject

typeclass

for an implementation of


Data Type à la Carte


ideas. The

Freek

library provides facilities to combine more than two algebras using some pretty involved type-level machinery. The solution proposed by the

Freer Monads, More Extensible Effects

paper also focuses on extensibility, and inspired a bunch of work of small Scala libraries such as

eff

,

emm

and

paperdoll

. Tagless Final interpreters take a somewhat of a dual approach by having typeclasses at their very core instead of the more traditional ADT/GADT. They also come with the great advantage of being out of the box extensible without having any apparent pitfall.

The

lecture notes

goes into great details in presenting and comparing both ADT/GADT and typeclass based approaches, referencing the former as

initial

and the later as

final

. For the sake of conciseness, this document focuses mainly on

final

interpreters.

Introduction

We will be working with simple mathematic expressions similar to the ones manipulated on calculators. Our task will not only consist in computing these expressions, but also serialize, deserialize, and simplify them. As lazy engineers, it makes perfect sense to represent the domain using an (embedded) domain specific language. Among other things this saves us from caring about all the possible incorrect representations of our domain: the host language compiler takes care of that for us. Our domain consists in integer literals with addition and negation. The encoding that might have popped right up into your mind might look like the following:

sealed trait IExp
final case class Lit(i: Int) extends IExp
final case class Neg(e: IExp) extends IExp
final case class Add(r: IExp, l: IExp) extends IExp

A mathematical expression such as

8 - (1 + 2)

can be encoded as a value of type

IExp

:

val fe: IExp = Add(Lit(8), Neg(Add(Lit(1), Lit(2))))

Now everything looks easy right? Interpreting

fe

as integer uses recursive function of type

IExp => Int

, serializing is done with a

IExp => Json

function, deserialize goes the other way around with

Json => Option[IExp]

, and transformations are done

IExp => IExp

functions.

In the lecture notes’ terminology, the

IExp

data type corresponds to the

initial

encoding of our domain. You can forget about it for now, as we will instead be using the

final

encoding:

trait Exp[T] {
   
  def lit(i: Int): T
  def neg(t: T): T
  def add(l: T, r: T): T
}

How do we represent

8 - (1 + 2)

with

Exp

? Something like the following:

def tf0[T](implicit e: Exp[T]): T =
  e.add(e.lit(8), e.neg(e.add(e.lit(1), e.lit(2))))

In Haskell (with proper language extension)

tf0

could be a polymorphic value. In Scala we use a function with a type parameter

T

and an

implicit Exp[T]

constraint. The syntax can be simplified (for example) by getting rid of the

e.

using helper functions:

object ExpSyntax {
   
  def lit[T](i: Int)    (implicit e: Exp[T]): T = e.lit(i)
  def neg[T](t: T)      (implicit e: Exp[T]): T = e.neg(t)
  def add[T](l: T, r: T)(implicit e: Exp[T]): T = e.add(l, r)
}
import ExpSyntax._ // It's safe to always have these in scope

def tf1[T: Exp]: T =
  add(lit(8), neg(add(lit(1), lit(2))))

At this point you probably wonder,

how do we write interpreters for this

tf1

thing?

. The answer is simple, by creating instances of

Exp

!

implicit val evalExp: Exp[Int] = new Exp[Int] {
   
  def lit(i: Int): Int = i
  def neg(t: Int): Int = -t
  def add(l: Int, r: Int): Int = l + r
}

implicit val printExp: Exp[String] = new Exp[String] {
   
  def lit(i: Int): String = i.toString
  def neg(t: String): String = s"(-$t)"
  def add(l: String, r: String): String = s"($l + $r)"
}

Interpretation is done by specifying types. Let’s looks at

tf1

as an

Int

:

scala> tf1[Int]
res0: Int = 5

What about

tf1

as a

String

?

scala> tf1[String]
res1: String = (8 + (-(1 + 2)))

Extensibility

What if we decide to extend our mathematical expressions with multiplication? With the

initial

(ADT based)