Tagless Final
for Humans

Noel Welsh

Inner Product

It was the best of times, it was the blurst worst of times

A Scala developer, discussing tagless final


                    Picture.circle(100).fillColor(Color.red).draw()
                  

                    object ExampleServer {
                      def run[F[_]: Async: Network]: F[Nothing] = // etc.
                    }

When is tagless final appropriate?

How to implement it effectively?

What is tagless final?

Ye Olde Tagless Final

Cast thine eyes upon this example


                    def scalar[Ui[_]: Controls: Layout](): Ui[(String, Boolean)] =
                      Layout[Ui].and(
                        Controls[Ui].text("What is your name?"),
                        Controls[Ui].choice(
                          "Are you enjoying Scalar?",
                          "Yes" -> true,
                          "Heck yes!" -> true
                        )
                      )

                    val consoleUi = scalar[Console]()
                    val (name, enjoyment) = consoleUi()

This doeth be a program


                    def scalar[Ui[_]: Controls: Layout](): Ui[(String, Boolean)] =
                      Layout[Ui].and(
                        Controls[Ui].text("What is your name?"),
                        Controls[Ui].choice(
                          "Are you enjoying Scalar?",
                          "Yes" -> true,
                          "Heck yes!" -> true
                        )
                      )

                    val consoleUi = scalar[Console]()
                    val (name, enjoyment) = consoleUi()

Verily, this be an interpreter


                    def scalar[Ui[_]: Controls: Layout](): Ui[(String, Boolean)] =
                      Layout[Ui].and(
                        Controls[Ui].text("What is your name?"),
                        Controls[Ui].choice(
                          "Are you enjoying Scalar?",
                          "Yes" -> true,
                          "Heck yes!" -> true
                        )
                      )

                    val consoleUi = scalar[Console]()
                    val (name, enjoyment) = consoleUi()

Thy program calls methods on thine context parameters


                    def scalar[Ui[_]: Controls: Layout](): Ui[(String, Boolean)] =
                      Layout[Ui].and(
                        Controls[Ui].text("What is your name?"),
                        Controls[Ui].choice(
                          "Are you enjoying Scalar?",
                          "Yes" -> true,
                          "Heck yes!" -> true
                        )
                      )

                    val consoleUi = scalar[Console]()
                    val (name, enjoyment) = consoleUi()

We shall know these context parameters as program algebras

Program algebras shall consist of constructors…


                  // String => Ui[String]
                  Controls[Ui].text("What is your name?"),

and combinators


                  // (Ui[A], Ui[B]) => Ui[(A, B)]
                  Layout[Ui].and(firstUi, secondUi)

What hast thou wrought?

With more program algebras thine program shall be extended


                    def scalar[Ui[_]: Controls: Layout]() = ...
                  

                    def scalar[Ui[_]: Controls: Layout: Events]() = ...

A new implementation of thy program algebras shall bring a new interpretation


                    val webUi = scalar[Dom]()
                    webUi.mountAtId("mount-point")

With tagless final, thou canst extend thine program and extend thine interpretation

Humans

Ye Olde Tagless Final is tedious to write


                    def scalar[Ui[_]: Controls: Layout]() =
                      Layout[Ui].and(
                        Controls[Ui].text("What is your name?"),
                        Controls[Ui].choice(
                          "Are you enjoying Scalar?",
                          "Yes" -> true,
                          "Heck yes!" -> true
                        )
                      )

Ye Olde Tagless Final raises barriers to entry

Higher-kinded types, given values, using clauses, context bounds

Ye Olde Tagless Final puts the burden on the wrong person

A little more work by the library author


                    val ui =
                      Controls
                        .text("What is your name?")
                        .and(
                          Controls.choice(
                            "Are you enjoying Scalar?",
                            Seq("Yes" -> true, "Heck yes!" -> true)
                          )
                        )

The five-step plan

  1. Subtyping for program algebras
  2. Type member for result type
  3. A program type
  4. Constructors
  5. Extension methods for combinators

Declare a base type for all program algebras


                    trait Algebra[Ui[_]]

                    trait Controls[Ui[_]] extends Algebra[Ui] {
                      def text(prompt: String): Ui[String]
                      // etc...
                    }
                    trait Layout[Ui[_]] extends Algebra[Ui] {
                      def and[A, B](t: Ui[A], b: Ui[B]): Ui[(A, B)]
                    }
                    // etc...

Make the result type a type member


                    trait Algebra {
                      type Ui[_]
                    }

                    trait Controls extends Algebra {
                      def text(prompt: String): Ui[String]
                      // etc...
                    }
                    trait Layout extends Algebra {
                      def and[A, B](t: Ui[A], b: Ui[B]): Ui[(A, B)]
                    }
                    // etc...

Let's see how this changes our example


                    def scalar[Ui[_]: Controls: Layout](): Ui[(String, Boolean)] =
                      Layout[Ui].and(
                        Controls[Ui].text("What is your name?"),
                        Controls[Ui].choice(
                          "Are you enjoying Scalar?",
                          "Yes" -> true,
                          "Heck yes!" -> true
                        )
                      )

Context bounds becomes single value


                    def scalar()(
                      using alg: Controls & Layout
                    ): alg.Ui[(String, Boolean)] =
                      alg.and(
                        alg.text("What is your name?"),
                        alg.choice(
                          "Are you enjoying Scalar?",
                          "Yes" -> true,
                          "Heck yes!" -> true
                        )
                      )

Use method dependent type


                    def scalar()(
                      using alg: Controls & Layout
                    ): alg.Ui[(String, Boolean)] =
                      alg.and(
                        alg.text("What is your name?"),
                        alg.choice(
                          "Are you enjoying Scalar?",
                          "Yes" -> true,
                          "Heck yes!" -> true
                        )
                      )

Declare a type for programs


                    trait Program[-Alg <: Algebra, A] {
                      def apply(using alg: Alg): alg.Ui[A]
                    }

Programs are now values


                    val scalar =
                      Program[Controls & Layout, (String, Boolean)] {
                        def apply(using alg: Controls & Layout) =
                          alg.and(
                            alg.text("What is your name?"),
                            alg.choice(
                              "Are you enjoying Scalar?",
                              "Yes" -> true,
                              "Heck yes!" -> true
                            )
                          )
                      }

Define constructors returning programs


                    object Controls {
                      def text(prompt: String): Program[Controls, String] =
                        Program[Controls, String] {
                          def apply(using alg: Controls): alg.Ui[String] =
                            alg.text(prompt)
                        }
                    }

Define combinators using extension methods


                    extension [Alg <: Algebra, A](p: Program[Alg, A]) {
                      def and[Alg2 <: Algebra, B](
                          second: Program[Alg2, B]
                      ): Program[Alg & Alg2 & Layout, (A, B)] =
                        Program[Alg & Alg2 & Layout, (A, B)] {
                          def apply(using alg: Alg & Alg2 & Layout): alg.Ui[(A, B)] =
                            alg.and(p, second)
                        }

Automatically accumulates required algebras


                    extension [Alg <: Algebra, A](p: Program[Alg, A]) {
                      def and[Alg2 <: Algebra, B](
                          second: Program[Alg2, B]
                      ): Program[Alg & Alg2 & Layout, (A, B)] =
                        Program[Alg & Alg2 & Layout, (A, B)] {
                          def apply(using alg: Alg & Alg2 & Layout): alg.Ui[(A, B)] =
                            alg.and(p, second)
                        }

Example


                  val c1: Program[Controls, String] = Controls.text(...)
                  val c2: Program[Controls, Boolean] = Controls.choice(...)

                  // Inferred type is
                  // Program[Controls & Layout, (String, Boolean)]
                  c1.and(c2)

Reached our goal


                    val ui =
                      Controls
                        .text("What is your name?")
                        .and(
                          Controls.choice(
                            "Are you enjoying Scalar?",
                            Seq("Yes" -> true, "Heck yes!" -> true)
                          )
                        )

Recap

User code reads like normal code

Extend functionality for platform specific actions (e.g. mobile functionality like location)

Extend interpretations for different platforms (e.g. new UI toolkits)

Just because you can…

Tagless final is only justified when you need the extensibility it provides

Very rarely the case in application code

This type of code is pure theatre


                    object ExampleServer {
                      def run[F[_]: Async: Network]: F[Nothing] = // etc.
                    }

Sometimes justified in library code

When justified, don't use Ye Olde Tagless Final

Scala can be incredibly productive…

if we stop using abstractions that offer no value!

Thanks!

Blossom photograph by Kat Smith on Pexels

Questions?

@noelwelsh.bsky.social

@noelwelsh@types.pl

noel@noelwelsh.com

Draft book at https://scalawithcats.com/