scala.bythebay.io: John A. De Goes, Streams for (Co)Free!
Recording: scala.bythebay.io: John A. De Goes, Streams for (Co)Free!
yeah so I'm John digos and I'm gonna talk to you about streams actually I'm not I lied I just said I was gonna talk to you about streams so I could get you in the room but I'm actually gonna talk to you about is functional programming and sort of by the way we're gonna happen to use a stream to do some of that exploration of some concepts in FP so today we're going to talk about induction and Co induction of it just to sort of frame this from a more theoretical background and then we're gonna talk about just how universally applicable strings are you can actually use them to solve a ton of real-world problems that everyone in here is wrestling with on a daily basis and then I'm gonna introduce an abstraction and functional programming called Co free which you may or may not have heard of has anyone heard of the free monad go to Kelly's talk or anything yeah so a fair number of people have heard of the free monad a co free is the categorical dual of that and is super useful or at least it's possible to model streams using Co free Co monads so if those words scary don't worry you're not alone but we're gonna go through them one step at a time and hopefully make a little sense of this and then finally I'm going to end with a little sort of call to arms and a challenge and you'll get to see what that's about soon so induction induction is the process of tearing down a structure to culminate in a terminal value and there are tons and tons of programs out there that have this structure of an inductive program for example parsing a config file or sorting a list or even generating an HTTP response that you send back from a request or computing the millionth digit or any other specific digit of the number pi these are all examples of inductive programs they start from some initial structure and then they do this this this this there's this and then finally they culminate in a single value however it actually turns out that most business problems are not inductive they're actually something called co inductive so what is what does that refer to well fundamentally Co induction is the process of starting from an initial value to build up an infinite structure and you should view it in your mind as the opposite of induction induction is starting from a finite structure and sort of tearing it down to produce a single value and then Co induction is the opposite process process of starting with that value and building it up into this potentially infinite data structure and there are tons and tons of examples of Co inductive processes for example producing the next state of the user-interface given a user employed user does something and that results in the next state of the user interface or producing the current state of a config file given an update to the config file so that happens sometimes if you want your application to be live updatable you want people to be able to configure it on the fly then of course you're gonna have to you're gonna have to build a little Co inductive process around that also I just used the example of generating an each sheet of your response as an example of an inductive program but we can sort of zoom out and look at the big picture a web server web server is Co inductive right because you have this infinite stream of HTTP requests or whatever and you're transforming those requests into responses and finally another example is producing the millionth of digit of pi is inductive but producing all or rather describing the process for producing all the digits of pi is an example of a co inductive process so programming languages they really really hate Co induction and why is this well every programming language is made up of functions and methods and stuff and these things return single values even your main function it turns a single value after doing a bunch of stuff most languages have no support for Co inductive concepts some like address actually have a notion of Co data and Co recursion and some like kaskell sort of blur things so you can use it for both but most programming languages don't have anything actually has anyone heard of Jen Raiders in JavaScript okay yeah so finally after 40 years they added a co inductive construct to a programming language unfortunately it's not very good and not very composable so there's that but at the same time like it's not escaped people's notice that's the business problems we solved today are largely Co inductive in nature and hence the rise of reactive and streams in fact I hear a whole company was built around the concept of reactivity you may have heard of them like ban formerly known as type safe so streams are really great easy to understand examples of Co inductive processes and you can find streams used in data processing web servers user interfaces discrete functional reactive programming and and so much more they're really all over the place and a good chunk of you probably came to this expecting to learn about stream so you must have some application here in your mind form well so streams are they give us a few capabilities that are really interesting and important for building programs one of which is their stateful and I don't mean that in a in an impure way like a mutable state because you don't need mutable state in order to model the concept of streams I mean that in simply the state of a fold for example you know where you're passing in the state and returning a new state you can model state in the purely functional way and all streams whether they're functional or not they allow you to build stateful things stateful machines they're capable of doing incremental computation and of course that's that's why they can handle infinite processes like a web server that runs forever or a user interface that never shuts down because they can do things little chunk at a time of course they can be infinite in nature and many streams are infinite or at least they don't have a well-defined ending point like the web server example you can you can shut it down but it could also run forever and finally they consume information and they also emit it sort of one step at a time you can use them to build all sorts of interesting data processing pipelines so when it comes to using streams you have lots of choices you do not suffer from a scarcity you have obviously acha streams and Java streams and scholars dead streams the successor to that which is fs2 and then lots of other stuff and that's just sort of accessible easily accessible from Scala and the big data space you have spark and flink and pachyderm and Kafka and just on and on and on and on there's so many libraries out there for stream processing and a good question is okay say you have some little use case in mind it might be small one project or it might be massive it might be the next big thing that your company depends on how are you going to choose between all of these different abstractions around the notion of streaming like to give you a little bit of help there in the form of a few laws of clean functional code and let's go through these one at a time I think you can use these principles to both help you choose libraries to solve problems that you have but I also think you can use these principles when you're building your own code especially if it's being used by other developers or if it's open source and it's going to be read a lot by other developers so first off reasonability is directly proportional to totality and referential transparency meaning if all your functions are total for some input they'll always return some output and the referent referentially transparent they're pure they don't do side-effects they return an actual values rather than just discarding information into the ether then the ability to reason about that software goes way way way up because then you have that guarantee if I send a value to a function I'm always going to get back the same return value for the same void so that affects testability your reasonability composability so many useful properties come out of that composability is inversely proportional to the number of data types so I want you to look at libraries like that when you see a library and you see 1,000 different data types 1000 different classes I can guarantee you that library does not have good composability they've built a bunch of monoliths that don't combine together in general-purpose ways and the reason for that is like composability it wants to be like LEGO building blocks where you have a small number of things and you can use those to snap them together in an infinite variety of way up obfuscation so obfuscation is directly proportional to number of wallis interfaces and what I mean by that is when you create an interface and that interface has methods and those methods they they don't have any laws that means this sole information communicated by that interface is in your intuition about the name of those methods and that's a way of obfuscating intent right because what we would like to be able to do is is create laws around our interfaces that give us generic reasoning principles that we can apply to all implementations of a given interface and if you find you you cannot express any laws over an interface there's a good chance that it's because it doesn't have any and therefore it's it's sort of ad-hoc it's gonna be very very hard to reason about that in the general case correctness is directly proportional to degree of polymorphism so the more monomorphic your code is if you have fixed definite types there's lots of ways to implement every function when things are polymorphic you have fewer ways to implement every function and the correctness tends to be much much much higher extremely polymorphic code like has anyone taken a look at lens especially like edy commits lens and Haskell super polymorphic code in many cases there's only one way of writing these functions and and it's the correct way sort of not not coincidentally sha dienes so what is sha dienes you know we all do this of course in lots of libraries do this and it happens when you create some really nasty horrible thing that you never want another developer to see and then you use encapsulation to hide that because if they if they see and play around with that that's like you know tinkering with an atomic bomb or something so the more encapsulation you see like when the guts aren't exposed nasty stuff going going on down there and of course sometimes we need to do that right we need if our programmers were paid to get stuff done we need to do that occasionally but it is always a sign of shot eNOS and finally volume is inversely proportional to orthogonality what I mean by that is you're gonna have more code if if you don't have those lego building blocks so if you if you're able to factor the problem space in such a way that every aspect is independent from every other aspect then you're going to dramatically cut down on the total amount of code that you need in order to solve a given problem so how do we apply these things to streams I don't know this is the classes inside of akkad Austria and I don't want to trash-talk akka dot stream obviously great library you know it's used to build bulletproof production systems so and many of these to use it and have used it and will continue to use it but but I do want you to consider the following that it behooves you in many cases to choose the least powerful abstraction for the job choose the most constrained one because that's going to give you tremendous power on the flip side and I don't have time to go into what that means but there's an excellent talk by rune or on on that constraints liberate and liberties constrain in which I recommend everyone check out if you haven't already really excellent talk choose the smallest interface that gets the job done and for some problems I can guarantee you this is not it and for other problems it may be but for some problems this is definitely not it so what can save us sort of from lots and lots of complexity what if I told you there were an abstraction that gave us extremely high reason ability because it's absolutely a hundred percent total and referentially transparent or that there's only one data type in the entire library there are no other data types is just one and you can use that one to combine together in lots of different ways or what if I said there are no wallis interfaces every single interface is has well-defined laws that have been sort of well studied and well tested and and that it's super polymorphic - in fact many implementations of functions there's just a few there's just a few to choose from and usually one reasonable one so it makes it much easier to get that code correct you don't have to hide anything and and everything is totally orthogonal and composable and bits and pieces I told you all that you'd probably laugh right there can't be such a thing Co free Co free is the abstraction that you've been looking for it has all the power free but with the ability to do streaming for those of you who don't know what free monads are think of them as a data structure that describes a sequential computation where subsequent steps in the computation can depend on the result of previous steps that's all a free monad is is this description of a program in terms of a data structure where the data structure models the different things that you want to do in that program and where one one of those instructions can depend on the result of preceding computations and Co free is the same way but it's it's designed for Co inductive processes so it has all the power of free but it's designed for the streaming stuff that we see on a daily basis when we're trying to solve real-world problems this is what Co free looks like and it has a strange sort of definition if you look there a co free of F first F is a higher kind of type so it's a type constructor of one type parameter list you could stuff in list here or you can stuff an option because both lists an option except one type parameter and then this a is is the a type of the value stored inside the Co free which is called head and the head contains in an element of a and then the tail it contains another Co free of F of a but wrapped in an F so let me give you two intuitions for what this thing is try to keep this in your mind as I'm explaining them first Co free of F of a is a co inductive process that generates a is using effect F so the co free has the a and then to get the next co free in there you're gonna have to to execute the F where F represents some sort of effect it could be task or promise or future for example but it could be lots of other things another intuition for this that is useful in some cases is that a Co free of F of a is a current position a on a landscape infinite landscape that requires effect F to move to a new position so on this landscape you can move to new positions but they require you to execute FS and I really like this particular intuition for Co free it has everything cocoa monads or Co free has the functor stuff well the functor method which is map and the functor laws that go along with it because go free is is a functor forms a functor i mean also as to other methods one called extract which basically tells you where you are at in the landscape of possibilities and this I call it terraforming method and tried to think of something clever there and that's the best I could do extend which allows you to basically feed it a function that's gonna produce a new B and it's gonna form a new landscape of beasts on top of that so you can look up their laws if you like and here's how we would use this Co free data structure to model the Fibonacci sequence which of course is infinite just a few lines of code and we can describe an infinite sequence of Fibonacci numbers using this we just construct we have to use this lazy type called name which stands for by name and this lazy type just ensures we don't eagerly evaluate the tail of the co free data structure because then we'd run out of memory and blow the stack so we defer that we created a lazy to structure by simply in for F our choice of F in this case is going to be basically a func a thunk that defers evaluation of the thing that it produces and so Co free of name of a is actually a lazy lazy sort of infinite list and I use that in this case to model the Fibonacci sequence alright so what can we do with this well one of the things that we can do with streams is we can append one stream to another that makes sense right if the first stream is finite that it makes sense to append something else to that stream and it turns out you can implement append by requiring your F not only be a functor but it be something called the plick ative plus so applicative is a type of hunger that's a little more powerful than an ordinary functor and it has additional facilities and plus allows you to take two of these applicative things and smash them together basically combine them in a certain way and once you have that capability you can take two Co free processes and you can append them such that you're gonna basically explore the one before you start exploring the other landscape also to sort of prove that these things really are as powerful as like Scala collections and other types of things it's very simple you can write this method called collect which can take any Co free of F of a and it can pump it it can pump it for values it can just keep on exploring and stuffing those things into a vector and then end up returning that vector inside an F and I won't go into the implementation but you can get an explore that on your own and see how it works and disperse is the inverse of that so if we have some sort of sequence and we want to disperse it into a landscape Co free landscape then we can call disperse and it requires again FB applicative bus so here this this should demonstrate hey we really can use these things to model things like Scala collections right and of course we saw in the case the fibs that these things can be lazy and infinite here zip so you can actually take to go free structures and you can zip them together there's a couple different ways you can do that but this is the most calm the only requirement is you have to be able to zip the FS together so for for something like name that's trivial for a list trivial and most of the types of type constructors one type argument that you can probably think of like data structures and whatnot zip is trivial and so you can implement this zip with method quite easily fold why can't we fold over a Co free structure exactly it's potentially infinite so folding doesn't make sense folding doesn't make sense at all but what we can do is the scan operation which sort of produces every intermediate and it never produces the final value it just keeps on scanning you know producing then building up of upstate but this is the equivalent of a fold if you want to do something for like using Co free skin and of course skal has skin left and skin right and so forth on its own collections how you can even filter these things so that's pretty amazing there's two ways you can filter if you have a CO free you can zero out the elements that you don't want yeah but you can also actually remove them and they require different degrees of power so in the first one if you just want to zero out the stuff you don't want which could be useful if you're using like a bike vector as your F because you you have these streams of bytes then you may just want to zero them out in zero amount corresponds to empty byte vectors and in chunks of data that you didn't want to process however the other way is to require that F be a monad and when you have when you have that much structure you can implement filter such that actually deletes the slots that you are a predicate passed a filter doesn't want well that's streams can we do can we do something better can we do sources and sinks and it turns out the answers yes and it's not that totally yep okay so well that concludes my presentation on Street however I want to leave you with a final a final challenge and that is go read the slides after the fact and look through the code and see everything that you can accomplish with a single data type and entirely lawful pipe classes and then I challenge you to in your own code maybe you don't end up using Co free for streams but take one thing one thing and try to simplify your application by using something in functional programming thank you very much [Applause]