Foundations of Differential Dataflow
Martín Abadi, Frank McSherry, and Gordon D. Plotkin
Discussion led by Dietrich Geisler on February 12, 2018
Differential dataflow is a recent approach to incremental computation that relies on a partially ordered set of differences. In the present paper, we aim to develop its foundations. We define a small programming language whose types are abelian groups equipped with linear inverses, and provide both a standard and a differential denotational semantics. The two semantics coincide in that the differential semantics is the differential of the standard one. Möbius inversion, a well-known idea from combinatorics, permits a systematic treatment of various operators and constructs.
PDF@Springer-Link