Kahn Process Networks are a very nice sweet spot for functional purity and concurrency, and are widely applicable. I’ve recently considered them as a viable alternative to monadic effects models. However, KPNs are missing an important feature: the ability to merge asynchronous inputs from different channels. There is no consistent sense of time for messages within a KPN.
Fortunately, it is easy to add time to KPNs, and thus have reactive process networks:
- Every process and message is stamped with an implicit time value.
- Channels have logical latency, adding that latency to time stamps.
- READ may return Nothing if no messages are available at the process time.
- WRITE will stamp the outgoing message with the process’s current time.
- In addition to READ and WRITE, a process may WAIT on a set of channels.
- WAIT will advance the process time to the earliest message in the set.
For efficient distributed implementation, we’d implicitly use synchronization messages to report the advance of logical time for a waiting process. Intriguingly, it is feasible to perform some optimistic concurrency: determine likely future outputs on an assumption that no last-second messages on open input ports will change things. And of course, we’ve also solved the expressive weakness of KPNs. We can merge asynchronous messages into a stream, or represent clock-like behaviors – loops with latency.
Another interesting point is that basic KPNs don’t support bounded-buffer ‘push back’ because it can result in datalock. We can implement them that way and accept the risk, but it isn’t part of Kahn’s original model. But with reactive KPNs, we don’t as much need bounded-buffers because we can bound computations in ‘time’, e.g. by evaluating a KPN up to a given time or controlling the advance of time for open input channels.
The time stamps are logical, and are never directly observed by a processes. Time stamps and latencies may use simple natural numbers. We can ‘normalize’ time stamps within a network, e.g. by subtracting the smallest time stamp in the network from all time stamps in the network. For integration with real-time systems, our logical time stamps may have a simple mapping to wall-clock times, such as logical microseconds. We can also use logical latencies to guide physical distribution when evaluating large process networks.
The original KPN behavior is supported. We can always WAIT before READ. Or we can simply use zero-latency wiring and never advance time on open input channels. While READ does not logically WAIT, it must still implicitly wait until we determine whether or not more messages will arrive at a process’s current time.
Reactive process networks resolve my few remaining concerns with using KPNs as both a primary effects model and as a foundation for first-class high-performance distributed programming within purely functional computations. Reactive KPNs could also serve as an excellent substrate for my reactive demand programming model.
Awelon Blue 