Tagless Final in Scala

hello ladies and gents this is daniel for rock the jvm and in this video i'm going to discuss a very sought-after topic in the skull world which is tagless final at least for mortals so this is a video on scala about the tagless final pattern so this will assume your familiarity with the skull language i'm going to write skull 3 in this video but this works very well on skull 2 as well and as a bonus you may or may not have read about tagless final previously in some article or blog or video or book or may have already experienced tagus final in your own programming experience but you may be still confused about what tackles final actually involves so the recommendations as always just write code with me and whenever you need to refresh your memory about this very interesting concept just refer back to this video or to the written form at the blog with the link in the description now this particular video deserves special thanks to the original tagless final paper written by oleg kiselyov and others who formalized the original taco's final design pattern and also special credits to pretty much every article book and video that i could get my hands on on the interwebs this video is a summarization of pretty much everything that i could get my hands on because no article or video or book was complete enough for my own understanding so if you're an article or book author and you find something in this video that resembles your stuff then yes i've probably read your stuff and i wanted to combine everything that i could get my hands on in something that i hope to be as digestible as possible for scala programming models such as myself so without further ado let me get back to my little dev environment where i created an object with the main method in case we need to test something and a word of warning tagless final might not be what you're expecting and i'm going to tell you why throughout the rest of this video now i wanted to start with a blank slate from the original problem that tagless final wanted to solve which is the expression problem now why do we have this expression problem we have it because in functional scala we think about programs as one giant expression returning a value and that value can be highly complex such as a an http server or a database or whatever service you might want to spin up but it's still a single expression and this is what i teach in both my courses on my website about scala and functional programming we want to think in terms of expressions instead of instructions therefore we have this expression problem which means evaluating an expression while maintaining type safety and returning the right value of the right type and i'm going to start with a very simple example so i'm going to call this little object i'm going to call this expression problem and here assuming i can type i'm going to define a trait i'm going to call this expression or expert for short and i'm going to define some case classes denoting booleans so this expression can be thought of as one giant boolean expression based out of boolean operators and operands that can be evaluated to a single value and i'm going to define a case class i'm going to call this b for simple value and i'm going to have a boolean as a boolean which extends expert and i'm going to have a case class for operators for example or which has a left operand as an expert and a write operand as an expert as well and this extends expert two and then i'm going to define a case class called and which has a left as an expert and write as an expert and this extends exper and another case class let's say not which has an expert and this negates it so i'm going to have expert here so we have a bunch of operators all of which are boolean and some operands or and and not one such expression would be something like a giant boolean as an expert and i'm going to have for instance an or between an and with boolean true and another boolean false and here as the second operand of or i'm going to have a boolean of false for instance so this is one expression that can be evaluated to a single boolean if we traverse that as a tree all right so this is the kind of stuff that we want to solve we want to evaluate this expression to a single value so i'm going to define a method called eval which takes an expert as an argument and this returns a final boolean that i can use and as an implementation all we have to do is run a pattern match so i'm going to have x per match i'm going to have a boolean with a b then i'm going to return that b which is wrapped inside in case i have an or with let's say two expressions a and b i'm going to have a valve for a or eval for b so recursively and similarly for the other stuff so i'm going to have an and for a and b and i'm going to return an eval for a and eval for b and in case i have a not with an expression i'm going to return not so not eval for that particular expression so notice that i'm recursively evaluating the nested expressions inside but finally at the very end i'm always going to return a boolean now all of this is pretty easy until we try to add new stuff to our little program over here because we have expressions only of type boolean but if we want to define a bigger set of functionalities for instance if we want to process numbers as well and also subject that to the same eval function will get into trouble so if we want to for instance include ins i would have a case class let's call this i for an int and this extends expert in a case class to for example process numbers i'm going to call the sum for left which is an expert and write which is an expert and this extends exper now if we wanted to include i and sum here in my eval function i'm going to run into trouble because if i want to process integers i'm i won't be able to return booleans at the very end i should be able to return either boolean or inst depending on the type of expression that i find and so i would have to define another method i'm going to call this eval version 2 which takes an expression as an argument and this returns either a boolean or an int if you're happy to work in skull 3 or if you're doing skull 2 you'll need to return a general type any which lost type safety so i can do now is to run that same pattern match so i'm going to run my expert here but if i do my pattern match my eval a and eval b are not known to be booleans so i would have to do casts so i'm going to have as instance of boolean if i'll be as instance of boolean and so on and so on so you would have to write casts everywhere not to mention that some evals may actually be instances of i or some which are not boolean so the loss of type safety can actually mean the crash at runtime which is something that we don't want so the expression problem means how do we structure our data types such that we can submit an expression of type boolean and return a boolean and submit an expression of type integer and return a proper integer through the same evaluation function this is the expression problem and this might sound a little contrived but if you think about it because we're writing pure functional scala all of our programs are of this style all of our programs are giant expressions returning a value and we want to return the right type for the right expression that we are using so this problem is very relevant and very very general so i'm going to move forward and try to solve this example which i'm pretty sure you understand and then we can generalize that to other things which might be closer to real life now i'm going to call this object i'm going to call this solution 1 and i'm also going to name it after we solve this expression problem in the first solution now in order to differentiate between integers and booleans one solution would be to add some external information to the street for example we might want to add a small tag which denotes whether this expression is of the type boolean or if it's of the type int so i'm going to define a trait i'm going to call this expert and i'm going to have a vowel called tag which is a string now in skull 3 we can pass constructor arguments to traits if you don't want to or if you're using scholar 2 you can define this vowel tag inside the trait all right now i'm going to define a case class i'm actually going to find case classes for all the data structures that we're using here so i'm going to copy and paste all of them so i'm going to have case class b which is a boolean and extends expert of type boolean and i'm going to use this tag over here to all the boolean expressions and i'm also going to copy the integer types and i'm going to pass the argument type let's say int here so notice that i've added some extra information to the expression so that we can differentiate between boolean and integer types now if we want to write the eval function which takes an expert as an argument this will still have to return the any type because we need to return a boolean if this is a boolean expression and int if this is an expression so the final return type should still be any and i will have to run a pattern match yet again so i'm going to have expert match now the advantage here is that now we can implement the proper cases and differentiate between the tags because we can tell from these strings which expressions are valid and which are not so for instance i can say case b of type boolean and i'm going to return that particular value in case i get an or for left and right now i can validate if left and right are of the right boolean type so i can say if left dot tag is not equal to bull or right dot tag is not equal to bull then i can signal an error maybe i can throw new let's say legal argument exception let's say improper argument type or something like that otherwise i'm going to return the right evaluations so i can do the proper casts so i can then say eval of left and i'm going to say as instance of boolean because now i'm safe or eval of rights as instance of boolean so my typecasts are now safe because i've checked against the tags and so on for all the other expressions now notice that this solution although it does return the right type for or the right value for the right expression type is still type unsafe for the type any and it still crashes with a different kind of exception if the tags are of the improper type so in effect we haven't solved that much we can surface the illegal argument exceptions at the very beginning of the construction of the expressions which might be a little better so i can say assert so i'm going to say assert that left tag is equal to bull and right tag is equal to bull so i'm going to copy this and i'm going to use the right operators so i'm going to have left tag must be equal to bull and right tag must be equal to bull and if this condition holds true then i don't need to run these extra checks and i can do my casts without any other concerns however the illegal argument exceptions or the assertion failures still happen at run time so in effect the solution 1 only adds some extra let's say peace of mind when we actually end up evaluating but functionally we haven't solved that much this solution one is called tagging because we're adding this tag which we use to differentiate between the different expression types so this solution moves at least a little step in the right direction because the expressions are validated for correctness at construction with these asserts instead of at evaluation phase however we still don't have any type safety and the errors are shown at runtime so maybe just maybe we can do a little better so i'm going to show you a solution number two now because scala is a strongly typed language and it has generics maybe we can use the generic type argument as the tag for differentiation between expressions so here's what i'm going to write i'm going to write a trait i'm going to call this expert but i'm going to add the tag in the form of a type argument so this eliminated the string tag so i'm going to call this expert a and i'm going to add the case classes for boolean or and and not and i'm going to add the right type so expression of type boolean and i'm going to use the boolean type everywhere so i'm going to use this thing and as well on the argument expert boolean and for the end types so for the int expressions i and sum i'm going to add the generic type argument for expert of type int and the int type argument needs to be present here on the i and sum respectively so notice that we've eliminated the tags but we now have the type arguments and the valve function now needs to take a type argument a and an expression of type a and this will return the right type for the right expression and the implementation is going to be a expert match and we're going to run the pattern match for all the appropriate types so in case we get a b of type boolean then i'm going to return that in case we get an i of type int i'm going to return that if i have a case for or with left and right i can safely do eval of left or eval of right because left and right are known to be expressions of type boolean by definition and also for the int type so i'm going to have a sum with left and right and i'm going to have an eval of left plus eval of right and so on so notice that we are returning the right type for the right expression without needing tags and this solution number two i'm going to call tag less so this is a tagless solution to the expression problem because we can now return the appropriate type for the right expression and the expressions are differentiated by their generic type arguments without runtime tags so i'm going to show you how this would work so if i have outside the tag list thing i'm going to have a method called demo tagless and i'm going to have no arguments just like that i'm going to import tagless so that i can import the types and the function and i can print line for instance eval for or with boolean true and and with boolean true and boolean false this is a proper expression and it's proven to be correct or not at compile time so if you pass the wrong types then the function will not work so if i try uh running this sort of operation with a boolean with 43 for instance then i'm going to get a compiler error because 43 is not of the appropriate type so notice that in this case the correctness is proven at compile time by the compiler doing the type checking for all the appropriate types in the data structures and similarly for in so i can save print line with eval with a sum with int 24 and end with negative 3 or something like that and may if i call demo tagless we are going to see the right values here all right so we have the value true for the first expression and the value 21 for the last expression so this is the tagless solution to the expression problem now this is not the tagless final solution to the expression problem because instead of the final value that we are working with which is the booleans or ins that we're ending up with after evaluation we're working with intermediate data structures such as the case classes that we're using here which is why this solution is called tagless initial now if you want to work with the final ins or booleans at the end of evaluation you're going to end up with what is called tagless final and i'm going to define a trade called expert a as before so it's tagless because we have the generic type arguments to make the difference between boolean expressions and expressions and here inside this expert a i'm going to have a value which is of type a and this is the final value we care about after evaluation now the difference is that in this situation creating instances of these expressions will be done a little differently in this case i'm going to define methods that will resemble our case classes so i'm going to find a method called b for a boolean and this is going to return an expert of boolean and this is going to be a new assuming i can type in the right place new expert of boolean where the vowel value is that particular boolean that i'm just receiving as an argument and same for the other things so i'm going to copy and use a def i'm going to call this i where the argument is an int and this is of type int and the expression is going to be an expert of end all over and just for the sake of argument i'm going to define two more i'm going to define an or where the left is an expert of boolean the right is an expert of boolean and finally we're going to get a new expert of boolean where the value so the val value is going to be left value plus right dot value so notice that the evaluation not plus but or in this case the value is computed right at the construction phase so the evaluation happens instantly and same for the sum so if i have a sum for left an expert of int and write as an expert of int this is going to be a new expert of int where the valve value is going to be left value plus write value so we have boolean ins and two operand operators for booleans and ins obviously we can implement the rest now in terms of evaluation we're going to have a method called eval which takes the type argument a and an expert which is an expert of a and this is going to return an a as expert.value because the expert trait has this member called value so notice that the evaluation happens pretty much instantly eval is just a wrapper over the value that the expression already has so in this case the evaluation happens in each of these methods independently and this is the difference between this solution and the initial tagless solution because in this case we're working with the actual values that we care about which is the result of evaluation and here i'm going to define a method called demo final tagless which is going to return unit i'm going to import tagless final and i'm going to print line pretty much the same thing except in this case i'm not going to use the or and and sum with the caps i'm going to use the or b lower caps a lower cap b lower caps b and the sum which is lower caps a i and i now i don't have an end i might just create one really really quickly i'm going to define a method called and here and the implementation is going to be left value and right value and we have a final tag list ready to demonstrate so in main i'm going to run this and we're going to see the same result as before so we're going to see the true and 21. noting that the final tagless method also works correctly so this is a variant of the tagless design pattern where we work with the actual evaluation directly in the expression and at the very end all we have to do is just surface that value out this is the tagless final pattern that is it and the question that i might get at this point is where's the f in the tagless final pattern usually when we look at tagus final in articles or books in scala we often refer to this sort of stuff with the higher kind of type f for which there is an implicit type class of your choice example monad as quote-unquote tagless final and the question is how is this related to tagless final now tagless final and type classes are two completely separate concepts tagless final is a design pattern i want you to think of it that way that solves a particular kind of problem which in this case is the expression problem and all we have to do is program against an interface and the implementations of the interface define the logic of our program so tagless final is nothing rocket science it's just programming to interfaces for a particular kind of problem i want you to think of that as a simple design pattern whereas type classes are a set of functionalities that you want to offer for some types and not for others tagless final is a solution where you want to return the right type for the right expressions and not for other types so notice that there is an overlap in representation between type classes and the kind of problem the tagless final wants to solve and there is a variant of tackles final that can use higher kind of types and i'm going to sketch one here i'm going to call this tagless final version 2 where the creation or rather the logic of the expressions creating a boolean expression all these operators are grouped together under a simple type class i'm going to define that as my type class and i'm going to define that in terms of a higher kind of type e for expression and the type class will contain all these operators and the type class has the capability of creating expressions of that type so for instance i can create a method called b which wraps a boolean and this returns an e of boolean regardless of what kind of type e is and i'm going to define a method called i for an int as an int and this will return an e of ins and so on so i'm going to define let's say or with a left as an e of boolean and write as an e of boolean and this returns another e of boolean and i'm going to copy that shamelessly and i'm going to paste that in an and method and finally i'm going to define a sum which has a left as an e of int and write as an e of int and finally i'm going to return an e of it so notice that all of this is very abstract and all these functionalities were grouped together under the type class type class this has a fancy term and it's called an algebra this is too fancy a term for my liking but just to separate ourselves from the type class name i'm just going to name this algebra now an implementation of the algebra will have as a generic type argument a concrete representation of an expression so i'm going to define my little case class i'm going to call this expert and this has a type argument a containing a value of type a just like that and i'm going to define an algebra of this kind of expression and i'm going to call this simple expression because it's very simple as just wraps a value now i would like to implement an instance of algebra that is applicable to this simple expert type so i'm going to define that as a value i'm going to call this simple algebra and actually i'm going to define that as a given instance because it's the only one that makes sense for this simple expert so i'm going to have simple algebra as algebra of type simple expert with notice i'm using the skull3 syntax here you can define an implicit vowel with the exact same significance and i'm going to define my methods so the boolean is just going to return simplex with that boolean and i'm going to override the i method which wraps a simple expression over an int i'm going to override the or method that takes two simple expressions of boolean i'm going to return another simple expression which wraps left dot value or right dot value so notice that the evaluation also happens here at construction phase which is very similar to the pattern that we wrote before and i'm going to copy that shamelessly i'm going to name that and and finally i'm going to implement it in the right way so left value and right value and i'm going to finally overwrite sum which takes two expressions of type typeint and i'm going to return another simple expression of typeint with left value plus right value so notice that at this point is just a matter of organizing code now in order to actually run programs in the style of this kind of expressions we will need to use this type simple expert with the simple algebra as its given value so i'm going to define let's call this program one which is the representation of or between a true and an end between a true and a false so i'm going to have program one which takes the type argument e which is the expression type and i'm going to have a using clause which in scott you would be an implicit argument i'm going to call this alg for algebra so algebra e and this is going to be an e of boolean and i'm going to say for instance import alg dot everything so that i don't have to write all these methods prefixing alg all the time and i can actually shamelessly copy this entire program and i'm going to return this same structure so this actual expression which wraps uh true true false and all these methods on the alg thing that i pass as a given value now if we want to realize a concrete instantiation of this program and evaluate it at runtime we are going to demonstrate that i'm going to also run the program two so def program two let me copy this signature i'm gonna call this program number two which is the something which i wrote after that so this is an e of int and finally i'm also going to have an import with alg everything and i'm going to take this exact expression copy it and return it in the method for program 2. and finally if i want to print these to the console so i'm going to have demo final tagless version 2. i will need to import tagless final version to everything and i'm going to have a print line of and i'm going to use program 1 with the type simple expert print line program 2 with the type simple expert this is pretty much what happens in programs written with cat's effect because at the very end we instantiate that with the proper effect type i o in that case so let me print this in main run this application and we're going to see the exact same values simple expert with true and simple expert 21 also i can obtain the final value at the end if you're interested in that all right so true n21 so notice that we obtain the final results regardless and this tagless final version two is much closer to what you've probably seen in programs that uh style themselves to using tagless final but this is not a requirement for tagless final tagless final was completely solved in the previous solution where we built expressions with the evaluation right at construction phase this is just a reorganization and a further abstraction down the line so we basically refactor the code to use a type class instead of a plain interface but the concept remains the same and the concept of tagless final and the concept of type classes are completely separate orthogonal some might say but they have an overlap in how the code ends up looking like when you apply the tagless final pattern in the style that i've showed you here but other than that tagless final and type classes have nothing to do with each other now the question is how might we use something like this how do we go from an example that looks kind of contrived with boolean expressions and integer expressions to something more real life like a server or something like that well this algebra might be refactored to say for instance a user login and this user login trait can be thought of as an abstraction of the kind of actions that might be done when a user logs in so for instance i can check i can check whether a user has logged in using multi-factor authentication so i can say check login and the boolean here can be mfa so multi-factor authentication the i can be refactored to a different name for example last error status which is an int i'm going to call this a code i'm going to refactor that the or can be thought of let's say multi-factor authentication or something like that multi-factor authentication versus version one so mfa version one left and right can be factor one or let's say email and password and the second argument can be sms all right and the end can be multi-factor authentication version two uh left can be uh phone and in this case uh we need for instance i don't know a mobile app and the sum can be refactored to let's say total session logins from server one logins and server two logins cool so this user login is our little authentication capability the simple expression can be user login status and simple algebra can be implementation so login flow or uh logging capability implementation so notice that from a boolean kind of problem we very quickly got into real life so this user login is a set of capabilities that we want to offer and similarly for all kinds of services that we might want to provide and program one can be for instance uh user login flow and program two can be check last status okay and in this case our code becomes very similar to what a real life implementation of a service might look like of course in a simplified version but notice that tagless final can be very very applicable to real services so i hope i managed to give a quick and digestible overview of tagless final in scala if you got to this point in thinking that tf is just a fancy terminology for programming to interfaces then you got the point and i've done my job i hope you like this video in which case i recommend that you subscribe to the channel for more videos like this check me out on twitter and linkedin for fresh updates on upcoming material and check out my website at rockthejvm.com for lots and lots of content on scala and functional programming akka cats cat's effect apache spark and so much more until next time i'm daniel signing off

Channel: Rock the JVM

Views: 1,263

Keywords:

Id: m3Qh-MmWpbM

Length: 36min 13sec (2173 seconds)

Published: Fri Dec 17 2021