Sunday, March 20, 2016

Generic Programming and POP with Swift – The Law of Useful Return

In my first post on Generic Programming I talked about the iterative approach to improving algorithms.  In this post I would like to discuss another concept from the From Mathematics to Generic Programming book that I am currently reading. This concept is called The Law of Useful Return.

The Law of Useful Return says:

If you have already done the work to get some useful result, don’t throw it away.  Return it to the caller because they may be able to use it.

What do we mean by this law.  Well the easy way to explain it is to look at an example.  In the From Mathematics to Generic Programming book, they explain this law based on a mathematical equation however, most developers that I know do not get that excited about complex mathematical equations therefore I am going to take a non-mathematical approach to explaining this.

Lets say that we were creating a pump that is connected to the Internet for real time monitoring (think IoT).  This pump could be used to pump different types of liquids and would be able to return the temperature of the liquid as it is being pumped.  In our application, that monitors the pump, we could then retrieve the temperature and send out an alert if it is outside of the acceptable range for the particular liquid that is being pumped.  Our function to monitor the temperature may look something like this:

func isTemperatureWithinRange() -> Bool {
    //Get liquid temperature
    var temp = getLiquidTemp()
   
    //Check if temp is within acceptable range
    if temp < MIN_TEMP || tem > MAX_TEMP {
        return false
    }
    return true
}

This function would work well and if the temperature was outside the acceptable range it would return false triggering an alert.  The problem that could arise from this is eventually we will want to display the actual temperature of the liquid being pumped, therefore someone may add another function that would simply retrieve the temperature of the liquid and return it.  This function may look something like this:

func getTemperature() -> Double {
    //Get liquid temperature
    return getLiquidTemp()
     }

Now in order to retrieve the temperature of the liquid and to also check if it is within the acceptable range we would need to call the getLiquidTemp() function twice.  Since this function retrieves the temperature from a remote device, making two separate calls like this is definitely not optimal.  What we could have done to avoid this problem was to return the temperature with the Boolean value that indicates if the temperature was within the acceptable range.  It would be very easy to do since we are already retrieving the temperature as part of the check.  The function that returns both values could look something like this:

func getTemperature() -> (acceptable:Bool, temperature: Double) {
    //Get liquid temperature
    var temp = getLiquidTemp()
   
    //Check if temp is within acceptable range
    if temp < MIN_TEMP || tem > MAX_TEMP {
        return (acceptable:false, temperature: temp)
    }
    return (acceptable:true, temperature: temp)
}

Be careful not to follow this law to closely because we only want to return data that is useful within our application.  When we create functions like this we really need to ask ourselves not only what information do we currently need but also what information may be useful.  In our example above, returning the temperature, since we already retrieved it, could definitely prove useful even if it is not needed with our current requirements.  Writing our API correctly (generically) the first time will save us from having to change the interface for our APIs in the future.  This means a lot less refactoring of our code.

To me, one of the ideas behind the Law of Useful Return is to avoid making our APIs so granular that we end up performing the same functions multiple times.  To illustrate this idea another way lets look at a second example.  Lets say that we have a NSDate object and we need to retrieve the month from it.  We could very easily design our API like this:

func getMonth(date: NSDate) -> Int {
    let components = NSCalendar.currentCalendar().components(.Month, fromDate: date)
    return components.month
}

This works great for our present need however what happens if in the future we also need to retrieve the day of the month.  We could write a second function to retrieve the day of the month however we would then need to make two function calls if we needed both the day of the month and month itself.  A better way to design our API is to think ahead and realize that if we are retrieving the month from the NSDate object maybe the day of the month and year would be useful.  We would then create a function that returns the month, day and year like this:

func getDate(date: NSDate) -> (month: Int, day: Int, year: Int) {
    let components = NSCalendar.currentCalendar().components([NSCalendarUnit.Month, NSCalendarUnit.Day, NSCalendarUnit.Year], fromDate: date)
    return (month: components.month, day: components.day, year: components.year)
}

By designing our API to return the month, day and year rather than just the month our function becomes much more generic and useful not just for our present needs but also for our future needs.

When we create APIs that only meet our present requirements we end up having to do a lot of extra code refactoring in the future when we have to change those API to meet our future needs.  When we are designing our APIs we should always remember to think beyond our present needs and think about how we can make our APIs generic enough to also meet our future needs.

There are going to (hopefully) be a number of posts in the Generic Programming and POP with Swift series therefore I made a separate post that contains links to all of the articles in this series.  The post is located here:  http://masteringswift.blogspot.com/2016/03/generic-programming-and-protocol.html


Saturday, March 19, 2016

Generic Programming and POP with Swift – Iterative approach to Algorithms

After I released my Protocol OrientedProgramming with Swift book, I had an e-mail conversation with Dave Abrahams about what exactly is protocol oriented programming.  If you are not familiar with who Dave Abrahams is, take a look at this video from the 2015 WWDC When the conversation started I did not realize the person I was talking to was the person that introduced Protocol Oriented Programming to the world even though I probably watched the video at least fifteen times while I was writing my book.  It is a very good presentation and a must see for anyone interested in Protocol Oriented Programming.

One of the things that Dave recommended to me was to focus on Generic Programming.  Well in my mind I knew what generic programming was.  It was about using Generics, right?  Wrong.  I could tell that Dave was getting frustrated with me and he ended up recommending that I check out the From Mathematicsto Generic Programming book.  I was very interested in what Dave was trying to explain so I started reading the book. 

I will say that the book is very interesting and I have enjoyed reading it so far.  I have not finished it yet but I did want to start sharing some of my initial thoughts.  First off, as the title would indicate, the book is not for those intimidated by mathematics.  I graduated from college and have not taken a course on mathematics since before my favorite young baseball player, Mookie Betts,  was born (I’m showing my age here) so I really had to shake some of those math cobwebs out of my head but it is worth it.   If you are intimidated by mathematics, you can read a more general overview here:  generic-programming.org.  The author Douglas Gregor has not updated the site since 2013 but it does appear to have some good information from what I have seen so far.

I do not want to spend the time writing a review of the book, instead, over the next few posts, I want to discuss some of the ideas behind Generic programming as I understand them.  I am learning what generic programming is as I write these posts so please leave comments with suggestions or any corrections if I get something wrong.

This book does start off by covering a lot of basic concepts that all advanced developers show know but sometimes we forget or ignore during our day to day work especially with the deadlines that we are always on.  Sometimes we need to be reminded of these concepts to make sure we are creating the best applications that we can.  This post will cover one of these concepts.

The second chapter of this book looks at the iterative approach to programming where we should be constantly improving our code.  At the end of the chapter the authors says that “No one writes good code the first time' it takes many iterations to find the most efficient or general way to do something.  No programmer should have a single pass mindset.  While most experience programmers realize this, a lot of times we are pressured with deadlines to just get the coding done.  This creates a lot of technical debt for our company and we should really take the time to make sure we find the most efficient way to do something.

To illustrate this iterative approach the authors’ shows how the algorithm for multiplication improved over time starting with how the ancient Egyptians did multiplication.  To me, an example that is presented in chapter 7 also does an excellent job showing this concept.  This example also demonstrates the concept that it is sometimes better to do more work rather than less.  The example that I am talking about shows how we would compute the nth Fibonacci number.  Since this blog is about programming in Swift, I would like to walk through this iterative process with examples in Swift. 

The Fibonacci sequence is a series of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89….

Where each number in the sequence is the sum of the previous two numbers in the sequence.  For example, 2+3 = 5 therefore 5 is the next number in the sequence after 3.  Also 3+5 = 8 therefore 8 is the next number in the sequence after 5.

Any entry-level developer could easily write a function to calculate the nth Fibonacci number using recursion like this:

func fibonacciRecursive(num: Int) -> Int {
    if num == 0 { return 0}
    if num == 1 { return 1}
   
    return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2)
}

This seems to work very well and we could call the function like this:

fibonacciRecursive(5)

Everything is good, right?  Wrong.  Lets try to make this call:

let start = NSDate()
fibonacciRecursive(20)
let end = NSDate()
let timeInterval: Double = end.timeIntervalSinceDate(start)

On my MacBook Pro this call takes almost 4 seconds.  This would indicate that we might have a problem.  Let's see what happens with this call:

let start = NSDate()
fibonacciRecursive(30)
let end = NSDate()
let timeInterval: Double = end.timeIntervalSinceDate(start)

This takes 492 seconds WOW.  If you try to find the 33rd Fibonacci number you might as well take a quick nap because it took 2295 seconds on my MacBook Pro.  Yes I would say that we have a problem here. To solve this problem we need to figure out why we have it. 

The best way to figure out what is wrong with an algorithm like this is to manually walk though it.  Let's go ahead and do this as if we were figuring out the 5th Fibonacci number. The fifth Fibonacci number would be the sum of the forth and third Fibonacci numbers and we would write the formula like this:  F5 = F4+F3.  With this format we would figure out the fifth Fibonacci number like this

     F5 = (F4)                            + (F3)
        = (F3 + F2)                       + (F2 + F1)
        = ((F2 + F1) + (F1 + F0))         + ((F1 + F0) + F1)
        = (((F1 + F0) + F1) + ( F1 + F0)) + ((F1 + F0) + F1)

As we can see, just to calculate the fifth Fibonacci number this code performs seven additions and also calculates F1 + F0 three times.  So how can we eliminate this duplicated work?  One way we could do this is to do our calculations going up the chain, rather than down and to pass the Fibonacci pair into the function.

func fibonacciRecursive2(count: Int, fPair: (Int, Int) = (0,1)) -> Int {
     let newCount = count - 1
     if newCount == 0 { return fPair.1 }
     let newFPair = (fPair.1, fPair.0 + fPair.1)
     return fibonacciRecursive2(newCount, fPair: newFPair)
}

This new function allows us to calculate the fifth Fibonacci number with five additions.  While there may not be that noticeable of a time distance when we are calculating the lower Fibonacci numbers once we get to the higher ones (like 30) there are some drastic time differences.  I am talking about the difference between 492 seconds and 0.0223 seconds.

Is this the best algorithm for us to calculate a Fibonacci number?  Probably not.  It does take a certain amount of time to call functions therefore using a recursive function does add additional time.  Let's see how we would take the recursion out but still keep the logic.

func fibonacciIterative(num: Int) -> Int {
     if num == 0 { return 0 }
     var values = (0,1)
     for _ in 1..<num {

          values = (values.1, values.0 + values.1)
     }
     return values.1
}


Now I think we have a great algorithm to compute a Fibonacci number.  To calculate the 70th Fibonacci number with the fibonacciRecursive2() function it takes 0.0472 seconds.  With the fibonacciIterative() function it takes 0.0235 seconds.

This example showed how we could improve an algorithm by taking an iterative approach where we improved the algorithm’s perform each time we rewrote the function.  On thing to keep in mind is the iterative approach can be used not only with mathematical algorithms as we just showed but also in our day-to-day development.  We should always be thinking about how we can improve our code to not only make it faster but also safer and more generic (we will be discussing this a lot more in future posts).  This post also showed that by doing more work in the function itself, rather than using a recursive function we ended up creating an algorithm that is faster and more efficent.  Another bonus is it really shows off how valuable Tuples can be when used correctly.

Over the next few posts I will write more about what I am reading.  Some of the posts will be like this one where we are reminded about some basic concepts like taking an iterative approach to our code while others will be about the concepts of Generic Programming. 

I made a separate post that contains links to all of the articles in this series.  The post is located here: http://masteringswift.blogspot.com/2016/03/generic-programming-and-protocol.html



Generic Programming and Protocol Oriented Programming with Swift

There will (hopefully) be a number of posts in the Generic Programming and Protocol Oriented Programming with Swift series.  This page will list the post with links to them.

1.  Iterative approach to Algorithms

In this post we will look at the iterative approach to programming where we should be constantly looking to improve our code.  Keep in mind that no one writes good code the first time' it takes many iterations to find the most efficient or general way to do something.  No programmer should have a single pass mindset.


2.  The Law of Useful Return

In this post I would like to look at the The Law of Useful Return.  The Law of Useful Return says:  If you have already done the work to get some useful result, don’t throw it away.  Return it to the caller because they may be able to use it.