Derivation

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) + "<<");
    }
}