Uncategorized

hello is is that sound okay guru yeah awesome hi hi everyone my name’s auspi marin and this talk is called functional pearls and it this title may be familiar to some of you if you’ve come to other pearl events before and I’m grandly naming it the functional pearls world tour which started off in Pisa at the Italian word pearl workshop and been first places in UK in Lisbon Turin and essentially I’ve spoken about various things that interest me while learning about functional programming from languages like Haskell and then try and see what can i implement in Perl so I’ve done monads and lazy lists and iterators and all kinds of fun stuff and so it always depends on what particularly interested in me at the moment so this is all new material and what I’m talking about at the moment is about immutable data so basically data structures that can’t change and so if you’ve been to Matt’s talk about DevOps or various other talks you’ll know that everything in programming is about data and data is all about change if you can’t change anything what’s the point of doing anything you know things that don’t change are mathematics and things that do change is what we do as you know computer engineers people writing internet sites and car manufacturing websites and all kinds of other stuff so it seems like a fairly big problem and it is and it isn’t and I’m gonna set this up as an epic struggle between mutable data and immutable data and we’re going to have a look at how you do things normally in Perl and in a typical programming language and how you might do things using just pure immutable data so if you’ve got a variable really simple thing you’ve got a variable dollar X and you’ve set it to 10 if you want to change that later you can just change it dollar X is now 20 from then on and of course you can’t do that this is really cool key difference with pure functional programming and and you average pearl you don’t change the value of X once it’s ten that’s your loft it’s ten what you can do is make a new variable called X two and that can have whatever value you want so you’re not prevented from doing anything there so in that example those two things are basically functionally equivalent so that’s really simple does it apply to more complicated data so here’s a really simple example you’ll know from the K in our book if you’ve ever studied C changing from centigrade to Fahrenheit and the way you might do it in a mutable language is you take a variable in and you do stuff to it you multiply that by nine you divide it by five you add 32 and then you return the new result and of course immutable data we can’t do that so we can take a variable in dollar C for centigrade we can multiply nine to it getting a new variable we can divide five new variable again and finally we return the value which is para height and all of these are new variables so again we can still do some fairly complicated processing and we haven’t lost any and the ability by using pure data so that’s quite promising so far and obviously you know both of those examples were fairly were fairly badly written you can actually remove a lot of these intermediate variables by writing it as an expression just like you would do in a mathematical equation so you may be wondering why do I care about the fact that data doesn’t change and well that’s actually a good question so what we can see though is that it would be really really bad thing if constants like the number one changed because suddenly all of your programs would be completely wrong so that’s a really extreme case of of not wanting data to change but what about variables why would I not want a variable to change so one of the problems is you can get issues with action at a distance if you have a constant variable here called one you expect it to stay one if something changes that later on then suddenly all the output from your other functions is gonna be a bit a bit skew if so obvious solution let’s use constants cuz we have them built into Perl so we use constant one and now that doesn’t change and that’s you know that’s sort of getting there but the problem is that you don’t really just have simple data that you never change and never process you’ve you’ve got hundreds of different variables all of

which like stacked Matroska dolls are based on the data that was contained kind of inside so you’re always processing data then you want to keep intermediate stages so for example if you’ve got a list of users you might want to have also a list of users with the dresses and then that’s processing that original list adding value to it and both of those things are equally valid and both of those things you don’t want some other bit of code somewhere else to change so if we think can I always pretend that immutable data is kind of important at the moment for the purpose of this talk then then we definitely want to make sure that it stays immutable so what we’re really looking for is a way of having variables which are still variables in that they can be set while you’re running the program and they can build on other data but once they’re set they’re totally read-only and luckily Pearl’s got modules to do that so you’ve got a model called read-only there’s also Const fast which is superior in some ways that allows you to set a variable there might in and then my out which is based on that and once those things have been set there totally read-only and again they can’t be changed so that’s pretty cool and so what happens if we try to subvert that by having a complex data structure there well not very complex hash of foo and a sub key a bar and we tried to change that now we’re going to subvert this this read only variable and you know it turns out that whoever wrote that was that Leon actually who’s here and has already thought of that so hurrah so just before we go on something a little bit more interesting because this is all very kind of just setting the scene for mutable and immutable data and here’s one consequence of the fact that immutable data you can’t change things you have got a whole load of intermediate variables variables there and so that means that you’ve you’ve had to allocate more memory for these variables and you need to have really good garbage collection otherwise otherwise you’re going to have a whole load of data in memory that you don’t need anymore so there’s kind of there’s actually some things about wanting to do a functional programming that changed the way that your compilers got to work if you’re going to do it in the real world so okay so that was all very simple with integers and really simple stuff so let’s look at actually programming with objects and see is it worth having the idea of purely functional objects so here’s a typical package now that we’re using modern Perl moose or Moo typed data the this package here has got a name field which is a string and it’ll be validated to make sure that you give it a string it’s got a height which is a number so you know this is this is all very nice and we can create a creature here here’s Donald Duck and his 50 centimeters tall he’s a duck but I got to thinking okay I have said 50 centimeters tall but do I really know how tall Donald Duck is and for the purpose of this kind of torque at yep see Europe it’s really important to do your research so apparently he’s two feet tall so I’ve got a problem here I’m taking centimeters and it’s two feet tall I had to do more research so there we go sixty point nine six centimeters tall so simple now we just changed Donald’s height to sixty point nine six any problems with that and so were there’s two problems one we’re talking about immutable data so we shouldn’t be trying to change the subject once there and the second is Moo’s already defined it as a read-only attributes so it’s not going to work so how do we work around this well its owns out that in in the land of Moose there’s a module called mu sex attribute change clone which allows us to get a copy of a variable but with with a particular attribute set to a different value so here we’ve got a donald with height sixty nine to six we now actually have two versions of donald duck one of them is fifty centimeters tall one of them sixty point nine six centimeters tall so what do we do with these two Donald Duck’s they’re gonna you know run around fight each other in it chaos could ensue so the idea again we talked about garbage collection once we’re no longer interested in the first duck we can just forget about it and and and just keep the new copy or unwanted old version of Donald Duck so does this seem a little bit round the houses what’s the what’s the point of keeping a copy and then forgetting about it and one really good

reason for this is that you suddenly get the value of one do for free you could keep every state of your objects as a separate reference and go back to it whenever you want and so if that’s Donald Duck that’s maybe not so interesting what if your object is a financial transaction or a the contents of a website or you know some other complicated object that you may want to be able to revert changes to so this stuff can be really powerful and and save you from getting into all kinds of trouble because you accidentally change data from something that you didn’t mean to and then you don’t know how to revert it or you forget to revert it properly so okay so I said that was possible using a moose module but in the example i gave i was using move which is a slightly simplified lighter version of moose and it doesn’t have attribute change clone so here’s a very quick module that will basically do the same thing you can give it some new data and it will create you a new version of the object but with that data add it to it and that’s a really bad way of doing it and move so don’t do that at home kids I mentioned that on hash moose and hogs written a modicum mu X clone with which we’ll make sure it takes care of all the lovely mu details like triggers and validations and so on that’s probably better to use but basically fundamentally the concept is that very simple code there so what we do now is we said we want to Donald Duck but we want to Donald Duck whose height is sixty point nine six instead of what it was before so so that’s great if you just did him Donald Duck but it gets really complicated when we factor in his Uncle Scrooge so because objects don’t just have simple simple values they’ve got references to other objects so these creatures can have an uncle and young curly is an instance of creatures this is another example of type standard validation which is really neat so in the example of this Donald Duck he’s got an uncle whose name is Scrooge but we didn’t check how tall Scrooge was dammit now we’ve got to update Scrooge and this is where it starts to get a little bit fun so if we were doing if we were just doing normal Perl objects we’d say Donald’s uncle’s height is 52 job done and if we do that with the mutable data we can do Donald uncle but height is 52 but what do we get at the end of that we’ve got a copy of the uncle so we’ve now got a copy of a Scrooge who’s the right height but he’s not linked in any way to Donald so this is starting to get a little bit more tricky just because we wanted to have immutable data so what we really wanted was this we actually wanted a new copy of Donald Duck who’s exactly the same but his uncle is a Scrooge duck who’s exactly the same as that one but he’s 52 centimeters tall so if you listening care you heard me say but twice oh yes at the end of that week and then forget about the original pair of objects and suddenly we’ve we’ve updated the things okay so what we really want to do is to write that which is kind of disgusting but you know okay so we’re going to be doing a lot of copying of objects so now did you know that Donald’s got nephews can you name all three of Donald Duck’s nephews Oh in German please thick thick and pluck so in English they’re called Huey Dewey and Louie I’m sure they’ve got different names in everything please tweet me afterwards with the with the names in your local language and I will retweet so we’ve got Huey whose uncle is called Donald whose uncle again is called Scrooge so if we wanted to update screwed from Huey we want Huey but his uncle is the same as Huey’s uncle but his uncle is the same as Huey’s uncle’s uncle but he has a height of 52 and at this point that’s that’s really disgusting and it makes you think well you know functional programming nice and theory nice at university nice of phd’s but you know I’ve got work to do and so that’s not good and it gets even more complicated if you look at the family tree I’ve really done my research for this so um and actually you can tell here my data modeling wasn’t very good because it turns out Scrooge has got two uncles but that’s for another talk implementing that is left as an exercise to thee to the viewer so what are we going to do about this really complex horrible code and the answer does not involve squirrels

but it does involve zips so we’re going to call a bit of code called a zipper so we’re going to start with Hughie and we’re going to zip Hughie and amazingly because I’m an idiot I didn’t spot that I’d actually made a pun with Gerard who a who was the French computer scientist who invented the zipper and so this is obviously in my subconscious being much whittier than I am and so this guy invented the date – called a zipper and a zipper basically points – to an object and allows you to do to kind of navigate it and make changes in place as conveniently as if you were doing standard lootable code so once we’ve done Huey zip we’ve basically got the zipper and all it’s doing is it’s pointing to Huey we’ve got exactly the same data structure we had before so this is all really straightforward now from Huey we want to go up the tree or down the tree into into the uncle and at this point this zipper is now pointing to Donald but we’ve also keeping a breadcrumb trail which reminds us that the uncle relationship came from Huey and again from there we need to go up again so finally we’re focused on Scrooge was where he wanted to be and we’ve got a breadcrumb trail leading us back to Donald and then Huey so now we can actually do an in-place edit yep okay so she’s asking what okay so the zipper is that structure there in that pink box and so the the zippers pointing at one of those so so you’re not zipping over two things at the same time you’re basically zipping over structure that started with Huey but you’re pointing at Scrooge so we’ve traveled we’ve prover cease from Huey via Uncle via Uncle again and we’re now pointing at Scrooge we’re not trying to change Donald we’re trying to change Scrooge because Donald you see there has already got a height sixty point nine six and Scrooge doesn’t so that’s why we’ve gone up the tree two times uh sorry so we’re trying to modify Scrooge and we’re trying to give him a height because so far he doesn’t have one so at this point we consent Scrooge’s height to Oh fifty-two okay they’re all 51 whatever and what we have now is a new version of Scrooge whose height is 51 centimeters and we could go back up to Donald and up again to Huey and we still have an old version of Scrooge there that nothing’s interested in anymore he’s basically he’s still there because he’s part of that other structure that we don’t want to ever change because we can’t because it’s immutable but we have a new Scrooge so that’s all very well but how do we then get that news fruit into the right place so we need to go back up the zipper so that we’re pointing at not that old Donald because he’s a he’s a useless old dog we want to be point to get this Donald here who’s got the right uncle but that old tree is still there because it’s immutable so the next step we go back up again and at this point we’re pointing at a new Hughie whose point to get a new Donald who’s pointing at a new Scrooge and oh we’re not pointing at that old tree anymore at all we’ve completely left that behind that’s like we’ve said the skin of a snake and we can get rid of that or we can keep it if we want to undo or you know whatever reason we might want to come back to that but we’ve now got exactly what we wanted which is a Hughie with the right height whose uncle is a Donald with the right height whose uncle is screwed with the right height so this is what we did we we went up the tree we set the the height and we went down the tree sorry we set the height we went back up again and then we went back from the zipper to the object so we’ve now got these two copies of of these relationships one of which has the right height one of which is the old one and at this point again we can forget about that and let garbage collection get rid of it so we can also make things a little bit easier because

whenever you unzip obviously you want to go back up to the top of the tree so we can relied that and assume that unzip we’ll go back to the top and we could also make it a little bit nicer by by having a dive command that’ll allow you to go into multiple relationships at the same time and we can even you know why bother having unzip at the end of it we could put it in a subroutine and then just call unzip magically at the end of that subroutine breath and in fact we can also make the zipper know about the relationships and it can now have an uncle methods magically placed onto it which does traverse onto uncle so suddenly these two things are looking really quite similar so basically our uncle uncle height 51 uncle uncle height 50 one with a set command in fact we could even change that the same way and those would then be identical but apparently I forgot to do that so yeah so the idea here is that we suddenly have a fairly convenient way of using complicated immutable data structures with objects with mu that gives us loads of advantages like knowing that our data isn’t going to change under us because we made the bug we made a mistake and it allows us to undo back to previous States so I think that’s quite exciting and we’ve got time for the bonus material question okay what do I do when one of those data structures has other references the the answer would be don’t do that and it would be possible to create a a mu extension that prevents you from having read write references or something like that at the end of the day the difference between Perl and Haskell is that in Perl you can do anything you want even if it’s going to hurt you so it requires a little bit of discipline if you use it the way it’s intended to you won’t shoot yourself in the foot that’s probably the it’s impossible to do better in Perl and I hopefully somebody will run away and and prove me wrong okay so um the original title for this talk was when is a hash not a hash so here’s a dictionary entry we’ve got a a key and we’ve got a definition to it and hash tables in Perl which is the way that we model dictionaries of keys and values are usually done as as as this kind of structure which is a hash table so you get your key and you apply a hashing function and then you look it up in basically an array and so you can have all kinds of hashing functions you can have really good hashing functions you can have cryptographically secure ones or you could have really stupid ones like taking the length of a keyword for example and no programming language would ever be so stupid as to do that PHP so here’s so here’s some examples using some perl keywords so say and die all three letters long so they’re hashed under three go to four letters long search has done before so if you wanted to look up go to in this hash it would go well how long’s go to the hashing function for okay look it up there Oh have I found it yes I have hurrah and it’ll give you back your data if it what if it if you looked up print for example it would look up under five and it would find there’s actually a list so check well is it print is it blessed okay yeah I found it in one of those or I didn’t so this is a really good data structure and obviously you know we use Perl we use hash tables all the time and they’re really useful so if we wanted to have an immutable hash table things are a little bit less good because if you want to add a new keyword to unshifted seven letters long and how do you how do you add that while keeping the old one well you could make a copy of it and then you end up with lots of very expensive copies of data because there’s no there’s no sharing of the data here and going back to the world of functional programming it turns out that one of the really classic data structures which is a tree can do this really well so here’s a binary tree

where we can come down go okay this now then alphabetically rather than by by the length of the of the of the functions so we’re looking for go-to we come down with we we say okay yeah this this node is already go-to we’re sorted if we wanted to look for bless we look at go-to it’s not that so let’s go to the left of it because it’s alphabetically lower we’re down to die still not that let’s try to the left of that and we find bless so with a tree if we added an element there we can do that we’ve got a we’ve got a space here and we can just stick state this thing here now from go-to to say two unshift you’ve got a relationship a little bit like from Huey to Donald – Scrooge where you had to copy those bits of information so if we were to make a new version of that particular tree we could do so but we’d have to change we’ve got this new one shift we need a new version of say and a new version of go-to but actually died bless and print can all stay exactly the same so we can add a new bit of information while keeping a whole load of stuff in this tree exactly the same so in terms of memory usage that’s actually much more efficient than than a typical hash table if you want to be able to have multiple versions of these so that’s kind of cool we’ve added on shift there and we can do the same thing at the eval there and we only have to change eval died and go to and that’s coarse so we can actually yeah so these are basically chains and this is quite efficient in a way that this tree isn’t so if we wanted to look for unshift well it’s not blessed so let’s look a little bit to the right of it well it’s not die let’s look to the right and eventually we come down to one shift so that’s effectively the same as using a linked list we have to go down through every element until we find the one that we want so we wanted something that was flatter than what we had before and again if we wanted to add something into this kind of not very well balanced tree then yeah we’d have to change all the elements above it so in that case just three but if we change done shifts suddenly we’ve got to change the whole thing and again it’s not very efficient so what we want is a tree that when we add stuff keeps its balancing so that we can oh we only have to go down the same amount of distance at any time and again in the land of functional programming there are ways of doing this and one of the most famous ones is a red-black tree and I’m not gonna go hugely into the detail on that largely because it confuses the hell out of me but what basically happens is you try to add something in a way that would become unbalanced and magic things happen and the tree gets rotated around to make sure that you only ever have two children from a particular node and that things don’t get too deep on any one side so basically does this sort of nice balancing act for you sure what that’s about so basically you color the different nodes red and black and you’ve got first cases where you’ve got to look at okay let’s look at the parent and both their children let’s look at the parent and its left child and it’s right grandchild and so on it’s you know it’s fairly complicated it’s quite well documented in this book by Okazaki for purely functional data structures which I kind of like but is also really matter see and I’ve read the first two chapters and then it scared me after that and also he tells you in lots of detail how to create a red black balance tree that allows you to insert data into it and retrieve data from it but not to delete from it because that gets a bit hard and it’s left as an exercise and I’ve tried to do the deletion and it confused the hell out of me I’ve tried several times and was too stupid so and luckily there’s a much simpler tree that only has two cases to look at and this is called the AAA tree not that AAA and basically it has two operations that do called skew and split and they do verse different rotation transformations and they put the tree into the right shape that you can be really efficient in updating it and the interesting thing is that because those rotations are actually they return a copy of the data we can actually use this but a feature again so we can you know return a copy of a node but the

left is pointing at the left of the previous right version and so on and that code there actually ends up looking much nicer than alternative phrasings of it yeah and also in fact well you see that but and but kind of syntax there and you think well hey actually could we use a zipper to make this simpler and it turns out we can so we can we can zip we can set the level we can go to the left set the the next thing and then go back up and actually that ends up being quite narrative it gives you a sort of a feeling of I’m going into the state of structure I’m doing some stuff and then I’m diving you know back up to the surface again so that’s been quite useful and there’s things like okay setting the level to be the level plus one if we were doing hashes we just go you know dollar a plus plus so you know they’re hash value plus plus and we can do that again we can add to the zipper an increment function start be quite nice so here’s some code from the from the deletion and you can see I’ve actually been a little bit cheeky because I’ve created that right value and actually I’m meaning go right and similarly skew and splits are calling that skew function and split function so basically you’re adding a lot of syntactic sugar but you’re using quite mathematical concept behind it so so they’re fairly robust which is quite nice so I suggested that this could be quite efficient because the tree you start from the top and you go down to the to the bottom but it’s nicely balanced but if you’re changing more than one bit of information at the same time then that’s actually a really bad example but if you change bless and evil at the same time you never even need to go back up to the top of the tree because you could just go to die and then come come down again so you can actually have a zipper that knows about the structure of the tree that it’s navigating and can be more efficient than just updating by going back to the top of the tree changing an item going back to the top changing another item and this stuff turns out to be really hard to calculate again if you’re not a PhD and Okazaki talks about it a lot and you’re basically using kind of almost financial metaphors about borrowing against future efforts by by doing stuff but it turns out that it has basically quite good performance which is great so I don’t know if your heads hurt as much as mine did writing that probably more but if you want to play with that code is currently on github some of the some of the syntactic sugar isn’t that it added yet but I will be working on that and forks and pull requests very very welcome so thank you very much and I think I have time for some questions ten minutes for questions good to wait for and so the main point about having the the immutable data and not modifying it because other people are seeing it the time moment employs quite a cute trick I think in that it’s notionally immutable hmm and so one of the mutation operators really return you a new value but they rely on the Perl trickery that you can get the reference count of an object and you can find out if it’s a temporary and things like that so if you attempt to mutate something thirty’s only a temporary with a ref count one then you know you’ve got the only copy of it so actually it just cheats and just mutates it directly so it sort of really you get the best of both kinds of things where you can do these really efficient in place mutations if you know it’s safe because nobody could have seen it that’s using the time mechanism no no that’s a whole load of sort of slightly crazy and excess code but it’s inter alia magical time moment okay which is a way of representing times time moment yes okay I would look into that I haven’t come across that yeah it’s corny one you didn’t mention anything about data

structure with cycles in them how do you handle that if at all so zippers work quite interestingly with data cycles and they have some fun features you can end up one interesting thing about about zippers is if you traverse up to Scrooge and they come back up again making no changes at all there is a risk that you could end up with an entirely different copy of the list than you had before same with them if you’re trying to do the equivalent of chew chewing tape for example in this way you can end up with entirely different data structures representing exactly the same thing and I think cycles can often lead into that kind of situation so simply things would work but you can get into trouble with things like memory usage and checking equality and things like that also you might change some data but then you go back to a previous version of that cycle which hasn’t been changed so I think it’s a research area actually well thank you very much

You Want To Have Your Favorite Car?

We have a big list of modern & classic cars in both used and new categories.