[cello-devel] Re: [cells-devel] Cells II Functional Requirements
Kenny Tilton
ktilton at nyc.rr.com
Tue Jun 8 04:45:13 UTC 2004
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
More information about the cello-devel
mailing list