Cells II seems to be OK, and is back at work running Cello as well as passing its regression tests. It will be released when I figure out whether to put everything up on the Cells or Cello project. I plan from here out to focus more on developing a commercial title (using Cello) than on porting Cello. This may mean I will not even look at OS X until the commercial title is ready to go and I want the OS X version (I will). This also means I want a very simple way to share my ongoing work on Cello/Cells and the easiest will be to have one cvs repository I update periodically.
Anyway, for now, here is the spec which guided the Cells II rewrite:
Suppose the application is at some steady state S in which all Cells (slots of instances) are either inputs (what I used to call c-variable) or have been computed from other Cells.
Now the application polls a socket or OS event stream and gets a new input, which leads to some cell X being assigned a new value.
Suppose also the new value for X is different from the prior value (according to a user-definable test). We now have not just a write operation but also a semantically meaningful change to X, so we also consider a new state S+ to have been established, with X being the only Cell to have reached state S+.
Now suppose there exists some cell A which depends only on cell B which depends only on X. Suppose also that when cell B gets recomputed to reach state S+, the change test for B's new value indicates "no change". Let us then say B is dependent on the change to X but /unaffected/ by it.
At this point, all data points other than X are obsolete. Formally:
dX establishes state S+; X is by definition affected by dX, and reaches S+ trivially; all state unaffected by dX is considered to be at state S+; all other state is still at S.
Cells is responsible for automatically ensuring all data points reach state S+ within these constraints:
[] completeness: all non-lazy cells affected by X will be recomputed
[] consistency: once state S+ exists, computations should involve values only from state S+. Note that this means state S++ cannot be allowed to arise during the transition from S to S+.
[] effciency: only cells affected by X get recomputed, only once, and only those cells which change will be scheduled for output.
[] useability: no re-entry of cell computation code, mainly so that programmers need not worry about it.
kt
Kenny Tilton wrote:
Cells II seems to be OK, and is back at work running Cello as well as passing its regression tests. It will be released when I figure out whether to put everything up on the Cells or Cello project. I plan from here out to focus more on developing a commercial title (using Cello) than on porting Cello. This may mean I will not even look at OS X until the commercial title is ready to go and I want the OS X version (I will). This also means I want a very simple way to share my ongoing work on Cello/Cells and the easiest will be to have one cvs repository I update periodically.
Anyway, for now, here is the spec which guided the Cells II rewrite:
Suppose the application is at some steady state S in which all Cells (slots of instances) are either inputs (what I used to call c-variable) or have been computed from other Cells.
Now the application polls a socket or OS event stream and gets a new input, which leads to some cell X being assigned a new value.
Suppose also the new value for X is different from the prior value (according to a user-definable test). We now have not just a write operation but also a semantically meaningful change to X, so we also consider a new state S+ to have been established, with X being the only Cell to have reached state S+.
Now suppose there exists some cell A which depends only on cell B which depends only on X. Suppose also that when cell B gets recomputed to reach state S+, the change test for B's new value indicates "no change". Let us then say B is dependent on the change to X but /unaffected/ by it.
should be "A and B are dependent on but unaffected by the change to X".
kt
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?
-- Michael
On Mon, 2004-06-07 at 21:51, Kenny Tilton wrote:
Cells II seems to be OK, and is back at work running Cello as well as passing its regression tests. It will be released when I figure out whether to put everything up on the Cells or Cello project. I plan from here out to focus more on developing a commercial title (using Cello) than on porting Cello. This may mean I will not even look at OS X until the commercial title is ready to go and I want the OS X version (I will). This also means I want a very simple way to share my ongoing work on Cello/Cells and the easiest will be to have one cvs repository I update periodically.
Anyway, for now, here is the spec which guided the Cells II rewrite:
Suppose the application is at some steady state S in which all Cells (slots of instances) are either inputs (what I used to call c-variable) or have been computed from other Cells.
Now the application polls a socket or OS event stream and gets a new input, which leads to some cell X being assigned a new value.
Suppose also the new value for X is different from the prior value (according to a user-definable test). We now have not just a write operation but also a semantically meaningful change to X, so we also consider a new state S+ to have been established, with X being the only Cell to have reached state S+.
Now suppose there exists some cell A which depends only on cell B which depends only on X. Suppose also that when cell B gets recomputed to reach state S+, the change test for B's new value indicates "no change". Let us then say B is dependent on the change to X but /unaffected/ by it.
At this point, all data points other than X are obsolete. Formally:
dX establishes state S+; X is by definition affected by dX, and reaches S+ trivially; all state unaffected by dX is considered to be at state S+; all other state is still at S.
Cells is responsible for automatically ensuring all data points reach state S+ within these constraints:
[] completeness: all non-lazy cells affected by X will be recomputed
[] consistency: once state S+ exists, computations should involve values only from state S+. Note that this means state S++ cannot be allowed to arise during the transition from S to S+.
[] effciency: only cells affected by X get recomputed, only once, and only those cells which change will be scheduled for output.
[] useability: no re-entry of cell computation code, mainly so that programmers need not worry about it.
kt
cells-devel site list cells-devel@common-lisp.net http://common-lisp.net/mailman/listinfo/cells-devel
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
-
Kenny Tilton -
Michael Naunton