Conference item
Fixing incremental computation: derivatives of fixpoints, and the recursive semantics of datalog
- Abstract:
- Incremental computation has recently been studied using the concepts of change structures and derivatives of programs, where the derivative of a function allows updating the output of the function based on a change to its input. We generalise change structures to change actions, and study their algebraic properties. We develop change actions for common structures in computer science, including directed-complete partial orders and Boolean algebras. We then show how to compute derivatives of fixpoints. This allows us to perform incremental evaluation and maintenance of recursively defined functions with particular application generalised Datalog programs. Moreover, unlike previous results, our techniques are modular in that they are easy to apply both to variants of Datalog and to other programming languages.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 490.1KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-030-17184-1_19
Authors
- Publisher:
- Springer
- Host title:
- European Symposium on Programming
- Journal:
- Lecture Notes in Computer Science More from this journal
- Volume:
- 11432
- Pages:
- 525-552
- Series:
- Lecture Notes in Computer Science
- Publication date:
- 2019-04-06
- Acceptance date:
- 2019-02-18
- DOI:
- Keywords:
- Pubs id:
-
pubs:974362
- UUID:
-
uuid:2afcaaba-3729-4905-b0fe-8b7f73f6fb33
- Local pid:
-
pubs:974362
- Source identifiers:
-
974362
- Deposit date:
-
2019-02-18
- ARK identifier:
Terms of use
- Copyright holder:
- Alvarez-Picallo et al
- Copyright date:
- 2019
- Notes:
-
© The Author(s) 2019. This is a conference paper which has been presented at the 22nd the 28th European Symposium on Programming (ESOP), 08-11 April 2019, Prague, Czech Republic.
Open Access
This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record