factorial and Fibonacci in BKO

Last post I defined arithmetic. So here a couple of examples:

Factorial:
|context> => |context: factorial>
fact |0> => |1>
n-1 |*> #=> arithmetic(|_self>,|->,|1>)
fact |*> #=> arithmetic( |_self>, |*>, fact n-1 |_self>)

eg:
sa: fact |5>
|120>

Fibonacci:
|context> => |context: Fibonacci>
fib |0> => |0>
fib |1> => |1>
n-1 |*> #=> arithmetic(|_self>,|->,|1>)
n-2 |*> #=> arithmetic(|_self>,|->,|2>)
fib |*> #=> arithmetic( fib n-1 |_self>, |+>, fib n-2 |_self>)
fib-ratio |*> #=> arithmetic( fib |_self> , |/>, fib n-1 |_self> )

eg:
sa: fib |10>
|55>

sa: fib |11>
|89>

sa: fib |20>
|6765>

sa: fib |21>
|10946>

sa: fib-ratio |30>
|1.6180339887482036>

-- NB: if we have only defined fib |0> and fib |1> the debugging info for fib-ratio |30> is insane!
So a massive speed up is to do these first:

fib |10> => fib |10>
fib |11> => fib |11>
fib |20> => fib |20>
fib |21> => fib |21>

-- NB: these work by making use of label descent.
-- and are an example of "memoization".

Next thing to observe is that fib/fact are linear and are applied separately to all kets in the superposition:

sa: fib (|10> + |11> + |12> + |13> + |14> + |15>)
|55> + |89> + |144> + |233> + |377> + |610>

sa: fact (|0> + |1> + |2> + |3> + |4> + |5> + |6> + |7>)
2.000|1> + |2> + |6> + |24> + |120> + |720> + |5040>

And that's it for now.
I guess I will also mention that I had not intended BKO to handle recursion, it just emerged naturally after implementing stored rules.

Update: First, it is time I explained these:
fib |10> => fib |10>
what is going on is that fib |10> on the right hand side is being computed. Then the result is being stored at "fib |10>". So next time you ask what is "fib |10>" it does a simple look-up, and not a full computation. The reason is that a simple look up has higher precedence than the general "fib |*>" rule (which is because of how we implemented label-descent).

Next, a quick example of the magic of tables:

sa: table[number,fact,fib] range(|1>,|11>)
+--------+----------+-----+
| number | fact     | fib |
+--------+----------+-----+
| 1      | 1        | 1   |
| 2      | 2        | 1   |
| 3      | 6        | 2   |
| 4      | 24       | 3   |
| 5      | 120      | 5   |
| 6      | 720      | 8   |
| 7      | 5040     | 13  |
| 8      | 40320    | 21  |
| 9      | 362880   | 34  |
| 10     | 3628800  | 55  |
| 11     | 39916800 | 89  |
+--------+----------+-----+