Programmatic cycle detection

[alandipert]

Background

Currently a cycle in the Cell graph trashes the browser and no additional information is provided about its cause.

The current behavior is tenable because:

1. Browsers handle infinite JavaScript loops gracefully, and the browser's reload button be clicked no matter what.
2. Cycles are usually not hard to find in a mostly static dataflow scenario, as cells tend to have a syntactic representation. Source bisection can be used to discover which edit introduced the cycle.

The Enhancement

In more dynamic scenarios the cause of a cycle can be more difficult to determine. These are scenarios in which the shape of the dataflow graph is changing while the program is running, instead of it having a fixed shape determined in source code.

I think a worthy enhancement would be to detect cycles at runtime and notify the developer of their presence, programatically, with as much information as possible without introducing significant overhead.

This would ease development of dynamic dataflow applications and would also amene dynamic Javelin graphs to generative testing.

Implementation Idea

The Flapjax paper mentions the cycle detection approach taken in Garnet and Amulet:

...they do support cyclic constraint networks, without the need for explicit time delays as Flapjax requires. Instead, they resolve cycles with a simple depth-first "once-around" algorithm, which stops propagation when it returns toa node that has already been update.

I think we can do the same thing very easily. In propagate!, we store the cells we've propagated so far in a set. When we encounter a cell we've already processed a second time, we throw an exception.

The Garnet/Amulet "Lessons Learned" paper elaborates slightly:

Support for Cycles: A constraint is evaluated at most once if it is in a cycle. If the constraint is asked to evaluate itself a second time, it simply returns its original value.

[alandipert]

We've decided to defer this until we're confronting real problems that we can attribute to dynamic graphs.

Open questions include: what should we do when a cycle is detected? what's the relationship between this and reference counting, another feature that might be useful for dynamic graphs?