Kenny replied to me saying: > Yep. But with Cells the dependency graph is just a shifting record of > who asked who, shifting because all of a sudden some outlier data will > enter the system and a rule will branch to code for the first time, > and suddenly "depend on" on some new other cell (new as in never > before used by this cell). This is not subject to static analysis > because, in fact, lexically everyone can get to everything else, what > with closures, first-class functions, runtime branching we cannot > predict... fuggedaboutit. > > So we cannot say, OK, here is "the graph" of our application > model. All we can do is let her rip and cross our fingers. :)
Yes, if you have Turing completeness in your dependency graph, the problem is unsolvable. However, it's like the static v. dynamic typing debate, you can pick how much you want to allow your graph to be dynamic versus how much "safety" you want. In particular, I suspect that in many applications, one can compute the set of potentially problematic dependencies (and that set will be empty). It's just a matter of structuring and annotating them correctly. Just like one can create type systems that work for ML and Haskell. Of course, if you treat your cell references like C pointers, then you get what you deserve. Note that you can even run the analysis dynamically, recomputing whether the graph is cycle free as each dependency changes. Most updates have local effect. Moreover, if you have used topological sort to compute an ordering as well as proving cycle-free-ness, the edge is only pontentially problemantic when it goes from a later vertex in the order to an earlier one. I wouldn't be surprised to find efficient algorithms for calculating and updating a topological sort already in the literature. It is worth noting that in typical chip circuitry there are constructions, generally called "busses" where the flow of information is sometimes "in" via an edge and sometimes "out" via the same edge and we can model them in a cycle-free manner. If you want to throw up your hands and say the problem is intractable in general, you can. However, in my opinion one doesn't have to give up quite that easily. -Chris -- http://mail.python.org/mailman/listinfo/python-list
