[cello-devel] Re: [cells-devel] Cells II Functional Requirements

[Kenny Tilton]

Michael Naunton wrote:

>So, (where = is an arbitrary function of)
>
>B = X
>A = B
>
>I can see how to gate on B such that A remains quiescent.
>
>What about:
>
>B = X
>C = B
>A = X+C+B
>
>After X changes, A and B need to move to S+.  How do you get the
>ordering between A and B such that A only gets recomputed once?  I could
>just recompute A, recomputing B recursively as needed, but surely C must
>be marked as "possibly needing recomputation" on dX, i.e. we must
>traverse all recursive dependants of X.
>
>Is the recursive step needed, or am I missing something obvious here?
>
Yes and no. Original cells (until last year when I did RoboCells and it 
started to bite me in the ass) violated the new rules and would indeed 
recalculate A twice, the first time using values from obsolete Cells 
still to be recalculated. So it is an astute observation. But it just 
takes a little engineering to avoid that, which I will describe shortly. 
But first FWIW the worst case is actually worse than A=X+C+B. It would 
be something like:

    :a (c? (if X C B))

In other words, we cannot use dependency info from state S to do 
lookahead and calculate things in the right order, because the new value 
of X or some dependency can cause other rules to branch differently and 
go after unanticipated other state.

So there is some hair-raising engineering involved, which in part 
involves a rather heavy-handed trick: each input or make-unbound is 
assigned a sequentially increasing numeric ID. Eventually I will switch 
to get-internal-real-time and maybe start to have some fun with real 
time programming.

Each cell, when it gets recalculated or when it is determined to be 
unaffected by an input, gets stamped with the current state ID.

If it gets recalculated /and/ turns out to have changed, it gets stamped 
as changed. If it turns out to be unaffected, its "changed" flag will be 
nil.

Each access checks that any cell mediating the slot is current, if not 
it runs down the dependency graph looking to see if anyone is (a) more 
current and (b) changed. If so, it recalculates. if not, as described 
above it gets stamped as current and unchanged. As we return back up the 
dependency graph, these results trigger other recalculations where 
appropriate. Finally the slot access returns the value requested.

By stamping unaffected Cells as current, we ensure that getting to S+ 
touches each node at most once.

In Cells Classic the model I had in mind was dataflow, where data got 
pushed along dependency "wires" to dependent cells which then 
recalculated and possibly pushed data further along the dependency 
graph. That is still the upshot in Cells II, but now the model is "Is 
everybody current with state S+?". We begin with the answer "no" only 
for the direct dependents of X, and set about recalculating them. If the 
first dependent is A and it turns out A uses B and B also uses X, there 
is no problem because the access to B (during the calculation of A) will 
JIT come up with a current value for B. recalculating B and then A will 
add their dependents to the list of cells known to require 
recalculation, but those are deferred until after the original 
calculation of A is complete (to avoid re-entrance into A should B just 
kick off recalculations willy-nilly and some user H (for "higher up" the 
dependency graph) of B turns out to be interested in A as well as B.

So calculations just calculate, deferring notification of dependencies 
and outputs (ne echos) until the calculation has completed, to avoid 
re-entrance. Slot access always checks that any computed cell is 
current, satisfying that constraint.

I should mention that a correspondent does not like the constraint that 
state S++ not arise until all state has reached state S+. Certainly a 
program could work correctly without satisfying that constraint. One can 
also abuse gotos and still come up with a correct program. Cells 
certainly worked magnificently for big applications while violating 
almost all the new rules flagrantly. But I see no loss of expressive 
power with these new constraints, so why not go with the correctness 
guarantee implicit in never using obsolete state or missing state 
changes by jumping from S to S++?

kenny

-- 
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film 
Your Project Here! http://alu.cliki.net/Industry%20Application