A sound algorithm for asynchronous session subtyping and its implementation
Session types, types for structuring communication between endpoints in concurrent systems, are recently being integrated into mainstream programming languages. In practice, a very important notion for dealing with such types is that of subtyping, since it allows for typing larger classes of systems...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
EPI Sciences
2021
|
| _version_ | 1826311916676448256 |
|---|---|
| author | Bravetti, M Carbone, M Lange, J Yoshida, N Zavattaro, G |
| author_facet | Bravetti, M Carbone, M Lange, J Yoshida, N Zavattaro, G |
| author_sort | Bravetti, M |
| collection | OXFORD |
| description | Session types, types for structuring communication between endpoints in concurrent systems, are recently being integrated into mainstream programming languages. In practice, a very important notion for dealing with such types is that of subtyping, since it allows for typing larger classes of systems, where a program has not precisely the expected behavior but a similar one. Unfortunately, recent work has shown that subtyping for session types in an asynchronous setting is undecidable. To cope with this negative result, the only approaches we are aware of either restrict the syntax of session types or limit communication (by considering forms of bounded asynchrony). Both approaches are too restrictive in practice, hence we proceed differently by presenting an algorithm for checking subtyping which is sound, but not complete (in some cases it terminates without returning a decisive verdict). The algorithm is based on a tree representation of the coinductive definition of asynchronous subtyping; this tree could be infinite, and the algorithm checks for the presence of finite witnesses of infinite successful subtrees. Furthermore, we provide a tool that implements our algorithm. We use this tool to test our algorithm on many examples that cannot be managed with the previous approaches, and to provide an empirical evaluation of the time and space cost of the algorithm. |
| first_indexed | 2024-03-07T08:19:50Z |
| format | Journal article |
| id | oxford-uuid:353c5e11-4a73-4eb6-a825-30600bfaa703 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:19:50Z |
| publishDate | 2021 |
| publisher | EPI Sciences |
| record_format | dspace |
| spelling | oxford-uuid:353c5e11-4a73-4eb6-a825-30600bfaa7032024-01-24T16:01:32ZA sound algorithm for asynchronous session subtyping and its implementationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:353c5e11-4a73-4eb6-a825-30600bfaa703EnglishSymplectic ElementsEPI Sciences2021Bravetti, MCarbone, MLange, JYoshida, NZavattaro, GSession types, types for structuring communication between endpoints in concurrent systems, are recently being integrated into mainstream programming languages. In practice, a very important notion for dealing with such types is that of subtyping, since it allows for typing larger classes of systems, where a program has not precisely the expected behavior but a similar one. Unfortunately, recent work has shown that subtyping for session types in an asynchronous setting is undecidable. To cope with this negative result, the only approaches we are aware of either restrict the syntax of session types or limit communication (by considering forms of bounded asynchrony). Both approaches are too restrictive in practice, hence we proceed differently by presenting an algorithm for checking subtyping which is sound, but not complete (in some cases it terminates without returning a decisive verdict). The algorithm is based on a tree representation of the coinductive definition of asynchronous subtyping; this tree could be infinite, and the algorithm checks for the presence of finite witnesses of infinite successful subtrees. Furthermore, we provide a tool that implements our algorithm. We use this tool to test our algorithm on many examples that cannot be managed with the previous approaches, and to provide an empirical evaluation of the time and space cost of the algorithm. |
| spellingShingle | Bravetti, M Carbone, M Lange, J Yoshida, N Zavattaro, G A sound algorithm for asynchronous session subtyping and its implementation |
| title | A sound algorithm for asynchronous session subtyping and its implementation |
| title_full | A sound algorithm for asynchronous session subtyping and its implementation |
| title_fullStr | A sound algorithm for asynchronous session subtyping and its implementation |
| title_full_unstemmed | A sound algorithm for asynchronous session subtyping and its implementation |
| title_short | A sound algorithm for asynchronous session subtyping and its implementation |
| title_sort | sound algorithm for asynchronous session subtyping and its implementation |
| work_keys_str_mv | AT bravettim asoundalgorithmforasynchronoussessionsubtypinganditsimplementation AT carbonem asoundalgorithmforasynchronoussessionsubtypinganditsimplementation AT langej asoundalgorithmforasynchronoussessionsubtypinganditsimplementation AT yoshidan asoundalgorithmforasynchronoussessionsubtypinganditsimplementation AT zavattarog asoundalgorithmforasynchronoussessionsubtypinganditsimplementation AT bravettim soundalgorithmforasynchronoussessionsubtypinganditsimplementation AT carbonem soundalgorithmforasynchronoussessionsubtypinganditsimplementation AT langej soundalgorithmforasynchronoussessionsubtypinganditsimplementation AT yoshidan soundalgorithmforasynchronoussessionsubtypinganditsimplementation AT zavattarog soundalgorithmforasynchronoussessionsubtypinganditsimplementation |