×

Session-typed concurrent contracts. (English) Zbl 1487.68165

The paper discusses the problem of checking that a subsystem of a concurrent system of a certain kind meets its specification. It is assumed that the subsystem and its user communicate via a bidirectional channel. A “monitor” process is put in between the subsystem and the user so that messages between the two go through the monitor, which can thus inspect them and raise an alarm if a message arrives at a wrong time or has wrong content.
The monitor should not affect the behaviour of the system other than raising an alarm. A major part of the paper is devoted to how this can be checked. Another main topic is showing that whatever can be checked with subtypes, can be checked with monitors.
The paper is more about verification using functional programming type theory than about concurrency. The concurrency model seems restrictive, and the paper says that deadlock freedom is not covered.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68N18 Functional programming and lambda calculus
68Q60 Specification and verification (program logics, model checking, etc.)

Software:

TreatJS

References:

[1] Jia, L.; Gommerstadt, H.; Pfenning, F., Monitors and blame assignment for higher-order session types, (Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’16 (2016)), 582-594 · Zbl 1347.68269
[2] Melgratti, H.; Padovani, L., Chaperone contracts for higher-order sessions, Proc. ACM Program. Lang., 1, ICFP, 35:1-35:29 (2017)
[3] Gommerstadt, H.; Jia, L.; Pfenning, F., Session-typed concurrent contracts, (27th European Symposium on Programming, ESOP 2018, Proceedings (2018)), 771-798 · Zbl 1418.68025
[4] Pfenning, F.; Griffith, D., Polarized substructural session types, (18th International Conference on Foundations of Software Science and Computation Structures. 18th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2015 (2015)), invited talk · Zbl 1459.68042
[5] Thiemann, P.; Vasconcelos, V. T., Context-free session types, (Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming. Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, ICFP 2016 (2016)), 462-475 · Zbl 1361.68052
[6] Wasserman, H.; Blum, M., Software reliability via run-time result-checking, J. ACM, 44, 6, 826-849 (1997) · Zbl 0904.68064
[7] Caires, L.; Pfenning, F., Session types as intuitionistic linear propositions, (21st International Conference on Concurrency Theory. 21st International Conference on Concurrency Theory, CONCUR 2010 (2010)) · Zbl 1287.68125
[8] Toninho, B., A logical foundation for session-based concurrent computation (2015), Carnegie Mellon University and New University of Lisbon, Ph.D. thesis
[9] Caires, L.; Pfenning, F.; Toninho, B., Linear logic propositions as session types, Math. Struct. Comput. Sci., 26, 3, 367-423 (2016), Special Issue on Behavioural Types · Zbl 1361.68162
[10] Cervesato, I.; Scedrov, A., Relating state-based and process-based concurrency through linear logic, Inf. Comput., 207, 10, 1044-1077 (2009) · Zbl 1181.68168
[11] Honda, K., Types for dyadic interaction, (4th International Conference on Concurrency Theory. 4th International Conference on Concurrency Theory, CONCUR 1993 (1993)) · Zbl 0939.68642
[12] Gay, S. J.; Hole, M., Subtyping for session types in the π-calculus, Acta Inform., 42, 2-3, 191-225 (2005) · Zbl 1079.68065
[13] Balzer, S.; Pfenning, F., Manifest sharing with session types, Proc. ACM Program. Lang., 1, ICFP, 37:1-37:29 (2017)
[14] Toninho, B.; Caires, L.; Pfenning, F., Higher-order processes, functions, and sessions: a monadic integration, (22nd European Symposium on Programming. 22nd European Symposium on Programming, ESOP 2013 (2013)) · Zbl 1381.68063
[15] Wadler, P.; Findler, R. B., Well-typed programs can’t be blamed, (18th European Symposium on Programming Languages and Systems. 18th European Symposium on Programming Languages and Systems, ESOP 2009 (2009)) · Zbl 1234.68063
[16] Dimoulas, C.; Findler, R. B.; Flanagan, C.; Felleisen, M., Correct blame for contracts: no more scapegoating, (Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’11 (2011)), 215-226 · Zbl 1284.68176
[17] Findler, R. B.; Felleisen, M., Contracts for higher-order functions, (Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming. Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming, ICFP ’02 (2002)), 48-59 · Zbl 1322.68039
[18] Dimoulas, C.; Hochstadt, S. T.; Felleisen, M., Complete monitors for behavioral contracts, (21st European Conference on Programming Languages and Systems. 21st European Conference on Programming Languages and Systems, ESOP 2012 (2012)) · Zbl 1352.68031
[19] Dimoulas, C.; Felleisen, M., On contract satisfaction in a higher-order world, ACM Trans. Program. Lang. Syst., 33, 5, 1-29 (2011)
[20] Wadler, P., A complement to blame, (1st Summit on Advances in Programming Languages. 1st Summit on Advances in Programming Languages, SNAPL 2015 (2015))
[21] Keil, M.; Thiemann, P., Blame assignment for higher-order contracts with intersection and union, (20th ACM SIGPLAN International Conference on Functional Programming. 20th ACM SIGPLAN International Conference on Functional Programming, ICFP 2015 (2015)) · Zbl 1360.68365
[22] Ahmed, A.; Findler, R. B.; Siek, J. G.; Wadler, P., Blame for all, (38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011 (2011)) · Zbl 1284.68156
[23] Dimoulas, C.; Pucella, R.; Felleisen, M., Future contracts, (Proceedings of the 11th ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. Proceedings of the 11th ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, PPDP ’09 (2009)), 195-206
[24] Swords, C.; Sabry, A.; Sam, T.-H., An extended account of contract monitoring strategies as patterns of communication, J. Funct. Program., 28, e4 (2018) · Zbl 1476.68055
[25] Disney, T.; Flanagan, C.; McCarthy, J., Temporal higher-order contracts, (16th ACM SIGPLAN International Conference on Functional Programming. 16th ACM SIGPLAN International Conference on Functional Programming, ICFP 2011 (2011)) · Zbl 1323.68068
[26] Bocchi, L.; Chen, T.-C.; Demangeon, R.; Honda, K.; Yoshida, N., Monitoring networks through multiparty session types, (Formal Techniques for Distributed Systems. Formal Techniques for Distributed Systems, FMOODS 2013 (2013))
[27] Chen, T.-C.; Bocchi, L.; Deniélou, P.-M.; Honda, K.; Yoshida, N., Asynchronous distributed monitoring for multiparty session enforcement, (6th International Symposium on Trustworthy Global Computing. 6th International Symposium on Trustworthy Global Computing, TGC 2011 (2012)), 25-45
[28] Bocchi, L.; Honda, K.; Tuosto, E.; Yoshida, N., A theory of design-by-contract for distributed multiparty interactions, (Proceedings of the 21st International Conference on Concurrency Theory. Proceedings of the 21st International Conference on Concurrency Theory, CONCUR 2010. Proceedings of the 21st International Conference on Concurrency Theory. Proceedings of the 21st International Conference on Concurrency Theory, CONCUR 2010, LNCS, vol. 6269 (2010), Springer), 162-176 · Zbl 1287.68121
[29] Waye, L.; Chong, S.; Dimoulas, C., Whip: higher-order contracts for modern services, Proc. ACM Program. Lang., 1, ICFP, 36:1-36:28 (2017)
[30] Thiemann, P., Session types with gradual typing, (9th International Symposium on Trustworthy Global Computing. 9th International Symposium on Trustworthy Global Computing, TGC 2014 (2014)) · Zbl 1444.68123
[31] Igarashi, A.; Thiemann, P.; Vasconcelos, V. T.; Wadler, P., Gradual session types, Proc. ACM Program. Lang., 1, ICFP, 38:1-38:28 (2017)
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.