Lambda the Ultimate

PvR: "We use computation spaces to wait until all threads suspend simultaneously."

I'm not familiar with Oz, so I don't know about computation spaces in oz. Does this scheme work if the upstream threads not strictly a hierarchy (they cross branch with other computations), or if the current thread is connected with others in a recursive loop?

I don't completely understand your question. A computation space contains an arbitrary set of threads, which are situated inside the space. The threads just execute concurrently in the usual fashion. There is no hierarchy between the threads that influences this. The space has a global synchronization operation that can wait until all the threads have finished their work.

There are rules that handle how information is communicated into a space and from a space. These rules are designed to be useful for constraint programming. One rule is that a space cannot bind a dataflow variable that is declared outside of the space. It can only read that variable. So I define two Oz ports outside of the space. The first port's stream is read inside the space, so sending to the first port will send information into the space. The second port's stream is read outside the space. So inside the space, sending to the second port will send information out of the space.

..but inside the space there are possibly redundant calculations being performed? If one has a static acyclic graph, then nodes can be scheduled with priorities assigned according to the index in a topological sort so that no redundant calculations are ever performed. I'm trying to understand to what extent computation spaces are a solution for preventing redundant calculations in a dynamic graph. It seems that within the space there can be redundant calculations, but the space prevents redundant firings from being observed leaving the space. Is that correct?

I have a real time system where any subset of a set of multiple input ports may fire simultaneously and I only want to compute the subgraph that depends on all of the ports that actually fired at the same time. I only know how to do this with a global topological sort. No local firing rules I know of work for all cases. Topological sorts are expensive to do in real time and so this encourages static graphs. I have used hierarchical graphs where subgraphs are spawned within nodes of a parent graph in order to be able to have some dynamic graph topology.

inside the space there are possibly redundant calculations being performed?

Yes. Threads inside the space are scheduled according to the usual preemptive round-robin scheduler.

the space prevents redundant firings from being observed leaving the space

Yes. The space makes it possible to put a global scheduling constraint on all the threads inside it: wait until all threads are blocked. This will keep redundant firings from being observed.

No local firing rules I know of work for all cases.

Yes, that is what our empirical investigations showed too. The space adds a global firing rule.

Topological sorts are expensive to do in real time

I agree. I think that the solution using computation spaces is quite efficient in many cases: the amount of redundant computation is small and bounded by a constant factor. In particular, the whole subgraph is not recomputed when a new event arrives, but only the part with changed values.

The space's scheduling constraint is implemented efficiently. I think that the design rule "no premature optimization" applies here. I would not do a topological sort until I had proof that my simpler solution was too expensive.

Components can be implemented with Java code, and so its possible for signals to be implemented in anyway thats convenient (e.g., with sockets). The biggest constraint is that state changes must be pushable. Caching components can be interposed in programs like registers can be interposed between components. This capability leads to interesting issues with glitches, which our implementation deals with.