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