## Fibonacci

Our first example is about as simple as it gets, the well known Fibonacci sequence. We start by defining the first two values of the sequence, and then define a recursion relation. Though there are quite a few things to unpack here. |*> is a special ket called the star ket, and we use it to define an operator with respect to all kets, not just a single ket. The second part of this is, at the time of learning, we don't know which ket the rule is being applied to. So we have another special ket called the self-ket |_self>, whose value is filled in at invoke time. Next up, we have another type of learn rule called the "memoizing learn rule", which is denoted by !=>. At invoke time, the RHS of the learn rule is calculated, and then stored with respect to the ket the operator was applied to, ie, memoized. This provides a particular speed-up for recursive operators, at the cost of a little memory. The next two pieces of this example are easier to explain. minus[n] subtracts n from the ket it is applied to, and ++ is an infix operator that adds the value of a pair of kets. Noting that we couldn't use just a single + since that is already taken by our notation for superpositions. Finally, we invoke the Fibonacci operator using our table operator, with input values in the range 0 to 15.

Here is the code:

```-- Implement the Fibonacci sequence:
-- updated to the version 3.1.1 language

Fib |0> => |0>
Fib |1> => |1>
Fib |*> !=> Fib minus[1] |_self> ++ Fib minus[2] |_self>

-- now a quick demonstration:
table[number, Fib] (|0> .. |15>)
```

Here is the output from the code:

```+--------+-----+
| number | Fib |
+--------+-----+
| 0      | 0   |
| 1      | 1   |
| 2      | 1   |
| 3      | 2   |
| 4      | 3   |
| 5      | 5   |
| 6      | 8   |
| 7      | 13  |
| 8      | 21  |
| 9      | 34  |
| 10     | 55  |
| 11     | 89  |
| 12     | 144 |
| 13     | 233 |
| 14     | 377 |
| 15     | 610 |
+--------+-----+
|table>
```

To demonstrate the effect of our memoizing learn rule, here is what we know after invoking the table:

```sa: dump
------------------------------------------
|context> => |Global context>

Fib |0> => |0>
Fib |1> => |1>
Fib |*> !=> Fib minus[1]|_self> ++ Fib minus[2]|_self>
Fib |2> => |1>
Fib |3> => |2>
Fib |4> => |3>
Fib |5> => |5>
Fib |6> => |8>
Fib |7> => |13>
Fib |8> => |21>
Fib |9> => |34>
Fib |10> => |55>
Fib |11> => |89>
Fib |12> => |144>
Fib |13> => |233>
Fib |14> => |377>
Fib |15> => |610>
------------------------------------------

sa:
```

Raw file here.