License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITP.2023.11
URN: urn:nbn:de:0030-drops-183867
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18386/
Go to the corresponding LIPIcs Volume Portal

Cruz-Filipe, Luís ; Montesi, Fabrizio

Now It Compiles! Certified Automatic Repair of Uncompilable Protocols

pdf-format:
LIPIcs-ITP-2023-11.pdf (0.7 MB)

Abstract

Choreographic programming is a paradigm where developers write the global specification (called choreography) of a communicating system, and then a correct-by-construction distributed implementation is compiled automatically. Unfortunately, it is possible to write choreographies that cannot be compiled, because of issues related to an agreement property known as knowledge of choice. This forces programmers to reason manually about implementation details that may be orthogonal to the protocol that they are writing.
Amendment is an automatic procedure for repairing uncompilable choreographies. We present a formalisation of amendment from the literature, built upon an existing formalisation of choreographic programming. However, in the process of formalising the expected properties of this procedure, we discovered a subtle counterexample that invalidates the original published and peer-reviewed pen-and-paper theory. We discuss how using a theorem prover led us to both finding the issue, and stating and proving a correct formulation of the properties of amendment.

BibTeX - Entry

@InProceedings{cruzfilipe_et_al:LIPIcs.ITP.2023.11,
  author =	{Cruz-Filipe, Lu{\'\i}s and Montesi, Fabrizio},
  title =	{{Now It Compiles! Certified Automatic Repair of Uncompilable Protocols}},
  booktitle =	{14th International Conference on Interactive Theorem Proving (ITP 2023)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-284-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{268},
  editor =	{Naumowicz, Adam and Thiemann, Ren\'{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18386},
  URN =		{urn:nbn:de:0030-drops-183867},
  doi =		{10.4230/LIPIcs.ITP.2023.11},
  annote =	{Keywords: choreographic programming, theorem proving, compilation, program repair}
}

Keywords: choreographic programming, theorem proving, compilation, program repair
Collection: 14th International Conference on Interactive Theorem Proving (ITP 2023)
Issue Date: 2023
Date of publication: 26.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI