Foundations of Differential Dataflow

Martín Abadi, Frank McSherry, Gordon Plotkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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.
Original languageEnglish
Title of host publicationFoundations of Software Science and Computation Structures
Subtitle of host publication18th International Conference, FOSSACS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015, Proceedings
EditorsAndrew Pitts
PublisherSpringer Berlin Heidelberg
Pages71-83
Number of pages13
ISBN (Electronic)978-3-662-46678-0
ISBN (Print)978-3-662-46677-3
DOIs
Publication statusPublished - 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume9034
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint Dive into the research topics of 'Foundations of Differential Dataflow'. Together they form a unique fingerprint.

Cite this