scale.bythebay.io: Sergei Winitzki, Declarative concurrent programming with Chymyst
Recording: scale.bythebay.io: Sergei Winitzki, Declarative concurrent programming with Chymyst
you furtive concurrent programming finished my name is Sergei vineet ski I work at workday we do Scala this is a side project that I did in my spare time it's an open-source project and I'll show you the github repository for it chemist is a Scala implementation of the chemical machine paradigm of concurrency this was invented about 20 years ago and it is known as joint calculus in the academic world but actually it's not a calculus it's a programming language which is a domain-specific declarative language for our concurrency and parallelism largely it's unknown and unused by the industry or software practitioners so I'm trying to remedy that I think it's a great paradigm by making available this open-source library and that's what I'm going to be talking about today so what problem does it solve we know that it's hard to write concurrent and parallel code correctly the reason it's hard is because we use the tools such as callbacks or threads or semaphores or logs and so on these tools force us to focus on reasoning about state concurrent state mutable state shared state and it's hard to reason about processes going in parallel and each mutating their state and then somehow coordinating or accessing shared mutable state it's also very hard to test such programs because programs have non deterministic runtime behavior every time you run them the result is a little different maybe and never enough testing there are race conditions deadlocks or live vlogs all of this is very tedious and hard and so people try to avoid this by using a different approach let such as using parallel collections spark or using futures using echo streams actors and the chemical machine is one of these approaches that make and currency easier so join calculus or chemical machine in my terminology is the same thing it's a programming language for concurrency a typical example of a concurrent problem is the dining philosophers so how many of you are familiar with dining philosophers so just okay quite a few people so I got this picture somewhere and then I actually looked up who these philosophers are I believe this is Socrates and this is kung fu Confucius or something like that anyway I'm not going to talk about this if since most people are familiar basically if you look at rosetta code for example there are solutions for dining philosophers and all kinds of programming languages so let's look at like c-sharp okay initialize stare down right header line right status line format disposable okay I'm kind of lost try to get right for try to get left for it it's kind of difficult right so that's the kind of thing that's that's I'm talking about it's hard you don't know if their program is right so I'm going to introduce the style of concurrency that I call the chemistry or chemical style of concurrency which is the chemical machine implemented by the chemist library and also I'm I'll talk about the actor model is kind of a precursor to this work how can you see that the actor model is a little less high level than than the chemical machine so if you're familiar with the actor model which I assume well euro are you'll appreciate that the chemical machine is easier to use there are other approaches to declarative concurrent programming which I'm not going to mention any more than just my name such as PI calculus PI calculus is a little similar to join calculus but it's actually harder to use low level compared with during calculus our lines message passing is the same as a Kaka's actors CSP that kind of communicating sequential processes is the basis for concurrency in the go language which is also kind of declarative for certain things but it's also less high-level finally a software transactional memory is another approach so what is joint how do we understand join caucus or a chemical machine so I suggest you think about actors so actors you have to start you have a reference to an actor it send a message to an actor by reference what if actors were automatically started if you don't have to handle references to actress at all you just send messages you don't worry about actors existing or running or not existing or not running you just send messages and everything just works that's the idea you don't want to use threads or semaphores or locks or anything you don't want to use mutable state shared mutable state that's what join calculus gives you that's what the chemical machine gives you the concurrency is much easier easier to reason about which I'll show non examples to understand this however it's a new paradigm you need to have some metaphors for understanding how the reason about it so I I have two metaphors for you so one metaphor is concurrent functions that compute with concurrent data so this is kind of a purely functional world on concurrency the second metaphor is a chemical soup with molecules and reactions so that metaphor is a little more concrete and down to earth and and that's how I like the reason about concurrency in joint calculus or chemical machine so but let's go back to this idea of automatically started actors so how would that work well obviously you send a message and then the actor needs to start consuming that message and working on it so it's like having a function call that's executed concurrently on a data item so what does it mean that we make function calls concurrent well several functions will run at once maybe and obviously they should have no shared state right so we're thinking functionally so each function is a pure function take some arguments and concurrent the executing functions should obviously work on different instances of data not on shared instances so how does the system decide which function to call if you give it an data item well obviously data items have to be labeled in some way for specific concurrent functions so that can be implemented if we have a special kind of site where we store these labelled data items and functions and then the functions will wait for data items to arrive at that site to consume them and start computing their stuff and then the computed results can be emitted back to that site as again new labeled data items so the operational semantics of this is that concurrent functions are waiting and automatically starting to run whenever their data items are available at the site and as I said different instances of concurrent execution will consume different separate data items so that's how you would logically design the system if you wanted to impose there wireman that actors are automatically started okay so I have not so much time to dwell on this but basically if you logically follow what needs to be done if you want to make actors automatically started you arrived to join calculus or the chemical machine so that's but I prefer the chemical metaphor which is that first you imagine real chemistry such a the reaction between the hydrochloric acid and sodium hydroxide and gives you the molecule of salt and a molecule of water so two molecules meet react are consumed and emit two product molecules so this is how real chemistry works now we're going to do abstract chemistry inspired by how real chemistry works so AB stroke a masti means that we have this imaginary chemical soup that contains instances of abstract molecules molecules of any kind that we define at will and then certain sorts of molecules will combine and start a reaction so for example we can define abstract chemical laws like this like molecule a and molecule B react and the result is molecule a now obviously that cannot happen in real chemistry that just the molecule B disappears but this is abstract a mystery we don't need to follow physics here or for actual real-world chemistry it's completely abstract we define whatever we want such as molecule a and molecule C react and yield nothing both molecules disappear and nothing is emitted back it's completely fine because it's completely virtual and abstract chemistry so here's a diagram that illustrates what what I just defined in these laws now the program code will define that molecules ABC and so on exist and these laws exist so an initial time the code will emit some molecules into the soup and then there will be a runtime system that will run all the available laws finding molecules that can react running the reactions emitting the products back into the soup and continuing this forever now notice that the Kin in chemistry each pair of molecules react reacts in parallel concurrently with all other molecules they don't wait for each other and that is possible because they operate on different data items so that's the model of concurrency we want to imitate so imagine we implemented this runtime simulator the chemical simulate or the chemical machine how would we use it to actually perform computations we need to add some data to this so we we say each molecule now carries a value or a data item a value of some type let's say integer and that will be our concurrent data so each molecule now has a type of value that it carries each reaction that let's say you have a plus B goes to a now a has a value so this value Z on the product of the reaction has to be computed somehow from the values X and Y on the input molecules so the function that computes Z out of x and Y is the body of the reaction this is just analogous to the body of the actor that takes the message data and computes some outgoing message but here we can have several molecules coming in at once so this is more general and actors it's like actors that can wait at wait for several messages to arrive at once and then so that's how we are going to simulate computation so we're going to define the molecules define all the functions that each reaction and the molecules have come in and come out so here's an example code actually I'll show more examples of course just the first example right here [Music] the site is a function call it declares the reaction site where the molecules and reactions are stored then we say a plus B goes to basically a and Z is computed as some function of x and y so x and y are input values and z is output value and we could it could have a side effect also in the reaction that's that's fine we can write arbitrary Scala code there but we don't have to usually so the semantics is that when the reaction is defined and the molecules are emitted then the the runtime will look for molecules that can be consumed so for example a and B so it will see whether some a and B has been emitted into the soup at this site and then if so it can start the reaction a and B will be consumed or two instantaneously disappear atomically so that's a synchronization primitive and then you compute a new value and you emit the molecule a with a new value in back into the soup and then let's say there are more B's in the soup then this can can continue so a first example would be to have a concurrently running counter so let's say you have a counter with an integer value you want to increment and decrement it from different concurrently running processes and you want this to be safe so there no no no mistakes due to shared States so here's what you do the only way to do anything is to define molecules in reactions so obviously the counter value must be on some molecule so let's call this molecule counter the decremented increment commands are modeled by emitting molecules so let's call these decrement incur and these molecules have a unit value so they we don't need value in them so let's have a unit unit type so then we say counter molecule reacts with decrement molecule and gives you a counter molecule with decremented value so the semantics is that both molecules are consumed instantaneously and then this new molecule is emitted and the next reaction is that increment will increment the value and do the same thing with the molecules now initially we in emit a counter with value 0 so then we can emit decorate and encrypt concurrently in any amount and you see because the semantics of reaction is that both input molecules must be consumed atomically and at once there's no way to mix this up there is no shared state there is no mutation even I mean this is this purely functional in a sense so suppose you have 5 Decker molecules and 10 in cream alla cules but only one counter molecule so only one reaction can start at a time just because the molecules in are not there enough to start more than one reaction at a time so in this way you completely make it safe only one Decker or incur will react with counter at at any given time and so there will be never the problem with shared mutable state when one thread starts to increment another start to decrement at the same time and you get an error so that area is completely impossible here's how you write this program in chemists so first you need to define these functions that emit molecules they are called molecule emitters and these are defined in the syntax so counter is integer molecule this is a unit valued molecule then you declare reactions using this go function and the reactions are defined as if their partial functions with pattern matching so in this case it's very easy interval but in principle this can be arbitrary Scala code partial function pattern match of any kind with guard conditions with case classes with all kinds of things you can do whatever you want here except that you only need you only can be can give one case at a time so here is the same code that as I was writing before here in pseudo code is kind of a chemical notation and that's how it works and then finally so you define these two reactions you define a reaction site by saying site with these two reactions this activates the reactions so after you say site you can omit these molecules and the reactions will start so this until you say site nothing is running so these reactions are values so this is a value of type reaction which describes the reaction it does not actually run anything yet when you say site you activate these so this can also be defined in line so you can just say site and then put this code into the into here these are just values so there's no there's no magic otherwise magic happens is that in that the chemical machine will run behind the scenes so here's what you do then you say counter 10 in cranker and then finally you wait for things to happen right this is all non-blocking so you say counter 10 it's a non-blocking side-effect of emitting a molecule into the soup we say enter is a non-blocking side-effect of emitting molecule enter into the soup so counter call or return unit it will emit the molecule will return right away there will no be there won't be any wait so this is all automatically concurrent and automatically non-blocking so at some point so after you do this initially the soup will have maybe this state of having 3 molecules in it and then it will run and let's see yeah so let's connect these two metaphors just very briefly so reaction consumes molecules in this chemical machine is the same as function consuming input input values so this is how reactions implement concurrent functions reaction emit more emits molecules as a result the same as functional returns a result value emitting molecule with value is like lifting data into this concurrent site or concurrent world if you wish and when you define a reaction like you did here that means you're lifting this function into the concurrent world and that's so this is how these metaphors are actually the same thing I prefer to think about it in chemical terms but you can also if you want think about just concurrent functions and concurrent data so let me perhaps show you all that I have to show you this first there's one other feature which is the blocking molecule so right now we have seen all molecules or non-blocking so you emit these molecules into the soup but you don't wait for anything there's another thing another feature of the chemical machine which is their useful blocking molecule which is a molecule where it's emitter will block the calling thread until some reaction starts consumes this molecule and returns the value back so in this way you can implement blocking weight if you need to so here's how it works so you declare an emitter let's say F for fetch so if you want to fetch the value of this concurrent counter and you want to make a blocking fetch so how do you do that you declare this as integer and string types so integer is the type of value it carries and string is the type that comes that comes back they reply value type then you you define the reaction like this implicitly this molecule F carries an a reply emitter which you do not put into it when you emit the molecule so it's it's an automatically included when you actually start the reaction so you have this reply emitter so the reaction can use that emitter to emit the reply computing some value and that's for example will consume the counter C consume F and emit the reply it will not emit molecules back let's say so here's how would you use that you would emit C with values 100 and then you would emit F with value 200 then you have C and F this reaction can start X will be 200 Y will be hundred this will be 300 string 300 will be on the reply and that magically will be the result of this blocking call so this feature allows you to block and wait until something happens which is useful in tests perhaps not very useful in actual code because you'd like everything to be non blocking as much as possible so the first example code that I can show now is that you count many let's say increments or decrements until you reach a certain counter value and then you need to reply to some blocking molecule and so you can kind of execute a test waiting until something is done so let me show you the code for this so we define a molecule C molecule Decker molecule finished molecule yeah just like I said this is abstract chemistry you can define any molecules you want any number of them molecules are not threads they're just little pieces of data it's very cheap to define different kinds of molecules or reactions so there are three reactions now the first reaction is that this this finished molecule reacts with the get molecule and produces a reply to the get so we will eventually call get and we hope that the finished molecule exists so until that exists the get call will be blocked the second reaction is that the deck ramallah q will decrement only when the value X is is positive and if it's not positive then no molecule will be emitted and actually I would actually write it like this maybe maybe this is better because then this reaction won't even start if the molecule is with the value X that is not positive so when the molecule has zero value then we omit the finished molecule initially we omit C with value 10,000 and we omit 10,000 Decker molecules so let's see if this if this runs we omit 10,000 extra molecules and when we countdown yeah countdown to zero finally this last reaction will run finished molecule will be created it will react with a get molecule will get a reply and this gate will unblock so this is how the test works any questions at this point yeah the rich algorithm Oh not familiar with that sorry I'm not familiar with that the question is whether the question is whether there's a relationship between the RET algorithm and joint calculus and we can talk about this after afterward all right okay well I I'm not familiar with with those systems so I cannot comment unfortunately all right so so this is how it works another interesting thing about implementing the chemical machine as as part of Scala as a DSL in Scala is that we can use all the features of Scala all the functional programming features local scopes types everything is just transparent the primitives that I gave you is the entire new thing that is added so there are these molecules and reactions are completely orthogonal to whatever programming language you embed them into you can do this in C in in Python in whatever it's completely orthogonal but we're embedding it in Scala so we have great functional programming features so for example we can have a molecule with this type the type of value that it carries is an emitter is another molecule so we can we can do whatever we want and it's all type safe we can also define molecules in local scope so the result is that we can make this counter example example of the concurrent counter that I made and we can define all of this chemistry in the local scope of some function the function will return the emitters for the molecules dekker and get but it will not return the emitter for the molecule see and the result of that is the outside code can make a counter so it will create this counter see and it's and emit it but the outside code does not have any access to this counter it's completely encapsulated so it can get the value it can decrement the counter but it cannot screw up with this with the chemistry so an example of screwing up would be to emit five more molecules C with different values so that will completely derail this logic because then the decra molecule will react with any of these counters and the get molecule react with some other counter perhaps so so this whole idea of counting just breaks down if you have different copies or different instances of the more of the molecule C at the same time so we have to guarantee that C is emitted only once to be very easy to guarantee if you put that into local scope so because local scope is tightly encapsulated we get a benefit that's completely independent of join calculus so so that's why I say it's functional programming plus join calculus or encargo is kind of neutral to the language you're embedding it into I made previously join calculus implementation and Objective C for iOS and in Java and Android it's ugly but it works it's completely orthogonal to your language so Scala is a great language for doing this you can have very nice and visual syntax another so there are more examples I can show for instance this example I can implement future in terms of molecules and I say future of and that's you know that's that's similar to having a future and can implement MapReduce in the interest of time I I will skip this for now but basically the way your reason about it is that you imagine what molecules need to be present so for example from appreduce you want to put data on a bunch of molecules and each molecule will start a reaction and that will start automatically in parallel and then at the end you want some other molecule to react with the results and gather the results and aggregate them so you just think about this visually like that and you get your MapReduce finally I want to show the example of dining philosophers now you see what happens with dining philosophers is that I define molecules that represent a thinking philosopher and the hungry philosopher and then I write these reactions between these molecules so for example thinking philosopher is this molecule it reacts just by itself doesn't need any other molecules to start a reaction and it it starts to think well thanks for some time and then it emits a molecule with a hungry philosopher and so on for other philosophers and here's the hungry philosopher takes two forks next to it next to the philosopher so and then starts eating and then starts thinking puts down the fork puts down the other fork now this is the entire code I mean I I showed you the C sharp result before but here's the here's the executable code right so this is the app these are the functions that think and eat these are definitions of molecules this is the code that I'm done you see this is completely declarative I can run this and you'll see what happens so that's that's the power of join calculus or the chemical machine it gives you the clarity of solution for concurrent problems so let me very briefly run the comparison with again with actors so the main difference between actors and and join calculus is that in actor's message emitters are specific to each actor reference in joint calculus message emitters are specific to data so for example in actors you have two actor references we need to send each one of them a message here we define reactions between data so data X is labeled by a Y is labeled by B and B can be consumed by different processes and so message emitters are really specific to data not to processes it's much easier to reason about data about data that is present then the reason about processes that run and change their state as they run or they terminate or they didn't yet terminate it's much harder to reason about that I'll skip for the in the interest of time but there's an interesting example of a concurrent merge sort algorithm which is which works by initiating a chain reaction so the merge sort on an initial array initially initiates reactions from merge sorts on the partially raised and they initiate their own child reactions and so that dynamically creates a tree of reactions when everything is done you have the entire array sorted and the parallelism is automatic this is the code you see it's very short I define a reaction here a new site a new molecule inside the reaction here so the the ones that I set in brown or yellow they are defined recursively so it's a reaction that defines recursively a different reaction inside it and that runs that which defines again new reactions the entire code is here this is this is the entire code that perform merge sort so I don't have time to explain step by step how this works but this is the idea is that it's a chain reaction that recursively creates more reactions and all of this is completely static type checked type safe and yet dynamic in the sense that you you can create any number of new reactions and new molecules depending on data all right so there are other things that I would want to say but one thing is that don't look I'd like to say don't look at the Wikipedia page okay just don't look there if you want to learn about join calculus don't read this I don't understand a word of this in this look communication occurs only on defined names okay you got it right I mean it doesn't occur on undefined names right okay anyway the unfortunately join calculus is a is this thing where they have this special jargon I prefer the chemistry terminology they have this terminology so I have a dictionary here for you there are many previous implementations only one of them is actually useful which is a Joe camel which is a maintained fork of Oh camel compiler so I'm trying to make this useful for the scala community and you're welcome and encouraged to check out my repository which is this one so please let me know if you are interested and I think I'll just I'll just stop here because I'd like you to think about it and ask me some questions thank you yes so the question is if I have different molecules that can trigger different reactions how are they chosen the reaction so this is non-deterministic so if you have let's say molecule a so counter can react with decrement and increment and well if you have all of them at once so this is non-deterministic so there are certain ways of controlling this but basically it means you are facing non determinism and you should face it you should organize the chemistry such that the molecules react in the way you want you should not depend there are no way to say priorities set priorities on reactions or molecules and it's it would be self-defeating if you did so you should face non determinism make your code so tight and it's easy to do with molecules much easier than with other other paradigms but you have to do it you have to face it so the quick so the question is are the reactions triggered in the order model molecules are emitted so I have I didn't show this slide much this slide shows you you know under what conditions that is true so there's there's an automatic optimization where there's static analysis on the code that you wrote and it determines whether certain molecules can be consumed in the order they're emitted without breaking down the semantics because that sometimes can break down the semantics but basically you can check that this is so in your code and if you need that you can you can make itself yeah how would do I relate to the to what okay the the question is are all the cores are used automatically or is there a way to fine-tune that so I have features to specify thread pools for specific reaction sites or even for specific reactions so if you need some reaction to be high priority low latency you can do that by creating a high priority low latency thread pool and using that I do not directly control cores all cores are used so it's yeah it's the Java thing one last question order of magnitude so look the question is this scale scaling with the number of molecules so how does it scale and what are the constraints and 100 million molecules so molecules are data on the heap and they're not threads the number of threads can be 5 and you can run so basically each molecule is a small data structure I have not particularly optimized right now for this use case I cannot tell you exactly how many megabytes you need 400 million molecules but there are just data structures and in the heap on the heap so I could probably and there some if molecules data is very simple then it's stored in a hash map if it's not a huge amount of data on each molecule then you can you can have hundreds of millions of molecules easily thank you very much you