Transforming Programming - Dave Thomas

it's kind of bad when you know people are embarrassed to introduce me okay so I got to start off by saying that this is a work in progress I think there is something really deep and fundamental in here and yet I can't quite put my finger on it so giving the talk is actually a way of helping me try to clarify my thinking so I appreciate you all being guinea pigs and I would really appreciate your feedback on it um okay supposed to applaud at the end of the talk okay now this actually is a thank you to the people here because I owe an awful lot of the pleasure in my life to the work that people you know at this conference have done you know the Erlang core a whole bunch of people working on same nerves which is my current joy and even Larry wall has given me a certain couple nights ago fantastic amount of pleasure and I've also changed to the future of computing for us all so I would say thank you and I want to think about just the people I talked about right these are people have changed history and you know we're all kind of like old kind of great beauty kind of people but you know what these people kind of know what they're talking about and what tends to happen over time if these old people get new people come along you might want to think about this as Erlang and elixir and the problem for the Erlang folks is elixir currently has the ring so what I want to do actually is to is to go back and look and honest some of that experience because ice elixir folks we tend to go around things we go really cool language alright and ignore a whole bunch of the really important stuff that we knew in the past and I think this new stuff actually comes forward and applies to what we should be doing tomorrow just to prove that I am also one of those old farts here is a picture from I think 71 or 72 of be my friend Toby Bailey the caption says programming analog computer actually it was turned off at the time you were just looking like so let's talk about some old stuff right this is all going to lead up to these ideas I've got about how is your program today but I just want to get some history and some background into it so state machines we all know what a state machine is right it's a way of pausing a stream of events we start with an initial state an event comes along and depending on that state that we're in that invent makes us go to a different state potentially and that just repeats over and over and over again until we're done a classic example is like one of these push-button locks so let's imagine that the code for this lock was 1 3 1 this would be one of those cool I hate programming challenges for job interviews I don't think anyone should ever do them I've never done one but this is actually a cool one to set as a programming challenge because my guess is about 80% of the people would actually get it wrong because you can actually unlock it obviously by giving it 131 you can also unlock it by giving it eight one seven one three one and you can unlock it by giving it three one three one the trick one though is that one because if you're just looking for a one followed by a three followed by one then you're going to bolt out on the second one go back and it's just not going to work most people get that wrong but doing this at the state machine is really easy except it's not okay first of all I apologize this is Ruby code but who cares this is how many people would code a state machine so what it is is basically we have an instance variable here state and then we have a function that accepts the next event and depending on what state were in we look at the event and say ah in that case I want to go to the next state and change my current state and we just do that for each of the possible state it's code like this that makes people think they need to go out and find a library to do state machines right I have no idea why people do that as you'll see in a minute you don't actually need it but this is what people code I prefer to do it like this a state machine is simply a hash and associative array a dictionary and in this case I'm using the state whoa I'm using the state as we sorry that the key is the state and then for each state I have another hash which says if I get a 1 then transition to that state if I get a 1 here transition to that state now and my entire event handler thing is I just basically go from the transition from the current state indexed by the key and if it doesn't match then I'm just going to go back to my default State so that's kind of easier so let's take it a step further let's add in some external real world stuff because one thing state machines don't talk about is actually interacting with the real world so let's make it do that here I have added what some people might call a model alright the outside world and in this case it's contraindicated in the lock and or you use a pass of the color it turns light on so I've invented my little state machine language here to add the ability to put not just the next state but also the next state and a function to invoke as I transition to that state and its really pretty lightweight the only thing that happens is event in the last waiting for a while and I get the one now I am unlocked and I will set the lead degree otherwise my default transition which me Sallee means I've always go back to the start state is set the lead back to red and by doing that you always go red if you get it wrong so let's take that one step further same code but split up a bit more so now I have my model which is the thing that my state machine is manipulating I have my set of rules which is what the state machine actually does then I have a generic finite state machine it knows nothing about locks and leads or anything all it knows is you pass it a set of rules and it does the business so what actually is a transition well at the simplest a transition is just an input in the state that produces a new state and along the way it's going to execute an action potentially you might ask yourself what is the program exactly the same thing if you went to like you know computer science 101 at some point a professor sit there and Drew's a picture on a board right input Aero processor output or something like that and that's what we're looking at here so a state machine is really a whole bunch of little small nested programs this is where we're after getting to in the end it's you know pretty straightforward online order processing you can see how that works in this case our state is the session where if we're talking to Twitter or something so my assertion is that a program is a deeply nested set of individual transitions and each one takes an input in the state and produces a new state and possibly an updated input and you'll see why I say that in a minute so this is the kind of the only diagram you need to program right if your those people that loves doing you know UML and class diagrams on what kind of stuff right well here is your new your new Nirvana right and that's all it is and the cool thing about it is you'll notice the output and input are the same so you can change them as much as you want they compose it's not wonderful so you can look at something like this this is a deliberately ugly example just to show it can be done right so here we're calculating something to do with an order which sort of terminating or finalizing an order for him to go through it and do all sorts of things to it and you'll see what we're doing is we're gradually go through and we are taking the inputs and using it to produce suitors of outputs now here is the thing that's really important this looks like I'm describing the flow through a program but I'm not there is nothing about time in that flow all I am doing is saying that if I have this as my current state then I can execute that if I don't yet have this then I got to hang around for a little bit so even though this shows you the dependencies of State in reality each of these could be a totally isolated freerunning process that's just waiting for as the correct set of inputs to come along for it to be able to do its thing there is no time element in this kind of programming and that's the key because one of the things that we try to do when we're coding what Thomas's rule of good design right is a good design is easier to change that a bad design right as far as I'm concerned that's the only rule of program design and one of the ways we make our designs better is by reducing coupling and one of the things that we do with functional programming is we have a really major bit of decoupling in that we decouple our state from our functions and although that's kind of scary if you come from an oil background it turns out to be remarkably liberating and I think that's one of the main reasons that functional programs are easier to change but we still have coupling in our functional program and the coupling is this kind of insidious temporal thing that I'm going to do this then that than the other now outside its particular process obviously we don't have that on the beam but inside each chunk of code inside each function we still say a then B then C then D and that is coupling that we don't need so how do we code this well too many people hand code it we could code it as a state machine I think we have the opportunity to do something better than I think we can code these transitions using pattern matching I always used to use Fibonacci numbers as my examples of pattern matching and then some mathematician said Oh Lucas numbers are way cooler right and the only difference is that rather than having one one it's one three right so so this is pattern matching calculating the Lucas numbers and okay everybody seen this every knows this code will do this kind of stuff right the cool thing here obviously is we have no conditional code nor do we have any sequencing that says you have to do this in this and this it just happens that way because things only trigger when their preconditions are met here's our lock expressed using pattern matching so we have a group of functions here none of which has a very real parameter they're all fixed parameters but it's exactly the same thing and the nice thing about this is because they're all functions I can return the next state through along the way I can also have side effects like setting the light to green I code a lot like that in my everyday coding right and it was kind of looking at code like that that led me to think about some other things and it also came about because increasingly over the last couple of years I don't know about you but this word reduce and reducers and stuff has become like you know the new object orientation or something it's a really big buzzword right everyone's talking about reductions and reducers and you can't have a JavaScript framework nowadays unless you've got reducers in there right so a reducer is that right it's a function that takes an input in this state and produces the new state that's all a reducer is why is it called a reducer because it is the function it's the signature of the function that you pass to reduce and it was going to be called a fold Eller but no one could pronounce fold Eller so they called it reducer instead so in this chunk of code which is our lock FSM here is our entire state machine alright this is why you don't have to go and buy a library to do state machines it's called reduce all right enum dot reduce initial state is you initialize the lock and then we just feed it through lot except until it finishes nothing else to do and there are our reducers they take a input and a current state and produce a new state so our reducers implement transition that look like that and I'm about to extend them to look like that so why should we code with reducers well firstly it tends to lead to incredibly small little self-contained functions functions that are really easy to understand it gets rid of this shared state between lines of code right my my personal view is a variable is a smell and if you can get rid of your variables then you've actually improved your code I find it a lot easier to read it's incredibly easier to test because all you're doing is testing one-line functions by feeding a particular state and input and making sure you get a particular output so easy in fact I don't bother to test them anymore and they are easier to reuse so okay say hello to Dobbin Dobbin is a horse that we're about to beat to death so the sum of an empty list is zero alright here's our reducer it doesn't actually have any input otherwise the sum of the head of the list blah blah blah you will know this so here we have list something written using exactly that pattern right it all just works and the pattern matching is going to do the state transitions to get to the end where we finish and it's all wonderful why am i showing this well I'm showing this because when you explain this in a book or something you end up showing a bit of code that looks something like this yeah you're trying to exit you're trying to examine how it works or explain how it works so you kind of expand it out like this so you could write our code using the new universal preadly notation as simply as this you'll have an input put and the state becomes the empty input and the new value okay so here's where the whole speaking company I didn't draw it it's not me I didn't draw it okay so I now know how to please you guys I'm gonna go more dead animals all right okay so there's something really obvious but interesting about this here is our state and in general terms here is our time first thing to notice is it doesn't have to be in that order it can be in any order you want but it happens to ask you in that order but the really cool thing is if you add up the input and add up and add it to the output you always get the same number 16 well duh of course you do but that idea leads us the idea of invariance now if you are old and gray like me then when you went to college you learnt about program proving you know back before they decided they couldn't actually do it and you learned about how to program using invariants and invariant was basically a statement of what is true at this particular point all right you say this is the sorry regardless of the values in the state this relationship holds between them and if you can use that and a whole lot of time you can actually prove that an if statement sometimes does what you want it to do right totally waste of time long term however thinking about invariance leads to really nice bits of design because the more you can think about invariant the tighter you can make your loops the easier you can know it's going to work or not work whatever so my point is that a correctly implemented reducer is going to transform state while maintaining the invariant right it's obviously the case with some but I think what we're looking at here is a wider picture so this is my most pretentious slide ever the most important thing in programming truth is conserved I'm sorry they're not dead actually they are they're stuffed there's what you couldn't get all three to sit in the same place like that otherwise give you that took me forever all right so the law of conservation of truth unless your name is Kellyanne truth is neither created nor destroyed it merely changes its representation yeah you're never ever going to be able to change truth that's kind of definition of it yeah but you can certainly change the way you represent it and that is all that programming is all of programming nothing apart from maintaining truth from beginning to end so some can serve that truth it can transforms our state but it conserves the truth all right okay you say big deal anyone can write a sum why do we care we care for the same reason we care about any programming practice and that is a good programming practice informs you it doesn't just let you get away with something it actually tells you this is good this is bad it helps you write better code for any definition is better you want apart from probably Jose who would say it's not quality but it's going to be it this idea leads to some really interesting code and so I started playing around with this and used a framework called diet which is not a framework sorry I used a really crappy little library called diet that I enjoy playing with it doesn't stand for anything unless you want it to but it's called diet because it's all about reductions so come back to our some of the list I promise I think this is a last time I sum a list you can you give me a quick time check to learn how much is plenty I will carry on what his check so here's a our set of truths if you like to sending a list we know that we have in our whole universe here we have a list and we have a result we know that at all times with some of the elements in the list plus the result is a constant I'll worship and we know that we finish when the list is empty okay now I'll show you that in code let me show it to you in diet so diet is simply some macros in elixir that you express that in kinda like a more compact form so in my module I use diet transformations which is what you guys are and I have a series of reductions so here I'm saying okay so I'm tending to use the first element of a tuple is like a verb but let's just you know it stops you getting it to some ugly kind of like circular things so here I'm saying to Sun a list well the fact was we have to have a list and a result and here we don't have a result all we have is a list so the first thing we have to do is to add our result in right so we're going to sum into our list what value does a result have well we know that the sum of the list such a result have to be the same as the sum of the list so it has to be zero no choice next the sum of the elements of the list plus the result is constant so hearing at a Sun into a list that has a head of and tail into the result and I do the obvious thing and then finally if I going into an AC list then there's my result again not dramatically new so how does this actually execute well I have a thing called diet dr. pepper and you pass it one of those descriptions so in this case it was in the module list some so I pass that module in and I pass in an initial state which in this case they don't care about and then I just run my stepper and I pass it the initial event so the initial event in this case is some 1 2 3 and how does that then work well the stepper basically looks at this as a big pool of challenges and it goes into this pool and says ok which one can I match and the first limit matches it's going to execute so in this case it's going to match the sum list and it's going to produce a new fad which is some into list 0 it hasn't finished yet because now it's going to take that new one and go back into this list and look for another one that matches or look for any one that matches so in that case this one doesn't match this one does so it's going to apply this one we're going to sum into we're going to do something new etc etc eventually it's going to get to this guy down here some into the empty list with the result returns the result but now the result doesn't match anything so the stepper goes not my problem and passes it back to you and that's why when you run that you get the results come back out again let's make that slightly more Oh actually know what let's actually yeah let's do it alright live code time okay so with any luck at all I actually have stepper aliased here yep all right so I am going to produce a new stepper and I can't remember what I told it this lump it was example that with some and no state okay ignore that that's just implementation right so now I'm going to use the result and the state a new state by running stepper don't run on that stepper and I'm going to pass it some oh let's be different three two one all right and honestly I don't care about the state at the end of this all I care about is the result so I'm just going to put the are there so it just displays the result and I got something wrong yay there's my result okay but no no no no no wait all right I'm English so I'm bound by contract to say but wait there's more all right because this stepper is not just executing code if I was to say diet dot debug and ask it to debug that particular step stepper it'll say okay I'm now looking at example dot list some and one of the interesting things I can do is say hey show me a trace of what actually happened and here it's showing me the set of things that actually went through to produce that result yeah and if I wanted to I could dig into any one of those and it shows me you know the details of what actually happened I can also well let me show you that later on okay so let me take another example let me get out of there slightly more complicated example this line I use all the time just because it's just that bit more complicated than summing and that is you're given a list of things and you want to run lengths encoded so if you have a run of same values in the input list you want to replace it with the value and account in a tuple and the reason I like this is it's another one of those programming challenges where you give it to people and typically they'll get it wrong first time they get most of it right but there's always boundary conditions that throw people off the most common one that confuses people is what happens if the run ends at the end of the list and have to handle that as a special case or something yeah if you're writing lots of ifs and loops in this kind of stuff so instead let's just ask what is true well help just like everything else we're going to change our input into our output and we know that if we really take our input as it currently stands and our output as it currently stands and concatenate them it will always be the same yeah and then when the input becomes empty the output will be the run length encoding list and there's a few other things we know we know that if our list starts with a duplicated value we're going to replace it with that value and a to and if our list this is the wrong way around I just noticed it's our list started with one of those duplication things and then has an a after it we're going to bump the count and move onto the next one so here is our runner length encoding written using that reduction style so the same thing we have to do in the previous one we have to create ourselves the output pyeong we're not passed it so we're going to say RLE of a list is our only other list plus an empty list ignore that one here we have the case where the first two elements the lists are the same so what we're going to do is going to replace those four two elements with the a and a two if we have one of those tuples followed by the same value a that we just bumped the count otherwise we copy the input to the output and the cool thing about this is you want to talk about if you write like this is so easy to reason about the code we guarantee that this thing is going to terminate because on every single match we're removing something from the input we have no choice but to terminate and it works it does from top to bottom just like Erlang analyst to do and yes it does yeah so the order of execution does not matter the order in which it matches does if that makes sense right so it doesn't actually execute each one of these things in turn and we're not giving it a season to execute in but we are also saying this as a higher priority than that so again we can do oh I don't have a early that's why is the example the early yes okay and then I can do our comer s equals step adult run s and I'll give it some input 1 2 2 2 3 4 4 5 5 5 6 7 8 why not okay and I'm just interested in the result Oh interesting I didn't give it the command orally I just passed the list so it went sure I don't recognize that have it back okay so I'm going to put our Huntress this is a feature not a bug I thought it was a bug but last time I actually gave this a very very different variation this talk in Chicago two nights ago and someone says oh that's really cool because that way you can code and when you miss things it will report it back to you yeah exactly right ah all right what am I doing wrong oh it's in code in code sorry about that I knew it was going to well yeah nil desperandum all right so and again though right this is a little complex example so let's use our debugger again and that's a look at the trace this time whoa all right let's shrink that down a bit do it again and that didn't help all right sorry about that take my word for it it's a lot of stuff but this shows you every single step it took along the way which means that if you have an arrow if you have a bug which of course you're not going to have this kind of way doing things but if you did have a bug it's going to be very easy to see why you didn't pick up that extra two or whatever it might be because you can just see it in each one of the transitions so let's really push the boat out these are all kind of like vaguely academic things but let's look for the real world right and what's more important in the real world than a game of hangman so let's write a step of version of the game of hangman let me see if I may actually have this on the slide yes so this is the game of hangman expressed as a set of reductions like the door lock it actually uses an external state and in this case the state is the module that holds things like oh it's not as module the structure the whole thing like the current word to guess the number of guesses that you've taken all that kind of stuff right it's all stored in our state and in our reductions the state is such an important thing that I just make it available for free so I'm here I call model name game and that means in all of our reductions I can use game and that's just going to refer to the model and the model at the top here i tells diet that I'm using hangman model as my model and I'm going to call it hm because I can't type hangman model all the time and otherwise and it just runs through here and again the order it actually executes in the order it matches in is palpable but the older excuse in who knows but because it starts off by making to make a move first thing it does is ask the model how I already use this letter right if I have already used this letter it could just respond to already tried otherwise it's going to set our new state to record move and pass in the move and record move is going to go oh I need to update the model so it explicitly says update the model and I do that because they hate that I do this because I think it's important to show people when you're updating the model and when you're not because you look at this a little to things update the model than all of this right and that's a big thing so you don't to read the whole thing and it'll be on the slides when I get around to publishing them but the idea is this actually will execute a game of hangman and it's really cool so let stress you go try and run that hangman okay now if you if you want to keep the suspense avert your eyes what I type the word we're going to get I do home version that uses a dictionary and I just hate losing in front of a crowd of people so all right so there's our there's our word so let's start running it R comma s equals step or dot run s comment what do I call it make move and I'm not cheating I'll just start with an A yeah and again I'm don't care about the new state I just want to keep look at the result hey it was a good guess right not exactly the best user interface but we can build on that so let's try something else let's go a B alright that's a strategy you start at a and you go to yin-yang go guess clearly it's the best strategy we can use so let's keep going while runner on a roll here let's try see damn all right we have a bad gift and I don't like that right because I really want to be perfect I mean who doesn't so let's just go back into our debugger here Oh doc debug s all right and here is the list of states that we went through to get to what happened the numbering system here is 100 n dot n this means this is the first time I called it and then inside that it actually run a ran eight separate transition then here it ran eight again here ran it again okay so and you can see that at the end of my transition here one point eight I got a good guess yay you'll also notice that this'll dot changes to an arrow on some of them that indicates the states changed on those particular ones so in fact if I get a bug that's something - the state change I could do something like let's have a look at two point three and it shows me that what happened was I've added a B to the list of guest things yes it highlights the changes that make sense it goes along now I got this problem that I made a mistake and I don't like making mistakes so you know what I can do I can clone my history up to a certain point so let me close my history let me just remove this - plug up to two point eight all right you'll notice now that has changed from hangman zero to hangman one that means that I'm on my second copy of hangman my clone right and now I can start making moves if I could remember how you do that I know second that that uh our that's right so let's our make move so I had well I have that a B let's do em good guess let's how was our history now ha I now have just three states and it went straight from B to M I'm perfect right and we can finish that off so our unless you just do that oh T W game one all right this is actually really pretty cool the fact that I can go back and Buzz inspect history but also fork it and then move forward is great imagine for example you have a server where the state is kind of expensive to set up then what you could do is run to that states that at once and then fork and now you've got everybody else shares that initial setup yeah if you need auditability not a problem and it's obvious implementation issues like potentially this is an infinitely long list and your small details like that but that's that's tractable you know there are many ways to compression this down first thing I can do is replace each of the individual sub steps with a compressed version once it gets to a certain size and I'll I can do more and more and more compression and get it down pretty pretty tight accept the fact that the further back you go in history the more granular it becomes so my point is that programming is transformations and that's what we need to think about nested composable transformations and the rule for programming is number one work out what should be true number two make it true and we call that establishing the initial conditions if you're a rails programmer you call it validates prison salt or something like that right it's what you do to get your data into a state where you can trust it and then your only job is to keep it true as you make lots of transformations and if you do that your programs will be correct so this is the slide I would use if this is a PhD presentation programming is reducing input to output in the presence of state yeah this is the slide I would use if I was jane austen programming is truth but the slide I would use if I am me is programming should be fun thank Oh God of course it is I'm confident exactly yes because everyone can't give me a history thing that I can do like that not in nug the point I'm trying to make is and what I showed the great no I am that's why I showed your Gandalf haven't you worked that out yet no Gandalf right what a night yeah right yeah was it two years see no the thing I'm trying to get to here is that all this stuff none of this stuff is new right I mean you know the Elm folk like to think oh we we've invented weed oceans and stuff no they didn't I mean that was 1958 probably or something stupid like that all right no none of us is new and when I've said that what I'm doing is honoring the past what I'm saying is I'm going back to the things yes erlang can do and prologue could do before it yeah but what I'm trying to do is to put it into a context where now we can look at this in a bigger picture and start using it as a tool right so it's not just a question of saying yeah Erlang could do this Erlang could do all of this any of this assembler could do any of this in all of this right it's really dispersion of how you think about it how does the language encourage you to think about things and what I'm thinking is or what I believe is that if I make it easier to think about things in terms of reducers people are more likely to use them and if that's how they do things then I think the quality of program will increase so I'm not in any way saying that this is brand new absolutely no you're doing a test every time you have an equals that has a fixed value on both sides I love you anyway Joe anybody else know cuz you're I could go on all night like this we forget Oh [Laughter] kind of why particularly so are you saying you want to see a javascript interpreter written using this style or do you want to see this style written in JavaScript I don't see why I couldn't a part of the fact that I'm probably likely to die before I'd finish or kill myself what was it but actually it does it does lend itself very well to that form of problem because when you think about it house transforms are fundamentally what we're doing right so we're pausing we're matching a pattern and then we're doing something with that pattern so you could actually see many of that kind of problem so interestingly I wrote a markdown Towser it's kind of like a sod off as a pet project it's like one of my challenges when I learn a new language is to write a mouth campfire in it and I wrote it in elixir and it was one of the first large elixir programs I wrote and it's not written using that notation because I didn't have it but it's actually written using pretty much that style so everything is done as a match followed by a new state and it works a treat and it really does work well but JavaScript may be kind leave that as an exercise to the reader thank you [Applause]

Channel: Erlang Solutions

Views: 12,610

Rating: 4.9293284 out of 5

Keywords:

Id: A76hM3MpEKo

Length: 46min 46sec (2806 seconds)

Published: Sat Mar 25 2017