I'm interested in the early history of published results on general-purpose space-time tradeoffs. In particular, I want to know who first described the following type of algorithm for evaluating a computation having an arbitrary dataflow graph with in-degree O(1) using space proportional to the depth (not width) of the dataflow graph (plus the size of the input) by doing a straightforward depth-first evaluation of the graph. In more detail:
Let the dataflow graph be G=(V,E) where V is the set of computational vertices (O(1)-size data values) and E is is the set of edges (v_p, v_s), such that the value of successor vertex v_s \in V depends immediately on the value of predecessor vertex v_p \in V. Let v_f be the vertex with no successors representing the final result of the computation. Let I be a canonically ordered set of input vertices (with no predecessors), for i \in I its value x(i) is given. For other vertices v \in S, their values are defined by x(v) = F_v(x(P(v))) where P(v) is a canonically ordered list of v's predecessors, x(P(v)) is the corresponding list of their values, and F_v is the vertex's function that determines its value as a function of the list of values of its predecessors. Assume that the length of P(v) is O(1) for all dataflow graphs in some given class of interest (e.g., Boolean circuits with 1- and 2-input gates).
Given this setup, the algorithm in question is fairly obvious & trivial:
def eval(v): (v can be any vertex in the graph)
let P := P(v), the list of v's predecessors (has O(1) elements by assumption)
let val[] := uninitialized array of |P| data values
for each predecessor p[i] in P (i.e. for i from 1 to |P|):
if p[i] is in I then
val[i] = x(p) (look up a given input)
else
val[i] = eval(p[i]) (recursive call)
return F_v(val[]) (apply vertex's function to list of predecessor values)
This takes O(d) levels of recursion, where d is the depth of the dataflow graph, and the stack space at each level is constant due to the assumptions that the in-degree of the dataflow graph is constant, and that the size of the data values is constant. (For simplicity here, I'm treating the size of the vertex references as constant as well, even though they are really logarithmic in |V|.) Thus, total space usage is O(d + |I|). The maximum width of the dataflow graph can be exponentially larger than this, so in the best case this technique can provide a pretty extreme space savings, in comparison to, say, a greedy forwards evaluation of the graph (which might be to, at each step, evaluate all vertices that directly depend only on vertices whose values are already known, and discard all vertices that are no longer needed because all of their immediate successors have already been computed).
Anyway, it's a fairly obvious technique, at least in retrospect, and it's certainly long-known, but I was wondering just how back the literature on it goes. Anyone know the early history of results of this sort (whether described in these terms, or other analogous ones), and what would be a good reference for digging into this subject?
Thanks very much, -Mike Frank
