Eric Shull: Communicating Sequential Processes (September 22, 2015)

well thank you it's good to see you here this evening I like the informal set up well like Jesse said my name is Eric I work here at atomic I'm a software developer and the first question I have for you I expect this to be interactive so you'll get to participate or have to participate as the case may be how many of you have heard of lambda calculus okay a number of you how many of you have heard of Pi calculus okay well after tonight you'll have heard of PI calculus so what we're gonna do is we're going to talk about I'm going to talk about communicating sequential processes and give you some background on the problem that it's trying to solve and how it goes about it what it's like to work with it and then we'll go into some examples using the go programming language which is very directly related and then give you a feel for some of the syntax by this point go has been out for several years a lot of other languages have picked up on the ideas that go is trying to share about how to go about doing concurrent programming so like Jessie mentioned closure has a core async library which tries to do things tries to do communicating sequential processes very much like go does there's some other libraries for things like Python and Ruby that use the mechanisms that those languages have whether it's threads or what might be called green threads or co-routines and we can talk more about that later if you're interested but to start out with there's a problem the original version of this talk was called effective communication or why telepathy might not be such a good idea and this is really the telepathy problem is more or less what you have right now in software development when you try to do low-level concurrency programming you've got a lot of different things going on at once you've got different processes or threads and they're all trying to access the same memory the same variables and that can create a whole host of problems it can create new problems when you try to solve it using particular solutions and in particular it all comes down to non determinism you've got a lot of different processes going on at once you don't know which one is going to happen when sometimes they'll be interleaved so if you have two different threads just printing a stream of numbers you can end up with you know two numbers from one thread a number from another thread three numbers from the first thread you don't know what's gonna happen it's gonna depend mostly on the operating system scheduler not on anything in your code and that creates race conditions where one thing happens before something else and you get into a bad situation because suddenly you have two things that are say both trying to update a number at the same time or change some values and in the effort to solve those you might use mutexes or locks and that can actually create a situation where you have deadlocks where you have all these different threads all waiting on each other before they can do anything and because these problems are non-deterministic they're very very difficult to reproduce and when they're difficult to reproduce that means that difficult to debug and when things are difficult to debug you have a hard time creating reliable software so with so much depending on software these days reliable software is very important you want your bank to have reliable software you want your your health insurance company and your hospitals to have reliable software so if you've got a lot of different things going on and you're in a situation where you have non-deterministic code because you've got concurrent code then sharing memory can lead to buggy software the people feel is unpredictable so there's a variety of solutions to trying to handle the the problem of sharing memory and these are just a few of them some are better than others but ultimately they all share some common weaknesses and one of them is that they're complex there's a lot of conceptual overhead to deal with anytime you're doing say you want to update a value if you know that other threads might have access to this value then you've got to say wrap it in a lock do you have the lock if not what do you do do you wait longer is it possible that you're in a deadlock situation when you are done you have to make sure to unlock it if you're using it otherwise the other things that are waiting on it won't be able to proceed and it's doable but it's easy to mess up this is sort of the concurrent this sort of parallels memory management that if you're not confident about how it should be it's very easy to start creating memory leaks in places here it's the opposite problem it's not stuff just running off a head and growing bigger it's just stopping dead in its tracks because it's waiting for something because you forgot to release a lock that you had created one of the other weaknesses that it has is that those can be leaky when you're dealing with say a function that deals with locks you might not think about calling that function having to do anything with other threads you might think it's perfectly safe that there's no reason I should share it but deep down you end up having to deal with other threads and then anytime you call that function you have to start worrying about whether or not you have to start worrying about what that function is doing down at deeper levels and the third problem that it can have is that these solutions to these different concurrency problems don't necessarily compose very well it's you might end up taking two things that seem to work well and when you put them together say atomic operations and transactions or mutexes and locks that you get unexpected behavior there's not a reliable way to necessarily think about these things and you generally don't see sort of like higher-order locks or some of those things that enable that show that the the concept is composable so what we want out of a concurrency solution is something that's simple abstract and composable and of course we wanted to be concurrent and so where might we look for inspiration does anybody have any ideas Erlang okay the actor model is one example Scala also I think has the akka library for doing the actor model that's a good point and we'll touch on that a little bit later has anybody in here done any sysadmin work anybody done any shell scripting what's what's one of the things that you learn in shell scripting beyond just invoking programs it's one of the core sort of paradigms and say the UNIX philosophy but about how you stick programs together message passing pipes so pipes are a really good place to start thinking about CSP communicating sequential processes for starters they're simple you it becomes very easy to take one programs output and send it as the input to another program in fact it only takes one character in a shell scripting language generally speaking and it really is not any more complicated than that and that means that you can chain several of those steps together I know that I've written shell scripts that use piping piping piping piping piping and then you end up really proud of it because of the information that you were able to parse out of maybe a very big log file or some other things that that show that it works very well to just glue piped output in to piped output and so they stick together very well like Lego blocks they're also parallel they can all run at the same time right the the first program when it's done with a line of text it can out hand it off to the next program and then that program can work on that while the first program is still working is working on the next line the classic example in this case is doing your laundry once you take the clothes out of the washer and put them into the dryer you can put a new load into the washer and have them going at the same time and generally speaking this is a very non leaky way to compose your programs together rarely does one program have to concern itself with even the implementation language of another program all it has to worry about is that interface boundary what is the input look like and so you can use completely different languages and you don't have to worry about the internals of what comes before you or what goes after you and so that's a really good starting point for thinking about communicating sequential processes this is a it's actually in algebra described by Tony Hoare and if you wonder why he's called Tony it's cuz the a stands for Anthony all the way back in 1978 you may already be familiar with some of Tony Hoare his work he actually invented when he was 26 the quicksort algorithm and you know we take it for granted today but that was 1960s so though non-trivial in those days and so CSP is really less invented and more described because it's more of a math it's not say necessarily even a language it's it's an algebra so I mentioned it was called PI calculus and horrors' paper generalized some principles of what pipes deal with at a very shallow level and he created a whole notation for describing it and lest you worry this is all the math that we're gonna have in this presentation if you'd like to read more you can read his papers which have more of the abstract formalism very thoroughly but what we're going to talk about here is more of the pragmatic side of CSP and actually using it yes I will dig those up yes and our supply links and so if you're interested in the algebra which it's it's dry reading but it's not too bad all things considered he doesn't just jump into trying to make it as abstract as he possibly can it's really fairly basic and it's a very gentle introduction and the reason I bring up the fact that it's an algebra is not because you have to understand that how algebra in order to you really use CSP I know sometimes if you're familiar with Haskell you might feel like you have to understand category theory in order to be able to use Haskell and CSP is not the case the reason I bring up the math is because the it really demonstrates that it's it's something that you can easily reason about they've actually created a whole mathematical notation describing what's going on here and there's rigor behind it and so it's not just the sort of thing that's been rigged up and just happens to work say like a Turing machine so you probably I know I haven't heard of like immutable object calculus or monkey-patching algebra so those those by comparison are much sort of conceptually harder to reason about strategies for dealing with different problems and this is really something that at the ground level without any computers involved whatsoever is solid and something that you can think about no there's a reason is because it's not something that you can apply any sort of mathematical rigor to it's just like wow I I did this and it works and so that's that's usually a sign that you're in for trouble down the road so just the whole idea here is to make software more maintainable and the CSP has really built on two very basic primitives the first one is processes this is not necessarily talking about your operating system processes this is a generic process which you might think of as an ordered sequence of operations it is not something that you have you know threads within a process like you would for an operating system process and in the math there's no shared memory if one process has some object or value no other process has access to that so they're not they're not sharing anything and that starts to solve a lot of your problems that you end up with in trying to create concurrent software we'll get into that a little bit the since it and if you look in the original paper the the math nothing is mutable in math so what the idea is that when when one process hands value off to another process it no longer has it if you start thinking in terms of immutable objects it's much less of a problem right you think of it you know it handed off a copy of this it's just this one operation is to copy it and pass it off and then you don't deal with that the the original formalization of it is really just saying like once you hand it off you no longer can do anything else with it which you're right in practical terms is not the way that you end up dealing with values so the other primitive is channels these are the ways in which processes communicate and you can pass whatever you want so pipes you can pass texts you maybe pass bytes when it comes to channels within a programming language that implements CSP you can really pass whatever you want it can be hold they can I thought about having an example of that but I still have a I've still not come up with like a really good reason to do that the closest I've got is some sort of like connection pooling that you can say you know pull from this channel and but you can definitely do that so anything in a language that's a value you presumably I'm speaking in terms of go since that's most what I'm familiar with it as far as its CSP is anything that's a value in the language you can pass over a channel and so yeah that's anything trees linked lists types that you define and in go things are passed by value so when you pass something over a channel we're doing what you're talking about where you're copying it effectively and then handing it off to something the caveat there is that you can pass pointers in which case you you actually are sharing it and that's your own fault so in the original CSP specification it's really a case of once you pass a value you lose access to it like we were talking about so that's used for communication between processes and you can pass data structures and as far as the math is concerned the values aren't shared so there's a lot of different arrangements that you can have between processes and channels and just to give a high-level overview you can have the obvious one-to-one relationship the boxes here would be processes and then the fat arrows would be your channels so in this case this process is putting a chant as putting a value onto this channel that this process is able to pull off that channel so you can think of it in a sense as sort of a publish/subscribe and then you can have obviously extensions to this idea you you can put it on a channel that a lot of different processes are listening on this and in this case this is not really a published system where each of these three processes is going to get whatever values we put on here is whoever grabs it off the channel first so think of it as almost like a work queue you've got these different workers who are all pulling items off and when they pull one off the others never see it and so it's really a case of who got there first obviously you have the reverse of this where you've got a lot of different processes feeding data into a channel and one other process consuming those and then just the end end version where you can have that so that you mentioned Airline earlier that sounds a lot about airline except it's synchronous so when this guy here puts a value on this channel he sits there and waits for somebody to take that before continuing on and obviously he has to wait if there's already a value on there you can you can in go and quarry sink you can get around that by making this a buffered channel and saying that you can put multiple you know n values on it and you won't block until you've gotten values actually on that channel waiting to be taken off and then you'll stop but in this case we're just talking about you've got you put a value on and you're just gonna hang out until that value is taken and then once it is you can continue on and the reason to do that is because then that gives you a point at which you can effectively synchronize between different processes and it makes it a lot easier to reason about then you know he just fired this off and then where did that go and then he went on to here and so but again that's parameterize Abul you can do a variety of different strategies and so the other thing that's different from the actor model such as an airline is that you're putting values onto a channel you're not putting it into some agents mailbox so this guy right here might not know anything about this other process in fact he doesn't because processes don't really they're not in you know they're not named at all the only way that you can interact with them is via channels so this guy is going to put a value on that channel and he doesn't know whether that channel is listened to by anybody by one process two processes five processes he's just putting it out there at a particular place where other people can pick it out where other processes can pick it off whereas in the actor model you're you are you know about the particular instance of an actor and that you're sending values to that directly so we're gonna get into go now and the connection between CSP and go is fairly direct early on Rob Pike worked on a language called squeak which was directly inspired by the CSP paper and then he refined those ideas in the language called creatively new squeak and if you look at new squeak and you're familiar with go you'll see a lot of the syntax in terms of the concurrency channels and go routines is shared with new squeaks so that's where it really started out just alright so we mentioned processes and channels what CSP calls a process go calls a go routine and they they're being clever in part it's because you know when you're talking about computers the term process is obviously overloaded you don't want to create confusion with operating system processes and make people think that you're spawning a brand new process every time you create a new one of these things and they also wanted to sort of invoke some similarities that it has with co-routines which are you know functions that you can suspend and re-enter and those sorts of things because you can get some co-routine like behavior with go routines and so like I said they're being clever the other difference between go and the CSP papers the CSP paper really thought of channels as being one-way channels you put a value on and they come out the other end and they never go back and go you can create one-way channels most of the time well you see our two-way channels because it doesn't make a big difference so go routine the reason it says functions in here is because a go routine and go is really just a function that you invoke with the go keyword and that will create a new go routine so like I said a note about them is they're not threads so they're actually much much more lightweight than threads they're on the order of a few kilobytes and so your your program might have millions of go routines and that's not really gonna you can still do that on a very resource constrained device it's not something that would weigh you down like having millions of threads running at a particular time so we're gonna go through some examples one of the obvious examples is to do asynchronous i/o so how many of you have used JavaScript or node where you've all you've got is asynchronous i/o so when you when you go out - just want to get some data from disk if you're using note or you want to get it from an HTTP server if you're using it in the browser you have to give it a callback and when it gets the data back it'll call that otherwise it's gonna it continues on with the the execution you don't have blocking i/o there are some special calls where you can get blocking i/o but generally speaking javascript is going to be asynchronous so go by default is synchronous so what we're gonna do is we're gonna switch over here and work out some examples let's see all right okay so just to give you a taste we're gonna create a basic I've got a couple servers running here which are slow so that we can see how it works to make HTTP calls so I have those running locally there and so we're gonna get the response the underscore is because I don't care about the errors at this point this has been so we're just going to get the B is bytes we're gonna get to read all the bytes off of the body and then convert those bytes to a string and print so in order to do this we actually need some imports yes yes let me see what I can do is that better yes okay perfect okay so this is a basic blocking call and what we can do is we can just run that program and we can see that it returns too and that happens to be how long how many seconds it waited before returning a response so if we were to run this again it's gonna randomly choose some it might be longer than two seconds because it's X or four seconds because it's actually building so to demonstrate that this is synchronous by default we're just going to do this several times and then go we have these weird little assignment operators which also declare what type they are and we just have to take those off since we're reusing those variables so now what we're going to do is we're gonna see this sequential happen sequentially so we've got that one with four seconds another one took four seconds and then two seconds and if what we do let's just build this so we don't have to worry about that and then if we time how long this takes it should be fairly close to the sum of all the different numbers that we see come back so yep sure enough took about six seconds a little bit longer immigrants you all right I know how if I'm in anybody's way so that's a really basic example of the fact that go by default has synchronous i/o and what we can do is we can go and we can make this asynchronous and say you know what there's no reason that we have to wait in serial right we can wait at the same time so what we'll do is we'll create some go routines which like I said use the go keyword and then you're just going to have an anonymous function and the difference is that you actually still have to have the parentheses on here to invoke it but beyond that we're gonna this will create a new go routine so just wrap all these and then alright so if we do that then we can go run sink and no output the reason for that is because you've got a main go routine and then we fired up these three other go routines and then the main go routine finished and it said we're all done so what we've got to do here is actually tell it to wait for each of these to finish before exiting and to do that we're going to create a channel so we don't have to create a fancy channel we can just take one that takes a boolean and what we can do is once we've done this we can say you're done and we need to do that for each of these and this is not quite enough we have to do one more thing which would be to wait for each of those so this syntax says put the value true on this channel and this syntax with the arrow on the other side of the channel says wait here and return the value that you pull off this channel in this case we don't care about the fact that these are all true now when we do this we should see hey look those two came at the same time and and so if we time that we should see that it only waits for the longest one and so yep four seconds so this is an example you'll notice that in this case these are all going to be in order because it's just the order or the the time in which they came back and this is an example of a really useless sorting algorithm called sleep sort and generally speaking is not very applicable than probably anything that you're doing so this is an example where what we did is we took a language which by default has synchronous i/o and made it asynchronous if you're using javascript you would have to do this what you do is you'd pass functions and we'll as callbacks and we'll look at an example like that in a little bit and they would pretty much do what this does right here where they all go out and they just run down through and then they all wait in parallel so when we want to look at next is okay so that's an example of sure right so sure so let's walk through this a little more clearly so we're creating a channel done up here at the top and then when each of these go routines finishes and gets a response back they're gonna put a value on done odd so what the main go routine does is it creates that channel fires off these go routines and then sits here on line 32 and just waits for somebody to finish right it might be this third go routine second one first one it doesn't it doesn't care once that one comes back then it goes on to wait for the next one on the very next line and then it goes on to wait for the third one and then once those it gets back all this this is a really terrible design in the sense that if I were to go in and add another IO call then I'd have to go and add another done and they're sort of separate in the code and be an easy thing to screw up this is more demonstrating that you it's very easy to take something that synchronous and make it asynchronous in CSP and which to me is a nice thing rather than having to choose a platform that either is synchronous or is a synchronous you and go have a choice whether you're you're gonna have some event be a blocking event or a non blocking event does anyone have any other questions about that it's easy for me to go fast because obviously I know what's going on here so if it's if anything is not clear let me know okay so let's actually do the opposite of this and create a new one called async so well let's see so we looked at asynchronous taking something that was synchronous and making it asynchronous let's actually look at the reverse of that now taking something that's asynchronous and making it synchronous and this will so okay so we have we're gonna create a new file here and what we're going to do is let's say that we've got a function called fetch that takes a URL and a success function and this would be very much like what you would see for i/o in JavaScript where you just give it a callback function and that's kind of where you end up being stuck so this is kind of a reimplementation of the JavaScript say Ajax call but other than that it's going to end up being just what we saw in the last example as far as the mechanics of making the HTTP request and then we're just gonna pass what we get back to our success function this function doesn't return anything the success function doesn't return anything and that's some of the pain of dealing with purely non blocking system is that these values go into these functions and then it becomes a lot trickier to get them back out and that's where things like promises are trying to help so let's say that we're gonna make a call to the same slow server and we've got to give it a function which takes a string and then what we do here is let's say we just want to print that and then let's do that a few times and we'll probably have the same issue that we had before where we have no reason no output so let's use similar trick we'll say and okay all right so I think those just happen to be in order if we did this again it probably won't be oh right right what am I thinking it's this is the asynchronous example so the trouble is say you wanted to combine all three of those bodies you get back a response from here here and here and if we wanted to add those up we're not actually going to do that right here but if you wanted to do that you're kind of stuck because they've got your you have this in this function and you start having to jump through some hoops in order to be able to get values that get returned to those functions all in one place together and so there's since this is how JavaScript works javascript has some libraries for doing this but they're sort of not they're not trivial and so if you try implementing it yourself you're you're gonna run into trouble so in this case though it's as simple as rather than waiting here at the end let's just wait after each one and then we should see that this takes as much time as it would if you were synchronous so okay so it's not in order anymore it's not synchronous it's blocking and so let's take a little bit longer look at what's going on here what happens is when this one gets done well you run through on your main go routine you've this fires off a go routine this fetch fetch function and then it sits there and wait and when this fetch function comes back and actually calls its callback that's when this done channel gets a value and here at line 24 we're able to continue on and the same thing happens three times so if we wanted all of those bodies in the same place say we just wanted to print out a you know string of them get concatenated together that's as easy as changing this to a string and saying rather than printing just send it back and so now we should actually do something with this let's say we'll just make the result an empty string and so then we can do something like this and we'll just concatenate all of those and then print the result at the end this will actually it'll look similar but what you'll get is you'll get all your output at the very all at once there you go so you in this case had to wait for 11 seconds in order to get that output but you can see that it all came it didn't it didn't all come together necessarily but it did come in the order in which you did things in here and you can play with different permutations of that in order to you know maybe you don't care about the order maybe you just want all those values at the same time in which case you can go right back to what we had at the beginning where you know we've got all of these happening at the same place in which case they would all do their weighting in parallel but you would still be able to get all the results out of these functions where they're effectively in sort of dead-end code unless you want to go through some extra work does anybody have questions about that sure I couldn't tell you I I pretty much always use the format library as well and the print line and printf and discovered that some point that it had a print function I don't know whether it's like not recommended for use but so this is a good time to talk about something that Rob Pike who's one of the inventors of go likes to touch on which is the difference between parallelism and concurrency parallelism he describes as being a lot of things happening at once or multiple things happening at once so say you've got a web server and you've got lots of requests from different people coming in you're handling them all in parallel in order to be really parallel you've got to have multiple cores concurrency on the other hand is what he described is not doing a lot at once but dealing with a lot at once and the distinction that he draws there is that you can do with concurrency you can do concurrency with a single core which means that you're not necessarily doing multiple things at once what you're doing is you've got a series of you've got several different processes going but in order for one to start another whatever one is running has to pause and so think about it maybe like you're you're at work and you're working away on a problem and then you get some email you have to stop doing that and go deal with the email and the email requires you to deal with getting a conference room or a calendar item and you have to go and switch to you know another thing that you have to deal with that would be concurrency you're dealing with a lot at once in a sense you've paused your programming you've paused your email in order to look at the calendar you're not doing all three of those things in parallel so that's some of the difference that he talks about between parallelism and concurrency with in this example where we maybe wait all at once it's deceptive because you're what you're really doing is you're it's more concurrency because you're dealing with each of these requests at the same time but you're not doing anything with them so you're not doing processing of you know an HTTP request where you're having to go to a database and do all sorts of processing while you're doing a bunch of other people's requests as well this is maybe not the best example of that but I think it's an interesting thing to consider when you look at when you think about how to solve the problem are a lot of problems you don't have to solve in parallel but it does help to think about them as being things that happen concurrently different processes all at once that you might suspend and that work together actually and so one of the other examples one of the other examples it uses for CSP is event coordination so you might have a bunch of different processes doing stuff and because they can talk to each other you can actually coordinating them much more conveniently than if you were trying to do it in say a system where you're working with different threads and they're having to pull some shared memory somewhere we don't have to go into that right now but if you're interested in that let me know the and then the last the last example of what it's useful for is sharing and I bring that up because go actually has a one of their mottos is that it is don't communicate by sharing memory share memory by communicating so and sort of unpacked what that that means is that in a lot of cases what's going on where you're using mutexes and locks and sharing memory and you've got different threads what's going on is that you're really trying to communicate between threads but the only way that you have to do that is by sharing memory between them and then you're creating other problems CSP gives you the option it bakes in communicating between threads as you're primitive and then that allows you to share information between those processes over those channels rather than having to share memory in order to get information from one process to another and it simplifies a lot in part because you have some reliable rules for handling for dealing with those channels such as when to block and when you don't block and you so it's much easier to reason about but it's it also makes the safer thing much easier to do it deals with the polling really at the length of the level of the execution runtime rather than something that you have to deal with and so it's a it's a higher level way of thinking about concurrency so that's a fairly brief introduction to communicating sequential processes I really like using it and go I have not done a really big application and go which would really take advantage of some of those things I know that most of the time were I encounter not encounter it but where I wish I had it is working in other languages that don't have it any time I want to do something in the background and you have to go and install some sort of job queue infrastructure in order to be able to just you know return a response while you continue doing something else I always wish I had just a go routine there that I could fling out and do so the easiest way to get started if you're interested is to just play with go or play with any of the other CSP libraries that different languages have available I find that when I play with it I understand it better and when I understand it better that actually enables me to use it

Channel: SoftwareGR

Views: 9,106

Rating: 4.7318435 out of 5

Keywords: Communicating Sequential Processes (Programming Language), Computer Science (Field Of Study), Eric Shull, Atomic Object, Software (Industry), Programming Language (Software Genre), Programmer (Profession), Software GR

Id: 3gXWA6WEvOM

Length: 43min 21sec (2601 seconds)

Published: Fri Oct 02 2015