Dependency graphs

[philip k]

Hi,

I've been working on a dataflow library in Clojure before hearing
about Flapjax / FrTime and came up with a way of describing dependency
graphs, however I'm not sure if I'm on the right track; I would love
to hear if somebody sees any fundamental flaws with this idea.

Basically the dependency graphs are described explicitly using maps
(Clojure syntax):

(def g (make-graph
{
:event (rfork :mousedown :mouseup)

:mousedown (rfilter :mdown-action #(= (:type %) event-type/mdown))
:mouseup (rfilter :mup-action #(= (:type %) event-type/mup))

:mdown-action (raction #(... do something on mdown...))
:mup-action (raction #(... do something on mup...))
}))

Events can then be pushed down the graph:

(push g :event some-event)

rfork, rfilter, raction produce functions that have the following
signature:

:: Graph -> Value -> ()

i.e. they don't return a value at all. Side effects happen only in the
leaves (:mdown-action, :mup-action in the above example). Graphs can
also be connected to other graphs, both pushing values to them or
receiving values (this is done through a global callback table).

For example rfilter has the following implementation:

(defn rfilter [node pred]
(fn [graph value] (if (pred value) (push graph node value)))) ; ::
Graph -> Value -> ()

That's it. Glitches can be prevented easily, since the only way to
introduce glitches is isolated in rfork, i.e. when a value is
distributed to multiple nodes; a graph maintains a value table,
storing the current value for every node. This means that rfork can
update the node values of all its dependencies before letting them
fire.

Dynamic dependencies can be achieved by having an implicit :self node
that always has the value of the current graph and upon receiving a
value, updates a global graph table. Every graph has an internal id
that doesn't change when it is updated; when pushing values, the graph
is first fetched from the global table, thus allowing delayed event
propagation.

The distinction between events and behaviors is implicit - it is
possible to define multiple-argument nodes (lifting in Flapjax's
terminology) that only fire when just a *subset* of their inputs fire
but still receive the current values of all their sources, thus
achieving the desired semantical difference between events and
behaviors, as I understand them.

The advantages of this scheme, from my limited understanding, are:

* isolation of mutable state in a global graph table (I'm not counting
the per-graph value table since it could easily be done in a purely
functional style by letting push return an updated graph) - no mutable
source / children arrays per node need to be maintained
* explicit flow of data - maybe easier to reason about flow logic?
* expanding on the previous point, this allows for things like easy
graphical representation of graphs, cycle detection, optimizations
(lowering), etc
* easy glitch prevention

The disadvantages:

* composability suffers - merging graphs is possible (by generating
unique node names), but not as elegant. This is a big one, however.
* and others I don't see right now

Do you see any fundamental flaws with this scheme? I would like to
decide if I should furhter pursue this or just reimplement a subset of
Flapjax.

Thanks!