Propagator networks are a pain to program. You have to break up your problem into a set of computation nodes, allocate cells for intermediate values, and wire up the inputs and outputs. It's pretty straightforward to do this by hand for a small program, but it would be pretty nasty for something more complex. In addition, propagator networks for recursive functions require a bit of trickery to get them to work. On the other hand, the standard recursive descent evaluation strategy, while being a much easier model to program to, imposes implicit restrictions on evaluation order that get in the way of non-deterministic programming.

The solution is to compile our Scheme programs into a propagator network. This is what Chris Hanson showed to us on day 5. This is doable, but it is quite tricky. I don't think Chris had the time to explain all the nuances of the compilation, but if he had a difficult time making it work correctly, it can't be easy.

One thing that I thought was unusual was the way recursive procedures were compiled. The propagator network for a recursive procedure is not instantiated and linked until the procedure is actually invoked. This allows recursive procedures to run by instantiating only as much of the propagator graph as necessary to compute the answer. What strikes me as unusual about this is that a standard expression-based language usually prevents runaway recursion by making conditionals be non-strict. The propagator network seems to have the recursion grounded in a different place. I asked Chris is this was an issue and he thinks it may be what is causing some of the compilation difficulties.

Now that we have generated a propagator network, we need to run it. It is relatively straightforward to create a scheduling process that notes which value cells have changed and pushes the values through the appropriate computation nodes, but the performance is nothing to write home about. What is more interesting is to create a propagation-based virtual machine and run our propagator network against that. We can use JIT technology to accelerate the virtual machine and get reasonable performance. It may also be possible to partition the propagator network into independent or loosely coupled subnets. If so, then we can distribute the computation of the subnets among several physical machines.

This is where we wrapped up the course.

Next post, maybe I'll mention some ideas that occurred to me while I was listening.