Concurrent Join Calculus in Scala

scala.bythebay.io: Sergei Winitzki, Concurrent Join Calculus in Scala

Recording: scala.bythebay.io: Sergei Winitzki, Concurrent Join Calculus in Scala

so I'm going to you about a concurrency paradigm or framework known as join calculus and first thing I should say thank you for inviting me I'm a software engineer at workday and we use Scala and we are hired join calculus first of all is not a calculus in the mathematical sense that I'm going to present it's a programming language and it's particularly suitable for general concurrent computations it's unfortunately largely ignored unknown unused not sure how many of you have heard ever of joint calculus please raise your hand okay few people how many of you have used it one - ah all right I'd like to see you after the talk I've never heard of anyone using it okay so before I start talking about joint calculus as such I'd like to talk a little bit about different notions of multitasking that we use so there's parallelism asynchrony and concurrency so I would like to very briefly discuss the differences between these things and what where we stand what what joint calculus is going to give so parallelism is basically you have a sequential computation that you're trying to speed up by executing certain parts of it on different threads or different machines but it's basically that's what that's all and the main problem in this domain is to take a sequential computation and split it into those parts that can be executed in Michelin or parallel lines so parallel collections in Scala or MapReduce or spark those are typical examples of this kind of computation and typical tasks count words and gazillion of files asynchrony means that we have a sequential computation still but this computation has a lot of wait times like you're starting to download something you don't know when it's going to be finished you're waiting for it to finish you'd like to start another one now you're waiting for two things now you want to start something else update something over there okay that's novel it's finished you're trying to manage these time delays but basically it's still it's conceptually it's a single thread run loop that you're trying to optimize to run many things and to wait for as many things as possible at once so that's how I see a synchrony and to do this people haven't invented things like futures promises async await streams of different kinds FFP functional reactive programming coroutines and other things so typical UI is built on this paradigm so for example you have an Excel spreadsheet and a the user can update any cell at any time and all other cells need to be recomputed according to some equations and then maybe something else can happen at any time so that kind of thing so that's asynchronous concurrency means that you have many computations running at the same time and they are all interacting with each other in some complicated ways so it is not conceptually equal to a sequential computation that we're just optimizing it's actually many computations running an unknown order and the main problem is to decide when you have to start a new one or you should still wait and not start it because something else needs to first so that kind of thing when you start using threads or the synchronized keyword or the semaphore object when you find yourself using those things that's because you're trying to solve an essentially concurrent problem so this is typical tasks for a concurrency is to simulate the so-called dining philosophers problem which is that five kalasa firs sit at a round table and they have food and a philosopher can eat only if two forks are available the two forks next to each philosopher so they cannot hold it at the same time they would like to perhaps but there must be some order but this order is unknown so one of them gets hungry at unpredictable time another gets hungry another unpredictable time starts eating so the task is to simulate this problem to make an algorithm that will tell each philosopher what to do not knowing how long other philosophers will choose to eat or to think after eating avoiding starvation and deadlock so that is a typical problem so I would like to summarize so we have concurrency as the most difficult of those problems parallelism the easiest and asynchrony is the middle because the concurrency is so difficult we try to avoid it actually most programmers like don't like it try to avoid it and it's a good a good rule of thumb to use the least powerful framework to do what you can what you have to do but sometimes you do have to use all these callbacks thread semaphores shared mutable state of courses very difficult to reason about and very difficult to test you have essentially unpredictable runtime behave you cannot test it enough you can never test it enough you can always expect something to happen because you didn't test it enough so that's the difficulty is like race conditions deadlocks like race condition is unpredictable it can happen you cannot usually you cannot prove it when what happens is too difficult the reason about those produce programs so in this talk I will introduce from scratch without any assumption about what you know the joint calculus style of concurrency I am working on a library called join run very small library which implements this paradigm in Scala as a embedded domain-specific language I will give some examples and a very small live coding demo and yeah how I learned to forget that looks and to love concurrency so join calculus is really a programming language like I said it's a declarative language for expressing concurrent programs if you're familiar with the actors framework how many of you are familiar with the actors framework everybody yeah great I will try to skip to the slide where I compare actors with joint caucus it's it's like actors if they were stateless really functional automatically started type safe and easy to reason about which yeah so the main metaphor that I'm going to use to explain Joe in calculus is chemical reactions this is based on a paper which I'm referencing up here yeah a paper from 96 by some French people very difficult to read but unlike a lot of other papers that are mostly also by French people on this subject this contained this paper contains in its introduction a very intuitively clear description of the chemical abstract machine and that's what I would like you to think about how I would like to think about is imagine that we're dealing with some imaginary chemistry or we have molecules and the molecules are flat or swimming around in some chemical solution and randomly meeting each other and producing chemical reactions each chemical reaction looks like some molecules meeting together then they disappear and the new molecule appears and so because it's completely imaginary we can postulate whatever chemical laws we want for example that molecule a and molecule C will meet and immediately disappear into nothing well that cannot happen in real chemistry but this is imaginary chemistry anything can can be done and we just define whatever we want we define any number of molecules we want an arbitrary chemical laws of reactions between these molecules then imagine that we have some kind of simulator for this chemical soup we throw some initial molecules into the soup and the simulator starts churning them around and finding pairs that can react producing new molecules and so forever and suppose that we have this simulator okay implementing that simulator is really a couple of maybe maybe a hundred lines of code it's not so much so big but that's the core of what during Congress is about so we will be talking about this chemical laws and chemical reactions and molecules and that's the terminology I prefer if you look at papers on during tacos you will not usually see this terminology you'll see terminology that I find very confusing like messages channels I find it very confusing especially for the beginning I will use the terminology of chemistry so how do we use chemistry to actually make a programming language and it's very nice to look at some simulation of molecules but here's what we do each molecule will now carry a value on it each molecule is strongly typed and it will have a value of certain type each reaction not just producing a new molecule it must produce a new value on the new molecule and this value will be a function of the values of the input molecules in the reaction that is our postulate so we required this be the case pure function for example compute Z I called it and it will compute some value z given x and y we require that our simulator should now run all these functions whenever a reaction occurs so that new values will be computed for each reaction so here for example we can imagine this reaction producing a side effect through the print statement and producing nothing no molecules as a result so that is an example in principle we can imagine that our simulator will automatically decide how many reactions can seat concurrently in actual chemistry what happens is that molecules don't really know about other molecules once reactions started nobody knows it started other reactions can start concurrently at any time and so that's what we want the simulator to do as well in other words we just inject some molecules into the soup the simulator with some values in them yes now with some values the simulator will find all the reactions that can proceed around them compute all the values that need to be computed according to these functions that we specify inject the resulting molecules back into the soup and go on reactions will start concurrently at any time that input molecules for the reaction are available that is it really that's the entire programming language that we're going to have except for one more feature which I will talk later about so this is the piece of code in the join run library which denotes this reaction is completely declarative just says join means that these two reactions are together in the sense that this a is the same as this a and that is required otherwise the molecules are not identified to be the same in different reactions then they'll say run and you describe each reaction so for example a of X and B of Y go to a of Z and a of X and C goes to nothing just does something so there's an arbitrary color coding here but these constructions are a declarative description of the chemistry that we want here's the first example a concurrent counter so we have a molecule with the counter value n and a molecule which is to decrement and to increment the counter these two molecules have an empty value which is which means unit type unit type of the value each molecule is required to have a type so these will have unit and these will have integer type and then we define two chemical laws that when the counter molecule meets the decrement molecule the decrement molecule will disappear and the counter molecule will be re-injected back but with the value decremented and the same with the increment so now you see that data stays on the molecules we don't have any state in the in the language so in the reactions there is no state and it's a pure function so we just compute some pure function with some values and that's it so the data stays on the molecules so it's kind of a data-driven parallelism now if you imagine that we have a counter molecule and we have 10,000 increment molecules and 20,000 decrement molecules what will happen well if we have only one counter molecule it can only react with one other molecule at that at a time so it will react first with some molecule and get decremented or incremented while the reaction is going on the molecules disappear so there is no counter molecule in the soup during that time there's absolutely no way a race condition can occur there will decrement an increment in time we'll all be reacting with this counter molecule at the end the counter molecule will carry exactly the right value there's no way that somebody can start decrementing while the other has not finished incrementing like in the typical race condition so how do we implement this in the library so this is the Scala code which I will run now once I explain what it does so oops I'm sorry yeah so we define the molecules using these constructions molecules so the counter decrement increment will specify the types we define the reactions which are just partial functions under this run method and we define join which is the two reactions together and then we inject the molecules with values injecting is non blocking reactions will start concurrently so for example calling counter color of 10 it will return immediately it will return unit but it will inject the molecule as a side-effect concurrently so the injection is not on not on the same thread usually as what you're doing here so it's completely country let me try to do some live coding here although I just realized I'm holding the microphone oh yeah thank you all right I'm using Emma Knight which is the fantastic thing done by Lee how are you I just published locally my artifact so I can import it right away so let me define counter I will define let's say decrement I will define a reaction I will just try to join right away just to save time so counter so I'm thinking while I'm doing this I'm thinking about what chemistry I'm going to implement so I have this molecule counter with value n it's going to react with decrement with unit value it's going to produce counter n minus 1 okay let me just do that what happened I forgot to say run skull is not good not strong enough to infer all the types so I need I need that ok we're good so I do counter 10 decrement decrement oh we don't see anything right so there's debugging which I put in now you see we want to know what molecules are now in the soup and what are the values on those molecules so in principle this is implicit this is not something that you see it's not a value the soup is not a value in principle that you can see but there is a debugging function so here's how it works by the counter well first of all counter has a member which is oops which is joined F which is the join definition and then I have a debugging tool which says print bag so it prints the bag of molecules and now you see so the debug output is that there's a joint definition with this reaction plus decrement goes somewhere and the soup contains molecule counter with value eight which is what we expected expected to happen now I suppose I could have put print statements inside reactions and that's also a good debugging tool but let me continue so a very important feature that remains to be discussed is the blocking molecule feature so far what we have seen was all non blocking so these molecules react at some time we don't know when and the result is floating around we don't know where it is this is not sufficient to implement arbitrary concurrent tasks what is missing is the blocking molecule the blocking molecule is that it imagine that you have this molecule and you want to inject it into the soup now ordinarily just drop it and you walk away with a blocking molecule injection low block until this molecule starts some reaction and then the reaction can give you a value back until that happens your injection call is blocked and you're waiting and then you get a value back so here's how it works in the chemistry so imagine that F is a blocking molecule implicitly it has a reply so it has a reply functionality so this reply functionality is represented by this reply molecule which is implicit which is not real you don't define it for fu it's already implicitly defined for every blocking molecule this reply molecule can be injected but in when it is injected with some value that's the value you get out of the blocking call so this is the construction that allows you to get values and wait for some reactions to happen and then yet get some responses back so here's how you would implement in the join run library the blocking molecule you would first of all define like this with two types so this is the type that the molecule carries and that is the type which it will return which will reply back then you add the reaction for example counter with value X and get in with a reply injects reply of X and it swallows counter let's say well we can do whatever we want let's do it like this just for an example so that will finish they will kill our counter molecule but it will reply with the value so once you define the join with that reaction you can use it like this so this blocking molecule looks like a function that you call it blocks while you call it and it returns the value so that is actually the entire extent of join calculus molecules blocking and non blocking there are no other constructions I have not said the word synchronised here I have not said the word semaphore I have not said locking threading or whatever I don't I didn't say that I will run through some more examples a benchmark that I made is that I have this non blocking counter and I put a lot of decrement molecules into soup so I initialize I'm again [Music] I initialize the counter with value thousand and I inject a thousand D molecules which are the decrement molecule and that means there will be a thousand reactions one after another which the runtime will have to schedule and run somehow and I've done benchmark how long that takes using a blocking molecule F which is kind of fetch the finished value and the finished value is the time that the reaction Rhian and then I I can see how many reactions my library can schedule in a second let's say these are very very short reactions that don't do much and so these reactions shouldn't take so much so on a on the machine like this I get about 100 to maybe 200,000 reactions per second so just one word about implementation this is bad by thread pools it can be also backed by akka actor to actor pools with a router and that is actually faster because I'm event-driven akka actors can schedule the closures faster than the threads but it's not a huge amount of gain I mean you expect to be held up in their performance by calculations and not by scheduling closures on threads but in principle that's okay so what I'd like to say is that this is an unrestricted concurrency programming language it can implement anything compliment any constructions that you want futures MapReduce you can do I'm going to I'm going to run a bit faster [Music] this is the code for dining philosophers okay there are five philosophers and five forks for each philosopher I have two different molecules I have defined T and H so this is a thinking philosopher one and that is a hungry philosopher one and I define the chemistry so that the thinking philosopher weights and then becomes hungry while a hungry philosopher needs the two forks that takes a hungry philosopher molecule and the two fork molecules to start this reaction then it waits and then it emits a thinking philosopher with two forks apart from declarations of these molecules this is the entire code that needs to be written to simulate dining philosophers this is completely declarative there is no you can make lots of mistakes here because there are all these different molecules but that's your specification one can always make a mistake in a specification but I write nothing else beyond writing the specification this is fully declarative specifications become executable programs now dining philosophers is perhaps an example that is particularly suitable to be implemented in this way and it's a very naive implementation there is no guarantee for example for typical wait time before the philosopher gets to eat there is no fairness you could have by chance that some philosopher waits a very long time you can fix all this however I'm just saying this is a fully declarative description of non-trivial concurrency there are some additional features I'm cemented in the library one is that I have explicit thread pools if I want so so if I know that certain reactions need to be massively parallel I can reallocate thread pools for them and the fire and other reactions will run on all on one thread let's say if I know that's okay so I can I can do that I can say run this reaction on these threads from this pool and run this reaction always on those threads from that pool why I wanted to implement this is that my previous experience was join calculus was on iOS and Android mobile applications where I implemented the prototype first and on those platforms you must run certain things on the so-called main thread and if you don't do that your application will just freeze so you must say which reactions run on which threads sometimes sometimes you don't care about this sometimes you do so in case this becomes a problem I have this feature another feature is limited kind of fault tolerance so what if I start a reaction and an exception is thrown then I can catch that and I can re-inject these molecules again to try running the reaction again this is a very primitive kind of fault tolerance but it just shows you that the runtime can be smart about what to do and the programmer doesn't have to worry about it I have some more features that I would rather implement next the main question here perhaps more for the audience than for me is what else is needed for this to be industry ready why is it that almost nobody is using it so people who did use it the two people here who did use it may have the answer but I don't have that answer so I'll be very interested in discussing that so yeah so the question is what kind of scheduling degradation will I have you have a very large number of different molecule and different types of molecules so so what you can do is just imagine that your scheduling all these reactions on a single thread so the scheduling happens single threaded because the bag of molecules needs to be locked while you choose the inputs for each reaction so once you have chosen them the reaction has started you can unlock the bag and somebody else can start choosing molecules from the bag but that's the synchronous synchronized part which has to be locked and so it cannot be multi-threaded and unless you're very smart about what reactions can be started and you know that it's safe to lock just one part of the bag and not other parts of the bag that's but that's what I do right now so you might have a big delay in scheduling a reaction because you have a lot of reaction to schedule and it's all done single threaded right now so that's maybe anyway so yeah thank you for your question so basically maybe these features maybe this is this is the reason why nobody uses joint calculus nobody so anyway but this I don't know now there are some let me let me perhaps skip to some overview of other implementations which Sun since we started discussing this issue of why it's not adopted in by the industry now these are all the things I I could have seen I have found on the web implementations of joint calculus now this a dead language this patch to the Java compiler then after this time Joe Camel is alive but how many of you use Oh camel one maybe two right compiler patch of 2003 this is color so old that the syntax is not the same anymore it won't work okay joins library for.net microsoft research project which you can download a binary for for dotnet scholar joins philip hala made the project it doesn't work very well it has many limitations who jensen made an improvement of that still has many limitations but that's what I'm building up one join adds again Microsoft research stuff now my projects my prototypes for Android and iOS don't think a lot of people use that this is an objective-c and this is plain Java which is Android specific so it won't work won't run without Android libraries so what of this is industry ready which one of these this is why I'm trying to push this I'm trying to develop better prototype with more features another problem I should mention is lack of documentation about joint calculus if you read tutorials that are not written by myself you will not understand them I guarantee you will be completely confused by terminology by lack of clear examples of what you want to do there are other approaches to concurrency of course actual Acas actors let me do a comparison briefly here so actor is like a reaction and an injected molecule is like is like a message sent to an actor except that actors need to be created and managed explicitly in your code actors will process one message at the time and they will typically hold mutable state reactions will start automatically whenever the required inputs are available you don't explicitly start them you don't allocate them you don't you just define that they should start this is what you want to be happening many reactions can start at once yes and reactions can require many molecules at once just one and this is this seems to be a difficult thing to understand maybe if you think about actors but when you think about reactions that's natural you need different pieces of data and once you have them you can do something it's so it's in my view this is kind of a data-driven concurrency it is not thread driven concurrency does not process driven commits data-driven you have data you can start working with it if you don't have data just wait what am I supposed to do I don't have the data I mean - wait print but actors are kind of complicated I mean this is the documentation for the actor class and these are the things you need to understand okay all these things need to understand them and that was item one and there are fourteen further items in the documentation so that's kind of complicated if you compare this with this is what you need to know about during calculus that's all these are the concepts these are the syntax that's it you're good to go you're just use it let me before I conclude I just have maybe yeah very little time but let me show you a mergesort example okay so this example illustrates an interesting feature that reactions are defined in local scope they are not somehow globally defined they're defined in local school their values molecule all these reactions they're just valuable define local scope so what you can do is you can define a recursive molecule that defines new reactions in its local scope and then this is how merge sort is implemented merge sort defines its own sorted reaction sorting reactions in its scope injects the inputs for these reactions gets the result merges them and returns so this is the skeleton code from merge sort you define this new reaction and then you inject itself with these molecules which it will inject and so on until you get well this is just a skeleton the foe code is here not much not much much more much more complicated it actually works I'm out of time but let me just give you the conclusions join calculus is the best ever declarative purely functional concurrency model which is more purely functional than anything else you have ever seen and [Music] yeah and actors is just complicated and you don't want to use that ever however even though this is all even though this is all true during calculus is never used so partially because the existing literature is not suitable as an introduction and partially because the implementations are lacking I'm trying to fix both of these at once so keep this space under your supervision learn about during calculus and use it thank you [Applause] [Music]