Foundations of Differential Dataflow

Abstract. 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 pro-gramming language whose types are abelian groups equipped with linear inverses, and provide both a standard and a differential denotational se-mantics. 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.