[cells-devel] Cells II Functional Requirements

[Michael Naunton]

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 at common-lisp.net
> http://common-lisp.net/mailman/listinfo/cells-devel