Thread by @YuriyBogomolov

Welcome to the fifth episode of #monadicmonday! Today we'll look at the famous Tagless Final pattern and its implementation in TypeScript.

If you haven't heard of Tagless Final style (also called "Finally Tagless Interpreters"), here's a brief recap.

Originally this pattern was introduced by Oleg Kiselyov et al. in his paper "Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages": okmij.org/ftp/tagless-fi…

TF style is a general method of embedding domain-specific languages (DSL) in a typed functional language. It effectively separates eDSL statements from their interpreters, allowing building a robust extensible applications.

One of the most notable features of TF – it allows building different interpreters for the same eSDL, so you can run your production code on optimizing cache-enabled interpreter, while your tests could be ran using simple Identity interpreter.

IMO, TF style is a valid choice for many functional languages like TypeScript. So let's build a small program in this style!

Our program will do the simple thing: it will as a user about random upper bound and return a random number in range [0, bound).

In TypeScript we don't have proper support for higher-kinded types, so we need to use some hacks. So we start with defining an "HKT" synonym which will adhere to Functor and Monad interfaces. As usual, I will be using fp-ts for this exercise:

Next we'll define a few algebras – sets of operations of type `A => F A`, which will be building blocks of our eDSL – i.e., expressions we can use to build the final program.

Now, when we have these expressive powers, we can express our program. I think of the following logic flow:

I would like to split the program's logic in small functions to show the core idea of TF style: you can "summon" only those parts of functionality you really use!

You may have noticed some "burden" of passing `F` instance over and over to various functions. This is a price we have to pay in TypeScript. In other languages like Scala such instances are passed implicitly, resulting in a much cleaner code.

With these building blocks we can finally express our main program:

However, if you try to run this code, you'll get… nothing. Why? Because our `main` is just an expression – it needs to be interpreted! And here come the second half of TF style: interpreters. It's a console application, so let's use `Task` typeclass for expressing async ops:

Finally, we can obtain our `mainTask` and run it:

Here's an example of program session:

Enter random upper bound:
> aaaa
"aaaa" is not an integer
Do you want to continue?
> y
Enter random upper bound:
> 23
Your random is: 4
Do you want to continue?
> n
Good-bye

However, our journey is not over yet. We can define a set of interpreters for `Identity` type which just do nothing and use hard-coded values – but allow us to debug the logic of our program on a fixed set of values:

Or we can use a `State` monad with a tuple of inputs, outputs and randoms – and use it for creating fully synchronous tests! Or we can, for example, define yet another set of algebra instances which "render" output as HTML and read input from dialog windows.

Or we can introduce some kind of network interaction – say, log our data not onto terminal, but put it in LogStash. Or in Kafka. Or in any database.

And this is the true power of Tagless Final Interpreters.

Also it's worth noticing that one of functional Scala influencers @jdegoes deprecate TF style in favour of slightly different approach using horizontal effect rotation: skillsmatter.com/skillscasts/13…
Great talk – you definitely should check it out!