\( \pi\) with leftovers: a mechanisation in Agda. (English) Zbl 1490.68143
Peters, Kirstin (ed.) et al., Formal techniques for distributed objects, components, and systems. 41st IFIP WG 6.1 international conference, FORTE 2021, held as part of the 16th international federated conference on distributed computing techniques, DisCoTec 2021, Valletta, Malta, June 14–18, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12719, 157-174 (2021).
Summary: Linear type systems need to keep track of how programs use their resources. The standard approach is to use context splits specifying how resources are (disjointly) split across subterms. In this approach, context splits redundantly echo information which is already present within subterms. An alternative approach is to use leftover typing
[G. Allais, “Typing with leftovers – a mechanization of intuitionistic multiplicative-additive linear logic”, LIPIcs – Leibniz Int. Proc. Inform. 104, Article No. 1, 22 p. (2018; doi:10.4230/LIPIcs.TYPES.2017.1);
I. Mackie, J. Funct. Program. 4, No. 4, 395–433 (1994; Zbl 0817.68042)],
where in addition to the usual (input) usage context, typing judgments have also an output usage context: the leftovers. In this approach, the leftovers of one typing derivation are fed as input to the next, threading through linear resources while avoiding context splits. We use leftover typing to define a type system for a resource-aware \(\pi \)-calculus
[R. Milner, Communicating and mobile systems: the \(\pi\)-calculus. Cambridge: Cambridge University Press (1999; Zbl 0942.68002);
R. Milner et al., Inf. Comput. 100, No. 1, 1–40 (1992; Zbl 0752.68036);
Inf. Comput. 100, No. 1, 41–77 (1992; Zbl 0752.68037)],
a process algebra used to model concurrent systems. Our type system is parametrised over a set of usage algebras
[R. Jung et al., in: Proceedings of the 42nd ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL’15. New York, NY: Association for Computing Machinery (ACM). 637–650 (2015; Zbl 1346.68135);
A. J. Turon et al., in: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL’13. New York, NY: Association for Computing Machinery (ACM). 343–356 (2013; Zbl 1301.68181)]
that are general enough to encompass shared types (free to reuse and discard), graded types (use exactly \(n\) number of times) and linear types (use exactly once). Linear types are important in the \(\pi \)-calculus: they ensure privacy and safety of communication and avoid race conditions, while graded and shared types allow for more flexible programming. We provide a framing theorem for our type system, generalise the weakening and strengthening theorems to include linear types, and prove subject reduction. Our formalisation is fully mechanised in about 1850 lines of Agda.
For the entire collection see [Zbl 1482.68037].
For the entire collection see [Zbl 1482.68037].
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
| 03B70 | Logic in computer science |
| 68N30 | Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) |
| 68Q60 | Specification and verification (program logics, model checking, etc.) |
| 68V20 | Formalization of mathematics in connection with theorem provers |
Citations:
Zbl 0817.68042; Zbl 0942.68002; Zbl 0752.68036; Zbl 0752.68037; Zbl 1346.68135; Zbl 1301.68181References:
| [1] | Affeldt, R.; Kobayashi, N., A Coq Library for Verification of Concurrent Programs, Electron. Notes Theor. Comput. Sci., 199, 17-32 (2008) · Zbl 1278.68152 · doi:10.1016/j.entcs.2007.11.010 |
| [2] | Allais, G.: Typing with leftovers - a mechanization of intuitionistic multiplicative-additive linear logic. In: Types for Proofs and Programs, TYPES. LIPIcs, vol. 104, pp. 1:1-1:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017). doi:10.4230/LIPIcs.TYPES.2017.1 · Zbl 1528.03242 |
| [3] | Atkey, R.: Syntax and semantics of quantitative type theory. In: Logic in Computer Science, LICS, pp. 56-65. ACM (2018). doi:10.1145/3209108.3209189 · Zbl 1452.03029 |
| [4] | Barendsen, E.; Smetsers, S., Uniqueness typing for functional languages with graph rewriting semantics, Math. Struct. Comput. Sci., 6, 6, 579-612 (1996) · Zbl 0863.68081 · doi:10.1017/S0960129500070109 |
| [5] | Bengtson, J.: The pi-calculus in nominal logic, vol. 2012 (2012). https://www.isa-afp.org/entries/Pi_Calculus.shtml · Zbl 1168.68436 |
| [6] | Castro, D.; Ferreira, F.; Yoshida, N., EMTST: engineering the meta-theory of session types, Tools and Algorithms for the Construction and Analysis of Systems, 278-285 (2020), Cham: Springer, Cham · doi:10.1007/978-3-030-45237-7_17 |
| [7] | Cervesato, I., Pfenning, F.: A linear logical framework. In: Logic in Computer Science, LICS, pp. 264-275. IEEE Computer Society (1996). doi:10.1109/LICS.1996.561339 · Zbl 1031.03056 |
| [8] | Ciccone, L., Padovani, L.: A dependently typed linear \(\pi \)-calculus in Agda. In: PPDP 2020: 22nd International Symposium on Principles and Practice of Declarative Programming, pp. 8:1-8:14. ACM (2020). doi:10.1145/3414080.3414109 |
| [9] | Dardha, O.: Recursive session types revisited. In: Carbone, M. (ed.) Workshop on Behavioural Types, BEAT. EPTCS, vol. 162, pp. 27-34 (2014). doi:10.4204/EPTCS.162.4 |
| [10] | Dardha, O.; Giachino, E.; Sangiorgi, D., Session types revisited, Inf. Comput., 256, 253-286 (2017) · Zbl 1376.68099 · doi:10.1016/j.ic.2017.06.002 |
| [11] | de Bruijn, N.G.: Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. In: Indagationes Mathematicae (Proceedings), vol. 75, pp. 381-392. Elsevier (1972) · Zbl 0253.68007 |
| [12] | Deransart, P., Smaus, J.: Subject reduction of logic programs as proof-theoretic property, vol. 2002 (2002). http://danae.uni-muenster.de/lehre/kuchen/JFLP/articles/2002/S02-01/JFLP-A02-02.pdf · Zbl 1037.68029 |
| [13] | Despeyroux, J.; van Leeuwen, J.; Watanabe, O.; Hagiya, M.; Mosses, PD; Ito, T., A higher-order specification of the \(\pi \)-Calculus, Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics, 425-439 (2000), Heidelberg: Springer, Heidelberg · Zbl 0998.68538 · doi:10.1007/3-540-44929-9_30 |
| [14] | Dybjer, P., Inductive families, Formal Asp. Comput., 6, 4, 440-465 (1994) · Zbl 0808.03044 · doi:10.1007/BF01211308 |
| [15] | Gay, SJ; Boulton, RJ; Jackson, PB, A framework for the formalisation of pi calculus type systems in Isabelle/HOL, Theorem Proving in Higher Order Logics, 217-232 (2001), Heidelberg: Springer, Heidelberg · Zbl 1005.68531 · doi:10.1007/3-540-44755-5_16 |
| [16] | Gay, SJ; Vasconcelos, VT, Linear type theory for asynchronous session types, J. Funct. Program., 20, 1, 19-50 (2010) · Zbl 1185.68194 · doi:10.1017/S0956796809990268 |
| [17] | Georges, AL; Murawska, A.; Otis, S.; Pientka, B.; Yang, H., LINCX: a linear logical framework with first-class contexts, Programming Languages and Systems, 530-555 (2017), Heidelberg: Springer, Heidelberg · Zbl 1485.68065 · doi:10.1007/978-3-662-54434-1_20 |
| [18] | Goto, MA; Jagadeesan, R.; Jeffrey, A.; Pitcher, C.; Riely, J., An extensible approach to session polymorphism, Math. Struct. Comput. Sci., 26, 3, 465-509 (2016) · Zbl 1361.68168 · doi:10.1017/S0960129514000231 |
| [19] | Honsell, F.; Miculan, M.; Scagnetto, I., pi-calculus in (Co)inductive-type theory, Theor. Comput. Sci., 253, 2, 239-285 (2001) · Zbl 0956.68095 · doi:10.1016/S0304-3975(00)00095-5 |
| [20] | Jung, R., et al.: Iris: monoids and invariants as an orthogonal basis for concurrent reasoning. In: Rajamani, S.K., Walker, D. (eds.) Symposium on Principles of Programming Languages, POPL 2015, pp. 637-650. ACM (2015). doi:10.1145/2676726.2676980 · Zbl 1346.68135 |
| [21] | Kobayashi, N.: Type systems for concurrent programs (2007). http://www.kb.ecei.tohoku.ac.jp/ koba/papers/tutorial-type-extended.pdf · Zbl 1274.68076 |
| [22] | Kobayashi, N., Pierce, B.C., Turner, D.N.: Linearity and the Pi-Calculus. In: Symposium on Principles of Programming Languages, POPL, pp. 358-371. ACM Press (1996). doi:10.1145/237721.237804 |
| [23] | Mackie, I., Lilac: a functional programming language based on linear logic, J. Funct. Program., 4, 4, 395-433 (1994) · Zbl 0817.68042 · doi:10.1017/S0956796800001131 |
| [24] | Matsakis, N.D., II, F.S.K.: The rust language. In: High Integrity Language Technology, HILT, pp. 103-104. ACM (2014). doi:10.1145/2663171.2663188 |
| [25] | McBride, C.; Lindley, S.; McBride, C.; Trinder, P.; Sannella, D., I got plenty o’ Nuttin’, A List of Successes That Can Change the World, 207-233 (2016), Cham: Springer, Cham · Zbl 1343.68060 · doi:10.1007/978-3-319-30936-1_12 |
| [26] | Milner, R., Communicating and Mobile Systems - The Pi-calculus (1999), Cambridge: Cambridge University Press, Cambridge · Zbl 0942.68002 |
| [27] | Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, Parts I and II, Inf. Comput., 100, 1, 1-40 (1992) · Zbl 0752.68036 · doi:10.1016/0890-5401(92)90008-4 |
| [28] | Orchard, D., Liepelt, V., III, H.E.: Quantitative program reasoning with graded modal types. Proc. ACM Program. Lang. 3(ICFP), 110:1-110:30 (2019). doi:10.1145/3341714 |
| [29] | Orchard, D.A., Yoshida, N.: Using session types as an effect system. In: Gay, S., Alglave, J. (eds.) Programming Language Approaches to Concurrency- and Communication-cEntric Software, PLACES 2015. EPTCS, vol. 203, pp. 1-13 (2015). doi:10.4204/EPTCS.203.1 |
| [30] | Rouvoet, A., Poulsen, C.B., Krebbers, R., Visser, E.: Intrinsically-typed definitional interpreters for linear, session-typed languages. In: Certified Programs and Proofs, CPP, pp. 284-298. ACM (2020). doi:10.1145/3372885.3373818 |
| [31] | Sangiorgi, D.; Walker, D., The Pi-Calculus - A Theory of Mobile Processes (2001), Cambridge: Cambridge University Press, Cambridge · Zbl 0981.68116 |
| [32] | Scalas, A., Dardha, O., Hu, R., Yoshida, N.: A linear decomposition of multiparty sessions for safe distributed programming. In: European Conference on Object-Oriented Programming, ECOOP. LIPIcs, vol. 74, pp. 24:1-24:31. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017). doi:10.4230/LIPIcs.ECOOP.2017.24 |
| [33] | Thiemann, P.: Intrinsically-typed mechanized semantics for session types, pp. 19:1-19:15 (2019). doi:10.1145/3354166.3354184 |
| [34] | Turon, A.J., Thamsborg, J., Ahmed, A., Birkedal, L., Dreyer, D.: Logical relations for fine-grained concurrency. In: Giacobazzi, R., Cousot, R. (eds.) Symposium on Principles of Programming Languages, POPL 2013, pp. 343-356. ACM (2013). doi:10.1145/2429069.2429111 · Zbl 1301.68181 |
| [35] | Wadler, P.: Linear types can change the world! In: Programming Concepts and Methods, p. 561. North-Holland (1990) |
| [36] | Zalakain, U., Dardha, O.: \( \pi\) with leftovers: a mechanisation in Agda. CoRR abs/2005.05902 (2020). https://arxiv.org/abs/2005.05902 |
| [37] | Zalakain, U., Dardha, O.: Typing the linear \(\pi \)-Calculus – formalisation in Agda (2021). https://github.com/umazalakain/typing-linear-pi |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
