dags.md

1. for "missing?" we often need to query database to check if an item exists. If predicates are truly independent, we will need to do the query again to return the item.
2. "data flow" looks something like this (in Prismatic's Graph lib):

(def stats-graph
  {:n  (fnk [xs]   (count xs))
   :m  (fnk [xs n] (/ (sum identity xs) n))
   :m2 (fnk [xs n] (/ (sum #(* % %) xs) n))
   :v  (fnk [m m2] (- m2 (* m m)))})

or as a picture:

This is basically a data structure that more-or-less explicitly encodes data dependencies between functions and allows to check stuff like "all data needed for a function is already computed when it's called".

On the other hand, "decision graph" (it can be encoded as FSM, as in the case of your HTTP decision diagram) is all about callbacks and outcomes. In all practical implementations that I've saw, callbacks were allowed to pass something "downstream" (in state or query) to solve the problem mentioned in (1). However, this introduces implicit data dependencies between callbacks that are inferior to explicit "data flow" model.

Therefore, it seems preferable to somehow "merge" both approaches, but I don't know yet how. It would be interesting to hear your thoughts on this.

ps: i starred your gist, so i should get notifications now. thanks for pinging me on twitter, don't know if git email notification is just slow or doesn't work on gists (starred or not)

Here is a braindump that came out of all this simmering in my head for a while.

I believe that the whole system can have an interface similar to Graph with a few exceptions.

First, we need "decision graph" (like the one that you've made for HTTP). While Graph deduces execution flow from functions' input/output specs, in the case of a protocol implementation it's fixed (except for possible optimizations). However, we can still define default implementations of callbacks in a way similar to Graph's — like a map from keys (:is-method-head-get?) to functions with semantics of "callback takes a map of values computed to the point and returns a value for it's key".

Second, "compilation model" is somewhat different: we walk through all possible trajectories through the decision graph. At each decision-related callback we look for "values needed" set, search for appropriate callback in a Graph-like map, plug it in before the "decision" callback if it exists and wasn't executed before in the trajectory or throw an error if it doesn't or if there is a circular dependency. All this defines some mix of lazy (for values needed by "decision" callbacks) and eager (for decision points) evaluation. We are also validating that every value needed "downstream" (like etag in the Datomic example) is produced by some callback "upstream".

As for specs, "values needed" sets for "decision" and "outcome" callbacks can (and probably should) be spec'd in addition to "decision graph". Spec should probably be concerned with required subsets of needed values (so user can depend on more values, but not less). This way, "200 OK" callback may depend on "entity" and "content-type" values:

{:outcome-200 [:entity :accepted-content-type]
 :accept-matches? [:accepted-content-type :available-content-types]}

To implement this stuff in a language of choice one will need to choose data structure for value name → callback map, implement a "compiler" and a way to read specs. To implement a particular protocol (such as HTTP), one implements all "decision" and "outcome" callbacks, as well as "custom" callbacks like entity.

By the way, all this looks like your "B" example.