Mon Jun 9 11:15:29 CEST 2008

concatenative dataflow language

it compiles to a dataflow graph. in order to do this incrementally, i
need to think about state. state, as represented in purrr, is the
current output of the network, so compilation is just adding a node.

(... [N1] [N2] +) -> (... [N3])


   [N1] [N2]
      | |

next decision: does this need a functional state, or can mutation be
used directly to build the graph? the tricky point is multiple

(... [N1] [N2] div/mod) -> (... [N3] [N4])

   [N1] [N2]
      | |
      | |
   [N3] [N4]

this could be represented as:

  [N1] = (div/mod [N1] [N2])
  [N2] = (shift (div/mod [N1] [N2]))

with dat structure sharing. this completely avoids the problem of
having to name intermediates.

a more symmetric rep would be

  [N1] = ((div/mod [N1] [N2]) 0)
  [N2] = ((div/mod [N1] [N2]) 1)

this even has a representation is straight scheme in the form of
memoized procedures.

let's try to build one on top of the pattern matcher.

the first notational problem i run into is specification of primitives
with multiple outputs, which is the problem i'm trying to solve!

so.. let's stop going in circles.

;;   Some important points:

;;   * Dataflow macros have a different representation. They have an
;;     entirely different compilation mechanism: one which involves
;;     register allocation and instruction scheduling. This
;;     representation should be made solid.

;;   * Give the dataflow macro rep, writing an automatic convertor to
;;     concatenative syntax is trivial.

;;   As a result, the macro/pattern.ss mechanism is only needed as a
;;   building block, not as a ui front end.

the composition mechanism should just build the graph, but represented
in such a way that 'executing' it is simplified.. this boils down to
how to do the binding, whether to use 2-way links, whether to represent
subgraph inputs by 2 nodes etc..

it looks like going for an explicit data structure that is later
interpreted or compiled might be the best approach. it's easiest to
understand. (the other way is to map it directly to scheme code, which
is also a DAG).

in hardware, all functions are many to one.. the only place where many
-> many functions come from is abstraction. can this fact be used to
simplify the problem? a subgraph is basically a list of (named)
expressions expressed in terms of (named) inputs.