The various functional approaches to dataflow programming represent trade-offs between effectiveness and efficiency. On the one hand, we have lower-level approaches which are highly expressive but permit the formulation of programs with significant space-time inefficiencies. On the other hand, we have more abstract approaches which guarantee efficiency but at the cost of restricting expressiveness. As is generally the case, the more abstract idioms also make it harder for the programmer to write erroneous programs. Perhaps the most abstract style of dataflow programming is self-adjusting computation (SAC), which replaces the explicit notions of event and signal with implicit dependency links between memory cells, which propagate changes automatically and transparently. We call this transparent dataflow. It is abstract, concise, and efficient, yet it suffers from a significant restriction which limits its usefulness. It disallows dependency cycles. We introduce a new language for transparent dataflow, which generalises it to dependencies with cycles, greatly increasing its applicability. To handle circular dependencies we change the propagation mode from asynchronous to synchronous, which enables further applications such as filters and pipelines. The language is defined via an abstract machine which can be used to reason about soundness and (theoretical) efficiency, confirming that the language has desirable properties. We also provide a semi-naive practical implementation as an OCaml PPX extension, validating its (practical) efficiency via benchmarks.
Preprint (icfp19mlworkshop-paper64 (1).pdf) | 256KiB |
Thu 22 AugDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
13:30 - 15:00 | |||
13:30 25mTalk | Transparent Synchronous Dataflow ML Steven Cheung University of Birmingham, UK File Attached | ||
13:55 25mTalk | Programming with Rational Coinductive Streams ML Jean-Baptiste Jeannin University of Michigan, USA File Attached | ||
14:20 25mTalk | Efficient Deconstruction with Typed Pointer Reversal ML Pre-print |