new feature memoizing rules

So, I was going to write up about "similar" in this phase of the project, but today I implemented a new feature I want to mention: "memoizing rules". Rules that save the results of their computation. I guess the motivation was quantum mechanics. This whole project I have been borrowing/co-opting ideas from QM. bra's, kets, operators, superpositions, exponentiating operators, and so on.

Indeed, stored rules were based on the QM idea that an object doesn't have a property until you measure it. In BKO, say an example like this (making use of stored rules):
is-alive |cat> #=> normalize pick-elt (0.5|yes> + 0.5|no>)

OK. So that is the start of a representation of Schroedinger's poor cat, but what about wave-fn collapse? The idea that before measurement it is in a superposition, but after measurement it is in a single state. Stored rules almost represent this, but not quite. And hence memoizing rules (NB: the "!=>"):
is-alive |cat> !=> normalize pick-elt (0.5|yes> + 0.5|no>)

With this new notation we have both "is-alive |cat>" is undefined until we measure, and once we measure it, it collapses into one state. Hopefully an example in the console will help explain:

-- load up the rules, and see what we have:
sa: dump
----------------------------------------
|context> => |context: memoizing Schrodingers cat>

is-alive |cat> #=> normalize pick-elt (0.5|yes> + 0.5|no>)
memoizing-is-alive |cat> !=> normalize pick-elt (0.5|yes> + 0.5|no>)
----------------------------------------

Now, ask in the console the status of the cat:

sa: is-alive |cat>
|yes>

sa: memoizing-is-alive |cat>
|no>

Now see what we have:

sa: dump
----------------------------------------
|context> => |context: memoizing Schrodingers cat>

is-alive |cat> #=> normalize pick-elt (0.5|yes> + 0.5|no>)
memoizing-is-alive |cat> => |no>
----------------------------------------

So there we have it! Undefined value until measurement, and collapse to a single value after measurement.

OK. So that is cool and all, but what is the use of this? Well, one is to drastically speed up recursive algo's like Fibonacci. Here, let me show:

sa: dump
----------------------------------------
|context> => |context: memoizing 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>)
----------------------------------------

-- ask value of fib |13>
sa: fib |13>
|233>
 
-- see what we now know:
sa: dump
----------------------------------------
|context> => |context: memoizing 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 |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>
----------------------------------------

Cool, huh! And is a massive speed up! I've been told normal Fibonacci is O(n!), not sure exactly what the memoizing fib is, but it is closer to O(n). And powerfully enough, we don't really have to do much work to use this auto-memoizing feature. Instead of using stored-rules "#=>", just use the exact same code with a memoizing-rule "!=>".

Update: I just ran fib-ratio |100>, and it was smoking fast! Almost instant. Previously, fib-ratio |30> was sloooow. Code here.

Home
previous: announcing phase 3 similar and find topic operators
next: a similarity metric

updated: 19/12/2016
by Garry Morrison
email: garry -at- semantic-db.org