Understanding Core Clojure Functions Jonathan Graham

good morning everyone it's coming along today it's great being back in London I'm living in Chicago now but I I used to live here and so fairly recently so I was at a talk by and in Wampler a month or two ago and one of the things he said was really focused on the fundamentals because everything else around us will change and that's something that really resonated with me and my approach to everything I've done my career on really understanding what's happening so it's it's fine relying on some of the head and magic and we can get by with that and you know things may be fine today but at some point one day we'll get tripped up by it if we don't really understand what's going on so today we're going to take a look at some of the core closure functions by way of looking at writing your own implementations of them so see what we learn about them by writing them ourselves so just a couple of quick questions first who's written their own implementation of some core functions within their own favorite languages okay quite a few again those of you who haven't I want you to go and have a look at this at some point after the talk and see what you learn by actually going through and seeing how they actually work in you know whichever language you're working secondly who he writes much closure okay so that's just a few of you what we'll do is we'll we'll start nice and slowly so that we can build things up and and hopefully everyone can follow along and a lot of things we're talking about it's going to be equally applicable in in any language so Before we jump into the code we're going to take a lot from the view from 10,000 feet which is something like this and one of the reasons I've got this up here is a I took the leap into software development after taking the leap from a plane because I'm pretty scared of heights and I thought if I can jump myself from a plane I can probably switch careers as well anyone else skydive not all that many of you I know G to do that as well it's a whole lot of fun but for a moment imagine that you skydive you've done it regularly you know exactly what you're doing is year rushing at terminal velocity towards the ground 10,000 feet below you you're just feeling confident you're packing a parachute you know how it works you feel fully in control as you as you're falling down you know when you pull the chute it'll deploy any old nice in control take yourself to the ground so you've done this plenty songs you know exactly what's happening you've got complete confidence in the equipment but are you missing out on the ultimate thrill of a base jump so a base jump like a skydive but instead of from a plane it's from a fixed structure so either a building like in this case or from a from a natural a natural structure is a cliff or a mountain so you're gonna throw yourself off and you're gonna deploy a parachute in the same way but as you're taking this job well one are you missing out on this because you don't think the equipment you've gotten the skills that you got from skydiving will allow you to do the base jump or are you just going and jumping straight in assuming that everything works the same and you just taken that leap of faith so we'll come back to this a bit more in the end after we've actually jumped into the code as we're getting through this just have a think when you're writing your code and every line in the code you feel fully in control do you know what's happening so that's the question that we're asking today and we're going to take a look at some of the some of the core closure functions and we're going to start with reduce they say it's fundamental to a lot of their the closure sequences there's a lot on here we're going to break this one down but what reduce is going to do is go and say iterate through a collection and just reduce it down to a single volume all have a function a initial value in a collection and it can also work if we don't supply it with the initial value we're going to look at the case first where we do supply an initial value well and reduce is going to return the result of applying the function to vowel in the first item in the collection and then it's going to take that result and apply it to their to the next item in the collection etc etc and if the collection has no items in it we're simply going to return the bulb and the function is not going to be called so this is where we're going to start off and we're going to build it up in a test driven development way when I was doing this I use the speckled testing framework so within the within the namespace for their tests so I'll reduce spec namespace going to require in the spec or testing framework and also require in the namespace where we're actually going to write our reduce function and start up simple tests we should get a result of one when we pass into our reduced function the addition function an initial value of one and then just an empty collection so if we call our reduced function with plus one and empty collection we should result in one so all we need to do in order to get this test to pass we move to our namespace while we're writing our reduced function we just need to define our reduce function so my reduce as being a function that takes in has three parameters the function the initial value in the collection and in order to get this first test to pass all we have to do is return the value so exactly like the closure Docs documentation for reducer if the collection is empty we just need to return Val without without applying the function so first test run and that passes so next next obvious thing have a single item within the collection so if we stick with the addition function an initial value of one and this time we have the element one within our collection then this should result in C so we're just adding one to they see the contents of the collection so we just need to put a conditional in in this case so if the collection is empty then we're going to just return the vowel as before the initial value if not we can just apply the function to the vowel and the first item in the collection and that's all we need to do in order to get this first test this next test to pass so this will return to for us we can then build it up when we have more than one item in the collection so in this case got a vector with two and three n so if again we use the addition function we reduce this and we should get six so we can keep the function the same at the start so if it's empty we're just going to return file and we can iterate through by just recursively calling our my reduced function with the function so addition in this case and then Val is returned as applying the function to Val on the first item in the collection and the collection is passed back is the rest of the items in the collection so in that way we're just iterating through our our input collection applying the point function to the vowel and the first item in the collection and in that way we're juicing it through so this works we've got a we've got another test working and we can add more tests in in order to look at different functions different collections and different import values so the initial vowel so this works and we can build up a test suite for this so we can then look at the situation when we don't have an initial vowel so we just have our function in a collection and this works just by applying the function to the first two items in the collection so that will then give us the first result and then we apply the function to that result with the next item in the collection etc etc so test for this we can just call our reduce function stain with addition in this case no initial value when we have a collection a vector with just a single value in so this should return 1 in order to get this to pass we can add in a second arity so just with a function in the collection no initial value and what we need to do is call our reduce function where we now have Val as being the first item in the collection and we pass the rest of the collection as cold so we just take you out the first item of the collection to become the initial value this test passed because in this case we've just got one in the collection so one becomes our our valve here the rest is just the empty collection and we know when there's an empty collection we just return Val so we get one as the result and we can continue adding tests for this as well where we have more than the one item in the collection and we can we can build up our test sweep to make sure that these still pass and then there is the extra condition within reduce that if the collection contains no items then the function must also accept no arguments and the results for reduce is just just returning the evaluation of the function with no arguments so we can do this we can we can write some tests so got one here for addition so if you if you pass the addition function so reduce with an empty collection this should result in zero evaluating the addition function results in zero and do a similar for multiplication that returns one so in order to get this to work we just need to modify our our arity here so put in the condition if the collection is empty so if we've got an empty collection which is going to evaluate the function otherwise we're gonna call our reduced function where we've taken the first father with the collection out is the initial value and the rest is the rest of the collection so that works that works for those tests so the question for you I've got a function that seems to be working it's passing our test suite how many tests is enough in order to be confident that our function does what we want it to do what do you think what do you tease things a good number anyone else one for each branch how many branches okay three is easy I think at the point when I built this up I'd got a run about ten or twelve and it's like okay it's doing what I want but I know by a long stretch I've not looked at any way near all of the different closure collections and functions that we could put together so yeah it works I'm fairly confident but I'm not 100% sure so I decided to look at some property based tests and see whether this would help me out my confidence of the work we've done so in property based test we're making statements about the expected behavior of the code across across all of the domain so rather than just individual and specific tests and those statements we can vary a gate we can verify a gate some pseudo randomly generated inputs I'm not going to solve much about property based tests because Aaron Berger is going to cover that in the next talk but I wrote these four for each of the four functions and you can do that enclosure with closure tests dot check so Reed Draper wrote this a couple of years ago so it's a great framework for doing the property based testing in closure so this is what I ended up with just for the reduced function but a lot of this code was reusable for the rest of the functions so we can generate closure collections and hours having generators of general so we're going to generate one of these cloches collection types so as an example we can generate a vector so and any size vector and that vector will contain any generator of any closure values so we can have any closure type any closure collection type with any type of value that we can pass into our tests so we can do this for vectors lists etc and then we can run this as a property based test with as many tests as we likes in this case at thousand examples so for all of those we're going to have a generator of collections and a generator of any closure values and we can assert that our function that we've written and my reduced function behaves the same as the core reduced function so we can we can just pass our generator of collections and our generator of initial values to a function so I just wrote a simple function to pass into the reduce where we just we just from two values we just take the second one so we can reduce through the collection in that way and we've put in put in an example so if we just evaluate the function on its own it's going to return a result in this case tree so we've got a generic function that we can apply to our reduced function and we can use our generated collections and generated initial vectors button to this so in that way we can run as many tests as we like and show over all of those collection types that the function that we wrote behaves the same as the core function so I found this really useful use the CD they approach with the unit tests in order to build things up and then use a property based testing to complement that to give confidence that things are working as we thought they were so what do we learn from doing that how confident are we about switching from the sky dive to the base jump so a couple of things that stood out for me going through this reduce functions that require two arguments can be possible to reduce just with a single argument so there's an example if we have a simple function that takes two parameters X Y and we're just going to return the sum of them if we try to call this function just with a single argument it would fail but we can pass to reduce the function with just a single collection and this is going to work we don't need to pass the two arguments to it because it is just a collection it's just going to return the first item and it's it's not going to actually evaluate the function so this will work so we can pass functions that require two arguments just with the single arguments to reduce and this works so this maybe gives us more power than we initially thought we also know that we need care when we're using functions when we're passing functions to reduce that they will return a value if they're evaluated with no initial value in an empty collection so we looked at the addition and the multiplication function when we had an empty collection and that worked fine because you can evaluate addition and you can evaluate multiplication and closure you can't evaluate the minus function so this will fail so if you're writing your own functions there are going to be passed to reduce we need to make sure that we look at the case where you just evaluate the function on its own without any arguments if there's any risk that we're going to have those edge cases where we have no initial value and no items in the collection so that's a possibility need to think carefully about how our function works and have something in place for how it can be evaluated just on its own when we firm from reduced accounts sir-sir Valley fairly straightforward it's going to return the number of items in the collection and nil will also return zero so that's what count needs to do we can build this up into TD DEA's way as well I'm gonna start with three tests here so if we have an empty list it should return zero nil should return zero if we have a single item in a collection that should return one so we've got a few tests that we can then start building our function on so we can write our my count function takes in a collection if that collection is empty it will return zero and nil also returns zero for this else we get a return one so that's all we need to do in order to get that last test to pass so if we go to an empty collection zero else one we can then build this up where we have more than one elements in the collection and we can do this by recursively building up the function so if we have a recurse point here we can start that with the initial collection and a result of zero we can have our escape from the recursion when the collection is empty and at that point we're going to return the result so for the initial tests we start with an empty collection so we'll just return the result straight away which is zero otherwise we're going to recurse through with the rest of the collection and we're simply incrementing the result so this works and you can you can have collections with as many items as you want and we'll get the correct result it doesn't doesn't look all that pretty though but now we've got a passing test week we can look to back to this and what we're doing within this function is we're just iterating through the collection and we're reducing that down to a single value so that sounds very much like the reduce that we're just written so we can refactor it with a function that we just with the function that we just wrote I'm sorry the right way oh yeah so with our reduced function so our reduced function is going to take an initial value of zero so if there's nothing in the collection we just return zero and it's going to take the collection and the function that we're going to have has two arguments so the the results on the collection well we don't care about the collection because all withing is the increment in the result so we can just no more result have an underscore for they for the second for the second parameter because we don't we don't care what that is in terms of the body of their function so we can use our reduced function iterate through the collection and return the count and this worked again we can use our property based testing to give us more confidence that this function behaves the same as the core closure function so given the same collection generator that we use before we can just write our property based test where we are asserting that my can't function with our generator collections behaves the same gives the same results as they come let's move on to filter so filter will return us a lazy sequence and that sequence will contain the items in the collection where a predicate is returned true and that predicate must be free of side effects it will also return a transducer if there's no collection provided but for the talk today we're not going to cover that we're just going to cover the examples where we actually do pass a collection in so we can start off where there with a test where we're just looking at a empty collection and we have a function such as zero but it could be pretty much anything in this case and we expect that it's going to return a lazy sequence so the class of our result is going to be a lazy seek and it should have a count of zero because we started off with an empty collection we're filtered for something we're going to get an empty collection al so we've got a couple of assertions in there we can use our current function that we just wrote and we can get this to pass by writing our filter function takes in the predicate and the collection and we return a lazy C of the collection so the lazy seek is going to take in a body of expression so in this case of the collection and it's going to return a lazy sequence which is just going to be a body weight says when it is first called and then the result is going to be and then the result is going to be cached for any subsequent calls okay so let's look at building this up recursively when we add more elements into the into the collection so in this case we've got the numbers 0 through 9 and we're going to filter they're even ones so we expect the result our lazy sequence where the 0 4 6 and 18 so we can build this up recursively so we have a recursed point in here and I decided I'm first doing this to start the results so that our collection of filtered items so be a vector and that way we could use cons to add in to the back of the vector everything that is past the predicate so everything that's filtered goes into our vector and then we can just convert that to a lazy sequence at the end and that way I didn't have to worry about what the import collection type was and how how cons works I could just use the vector and I knew that I'd get things in the right order so if they when the input collection is empty we're just going to return the lazy seek of the result and until then we're going to recurse through with a with the rest of the input and if the predicate holds true for the first input so the one that we're looking up we're going to add that into our results vector so we're going to cons the results with our first input and if not we're just going to return the resultant so the vector that we're getting so this test passes and we can add more tests and these can pass but what's the problem with this so we're getting the right result but we're not actually doing it lazily so we convert it to a lazy seek at the end but we're not actually doing the filter lately so we're not getting any of the efficiency benefits of running the filter in that way and a reason for that is that cons behaves differently from cons so cons and closure depends on the collection type to know how to how to work with it so because of this it needs to evaluate immediately so it needs to realize the result immediately in order to know what to do with it cons is diff and though cons is always going to add into the front of the collection no matter what that collection type is and so that can be evaluated lazily so let's refactor this now using cons rather than cons so that we actually have our filter which is lazy so in order to do this we can run button start here we can say if the predicate is true on the first item of the collection what we're going to do is we're going to con so we're going to add their first item of the collection into the collection which contains all of the other items to come in that collection so we're just adding into the front of everything to come so everything to come is when we pass in back and so my filter the predicate and the rest of the collection so we're just building up recursively what's happening by adding into the front of everything that's to come if the predicate is false we're just going to recall my filter with a predicate and the rest of the collection so that's going to that's going to continue whilst we the seek on call returns true and this will return true when there's an item in the collection so as long as there's items in the collection we will continue recursing through the collection and then that that result is an pasta lady see so we'll end up with a lazy seek of our result and this time we've done it lazily because we're coming into the front rather than realizing each time with cons that we had before so what did we learn before taking this this plunge this jump there's a question how do we get a vector containing just the even numbers given this input so a vector the number 0 1 2 3 4 5 so may think just we can do the filter on even numbers on that collection and that's fine and this type we think tripped me up when I was first looking at closure because yes that gives the right numbers but it gives it as a lazy as a lazy seek and actually is a vector so if you're wanting to do other things with it still as a vector type we need to take that result into a vector so if you're getting the wrong type of type of data structure back then you thought the way that filter works returning later sequence could be could be a reason for that that was filter let's move on to map map again is going to return a lazy sequence and it's going to do that by applying the applying the results of the function to the first items and all the collections followed by applying the function to the second item then all of the collections etc going through and they map can take any number of collections again it's got an option where it doesn't take any collections and returns a transducer and we're we're not going to look at that today so we can build this up first of all just looking at single collection and we can write this and in an analogous way as we just did with filter so instead of having the predicate and we can just cons the results of applying the function to the first item in the collection to the result of applying the functions are there to the rest and we're going to carry on with this whilst there are items in the collection and then pass that's a lazy seek so this works we can also extend it to two collections so I think in the the arity where we have the function and two collections rather than just one and we can say whilst there are items in both of the collections so when C C 1 and C 2 are both true because we've mark we're going to carry on in sell one of them is empty so whilst there are items in them we're gonna cons the result of applying the function so the first item in the first collection and the second in the first item in the second collection to all of the other mut results to come so this works and we could carry on building this up so if we had three collections we could put in an errand C for that etc etc apart from accept limits actually can go on a long time so how about building this up recursively for more arguments going in for more collections so we can we can take a look at this so where we we pass in two collections and a collection of more collections and we can have a recurse point here where we we set our as this collection of the more arguments come here in the more collections coming in and we're going to we're going to carry on until there are no more arguments so we've just got the first two a which point we can return calling our function our my map function with a function and just the first two collections and until then we can just apply there my map the function over the first two collections and have the result of that being the first collection and then we iterate through the rest of the collections to come so we're just going to be applying my map to two at a time in going through so this can work and had tests that this passes with so it's fine it's just going to go through two by two go which is fine until we start looking at non commutative functions so such as this example where we're trying to apply vector across this this vector of vectors so this should result in taking the mapping the first items of each so ad in G so vector so we get 18 G up and then the second items be e and H so we end up with with our three vectors but what happens though when we use this function it fails because we're just applying to the first two so we get a vector ad be e CF and that's then apply to the rest accom so we end up with a nested vector so we have the first one rather than just being a vector ad G it's going to be a vector containing a vector ad and then G so it's not the result we want and again this comes down to the fact that we're we're not actually doing what we need to do we're not building this up lately so how can we do that and we're going to start just in English yeah what is it we want to do and what we want is to take all of our input collections and we can put them all in one big collection we can then reorder the sequence because what we want is a collection containing all of the first elements and then another collection containing all of the second elements next collection containing although the third elements etc and if we've got that reordered collections so all the first elements together all the second ordered elements together we can just map the result of applying the function across each of those reordered collections insert so rather than just going through the collection as we had it if we real to them we can just map each one insert so how do we do this so first part if we just pass in the function with one collection and then this collection of others we can make our single collection just by cons in the first collection into all of the others so we end up with a single sequence of all the collections if we pass this to some function called reordered which is going to realtor all of these so we have all the first items together all the second lord items together we can just apply our function across each of a sum term so we can map applying the function across each of those and that would give us the result so what does this real the function look like we want to do this whilst there are items in in every one of the collection because we know that map only goes on until one of the collections is exhausted so when everyone is sequel so when everyone is has got an item in what we want to do is add the results of applying my map to all of the the first items in the collection we want to add that to what happens when we reorder all of the rest so we got this real the function that is going to get all of our first items together etc and then we can just map the results applying the function across each of those in turn and because these two functions are mutually recursive we need to declare one of them at the top so that they so that they know about each other and can work through so this works and this then works for there for other functions including the commune commutative ones so that was map and the last one that we're going to look at is parallel map team-up so this is light map except for the function is applied in parallel so this is only of use for computationally intense functions so functions were there the time it takes to to do the computation is more than the expense of setting up the zatia talks about being semi lazy and we'll look at what that means is we build it up so I didn't want to have a a [Music] computationally intense function instead I just wrote one where we put a sleep in so we we sleep the thread for a thousand milliseconds so we've got this long-running job function which can take in any number of arguments we're gonna sleep for a thousand milliseconds and then we're going to apply a function to that argument so when I was first doing this I just applied the addition of ten on to across although they all of the collections when it started looking at all their collection types that can go in here and all their type of functions can make this just apply list to it and then it can deal with with any different type of function and collections that you throw at it so we've got a long-running job we can test that this does actually sleep as we want it to so just testing this job we can let s T so the start time be the system time at the start we call our long-running job in this case just where's the number one and then we stop the clock at the end and just adjust it to convert the time into seconds and so we can assert that call either long-running job should take longer than one second because we got the one second sleep what's the execution time and that works that's fine so that function works so what happens if we map so we're just using the the closure map function if we map that long-running job across a collection so in this case effects are one two three four so we can assert that this is going to take longer than a second and in fact we'd expect this should take longer than four second so a second for each element as it iterates through but this isn't actually the case this fails and it fails because that actually just takes a fraction of a second and again it comes down - the fact that map is lazy so we're not actually measuring the time it takes to execute the function we're just takin it we're just measuring the time it takes to form that new lazy C which doesn't take long so their test fails so in order to get this to work we need to make sure we evaluate that long-running function every time we call it so we can do this by I pull that into a separate function our testing time rather than having it in the test again we we're going to set the start time and then we're going to apply realize lazy C function to our map types in this case map or the function and the collection and then realize lazy see they realize lazy seek is going to take in those arguments to the map type of function and however many collections and it's going to set set a recursive loop so where salt is applying the applying map function with the collections and it's going to iterate through this and call the result so when there's a results of this calls it so it's actually going to to realize that lazy seek and then it will recurse through so we'll go through and make sure that we're actually running that function rather than just the lazy seek so that gets the map to work and it does indeed take greater than four seconds so now we can actually start looking at building up our our p map so if we pass in the same collection so long-running map we expect that this will take less than 1.1 seconds it's an example so should take each of these we'll take a second if they're run sequentially if we run them in parallel it should just take a second plus the bit of overhead time so less than 1.1 seconds so how do we build this up so we can imagine that we that we can just use the closure futures so this enables us to run to execute things in parallel so we can apply the future of calling F calling the function on each item in the collection in turn and map through that so this will give us our collection of futures those futures can then be run across the available threads and we can dereference them by calling DRS so we can take our collection of futures and then we can apply D ref to it map that to give us our collection of results so this looks like it may work but it doesn't this fails and it fails because all we're doing the first point one we're setting up the futures as we're setting them up in a lazy sequence but we're not actually we're not actually generating them so we're never starting off those futures and we're only ever calling them when we call what the rep on them so as we're iterating through we we start our futures at the same time as we then call them so in this way we end up just taking as much time as we did with map we generate the future and then we're blocked until we get the result through so how do we move this in order so that it works what we need to generate all of the futures first before we try to do ref them and we can do this using the trick that actually trips us up earlier when we were using cons because cons isn't lazy so this means it's going to evaluate the results as it goes through so now we can have up apply our function to the collection still but as we do that we can cons that into a vector so because we're playing cons we're going to generate that future as we go so we can use our function we're going to iterate through our collection and return a thing of value and this value being a vector containing all of the generated futures at the results so now at the start would generate all of our futures they can all run in parallel and then we can just map that collection of futures to the collection of actual results by dereferencing them with DRF so now these are actually running in parallel and our test works and we can extend that test so or the collection sites and we can extend so more than one collection in exactly the same way as we did with map so now this behaves the same as they call pea map does and we use that trick of conjuring to realize the futures so that we can have our semi lazy team-up implementation just as the same with all of the other functions we can use property based tests to confirm that our function are given the same results behaving the same as their core functions so given this how do we feel about taking that base jump so when you take a skydive you've got a long way to go so you've got enough time in order to get up to terminal velocity we're more stable when we're at terminal velocity so we can have a more stable parachute deployment so things are fine that's not necessarily the case with a base jump you jumping at lower altitudes you don't have enough time to get to terminal velocity which means you're less stable so you have to make sure that your input into the jump is very steady and prepared and you can deploy carefully without going back into the building or hitting other people so you need to really know your equipment your equipment needs to be correct for the job for deploying at lower speeds and for slowing you down quicker and you need to make sure your important to the job is well executed because if you don't start steady you're not going to be able to study up in time in order to deploy so it's the same in the code when we jump into things we need to make sure we understand the important done the function how it works so that we don't get tripped up and and take that jump into using the function when it doesn't actually work as we want it so allows you to go and have a look in whichever language if you work in implementing your own versions of some of the functions really understand how it all works and use that to make sure that you understand every line of code is you're moving forward with your work thank you [Applause]

from infoq