There was once a famous dispute of Greek philosophers about a ship that was said to have been owned by an hero centuries ago. Of course, the boat had changed: every bit of wood, every rusty nail and every string of linen had to be exchanged during all that time. Now the thinkers were wondering whether or not it was still the same ship.The morale of this little tale is that things can get complicated if stuff changes. But that’s just the way it is, right? That things change is the whole point of programming. Or maybe not… most think of programming as changing states of a machine, however it can be shown, that just calling functions is equivalent to our beloved Turing Machine. And I mean functions as in mathematical functions – they always return the same output for the same input.

So you can program without ever changing anything. But that begs the question: Why would you do that? It seems quite counter-intuitive. Yeah,welcome to the wondrous world of functional programming, where nothing ever changes!

Techniques

Memory

What is the clockrate of the computer you are working on? Chances are, it’s about 2.5GHz. However you probably got at least two cores, the newer the more. That’s the trend, you don’t get faster processors, but you get more. There are problems with that. If you can do more things in parallel, but want to do something as fast as possible, your CPU power does not just add. And if something changes, it can not spread very well across processors, because different parts of the program might change the same value at the same time making them inconsistent. Or you lock access while you access it, but then you’d have to wait.

Or you don’t change it at all and copy it in a smart way. You’d expect this to make your code even slower, but scientist did a great job inventing datastructures, that make this easy. In fact, you’ll probably never see a case that would make your code more than a factor of log(n)slower, as experiments have shown.

As memory access is the performance bottleneck today, being able to perform it in parallel helps quite a bit.

Remember your Calls

Another cool bit is memoization. To show students why recursion sucks, professors like to use the following example

Recursive version

def fibonacci(n):
	if n < 2:
		return 1
	else:
		return fibonacci(n-1)+fibonacci(n-2)

Iterative version

def fibonacci(n):
	a = b = 1
	for i in range(n):
		a,b = b,a+b
	return a

The first one is usually slow as hell, because you keep computing the same numbers over and over again. But as fibonacci is just dependent on n, you could just make a table for it and only compute the number, if it hasn’t been done already. That makes the performance the same as the iterative approach. We call that memoization and you can perform that only if your function is pure, because otherwise, there might be other influences on the outcome, which would not be taken into account with the caching. If the function is pure however, you can use it for all of dynamic programming without real performance penalty.

Being Lazy pays off

Quite possibly my favorite part is laziness. If the return value of a function call does not depend on its environment and thus the precise moment, in which it is called, you don’t need to compute it right away. Wait ’til you actually use the value and maybe, you don’t even need to calculate it at all. This extends so far, that you can simply make an infinitely big datastructure, for example a list of all natural numbers.

That’s it for today, but there might be other articles following up on this topic.

Have fun!

Zombiecalypse