Building a Tagless Final DSL for WebGL i...

scale.bythebay.io: Luka Jacobowitz, Building a Tagless Final DSL for WebGL in Scala

Recording: scale.bythebay.io: Luka Jacobowitz, Building a Tagless Final DSL for WebGL in Scala

you building a tag was final DSL for WebGL my name is Luca Jacobites I'm from Germany just sort of Germany I'd like to do a lot of Scala especially in my free time I do a lot of type level projects so that's kind of cool check that out okay so without further ado I'm gonna start and I'm gonna start with the motivation for this talk right so tagless final isn't encoding but why would we actually need it or what is it good for so basically what what we often have is functional programmers right we we don't want side-effects but we still often have to like interface or work with some like super imperative languages and for this talk I chose to use a library called WebGL which probably most of you know but it's like this super super imperative language right so it's kind of hard to find anything more imperative than graphics programming okay so how can we then give these libraries a nice and clean functional API yeah this is like the main question of this talk and the answer of course is actually oh the answer is not not this but this is an answer it was too fast there okay so the solution number one is to just wrap anything in IO or task or whatever just these side-effect capturing monads and this works this is completely purely functional right but the problem with this is to me that it's it might be purely functional but it's also not really better than working with imperative programming because there's a lot of like like hidden things going on here that we can't observe so in order to get like a really functional API a declarative API there's still a lot lots of work to be done and some other problems is our that this breaks like the separations of concerns right here we see like we're printing but we're also like creating Dom elements we're using the GL library it's like it's not nice right we don't have any way to dissemble disambiguate between like an i/o that does does like Dom things or an iota does WebGL things or logging things so there's a lot of things that we don't like about this I don't like about this it's also super difficult to test because the only way to test it is to actually run it and then you have to like manually check the Dom and then you have all the problems with like mutability and it's it's kind of a mess and also it's hard to keep track of the level of abstraction because like right here like this geo dot clear color it's a super super low that we'll call but they also have this more higher level Dom Dom API that we're working with so it kind of mixes and matches whatever and it just wraps it all and this one type called IO it's not what we want so it'd be really cool if you could just use like a functional DSL to access all of our imperative libraries that sadly still exist and a short digression if you've read my abstract I talked a lot about EDS ELLs in it and what's actually the E and E DSL so if we talk about like normal DSL we have something like GLSL which is GL shading language we have sequel we have shell scripts these are all languages in their own right right and embedded DSL which is what the e stands for are embedded into another language this means we build up like a tree of expression or it doesn't actually have to be a tree we build up something and then we compile it into like Scala or hospital or any language that acts basically as the host of our DSL so it's actually part of the language it's expressed inside of the language that's those are embedded dia cells so what kind of edia cells could we have like the most simple thing you can think of is to just use an AST right and we can express these as generalized or not generalized algebraic data types if you think about like a really small example you can build like arithmetic expression as as like an algebraic data type and then you can compile it to different things you could you could use like an interpreter to to pretty print it you can use it and could use an interpreter to actually do the arithmetic and get out like a number numerical value so this is also this is already kind of cool like ASCs are pretty cool but we don't really get a lot of you know really really getting a lot of flexibility in the sense that like we want a lot we want R to put our computations to be in a to behave in a certain way and that's where something like the free monad or free applicatives come in because free monad if you've watched Rob's talk yesterday he talked about monads and monads basically allow you to express dependent sequential computations right so this is super super powerful and it's it's no no wonder that a lot of talks around here are about monads and basically the free monad what it does is it allows you to borrow like this monad structure and and we can build our algebras in terms of these monad structures and basically just sequence the actions of our algebra and the applicator on the other hand can do what an applicative does which is independent computations so we can do all of our independent computations defined as an algebra so these are the two I'm not going to talk about today I'm going to talk about of course is tagless final and Tech's final basically is where it basically works like this so we our algebras not as trade not as actual data structures but instead as an abstract trait right and repair to that pyramid that is such a dumb word parametrize with it our algebra with the type constructor and this type constructor will when interpreted it will represent our effect type right effect type in the sense like option or a list or i/o is in effect right okay so then we can build programs with these algebras and actually constrain them this means we get to choose actually the the behavior to constrain them with like with with a free monad we're bound to a monad and lots of times in tagless final we will want to use the monad because well dependent calculating computations are so powerful and so useful that it's just like the mo the thing that makes most sense but a lot of times we don't actually need the power of monads so we can use whatever we want a lot of times just the flat map type class is enough a lot of times also we might just want to use independent computations so an applicative is enough or even just an apply so really the the principle of least power completely applies when doing tagless final algebra tag his final programs sorry and then we want to actually interpret our algebras we can just simply define an implementation for our algebra right so if our algebra is a abstract trait the interpreter is just an implementation so this is super simple we don't have to deal with like these fancy natural transformations or any of that so let's look at our very simple example it's right here at the top we have our algebra which is just going to be an algebra that describes console-like programs so dealing with like printing and reading it's a really simple example and it's kind of overused for these kind of things but it works so we have two actions operations the first one is print line which takes a string and then returns our our type parameter with with a unit inside right so this F is totally abstract right now and it doesn't represent anything and then we also have read line which returns a string inside something and then once we build our program we actually say ok our F has to be a monad so what this means basically is that we we want to run these operations in the algebra sequentially right they're dependent on each other so our program right here just takes as a parameter our console out algebra constrained by F and then it will just print out please enter your name and then it will get the name from from from your console when you type something into it and then it will just print out again you entered your name and that's the whole program bless you and then to define an interpreter it's really simple we can we can use well we just have to implement a straight right so we can use an object but we could also use like an anonymous class yeah an anonymous class lots of different ways you could just use a vowel but the most simple way I find is to just use an object that extends the that the trait and where we can see here is we we basically interpret it into a Monique's task because monix task is kind of cool but it doesn't really have to be a Monique's test but it doesn't have to be an i/o type at all it could be like to test it we could just interpret it into ID which is then just type itself or we could use any other things to like test or play with the algebra yeah so the implementation is super simple we just print and read and all that inside the task and then at the end to run to actually run our program or to interpret the program we just say the program and then we inter insert the interpreter inside and then this part is basically the task of unit and then we just run it okay so that's that's kind of cool pretty basic but let's look at something like combining algebra because this is kind of difficult or free so here right here we have a second algebra that's gonna be a key value store and it has two functions defined on it and the first one is just put where we give it a string and an A and it's gonna return nothing and the second one is get where we just get a we put in a string and want to get something out of it but we can't guarantee that it's in there so we get an option of a and then to create a program with it it's actually super simple it not much has changed except for the fact that we're just gonna enter two two algebra right so this is the only new part here and the rest and the rest basically stayed the same oh of course we changed we also changed our program to at the end put the name inside of our key value store and also I changed the constraint on the F type parameter to be a flat map instead because we don't actually we're not actually using the pure function inside here anywhere so oftentimes we can use the principle of police power and just use whatever type class we actually need so so far this is pretty cool we can do a lot of thing but now comes like the real cool part that allows us to to do a lot of to do to write really cool dear cells and this is layering your languages right so if we want to do some really fancy stuff with GL WebGL we're going to want to define like a low-level language that exactly represents their operations on GL and then we can define higher-level languages and compile down to them right so I think like Rob Norris he does something similar with free and doobie he like automatically generates all of the JDBC JDBC methods onto like into free algebras and then he defines a higher order a higher-level language that compiles down to them and this is the same idea right so we have our trade prompt or algebra prompt and basically what it's supposed to do is just write something to the console and then read it back and then read whatever came back right so you put a string in you put a you get a string out right and turn to build an interpreter that interprets to the console algebra we define them before we just pass it into the interpreter right so basically that this is all you need to to interpret your higher-level language into the lower level language right so this is super easy as well and now let's check out some some actual code that I wrote for WebGL okay so first the idea is to to make a small game like a racing game this is a small racetrack that I built out of individual tiles that my friend Simon created for a university project years ago and what I wanted to do is to to build a game that's basically like Mario Kart a Super Mario Kart or f-zero and the SNES I'm not sure if any of you remember probably in this audience but basically what the SNES could do was not do actually 3d but it could basically do perspective projection so so that you could have like a single tile as as like the the background of of a scene and you could total like it looked super 3d back in the day but it was actually just well it was all tiles right so here's my car so you can just see it like from behind it's not a model or anything it's just a tile it's just a sprite okay so first I defined an algebra to work with the DOM and this is this is not obviously the whole algebra ought to work with the Dom this is just what I needed where we can see right here that we have the basic building blocks is this big enough can everyone see this right okay great so we have an append to body function we want to create image elements of course we want to render something in a loop you want to catch key key events like on keydown and keyup is super simple but it's necessary and then we also have a WebGL algebra that is the lowest the lower level algebra and what's up what's happening here is just basically wrapping or wrapping the exact API that WebGL gives us we can see here that's pretty like there's lots of things going on to create it like a shader we need to do you need to call the create shader function then we need to call that a shader source function we need to compile the shader then we don't know if something went wrong so we get like have to get shader parameters and then the info log so it's kind of like a a mess right and we need to create programs out of these shaders we need to create like at least vertex and fragment shader and we also need to link that program we can then get program primers and use the program so there's a lot lots and lots of stuff going on to create textures just as much and to actually draw something we need to like buying all of these things but the whole thing is super imperative right most of the things we return here are f unit so what I did was to define simple algebra that does this a lot more succinctly right so we can what we can do with this algebra which is called draw image which is not a great name but we'll deal with that later we can create a full size with this we can clear the screen in a red green and blue values RJ RGB we can compile a vertex shader and instead of getting all these small steps we just come we just give it a source and then we get back an F of either an error or the vertex shader and same with the fragment shader and then to create a program we actually have to give it a vertex shader and a fragment shader and even that can fail so we also get like an either back here and then we can create a texture info with an HTML image element and in the end we want to draw an image by just giving it the valid program giving it WebGL texture which we get from here and then a matrix to determine the position and matrix for is just four by four matrix used for all of this graphic stuff so let's check out a program written in this in this algebra so basically what happens here is what I call simple race even though it doesn't actually run in a loop yet so there's no racing going on but nevermind and I constrain the whole program by a monad and I needed the the Dom algebra and the glow image algebra and I defined here like some vertex shader codes some fragment shader code you're not gonna get in too much I got the track here the at our scale here which is the matrix for scaling the track it's kind of baked 20 by 20 I translated to someplace and I also defined model matrix for cars and a view matrix so but this is the interesting part right we can now use these operations we defined inside of our tagless algebra 2 lot to basically build a program right so we create a full-size canvas with WebGL or with the draw image algebra and we append it to the body we create a projection view matrix we compile the fragment shader the vertex shader so this is actually this should be an either of either of or it says either a string or the vertex shader and then the programs should also be like it either and might be IntelliJ can do that it should be either a string or the the compiling program and we also create image elements we think we create textures out of these clear the scream and then we traverse or either and then just do all these two images so it's it's not a lot but this this actually works I'm not gonna run this right now so I don't have that much time instead because this is kind of medium level I built another even higher level deer algebra for it so I call this one render engine even though it's totally not an engine but I just I just wanted to show you what you can do by just parameterizing even further right so this render engine it takes it has two two functions the first one initializes the engine and then we just run a render loop so this is it's not a lot of stuff going on here but we have this we given this options which is parametrized by the engine so we actually get to choose what kind of options we do this when we have an interpreter great and we also paralyze the error type so if the initialization fails it's going to return either the error type E or a context which we also don't know what it is because it's also parametrized and then we get we get the second function which is render loop where we give it the context that we created when our initialization worked and then we give it a seed which is a render output so it's this is Wender output is just like the initial object so we have a camera which is just like the position of the camera and the position where the camera looks at and then a list of render objects which are also parameterize by this texture object so it would doesn't necessarily have to be like a WebGL texture it could be anything else and yeah so this is we also have this function that that determines what the camera is gonna do next so basically this function takes the old camera and a set of keys so anytime you press something on your screen this this the keys are gonna be inside the set and we then we have to create a new camera out of these out of these parameters so this is basically like a scan on an observable but yeah I'm not gonna go into too much detail here so when we actually want to interpret this we interpret this using our draw image and Dom algebras right so we we have what we have is basically interpreters all the way down right so we have this super high level algebra which compiles to our medium level algebra and that compiles to a low level algebra and we could build infinite amounts varlyn infinite but you know like a very very high number of algebras that all compile to each other and because this is just function application it's basically for free so yeah this is their winter engine interpreter drawimage sorry for the bad names but this is what I got and yeah I'm not gonna go too much into what it does this is the initialization code it just uses all of all of the stuff that we defined for so it's very similar and then still got it to do here that I wanted to remove but yeah this is what it does so let's actually check that out in real time yeah so this is the final product I'm super excited I'm I'm just gonna do a lap so we can go right here we can thank you thank you this is cool because I think it's showcases that like we can build complex programs this is not really a complex program but it's close to like a complex program and it allows you in it was built using a pretty simple DSL yeah like the algebra you saw at the end it was it was pretty simple right I mean anyone could grasp that if you're like into programming of course but yeah okay so much for that let's go back to the presentation so as a bonus slide we can also do parallelism and this is the new cat's parallel class which basically lets lets us do applicative combination but independent from the actual monad right so for example task has a monad instance where when you when you want to use the applicative the applicative function the app function to to combine two tasks independent from each other what it does is right now it uses it uses sequential computation but with this parallel class we can define a an applicative that does this in parallel and we can associate it with this using this parallel class and then what we can do is use these power map functions aparment and function or stuff like part Traverse similar things to totally do this in parallel so with free you kind of have the problem like you either have free monads which does everything sequentially or you have three applicatives which does everything which can do everything in parallel yeah question right here it's right here oh yeah that's not out of scope it's yeah it's kind of same as a it's just an example sorry I should have picked a better example but yeah sure so but this is just a showcase like the per map and function and how well it works with tagless final and we can totally combine like sequential computations with parallel computations and it all works in tagless final there's no redirection I know that like my colleague Marcus how he had a whole talk on how to combine free monad and free applicative and I think most people just ran away because it was super complex basically had to embed the free applicative inside the free monad and this gives it to your basically for free that's a bad pun but yeah so other cool things we can do with titles final and well difficult it's totally possible to inspect and optimize or programs right so with free or with free applicative in particular it allows you to analyze and optimize the the program we actually build up with the titles final it's kind of difficult because you don't actually build up like a value that we can actually look inside but if you look at all like keys all your original paper titled typed tagless final our interpreters he actually does that for like a simple algebra I'm pretty sure you could probably do that for more complex as well so and what I also would like to tell you about is the Maine library which is built by another cat's contributor Kailua rang and hope I got that name right but yeah we which allows us to like very generic generically compose and transform our tackles final algebras so it's really cool if you want to check out tagless final and I want to do some craziest things with it you should totally check out Maine and while Texas well for example the free monad totally guarantees stack safety on all events in tag was final it kind of depends on the monad or whatever you interpret into right so if you interpret into a Mona's that it's that is not stock safe you're not gonna get any stack safety for free that you get with free but it is totally possible to compile our type of spinal algebras to free Monette and then compiled a free mode ad back into whatever we won did and there we get stack safety for free so yeah take a raise conclusions tagging was fine allows us to use our own algebras for defining interactions so we saw that we can define like in an algebra that exactly maps to the domain we want to use or that we want to work with and all of these algebras can be composed or and/or layered and you can also define like multiple interpreters and this gives us super super great flexibility and the ability to test and refactor without like breaking existing code this is actually easier to do in Scala than in high school because in high school you have to do this as like a type class and type classes can only have like one instance for each type so this is actually cooler in Scala in high school this is like the first time that's ever happened yeah and and also our programs we can constrain them to be exactly as powerful as we want them to be right so if we need sequential and parallel computation we can we can tell we can constrain the program to do that and we can only interpret it with with a type that actually actually guarantees us all of these properties and if we don't need them if you only need something like foldable or apply flat map they we can and we can do it with it just that it's it's really allows us a lot more a lot more reasoning capabilities because we can constrain it to exactly what we want it to be and at the end we can work like at an extra level of abstraction we also maintain flexibility with which is to me pretty cool yeah I think that's it so thank you very much for listening if you're on Twitter you can find me at Luke ajikko boards or on github at Luke at JCB or are there any questions yes definitely I'll just post them on Twitter so if you follow me right now but yeah totally also the code is on github I'm gonna link to it when I upload the slides any other questions sure Cody no I think it does have like valid use cases I'm pretty sure it's it's pretty cool for a lot of things especially because you get like the stack safety for free I think tagless final in a lot of cases is cooler for when you have like a lot of algebra is because composing algebras with free you have to do the whole data types a lot card thing with inject K you have to basically build up a huge co-product of all our different algebras so yeah tagless final any other questions I don't completely understand it to be honest like III did the example that that Oleg mentioned in his paper in Scala I put it into Scala and it worked but still kind of like I couldn't explain it to you that would actually like manage the detail give you the same detail that the paper as so the paper is cool O'Lakes papers are usually cool so should check it out okay I think Oh Rob sure [Music] yeah okay so the question was that what about treating our algebras as type classes and then using context bounds to pass them around so this is basically like what Haskell or what you would do in Haskell in pure script because it's the only thing available to you to be honest it's it's not a huge difference it's just I mean I guess it looks different when you build your interpreters and programs but the only thing you could that basically constrains you to do is to only have an interpreter into one type right so you can't have an interpreter into like tasks and then an interpreter into tasks again that does something slightly different which is to me like an arbitrary like it doesn't do you don't need to have that restriction I think so I don't I don't really see any benefit in doing that sure you could maybe there maybe I'm totally wrong but I haven't like tried it out and contrasted it enough okay Oh Christian or is it yeah sure yeah if you like if you mostly you're gonna like interpret into something like IO or a task or something like that so these are usually type stacked safe and you don't probably need the whole trampolining most of the time but yeah if you do like okay okay so that's it no more questions and if you have any other questions and you're too shy or you wanted to ask later just I'm here I'm around I was glad to add some questions okay thank you guys [Applause]