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

[Chris F Clark]

David C Ullrich asked:
> Q: How do we ensure there are no loops in the dependencies?
> 
> Do we actually run the whole graph through some algorithm
> to verify there are no loops?

The question you are asking is the dependency graph a "directed
acyclic graph" (commonly called a DAG)?  One algorithm to determine if
it is, is called "topological sort".  That algorithm tells you where
there are cyclces in your graph, if any, and also tells you the order
of the dependencies, i.e. if x is updated, what you have to update
downstream AND THE ORDER you have to perform the downstream
computations in.  We use this algorithm for solving just the kind of
dataflow problems you are talking about in our circuit design tools.
Circuit designs have one-way dependencies that we want to sort and
resolve--similarly, we don't want cycles in our circuits except ones
that pass through clocked flip-flops.  We solve such problems on
circuits with millions of gates, i.e. enough gates to represent the
CPU of your computer or a disk controller chip or a router.

I believe there are also algorithms that allow you to construct only
acyclic (the technical term for non-looping) graphs and don't require
you to enter the vertexes (verticies if you prefer) of the graph in
any specific order, and in the worst case you can always run the
topological sort on any graph and determine if the graph is cyclic.

The area is well-studied and you can find a variety of algorithms that
solve most interesting graph problems as they all occur over-and-over
in numerous diverse fields.

Hope this helps,
-Chris

*****************************************************************************
Chris Clark                    Internet   :  compres at world.std.com
Compiler Resources, Inc.       Web Site   :  http://world.std.com/~compres  
23 Bailey Rd                   voice      :  (508) 435-5016
Berlin, MA  01503  USA         fax        :  (978) 838-0263  (24 hours)
------------------------------------------------------------------------------