This is some post showing off work I have done for my thesis. Well,
actually I will try to skip that and just publish it here, because
there will be no real need to publish it in a scientific way. It is
kind of a stupid step by step transformation. Hope you can follow
along. I know you will.
Can you show me the 'Hello World'-Program in Python once more.
Sure it's:
fib = lambda n: 1 if n == 0 or n == 1 else return fib(n -
2) + fib(n - 1)
This is great, but isn't it a huge waste to recalculate fib over and
over again?
Yes it is. And there is this thing memoization that saves the values.
Okay let's copy some pre.
No, we will not. For reasons described later we will try to implement
the turtles all the way down.
What does that mean?
Well, with Python we are writing in a very high level language.
Nothing special about this. But this post will describe the way down
what I compiler could do and grasps the notion towards the machine.
I don't understand what you mean.
Act don't talk.
Let's implement a stack where we push the values of functions unto.
The first to values are already known by definition.
cash = {}
cash[0] = 1
cash[1] = 1
So first thing to do is to look if the values are already in the dict.
try:
return cash[n]
except KeyError:
The recursive rest:
return cash[n] = fib(n - 2) + fib(n - 1)
This is the boring version. But you know, that there are more turtles
to run with. We are going deeper down.
So what is it doing this function-call?
Well nothing but pushing a new environment unto a stack. So let's do
this.
First we create the stack:
xs = []
And push a function there:
f = lambda d, e: d[e[1]] + d[e[2]]
>
This is tricky!
No it is not.
Judge by the actions:
cash[x[0]] = f(cash, x)
What we are doing is pushing the value of a function on the stack.
'cash' is the cash, of all calculated values, so we don't have to
recalculate anything twice. 'x' is something I have hidden from you.
So what is x?
It is a list!
(n - i, n - i - 1, n - i - 2)
Recognize that pattern? It is inside the Fibonacci function.
Why don't we pass just the arguments along, why do we have to save
this?
Now I have to show you the full source:
i = 0
xs = []
while True:
try:
x = (n - i, n - i - 1, n - i - 2)
f = lambda d, e: d[e[1]] + d[e[2]]
cash[x[0]] = f(cash, x)
for x in xs:
cash[x[0]] = f(cash, x)
break
except KeyError:
xs.insert(0, x)
i += 1
Do you notice there this hole thing has it's goto?
Yes, right before the for-loop.
Because there is the point there you have to go back in time and have
all the results precomputed. But before you have to insert the result
into xs. We have 'i' which controls we arguments all the way down.
The complete program is:
cash = {}
cash[0] = 1
cash[1] = 1
def fib(n):
try:
return cash[n]
except KeyError:
i = 0
xs = []
while True:
try:
x = (n - i, n - i - 1, n - i - 2)
f = lambda d, e: d[e[1]] + d[e[2]]
cash[x[0]] = f(cash, x)
for x in xs:
cash[x[0]] = f(cash, x)
break
except KeyError:
xs.insert(0, x)
i += 1
return cash[n]
import sys
print fib(int(sys.argv[1]))
Should we write programs like that? No! We can derive to such
programs. But just if there is a need for such optimizations. Also
think of the algorithm twice. I, myself found it easy to derive an
algorithm straight forward from the books, by reversing the process in
the end.
The cool thing about such derivation is, that the programm is correct
in the end. If you do it correctly with assertions. The hard part
about programming is, to define the problem correctly in a
mathematical way. That is challenging. Afterwards where should be
nothing but a derivation to a form a machine could do as fast as
possible. In research this is a hot topic to derive there
automatically. And me myself feel somehow being code-monkeyed to
derive to the actual program.
But it could also be a stimulating feeling like a painter to step back
and proof that the algorithm is still right.
For my project I did a mathematical analyse first, and then
implemented the program in Python because it is such an easy thing to
do. Most programs in controlling are just a bit set theory and
statistics.
Hope you enjoy this post.
P.S.:
Here is the Java-Version:
import java.util.ArrayList;
public class Fib {
static ArrayList cash;
static Integer fib(int n) {
try {
return cash.get(n);
} catch (IndexOutOfBoundsException idx1) {
int i = 0;
ArrayList xs = new ArrayList();
while (true) {
Integer[] x = null;
try {
x = new Integer[] { n - i, n - i - 1, n - i - 2 };
cash.add(cash.get(x[0]), cash.get(x[1]) + cash.get(x[2]));
for (Integer[] xx : xs) {
cash.add(cash.get(x[0]),
cash.get(xx[1]) + cash.get(xx[2]));
}
break;
} catch (IndexOutOfBoundsException idx2) {
xs.add(0, x);
i++;
}
}
}
return cash.get(n);
}
public static void main(String[] args) {
cash = new ArrayList();
cash.add(1);
cash.add(1);
System.out.println(">>" + fib(2) + "<<");
}
}
