Use functional programming concepts to increase quality when re-factoring

Sometimes when you want to implement a new feature to a system the developer needs to figure out if this is new functionality, or a modification of the existing. How is this going to fit in, or is it new on its own? Chances are you have parts of the functionality there already but it be a mess. There are functions being called from other components and doing mostly the same thing, but in a slightly different way. This is a great opportunity to refactor this behaviour to one abstract type so you can add some automated tests, fix the design issue (without fixing everything) and leaving it in a better place than you found it.

By using some function programming basics your code can read and perform better than when you found it. By recognizing these patterns and the value they bring, you will find yourself recognizing this situation in many places and it will become easier to have smaller refactors that don’t slow you down on your current estimate, but give you the peace of mind that you will save some time down the road.

This will cover (IMHO) the basics of functional programming that benefit any codebase; iterative functions, OOP classes and any ball of mud you run into

Immutability

Immutable parameters don't change the value internally. use this value to create a new one
this is referred to as ‘side effects’

This is essential when doing concurrent programming. The data you put into that thread can’t have a hard reference (or any ref) to the global value.

By default, try to keep inputs immutable. Be efficient at copying the data you need and returning a new set (or reference to that set). You can enforce this in Java with the final keyword. In python, you can use tuples to pass arguments into functions (instead of lists)

Functional Composition

When you have many functions in a file, the callee has to know all of the details of the internals to be able to create the behaviour desired by combining the function calls in the correct sequence.

This really violates basic encapsulation and leaving this will cause some messy coupling between components and pieces of code will call specific functions. Easier to provide an interface that has specific behaviour. There is a parallel here with the Facade pattern in OOP, provide a simplified interface for the behaviour of the component and then refactor all the reference to that functionality to the new interface. This is a great re-factoring strategy, to add some functional design to your classes. Use abstract data types or interfaces to enforce the behaviour of the internals.

Higher-order functions

Using higher order functions in any language that you are using is really important. Why? because you end up making these functions anyway. So, you can create one of your own making with many loops and callbacks, or just use the built-in versions that come with many languages; or are available as a library to extend the languages base functionality.

The most common are using map, reduce, and filter

• Map - apply a function to all elements in the list. The list won’t change, but he values in the like will
• Filter - remove elements from the list that don’t satisfy a certain condition
• Reduce - apply a function to each element, and combine all results into one value

Immutability in these functions. 

When using map, the elements in the list will change, so these are mutable elements. For Filter and Reduce, you are reading the elements and producing a new output. With these immutable values, you could use partition the list, and use concurrency to run filter and reduce in parallel.

Monoid

This has an obscure name; but its really some very fundamental algebraic rules for designing functional behaviour. Monoids have properties and its a good idea to follow these as a guidelines when creating the functions that are used/applied in the higher order functions like map, reduce and filter. 

Closure - types inputs is type output. When you pass in integers, you have integers returned.

Identity - depending on operation, the base value for type

• for addition: 0  (1 + 0  = 1)
• multiplication: is 1  (1 * 5 = 5)
• concatenation is empty: "this" + "" = "this"

Associative

• a + b = b + a
• a * b = b * a

Recursion vs Iteration

Recursion can improve readability, but it comes at a cost of execution. you can exhaust the resources of your stack pretty easily when dealing with large datasets. Use iteration when possible for more predictable linear nature of the execution

Conclusion

By using some concepts from functional programming and being able to see these patterns emerge when refactoring code; the quality and consistency of the refactored result will increase in quality. This is from using tried and true concepts that, like many patterns, will just emerge from your work and add consistency so your teammates will be able to more easily read and maintain the code.

What math is needed for software development?

We sometimes see the articles or comments that you don't need math to be a good programmer.
The thing is, software development has its roots in computer science, and cs is applied mathematics. So, it is true that you don't need math to do software development, it just makes it a lot easier if you do. How good do you want your work to be?

In the more broad spectrum of software development there is so much to do. Planning, designing, reviewing, etc. Do they have the design skills to make it look good? Do you have the empathy skills to know what the customer wanted in the first place? These don't seem related to math at all; but in pulling them all together to create a solution you would benefit from the problem solving skills that math provides

What actual math is needed for programming?

Computer Science is Applied Mathematics, so to be a computer scientist you would need a strong mathematical foundation. For making software, you don't have to be a full-blown computer scientist, but first you would have to use and understand the logic and data involved and how these two things work together to create your program.

One cannot do computer science well without being a good programmer, nor can one understand the underpinnings of computer science without a strong background in mathematics. Education must make students fluent speakers of mathematics and programming, and to expose them to both functional and imperative language paradigms so that they can effectively learn computer science.

Early programming courses and discrete mathematics will articulate the strong ties between mathematics and programming. Then the coursework should bridge the gap between the mathematical perspective and the implementation of an algorithm as a sequence of instructions through an imperative language.

I have thought of programming as largely a combination of set theory and predicate logic. Category theory may be a better way of going about the first part, as it is really set theory when combined with functions. I'm not sure if that replaces logic as much as it extends it. I'm really seeing more light in functional approach as the way to glue the concepts together.

How to get there

The first year programming course should not be viewed as computer science in it's entirety. It is a formal language and propositional logic course, which is a foundation aspect to CS, but doesn't represent the entire profession.

• set theory
• predicate logic
• combinatorics
• probability
• number theory
• algorithms
• algebra
• graph theory

• Understand sets and how regular algorithms apply to them
• Functions ,Transcendental functions, including trigonometric functions, logarithmic and exponential. Algebraic vectors. Combinatory logic is the root of lambda calculus 
• Computability and Turing style computer science is a bit at odds with formalism. It's a different philosophy of the nature of mathematics

Logic - first order logic http://en.wikipedia.org/wiki/First-order_theory theory of computation second order logic and computational complexity np complete also need to understand relations: unary, binary, ternary, n-ary important for iterations over sets with algorithms, check out STL style of applying functions. relational data

Numerical methods for solving simultaneous linear equations, roots of equations, eigenvalues and eigenvectors, numerical differentiation and integration, interpolation, solution of ordinary and partial differential equations, and curve fitting.

Wrap it up

Math is the language of technology and the computer science is applied mathematics. The more you know about these foundations allows you to make better software.

Algorithms intro: implementing a math proof

What's a nice way of showing a visual example to better understand how a math proof can be implemented as an algorithm in code? Here we are showing an example of implementing an algorithm, comparing iterative and recursive algorithms for solving a method; and validating the results with profiling.

In problem solving, a great methodology to use is: Understand, Plan, Execute and Review.
We will use a bit of geometry to understand the problem, and then plan how to solve it; then we will implement code to execute that plan and review how things worked out.

Understand

The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b. (or x and y).

We can use some geometry to visualize this, check out this video of it in action. From that, it looks like a matter of:

1. Fill with squares along the shortest side of the rectangle
2. For the remaining rectangle, fill with squares again, until smallest square is found.

Plan

Lets write down the steps in more detail:

• fill rectangle with squares
• find shortest sid
• divide long side by square side, get remainder
• if remainder is 0, smallest square is found
• for remainder, fill rectangle with squares

Execute

To model the visualization, lets make a Rectangle object, and use that with a function. Lets start with what we know, the Rectangle:

class Rectangle(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __str__(self):
        return "%s, %s" % (self.x, self.y)

Now lets plan how to fill the rectangle just like the visualization happens, the next rectangle is filled, and so on until the end. This style of implementation is recursive.

• fill_rectangle_with_squares(2,4)
• fill_rectangle_with_squares(2,2)
• 2 is smallest square

We keep calling the fill_rectangle_with_squares function, until the x and y sides are equal. This is the stopping condition.

def fill_rectangle_with_squares(rectangle):
    print("Fill " + str(rectangle))
    # check the sides, if they aren't equal make a new rectangle with the remaining
    if rectangle.x == rectangle.y:
        print('smallest square found %s ' % str(rectangle))
        return rectangle.x
    elif rectangle.x > rectangle.y:
        return fill_rectangle_with_squares(Rectangle(rectangle.x - rectangle.y, rectangle.y))
    elif rectangle.y > rectangle.x:
        return fill_rectangle_with_squares(Rectangle(rectangle.x, rectangle.y - rectangle.x))

Now we call the function with an assert to test the result

To test to see if this function returns what we want, we use assert to check. We want to assert that a 2 by 4 rectangle is anything other than 2. Lets test some others as well

assert fill_rectangle_with_squares(Rectangle(2,2)) == 2
assert fill_rectangle_with_squares(Rectangle(140,68)) == 4

assert fill_rectangle_with_squares(Rectangle(24,12)) == 12

Review

Lets keep reviewing our solution with other sizes, like: Rectangle(143,62) and Rectangle(270,192). These work fine, but what happens when larger values are involved?

Rectangle(2400000223334219423423424234240,1945303434230234234242322)

When this would fail would vary from machine to machine, but on my home laptop I get a:

RuntimeError: maximum recursion depth exceeded


This means the call stack limit is reached, and this limit is bound by the design of the python language itself. Some languages like LISP don't have this limitation, it's just ends up using what resources it has. The limit is imposed because the amount of callable memory is a finite space on the machine. If you are using a large amount of recursion depth, and not getting the results you need then there is way to only bound by time, and the running of the CPU.

How can we make this better? Lets implement the algorithm using iteration.

def fill_rectangle_with_squares_iterative(x,y):
    rectangle = Rectangle(x,y)
    print('fill %s with squares ' % str(rectangle))
    found = False
    while not found:
        found = rectangle.x == rectangle.y
        if rectangle.x > rectangle.y:
            rectangle.x = rectangle.x - rectangle.y
        elif rectangle.y > rectangle.x:
            rectangle.y = rectangle.y - rectangle.x
    print('smallest square found %s ' % str(rectangle))

So far, so good, and the tests work with fill_rectangle_with_squares_iterative(24000000,19453003)

Can the iterative version take the massive difficult rectangle that blew the call stack with the recursive version?

fill_rectangle_with_squares_iterative(2400000223334219423423424234240,1945303434230234234242322)

It does, but takes a couple seconds.

Optimize

I know it took a couple seconds because the console lets me know how long any code execution takes. What's really happening here? To find out more I need to profile the code which will will in the second part of this post.

Before we do though, lets take a crack at optimizing the code even farther.

When you look at the iterative function, see that we are just modifying the Rectangle objects x and y values. We can just keep track of the x and y and not bother making the Rectangle object at all. We could maybe make one object and pass it instead of making a new object for each call, but lets go the step further. It's only 2 variables that makes it concise.

We used the Rectangle as a way to visualize the problem, but nice terse notation is possible and ends up being very clear, so lets boil down the description to the original:

Given two (natural) numbers not prime to one another, to find their greatest common measure.
(The Elements: Book VII: Proposition 2)

def greatest_common_divisor(x,y):
    while not x == y:
        if x > y:
            x = x - y
        elif y > x:
            y = y - x
    return x
    
print('greatest common divisor found %s' % (str(greatest_common_divisor(24,10))))

That's much more straightforward, and can probably be more concise, but I'd like to stop here to keep it readable and easier to understand.

Wrap it up

Lets review what we did in the post. we understood the problems and used some geometry to show a solution. Since it was Euclids proof, it seems like the right thing to do. We then planned a solution using recursion as it matched our real world model.
This worked to a point, but we reviewed our options and implemented an iterative method that could handle much larger rectangles. Once we had that solved we optimized for the computational abilities of the language and the machine we are using.

Our last implementation works for all the tests above, and certainly seems to run faster. How much faster?
We will profile all these functions and find out in the next post:  http://jseller.blogspot.ca/2016/11/algorithms-intro-profiling-python-code.html

Anxiety about math may be a mis-understanding

Math. 

"Gaa!" is usually the reaction I get to that word, and I think that's too bad.

Why do I need to know it?

The reasons to learn math are really the same reasons we need to learn to read and write. Its not to remember words and recite what letter comes next; its so we can communicate with other people and understand what they are talking about, even if they aren't there.
We communicate to understand each other, and our language is made up of the bit and parts we learn by reading and writing on our own.
Math is a language that allows us to understand the world around us, and how it works. Its the language that we use to build technology.

Learning to read and write a language allows you to communicate. Its not about know what exact pronouns and adverbs go here or there; it gives you the tool to communicate with other people and understand what is happening.

Similar with math; the point isn't memorizing a times table; it's about having the tools to solve problems. If you can solve math problems many other problems just become easy to solve. Like getting employment and doing your taxes and not getting ripped off by the slicksters you will run into during your life. It just makes life more enjoyable having more tools in your toolbox.

By learning where math came from and why we use it, we can appreciate and understand it much easier than repetitive memorization. Math is the fundamental technology, and how technology is defined will help understand that line a little better.

Math is a handy tool we use to understand the world around us. People made it up, and use it for many purposes. Tools can be mis-used; but the tool itself isn't something to be scared of, even just a little bit.

Art

Math is art, with very practical uses. How is it an art? If you learn math as an art the practical aspects will emerge.

1. Reasoning and critical thinking
2. Elegance of solutions. Math is good when the solution has removed all needless complexity.

How do math relate to other arts?

• painting is both art, and practical when you paint rooms in a house
• music is art, is it practical? would the world be better off without music? of course not.

Practical is problem solving

• A defined, repeatable structure of problem solving can be transferred to any parts of life. Use the How to Solve it steps for any problem:
• Understand
• Plan
• Execute
• Review

Models that reflect real life

Why math? The patterns of life are all around us can be added up, so they were. There are hours in a day, and things to do. There is stuff to measure all the time, so a way to measure it was needed that everyone could understand. How do you count when you are small and learning? Usually its with your fingers: one, two, three, four, or five fingers can signal between two people the count of something. Once we got past 10 things to deal with, then it can get a bit complicated. This is where the tool called math shows its most basic and important value; the ability to model the real world with symbols and notation so we can understand them, and be able to understand the same thing together.

You can create it all with the basic fundementals, so learn those techniques and you will realize that more complex solutions are just extending these fundamentals. Don't Memorize solutions; memorizing math is like memorizing colors and shapes. Just create them with the basics

The real world problems early math was dealing with and help solve were not that complicated. Way back, you would have been farming, or maybe making pottery. If you are farming, you would have to know where to plant the crop seeds, or tend the herd of animals. How to measure this land?

To measure the land people used numbers to indicate how many steps (feet) they took around the land, and this was usually the shape that we know now to be a square or rectangle. (graphic). Now that all this land has been measured, it can be measured again to divide up what goes where. All of those smaller pieces can be added up to make the whole piece.

Adding (+) enabled us to go past counting on our hands, and was soon followed by subtracting (-).

At this point in history we just have numbers and geometry. This was the world of math for a long, long time.

Numbers

In the west, roman numerals were replaced with the set of numerals. 117 is easier than CXVII, and enabled the same operations to work on different bases then 10. Base 2 enables modern computation. These numbers originated in Arabia and India. Lots of important math advances occurred there while western Europe was in the dark ages.

Commerce

As people interacted and traded with each other, they needed to know how many potatoes they were trading for those 4 chickens. Currency was used, and basic math ensured that people could trust it as a mechanism to trade fairly.

Time

This did a whole lot to help us work with each other and understand how things worked in the world around us. How far something was and how long it would take to get there could be calculated.

Geometry

The size of the world was becoming comprehensible once we realized it wasn't flat, so the geometry of a sphere was discovered to understand that. It also works with a soap bubble and a basketball. That's a powerful tool!

People

It was a lot, and now valuable, so the sways of people and the ideologies they brought with them shaped the development of math and its understanding in the general public. This continues to this day!

Technology

Technology is a term used to describe the set of tools that we have made for ourselves. Math is the underlying technology to it all.
The size of the house and how big or small that can be. This enabled more and more technology through the correctness that math enables in engineering and architecture. Houses, buildings, trains, automobiles and airplanes, followed,
Computing and computing machines is an example of applying many types of mathematics to enable many amazing things we have around us today.
To build any technology we use math to define and tie all the components together, this is why its the fundamental technology

Who does math?

This is a list of my favourite characters from the long history that mathematics has.

https://al3x.svbtle.com/alexander-grothendieck

Galois

John Holland

Euler

Polya