DSL: Represent transient nodes

[anshumanmohan]

We have a whole discussion, starting at #5 (comment), about giving the DSL the ability to represent transient nodes. This issue is just a bookmark so we don't forget about that thread.

Original post below, and much more discussion in the thread.

The idea is for the DSL to be able to represent not only a source program (like a user might write) but also a program that has been compiled (in the Formal Abstractions sense) into a program that runs against a different topology but behaves identically.

So for example, the user might write the policy

fair(fifo (foo),
     fifo (bar),
     fifo (baz))

which is written against a ternary tree of height two.

Then we might compile this policy so it runs against a binary tree of minimum height. The catch is that we still want to express that new policy in the DSL. That is, we want to be able to look at and study the compiled policy in a DSL before we compile it (in the Calyx sense) down to an accelerator.

The compiled policy won't be as neat and tidy as our user-written one, but at least it'll be somewhat readable. We'll also be able to state and prove equivalence of two programs written in the same DSL. This is nicer than trying to directly prove that a program written in the DSL is equivalent to the program running on the accelerator.

The challenge, of course, is that when we compile policies running on one topology to run on another, the new control program often needs to make scheduling decisions that "look through" intermediate nodes. The DSL as presented above is not immediately going to be able to do what this comment describes. We will need a careful tweak.