The Participants-as-Interfaces (PaI) approach to system composition suggests that participants in a system can be considered interfaces to the outside world. Given a set of systems, one participant per system is chosen to play the role of an interface. When systems are composed, these interface participants are replaced by gateways that communicate with each other by forwarding messages. The PaI approach for systems of asynchronously communicating finite state machines (CFSMs) has been exploited in the literature for binary composition where the forwarding policy is necessarily unique. In this paper we consider the case of multiple system composition and extend preliminary work to the case where interactions among gateways can be mediated by additional orchestrating participants that comply with a given connection model . We represent the interactions among gateways as CFSM systems (called orchestrated connection policies ) and prove that a number of relevant communication properties (e.g. deadlock-freedom, reception-error-freedom) are preserved by orchestrated PaI multicomposition , provided that the orchestrated connection policy used also satisfies the communication property in question.

A multiparty session formalises a set of concurrent communicating participants. The possibility for a participant to delegate some interactions to another participant is crucial for the expressivity of multiparty sessions. We propose the first type system for multiparty sessions with delegation where some communications between participants can be ignored. This allows us to type some sessions with global types representing interesting protocols, which have no type in the standard type systems. Our type system enjoys Subject Reduction, Session Fidelity and partial Lock-freedom. The last property ensures the absence of locks for participants with non-ignored communications. A sound and complete type inference algorithm is also discussed.

A well-formed global type describes the interaction protocol of multiple end-points via the projection to local specifications. Typed sessions of processes enjoy good communication properties and their overall behaviour is the one described by the global type. We show that a projectable global type is bounded (also said “balanced” in the literature) but also that projectability is not necessary for a global type to be a sound description of well-behaved systems. By revising the semantics of global types via a coinductively defined LTS, we obtain a conservative extension of previous type systems in case of simple sessions without channels and local types, which we call Simple MultiParty Sessions, accommodating unbounded and hence un-projectable global types. Such a system is sound and encompasses infinite sessions that do not type-check for any bounded and/or projectable global type.

Modular methodologies for the development and verification of concurrent/distributed systems are increasingly relevant nowadays. We investigate the simultaneous composition of multiple systems in a multiparty-session-type setting, working on suitable notions of interfacing policy and multicompatibility. The resulting method is conservative (it makes only the strictly needed changes), flexible (any system can be looked at as potentially open) and safe (relevant communication properties, e.g. lock-freedom, are preserved by composition). We obtain safety by proving preservation of typability. We also provide a sound and complete type inference algorithm.

We introduce a meta-model based on formal languages, dubbed formal choreographic languages, to study message-passing systems. Our framework allows us to generalise standard constructions from the literature and to compare them. In particular, we consider notions such as global view, local view, and projections from the former to the latter. The correctness of local views projected from global views is characterised in terms of a closure property. We consider a number of communication properties -- such as (dead)lock-freedom -- and give conditions on formal choreographic languages to guarantee them. Finally, we show how formal choreographic languages can capture existing formalisms; specifically we consider communicating finite-state machines, choreography automata, and multiparty session types. Notably, formal choreographic languages, differently from most approaches in the literature, can naturally model systems exhibiting non-regular behaviour.

International audience

invited-talk Two notions of sub-behaviour for session-based client/server systems: 10 Years Later Share on Authors: Franco Barbanera Universita di Catania, Italy Universita di Catania, ItalyView Profile , Ugo de'Liguoro Universita di Torino, Italy Universita di Torino, ItalyView Profile Authors Info & Claims PPDP '20: Proceedings of the 22nd International Symposium on Principles and Practice of Declarative ProgrammingSeptember 2020 Article No.: 2Pages 1–3https://doi.org/10.1145/3414080.3414082Published:08 September 2020 0citation17DownloadsMetricsTotal Citations0Total Downloads17Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We introduce an intersection type system for the lambda-mu calculus that is invariant under subject reduction and expansion. The system is obtained by describing Streicher and Reus's denotational model of continuations in the category of omega-algebraic lattices via Abramsky's domain-logic approach. This provides at the same time an interpretation of the type system and a proof of the completeness of the system with respect to the continuation models by means of a filter model construction. We then define a restriction of our system, such that a lambda-mu term is typeable if and only if it is strongly normalising. We also show that Parigot's typing of lambda-mu terms with classically valid propositional formulas can be translated into the restricted system, which then provides an alternative proof of strong normalisability for the typed lambda-mu calculus.

Abstract In the setting of session behaviours , we study an extension of the concept of compliance when a disciplined form of backtracking and of output skipping is present. After adding checkpoints to the syntax of session behaviours, we formalise the operational semantics via an LTS, and define natural notions of checkpoint compliance and sub-behaviour , which we prove to be both decidable. Then we extend the operational semantics with skips and we show the decidability of the obtained compliance.

We propose a refinement and a simplification of the behavioural semantics of session types, based on the concepts of compliance and sub-behaviour from the theory of web contracts. We introduce three relations on a suitable class of behaviours with higher-order input/output, called ‘session behaviours’. Such relations, depending on each other, represent the idea of sub-behaviour from the point of view of a client, a server or a peer, respectively. A restriction of the intersection of the first two relations characterizes the ‘usual’ sub-behaviour relation from the literature. We then device an algorithmic formal system for three subtyping relations (dubbed CSP-subtyping) for session types that takes into account the role played by a user of a channel during an interaction, so extending Gay and Hole subtyping theory. We show that our session behaviours and sub-behaviour relations provide sound and complete semantics for CSP-subtyping, and for Gay and Hole subtyping as a by-product.

We propose a refinement and a simplification of the behavioural semantics of types, based on the concepts of compliance and sub-behaviour from the theory of web contracts. We introduce two relations, representing the idea of sub-behaviour from the point of view of the client and the server, respectively, and characterize the sub-behaviour relation (from the literature) as the intersection of the other two. We show that a proper subclass of behaviours, called session behaviors, and the sub-behaviour relations model types and subtyping, clarifying the otherwise problematic extension of type subtyping with concepts from the theory of contracts.

In this paper we present the algebraic-λ-cube, an extension of Barendregt's λ-cube with first- and higher-order algebraic rewriting. We show that strong normalization is a modular property of all the systems in the algebraic-λ-cube, provided that the first-order rewrite rules are non-duplicating and the higher-order rules satisfy the general schema of Jouannaud and Okada. We also prove that local confluence is a modular property of all the systems in the algebraic-λ-cube, provided that the higher-order rules do not introduce critical pairs. This property and the strong normalization result imply the modularity of confluence.

Abstract We present a short and direct syntactic proof of the fact that adding the axiom of choice and the principle of excluded-middle to Coquand–Huet's Calculus of Constructions gives proof-irrelevance.

Presents the algebraic-/spl lambda/-cube, an extension of Barendregt's (1991) /spl lambda/-cube with first- and higher-order algebraic rewriting. We show that strong normalization is a modular property of all systems in the algebraic-/spl lambda/-cube, provided that the first-order rewrite rules are non-duplicating and the higher-order rules satisfy the general schema of Jouannaud and Okada (1991). This result is proven for the algebraic extension of the calculus of constructions, which contains all the systems of the algebraic-/spl lambda/-cube. We also prove that local confluence is a modular property of all the systems in the algebraic-/spl lambda/-cube, provided that the higher-order rules do not introduce critical pairs. This property and the strong normalization result imply the modularity of confluence.>

A model is given for the second-order lambda calculus extended with inheritance, bounded quantification, recursive types, constructors and kinds. This language, called mu -FunK, can be viewed as the core of the QUEST language defined by L. Cardelli (SRC Rep. 45, 1989). Types are interpreted as intervals of partial equivalence relations. Because of the properties of intervals and their ordering, all the type constructors are continuous functions. As a consequence a system where a kind is given to each constructor constant employed can be modeled. In such a model the meaning of operator mu , the constructor of recursive types, turns out to be just the minimal fixed-point operator.>