Foundations of Differential Dataflow

Martín Abadi; Frank McSherry; Gordon Plotkin

doi:10.1007/978-3-662-46678-0_5

Foundations of Differential Dataflow

Martín Abadi, Frank McSherry, Gordon Plotkin

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Foundations of Software Science and Computation Structures
Subtitle of host publication	18th 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
Editors	Andrew Pitts
Publisher	Springer
Pages	71-83
Number of pages	13
ISBN (Electronic)	978-3-662-46678-0
ISBN (Print)	978-3-662-46677-3
DOIs	https://doi.org/10.1007/978-3-662-46678-0_5
Publication status	Published - 2015

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	9034
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-662-46678-0_5

Abadi et al 2015 Foundations of Diffoerential DataflowAccepted author manuscript, 577 KB

http://dx.doi.org/10.1007/978-3-662-46678-0_5

Cite this

Abadi, M., McSherry, F., & Plotkin, G. (2015). Foundations of Differential Dataflow. In A. Pitts (Ed.), Foundations of Software Science and Computation Structures: 18th 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 (pp. 71-83). (Lecture Notes in Computer Science; Vol. 9034). Springer. https://doi.org/10.1007/978-3-662-46678-0_5

Abadi, Martín ; McSherry, Frank ; Plotkin, Gordon. / Foundations of Differential Dataflow. Foundations of Software Science and Computation Structures: 18th 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. editor / Andrew Pitts. Springer, 2015. pp. 71-83 (Lecture Notes in Computer Science).

@inproceedings{522158de21a9415abd6e55b311cb7fd8,

title = "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 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{\"o}bius inversion, a well-known idea from combinatorics, permits a systematic treatment of various operators and constructs.",

author = "Mart{\'i}n Abadi and Frank McSherry and Gordon Plotkin",

year = "2015",

doi = "10.1007/978-3-662-46678-0\_5",

language = "English",

isbn = "978-3-662-46677-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "71--83",

editor = "Andrew Pitts",

booktitle = "Foundations of Software Science and Computation Structures",

address = "United Kingdom",

}

Abadi, M, McSherry, F & Plotkin, G 2015, Foundations of Differential Dataflow. in A Pitts (ed.), Foundations of Software Science and Computation Structures: 18th 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. Lecture Notes in Computer Science, vol. 9034, Springer, pp. 71-83. https://doi.org/10.1007/978-3-662-46678-0_5

Foundations of Differential Dataflow. / Abadi, Martín; McSherry, Frank; Plotkin, Gordon.
Foundations of Software Science and Computation Structures: 18th 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. ed. / Andrew Pitts. Springer, 2015. p. 71-83 (Lecture Notes in Computer Science; Vol. 9034).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Foundations of Differential Dataflow

AU - Abadi, Martín

AU - McSherry, Frank

AU - Plotkin, Gordon

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-662-46678-0_5

DO - 10.1007/978-3-662-46678-0_5

M3 - Conference contribution

SN - 978-3-662-46677-3

T3 - Lecture Notes in Computer Science

SP - 71

EP - 83

BT - Foundations of Software Science and Computation Structures

A2 - Pitts, Andrew

PB - Springer

ER -

Abadi M, McSherry F, Plotkin G. Foundations of Differential Dataflow. In Pitts A, editor, Foundations of Software Science and Computation Structures: 18th 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. Springer. 2015. p. 71-83. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-46678-0_5

Foundations of Differential Dataflow

Abstract

Publication series

Access to Document

Fingerprint

Cite this