A critic of Guido's blog on Python's lambda

[Chris F Clark]

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