Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-08T04:26:12.705Z Has data issue: false hasContentIssue false
  • English
  • Français

Proof-relevant π-calculus: a constructive account of concurrency and causality

Published online by Cambridge University Press:  04 May 2017

ROLY PERERA  and
JAMES CHENEY
ROLY PERERA
Affiliation:
School of Computing Science, University of Glasgow, Glasgow, U.K. Email: [email protected] School of Informatics, University of Edinburgh, Edinburgh, [email protected]
JAMES CHENEY
Affiliation:
School of Informatics, University of Edinburgh, Edinburgh, [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We present a formalisation in Agda of the theory of concurrent transitions, residuation and causal equivalence of traces for the π-calculus. Our formalisation employs de Bruijn indices and dependently typed syntax, and aligns the ‘proved transitions’ proposed by Boudol and Castellani in the context of CCS with the proof terms naturally present in Agda's representation of the labelled transition relation. Our main contributions are proofs of the ‘diamond lemma’ for the residuals of concurrent transitions and a formal definition of equivalence of traces up to permutation of transitions.

In the π-calculus, transitions represent propagating binders whenever their actions involve bound names. To accommodate these cases, we require a more general diamond lemma where the target states of equivalent traces are no longer identical, but are related by a braiding that rewires the bound and free names to reflect the particular interleaving of events involving binders. Our approach may be useful for modelling concurrency in other languages where transitions carry meta-data sensitive to particular interleavings, such as dynamically allocated memory addresses.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 28 , Special Issue 9: Logical Frameworks and Meta-Languages 2015 , October 2018 , pp. 1541 - 1577
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Accattoli, B. (2012). Proof pearl: Abella formalization of λ-calculus cube property. In: Hawblitzel, C. and Miller, D. (eds.) Certified Programs and Proofs, Lecture Notes in Computer Science, vol. 7679, Springer, Berlin, Heidelberg, 173–187.Google Scholar
Affeldt, R. and Kobayashi, N. (2008). A Coq library for verification of concurrent programs. Electronic Notes in Theoretical Computer Science 199 17–32.Google Scholar
Aït Mohamed, O. (1995). Mechanizing a pi-calculus equivalence in HOL. In: Proceedings of the 8th International Workshop on Higher Order Logic Theorem Proving and Its Applications, London, UK, Springer-Verlag, 1–16.Google Scholar
Angiuli, C., Morehouse, E., Licata, D.R. and Harper, R. (2014). Homotopical patch theory. In Proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming, ICFP '14, New York, NY, USA: ACM, 243–256.Google Scholar
Baelde, D., Chaudhuri, K., Gacek, A., Miller, D., Nadathur, G., Tiu, A. and Wang, Y. (2014). Abella: A system for reasoning about relational specifications. Journal of Formalized Reasoning 7 (2) 1–89.Google Scholar
Bengtson, J. and Parrow, J. (2009). Formalising the pi-calculus using nominal logic. Logical Methods in Computer Science 5 (2:16).Google Scholar
Boreale, M. and Sangiorgi, D. (1998). A fully abstract semantics for causality in the π-calculus. Acta Informatica 35 (5) 353–400.Google Scholar
Boudol, G. and Castellani, I. (1989). Permutation of transitions: An event structure semantics for CCS and SCCS. In: Bakker, J., Roever, W.-P. and Rozenberg, G. (eds.) Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, Lecture Notes in Computer Science, vol. 354, Springer, 411–427.Google Scholar
Boudol, G. and Castellani, I. (1991). Flow models of distributed computations: Three equivalent semantics for CCS. Information and Computation 114 247–312.Google Scholar
Bucalo, A., Honsell, F., Miculan, M., Scagnetto, I. and Hofmann, M. (2006). Consistency of the theory of contexts. Journal of Functional Programming 16 (3) 327–372.Google Scholar
Carbone, M. and Maffeis, S. (2003). On the expressive power of polyadic synchronisation in π-calculus. Nordic Journal of Computing 10 (2) 70–98.Google Scholar
Cervesato, I., Pfenning, F., Walker, D. and Watkins, K. (2002). A concurrent logical framework ii: Examples and applications. Technical Report CMU-CS-02-102, Carnegie Mellon University.Google Scholar
Cristescu, I., Krivine, J. and Varacca, D. (2013). A compositional semantics for the reversible pi-calculus. In: LICS 388–397.Google Scholar
Cristescu, I.D., Krivine, J. and Varacca, D. (2015). Rigid families for CCS and the π-calculus. In: Theoretical Aspects of Computing - ICTAC 2015: 12th International Colloquium, Cali, Colombia, October 29-31, 2015, Proceedings, Springer International Publishing, 223–240.Google Scholar
Curry, H.B. and Feys, R. (1958). Combinatory Logic, Studies in Logic and the Foundations of Mathematics, vol. 1, North-Holland, Amsterdam, Holland.Google Scholar
Danos, V. and Krivine, J. (2004). Reversible communicating systems. In: Gardner, P. and Yoshida, N. (eds.) Concurrency Theory, 15th International Conference, CONCUR '04, Lecture Notes in Computer Science, vol. 3170, Springer, 292–307.Google Scholar
de Bruijn, N. (1972). Lambda-calculus notation with nameless dummies: A tool for automatic formula manipulation with application to the Church-Rosser theorem. Indagationes Mathematicae 34 (5) 381–392.Google Scholar
Degano, P. and Priami, C. (1999). Non-interleaving semantics for mobile processes. Theoretical Computer Science 216 (1–2) 237–270.Google Scholar
Despeyroux, J. (2000). A higher-order specification of the pi-calculus. In: IFIP TCS, Lecture Notes in Computer Science, vol. 1872, London, UK: Springer-Verlag, 425–439.Google Scholar
Fournet, C. and Gonthier, G. (2002). The join calculus: A language for distributed mobile programming. In: Applied Semantics: Advanced Lectures, Lecture Notes in Computer Science, vol. 2395/2002, Berlin/Heidelberg: Springer, 268–332.Google Scholar
Gabbay, M.J. (2003). The pi-calculus in FM. In: Kamareddine, F. (ed.) Thirty-Five Years of Automating Mathematics, Kluwer Applied Logic Series, vol. 28, Kluwer, 247–269.Google Scholar
Gabbay, M.J. and Pitts, A.M. (2002). A new approach to abstract syntax with variable binding. Formal Aspects of Computing 13 341–363.Google Scholar
Gay, S.J. (2001). A framework for the formalisation of pi calculus type systems in Isabelle/HOL. In: TPHOLs, London, UK: Springer-Verlag, 217–232.Google Scholar
Gordon, A.D. and Jeffrey, A. (2003). Typing correspondence assertions for communication protocols. Theoretical Computer Science 300 (1–3) 379–409.Google Scholar
Hirschkoff, D. (1997a). A full formalisation of pi-calculus theory in the calculus of constructions. In: TPHOLs 153–169.Google Scholar
Hirschkoff, D. (1997b). Handling substitutions explicitly in the pi-calculus. In: Proceedings of the Second International Workshop on Explicit Substitutions: Theory and Applications to Programs and Proofs, 28–43.Google Scholar
Honsell, F., Miculan, M. and Scagnetto, I. (2001). π-calculus in (co)inductive-type theory. Theoretical Computer Science 253 (2) 239–285.Google Scholar
Huet, G.P. (1994). Residual theory in λ-calculus: A formal development. Journal of Functional Programming 4 (3) 371–394.Google Scholar
Lanese, I., Mezzina, C.A. and Stefani, J.-B. (2010). Reversing higher-order pi. In Concurrency Theory, 21st International Conference, CONCUR '10, Springer-Verlag 478–493.Google Scholar
Lévy, J.-J. (1980). Optimal reductions in the lambda-calculus. In: Seldin, J.P. and Hindley, J.R. (eds.) To H. B. Curry: Essays in Combinatory Logic, Lambda Calculus and Formalism, Academic Press, New York, NY, USA 159–191.Google Scholar
Mazurkiewicz, A. (1987). Trace theory. In: Advances in Petri Nets 1986, Part II on Petri Nets: Applications and Relationships to Other Models of Concurrency, Lecture Notes in Computer Science, vol. 255, New York, NY, USA: Springer-Verlag 279–324.Google Scholar
Melham, T.F. (1994). A mechanized theory of the π-calculus in HOL. Nordic Journal of Computing 1 (1) 50–76.Google Scholar
Milner, R. (1980). A Calculus of Communicating Systems, Lecture Notes in Computer Science, vol. 92, Springer-Verlag.Google Scholar
Milner, R. (1999). Communicating and Mobile Systems: The π Calculus, Cambridge University Press, Cambridge, UK.Google Scholar
Milner, R., Parrow, J. and Walker, D. (1992). A calculus of mobile processes, I and II. Information and Computation 100 (1) 1–77.Google Scholar
Norell, U. (2009). Dependently typed programming in Agda. In: Advanced Functional Programming, Lecture Notes in Computer Science, vol. 5832, Springer 230–266.Google Scholar
Orchard, D.A. and Yoshida, N. (2015). Using session types as an effect system. In: Proceedings 8th International Workshop on Programming Language Approaches to Concurrency- and Communication-cEntric Software, PLACES 2015, London, UK, 18th April 2015 1–13.Google Scholar
Perera, R. and Cheney, J. (2015). Proof-relevant pi-calculus. In: Cervesato, I. and Chaudhuri, K. (eds.), Proceedings 10th International Workshop on Logical Frameworks and Meta Languages: Theory and Practice (LFMTP '15), Electronic Proceedings in Theoretical Computer Science, vol. 185, Open Publishing Association, 46–70.Google Scholar
Perera, R., Garg, D. and Cheney, J. (2016). Causally consistent dynamic slicing. In Desharnais, J. and Jagadeesan, R. (eds.), Concurrency Theory, 27th International Conference, CONCUR '16, Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.Google Scholar
Philippou, A. and Walker, D. (1997). On confluence in the pi-calculus. In: Proceedings of the 24th International Colloquium on Automata, Languages and Programming, ICALP '97, London, UK, Springer-Verlag, 314–324.Google Scholar
Röckl, C. (2001). A first-order syntax for the pi-calculus in Isabelle/HOL using permutations. Electronic Notes in Theoretical Computer Science 58 (1) 1–17.Google Scholar
Röckl, C. and Hirschkoff, D. (2003). A fully adequate shallow embedding of the π-calculus in Isabelle/HOL with mechanized syntax analysis. Journal of Functional Programming 13 (2) 415–451.Google Scholar
Röckl, C., Hirschkoff, D. and Berghofer, S. (2001). Higher-order abstract syntax with induction in Isabelle/HOL: Formalizing the pi-calculus and mechanizing the theory of contexts. In: FOSSACS, FoSSaCS '01, London, UK: Springer-Verlag 364–378.Google Scholar
Sangiorgi, D. and Walker, D. (2001). The Pi-Calculus - A Theory of Mobile Processes, Cambridge University Press.Google Scholar
Stark, E.W. (1989). Concurrent transition systems. Theoretical Computer Science, 64 (3) 221–269.Google Scholar
Tiu, A. and Miller, D. (2010). Proof search specifications of bisimulation and modal logics for the π-calculus. ACM Transactions on Computational Logic 11 (2) 13:1–13:35.Google Scholar
The Univalent Foundations Program (2013). Homotopy Type Theory: Univalent Foundations of Mathematics. http://homotopytypetheory.org/book, Institute for Advanced Study.Google Scholar
Urban, C. (2008). Nominal techniques in Isabelle/HOL. Journal of Automated Reasoning 40 (4) 327–356.Google Scholar
Watkins, K., Cervesato, I., Pfenning, F. and Walker, D. (2008). Specifying properties of concurrent computations in CLF. Electronic Notes in Theoretical Computer Science 199 67–87.Google Scholar