Posted Feb 7, 2019 2019-02-07T00:00:00+01:00 by Juan Pablo Royo Sales
To get a complete version of the source code presented here, go here Github Repo.
All the examples of this post can be found on demo-end branch and NOT in master
All the techniques and code that is going to be shown here are completely agnostic of any library. We are not going to use any Scala FP library such as cats, scalaz or any other. Obviously using any of those libraries could help us to implement these techniques without needing to write so much code, but the goal here is to shown how we can implement Tagless Final Encoding using only pure Scala language features.
This is my first blog post about Scala and i would like to describe a well known topic for the whole Scala FP community which is Tagless Final Encoding.
There are so many great code examples and blog post about the subject around there, but since there is always room to understand the technique from other perspective, I decided to take the chance and maybe help others to understand it in a more practical point of view.
I am going to deep dive in the technique with a real use case example and in the middle i will mix it with more theoretical concepts. This journey is going to start from an imperative approach until we get to a Tagless Final FP approach. So, fasten your seat belts and lets enjoy the ride!!!
I’ve created an example problem to be solved based on some things of my personal work, so everything in the example could be real production code. This is obviously a minimalist version of the problem.
We are going to describe a Recommender Program that given an algorithm and a user is going to generate recommendations for that user based on the selected algorithm. A Recommender system could be for example the most likely recommendations you received when visit any Marketplace such as Amazon, Ebay, or any other after searching for some products and navigate through these sites. For example: “Since you have been searching for X cars, maybe you are interested in R, Y and Z also”.
As an user i want to get recommendations from an specific algorithm, but if there are no recommendations for this algorithm or i forgot to specify what algorithm should be use i would like to have default recommendations from the best algorithm the system has.
As an user i want to get a message if recommendation’s algorithm i requested is wrong.
As an user i want to be able to be retrieve with a limited number of recommendations.
Although this imperative code version is fine, we can take the advantage of for-comprehension syntax sugar since we are manipulating Option[+A] type.
We can even go further and separate our program in 2 functions:
getRecommendations: for-comprehension where the program logic takes place
printResults: print results or errors to the user.
Now we are done with our imperative code style and we can say it is in a good shape.
But we don’t like imperative style, we love doing Functional Programming and applying all the Math science we have at our disposal, don’t we? So, lets start to refactor our code with Tagless Final Encoding approach.
Tagless Final Encoding
Tagless Final Encoding is a technique for embedding a DSL (Domain Specific Language) in a Type Functional Language such as Scala, Haskell, OCaml or other similar. Since we are embedding a DSL (a.k.a. Language) we are defining a Language in order to use its syntax and semantic (Algebra) in our program. We are defining also an interpreter of the Language to indicate how it should behave on each used term (Interpreter).
If you want to visit a more advanced approach of this, I would strongly recommend after this lecture to take a look on Free Monads.
We can say that in Tagless Final style there are:
Algebras: Set of operations over a Structure. In a Programming language idiom could be a set of functions that operates over some Type.
Interpreter: The way of those operations behave according to an specific Type. In a Programming language idiom the implementation of those functions depending on the specific Type.
The first thing to do with this technique is to define our Algebras, our operations that are needed to solve our domain problem. If you already have some program in a good shape but with an imperative style approach like describe it above, it is quite easy to define these operations because it is already provided by the semantic of the for-comprehension. In our case we have the following operations:
Now the only thing left to build our Algebra is to group those operation in different Algebras depending on the structure they are operating on:
User: operations related to handle users
Algorithm: operations related to handle algorithms
Filter: operation for filtering results
Since our Algebras are only definition of our operations we are going to use Trait for defining this abstract representation.
Here we have a couple of things perhaps new for the reader:
We are defining our Algebras in Traits. So far so good. Nothing new or fancy.
We are defining our Types with Higher-Kinded Types parameters (F[_]) to abstract out the Container Structure that it is going to be use in each Interpreter. A Higher-Kinded Type or Type Constructor is a Type which constructs a new Type based on a Type Parameter. For example Option[+A] is a Type constructor which takes a Type, for example String and constructs the final Type, for example Option[String]. You can probe this in a Scala console with :kind command:
A last thing we are adding here in companion objects are a technique called Summoned values, which allow us to get the implicit value using the Companion Object Trait’s constructor.
With all this machinery in place we can add some utility functions to avoid calling companion objects and just calling functions from the client program:
Now it is time to use our Algebras from getRecommendations program. In order to do that we are going to use Context Bounds allowing the compiler to infer implicit values from context.
Although it seems we have arrived to an acceptable solution we are not ready yet. We need to have at least one interpreter which is the real implementation of our Algebra. Recall that we are resting everything on Option[+A] for the moment, so our interpreter should be on Option[+A] Type.
One possible interpreter could be:
We need to do for letting the compiler infer the implicit values it is just importing our implicit values on the context.
Have you notice that we are calling getRecommendations with Option[+A] as the Higher-Kinded Type or Type Constructor?. Since we have indicated in getRecommendations that F[_] is context bounded by UserRepo and AlgorithmRepo and Filter, and
$$F[\_] \cong Option[+A]$$
the compiler should look for an implicit value for each Algebras whose F is Option[+A]. And that is what exactly we have provided to the compiler. But is this code compile and runs or only runs? Lets check
Why is this happening? Because getRecommendations is Context Bound or Constrained on UserRepo: AlgorithmRepo: Filter and for-comprehension in Scala is only a syntactic sugar for flatMap, map and withFilter. Of course Option[+A] type implements those methods and can be used in a for-comprehension syntax, but for-comprehension used on getRecommendations doesn’t know anything about Option[+A] or any other Type until it is bound in program function.
Remember as i mentioned in Disclaimer section that we are not using any extra FP library to do the job. If we are using cats or scalaz we can easily ConstraintgetRecommendations with FlatMap or MonadTypeclasses
Program Syntax: For-Comprehension aware
We need a way to tell the compiler that getRecommendations supports for-comprehension syntax. We can do that creating an Algebra to support that syntax.
I would like to point out that this part of the code is inspired on John De Goes Talk FP to the Max and i would strongly encourage you to watch this video.
In our Algebra we are going to have this:
An in our Interpreter we need resolution bind for Option[+A]:
Last thing to do is to add ProgramConstraint to getRecommendations:
Now the code compiles and run!!
Printing results: The right way
Recalling to our printing results function. In this case our fold over result is working because we are expecting an Option[+A] result, but getRecommendations is agnostic in that sense and printResults should also be.
This is a better version but our program doesn’t compile because Program Algebra doesn’t have defined a fold operation. So lets do it:
Now we have defined our fold operation which is going to fold over F. It is time to add the interpretation of this operation:
The code compiles and runs again with an abstract version of printResults. Lets see some examples:
It doesn’t look accurate, does it? Error cases such as userId not found, no recommendations found and so on are not displayed and the messages for the user are vague in those cases. This is because we are dealing with Option[+A] type and it doesn’t give us the expressiveness we need to notify the user with the exact errors on our program.
Handling Errors: Sum Type to Rescue
We need to alert program’s user about what specific errors have been found during the execution. For that purpose it will be great to have our execution in terms of Either[+A,+B] instead of Option[+A].
The cost of doing that with all the machinery we have defined until now is minimum because of the following:
Either[+A,+B] is a Higher-Kinded Type but with 2 Type parameters instead of 1 as our Algebras are requesting. We are going to see in a minute how to solve that problem.
We only need to write an interpreter for that Type, bind getRecommendations call with Either[+A,+B] and let the compiler use the correct interpreter on runtime for us.
Lets try to figure out our first problem which is how to bind a Type Constructor with 1 Type parameters (Either[+A,+B]) in a definition with only 1 Type parameter (F[_])
$$F[\_] \ncong Either[+A,+B]$$
We can check this incongruence in Scala console very easily
As we can appreciate Either[+A,+B] has kind F[+A,+B] and we are asking a kind F[+A], but we cannot change our Algebras to support F[+A,+B] because it is not going to accept anymore Option[+A] and we want to support both. Instead of changing our algebra we are going to adapt Either[+A,+B] to be a Type Constructor with 1 Type parameter. For that job we are going to use Lambda Types.
Basically a Lambda Type is similar to a Partially applied function but at a Type Level. We can curry our 2 parameter Type Constructor to obtain another 1 parameter Type Constructor. This is how it is done:
As we can see in Scala console example we are fixing LeftEither parameter type with AppError since all errors we are going to generate are subtypes of this, and let this phantom type be parameterized only in its Right value Type which is the Type it is going to change during execution.
In our code we are going to use kind-projector compiler plugin to avoid this boilerplate syntax.
With kind-projector we can have a more readable Lambda Type like this:
Interpreter for Either[+A,+B]
Now the only thing missing is to write our interpreter for this new type:
And we can execute both programs running on different interpreters at the same time:
If we run this program now we can compare detailed error when we interpret the Algebra with Either[+A,+B] against unknown errors with Option[+A]:
With this approach we can test our code in a straight forward way. We only need to provide a Test 1 parameter Type constructor and write our interpreters. Thats all.
To have an idea of this approach to that this could be done like this:
Tagless Final Encoding is a very good technique to encode DSL and separate the interpretation of DSL definition from implementation in a pure Functional way and as i pointed out on Disclaimer section, implementing this technique with some Scala FP library such as cats, scalaz or any other do the work strait forward and easy, removing a lot of boilerplate code we are using here, specially Program Algebra