Skip to main content



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