Formal Methods for Components and Objects: First International Symposium, FMCO 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 2852 3 Berlin Heidelberg New ...

Author: frank s. de (editor) ; bonsangue | marcello (editor) ; graf | susanne (editor) boer

26 downloads 1183 Views 4MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen

2852

3

Berlin Heidelberg New York Hong Kong London Milan Paris Tokyo

Frank S. de Boer Marcello M. Bonsangue Susanne Graf Willem-Paul de Roever (Eds.)

Formal Methods for Components and Objects First International Symposium, FMCO 2002 Leiden, The Netherlands, November 5-8, 2002 Revised Lectures

13

Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Volume Editors Frank S. de Boer Centre for Mathematics and Computer Science, CWI Kruislaan 413, 1098 SJ Amsterdam, The Netherlands E-mail: [email protected] Marcello M. Bonsangue Leiden University, Leiden Institute of Advanced Computer Science P.O. Box 9512, 2300 RA Leiden, The Netherlands, E-mail: [email protected] Susanne Graf VERIMAG 2 Avenue de Vignate, Centre Equitation, 38610 Grenoble-Gi`eres, France E-mail: [email protected] Willem-Paul de Roever Christian-Albrechts-University of Kiel Institute of Computer Science and Applied Mathematics Hermann-Rodewald-Straße 3, Kiel, Germany E-mail: [email protected] Cataloging-in-Publication Data applied for A catalog record for this book is available from the Library of Congress. Bibliographic information published by Die Deutsche Bibliothek Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data is available in the Internet at . CR Subject Classification (1998): D.2, D.3, F.3, D.4 ISSN 0302-9743 ISBN 3-540-20303-6 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg NewYork a member of BertelsmannSpringer Science+Business Media GmbH www.springeronline.com c Springer-Verlag Berlin Heidelberg 2003 Printed in Germany Typesetting: Camera-ready by author, data conversion by Olgun Computergrafik Printed on acid-free paper SPIN: 10961087 06/3142 543210

Preface

Large and complex software systems provide the necessary infrastucture in all industries today. In order to construct such large systems in a systematic manner, the focus in the development methodologies has switched in the last two decades from functional issues to structural issues: both data and functions are encapsulated into software units that are integrated into large systems by means of various techniques supporting reusability and modiﬁability. This encapsulation principle is essential to both the object-oriented and the more recent componentbased sofware engineering paradigms. Formal methods have been applied successfully to the veriﬁcation of mediumsized programs in protocol and hardware design. However, their application to large systems requires the further development of speciﬁcation and veriﬁcation techniques supporting the concepts of reusability and modiﬁability. In order to bring together researchers and practioners in the areas of software engineering and formal methods, we organized the 1st International Symposium on Formal Methods for Components and Objects (FMCO) in Leiden, The Netherlands, November 5–8, 2002. The program consisted of invited tutorials and more technical presentations given by leading experts in the ﬁelds of Theoretical Computer Science and Software Engineering. The symposium was attended by more than 100 people. This volume contains the contributions of the invited speakers to FMCO 2002. We believe that the presented material provides a unique combination of ideas on software engineering and formal methods which we hope will be an inspiration for those aiming at further bridging the gap between the theory and practice of software engineering. The very idea to organize FMCO arose out of the NWO/DFG bilateral project Mobi-J. In particular we acknowledge the ﬁnancial support of the NWO funding of Mobi-J. Additional ﬁnancial support was provided by the Lorentz Center, the IST project Omega (2001-33522), the Dutch Institute for Programming Research and Algorithmics (IPA), the Royal Netherlands Academy of Arts and Sciences (KNAW), the Centrum voor Wiskunde en Informatica (CWI), and the Leiden Institute of Advanced Computer Science (LIACS).

July 2003

F.S. de Boer M.M. Bonsangue S. Graf W.-P. de Roever (Editors)

VI

Preface

The Mobi-J Project Mobi-J is a project founded by a bilateral research program of the Dutch Organization for Scientiﬁc Research (NWO) and the Central Public Funding Organization for Academic Research in Germany (DFG). The partners of the Mobi-J projects are: – Centrum voor Wiskunde en Informatica (F.S. de Boer) – Leiden Institute of Advanced Computer Science (M.M. Bonsangue) – Christian-Albrechts-Universit¨ at, Kiel (W.-P. de Roever) This project aims at the development of a programming environment which supports component-based design and veriﬁcation of Java programs annotated with assertions. The overall approach is based on an extension of the Java language called Mobi-J with the notion of a component which provides for the encapsulation of its internal processing of date and composition in a network by means of mobile asynchronous channels. The activities of Mobi-J include the organization of international symposia funded by the NWO and Ph.D. research funded by DFG. By means of regular meetings the partners discuss intensively Ph.D. research involving Mobi-Jrelated topics. Mobi-J also maintains contacts with other German universities, including the universities of Oldenburg and Munich, and a close collaboaration with the European IST project OMEGA.

The Omega Project The overall aim of the European IST project Omega (2001-33522) is the deﬁnition of a development methodology in UML for embedded and real-time systems based on formal veriﬁcation techniques. The approach is based on a formal semantics of a suitable subset of UML, adapted and extended where needed with a special emphasis on time-related aspects. The Omega project involves the following partners: VERIMAG (France, Coordinator) Centrum voor Wiskunde en Informatica (The Netherlands) Christian-Albrechts-Universit¨ at (Germany) University of Nijmegen (The Netherlands) Wiezmann Institute (Israel) OFFIS (Germany), EADS Launch Vehicles (France) France Telecom R&D (France) Israel Aircraft Industries (Israel) National Aerospace Laboratory (The Netherlands)

Table of Contents

A Tool-Supported Proof System for Multithreaded Java . . . . . . . . . . . . . . . . ´ E. Abrah´ am, F.S. de Boer, W.-P. de Roever, and M. Steﬀen

1

Abstract Behavior Types: A Foundation Model for Components and Their Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 F. Arbab Understanding UML: A Formal Semantics of Concurrency and Communication in Real-Time UML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 W. Damm, B. Josko, A. Pnueli, and A. Votintseva Live and Let Die: LSC-Based Veriﬁcation of UML-Models . . . . . . . . . . . . . . . 99 W. Damm and B. Westphal Reactive Animation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 D. Harel, S. Efroni, and I.R. Cohen Model-Checking Middleware-Based Event-Driven Real-Time Embedded Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 X. Deng, M.B. Dwyer, J. Hatcliﬀ, G. Jung, Robby, and G. Singh Equivalent Semantic Models for a Distributed Dataspace Architecture . . . . 182 J. Hooman and Jaco van de Pol Java Program Veriﬁcation Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 B. Jacobs, J. Kiniry, and M. Warnier ToolBus: The Next Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 H. de Jong and P. Klint High-Level Speciﬁcations: Lessons from Industry . . . . . . . . . . . . . . . . . . . . . . . 242 B. Batson and L. Lamport How the Design of JML Accommodates Both Runtime Assertion Checking and Formal Veriﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 G.T. Leavens, Y. Cheon, C. Clifton, C. Ruby, and D.R. Cok Finding Implicit Contracts in .NET Components . . . . . . . . . . . . . . . . . . . . . . . 285 K. Arnout and B. Meyer From Co-algebraic Speciﬁcations to Implementation: The Mihda Toolkit . . 319 G. Ferrari, U. Montanari, R. Raggi, and E. Tuosto A Calculus for Modeling Software Components . . . . . . . . . . . . . . . . . . . . . . . . 339 O. Nierstrasz and F. Achermann

VIII

Table of Contents

Speciﬁcation and Inheritance in CSP-OZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 E.-R. Olderog and H. Wehrheim Model-Based Testing of Object-Oriented Systems . . . . . . . . . . . . . . . . . . . . . . 380 B. Rumpe Concurrent Object-Oriented Programs: From Speciﬁcation to Code . . . . . . . 403 E. Sekerinski Design with Asynchronously Communicating Components . . . . . . . . . . . . . . . 424 J. Plosila, K. Sere, and M. Wald´en Composition for Component-Based Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . 443 G. G¨ ossler and J. Sifakis Games for UML Software Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 P. Stevens and J. Tenzer Making Components Move: A Separation of Concerns Approach . . . . . . . . . 487 D. Pattinson and M. Wirsing

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509

A Tool-Supported Proof System for Multithreaded Java ´ Erika Abrah´ am1 , Frank S. de Boer2 , Willem-Paul de Roever1 , and Martin Steﬀen1 1

Christian-Albrechts-University Kiel, Germany 2 CWI Amsterdam, The Netherlands

Abstract. Besides the features of a class-based object-oriented language, Java integrates concurrency via its thread classes. The concurrency model includes shared-variable concurrency via instance variables, coordination via reentrant synchronization monitors, synchronous message passing, and dynamic thread creation. To reason about safety properties of multithreaded Java programs, we introduce an assertional proof method for a multithreaded sublanguage of Java, covering the mentioned concurrency issues as well as the objectbased core of Java. The veriﬁcation method is formulated in terms of proof-outlines, where the assertions are layered into local ones specifying the behavior of a single instance, and global ones taking care of the connections between objects. From the annotated program, a translator tool generates a number of veriﬁcation conditions which are handed over to the interactive theorem prover PVS.

1

Introduction

Besides the features of a class-based object-oriented language, Java integrates concurrency via its thread classes. The semantical foundations of Java [GJS96] have been thoroughly studied ever since the language gained widespread popularity (e.g. [AF99,SSB01,CKRW99]). The research concerning Java’s proof theory mainly concentrated on sequential sub-languages (e.g. [Hui01,vON02,PHM99]). This work presents a tool-supported assertional proof system for Javasynch , a subset of Java, featuring dynamic object creation, method invocation, object references with aliasing, and, speciﬁcally, concurrency and Java’s monitor discipline. The behavior of a Javasynch program results from the concurrent execution of methods. To support a clean interface between internal and external object behavior, Javasynch does not allow qualiﬁed references to instance variables. As a consequence, shared-variable concurrency is caused by simultaneous execution within a single object, only, but not across object boundaries. To mirror this

Part of this work has been ﬁnancially supported by IST project Omega (IST-200133522) and NWO/DFG project Mobi-J (RO 1122/9-1, RO 1122/9-2).

F.S. de Boer et al. (Eds.): FMCO 2002, LNCS 2852, pp. 1–32, 2003. c Springer-Verlag Berlin Heidelberg 2003

2

´ E. Abrah´ am et al.

modularity, the assertional logic and the proof system are formulated at two levels, a local and a global one. The local assertion language describes the internal object behavior. The global behavior, including the communication topology of the objects, is expressed in the global language. As in the Object Constraint Language (OCL) [WK99], properties of object-structures are described in terms of a navigation or dereferencing operator. The proof system is formulated in terms of proof outlines [OG76], i.e., of programs augmented by auxiliary variables and annotated with Hoare-style assertions [Flo67,Hoa69]. The satisfaction of the program properties speciﬁed by the assertions is guaranteed by the veriﬁcation conditions of the proof system. The execution of a single method body in isolation is captured by standard local correctness conditions, using the local assertion language. Interference between concurrent method executions is covered by the interference freedom test [OG76,LG81], formulated also in the local language. It has especially to accommodate for reentrant code and the speciﬁc synchronization mechanism. Possibly aﬀecting more than one instance, communication and object creation is treated in the cooperation test, using the global language. The communication can take place within a single object or between diﬀerent objects. As these cases cannot be distinguished syntactically, our cooperation test combines elements from similar rules in [AFdR80] and in [LG81] for CSP. Our proof method is modular in the sense that it allows for separate interference freedom and cooperation tests (Fig. 1). This modularity, which in practice simpliﬁes correctness proofs considerably, is obtained by disallowing the assignment of the result of communication and object creation to instance variables. Clearly, such assignments can be avoided by additional assignments to fresh local variables and thus at the expense of new interleaving points.

Java program

augmentation annotation

Proof Verger Verification outline tool conditions

Syntax of assertions

Javasynch correctness

interference freedom Fig. 1. Modularity of the proof system.

PVS

Program correctness proof

Semantics of assertions

Proof of the conditions

cooperation test

Condition generation

sequential correctness

Fig. 2. The veriﬁcation process.

Computer-support is given by the tool Verger (VERiﬁcation condition GEneratoR), taking a proof outline as input and generating the veriﬁcation conditions as output. We use the interactive theorem prover PVS [ORS92] to verify the conditions, for which we only need to encode the semantics of the assertion language (cf. Figure 2). The veriﬁcation conditions are generated by a syntax-

A Tool-Supported Proof System for Multithreaded Java

3

directed Hoare logic based on a logical modeling of assignments by means of substitutions, instead of more semantic approaches using the global store model [AL97,JKW03,vON02,PHM99], which requires an explicit encoding of the semantics of assignments. To transparently describe the proof system, we present it incrementally in three stages: We start with a sequential, class-based sublanguage of Java and its proof system in Section 2, featuring dynamic object creation and method invocation. This level shows how to handle activities of a single thread of execution. On the second stage we include concurrency in Section 3, where the proof system is extended to handle dynamic thread creation and aspects of interleaving and shared variable concurrency. Finally, we integrate Java’s monitor synchronization mechanism in Section 4. Section 5 shows how we can prove deadlock freedom, and Section 6 discusses related and future work. The incremental development shows how the proof system can be extended stepwise to deal with additional features of the programming language. Further extensions with for example the concepts of inheritance and subtyping build topics for future work. In this paper, the veriﬁcation conditions are formulated as standard Hoaretriples {ϕ}stm{ψ}. Their meaning is, that if stm is executed in a state satisfying ϕ, and the execution terminates, then the resulting state satisﬁes ψ. For the formal semantics of Hoare-triples, given by means of a weakest precondition calculus, for soundness and completeness of the proof method, and for the de´ scription of the tool support see [AdBdRS03].

2

The Sequential Sublanguage

In this section we start with a sequential part of our language, ignoring concurrency issues of Java, which will be added in later sections. Furthermore —and throughout the paper— we concentrate on the object-based core Java, i.e., we disregard inheritance and consequently subtyping, overriding, and late-binding. For simplicity, we neither allow method overloading, i.e., we require that each method name is assigned a unique list of formal parameter types and a return type. In short, being concerned with the veriﬁcation of the run-time behavior, we assume a simple monomorphic type discipline. Programs, as in Java, are given by a collection of classes containing instance variable and method declarations. Instances of the classes, i.e., objects, are dynamically created, and communicate via method invocation, i.e., synchronous message passing. The languages we consider are strongly typed languages. Besides class types c, they support booleans Bool and integers Int as primitive types, furthermore pairs t × t and lists list t as composite types. Each domain is equipped with a standard set of operators. Without inheritance and subtyping, the type system is rather straightforward. Throughout the paper, we tacitly assume all constructs of the abstract syntax to be well-typed, without further explicating the static semantics here. We thus work with a type-annotated abstract syntax where we omit the explicit mentioning of types when no confusion can arise.

´ E. Abrah´ am et al.

4

2.1

Syntax

The abstract syntax of the sequential language Javaseq is summarized in Table 1. Though we use the abstract syntax for the theoretical part of this work, our tool supports Java syntax. For variables, we notationally distinguish between instance variables x ∈ IVar and local or temporary variables u ∈ TVar . Instance variables hold the state of an object and exist throughout the object’s lifetime. Local variables are stack-allocated; they play the role of formal parameters and variables of method deﬁnitions and only exist during the execution of the method to which they belong. We use Var = IVar ∪˙ TVar for the set of program variables with typical element y. The set IVar c of instance variables of a class c is given implicitly by the instance variables occurring in the class; the set of local variables of method declarations is given similarly. Besides using instance and local variables, expressions e ∈ Exp are built from the self-reference this, the empty reference null, and from subexpressions using the given operators. To support a clean interface between internal and external object behavior, Javaseq does not allow qualiﬁed references to instance variables. As statements stm ∈ Stm , we allow assignments, object creation, method invocation, and standard control constructs like sequential composition, conditional statements, and iteration. We write for the empty statement. A method deﬁnition consists of a method name m, a list of formal parameters u1 , . . . , un , and a method body of the form stm; return eret , i.e., we require that method bodies are terminated by a single return statement, giving back the control and possibly a return value. The set Meth c contains the methods of class c. We denote the body of method m of class c by body m,c . A class is deﬁned by its name c and its methods, whose names are assumed to be distinct. A program, ﬁnally, is a collection of class deﬁnitions having diﬀerent class names, where class main deﬁnes by its run-method the entry point of the program execution. We call the body of the run-method of the main class the main statement of the program1 . The run-method cannot be invoked. Besides the mentioned simpliﬁcations on the type system, we impose for technical reasons the following restrictions: We require that method invocation and object creation statements contain only local variables, i.e., that none of the expressions e0 , . . . , en in a method invocation e0 .m(e1 , . . . , en ) contains instance variables. Furthermore, formal parameters must not occur on the left-hand side of assignments. These restrictions imply that during the execution of a method the values of the actual and formal parameters are not changed, and thus we can use their equality to describe caller-callee dependencies when returning from a method call. The above restrictions could be released by storing the identity of the callee object and the values of the formal and actual parameters in additional 1

In Java, the entry point of a program is given by the static main-method of the main class. Relating the abstract syntax to that of Java, we assume that the main class is a Thread-class whose main-method just creates an instance of the main class and starts its thread. The reason to make this restriction is, that Java’s main-method is static, but our proof system does not support static methods and variables.

A Tool-Supported Proof System for Multithreaded Java

5

Table 1. Javaseq abstract syntax. e ::= x | u | this | null | f(e, . . ., e) eret ::= | e stm ::= x := e | u := e | u := newc | u := e.m(e, . . ., e) | e.m(e, . . ., e) | | stm; stm | if e then stm else stm ﬁ | while e do stm od . . . meth ::= m(u, . . ., u){ stm; return eret } meth run ::= run(){ stm; return } class ::= c{meth. . .meth} class main ::= c{meth. . .meth meth run } prog ::= class. . .class class main

built-in auxiliary variables. However, the restrictions simplify the proof system and thus they make it easier to understand the basic ideas of this work. Finally, the result of an object creation or method invocation statement may not be assigned to instance variables. This restriction allows for a proof system with separated veriﬁcation conditions for interference freedom and cooperation. It should be clear that it is possible to transform a program to adhere to this restrictions at the expense of additional local variables and thus new interleaving points. Also this restriction could be released, without loosing the mentioned modularity, but it would increase the complexity of the proof system. 2.2

Semantics

States and Conﬁgurations. Let Val t be the disjoint domains of the various t ˙ types t and Val = t Val , where ∪˙ is the disjoint union operator. For class names c, the disjunct sets Val c with typical elements α, β, . . . denote inﬁnite sets / of object identiﬁers. The value of the empty reference null in type c is null c ∈ Val c . In general we will just write null , when c is clear from the context. We deﬁne Val cnull as Val c ∪˙ {null c } and correspondingly for compound types, and Val null = ˙ t Val tnull . Let Init : Var → Val null be a function assigning an initial value to each variable y ∈ Var , i.e., null , false, and 0 for class, boolean, and integer types, respectively, and analogously for compound types, where sequences are initially empty. We deﬁne this ∈ / Var , such that the self-reference is not in the domain of Init 2 . A local state τ ∈ Σloc of type TVar Val null is a partial function holding the m,c of method m values of the local variables of a method. The initial local state τinit of class c assigns to each local variable u of m the value Init(u). A local conﬁguration (α, τ, stm) of a thread executing within an object α speciﬁes, in addition to its local state τ , its point of execution represented by the statement stm. A thread conﬁguration ξ is a stack of local conﬁgurations (α0 , τ0 , stm 0 ) . . . (αn , τn , stm n ), representing the call chain of the thread. We write ξ ◦ (α, τ, stm) for pushing a new local conﬁguration onto the stack. 2

In Java, this is a “ﬁnal” instance variable, which for instance implies, it cannot be assigned to.

6

´ E. Abrah´ am et al.

An object is characterized by its instance state σinst ∈ Σinst , a partial function of type IVar ∪˙ {this} Val null , which assigns values to the self-reference c,init this and to the instance variables. The initial instance state σinst of instances c instance of class c assigns a value from Val to this, and to each of its remaining variables x the value Init(x). A global state σ ∈ Σ of type ( ˙ c Val c ) Σinst stores for each currently existing object, i.e., an object belonging to the domain dom(σ) of σ, its instance state. The set of existing objects of type c in a state σ is given by Val c (σ), and Val cnull (σ) = Val c (σ) ∪˙ {null c }. For the remaining types, Val t (σ) and Val tnull (σ) are deﬁned correspondingly, Val (σ) = ˙ t Val t (σ), and Val null (σ) = ˙ t Val tnull (σ). A global conﬁguration T, σ describes the currently existing objects by the global state σ, where the set T contains the conﬁguration of the executing thread. For the concurrent languages of the later sections, T will be the set of conﬁgurations of all currently executing threads. In the following, we write (α, τ, stm) ∈ T if there exists a local conﬁguration (α, τ, stm) within one of the execution stacks of T . We denote by τ [u → v] the local state which assigns the value v to u and agrees with τ on the values of all other variables; σinst [x → v] is deﬁned analogously, where σ[α.x → v] results from σ by assigning v to the instance variable x of object α. We use these operators analogously for vectors of variables. We use τ [y → v] also for arbitrary variable sequences, where instance variables are untouched; σinst [y → v] and σ[α.y → v] are analogous. Finally for global states, σ[α → σinst ] equals σ except on α; note that in case α ∈ / Val (σ), the operation extends the set of existing objects by α, which has its instance state initialized to σinst . Operational Semantics. Expressions are evaluated with respect to an instance local state (σinst , τ ), where the instance state gives meaning to the instance variables and the self-reference, whereas the local state determines the values of the σ ,τ local variables. The main cases of the evaluation function are [[x]]E inst = σinst (x) σinst ,τ = τ (u). The operational semantics of Javaseq is given inductively and [[u]]E by the rules of Table 2 as transitions between global conﬁgurations. The rules are formulated such a way that we can re-use them for the concurrent languages of the later sections. Note that for the sequential language, the sets T in the rules are empty, since there is only one single thread in global conﬁgurations. We elide the rules for the remaining sequential constructs —sequential composition, conditional statement, and iteration— as they are standard. Before having a closer look at the semantical rules for the transition relation −→, let us start by deﬁning the starting point of a program. The initial conﬁgc,init uration T0 , σ0 of a program satisﬁes dom(σ0 ) = {α}, σ0 (α) = σinst [this → α], run,c and T0 = {(α, τinit , body run,c )}, where c is the main class, and α ∈ Val c . A conﬁguration T, σ of a program is reachable if there exists a computation T0 , σ0 −→ ∗ T, σ such that T0 , σ0 is the initial conﬁguration of the program and −→ ∗ the reﬂexive transitive closure of −→. A local conﬁguration (α, τ, stm) ∈ T is enabled in T, σ, if it can be executed, i.e., if there is a computation step T, σ → T , σ executing stm in the local state τ and object α. Assignments to instance or local variables update the corresponding state component (see rules Assinst and Assloc ). Object creation by u := newc , as

A Tool-Supported Proof System for Multithreaded Java

7

Table 2. Javaseq operational semantics. σ(α),τ T ∪˙ {ξ ◦ (α, τ, x:=e; stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ, stm)}, σ[α.x →[[e]]E ]

σ(α),τ T ∪˙ {ξ ◦ (α, τ, u:=e; stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ [u →[[e]]E ], stm)}, σ

β ∈ Val c \Val (σ)

c,init σinst = σinst [this → β]

σ = σ[β → σinst ]

→ β], stm)}, σ T ∪˙ {ξ ◦ (α, τ, u:=newc ; stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ [u

Assinst

Assloc

New

m(u){ body } ∈ Meth c β=

σ(α),τ [[e0 ]]E

∈ Val c (σ)

σ(α),τ

m,c τ = τinit [u →[[e]]E

]

Call

T ∪˙ {ξ ◦ (α, τ, u := e0 .m(e); stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ, receive u; stm) ◦ (β, τ , body)}, σ σ(β),τ

→[[eret ]]E τ = τ [uret

]

Return

T ∪˙ {ξ ◦ (α, τ, receive uret ; stm) ◦ (β, τ , return eret )}, σ −→

T ∪˙ {ξ ◦ (α, τ , stm)}, σ

T ∪˙ {(α, τ, return)}, σ −→ T ∪˙ {(α, τ, )}, σ

Returnrun

shown in rule New, creates a new object of type c with a fresh identity stored in the local variable u, and initializes its instance variables. Invoking a method extends the call chain by a new local conﬁguration (cf. Call). After initializing the local state and passing the parameters, the thread begins to execute the method body. When returning from a method call (cf. Return), the callee evaluates its return expression and passes it to the caller which subsequently updates its local state. The method body terminates its execution and the caller can continue. We have similar rules not shown in the table for the invocation of methods without return value. The executing thread ends its lifespan by returning from the run-method of the initial object (see Returnrun ). 2.3

The Assertion Language

The assertion logic consists of a local and a global sublanguage. Local assertions p, q, . . . are used to annotate methods in terms of their local variables and of the instance variables of the class to which they belong. Global assertions P, Q, . . . describe a whole system of objects and their communication structure and will be used in the cooperation test. In the assertion language we add the type Object as the supertype of all classes, and we introduce logical variables z diﬀerent from all program variables. Logical variables are used for quantiﬁcation and as free variables to represent local variables in the global assertion language.

´ E. Abrah´ am et al.

8

Table 3. Semantics of assertions. ([[∃z. p]]L

ω,σinst ,τ

= true)

iﬀ

ω,σinst ,τ

([[p]]L

([[∃z∈e. p]]L

= true)

iﬀ

([[z∈e ∧ p]]L

[[E.x]]ω,σ G

=

σ([[E]]ω,σ G )(x)

= true)

iﬀ

([[P ]]G

([[∃z. P ]]ω,σ G

ω[z → v],σinst ,τ

= true for some v ∈ Val )

ω[z → v],σinst ,τ

ω[z → v],σ

=true for some v ∈ Val null )

= true for some v ∈ Val null (σ))

Expressions and assertions are interpreted relative to a logical environment ω, assigning values to logical variables. Assertions are boolean program expressions, extended by logical variables and quantiﬁcation3 . Global assertions may furthermore contain qualiﬁed references. Note that when the global expressions E and E refer to the same object, that is, E and E are aliases, then E.x and E .x denote the same variable. Quantiﬁcation can be used for all types, also for reference types. However, the existence of objects dynamically depends on the global state, something one cannot speak about on the local level. Nevertheless, one can assert the existence of objects on the local level, provided one is explicit about the domain of quantiﬁcation. Thus quantiﬁcation over objects in the local assertion language is restricted to ∀z ∈ e. p for objects and to ∀z e. p for lists of objects, and correspondingly for existential quantiﬁcation and for composite types. Unrestricted quantiﬁcation ∀z. p can be used in the local language for boolean and integer domains only. Global assertions are evaluated in the context of a global state. Thus, quantiﬁcation is allowed unrestricted for all types and ranges over the set of existing values. ω,σ ,τ The evaluations of local and global assertions are given by [[p]]L inst and ω,σ [[P ]]G . The main cases are shown in Table 3. We write ω, σinst , τ |=L p for ω,σ ,τ [[p]]L inst = true, and |=L p if p holds in all contexts; we use analogously |=G for global assertions. To express a local property p in the global assertion language, we deﬁne the lifting substitution p[z/this] by simultaneously replacing in p all occurrences of this by z, and transforming all occurrences of instance variables x into qualiﬁed references z.x. We assume z not to occur in p. For notational convenience we view the local variables occurring in the global assertion p[z/this] as logical variables. Formally, these local variables are replaced by fresh logical variables. We will write P (z) for p[z/this], and similarly for expressions. 2.4

The Proof System

The proof system has to accommodate for dynamic object creation, aliasing, and method invocation. Before describing the proof method we ﬁrst show how to augment and annotate programs resulting in proof outlines or asserted programs. 3

In this paper we use mathematical notation like ∀z. p etc. for phrases in abstract syntax. The concrete syntax used by Verger is an adaptation of jml.

A Tool-Supported Proof System for Multithreaded Java

9

Proof Outlines. For a complete proof system it is necessary that the transition semantics of Javaseq can be encoded in the assertion language. As the assertion language reasons about the local and global states, we have to augment the program with fresh auxiliary variables to represent information about the control points and stack structures within the local and global states. Invariant program properties are speciﬁed by the annotation. An augmentation extends a program by atomically executed multiple assignments y := e to auxiliary variables, which we call observations. Furthermore, the observations have, in general, to be “attached” to statements they observe in an atomic manner. For object creation this is syntactically represented by the augmentation u := newc ; y := enew which attaches the observation to the object creation statement. Observations y 1 := e 1 of a method call and observations y 4 := e 4 of the corresponding reception of a return value4 is denoted by u := e0 .m(e); y 1 := e 1 !call y 4 := e 4 ?ret . The augmentation y 2 := e 2 ?call stm; return eret ; y 3 := e 3 !ret of method bodies speciﬁes y 2 := e 2 as the observation of the reception of the method call and y 3 := e 3 as the observation attached to the return statement. Assignments can be observed using y := e; y := e ass . A stand-alone observation not attached to any statement is written as y := e ; it can be inserted at any point in the program. The augmentation does not inﬂuence the control ﬂow of the program but enforce a particular scheduling policy. An assignment statement and its observation are executed simultaneously. Object creation and its observation are executed in a single computation step, in this order. For method call, communication, sender, and receiver observations are executed in a single computation step, in this order. Points between a statement and its observation are no control points, since the statement and its observation are executed in a single computation step; we call them auxiliary points. In the following we call assignment statements with their observations, unobserved assignments, alone-standing observations, or observations of communication or object creation general as multiple assignments, since they are executed simultaneously. In order to express the transition semantics in the logic, we identify each local conﬁguration by the object in which it executes together with the value of its built-in auxiliary local variable conf storing a unique object-internal identiﬁer. Its uniqueness is assured by the auxiliary instance variable counter, incremented for each new local conﬁguration in that object. The callee receives the “return address” as auxiliary formal parameter caller of type Object × Int, storing the identities of the caller object and the calling local conﬁguration. The parameter caller of the initial invocation of the run-method of the initial object get the value (null , 0). Syntactically, the built-in augmentation translates each method deﬁnition m(u){stm} into m(u, caller){conf, counter := counter, counter + 1?call stm}. Cor4

To exclude the possibility, that two multiple assignments get executed in a single computation step in the same object, we require that caller observations in a self´ communication may not change the values of instance variables [AdBdRS03].

´ E. Abrah´ am et al.

10

respondingly, method invocation statements u := e0 .m(e) get extended to u := e0 .m(e, (this, conf)). For readability, in the examples of the following sections we will not explicitly list the built-in augmentation; they are meant to be automatically included. To specify invariant properties of the system, the augmented programs are annotated by attaching local assertions to each control and auxiliary point. We use the triple notation {p} stm {q } and write pre(stm) and post(stm) to refer to the pre- and the post-condition of a statement. For assertions at auxiliary points we use the following notation: The annotation {p0 }

u := new c; {p1 }new y := enew {p2 }

of an object creation statement speciﬁes p0 and p2 as pre- and postconditions, where p1 at the auxiliary point should hold directly after object creation but before the observation. The annotation { p0 } u

:= e0 .m(e);

{p1 }!call y 1

:= e1 !call

{p2 }wait

{p3 }?ret y 4

:= e4 ?ret

{p4 }

assigns p0 and p4 as pre- and postconditions to the method invocation; p1 and p3 are assumed to hold directly after method call and return, resp., but prior to their observations; p2 describes the control point of the caller after method call and before return. The annotation of method bodies stm; return e is as follows: {p0 }?call y 2

:= e2 ?call {p1 }

stm;

{p2 }

return e; {p3 }!ret y 3 := e3 !ret {p4 }

The callee postcondition of the method call is p1 ; the callee pre- and postconditions of return are p2 and p4 . The assertions p0 resp. p3 specify the states of the callee between method call resp. return and its observation. Besides pre- and postconditions, the annotation deﬁnes for each class c a local assertion Ic called class invariant, specifying invariant properties of instances of c in terms of its instance variables5 . We require that the precondition of each method’s body is the class invariant. Finally, a global assertion GI called the global invariant speciﬁes properties of communication between objects. As such, it should be invariant under object-internal computation. For that reason, we require that for all qualiﬁed references E.x in GI with E of type c, all assignments to x in class c occur in the observations of communication or object creation. We require that in the annotation no free logical variables occur. In the following we will also use partial annotation. Assertions which are not explicitly speciﬁed are by deﬁnition true. Veriﬁcation Conditions. The proof system formalizes a number of veriﬁcation conditions which inductively ensure that for each reachable conﬁguration the 5

The notion of class invariant commonly used for sequential object-oriented languages diﬀers from our notion: In a sequential setting, it would be suﬃcient that the class invariant holds initially and is preserved by whole method calls, but not necessarily in between.

A Tool-Supported Proof System for Multithreaded Java

11

local assertions attached to the current control points in the thread conﬁguration as well as the global and the class invariants hold. The conditions are grouped, ´ as usual, into initial conditions [AdBdRS03], and for the inductive step into local correctness and tests for interference freedom and cooperation. Arguing about two diﬀerent local conﬁgurations makes it necessary to distinguish between their local variables, since they may have the same names; in such cases we will rename the local variables in one of the local states. We use primed assertions p to denote the given assertion p with every local variable u replaced by a fresh one u , and correspondingly for expressions. Local Correctness. A proof outline is locally correct, if the properties of method instances as speciﬁed by the annotation are invariant under their own execution. For example, the precondition of an assignment must imply its postcondition after its execution. The following condition should hold for all multiple assignments being an assignment statement with its observation, an unobserved assignment, or an alone-standing observation: Deﬁnition 1 (Local Correctness: Assignment). A proof outline is locally correct, if for all multiple assignments {p1 } y := e {p2 } in class c, which is not the observation of object creation or communication, |=L {p1 }

y := e

{p2 } .

(1)

The conditions for loops and conditional statements are similar. Note that we have no local veriﬁcation conditions for observations of communication and object creation. The postconditions of such statements express assumptions about the communicated values. These assumptions will be veriﬁed in the cooperation test. The Interference Freedom Test. Invariance of local assertions under computation steps in which they are not involved is assured by the proof obligations of the interference freedom test. Its deﬁnition covers also invariance of the class invariants. Since Javaseq does not support qualiﬁed references to instance variables, we only have to deal with invariance under execution within the same object. Aﬀecting only local variables, communication and object creation do not change the instance states of the executing objects. Thus we only have to cover invariance of assertions at control points over assignments in the same object, including observations of communication and object creation. To distinguish local variables of the diﬀerent local conﬁgurations, we rename those of the assertion. Let q be an assertion at a control point and y := e a multiple assignment in the same class c. In which cases does q have to be invariant under the execution of the assignment? Since the language is sequential, i.e., q and y := e belong to the same thread, the only assertions endangered are those at control points waiting for return earlier in the current execution stack. Invariance of a local conﬁguration under its own execution, however, need not be considered and is excluded by requiring conf

= conf . Interference with the matching return statement in a self-communication need also not be considered, because

12

´ E. Abrah´ am et al.

communicating partners execute simultaneously. Let caller obj be the ﬁrst and caller conf the second component of caller. We deﬁne waits for ret(q, y := e) by – conf

= conf, for assertions {q }wait attached to control points waiting for return, if y := e is not the observation of return; = conf ∧ (this

= caller obj ∨ conf

= caller conf), for assertions {q }wait , if – conf

y := e observes return; – false, otherwise. The interference freedom test can now be formulated as follows: Deﬁnition 2 (Interference Freedom). A proof outline is interference free, if for all classes c and multiple assignments y := e with precondition p in c, |=L {p ∧ Ic }

y := e

{Ic } .

(2)

Furthermore, for all assertions q at control points in c, |=L {p ∧ q ∧ waits for ret(q, y := e)}

y := e

{q } .

(3)

Note that if we would allow qualiﬁed references in program expressions, we would have to show interference freedom of all assertions under all assignments in programs, not only for those occurring in the same class. For a program with n classes where each class contains k assignments and l assertions at control points, the number of interference freedom conditions is in O(c · k · l), instead of O((c · k) · (c · l)) with qualiﬁed references. Example 1. Let {p1 } this.m(e); {p2 }!call stm 1 !call {p3 }wait {p4 }?ret stm 2 ?ret {p5 } be an annotated method call statement in a method m of a class c with an integer auxiliary instance variable x, such that all assertions imply conf = x. I.e., the identity of the executing local conﬁguration is stored in the instance variable x. The annotation expresses that the method m of c is not called recursively. That means, in our sequential language, no pairs of control points in m of c can be simultaneously reached. The assertions p2 and p4 do not have to be shown invariant, since they are attached to auxiliary points. Interference freedom neither requires invariance of the assertions p1 and p5 , since they are not at control points waiting for return, and thus the antecedents of the corresponding conditions are false. Invariance of p3 under the execution of the observation stm 1 with precondition p2 requires validity of |=L {p2 ∧ p3 ∧ waits for ret(p3 , stm 1 )} stm 1 {p3 }. The assertion p2 ∧ p3 ∧ waits for ret(p3 , stm 1 ) implies (conf = x) ∧ (conf = x) ∧ (conf = conf), which evaluates to false. Invariance of p3 under stm 2 is analogous. Example 2. Assume a partially6 annotated method invocation statement of the form {p1 } this.m(e); {conf = x ∧ p2 }wait {p3 } in a class c with an integer auxiliary instance variable x, and assume that method m of c has the annotated 6

As already mentioned, missing assertions are by deﬁnition true.

A Tool-Supported Proof System for Multithreaded Java

13

return statement {q1 } return; {caller = (this, x)}!ret stm !ret {q2 } . The annotation expresses that the local conﬁgurations containing the above statements are in caller-callee relationship. Thus upon return, the control point of the caller moves from the point at conf = x ∧ p2 to that at p3 , i.e, conf = x ∧ p2 does not have to be invariant under the observation of the return statement. Again, the assertion caller = (this, x) at an auxiliary point does not have to be shown invariant. For the assertions p1 , p3 , q1 , and q2 , which are not at a control point waiting for return, the antecedent is false. Invariance of conf = x ∧ p2 under the observation stm with precondition caller = (this, x) is covered by the interference freedom condition |=L { caller = (this, x) ∧ (conf = x ∧ p2 )∧ waits for ret((conf = x ∧ p2 ), stm) } stm {conf = x ∧ p2 } . = (this, conf ), which contradicts the The waits for ret assertion implies caller

assumptions caller = (this, x) and conf = x; thus the antecedent of the condition is false. Satisfaction of caller = (this, x) directly after communication and satisfaction of p3 and q2 after the observation is assured by the cooperation test. The Cooperation Test. Whereas the interference freedom test assures invariance of assertions under steps in which they are not involved, the cooperation test deals with inductivity for communicating partners, assuring that the global invariant, and the preconditions and the class invariants of the involved statements imply their postconditions after the joint step. Additionally, the preconditions of the corresponding observations must hold immediately after communication. The global invariant expresses global invariant properties using auxiliary instance variables which can be changed by observations of communication, only. Consequently, the global invariant is automatically invariant under the execution of non-communicating statements. For communication and object creation, however, the invariance must be shown as part of the cooperation test. We start with the cooperation test for method invocation. Since diﬀerent objects may be involved, the cooperation test is formulated in the global assertion language. Local properties are expressed in the global language using the lifting substitution. As already mentioned, we use the shortcuts P (z) for p[z/this], Q (z ) for q [z /this], and similarly for expressions. To avoid name clashes between local variables of the partners, we rename those of the callee. Remember that after communication, i.e., after creating and initializing the callee local conﬁguration and passing on the actual parameters, ﬁrst the caller, and then the callee execute their corresponding observations, all in a single computation step. Correspondingly for return, after communicating the result value, ﬁrst the callee and then the caller observation gets executed. Let z and z be logical variables representing the caller, respectively the callee object in a method call. We assume the global invariant, the class invariants of the communicating partners, and the preconditions of the communicating statements to hold prior to communication. For method invocation, the precondition of the callee is its class invariant. That the two statements indeed repre-

14

´ E. Abrah´ am et al.

sent communicating partners is captured in the assertion comm, which depends on the type of communication: For method invocation e0 .m(e), the assertion E0 (z) = z states, that z is indeed the callee object. Remember that method invocation hands over the “return address”, and that the values of formal parameters remain unchanged. Furthermore, actual parameters may not contain instance variables, i.e., their interpretation does not change during method execution. Therefore, the formal and actual parameters can be used at returning from a method to identify partners being in caller-callee relationship, using the built-in auxiliary variables. Thus for the return case, comm additionally states u = E(z), where u and e are the formal and the actual parameters. Returning from the run-method terminates the executing thread, which does not have communication eﬀects. As in the previous conditions, state changes are represented by assignments. For the example of method invocation, communication is represented by the assignment u := E(z), where initialization of the remaining local variables v is covered by v := Init(v). The assignments z.y 1 := E 1 (z) and z .y 2 := E 2 (z ) stand for the caller and callee observations y 1 := e 1 and y 2 := e 2 , executed in the objects z and z , respectively. Note that we rename all local variables of the callee to avoid name clashes. Deﬁnition 3 (Cooperation Test: Communication). isﬁes the cooperation test for communication, if

A proof outline sat-

|=G {GI ∧ P1 (z) ∧ Q1 (z ) ∧ comm ∧ z = null ∧ z = null} fcomm {P2 (z) ∧ Q2 (z )} |=G {GI ∧ P1 (z) ∧ Q1 (z ) ∧ comm ∧ z = null ∧ z = null} fcomm ; fobs1 ; fobs2 {GI ∧ P3 (z) ∧ Q3 (z )}

(4)

(5)

hold for distinct fresh logical variables z of type c and z of type c , in the following cases: 1. Call: For all statements {p1 } uret := e0 .m(e); {p2 }!call y 1 := e 1 !call {p3 }wait (or such without receiving a value) in class c with e0 of type c , where method m of c has body {q2 }?call y 2 := e 2 ?call {q3 } stm; return eret , formal parameters u, and local variables v except the formal parameters. The callee class invariant is q1 = Ic . The assertion comm is given by E0 (z) = z . Furthermore, fcomm is u , v := E(z), Init(v), fobs1 is z.y 1 := E 1 (z), and fobs2 is z .y 2 := E 2 (z ). 2. Return: For all uret := e0 .m(e); y 1 := e 1 !call {p1 }wait {p2 }?ret y 4 := e 4 ?ret {p3 } (or such without receiving a value) occurring in c with e0 of type c , such !ret that method m of c has the return statement {q1 } return eret ; {q2 } y 3 := e 3 !ret {q3 } , and formal parameter list u, the above equations must hold with (z ), comm given by E0 (z) = z ∧ u = E(z), and where fcomm is uret := Eret fobs1 is z .y 3 := E 3 (z ), and fobs2 is z.y 4 := E 4 (z).

A Tool-Supported Proof System for Multithreaded Java

15

3. Returnrun : For {q1 } return; {q2 }!ret y 3 := e 3 !ret {q3 } in the run-method of the main class, p1 = p2 = p3 = true, comm = true, fobs1 is z .y 3 := E 3 (z ), and furthermore fcomm and fobs2 are the empty statement. Example 3. This example illustrates how one can prove properties of parameter passing. Let {p} e0 .m(v, e), with p given by v > 0, be a (partially) annotated statement in a class c with e0 of type c , and let method m(u, w) of c have the body {q } stm; return where q is u > 0. Inductivity of the proof outline requires that if p is valid prior to the call (besides the global and class invariants), then q is satisﬁed after the invocation. Omitting irrelevant details, Condition 5 of the cooperation test requires proving |=G {P (z)} u := v {Q (z )}, which expands to |=G {v > 0} u := v {u > 0}. Example 4. The following example demonstrates how one can express dependencies between instance states in the global invariant and use this information in the cooperation test. Let {p} e0 .m(e), with p given by x > 0 ∧ e0 = o, be an annotated statement in a class c with e0 of type c , x an integer instance variable, and o an instance variable of type c , and let method m(u) of c have the annotated body {q } stm; return where q is y > 0 and y an integer instance variable. Let furthermore z ∈ LVar c and let the global invariant be given by ∀z. (z

= null ∧ z.o

= null ∧ z.x > 0) → z.o.y > 0. Inductivity requires that if p and the global invariant are valid prior to the call, then q is satisﬁed after the invocation (again, we omit irrelevant details). The cooperation test Condition 5, i.e., |=G {GI ∧ P (z) ∧ comm ∧ z

= null ∧ z = null} u := E(z) {Q (z )} expands to = null ∧ z.o

= null ∧ z.x > 0) → z.o.y > 0)∧ |=G {(∀z. (z

(z.x > 0 ∧ E0 (z) = z.o) ∧ E0 (z) = z ∧ z = null ∧ z = null } u := E(z) {z .y > 0} Instantiating the quantiﬁcation by z, the antecedent implies z.o.y > 0 ∧ z = z.o, i.e., z .y > 0. Invariance of the global invariant is straightforward. Example 5. This example illustrates how the cooperation test handles observations of communication. Let {¬b} this.m(e){b}wait be an annotated statement in a class c with boolean auxiliary instance variable b and let m(u) of c have the body {¬b}?call b := true?call {b} stm; return. Condition 4 of the cooperation test assures inductivity for the precondition of the observation. We have to show |=G {¬z.b ∧ comm}u := E(z){¬z .b}, i.e., since it is a self-call, |=G {¬z.b ∧ z = z }u := E(z){¬z .b}, which is trivially satisﬁed. Condition 5 of the cooperation test for the postconditions requires |=G {comm}u := E(z); z .b := true{z.b∧z .b} which expands to |=G {z = z }u := E(z); z .b := true{z.b ∧ z .b}, whose validity is easy to see.

16

´ E. Abrah´ am et al.

Besides method calls and return, the cooperation test needs to handle object creation, taking care of the preservation of the global invariant, the postcondition of the new-statement and its observation, and the new object’s class invariant. We can assume that the precondition of the object creation statement, the class invariant of the creator, and the global invariant hold in the conﬁguration prior to instantiation. The extension of the global state with a freshly created object is formulated in a strongest postcondition style, i.e., it is required to hold immediately after the instantiation. We use existential quantiﬁcation to refer to the old value: z of type list Object represents the existing objects prior to the extension. Moreover, that the created object’s identity stored in u is fresh and that the new instance is properly initialized is expressed by the global assertion Fresh(z , u) deﬁned as InitState(u)∧u

∈ z ∧∀v. v ∈ z ∨v = u, where Init is a syntactical operator with interpretation Init (cf. page 5), IVar is theset of instance variables of u, and InitState(u) is the global assertion u

= null ∧ x∈IVar \{this} u.x = Init(x), expressing that the object denoted by u is in its initial instance state. To express that an assertion refers to the set of existing objects prior to the extension of the global state, we need to restrict any existential quantiﬁcation in the assertion to range over objects from z , only. So let P be a global assertion and z of type list Object a logical variable not occurring in P . Then P ↓ z is the global assertion P with all quantiﬁcations ∃z. P replaced by ∃z. obj(z) ⊆ z ∧ P , where obj (v) denotes the set of objects occurring in the value v. Thus a predicate (∃u. P ) ↓ z , evaluated immediately after the instantiation, expresses that P holds prior to the creation of the new object. This leads to the following deﬁnition of the cooperation test for object creation: Deﬁnition 4 (Cooperation Test: Instantiation). A proof outline satisﬁes the cooperation test for object creation, if for all classes c and statements c {p1 } u := new ; {p2 }new y := enew {p3 } in c : |=G z

=null ∧ z

=u ∧ ∃z . Fresh(z , u) ∧ (GI ∧ ∃u. P1 (z)) ↓ z (6) → P2 (z) ∧ Ic (u) |=G {z

=null ∧ z

=u ∧ ∃z . Fresh(z , u) ∧ (GI ∧ ∃u. P1 (z)) ↓ z } z.y := E(z) {GI ∧ P3 (z)}

(7)

with z of type c and z of type list Object fresh. Example 6. Assume a statement u := newc ; {u = this} in a program, where the class invariant of c is x ≥ 0 for an integer instance variable x. Condition 6 of the cooperation test for object creation assures that the class invariant of the new object holds after its creation. We have to show validity of |=G (∃z . Fresh(z , u)) → u.x ≥ 0, i.e., |=G u.x = 0 → u.x ≥ 0, which is trivial. For the postcondition, Condition 7 requires |=G {z = u}{u = z} with the empty statement (no observations are executed), which is true.

A Tool-Supported Proof System for Multithreaded Java

3

17

Multithreading

In this section we extend the language Javaseq to a concurrent language Javaconc by allowing dynamic thread creation. Again, we deﬁne syntax and semantics of the language, before formalizing the proof system. 3.1

Syntax and Semantics

Expressions and statements can be constructed as in Javaseq . The abstract syntax of the remaining constructs is summarized in Table 4. Table 4. Javaconc abstract syntax. meth meth run class class main prog

::= ::= ::= ::= ::=

m(u, . . ., u){ stm; return eret } run(){ stm; return } c{meth. . .meth meth run meth start } class class. . .class class main

As we focus on concurrency aspects, all classes are Thread classes in the sense of Java: Each class contains the pre-deﬁned methods start and run. The runmethods cannot be invoked directly. The parameterless start-method without return value is not implemented syntactically; its semantics is described below. Note, that the syntax does not allow qualiﬁed references to instance variables. As a consequence, shared-variable concurrency is caused by simultaneous execution within a single object, only, but not across object boundaries. The operational semantics of Javaconc extends the semantics of Javaseq by dynamic thread creation. The additional rules are shown in Table 5. The ﬁrst invocation of a start-method brings a new thread into being (Callstart ). The new thread starts to execute the user-deﬁned run-method of the given object while the initiating thread continues its own execution. Only the ﬁrst invo7 cation of the start-method has this eﬀect (Callskip start ) . This is captured by the predicate started (T, β) which holds iﬀ there is a stack (α0 , τ0 , stm 0 ) . . . (αn , τn , stm n ) ∈ T such that β = α0 . A thread ends its lifespan by returning from a run-method (Returnrun of Table 2) 8 . 3.2

The Proof System

In contrast to the sequential language, the proof system additionally has to accommodate for dynamic thread creation and shared-variable concurrency. Before describing the proof method, we show how to extend the built-in augmentation of the sequential language. 7 8

In Java an exception is thrown if the thread is already started but not yet terminated. The worked-oﬀ local conﬁguration (α, τ, ) is kept in the global conﬁguration to ensure that the thread of α cannot be started twice.

18

´ E. Abrah´ am et al. Table 5. Javaconc operational semantics. σ(α),τ

β = [[e]]E

∈ Val c (σ)

¬started (T ∪ {ξ ◦ (α, τ, e.start(); stm)}, β)

run,c T ∪˙ {ξ ◦ (α, τ, e.start(); stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ, stm), (β, τinit , body run,c )}, σ

σ(α),τ

β = [[e]]E

∈ Val (σ)

started (T ∪ {ξ ◦ (α, τ, e.start(); stm)}, β)

T ∪˙ {ξ ◦ (α, τ, e.start(); stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ, stm)}, σ

Callstart

Callskip start

Proof Outlines. As mentioned, an important point of the proof system to achieve completeness is the identiﬁcation of communicating partners. For the concurrent language we additionally have to be able to identify threads. We identify a thread by the object in which it has begun its execution. This identiﬁcation is unique, since an object’s thread can be started only once. We use the type Thread thus as abbreviation for the type Object. During a method call, the callee thread receives its own identity as an auxiliary formal parameter thread. Additionally, we extend the auxiliary formal parameter caller by the caller thread identity, i.e., let caller be of type Object × Int × Thread, storing the identities of the caller object, the calling local conﬁguration, and the caller thread. Note that the thread identities of caller and callee are the same in all cases but the invocation of a start-method. The run-method of the initial object is executed with the values (α0 , (null , 0, null )) assigned to the parameters (thread, caller), where α0 is the initial object. The boolean instance variable started, ﬁnally, remembers whether the object’s start-method has already been invoked. Syntactically, each formal parameter list u in the original program gets extended to (u, thread, caller). Correspondingly for the caller, each actual parameter list e in statements invoking a method diﬀerent from start gets extended to (e, thread, (this, conf, thread)). The invocation of the parameterless start-method of an object e0 gets the actual parameter list (e0 , (this, conf, thread)). Finally, the callee observation at the beginning of the run-method executes started := true. The variables conf and counter are updated as in the previous section. Veriﬁcation Conditions. Local correctness is not inﬂuenced by the new issue of concurrency. Note that local correctness applies now to all concurrently executing threads. The Interference Freedom Test. An assertion q at a control point has to be invariant under an assignment y := e in the same class only if the local conﬁguration described by the assertion is not active in the computation step executing the assignment. Note that assertions at auxiliary points do not have to be shown invariant. Again, to distinguish local variables of the diﬀerent local conﬁgurations, we rename those of the assertion. If q and y := e belong to the same thread, i.e., thread = thread , then we have the same antecedent as for the sequential language. If the assertion and the assignment belong to diﬀerent threads, interference freedom must be shown in

A Tool-Supported Proof System for Multithreaded Java

19

any case except for the self-invocation of the start-method: The precondition of such a method invocation cannot interfere with the corresponding observation of the callee. To describe this setting, we deﬁne self start(q, y := e) by caller = (this, conf , thread ) iﬀ q is the precondition of a method invocation e0 .start(e) and the assignment is the callee observation at the beginning of the run-method, and by false otherwise. Deﬁnition 5 (Interference Freedom). A proof outline is interference free, if the conditions of Deﬁnition 2 hold with waits for ret(q, y := e) replaced by interleavable(q, y := e) = thread = thread → waits for ret(q, y := e) ∧ (8) thread

= thread → ¬self start(q, y := e) . def

Example 7. Assume an assignment {p} stm in an annotated method m of c, and an assertion q at a control point in the same method, which is not waiting for return, such that both p and q imply thread = this. I.e., the method is executed only by the thread of the object to which it belongs. Clearly, p and q cannot be simultaneously reached by the same thread. For invariance of q under the assignment stm, the antecedent of the interference freedom condition implies p ∧ q ∧ interleavable(q, stm). From p ∧ q we conclude thread = thread , and thus by the deﬁnition of interleavable(q, stm) the assertion q should be at a control point waiting for return, which is not the case, and thus the antecedent of the condition evaluates to false. The Cooperation Test. The cooperation test for object creation is not inﬂuenced by adding concurrency, but we have to extend the cooperation test for communication by deﬁning additional conditions for thread creation. Invoking the start-method of an object whose thread is already started does not have communication eﬀects. The same holds for returning from a run-method, which is already included in the conditions for the sequential language as for the termination of the only thread. Note that this condition applies now to all threads. Deﬁnition 6 (Cooperation Test: Communication). A proof outline satisﬁes the cooperation test for communication, if the conditions of Deﬁnition 3 hold for the statements listed there with m

= start, and additionally in the following cases: 1. Callstart : For all statements {p1 } e0 .start(e); {p2 }!call y 1 := e 1 !call {p3 } in class c with e0 of type c , comm is given by E0 (z) = z ∧ ¬z .started, where {q2 }?call y 2 := e 2 ?call {q3 } stm is the body of the run-method of c having formal parameters u and local variables v except the formal parameters. As in the Callcase, q1 = Ic , fcomm is u , v := E(z), Init(v), fobs1 is z.y 1 := E 1 (z), and fobs2 is z .y 2 := E 2 (z ). 2. Callskip start : For the above statements, the equations must additionally hold with the assertion comm given by E0 (z) = z ∧ z .started, q1 = Ic , q2 = q3 = true, fobs1 is z.y 1 := E 1 (z), and fcomm and fobs2 are the empty statement.

´ E. Abrah´ am et al.

20

The Language Javasynch

4

In this section we extend the language Javaconc with monitor synchronization. Again, we deﬁne syntax and semantics of the language Javasynch , before formalizing the proof system. 4.1

Syntax and Semantics

Expressions and statements can be constructed as in the previous languages. The abstract syntax of the remaining constructs is summarized in the Table 6. Formally, methods get decorated by a modiﬁer modif distinguishing between non-synchronized and synchronized methods9 . We use sync(c, m) to state that method m in class c is synchronized. In the sequel we also refer to statements in the body of a synchronized method as being synchronized. Furthermore, we consider the additional predeﬁned methods wait, notify, and notifyAll, whose deﬁnitions use the auxiliary statements !signal, !signal all, ?signal, and returngetlock 10 . Table 6. Javasynch abstract syntax. modif meth meth run meth wait meth notify meth notifyAll meth predef class class main prog

::= ::= ::= ::= ::= ::= ::= ::= ::= ::=

nsync | sync modif m(u, . . ., u){ stm; return eret } nsync run(){ stm; return } nsync wait(){ ?signal; returngetlock } nsync notify(){ !signal ; return } nsync notifyAll(){ !signal all; return } meth start meth wait meth notify meth notifyAll c{meth. . .meth meth run meth predef } class class. . .class class main

The operational semantics extends the semantics of Javaconc by the rules of Table 7, where the Call rule is replaced. Each object has a lock which can be owned by at most one thread. Synchronized methods of an object can be invoked only by a thread which owns the lock of that object (Call), as expressed by the predicate owns, deﬁned below. If the thread does not own the lock, it has to wait until the lock gets free. A thread owning the lock of an object can recursively invoke several synchronized methods of that object, which corresponds to the notion of reentrant monitors. The remaining rules handle the monitor methods wait, notify, and notifyAll. In all three cases the caller must own the lock of the callee object (Callmonitor ). A thread can block itself on an object whose lock it owns by invoking the object’s wait-method, thereby relinquishing the lock and placing itself into the 9 10

Java does not have the “non-synchronized” modiﬁer: methods are non-synchronized by default. Java’s Thread class additionally support methods for suspending, resuming, and stopping a thread, but they are deprecated and thus not considered here.

A Tool-Supported Proof System for Multithreaded Java

21

Table 7. Javasynch Operational semantics. m∈ / {start, run, wait, notify, notifyAll} σ(α),τ

β = [[e0 ]]E

∈ Val c (σ)

modif m(u){ body } ∈ Meth c σ(α),τ

m,c τ = τinit [u →[[e]]E

]

sync(c, m) → ¬owns(T, β)

Call

T ∪˙ {ξ ◦ (α, τ, u := e0 .m(e); stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ, receive u; stm) ◦ (β, τ , body)}, σ m ∈ {wait, notify, notifyAll} σ(α),τ

β = [[e]]E

∈ Val c (σ)

owns(ξ ◦ (α, τ, e.m(); stm), β)

T ∪˙ {ξ ◦ (α, τ, e.m(); stm)}, σ −→

Callmonitor

m,c T ∪˙ {ξ ◦ (α, τ, receive; stm) ◦ (β, τinit , body m,c )}, σ

¬owns(T, β) T ∪˙ {ξ ◦ (α, τ, receive; stm) ◦ (β, τ , returngetlock )}, σ −→

Returnwait

T ∪˙ {ξ ◦ (α, τ, stm)}, σ Signal T ∪˙ {ξ ◦ (α, τ, !signal; stm)} ∪˙ {ξ ◦ (α, τ , ?signal; stm )}, σ −→ T ∪˙ {ξ ◦ (α, τ, stm)} ∪˙ {ξ ◦ (α, τ , stm )}, σ wait(T, α) = ∅ T ∪˙ {ξ ◦ (α, τ, !signal; stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ, stm)}, σ

Signalskip

T = signal (T, α) T ∪˙ {ξ ◦ (α, τ, !signal all; stm)}, σ −→ T ∪˙ {ξ ◦ (α, τ, stm)}, σ

SignalAll

object’s wait set. Formally, the wait set wait(T, α) of an object is given as the set of all stacks in T with a top element of the form (α, τ, ?signal; stm). After having put itself on ice, the thread awaits notiﬁcation by another thread which invokes the notify-method of the object. The !signal-statement in the notify-method thus reactivates a non-deterministically chosen single thread waiting for notiﬁcation on the given object (Signal). Analogously to the wait set, the notiﬁed set notiﬁed (T, α) of α is the set of all stacks in T with top element of the form (α, τ, returngetlock ), i.e., threads which have been notiﬁed and trying to get hold of the lock again. According to rule Returnwait , the receiver can continue after notiﬁcation in executing returngetlock only if the lock is free. Note that the notiﬁer does not hand over the lock to the one being notiﬁed but continues to own it. This behavior is known as signal-and-continue monitor discipline [And00]. If no threads are waiting on the object, the !signal of the notiﬁer is without eﬀect (Signalskip ). The notifyAll-method generalizes notify in that all waiting threads are notiﬁed via the !signal all-broadcast

22

´ E. Abrah´ am et al.

(SignalAll). The eﬀect of this statement is given by setting signal (T, α) as (T \ wait(T, α)) ∪ {ξ ◦ (β, τ, stm) | ξ ◦ (β, τ, ?signal; stm) ∈ wait(T, α)}. Using the wait and notiﬁed sets, we can now formalize the owns predicate: A thread ξ owns the lock of β iﬀ ξ executes some synchronized method of β, but not its wait-method. Formally, owns(T, β) is true iﬀ there exists a thread ξ ∈ T and a (β, τ, stm) ∈ ξ with stm synchronized and ξ ∈ / wait(T, β) ∪ notiﬁed (T, β). The deﬁnition is used analogously for single threads. An invariant of the semantics is that at most one thread can own the lock of an object at a time. 4.2

The Proof System

The proof system has additionally to accommodate for synchronization, reentrant monitors, and thread coordination. First we deﬁne how to extend the augmentation of Javaconc , before we describe the proof method. Proof Outlines. To capture mutual exclusion and the monitor discipline, the instance variable lock of type Thread × Int stores the identity of the thread who owns the lock, if any, together with the number of synchronized calls in the call chain. Its initial value free = (null , 0) indicates that the lock is free. The instance variables wait and notiﬁed of type list(Thread×Int) are the analogues of the waitand notiﬁed -sets of the semantics and store the threads waiting at the monitor, respectively those having been notiﬁed. Besides the thread identity, the number of synchronized calls is stored. In other words, these variables remember the old lock-value prior to suspension which is restored when the thread becomes active again. All auxiliary variables are initialized as usual. For values thread of type Thread and wait of type list(Thread × Int), we will also write thread ∈ wait instead of (thread , n) ∈ wait for some n. Syntactically, besides the augmentation of the previous section, the callee observation at the beginning and at the end of each synchronized method body executes lock := inc(lock) and lock := dec(lock), respectively. The semantics of σ ,τ incrementing the lock [[inc(lock)]]E inst is (τ (thread), n+1) for σinst (lock) = (α, n). Decrementing dec(lock) is inverse. Instead of the auxiliary statements of the semantics, notiﬁcation is represented in the proof system by auxiliary assignments operating on the wait and notiﬁed variables. Entering the wait-method gets the observation wait, lock := wait ∪ {lock}, free; returning from the wait-method observes lock, notiﬁed := get(notiﬁed, thread), notiﬁed\{get(notiﬁed, thread)}. Given a thread α, the get function retrieves the value (α, n) from a wait or notiﬁed set. The semantics assures uniqueness of the association. The !signal-statement of the notify-method is represented by the auxiliary assignment wait, notiﬁed := notify(wait, notiﬁed), where notify(wait, notiﬁed ) is the pair of the given sets with one element, chosen nondeterministically, moved from the wait into the notiﬁed set; if the wait set is empty, it is the identity function. Finally, the !signal all-statement of the notifyAll-method is represented by the auxiliary assignment notiﬁed, wait := notiﬁed ∪ wait, ∅.

A Tool-Supported Proof System for Multithreaded Java

23

Veriﬁcation Conditions. Local correctness agrees with that for Javaconc . In case of notiﬁcation, local correctness covers also invariance for the notifying thread, as the eﬀect of notiﬁcation is captured by an auxiliary assignment. The Interference Freedom Test. Synchronized methods of a single object can be executed concurrently only if one of the corresponding local conﬁgurations is waiting for return: If the executing threads are diﬀerent, then one of the threads is in the wait or notiﬁed set of the object; otherwise, both executing local conﬁgurations are in the same call chain. Thus we assume that either not both the assignment and the assertion occur in a synchronized method, or the assertion is at a control point waiting for return11 . Deﬁnition 7 (Interference Freedom). A proof outline is interference free, if Deﬁnition 5 holds in all cases, such that either not both p and q occur in a synchronized method, or q is at a control point waiting for return. For notiﬁcation, we require also invariance of the assertions for the notiﬁed thread. We do so, as notiﬁcation is described by an auxiliary assignment executed by the notiﬁer. That means, both the waiting and the notiﬁed status of the executing thread are represented by a single control point in the wait-method. The two statuses can be distinguished by the values of the wait and notiﬁed variables. The invariance of the precondition of the return statement in the waitmethod under the assignment in the notify-method represents the notiﬁcation process, whereas invariance of that assertion over assignments changing the lock represents the synchronization mechanism. Information about the lock value will be imported from the cooperation test as this information depends on the global behavior. Example 8. This example shows how the fact, that at most one thread can own the lock of an object, can be used to show mutual exclusion. We use the assertion owns(thread, lock) for thread

= null ∧ thread(lock) = thread, where thread (lock ) is the ﬁrst component of the lock value. Let furthermore free for(thread, lock) be thread

= null ∧ (owns(thread, lock) ∨ lock = free). Let q, given by owns(thread, lock), be an assertion at a control point and let {p}?call stm ?call

def

with p = free for(thread, lock) be the callee observation at the beginning of a synchronized method in the same class. Note that the observation changes the lock value. The interference freedom condition |=L {p ∧ q ∧ interleavable(q, stm)}stm{q } assures invariance of q under the observation stm. The assertions p and q imply thread = thread . The points at p and q can be simultaneously reached by the same thread only if q describes a point waiting for return. This fact is mirrored by the deﬁnition of the interleavable predicate: If q is not at a control point waiting for return, then the antecedent of the condition evaluates to false. Otherwise, after the execution of the built-in augmentation lock := inc(lock) in stm we have owns(thread, lock), i.e., owns(thread , lock), which was to be shown. 11

This condition is not necessary for a minimal proof system, but reduces the number of veriﬁcation conditions.

24

´ E. Abrah´ am et al.

The Cooperation Test. We extend the cooperation test for Javaconc with synchronization and the invocation of the monitor methods. In the previous languages, the assertion comm expressed, that the given statements indeed represent communicating partners. In the current language with monitor synchronization, communication is not always enabled. Thus the assertion comm has additionally to capture enabledness of the communication: In case of a synchronized method invocation, the lock of the callee object has to be free or owned by the caller. This is expressed by z .lock = free ∨ thread(z .lock) = thread, where thread is the caller-thread, and where thread(z .lock) is the ﬁrst component of the lock value, i.e., the thread owning the lock of z . For the invocation of the monitor methods we require that the executing thread is holding the lock. Returning from the wait-method assumes that the thread has been notiﬁed and that the callee’s lock is free. Note that the global invariant is not aﬀected by the object-internal monitor signaling mechanism, which is represented by auxiliary assignments. Deﬁnition 8 (Cooperation Test: Communication). A proof outline satisﬁes the cooperation test for communication, if the conditions of Deﬁnition 6 hold for the statements listed there with the exception of the Call-case, and additionally in the following cases: 1. Call: For all statements {p1 } uret := e0 .m(e); {p2 }!call y 1 := e 1 !call {p3 }wait (or such without receiving a value) in class c with e0 of type c , where method m ∈ / {start, wait, notify, notifyAll} of c is synchronized with body ?call {q 2 } y 2 := e 2 ?call {q3 } stm, formal parameters u, and local variables v except the formal parameters. The callee class invariant is q1 = Ic . The assertion comm is given by E0 (z) = z ∧ (z .lock = free ∨ thread(z .lock) = thread). Furthermore, fcomm is u , v := E(z), Init(v), fobs1 is given by z.y 1 := E 1 (z), and fobs2 is z .y 2 := E 2 (z ). If m is not synchronized, z .lock = free ∨ thread(z .lock) = thread in comm is dropped. 2. Callmonitor : For m ∈ {wait, notify, notifyAll}, comm is given by E0 (z) = z ∧ thread(z .lock) = thread. 3. Returnwait : For {q1 } returngetlock ; {q2 }!ret y 3 := e 3 !ret {q3 } in a wait-method, comm is E0 (z) = z ∧ u = E(z) ∧ z .lock = free ∧ thread ∈ z .notiﬁed. Example 9. Assume the invocation of a synchronized method m of a class c, where m of c has the body stm ?call {thread(lock) = thread} stm ; return. Note that the built-in augmentation in stm sets the lock owner by the assignment lock := inc(lock). Omitting irrelevant details again, the cooperation test requires |=G {true}z .lock := inc(z .lock){thread(z .lock) = thread }, which holds by the deﬁnition of inc.

5

Proving Deadlock Freedom

The previous sections described a proof system which can be used to prove safety properties of Javasynch programs. In this section we show how to apply the proof system to show deadlock freedom.

A Tool-Supported Proof System for Multithreaded Java

25

A system of processes is in a deadlocked conﬁguration, if no one of them is enabled to compute, but not yet all started processes are terminated. A typical deadlock situation can occur, if two threads t1 and t2 both try to gather the locks of two objects z1 and z2 , but in reverse order: t1 ﬁrst applies for access to synchronized methods of z1 , and then for those of z2 , while t2 ﬁrst collects the lock of z2 , and tries to become the lock owner of z1 . Now, it can happen, that t1 gets the lock of z1 , t2 gets the lock of z2 , and both are waiting for the other lock, which will never become free. Another typical source of deadlock situations are threads which suspended themselves by calling wait and which will never get notiﬁed. What kind of Javasynch -statements can be disabled and under which conditions? The important cases, to which we restrict, are – the invocation of synchronized methods, if the lock of the callee object is neither free nor owned by the executing thread, – if a thread tries to invoke a monitor method of an object whose lock it doesn’t own, or – if a thread tries to return from a wait-method, but either the lock is not free or the thread is not yet notiﬁed. To be exact, the semantics speciﬁes method calls to be disabled also, if the callee object is the empty reference. However, we won’t deal with this case; it can be excluded in the preconditions by stating that the callee object is not null. Assume a proof outline with global invariant GI . For a logical variable z of type Object, let I(z) = I[z/this] be the class invariant of z expressed on the global level. Let the assertion terminated(z) express that the thread of z is already terminated. Formally, we deﬁne terminated(z) = q[z/thread][z/this], where q is the postcondition of the run-method of z. For assertions p in z let furthermore blocked(z, z , p) express that the thread of z is disabled in the object z at control point p. Formally, we deﬁne blocked(z, z , p) by = free ∧ thread(e0 .lock) = thread if p is the – ∃v. p[z/thread][z /this] ∧ e0 .lock

precondition of a call invoking a synchronized method of e0 , – ∃v. p[z/thread][z /this] ∧ thread(e0 .lock)

= thread if p is the precondition of a call invoking a monitor method of e0 , – ∃v. p[z/thread][z /this] ∧ (z .lock

= free ∨ z ∈ / z .notiﬁed) if p is the precondition of the return-statement in the wait-method, and – false otherwise, where v is the vector of local variables in the given assertion without thread, and z and z fresh. Let ﬁnally blocked(z, z ) express thatthe thread of object z is blocked in the object z . It is deﬁned by the assertion p∈Ass(z ) blocked(z, z , p), where Ass(z ) is the set of all assertions at control points in z . Now we can formalize the veriﬁcation condition for deadlock freedom:

´ E. Abrah´ am et al.

26

Deﬁnition 9. A proof outline satisﬁes the test for deadlock freedom, if |=G (GI ∧ (9) (∀z. z

= null → (I(z) ∧ = null ∧ blocked(z, z )))))) ∧ (z.started → (terminated(z) ∨ (∃z . z

(∃z. z

= null ∧ z.started ∧ (∃z . z

= null ∧ blocked(z, z )))) → false . The above condition states, that the assumptions that all started processes are terminated or disabled, and that at least one thread is not yet terminated, i.e., that the program is in a deadlocked conﬁguration, lead to a contradiction. Soundness of the above condition, i.e., that the condition indeed assures absence of deadlock, is easy to show. Completeness results directly from the completeness of the proof method. Example 10. In the following example, the assertion owns is as in Example 8, proj (v, i) denotes the ith component of the tuple v, and not owns(thread, lock) is thread

= null ∧ proj(lock, 1)

= thread. Again, the built-in augmentation is not listed in the code. We additionally list instance and local variable declarations type name;, where type name; declares auxiliary variables. We sometimes skip return statements without giving back a value, and write explicitly ∀(z : t).p for quantiﬁcation over t-typed values. The proof outline below deﬁnes two classes, Producer and Consumer, where Producer is the main class. The initial thread of the initial Producer-instance creates a Consumer-instance and calls its synchronized produce method. This method starts the consumer thread and enters a non-terminating loop, producing some results, notifying the consumer, and suspending itself by calling wait. After the producer suspended itself, the consumer thread calls the synchronized consume method, which consumes the result of the producer, notiﬁes, and calls wait, again in a non-terminating loop. For readability, we only list a partial annotation and augmentation, which already implies deadlock freedom. Invariance of the properties listed below has been shown in PVS using an extended augmentation and annotation. Also deadlock freedom has been proven in PVS. def

GI = (∀(p : Producer ).(p = null ∧ ¬p.outside ∧ p.consumer = null) → p.consumer .lock = (null, 0))∧ (∀(c : consumer ).(c = null ∧ c.started) → (c.producer = null ∧ c.producer .started))∧ (∀(c1 : consumer ).(c1 = null → (∀(c2 : consumer ).c2 = null → c1 = c2)) def

IProducer = true def

IConsumer = (lock = (null, 0) ∨ (owns(this, lock ) ∧ started) ∨ owns(producer , lock ))∧ length(wait) ≤ 1 class Producer { Consumer consumer ; boolean outside ; nsync wait () {

{false }

}

A Tool-Supported Proof System for Multithreaded Java

27

nsync run () { Consumer c ; c = newConsumer ; consumer = cnew {c = consumer ∧ ¬outside ∧ consumer = null ∧ consumer = this ∧ thread = this } c . produce () ; outside = (if c = this then outside else true ﬁ)!call {false } } } class Consumer { int buffer ; Producer producer ; nsync wait () { {started ∧ not owns(thread, lock ) ∧ (thread = this ∨ thread = producer )∧ (thread ∈ wait ∨ thread ∈ notiﬁed)} } sync produce () { int i ; = proj (caller , 1)?call i =0; start () ; while ( true ) { // produce i here buffer = i ; {owns(thread, lock )} notify () ; {owns(thread, lock )} wait () }

producer

} nsync run () { {not owns(thread, lock ) ∧ thread = this } consume () ; {false } } sync consume () { int i ; while ( true ) { i = buffer ; // consume i here {owns(thread, lock )} notify () ; {owns(thread, lock )} wait () } } }

Both run-methods have false as postcondition, stating that the corresponding threads don’t terminate. The preconditions of all monitor method invocations express that the executing thread owns the lock, and thus execution cannot be enabled at these control points. The wait-method of Producer-instances is not invoked; we deﬁne false as the precondition of its return-statement, implying that disabledness is excluded also at this control point. The condition for deadlock freedom assumes that there is a thread which is started but not yet terminated, and whose execution is disabled. This thread is either the thread of a Producer-instance, or that of a Consumer-instance. We discuss only the case that the disabled thread belongs to a Producerinstance z diﬀerent from null; the other case is similar. Note that the control

28

´ E. Abrah´ am et al.

of the thread of z cannot stay in the run-method of a Consumer-instance, since the corresponding local assertion implies thread = this, which would contradict the type assumptions. Thus the thread can have its control point prior to the method call in the run-method of a Producer-instance, or in the wait-method of a Consumer-instance. In the ﬁrst case, the corresponding local assertion and the global invariant imply that the lock of the callee is free, i.e., that the execution is enabled, which is a contradiction. In the second case, if the thread of z executes in the wait-method of a Consumer-instance z , the local assertion in wait together with the type assumptions implies z .started ∧ not owns(z, z .lock) ∧ z = z .producer, and that z is either in the wait- or in the notiﬁed-set of z . According to the assumptions of the deadlock freedom condition, also the started thread of z is disabled or terminated; its control point cannot be in a Producer-instance, since that would contradict to the type assumptions. Thus the control of z stays in the run- or in the wait-method of a Consumer-instance; the annotation implies that the instance is z itself. If the control stays in the run-method, then the corresponding local assertion and the class invariant imply that the lock is free, since neither the producer, nor the consumer owns it, which leads to a contradiction, since in this case the execution of the thread of z would be enabled. Finally, if the control of the thread of z stays in the wait-method of z , then the annotation assures that the thread doesn’t own the lock of z ; again, using the class invariant we get that the lock is free. Now, both threads of z and z have their control points in the wait-method of z , and the lock of z is free. Furthermore, both threads are disabled, and are in the wait- or in the notiﬁed set. If one of them is in the notiﬁed set, then its execution is enabled, which is a contradiction. If both threads are in the wait set, then from z

= z we imply that the wait-set of z has at least two elements, which contradicts the class invariant of z . Thus the assumptions lead to a contradiction, which was to be shown.

6

Conclusion

This paper presents a tool-supported assertional proof method for a multithreaded sublanguage of Java including its monitor discipline. This builds on ´ ´ earlier work ([AMdB00] and especially [AMdBdRS02]). The underlying theory, the proof rules, their soundness and completeness, and the tool support are ´ presented in greater detail in [AdBdRS03]. Related Work. As far as proof-systems and veriﬁcation support for objectoriented programs is concerned, research mostly concentrated on sequential languages. Early examples of Hoare-style proof systems for a sequential objectoriented languages are [dF95] and [LW90,LW94]. With Java’s rise to prominence, research more intensively turned to (sublanguages of) Java, as opposed of capturing object-oriented language features in the abstract. In this direction, jml [LBR98,LCC+ 03] has emerged as some kind of common ground for asserting Java programs. Another trend is to oﬀer mechanized proof support for the languages.

A Tool-Supported Proof System for Multithreaded Java

29

For instance, Poetzsch-Heﬀter and M¨ uller [PHM99,PH97b,PH97a,PHM98] develop a Hoare-style programming logic presented in sequent formulation for a sequential kernel of Java, featuring interfaces, subtyping, and inheritance. Translating the operational and the axiomatic semantics into the HOL theorem prover allows a computer-assisted soundness proof. The work in the Loop-project (cf. e.g. [Loo01,JvdBH+ 98]) also concentrates on a sequential subpart of Java, translating the proof-theory into PVS and Isabelle/HOL. The work [RW00,RHW01] use a modiﬁcation of the object constraint language OCL as assertional language to annotate UML class diagrams and to generate proof conditions for Java-programs. The work [BFG02] presents a model checking algorithm and its implementation in Isabelle/HOL to check type correctness of Java bytecode. In [vO01] a large subset of JavaCard, including exception handling, is formalized in Isabelle/HOL, and its soundness and completeness is shown within the theorem prover. The work in [AL97] presents a Hoare-style proof-system for a sequential object-oriented calculus [AC96]. Their language features heap-allocated objects (but no classes), side-eﬀects and aliasing, and its type system supports subtyping. Furthermore, their language allows nested statically let-bound variables, which requires a more complex semantical treatment for variables based on closures, and ultimately renders their proof-system incomplete. Their assertion language is presented as an extension of the object calculus’ language of type and analogously, the proof system extends the type derivation system. The close connection of types and speciﬁcations in the presentation is exploited in [TH02] for the generation of veriﬁcation conditions. Work on proof systems for parallel object-oriented languages or in particular the multithreading aspects of Java is more scarce. [dB99] presents a sound and complete proof system in weakest precondition formulation for a parallel object-based language, i.e., without inheritance and subtyping, and also without reentrant method calls. Later work [PdB03,dBP03,dBP02] includes more features, especially catering for Hoare logic for inheritance and subtyping. A survey about monitors in general, including proof-rules for various monitor semantics, can be found in [BFC95]. Future Work. As ti future work, we plan to extend Javasynch by further constructs, like inheritance, subtyping, and exception handling. Dealing with subtyping on the logical level requires a notion of behavioral subtyping [Ame89].

Acknowledgments We thank Cees Pierik for fruitful discussions and suggestions, and furthermore Tim D’Avis for careful reading and commenting on an earlier version of this document.

References AC96.

Mart´ın Abadi and Luca Cardelli. A Theory of Objects. Monographs in Computer Science. Springer, 1996.

30

´ E. Abrah´ am et al.

´ AdBdRS03.

´ Erika Abrah´ am, Frank S. de Boer, Willem-Paul de Roever, and Martin Steﬀen. A Hoare logic for monitors in Java. Techical report TR-ST03-1, Lehrstuhl f¨ ur Software-Technologie, Institut f¨ ur Informatik und Praktische Mathematik, Christian-Albrechts-Universit¨ at zu Kiel, April 2003. AF99. Jim Alves-Foss, editor. Formal Syntax and Semantics of Java, volume 1523 of LNCS State-of-the-Art-Survey. Springer-Verlag, 1999. AFdR80. K. R. Apt, N. Francez, and W.-P. de Roever. A proof system for communicating sequential processes. ACM Transactions on Programming Languages and Systems, 2:359–385, 1980. AL97. Mart´ın Abadi and K. Rustan M. Leino. A logic of object-oriented programs. In Michel Bidoit and Max Dauchet, editors, Proceedings of TAPSOFT ’97, volume 1214 of Lecture Notes in Computer Science, pages 682–696, Lille, France, April 1997. Springer-Verlag. An extended version of this paper appeared as SRC Research Report 161 (September 1998). ´ ´ AMdB00. Erika Abrah´ am-Mumm and Frank S. de Boer. Proof-outlines for threads in Java. In Catuscia Palamidessi, editor, Proceedings of CONCUR 2000, volume 1877 of Lecture Notes in Computer Science. Springer-Verlag, August 2000. ´ ´ AMdBdRS02. Erika Abrah´ am-Mumm, Frank S. de Boer, Willem-Paul de Roever, and Martin Steﬀen. Veriﬁcation for Java’s reentrant multithreading concept. In Mogens Nielsen and Uﬀe H. Engberg, editors, Proceedings of FoSSaCS 2002, volume 2303 of Lecture Notes in Computer Science, pages 4–20. Springer-Verlag, April 2002. A longer version, including the proofs for soundness and completeness, appeared as Technical Report TR-ST-02-1, March 2002. Ame89. Pierre America. A behavioural approach to subtyping in objectoriented programming languages. 443, Phillips Research Laboratories, January/April 1989. And00. Gregory R. Andrews. Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, 2000. BdBdRG03. Marcello Bosangue, Frank S. de Boer, Willem-Paul de Roever, and Susanne Graf, editors. Proceedings of the First International Symposium on Formal Methods for Components and Objects (FMCO 2002), Leiden, Lecture Notes in Computer Science. Springer-Verlag, 2003. BFC95. Peter A. Buhr, Michel Fortier, and Michael H. Coﬃn. Monitor classiﬁcation. ACM Computing Surveys, 27(1):63–107, March 1995. BFG02. David Basin, Stefan Friedrich, and Marek Gawkowski. Veriﬁed bytecode model checkers. In Victor A. Carre˜ no, C´esar A. Mu˜ noz, and Soﬁ`ene Tahar, editors, Theorem Proving in Higher Order Logics (TPHOLs’02), volume 2410 of Lecture Notes in Computer Science, pages 47–66. Springer-Verlag, August 2002. CKRW99. P. Cenciarelli, A. Knapp, B. Reus, and M. Wirsing. An event-based structural operational semantics of multi-threaded Java. In Alves-Foss [AF99], pages 157–200. dB99. Frank S. de Boer. A WP-calculus for OO. In Wolfgang Thomas, editor, Proceedings of FoSSaCS ’99, volume 1578 of Lecture Notes in Computer Science, pages 135–156. Springer-Verlag, 1999.

A Tool-Supported Proof System for Multithreaded Java dBP02.

dBP03.

dF95. Flo67. GJS96. HJ89. Hoa69. Hui01. JKW03. JvdBH+ 98.

LBR98. LCC+ 03. LG81. Loo01. LW90.

LW94.

OG76.

31

Frank S. de Boer and Cees Pierik. Computer-aided speciﬁcation and veriﬁcation of annotated object-oriented programs. In Bart Jacobs and Arend Rensink, editors, Proceedings of the Fifth International Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS 2002), volume 209, pages 163–177. Kluwer, 2002. Frank S. de Boer and Cees Pierik. Towards an environment for the veriﬁcation of annotated object-oriented programs. Technical report UU-CS-2003-002, Institute of Information and Computing Sciences, University of Utrecht, January 2003. C. C. de Figueiredo. A proof system for a sequential object-oriented language. Technical Report UMCS-95-1-1, University of Manchester, 1995. Robert W. Floyd. Assigning meanings to programs. In J. T. Schwartz, editor, Proc. Symp. in Applied Mathematics, volume 19, pages 19–32, 1967. J. Gosling, B. Joy, and G. Steele. The Java Language Speciﬁcation. Addison-Wesley, 1996. C. A. R. Hoare and Cliﬀ B. Jones, editors. Essays in Computing Science. International Series in Computer Science. Prentice Hall, 1989. C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM, 12:576–580, 1969. Also in [HJ89]. Marieke Huisman. Java Program Veriﬁcation in Higher-Order Logic with PVS and Isabelle. PhD thesis, University of Nijmegen, 2001. Bart Jacobs, Joseph Kiniry, and Martijn Warnier. Java program veriﬁcation challenges. In Bosangue et al. [BdBdRG03]. Bart Jacobs, Jan van den Berg, Marijke Huisman, M. van Barkum, Ulrich Hensel, and Hendrik Tews. Reasoning about classes in Java (preliminary report). In Object Oriented Programing: Systems, Languages, and Applications (OOPSLA) ’98, pages 329–340. ACM, 1998. in SIGPLAN Notices. Gary T. Leavens, Albert L. Baker, and Clyde Ruby. JML: a Java modelling language. In Formal Underpinnings of Java Workshop (at OOPSLA’98), 1998. G. T. Leavens, Y. Cheon, C. Clifton, C. Ruby, and D. R. Cok. How the design of jml accommodates both runtime assertion checking and formal veriﬁcation. In Bosangue et al. [BdBdRG03]. G. M. Levin and D. Gries. A proof technique for communicating sequential processes. Acta Informatica, 15(3):281–302, 1981. The LOOP project: Formal methods for object-oriented systems. http://www.cs.kun.nl/˜bart/LOOP/, 2001. Gary T. Leavens and William E. Wheil. Reasoning about objectoriented programs that use subtypes. In Object Oriented Programing: Systems, Languages, and Applications (OOPSLA) ’90 (Ottawa, Canada), pages 212–223. ACM, 1990. Extended Abstract. Gary T. Leavens and William E. Wheil. Speciﬁcation and veriﬁcation of object-oriented programs using supertype abstraction. Acta Informatica, 1994. An expanded version appeared as Iowa State Unversity Report, 92-28d. Susan Owicki and David Gries. An axiomatic proof technique for parallel programs. Acta Informatica, 6(4):319–340, 1976.

32 ORS92.

PdB03.

PH97a.

PH97b. PHM98.

PHM99.

RHW01.

RW00. SSB01. TH02.

vO01. vON02.

WK99.

´ E. Abrah´ am et al. S. Owre, J. M. Rushby, and N. Shankar. PVS: A prototype veriﬁcation system. In D. Kapur, editor, Automated Deduction (CADE-11), volume 607 of Lecture Notes in Computer Science, pages 748–752. SpringerVerlag, 1992. Cees Pierik and Frank S. de Boer. A syntax-directed Hoare logic for object-oriented programming concepts. Technical report UU-CS-2003010, Institute of Information and Computing Sciences, University of Utrecht, 2003. Arnd Poetzsch-Heﬀter. A logic for the veriﬁcation of object-oriented programs. In Rudolf Berghammer and Friedeman Simon, editors, Proceedings of Programming Languages and Fundamentals of Programming, pages 31–42. Institut f¨ ur Informatik und Praktische Mathematik, Christian-Albrechts-Universit¨ at Kiel, November 1997. Bericht Nr. 9717. Arnd Poetzsch-Heﬀter. Speciﬁcation and Veriﬁcation of ObjectOriented Programs. Technische Universit¨ at M¨ unchen, January 1997. Habilitationsschrift. Arnd Poetzsch-Heﬀter and Peter M¨ uller. Logical foundations for typed object-oriented languages. In David Gries and Willem-Paul de Roever, editors, Proceedings of PROCOMET ’98. International Federation for Information Processing (IFIP), Chapman & Hall, 1998. Arnd Poetzsch-Heﬀter and Peter M¨ uller. A programming logic for sequential Java. In S.D. Swierstra, editor, Programming Languages and Systems, volume 1576 of Lecture Notes in Computer Science, pages 162–176. Springer, 1999. Bernhard Reus, Rolf Hennicker, and Martin Wirsing. A Hoare calculus for verifying Java realizations of OCL-constrained design models. In H. Hussmann, editor, Fundamental Approaches to Software Engineering, volume 2029 of Lecture Notes in Computer Science, pages 300–316. Springer-Verlag, 2001. Bernhard Reus and Martin Wirsing. A Hoare-logic for object-oriented programs. Technical report, LMU M¨ unchen, 2000. Robert St¨ ark, Joachim Schmid, and Egon B¨ orger. Java and the Java Virtual Machine. Springer-Verlag, 2001. Francis Tang and Martin Hofmann. Generation of veriﬁcation conditions for Abadi and Leino’s logic of objects (extended abstract). In Proceedings of the 9th International Workshop on Foundations of ObjectOriented Languages (FOOL’02), 2002. A longer version is available as LFCS technical report. David von Oheimb. Hoare logic for Java in Isabelle/HOL. Concurrency and Computation: Practice and Experience, 13(13):1173–1214, 2001. David von Oheimb and Tobias Nipkow. Hoare logic for NanoJava: Auxiliary variables, side eﬀects and virtual methods revisited. In L.H. Eriksson and P.-A. Lindsay, editors, Proceedings of Formal Methods Europe: Formal Methods – Getting IT Right (FME’02), volume 2391 of Lecture Notes in Computer Science, pages 89–105. Springer-Verlag, 2002. Jos B. Warmer and Anneke G. Kleppe. The Object Constraint Language: Precise Modeling With Uml. Object Technology Series. AddisonWesley, 1999.

Abstract Behavior Types: A Foundation Model for Components and Their Composition Farhad Arbab CWI, Amsterdam, The Netherlands [email protected]

Abstract. The notion of Abstract Data Type (ADT) has served as a foundation model for structured and object oriented programming for some thirty years. The current trend in software engineering toward component based systems requires a foundation model as well. The most basic inherent property of an ADT, i.e., that it provides a set of operations, subverts some highly desirable properties in emerging formal models for components that are based on the object oriented paradigm. We introduce the notion of Abstract Behavior Type (ABT) as a higherlevel alternative to ADT and propose it as a proper foundation model for both components and their composition. An ABT deﬁnes an abstract behavior as a relation among a set of timed-data-streams, without specifying any detail about the operations that may be used to implement such behavior or the data types it may manipulate for its realization. The ABT model supports a much looser coupling than is possible with the ADT’s operational interface, and is inherently amenable to exogenous coordination. We propose that both of these are highly desirable, if not essential, properties for models of components and their composition. To demonstrate the utility of the ABT model, we describe Reo: an exogenous coordination language for compositional construction of component connectors based on a calculus of channels. We show the expressive power of Reo, and the applicability of ABT, through a number of examples.

1

Introduction

An Abstract Data Type (ADT) deﬁnes an algebra of operations with mathematically well-deﬁned semantics, without specifying any detail about the implementation of those operations or the data structures they operate on to realize them. As such, ADT is a powerful abstraction and encapsulation mechanism that groups data together with their related operations into logically coherent and loosely-dependent entities, such as objects, yielding better structured programs. ADT has served as a foundation model for structured and object oriented programming for some thirty years. The immense success of object oriented techniques has distracted proper attention away from critical evaluation of some of its underpinning concepts from the perspective of their utility for components. We propose that the most basic inherent property of an ADT, i.e., that it provides a set of operations in F.S. de Boer et al. (Eds.): FMCO 2002, LNCS 2852, pp. 33–70, 2003. c Springer-Verlag Berlin Heidelberg 2003

34

F. Arbab

its interface, subverts some highly desirable properties in emerging models for component based systems. This is already evident in the current attempts at extending the object oriented models into the realm of components (see, e.g., Sections 3 and 5). We introduce the notion of Abstract Behavior Type (ABT) as a higher-level alternative to ADT and propose it as a proper foundation model for both components and their composition. An ABT deﬁnes an abstract behavior as a relation among a set of timed-data-streams, without specifying any detail about the operations that may be used to implement such behavior or the data types it may manipulate for its realization. In contrast with the algebraic underpinnings of the ADT model, the (generally) inﬁnite streams that are the elements of behavior in the ABT model naturally lend themselves to the coalgebraic techniques and the coinduction reasoning principle that have recently been developed as a general theory to describe the behavior of dynamic systems. The ABT model supports a much looser coupling than is possible with ADT and is inherently amenable to exogenous coordination. We propose that both of these are highly desirable, if not essential, properties for components and their composition. In our view, a component based system consists of component instances and their connectors (i.e., the “glue code”), both of which are uniformly modeled as ABTs. Indeed, the only distinction between a component and a connector is just that a component is an atomic ABT whose internal structure is unknown, whereas a connector is known to be an ABT that is itself composed out of other ABTs. As a concrete instance of the application of the ABT model, we describe Reo: an exogenous coordination model wherein complex coordinators, called “connectors” are compositionally built out of simpler ones [3,4]. Reo can be used as a glue language for compositional construction of connectors that orchestrate component instances in a component based system. We demonstrate the surprisingly expressive power of ABT composition in Reo through a number of examples. The rest of this paper is organized as follows. In Section 2 we motivate our view of components and their composition as a conceptual model at a higher level of abstraction than objects and their composition. Section 3 contains a brief overview of some related work. We review the formal notion of abstract data types in Section 4, and elaborate on its links with and implications on object oriented programming in Section 5. We argue that some of these implications impede the ability of component models based on the object oriented paradigm to support ﬂexible composition and exogenous coordination, both of which, we propose, are highly desirable properties in component based systems. Section 6 is an informal description of our component model, and in Section 7 we describe its accompanying model of behavior. Section 8 is an introduction to Abstract Behavior Types and their composition. In Section 9 we show how channels, connectors, and their composition in Reo are easily expressed as ABTs and their composition. Finally, we close with our concluding remarks in Section 10.

Abstract Behavior Types: A Foundation Model for Components

2

35

A Component Manifesto

The bulk of the work on component based systems is primarily focused on what components are and how they are to be constructed. Relatively little attention has been paid to alternative models and languages for composing components into (sub)systems, which is typically considered to be the purpose of the so-called glue code, assumed to be written in some scripting language. Clearly, components and their composition are not independent of one another: explicitly emphasizing one deﬁnes or at least constrains the other as well, if only implicitly. A conspicuous driving force behind the upsurge of interest and activity in component based software is the recognition that the object oriented paradigm is not the silver-bullet that some of its over-zealous advocates purported it to be. Nevertheless, presently, the dominant view of what components are or should be reﬂects a prominent object oriented legacy: components are fortiﬁed collections of classes and/or objects, with very similar interfaces. It follows that the interactions among and the composition of components must use mechanisms very similar to those for interactions among and composition of classes and objects. Thus, the method invocation semantics of message passing in object oriented programming becomes the crux of the component composition mechanisms in scripting languages. This approach to components “solves” some of the problems that are rooted in the inadequacies of the object oriented paradigm simply by shifting them elsewhere. For instance, the relatively tight coupling that must be established between a caller and a callee pair of objects indeed disappears as a concern at the intra-component level when the two objects reside in diﬀerent component instances, but becomes an issue to be addressed in the glue code and its underlying middleware used to compose those components. As long as components and their interfaces are essentially the same as objects and their interfaces, the (scripting) programs that constitute the glue code end up to be inherently no different than other object oriented software. In complex systems, the body of such specialized glue code can itself grow in size, complexity, intricacy, fragility, and rigidity, rendering the system hard to evolve and maintain, in spite of the fact that this inﬂexible code wraps and connects otherwise reusable, upgradeable, and replaceable components. An alternative view of components emerges if we momentarily ignore how they are made or even what they are made of, emphasizing instead what we want to do with them. Beyond fashionable jargon, hype, and merely technical idiosyncrasies, if there is to be any conceptual substance behind the term “component” deserving its minting, it must be that components are less interdependent and are easier and more ﬂexible to compose than objects and classes. The deﬁnition of a class or an object speciﬁes the methods it oﬀers to other entities, and the method calls within the code of its methods determine the services and entities it requires to work. This results in a rather tight semantic interdependence among objects/classes and grants each individual a signiﬁcant degree of control over precisely how it is composed with other classes or objects. In contrast to objects and classes, it is highly desirable for components to be semantically independent of one another and internally impose no restrictions on

36

F. Arbab

the other components they compose with. This yields a level of composition ﬂexibility that is not possible with objects and classes1 and which is a prerequisite for another highly desirable property in component based systems: we would like for the whole (system) to be more than the mere sum of its (component) parts. This implies that not only it should be generally possible to produce diﬀerent systems by composing the same set of components in diﬀerent ways, but also that the difference between two systems composed out of the same set of components (i.e., the diﬀerence between the “more” than the “sum of the parts” in each system) must arise out of the actual rules that comprise their two diﬀerent compositions, i.e., their glue code. The signiﬁcance of the latter point is that it requires the glue code to contribute to the semantics of the whole system well beyond the mere so-called “wiring-standard-level” support provided by the current popular middleware and component based technologies. On the other hand, we intuitively expect glue code to be void of any application-domain speciﬁc functionality: its job is merely to connect components, facilitating their communication and coordinating their interactions, not to perform any application-domain speciﬁc computation. This leads to a subtlety regarding the interaction between glue code and components which fundamentally impacts both. If the contribution of the glue code to the behavior of a composed system is no more than connecting its components, facilitating their communication and coordinating their interactions, then the diﬀerence between the behavior of two systems composed out of the same set of components can arise not out of any application-domain speciﬁc computation (and certainly not out of the components), but only out of how the glue code connects and coordinates these components to interact with one another. Since glue code is external to the components it connects, this implies that (1) the components must be amenable to external coordination control and (2) the glue code must contain constructs to provide such external coordination. The ﬁrst implication constrains the mechanisms through which components can interact with their environment. The second implication means that the glue code language must incorporate an exogenous coordination model [2]. Finally, if glue code is to have its own non-trivial semantics in a composed system, it is highly desirable both for the glue code itself to be piece-wise explicitly identiﬁable, and for the semantics of each of its pieces to be independent of the semantics of the speciﬁc components that it composes. This promotes the recognition of the glue code as an identiﬁable, valuable software commodity, emphasizes the importance of its reusability, and advocates glue code construction through composition of reusable glue code pieces. The notion of compositional construction of glue code out of smaller, reusable pieces of glue code all but eliminates the conceptual distinctions between components and glue code. This behooves us to ﬁnd conceptual models and formal 1

Observe that generally speaking, it is the code for the methods of an object that determines the other objects it “composes with” to function properly. Thus, objects/classes “decide for themselves” how they compose with each other and their composition generally cannot be determined or inﬂuenced from outside.

Abstract Behavior Types: A Foundation Model for Components

37

methods for component based systems wherein the same rules for compositional construction indiscriminately apply to both components as well as their glue code connectors. In such a model, the (perhaps somewhat subjective) distinction between components and their (pieces of glue code) connectors still makes practical sense: although they are indistinguishable when used as primitives to compose more complex constructs, components and connectors are still diﬀerent in that components are black-box primitives whose internal structures are invisible, whereas the internal structure of a connector shows that it, in turn, is constructed out of other (connector and/or component) primitives according to the same rules of composition.

3

Background and Related Work

In popular models of components (e.g., Enterprise Java Beans [36,18], CORBA [55,16], and DCOM [21]) component instances are fortiﬁed (collections of) objects. Consequently, they typically use variants of message passing with the semantics of method invocation for inter-component communication. The tight coupling inherent in the method call semantics is more appropriate for intracomponent communication. In contrast, inter-component communication invariably requires a minimum level of “control from the outside” of the participating components. In order to break the tight coupling induced by the method call semantics and reduce the interdependence of components on each other, the underlying middleware that supports these component models provides mechanisms or entities (such as the ORB in CORBA) to intercept inter-component messages. Messages may be intercepted to, for instance, provide services (e.g., binding and name servers), enforce imposed constraints (e.g., suppress certain messages in certain states), ensure protocols, and/or enact assigned roles. One way or the other, the middleware’s intervention loosens the otherwise tight coupling that would be imposed by targeted active messages (i.e., messages with methodinvocation semantics) and furthermore, enforces a certain restricted form of coordination from outside the components. Coordination languages [19,45] oﬀer an alternative for inter-component communication, as exempliﬁed by JavaSpaces in the Jini architecture [31,44,35]. They impose a stricter sense of temporal and spacial decoupling that supports a looser inter-component semantic dependency, compared with the method invocation semantics of message passing in object oriented paradigms. Most common component models deﬁne components as reusable binary units of software with interfaces that have no more than a syntactic content. This view of components enforces information hiding in only a rather primitive way: the good practice discipline of using questionably suggestive symbolic names in component interfaces non-withstanding, such an interface does not reveal any of the externally relevant semantics of the contents of its component. Such component models cannot support (semi-)formal speciﬁcation/veriﬁcation of their external behavior. A broader deﬁnition of components is oﬀered by the Eiﬀel language [37,38,20]: components are client-oriented software with the desirable property that a com-

38

F. Arbab

ponent, x , can be used by other programs that do not need to be known to x . This property is supported in Eiﬀel through formal speciﬁcation techniques which include pre- and post-conditions and invariants. In general, this notion of components requires enhanced speciﬁcation and veriﬁcation techniques, as also observed by Hennicker and Wirsing [57,24]. Our notion of components [9,6,17] uses channels as the basic intercomponent communication mechanism. A channel is a point-to-point medium of communication with its own unique identity and two distinct ends. A channel supports transfer of passive data only; no transfer of control (e.g., procedure calls, exchange of pointers to internal objects/entities) can take place through a channel. Using channels as the only means of inter-component communication allows a clean, ﬂexible, and expressive model for construction of the glue code for component composition which also supports exogenous coordination. Synchronous channels are the basic primitives in π-calculus [39,40]. Some of the variants of π-calculus and its asynchronous versions [54] have been used in models proposed for component interaction and composition. Notably, Piccola [43] is an experimental component composition language based on a higherorder version of the asynchronous π-calculus, extended with explicit name-spaces called forms. Forms in Piccola provide a uniﬁed mechanism to address such aspects of component composition as styles, scripts, and glue code. The agents and channels provided by Piccola’s underlying calculus support the coordination aspect of component composition. In contrast to such calculi, our notion of channel is very general and we speciﬁcally allow a variety of diﬀerent channel types (even user-deﬁned ones) to be used simultaneously and composed together. This diﬀerentiates our model from the way channels are used in virtually all other channel-based models, which typically allow only one or at most a small number of simple predeﬁned channel types. Speciﬁcally, our liberal notion of channels, the potency that our model derives from mixing and composing channels of diﬀerent types, and their consequent harmonious combination of synchrony and asynchrony are unique. For instance, these features of our model are in sharp contrast with the use of channels in the Ptolemy project [15,34,33] which ascribes a single interpretation for its connecting channels in each context. Asynchronous channels form the basis of the dataﬂow architecture for networks of components as proposed and formally investigated by Broy and his group [13,25]. In this architectural model, large systems can be realized, allowing programmers to easily understand the input/output behavior of a system as the composition of the behavior of its individual components. Our model of component composition is fundamentally diﬀerent than (even dynamic) dataﬂow models because it (1) supports a much wider and more general notion of channels and diﬀerent channel types; and (2) introduces the notion of channel composition as the construct through which channels are connected to other channels, forming higher level and more sophisticated connectors for component composition.

Abstract Behavior Types: A Foundation Model for Components

4

39

Abstract Data Types

Formally, an ADT is a triplet S, O, A, where S is a set of sorts denoting the required types, O is a set of operators over S, and A is a set of axioms written as algebraic equations deﬁning the results of various combinations of operations in O on data items of various types in S. Stack

Queue

S: stack , data, boolean

S: queue, data, boolean

O: top(s) → d pop(s) → s push(s, d ) → s empty(s) → b

O: ﬁrst(q) → d deq(q) → q enq(q, d ) → q empty(q) → b

A: empty(λ) = true A: empty(λ) = true empty(push(s, d )) = false empty(enq(q, d )) = false top(push(s, d ) = d ﬁrst(enq(λ, d )) = d pop(push(s, d ) = s ﬁrst(enq(enq(q, d1 ), d2 )) = ﬁrst(enq(q, d1 )) deq(enq(λ, d )) = λ pop(λ) = 1 pop(1 ) = 1 deq(enq(enq(q, d1 ), d2 )) = enq(deq(enq(q, d1 ), d2 ) top(λ) = 2 deq(λ) = 1 deq(1 ) = 1 ﬁrst(λ) = 2 Fig. 1. Abstract Data Types for stack and queue.

For example, Figure 1 shows the formal ADT deﬁnitions for the two common data types stack and queue, in separate columns. The set S contains stack , data, and boolean types for stack, and queue, data, and boolean types for queue. We use s, q, d , and b to represent items of types stack , queue, data, and boolean, respectively. Furthermore, in the stack column in this ﬁgure λ is an item of type stack representing the empty stack, and likewise in the queue column λ is an item of type queue representing the empty queue. Similarly, in each column 1 and 2 are special error values of their respective types. The set O in each column deﬁnes the signature of four operations. For the case of the stack, top(s) is expected to produce the data item at the top of the stack s; pop(s) is expected to produce the stack obtained by removing the data item at the top of the stack s; push(s, d ) is expected to produce a stack obtained by pushing the data item d on top of the stack s; and empty(s) is expected to produce a boolean indicating whether or not the stack s is empty. For the case of queue, ﬁrst(q) is expected to produce the ﬁrst data item at the head of the queue q; deq(q) is expected to produce the queue obtained by removing the ﬁrst data item at the head of the queue q (dequeue); enq(q, d ) is expected to produce a queue obtained by adding the data item d to the tail end of the queue

40

F. Arbab

q (enqueue); and empty(q) is expected to produce a boolean indicating whether or not the queue q is empty. Of course, the set O contains only the signatures of these operations and as such it is void of any formal hint of what they (are expected to) do. It is the set of axioms, A, that formally deﬁnes the semantics of the operations in O in terms of their mutual eﬀects on each other. In the case of the stack, the two axioms for the empty operation state that (1) empty(λ) = true, and (2) empty applied to a stack obtained from a push operation on any stack yields false. The top axioms state that (1) top applied to the empty stack yields an error (2 ), and (2) top applied to a stack obtained from pushing the data item d onto some other stack, yields d . The pop axioms state that (1) popping a stack obtained from pushing a data item onto some other stack, s, yields s; (2) popping an empty stack yields an error (1 ); and (3) popping this error value yields the same error value. Any stack is canonically represented as a sequence of push operations that add data items on the result of their preceding push, starting with the empty stack, e.g., push(push(push(push(λ, d1 ), d2 ), d3 ), d4 ). An expression that cannot be transformed into such a cannonical form, e.g., push(push(pop(pop(push(λ, d1 ))), d2 ), d3 ), is not a legal stack. Our stack axioms leave empty(1 ) and top(1 ) undeﬁned; alternatively, we can explicitly deﬁne them as errors too. Many of the queue axioms are analogous to their respective stack axioms. The axioms for ﬁrst and deq are a bit more interesting. Any queue is canonically represented as a sequence of enq operations that add data items on the result of their preceding enq, starting with the empty queue; e.g., enq(enq(enq(enq(λ, d1 ), d2 ), d3 ), d4 ). The ﬁrst axioms state that to ﬁnd the ﬁrst element in a queue, we must “peel” it away until we reach the empty queue, at which point we obtain the ﬁrst data item at the head of the queue. Thus: ﬁrst(enq(enq(enq(enq(λ, d1 ), d2 ), d3 ), d4 )) = ﬁrst(enq(enq(enq(λ, d1 ), d2 ), d3 )) = ﬁrst(enq(enq(λ, d1 ), d2 )) = ﬁrst(enq(λ, d1 )) = d1 Analogously, deq peels away the canonical representation of a queue, but it also reconstructs it as it moves inside. For instance: deq(enq(enq(enq(enq(λ, d1 ), d2 ), d3 ), d4 )) = enq(deq(enq(enq(enq(λ, d1 ), d2 ), d3 )), d4 ) = enq(enq(deq(enq(enq(λ, d1 ), d2 )), d3 ), d4 ) = enq(enq(enq(deq(enq(λ, d1 )), d2 ), d3 ), d4 ) = enq(enq(enq(λ, d2 ), d3 ), d4 ) These examples show that an ADT deﬁnes a data type in terms of the operations on that data type and how they mutually aﬀect each other. It abstracts away from the implementation of those operations and the data structures they manipulate. The semantics of an ADT is given as algebraic equations. The strong

Abstract Behavior Types: A Foundation Model for Components

41

conceptual link between abstract data types and object oriented programming stems from the common manner in which they associate data and the operations that manipulate them together. The ADT for a type, T , deﬁnes all operations applicable to entities of type T . It encapsulates the representation of T and the implementation of its operations. This prevents manipulation of the entities of type T in any way other than through its own deﬁned operations.

5

ADT and Object Oriented Programming

Their common aspiration to (1) encapsulate data structures behind operations that manipulate them, and (2) hide the details of those operations as well, has made ADT a suitable foundation model for object oriented programming. An ADT can be seen as a formal description of the interface of an object/class. This encapsulation signiﬁcantly loosens the coupling between the implementation of an ADT (or object/class) and other code that can use it only through its prescribed operations. The operational interface of an ADT (or object/class) also readily supports extensibility in the form of polymorphism. Extensibility in object oriented programming typically goes beyond mere polymorphism, through some form of inheritance that gives rise to object/class hierarchies. Although a formal semantics of its operations is an integral part of the deﬁnition of an ADT, object/class interfaces in object oriented languages are purely syntactic and contain no semantics. Moreover, the explicit deﬁnition of the set of all sorts (both provided and required) by an ADT has no correspondence in the object/class interface deﬁnitions in main-stream object oriented languages: they do not mention what their respective objects/classes require, but specify only the operations that they provide. The diﬀerences between the ADT model and object oriented programming give rise to a number of problems that have already been discussed in the literature. Some counter-measures for problems such as the conﬂict between inheritance and encapsulation [56], the purely syntactic nature of interfaces, and their asymmetric speciﬁcation of oﬀered/required services, have been integrated in the design of certain more advanced object oriented languages and component models. What has not been explored so explicitly and extensively in the literature is how message passing in the object oriented paradigm aﬀects software composition and what alternative mechanisms can be used in its place for components. The method invocation semantics of object oriented message passing implies a rather tight semantic coupling between the caller and callee pairs of objects. By this semantics, if an object c sends a message m(p) to another object e, then c is invoking the method m of e with the actual parameters p. For this to happen: – c must know (how to ﬁnd) e; – c must know the syntax and the semantics of the method m of e; – e must (pretend to) perform the activated method m on parameters p, and return its result to c upon its completion (the “pretense” refers to when e delegates the actual execution of m to a third object); and

42

F. Arbab

– c typically suspends between its sending of m and the receiving of its (perhaps null) result. Not only this “rendezvous semantics” is far from trivial, it is still susceptible to signiﬁcantly diﬀerent and mutually incompatible variations (e.g., with synchronous vs. asynchronous message passing, active vs. passive objects, etc.). Underneath the precise semantics of this rendezvous and its various incarnations in diﬀerent object oriented models, is a strong conceptual link with ADT. By its virtue of providing a set of operations, all that one can do with an ADT is to perform one of its operations. Similarly, the fact that an object provides a set of methods in its interface means that one can do nothing with an object but to invoke those methods. This operational interface (of objects or ADTs) induces an asymmetric, unidirectional semantic dependency of users (of operations) on providers (of those operations). On the one hand, the operations provided by an ADT (or object) can be used by any other entity (that has access to it). On the other hand, an ADT internally decides what operation of what other ADT to perform. This puts users and providers in asymmetric roles. Users internally make the decisions on what operations are to be performed, and generally rely on some speciﬁc semantics that they expect of these operations, while it is left to be the responsibility of the providers to carry out the decisions made by the users to satisfy their expectations. Far from a universal pitfall, it can even be argued that the presumed level of intimacy required among a set of objects composed together through message passing, is an advantage in building individual components. However, at the inter-component level, such intimacy subverts independence of components, contributes to breaking of their encapsulation, and leads to a level of interdependence among components that is no looser than that among objects within a component.

6

A Bland Notion of Components

Instead of relying on targeted active messages for inter-component communication, our component model allows a component instance to exchange only untargeted, passive messages with its environment. Passive messages contain only data and carry no control information (e.g., imply no method invocation). Not implying the exchange of any control information makes passive messages more abstract and more ﬂexible than active messages. For instance, because no form of “call” is implied, the receiver of a message need not interpret the message as an operation that it must perform. The receiver of a message is not even obligated to reply. Consequently, the sender does not necessarily suspend waiting for a result either. Untargeted messages break the asymmetry between senders and receivers that is inherent in models that use targeted messages. With targeted messages, the knowledge of who the receiver of a message is, or at least how it can be identiﬁed, must be contained in its sender. The receiver of a message, on the other hand, is not required to know anything about its sender beforehand: it

Abstract Behavior Types: A Foundation Model for Components

43

is prepared to receive messages “from its environment” not from any speciﬁc sender. This asymmetry makes the sender of a message semantically dependent on (properties and the scheme used to identify) its receiver. This inherent semantic dependency stiﬂes exogenous coordination by severely restricting the ability of a third party to, e.g., set up the interaction of such a sender with a receiver of its own choosing instead of the one prescribed by the sender. With untargeted messages, both senders and receivers symmetrically exchange messages only with their environment, not with any pre-speciﬁed entity. In contrast to the more sophisticated mechanisms necessary for exchanging targeted passive messages, or even more sophisticated ones to support (remote) method invocation for active messages, the mechanism necessary for exchanging untargeted passive messages essentially supports only the mundane I/O primitives: an untargeted message itself is merely some passive data that an entity exchanges with its environment; “sending” such a message is just a write operation; and “receiving” it is just a “read” operation. The I/O operations read and write are performed by a component instance on “contact points” that are recognized by its environment for the purpose of information exchange. We refer to these contact points as the ports of a component instance. Without loss of generality, we assume ports are unidirectional, i.e., the information ﬂows through a port in one direction only: either from the environment into its component instance (through read) or from its component instance to the environment (through write). Each I/O operation inherently synchronizes the entity that performs it with its environment: a write operation suspends until the environment accepts the data it has to oﬀer through its respective port; likewise, a read operation suspends until the environment oﬀers the suitable data it expects through its respective port. This view of component communication leads to a generic component model. In this model, a component instance is a black box that contains one or more active entities. An active entity is one that has its own independent thread of control. Examples of active entities are processes, threads, active objects, agents, etc. No assumption is made in this model about how the active entities inside a component instance communicate with each other. However, simple I/O operations through its ports are the only means of communication for the active entities inside a component instance with any entity not in the same component instance. By this deﬁnition, a Unix process, for instance, qualiﬁes as a component instance: it contains one or more threads of control which may even run in parallel on diﬀerent physical processors, and its ﬁle descriptors qualify as ports. A component instance may itself consist of a collection of other component instances, perhaps running in a distributed environment. Thus, by identifying their relevant ports through which they exchange data with their environment, entire systems can be viewed and used as component instances, abstracting away their internal details of operation, structure, geography, and implementation. Such a simple model of components may at ﬁrst appear rather banal. Nevertheless, it leads to a simple yet useful notion of behavior and behavioral interface. One of the strengths of this model is that it innately espouses anonymous com-

44

F. Arbab

munication: entities that communicate with each other need not know each other. It makes the model inherently amenable to exogenous coordination and supports highly ﬂexible composition possibilities, yielding a very powerful paradigm for component/behavior composition.

7

Elements of a Behavioral Interface

There are diﬀerent ways in which one can represent behavior. Given our model of components, the most direct and obvious way to represent the observable behavior of a component instance is to model it as a relation on its observable input and output. Because this input/output takes place through the ports of the component instance, sequences of data items that pass through a port emerge as the key building blocks for describing behavior. Relating sequences of data items that pass through diﬀerent ports of a component instance requires a sense of relative temporal order to inter-relate otherwise independent events. We need to state, for instance, that a certain data item passes through this port before or after some other data item passes through that port. The assumption of a global clock is stiﬂing in distributed systems and is an overkill for our purpose. Indeed, what we need is a very diluted notion of time that is much less restrictive than the notion of global time. We need to accommodate for: – ordering of events: stating that the occurrence of a certain event precedes or succeeds that of another; – atomicity of a set of events: stating that a given set of events occur only atomically. – temporal progression: stating that only a ﬁnite set of events can occur within any bounded temporal interval. Observe that we do not speak of simultaneity in our list of requirements here. Simultaneity is a rather ambiguous notion in distributed systems. Instead, we speak of atomicity. The atomicity of a set of events means that either none of them occurs, or else they all occur before any other event (not in that set) occurs, i.e., the occurrence of an atomic set of events cannot be interleaved with the occurrence of any other event. Stating that a set of events must occur atomically allows but does not require (any subset of) those events to occur simultaneously. It also allows for those events to occur in any nondeterministic order, so long as either they all occur or none occurs at all. Atomicity can be seen as a relaxing generalization of simultaneity. It is as if an atomic set of events all happen “simultaneously,” except that we elongate the moment of their occurrence into a temporal interval. The provision that no other event may interleave with the occurrence of those in the set ensures that our “elongation of the time moment into an interval” is not detectable by other entities in the system. Requiring that only a ﬁnite set of events can occur within any bounded temporal interval precludes anomalies such as Zeno’s paradox.

Abstract Behavior Types: A Foundation Model for Components

45

We use positive numbers to represent moments in time, with the proviso that it is not the actual numeric values of the time moments, but only their relative ordering that is signiﬁcant. The numerical less-than relation represents the ordering of events. The numeric equal-to relation represents atomicity, not simultaneity. Temporal progression can be enforced by requiring that in every temporal sequence a, for any number N ≥ 0 there exists an i ≥ 0 such that the i th element in a exceeds N .

8

Abstract Behavior Types

An ABT deﬁnes an abstract behavior as a relation among the observable input/output that occur through a set of “contact points” (e.g., ports of a component instance) without specifying any detail about: (1) the operations that may be used to implement such behavior; or (2) the data types those operations may manipulate for the realization of that behavior2 . This deﬁnition parallels that of an ADT, which abstracts away from the instructions and the data structures that may be used to implement the operational interface it deﬁnes for a data type. In contrast, an ABT deﬁnes what a behavior is in terms of a relation (i.e., constraint) on the observable input/output of an entity, without saying anything about how it can be realized. More formally, an ABT is a (maximal) relation among a set of timed-datastreams. The notion of timed-data-streams as well as most of the technical content in this section come from the work of J. Rutten on coalgebras [49,30], stream calculus [48], and a coalgebraic semantics for Reo [8]. Coalgebraic methods have been used for dynamical systems, automata and formal languages, modal logic, transition systems, hybrid systems, inﬁnite data types, the control of discrete event systems, formal power series, etc. (see for instance [53], [41], [42], [50], [51], [52], [22], [27]). Coalgebras have also been used as models for various programming paradigms, notably for objects and classes (see, e.g., [47], [28], and [26]). One of the ﬁrst applications of coalgebras to components appears in [11]. Deﬁning observable behavior in terms of input/output implants a dataﬂow essence within ABTs akin to such dataﬂow-like networks and calculi as [10], [32], and especially [14]. The coalgebraic model of ABT presented here diﬀers from all of the above-mentioned work in a number of respects. Most importantly, the ABT model is compositional. Its explicit modeling of ordering/timing of events in terms of separate time streams provides a simple foundation for deﬁning complex synchronization and coordination protocols using a surprisingly expressive small set of primitives. The use of coinduction as the main deﬁnition and proof principle to reason about both data and time streams allows simple compositional construction of ABTs representing many diﬀerent generic coordination schemes involving combinations of various synchronous and asynchronous primitives that are not present (and not even expressible) in any of the aforementioned models. 2

The term “Abstract Behavior Type” is a variation of the term “Abstract Behavioral Type” proposed by F. de Boer for a related concept.

46

F. Arbab

A stream (over A) is an inﬁnite sequence of elements of some set A. Streams over sets of (uninterpreted) data items are called data streams and are typically denoted as α, β, γ, etc. Zero-based indices are used to denote the individual elements of a stream, e.g., α(0), α(1), α(2), ... denote the ﬁrst, second, third, etc., elements of the stream α. We use the inﬁx “dot” as the stream constructor: x .α denotes a stream whose ﬁrst element is x and whose second, third, etc. elements are, respectively, the ﬁrst and its successive elements of the stream α. Following the conventions of stream calculus [48], the well-known operations of head and tail on streams are called initial value and derivative: the initial value of a stream α (i.e., its head) is α(0), and its (ﬁrst) derivative (i.e., its tail) is denoted as α . The k th derivative of α is denoted as α(k ) and is the stream that results from taking the ﬁrst derivative of α and repeating this operation on the resulting stream for a total of k times. Relational operators on streams apply pairwise to their respective elements, e.g., α ≥ β means α(0) ≥ β(0), α(1) ≥ β(1), α(2) ≥ β(2), .... Time streams are constrained streams over (positive) real numbers, representing moments in time, and are typically denoted as a, b, c, etc. To qualify as a time stream, a stream of real numbers a must be (1) strictly increasing, i.e., the constraint a < a must hold; and (2) progressive, i.e., for every N ≥ 0 there must exist an index n ≥ 0 such that a(n) > N . We use positive real numbers instead of natural numbers to represent time because, as observed in the world of temporal logic [23], real numbers induce the more abstract sense of dense time instead of the notion of discrete time imposed by natural numbers. Speciﬁcally, we sometimes need ﬁnitely many steps within any bounded time interval for certain ABT equivalence proofs (see, e.g., [8]). This is clearly not possible with a discrete model of time. Recall that the actual values of “time moments” are irrelevant in our ABT model; only their relative order is signiﬁcant and must be preserved. Using dense time allows us to locally break strict numerical equality (i.e., simultaneity) arbitrarily while preserving the atomicity of events. A Timed Data Stream is a twin pair of streams α, a consisting of a data stream α and a time stream a, with the interpretation that for all i ≥ 0, the input/output of data item α(i ) occurs at “time moment” a(i ). Two timed data streams α, a and β, b are equal if their respective elements are equal, i.e. α, a = β, b ≡ α = β ∧ a = b. An Abstract Behavior Type (ABT) is a (maximal) relation over timed data streams. Every timed data stream involved in an ABT is tagged either as its input or its output. The input/output tags of the timed data streams involved in an ABT are meaningless in the relation that deﬁnes the ABT. However, these tags are crucial in ABT composition described in Section 8.2. Generally, we use the preﬁx notation R(I1 , I2 , ..., Im ;O1 , O2 , ..., On ) and the separator “;” to designate the ABT deﬁned by the (m + n)-ary relation R over the m ≥ 0 sets of input timed data streams Ii , 0 ≤ i ≤ m and the n ≥ 0 sets of output timed data streams Oj , 0 ≤ j ≤ n. As usual, m + n is called the arity of R and we refer to m and n individually as the input arity and the output arity

Abstract Behavior Types: A Foundation Model for Components

47

of R. In the special case where m = n = 1 it is sometimes convenient to use the inﬁx notation I R O instead of the standard R(I ;O). To distinguish the set of timed data streams that appears in a position in the relation that deﬁnes an ABT (i.e., a column in the relation) from a speciﬁc timed data stream in that set (i.e., which may appear in a row of the relation in that position) we refer to Ii and Oj as, respectively, the i th input and the j th output portals of the ABT. Formally, a component, as deﬁned in Section 6, with m ≥ 0 input and n ≥ 0 output ports is an ABT with m input and n output portals. The set of all possible streams of data items that can pass through each port of the component, together with their respective timing, comprise the set of timed data streams of the ADT’s portal that corresponds to that port. 8.1

ABT Examples

In this section we show the utility of the ABT model through a number of examples. Basic Channels. Following is a list of some useful simple binary abstract behavior types. Each has a single input and a single output portal. 1. The behavior of a synchronous channel is captured by the Sync ABT, deﬁned as α, a Sync β, b ≡ α, a = β, b. Because α, a = β, b ≡ α = β ∧ a = b, the Sync ABT represents the behavior of any entity that (1) produces an output data stream identical to its input data stream (α = β), and (2) produces every element in its output at the same time as its respective input element is consumed (a = b). Recall that “at the same time” means only that the two events of consumption and production of each data item by a Sync channel occur atomically. 2. The behavior of an asynchronous unbounded FIFO channel is captured by the FIFO ABT, deﬁned as α, a FIFO β, b ≡ α = β ∧ a < b. The FIFO ABT represents the behavior of any entity that (1) produces an output data stream identical to its input data stream (α = β), and (2) produces every element in its output some time after its respective input element is observed (a < b). 3. The behavior of an asynchronous channel with the bounded capacity of 1 is captured by the FIFO1 ABT, deﬁned as α, a FIFO1 β, b ≡ α = β ∧ a < b < a . The FIFO1 ABT represents the behavior of any entity that (1) produces an output data stream identical to its input data stream (α = β), and (2) produces every element in its output some time after its respective input element is observed (a < b) but before its next input element is observed (b < a which means b(i ) < a(i + 1) for all i ≥ 0).

48

F. Arbab

4. The behavior of an asynchronous channel with the bounded capacity of 1 ﬁlled to contain the data item D as its initial value is captured by the FIFO1 (D) ABT, deﬁned as α, a FIFO1 (D) β, b ≡ β(0) = D ∧ α = β ∧ b < a < b . The FIFO1 (D) ABT represents the behavior of any entity that (1) produces an output data stream consisting of the initial data item D followed by the input data stream of the ABT (β(0) = D ∧ α = β ), and (2) for i ≥ 0 performs its i th input operation some time between its i th and i + 1st output operations (b < a < b ). 5. The behavior of an asynchronous channel with the bounded capacity of k > 0 is captured by the FIFOk ABT, deﬁned as α, a FIFOk β, b ≡ α = β ∧ a < b < a (k ) . Recall the a (k ) is the k th -derivative (i.e., the k th -tail) of the stream a. The FIFOk ABT represents the behavior of any entity that (1) produces an output data stream identical to its input data stream (α = β), and (2) produces every element in its output some time after its respective input element is observed (a < b) but before its k th -next input element is observed (b < a (k ) which means b(i ) < a(i + k ) for all i ≥ 0). Observe that FIFO1 is indeed a special case of FIFOk with k = 1. It is illuminating to compare the FIFO ABT deﬁned above with the deﬁnition of the queue ADT in Figure 1. They are both mathematically well-deﬁned constructs that describe the same thing: an unbounded FIFO queue. The ADT deﬁnes a queue in terms of a set of operations and a set of axioms that constrain the observable mutual eﬀect of those operations on each other. It abstracts away the actual instructions for the implementation of those operations and the data structures that they manipulate. The ABT deﬁnes a queue in terms of what data items it exchanges with its environment, when it consumes and produces them, and a set of axioms that constrain their interrelationships. It abstracts away the operations for the realization (or enforcement) of those relationships and the data types that they may utilize to do so. Merge and Replicate. We now deﬁne two other ABTs that, as we see in Section 9, form a foundation for an interesting and expressive calculus: merger and replicator. The merger ABT is deﬁned as: Mrg(α, a, β, b;γ, c) ≡  α(0) = γ(0) ∧ a(0) = c(0) ∧ Mrg(α , a , β, b;γ , c ) if a(0) < b(0)    ∃t:a(0) < t < min(a(1), b(1)) ∧ ∃r , s ∈ {a(0), t} ∧ r = s ∧ if a(0) = b(0) Mrg(α, r .a , β, s.b ;γ, c)    if a(0) > b(0) β(0) = γ(0) ∧ b(0) = c(0) ∧ Mrg(α, a, β , b ;γ , c ) Intuitively, the Mrg ABT produces an output that is a merge of its two input streams. If α(0) arrives before β(0), i.e. a(0) < b(0), then the ABT produces

Abstract Behavior Types: A Foundation Model for Components

49

γ(0) = α(0) as its output at c(0) = a(0) and proceeds with the tails of the streams in its ﬁrst input timed data stream. If α(0) arrives after β(0), i.e. a(0) > b(0), then the ABT produces γ(0) = β(0) as its output at c(0) = b(0) and proceeds with the tails of the streams in its second input timed data stream. If the α(0) and β(0) arrive “at the same time” (i.e., a(0) = b(0)), then in this formulation Mrg picks an arbitrary number t in the open time interval (a(0), min(a(1), b(1))) and uses it to nondeterministically break the tie. The assumption of dense time guarantees the existence of an appropriate t. Recall that the construct r .a is a stream whose derivative (tail) is a and whose initial value (head) is r . Thus, for a(0) = b(0) Mrg nondeterministically changes the head of one of the two time streams, a or b, thereby “delaying” the arrival of its corresponding data item to break the tie. The ﬁnite delay introduced by Mrg in this case is justiﬁed because although it breaks simultaneity, its value is constrained to preserve atomicity. Observe that Mrg(α, a, β, b;γ, c) = Mrg(β, b, α, a;γ, c). The replicator ABT is deﬁned as: Rpl (α, a;β, b, γ, c) ≡ β = α ∧ γ = α ∧ b = a ∧ c = a It is easy to see that this ABT captures the behavior of any entity that synchronously replicates its input stream into its two identical output streams. Observe that Rpl (α, a;β, b, γ, c) = Rpl (α, a;γ, c, β, b). Sum. As an example of an ABT that performs some computation, consider a simple dataﬂow adder. The behavior of such a component is captured by the Sum ABT deﬁned as Sum(α, a, β, b;γ, c) ≡ γ(0) = α(0) + β(0)∧ ∃t:max (a(0), b(0)) < t < min(a(1), b(1)) ∧ c(0) = t∧ Sum(α , a , β , b ;γ , c ). Sum deﬁnes the behavior of a component that repeatedly reads a pair of input values from its two input ports, adds them up, and writes the result out on its output port. As such, its output data stream is the pairwise sum of its two input data streams. This component behaves asynchronously in the sense that it can produce each of its output data items with some arbitrary delay after it has read both of its corresponding input data items (c(0) = t ∧t > max (a(0), b(0))). However, it is obligated to produce each of its output data items before it reads in its next input data item (t < min(a(1), b(1))). Philosophers and Chopsticks. The classical dining philosophers problem can be described in terms of n > 1 pairs of instances of two components: philosopher instances of Phil and chopstick instances of Chop. We deﬁne the externally observable behavior of each of these components as an ABT. We show in Section 9

50

F. Arbab

how instances of these components can be composed into diﬀerent component based systems both to exhibit and to solve the famous deadlock problem. We assume that a chopstick component has two input ports, t (for take) and f (for free), through which it reads in the timed data streams αt , at and αf , af , respectively. The data items in αt and αf are tokens whose actual values are not of interest to us. In practice, it is a good idea for these tokens to contain the identiﬁer of the entity (e.g., philosopher) who uses the chopstick, but as long as such informative requirements do not aﬀect behavior, they are irrelevant for our ABT deﬁnition. When a chopstick is free (its initial state) it is ready to accept a take request and thus reads from its t port the next take request token out of αt , at . Once taken, a chopstick is ready to accept a free request and thus reads from its f port the free request token out of αf , af . For the user of the chopstick, the success of its I/O operation on port t or f means the chopstick has accepted its (take or free) request. This simple behavior is captured by the Chop ABT deﬁned as Chop(αt , at , αf , af ;) ≡ at < af < at . Because we are not interested in the actual value of the take/free tokens, the Chop ABT has nothing to say about the data streams αt and αf ; it is only the timing that is relevant here. The timing equation simply states that initially, there must be a take, followed by a free, and this sequence repeats. We assume that a philosopher component has four output ports, lt (for lefttake), lf (for left-free), rt (for right-take), and rf (for right-free), through which it writes the timed data streams αlt , alt , αlf , alf , αrt , art , and αrf , arf , respectively. The two ports lt and lf are “on the left” and two ports rt and rf are “on the right” of the philosopher component, so to speak. The philosopher’s requests to take and free the chopsticks on its left and right are issued through their respective ports. The externally observable behavior of a philosopher component is as follows. After some period of “thinking” it decides to eat, at which point it attempts to obtain its two chopsticks by issuing take requests on its lt and rt ports. We assume it always issues a request for its left chopstick before requesting the one on its right. The philosopher component interprets the success of its write operation as the acceptance of its request (e.g., for exclusive access to the chopstick). Once, and if, both of its take requests are granted, it proceeds to “eat” for some time, at the end of which it then issues requests to free its left and right chopsticks by writing tokens to its lf and rf ports. The philosopher component then repeats the cycle by entering its thinking period again. This behavior is captured by the Phil ABT deﬁned as Phil (;αlt , alt , αlf , alf , αrt , art , αrf , arf ) ≡ alt < art < alf < arf < alt . Again, because we are not interested in the actual values of the take/free tokens that this component produces, the Phil ABT says nothing about the data

Abstract Behavior Types: A Foundation Model for Components

51

streams. All we are interested in is the timing constraints: an arbitrary “thinking” delay; followed by a request to take the left chopstick; once granted, followed by a request to take the right chopstick; once granted, followed by an arbitrary “eating” delay; followed by the requests to free the left and the right chopsticks; and the cycle repeats. 8.2

ABT Composition

Abstract behavior types can be composed to yield other abstract behavior types through a composition similar to the relational join operation in relational databases. Two ABTs can be composed over a common timed data stream if one is the producer and the other the consumer of that timed data stream. The same two ABTs can be composed over zero or more common timed data streams, each ABT playing the role of the producer or the consumer of one of the timed data streams, independent of its role regarding the others. Observe that the producer and the consumer of a timed data stream, α, a, necessarily synchronize their I/O operations on their respective portals for the mutual exchange of the data items in its data stream α, according to the schedule in its twin time stream a. This is accomplished simply by “fusing” their respective portals together such that the timed data stream observed on one is identical to the one observed on the other. Consider two ABTs B1 with arity p = pi + po and B2 with arity q = qi + qo , where pi and po are, respectively, the input arity and the output arity of B1 , and qi and qo , those for B2 . B1 and B2 can be composed with 0 ≤ k ≤ min(pi , qo ) + min(po , qi ) pairs of mutually fused portals, where the data items produced through an output portal, O, of one ABT are fed for consumption by the other ABT through its input portal that is fused with O. We deﬁne the k -dyad composition of B1 (I 11 , I 12 , ...I 1pi ;O11 , O12 , ...O1po ) and B2 (I 21 , I 22 , ...I 2qi ;O21 , O22 , ...O2qo ) as a special form of the join of the two relations B1 and B2 where k distinct portals (i.e., relational columns) of B1 are paired each with a distinct portal of B2 into k dyads such that (1) the two portals in each dyad have opposite input/output tags, and (2) the two timed data streams of the portals in each dyad are equal. The k -dyad composition of B1 and B2 yields a new ABT, B (I1 , I2 , ...Im ;O1 , O2 , ...On ), with arity m +n = p+q −2×k , deﬁned as a relation over those portals of B1 and B2 that are not involved in a dyad (i.e., the fused portals disappear from the resulting relation). The list I1 , I2 , ...Im is obtained from the list I 11 , I 12 , ...I 1pi , I 21 , I 22 , ...I 2qi by eliminating every one of its elements involved in a dyad. Similarly, the list O1 , O2 , ...On is obtained from the list O11 , O12 , ...O1po , O21 , O22 , ...O2qo by eliminating every one of its elements involved in a dyad. We use the dyad indices 1 ≤ l ≤ k as superscripts to mark the corresponding portals of B1 and B2 in their k -dyad composition. For example, B = B1 (α, a, β, b1 ;γ, c) ◦ B2 (δ, d ;µ, m1 ) denotes the 1-dyad composition of the two abstract behavior types B1 and B2 where the output (portal) of B2 is identical to the second input (portal) of B1 . The resulting ABT is deﬁned through the relation B ≡ {α, a, δ, d ;γ, c | α, a, β, b;γ, c ∈ B1 ∧

52

F. Arbab

δ, d ;µ, m ∈ B2 ∧ β, b = µ, m}. Another example is the ABT B = B1 (α, a, β, b1 ;γ, c2 ) ◦ B2 (δ, d 2 ;µ, m1 , ν, n), which denotes the 2-dyad composition of the two abstract behavior types B1 and B2 where the ﬁrst output of B2 is identical to the second input of B1 and the output of B1 is identical to the input of B2 . The resulting ABT is deﬁned as the relation B ≡ {α, a;ν, n | α, a, β, b;γ, c ∈ B1 ∧ δ, d ;µ, m, ν, n ∈ B2 ∧ β, b = µ, m ∧ γ, c = δ, d }. The common case of the 1-dyad composition of B1 and B2 where the single output of B1 is identical to the single input of B2 is abbreviated as B1 (...;α, a)◦ B2 (β, b;...) instead of B1 (...;α, a1 ) ◦ B2 (β, b1 ;...). This abbreviation is particularly convenient together with the inﬁx notation for binary abstract behavior types. For instance, B = α, aB1 β, b ◦ γ, cB2 δ, d denotes the 1-dyad composition of the two abstract behavior types B1 and B2 where the output of B1 is identical to the input of B2 . Of course, the resulting ABT is deﬁned as the relation α, aB δ, d ≡ {α, a;δ, d | α, a;β, b ∈ B1 ∧ γ, c;δ, d ∈ B2 ∧ β, b = γ, c}. For example, consider the binary ABTs deﬁning the basic channels presented in Section 8.1. It is not diﬃcult to see that the (1-dyad) composition of these ABTs produces results that correspond to our intuition. For instance, the composition of two Sync ABTs produces a Sync ABT. Indeed, composition of a Sync ABT with any other ABT (on its left or right) yields the same ABT. More interestingly, the composition of two FIFO ABTs produces a FIFO ABT. Composing two FIFO1 ABTs produces a FIFO2 ABT. The formal proof of this latter equivalence relies on our notion of dense time (as opposed to discrete time) and is given in [8], together with the formal treatment of many other interesting examples.

9

Reo

The ABT model provides a simple formal foundation for deﬁnition and composition of components. The k -dyad composition of ABTs supports a very ﬂexible mechanism for software composition in component based systems. This furnishes the desired level of composition ﬂexibility we expect in a component model. However, composing components directly with one another in this way reduces the glue code to essentially nothing more than repeated applications of the k -dyad composition operator. More importantly, it all but extinguishes the possibility of wielding exogenous coordination through the glue code. The ABT model is too low-level to directly provide any form of non-trivial coordination (beyond the simple synchronization implied by its timed data streams); for that, we need an eﬀective exogenous coordination model. Reo is a channel-based exogenous coordination model wherein complex coordinators, called connectors are compositionally built out of simpler ones [7,4,8]. The simplest connectors in Reo are a set of channels with well-deﬁned behavior supplied by users. Reo can be used as a language for coordination of concurrent processes, or as a “glue language” for compositional construction of connectors that orchestrate component instances in a component based system. The

Abstract Behavior Types: A Foundation Model for Components

53

emphasis in Reo is on connectors and their composition only, not on the entities that connect to, communicate, and cooperate through these connectors. Each connector in Reo imposes a speciﬁc coordination pattern on the entities (e.g., component instances) that perform I/O operations through that connector, without the knowledge of those entities. Channel composition in Reo is a very powerful mechanism for construction of connectors. The expressive power of connector composition in Reo has been demonstrated through many examples in [3,4,8]. For instance, exogenous coordination patterns that can be expressed as (meta-level) regular expressions over I/O operations performed by component instances can be composed in Reo out of a small set of only ﬁve primitive channel types. A mobile channel allows (physical or logical) relocation of one of its ends without the knowledge or the involvement of the entity at its other end. Logical mobility changes the topology of the interconnections of communicating entities, while physical mobility can have other implications, e.g., on an entity’s (eﬃciency of) access to various resources. An eﬃcient distributed implementation of channels supporting this notion of mobility is described in [5]. Both component instances and channels are mobile in Reo. Logical mobility of channel ends in Reo allows dynamic reconﬁguration of connectors, even while they are being used by component instances. In this respect, Reo resembles dynamically reconﬁgurable generalized Kahn networks, as in IWIM [1] and Manifold [12], and its dataﬂow nature is also related to Broy’s timed dataﬂow model, although Reo is more general and more expressive that these and similar models. Much as Reo supports physical mobility through its move operation to allow more eﬃcient ﬂow of data, it ascribes no semantic signiﬁcance to it. The move operation does not semantically aﬀect connector topologies, ﬂow of data, or connectivity of components to connectors. In this sense, Reo is orthogonal to the concerns involving the physical mobility of code, e.g., in models such as that of [46]. It turns out that the ABT model is quite adequate for deﬁning the channel and connector composition operation which is the crux of exogenous coordination in Reo. In the rest of this section we show how connector construction in Reo can be seen as an application of the ABT model. 9.1

Channels and Connectors

Channels are the only primitive medium of communication between two components in Reo. The notion of channel in Reo is far more general than its common interpretation. A channel in Reo has its own unique identity and always has exactly two directed ends, each with its own unique identity. Based on their direction, there are two types of channel ends: source and sink ends. Data enters through a source channel end into its respective channel, and it leaves through a sink channel end from its respective channel. (Channels themselves have no direction in Reo, only their ends do.) Beyond a small set of mild obvious requirements, such as enabling I/O operations to read/write data items from/to their ends, Reo places no restrictions on the behavior of channels. This allows an open-ended set of diﬀerent chan-

54

F. Arbab

nel types to be used simultaneously together in Reo, each with its own policy for synchronization, buﬀering, ordering, computation, data retention/loss, etc. Some typical examples of conventional channels are, e.g., the ones deﬁned in Section 8.1. These channels happen to each have a source end and a sink end. More unconventional channels are also possible in Reo, especially because a channel can also have only two source ends or only two sink ends. A few examples of some such exotic channels appear in Section 9.3; even more examples are presented in [3,7,4]. Strictly speaking, Reo itself neither provides nor assumes the availability of any speciﬁc set of channel types; it simply assumes that an appropriate assortment of channel types, each with its properly well-deﬁned semantics, is provided by users for it to operate on. Nevertheless, it is reasonable to expect that in practice certain most primitive channel types, e.g., synchronous channels, will always be made available in all cases. Reo deﬁnes a connector as a set of channel ends and their connecting channels organized in a graph of nodes and edges such that: – Zero or more channel ends coincide on every node. – Every channel end coincides on exactly one node. – There is an edge between two (not necessarily distinct) nodes if and only if there is a channel one end of which coincides on each of those nodes. We use x → N to denote that the channel end x coincides on the node N , and x to denote the unique node on which the channel end x coincides. For a node N , we deﬁne the set of all channel ends coincident on N as [N ] = {x | x → N }, and disjointly partition it into the sets Src(N ) and Snk (N ), denoting the sets of source and sink channel ends that coincide on N , respectively. Observe that nodes are neither components nor locations. Although some nodes are attached to component instances to allow their exchange of information, nodes and components are diﬀerent notions and not every node can be associated with or attached to a component instance. A node is a fundamental concept in Reo representing an important topological property: all channel ends x ∈ [N ] coincide on the same node N . This property entails speciﬁc implications in Reo regarding the ﬂow of data among the channel ends x ∈ [N ], irrespective of concern for the location of those channel ends or N , or the possible attachment of N to a component instance. A node N is called a source node if Src(N ) = ∅ ∧ Snk (N ) = ∅. Analogously, N is called a sink node if Src(N ) = ∅ ∧ Snk (N ) = ∅. A node N is called a mixed node if Src(N ) = ∅ ∧ Snk (N ) = ∅. By the above deﬁnition, every channel represents a (simple) connector with two nodes. From the point of view of Reo a port of a component instance is just a node that (initially) contains a single channel end. An input port is (initially a singleton) source node, and an output port is (initially a singleton) sink node. From the point of view of a component instance, each of its ports is merely a simple connector corresponding to a synchronous channel (the node of) one end of which is made publicly accessible for I/O by its environment, while (the node of) its other end is hidden for exclusive use by the component instance itself. An

Abstract Behavior Types: A Foundation Model for Components

55

output port of a component instance has the sink node of its synchronous channel public while its source node is available only for I/O operations performed by that component instance. Likewise, an input port has the source node of its synchronous channel public while its sink node is hidden for exclusive use by its component instance. Reo provides I/O operations on source and sink nodes only; components cannot read from or write to mixed nodes. A component instance can write to a source node and can read from a sink node using node I/O operations of Reo. The graph representing a connector is not directed. However, for each channel end xc of a channel c, we use the directionality of xc to assign a local direction in the neighborhood of xc to the edge that represents c. The local direction of the edge representing a channel c in the neighborhood of the node of its source xc is presented as an arrow emanating from xc . Likewise, the local direction of the edge representing a channel c in the neighborhood of the node of its sink xc is presented as an arrow pointing to xc . See Figures 2 and 3 for examples. Complex connectors are constructed in Reo out of simpler ones using its join operation. The join operation in Reo is deﬁned only on nodes. Joining two nodes N1 and N2 destroys both nodes and produces a new node N with the property that [N ] = [N1 ] ∪ [N2 ]. This single operation allows construction of arbitrarily complex connector graphs involving any combination of channels picked from an open-ended set of channel types. The semantics of a connector is deﬁned as a composition of the semantics of its (1) constituent channels, and (2) nodes. Because Reo does not provide any channels, it does not deﬁne their semantics either. What Reo deﬁnes is the composition of channels into connectors and the semantics of this composition through the semantics of its (three types of) nodes. Intuitively, a source node replicates every data item written to it as soon as all of its coincident source channel ends can consume that data item. Reading from a sink node nondeterministically selects one of the data items available through its coincident sink channel ends. A mixed node is a self-contained “pumping station” that combines the behavior of a sink node and a source node in an atomic iteration of an inﬁnite loop: in each atomic iteration it nondeterministically selects an appropriate data item available through its coincident sink channel ends and replicates that data item into all of its coincident source channel ends. A data item is appropriate for selection in an iteration only if it can be consumed by all source channel ends that coincide on that node. 9.2

ABT Models of Nodes and Connectors

Consider a sink node N with [N ] = {x , y}, as in Figure 2.a. The read operations performed on this node induce an output timed data stream, αN , aN , for this sink node. We use αx , ax and αy , ay to designate the timed data streams corresponding to the channel ends x and y, respectively. The semantics of this sink node is deﬁned by the ABT Mrg(αx , ax , αy , ay ;αN , aN ). The semantics of a sink node N where [N ] = {x , y, z }, as in Figure 2.b, is deﬁned as the 1-dyad composition

56

F. Arbab x y a

y

b

x

x

x

z

y

z c

y

d

e

Fig. 2. Representation of nodes in Reo.

Mrg3(αx , ax , αy , ay , αz , az ;αN , aN )) ≡ Mrg(αx , ax , αy , ay ;β1 , b1 1 ) ◦ Mrg(γ1 , c1 1 , αz , az ;αN , aN ) where αN , aN is the output timed data stream of the node, as before, and β1 , b1 and γ1 , c1 are internal timed data streams. Because Mrg is associative with respect to its input portals, merging the intermediate result of the merge of x and y with z is the same as merging x with the intermediate result of the merge of y and z ; i.e., Mrg3 is associative with respect to its input portals. As such, the simple graphical notation of Reo (e.g., in Figures 2.a and b) is quite appropriate because it does not suggest any precedence for the Mrg operations. Clearly this scheme can be used to deﬁne the semantics of sink nodes with more coincident channel ends in general as the ABT Mrgk with k > 0 input and one output portals. For completeness, we deﬁne Mrg1(αx , ax ;αN , aN )) ≡ αx , ax = αN , aN and consider Mrg2 to be a pseudonym for Mrg. The write operations performed on a source node N with [N ] = {x , y}, as in Figure 2.c, induce an input timed data stream, αN , aN , for N . The semantics of N in this case is deﬁned by the ABT Rpl (αN , aN ;αx , ax , αy , ay . The semantics of a source node N with [N ] = {x , y, z }, as in Figure 2.d, is deﬁned as the 1-dyad composition Rpl 3(αN , aN ;αx , ax , αy , ay , αz , az ) ≡ Rpl (αN , aN ;αx , ax , β1 , b1 1 ) ◦ Rpl (γ1 , c1 1 ;αy , ay , αz , az ) where αN , aN is the input timed data stream of the node, as before, and β1 , b1 and γ1 , c1 are internal timed data streams. Because Rpl is associative with respect to its output portals, the precedence of the Rpl operations is irrelevant and Rpl 3 is also associative with respect to its output portals. Similarly, the general ABT Rpl k with one input and k > 0 output portals deﬁnes the semantics of a source node with k coincident channel ends. Again, for completeness, we deﬁne Rpl 1(αN , aN ;αx , ax )) ≡ αx , ax = αN , aN and consider Rpl 2 to be a pseudonym for Rpl . A mixed node, as in Figure 2.e, is a composition of two “half-nodes,” a source and a sink. Because no component is allowed to perform an I/O operation on a mixed node, no input/output timed data stream can be deﬁned for a mixed node. A mixed node is a closed entity that does not interact with any component; instead it internally pumps data items from its sink channel ends to its source channel ends. The semantics of a mixed node N with m > 0 sink and n >

Abstract Behavior Types: A Foundation Model for Components

57

0 source channel ends is thus deﬁned as the 1-dyad composition of the two ABTs describing the behavior of each of its half nodes: Mrgm(I1 , I2 , ...Im ;β1 , b1 ) and Rpl n(γ1 , c1 ;O1 , O2 , ...On ). The portals Ii and Oj designate the timed data streams observed at the m sink and the n source channel ends coincident on N , respectively. The resulting ABT is thus P mx n(I1 , I2 , ...Im ;O1 , O2 , ...On ) ≡ Mrgm(I1 , I2 , ...Im ;β1 , b1 ) ◦ Rpl n(γ1 , c1 ;O1 , O2 , ...On ). For instance, the behavior of the mixed node in Figure 2.e is captured by the ABT deﬁned as the relation P 3x 2(I1 , I2 , I3 ;O1 , O2 ) over the timed data streams of its respective 3 sink and 2 source channel ends. Every edge of a connector corresponds to a channel whose semantics is deﬁned as an ABT. Since a connector consists of (three types of) nodes and edges, all of whose semantics are now deﬁned as ABTs, the semantics of every connector in Reo can be derived as a composition of the ABTs of its constituent nodes and edges. 9.3

A Cogent Set of Primitive Channels

To demonstrate the utility of Reo we must supply it with a set of primitive channels. The fact that Reo accepts and the ABT model allows deﬁnition of an open-ended set of arbitrarily complex channels is interesting. What is more interesting, however, is that connector composition in Reo is itself powerful enough to yield surprisingly expressive complex connectors out of a very small set of trivially simple channels. A useful set of primitive channels for Reo consists of 7 channel types: Sync, FIFO, FIFO1 , FIFO1 (D), Filter(P ), LossySync, and SyncDrain. This is not a minimal set, in the sense that some of the channel types in this set can themselves be composed in Reo out of others; however, minimality is not our concern here and these channel types turn out to be both simple and frequently useful enough to deserve their own explicit mention. The ﬁrst four channel types were deﬁned as ABTs in Section 8.1. We deﬁne the ABTs for the rest below. The common characteristics of the last three channels, above, are that they are all (1) synchronous, and (2) lossy. Neither channel has a buﬀer to store data and if necessary, delays the I/O operation on either one of its ends until it is matched with an I/O operation on its other end. A channel is lossy if it does not deliver through its sink end every data item it consumes through its source end. The diﬀerence between these three channels is in their loss policy. 1. A Filter(P ) channel is a synchronous channel with a source and a sink end that takes a pattern P parameter upon its creation. It behaves like a Sync channel, except that only those data items that match the pattern P can actually pass through it; others are always accepted by its source, but are immediately lost. The behavior of such a channel is captured by the Filter(P ) ABT deﬁned as

58

F. Arbab

α,a Filter(P ) β, b ≡ β(0) = α(0) ∧ b(0) = a(0) ∧ α , a Filter(P ) β , b if α(0) P otherwise α , a Filter(P ) β, b The inﬁx operator α(0) P denotes whether or not the data item α(0) matches with the pattern P . If so, α(0) passes through, otherwise it is lost, and the ABT proceeds with the rest of its timed data streams. 2. A LossySync channel is also like a Sync channel except that it is always ready to consume every data item written to its source end. If a matching read operation is pending at its sink, the data item written to its source is actually transferred; otherwise, the written data item is lost. The behavior of this channel is captured by the LossySync ABT deﬁned as α, a LossySync β, b ≡ if a(0) > b(0)  α, a LossySync β, a(0).b β(0) = α(0) ∧ α , a LossySync β , b if a(0) = b(0)  otherwise α , a LossySync β, b 3. A SyncDrain is a channel with two source ends. Because it has no sink end, it has no way to ever produce any data items. Consequently, every data item written to its source ends is simply lost. SyncDrain is synchronous because a write operation on one of its ends remains pending until a write is performed on its other end as well; only then both write operations succeed together. The behavior of this channel is captured by the SyncDrain ABT deﬁned as α, a SyncDrain β, b ≡ a = b 9.4

Coordinating Glue Code

To demonstrate the expressive power of connector composition, in this section we describe a number of examples in Reo. More examples are presented elsewhere [3,7,8,4]. Write-Cue Regulator. Consider the connector in Figure 3.a, composed out of the three channels ab, cd, and ef. Channels ab and cd are of type Sync and ef is of type SyncDrain. This connector shows one of the most basic forms of exogenous coordination: the number of data items that ﬂow from a to d is the same as the number of write operations that succeeds on f. (Recall that a designates the unique node on which the channel end a coincides.) The analogy between the behavior of this connector and a transistor in the world of electronic circuits is conspicuous. A component instance with a port connected to f can count and regulate the ﬂow of data between the two nodes a and d by the timing and the number of write operations it performs on f. The entity that regulates and/or counts the number of data items through f need not know anything about the entities that write to a and/or take from d, nor that its write actions actually regulate this ﬂow. The two entities that communicate through a and d need not know

Abstract Behavior Types: A Foundation Model for Components a

b,e,c

d

f

a

b,e,c

g

d

h,f,i

a

a

c

b

j

b

d

c b b

a

b

c

d

59

c

c

a

a

o Sequencer

e

f

Sequencer

g

Fig. 3. Examples of connectors in Reo.

anything about the fact that they are communicating with each other, nor that the volume of their communication is regulated and/or measured by a third entity at f. Barrier Synchronizers. We can build on our write-cue regulator to construct a barrier synchronization connector, as in Figure 3.b. The four channels ab, cd, gh, and ij are all of type Sync. The SyncDrain channel ef ensures that a data item passes from a to d only simultaneously with the passing of a data item from g to j (and vice versa). This simple barrier synchronization connector can be trivially extended to any number of pairs, as shown in Figure 3.c. Ordering. The connector in Figure 3.d consists of three channels: ab, ac, and bc. The channels ab and ac are SyncDrain and Sync, respectively. The channel bc is of type FIFO1 . The behavior of this connector can be seen as imposing an order on the ﬂow of the data items written to a and b, through to c: the data items obtained by successive read operations on c consist of the ﬁrst data item written to a, followed by the ﬁrst data item written to b, followed by the second data item written to a, followed by the second data item written to b, etc. See [3,4] for more detail and [8] for a formal treatment of this connector. The coordination pattern imposed by our connector can be summarized as c = (ab)∗, meaning the sequence of values that appear through c consist of zero or more repetitions of the pairs of values written to a and b, in that order. Sequencer. Consider the connector in Figure 3.e. The enclosing box represents the fact that the details of this connector are abstracted away and it provides only the four nodes a, b, c, and d for other entities (connectors and/or component instances) to (in this case) read from. Inside this connector, we have four Sync, a FIFO1 (o), and three FIFO1 channels connected together. The FIFO1 (o) channel is the leftmost one and is initialized to have a data item in its buﬀer, as indicated by the presence of the symbol “o” in the box representing its buﬀer. The actual

60

F. Arbab

value of this data item is irrelevant. The read operations on the nodes a, b, c, and d can succeed only in the strict left to right order. This connector implements a generic sequencing protocol: we can parameterize this connector to have as many nodes as we want, simply by inserting more (or fewer) Sync and FIFO1 channel pairs, as required. Figure 3.f shows a simple example of the utility of our sequencer. The connector in this ﬁgure consists of a two-node sequencer, plus a pair of Sync channels and a SyncDrain channel connecting each of the nodes of the sequencer to the nodes a and c, and b and c, respectively. The connector in Figure 3.f is another connector for the coordination pattern c = (ab)∗, although there is a subtle diﬀerence between the behavior of this connector and the one in Figure 3.d. See [3,4] for more detail. It takes little eﬀort to see that the connector in Figure 3.g corresponds to the meta-regular expression c = (aab)∗. Figures 3.f and g show how easily we can construct connectors that exogenously impose coordination patterns corresponding to the Kleen-closure of any “meta-word” made up of atoms that stand for I/O operations, using a sequencer of the appropriate size. 9.5

Fibonacci Series

A simple example of how a composition of a set of components yields a system that delivers more than the sum of its parts is the computation of the classical Fibonacci series. To assemble a component based application to deliver this series we actually need only one (instance of one) component plus a number of channels. The component we need is a realization of the Sum ABT that we already saw in Section 8.1.

0 Sum 1

Fig. 4. Computing the Fibonacci series.

Figure 4 shows a component (the outermost thick enclosing box) with only one output port (the only exposed node on the right border of the box). This is our component based application for computing the Fibonacci series. Peeking inside this component, we see how it is made out of an instance of Sum, a FIFO1 (1), a FIFO1 (0), a FIFO1 , and ﬁve Sync channels.

Abstract Behavior Types: A Foundation Model for Components

61

As long as the FIFO1 (0) channel is full, nothing can happen: there is no way for the value in FIFO1 (1) to move out. At some point in time, the value in FIFO1 (0) moves into the FIFO1 channel. Thereafter, the FIFO1 (0) channel becomes empty and the two values in the FIFO1 (1) and the FIFO1 channels become available for Sum to consume. The intake of the value in FIFO1 (1) by Sum inserts a copy of the same value into the FIFO1 (0) channel. When Sum is ready to write its computed value out, it suspends waiting for some entity in the environment to accept this value. Transfer of this value to the entity in the environment also inserts a copy of the same value into the now empty FIFO1 (1) channel. At this point we are back to the initial state, but with diﬀerent values in the buﬀers of the FIFO1 (1) and the FIFO1 (0) channels. The ABT models of the component Sum, channels, and Reo nodes that we presented earlier suﬃce for a formal analysis of the behavior of their composition in this example. Observe that all entities involved in this composed application are completely generic and, of course, neither knows anything about the Fibonacci series, nor the fact that it is “cooperating” with other entities to compute it. It is the speciﬁc glue code of this application, made by composing 8 simple generic channels in a speciﬁc topology in Reo, that coordinates the communication of the components (in this case, only one) with one another (in this case, with itself) and the environment to compute this series. 9.6

Dining Philosophers

We can vividly demonstrate the signiﬁcance of exogenous coordination in component based system composition through the classical dining philosophers problem. In this section we use instances of two components, each of which is a realizations of one of the two ABTs Phil and Chop deﬁned in Section 8.1, to (1) compose a dining philosophers application that exhibits the famous deadlock problem; and (2) compose another dining philosophers application that prevents the deadlock. Figure 5.a shows 4 philosophers and 4 chopsticks around a virtual round table. Each philosopher has 4 output ports, corresponding to the lt, lf , rt, and rf portals of the Phil ABT in Section 8.1. In this ﬁgure, philosophers face the table, thus their sense of left and right is obvious. Each chopstick has two input ports, corresponding to the t and f input portals of the Chop ABT in Section 8.1. In Figure 5.a, chopstick ports on the outer-edge of the table are their t ports and the ones closer to the center of the table are their f ports. The t (take) port of each chopstick is connected to the take ports of its adjacent philosophers, and its f port to their respective free ports. All channels are of type Sync. Consider what happens in the node at the three-way junction connected to the t port of Chop1 . If Chop1 is free and is ready to accept a token through its t port, as it initially is, whichever one of the two philosophers Phil1 and Phil4 happens to write its take request token ﬁrst will succeed to take Chop1 . Of course, it is possible for Phil1 and Phil4 to attempt to take Chop1 at the same time. In this case, the semantics of this mixed node (by the deﬁnition of the ABT Mrg) guarantees that only one of them succeeds, nondeterministically; the

F. Arbab

l2 hi

Chop4

hi

a

l4

l4

P

hi P

P l3

Chop1

hi

hi

Chop4

Chop3

P

l3

l1

P

hi

hi

l1

P

P

hi

Chop1

Chop3

Chop2

P

Chop2

l2

62

b Fig. 5. Dining philosophers in Reo.

write operation of the other remains pending until Chop1 is free again. Because the deﬁnition of the ABT Phil states that a philosopher frees a chopstick only after it has taken it, there is never any contention at the three-way junction connected to the f port of a chopstick. The composition of channels in this Reo application enables philosophers to repeatedly go through their “eat” and “think” cycles at their leisure, resolving their contentions for taking the same chopsticks nondeterministically. The possibility of starvation is ruled out because the nondeterminism in Mrg is assumed to be fair. This simple glue code composed of nothing but common generic Sync channels directly renders a faithful implementation of the dining philosophers problem; all the way down to its possibility of deadlock. Because all philosophers are instances of the same component, they all attempt to fetch their chopsticks in the same order. The Phil ABT deﬁnes this to be left-ﬁrst. If all chopsticks are free and all philosophers attempt to take their left chopsticks at the same time, of course, they will all succeed. However, this leaves no free chopstick for any philosopher to take before it can eat. No philosopher will relinquish its chopstick before it ﬁnishes its eating cycle. Therefore, this application deadlocks, as expected. Avoiding the Deadlock. Interestingly, with Reo, solving the deadlock problem requires no extra code, central authority, or modiﬁcation to any of the components. In order to prevent the possibility of a deadlock, all we need to do is to change the way in which we compose our application out of the very same components. Figure 5.b shows a slightly diﬀerent composition topology of the same set of Sync channels comprising the glue code that connects the exact same instances of Phil and Chop as before. We have ﬂipped one philosopher’s left and right connections to its adjacent chopsticks (in this particular case, those of Phil2 ) without its knowledge. None of the components in the system are aware

Abstract Behavior Types: A Foundation Model for Components

63

of this change, nor is any of them modiﬁed in any way to accommodate it. Our ﬂipping of these connections is purely external to all components. It is not diﬃcult to see why this new topology prevents deadlock. If all philosophers attempt to take their left chopsticks now at the same time, one of them, namely Phil2 , will actually reach for the one on its right-hand-side. Of course, Phil2 is unaware of the fact that as it reaches out through its left port to take its ﬁrst chopstick, it is actually the one on its right-hand-side it competes to take. In this case it competes with Phil3 , which is also attempting to take its ﬁrst chopstick. It makes no diﬀerence which one of the two wins this competition, one will be denied access to its ﬁrst chopstick. This ensures that at least one chopstick will remain free (no philosopher attempts to take Chop2 as its ﬁrst chopstick) to enable at least one philosopher to obtain its second chopstick as well and complete its eating cycle. Comparing the composition topologies in Figures 5.a and b, we see that in Reo (1) diﬀerent glue code connecting the same components produces diﬀerent system behavior; and (2) coordination protocols are imposed by glue code on components that cooperate with one another through the glue code, without being aware of each other or their cooperation. The two fundamental notions that underpin this pair of highly desirable provisions are: – The underlying notion of component (Section 6) in the ABT model prevents a component from distinguishing individual entities within its environment directly. Components can exchange only passive data with their environment through communication primitives that (1) do not allow them to discern speciﬁc targets as communication partners, and (2) do not entail any further obligation on behalf of the environment. The ABT model of components, thus, grants the environment great ﬂexibility in making late, even dynamic, decisions about how components are composed. This makes ABT components highly susceptible to exogenous coordination, although the ABT model itself oﬀers no non-trivial coordination primitives. – Reo is a coordination model that takes full advantage of the composition ﬂexibility oﬀered by the ABT model and oﬀers a calculus of connector composition based on a user-deﬁned set of primitive channels, all deﬁned as ABTs. The crux of this calculus is the join operator in Reo for composing channel ends into composite nodes, and the speciﬁc semantics it deﬁnes for these nodes as ABTs (Section 9.2). Connector composition in Reo offers a simple yet surprisingly expressive exogenous coordination model that eﬀectively exploits the ﬂexibility of components in the ABT model. The two systems in Figures 5.a and b are made of the same number of constituent parts of the same types: the same number of component instances of the same kinds, and the same number of primitive connectors (Sync channels). The only diﬀerence between the two is in the topology of their inter-connections. This topological diﬀerence is the only cause of the diﬀerence between the “more than sum of the parts” in these two systems.

64

F. Arbab

Making of a Chopstick. A moment of reﬂection reveals that, especially since there is no computation involved in the behavior of a chopstick, it should be easy to realize the behavior deﬁned by the ABT Chop through channel composition. The behavior deﬁned as Chop is indeed all coordination: it must alternate enabling the write operations on one (t) then on the other (f ) of its two input ports. Indeed, we can easily use a two-port sequencer (Figure 3.e) plus two SyncDrain channels to realize this behavior. But a much simpler construction is possible as well.

t

f Fig. 6. Inside of a chopstick.

The connector hidden inside the enclosing box in Figure 6 is a simpliﬁed two-port sequencer which exactly implements the behavior of the ABT Chop. This connector consists of two channels: a FIFO1 and a SyncDrain. Initially, the FIFO1 is empty, therefore enabling the ﬁrst write to its port t to succeed immediately. While this channel is empty, a write to its f port suspends because there is no data item to be “simultaneously” consumed by the opposite (source) end of the SyncDrain. Once a write to t succeeds, the FIFO1 channel becomes full and the next write operation on port t will suspend until this channel becomes empty again. When the FIFO1 channel is full, a write to f succeeds, causing the SyncDrain channel to consume the contents of the FIFO1 channel as well. This returns the connector to its original state allowing it to cyclically repeat the same behavior. Adaptation of a Philosopher. As a simple example of the usefulness of Filter(P ) channels, suppose the interface of the philosopher component we acquire for our application does not exactly match that of our Phil ABT. The component we obtain, Philos has only one output port and it writes all its tokens to the same port. Figure 7 shows how Philos can be adapted to ﬁt the interface of Phil , using four ﬁlter channels. The wiggly segment in the representation of a ﬁlter channel suggests a “resistor” that inhibits the transmission of values that do not match its ﬁlter pattern. The text above the wiggly line is the ﬁlter pattern. Because Philos writes all of its tokens to the same port, it must distinguish them by their values. We assume it writes the four values lt, lf, rt, and rf to identify these tokens. Every value written to the output port of Philos is automatically replicated into the source ends of the four channel ﬁlters that coincide on this node. This copying happens whenever all four source channel ends are ready to consume the replicated value. Whatever the value is, three of the four channels will always be ready to accept it

Abstract Behavior Types: A Foundation Model for Components

lf

65

rf rt

rf

lf

lt lt

rt

Philos

Fig. 7. Adapting Philos to appear as Phil .

unconditionally, because it will not match their ﬁlters and they will immediately lose the value. The fourth channel, the one whose pattern matches the written value, is the one whose acceptance triggers the actual replication/transfer. This happens only when the node at the sink end of this ﬁlter channel can synchronously dispose of the value, which is possible only when there is a read on that node.

10

Conclusion

The operational interface that is inherent in the Abstract Data Type model and object oriented programming introduces two very diﬀerent concepts for (1) entities, and (2) the mechanism of their composition. To their outside world, entities are what their interfaces advertise them to be: a set of operations. The mechanism that composes entities is based on performing the operations of other entities. This makes composition endogenous (i.e., an entity internally decides what operations of which other entities to perform) and relies on rather strong assumptions about the environment (i.e., the actual availability of appropriate other entities to support those operations with their expected semantics). Unlike the ADT model, main-stream object oriented models do not oﬀer any formal semantics in their object/class interfaces. The purely syntactic nature of their interfaces becomes the weakest link in the reliability of the assumptions that underlie the validity of each composition: unless the entity that invokes the operation knows the entity whose operation it invokes rather intimately, the semantics that one assumes may be diﬀerent than what the other guarantees; even subtle diﬀerences here can sabotage a composition. Furthermore, the composition of two objects does not produce another object. Components are expected to be independent commodities, viable in their binary forms in the (not necessarily commercial) marketplace, developed, offered, exploited, deployed, integrated, maintained, and evolved by separate autonomous organizations in mutually unknown and unknowable contexts, over very long spans of time. The level of intimacy that is implicitly required of objects that compose by invoking each other’s methods, is simply too unrealistic in the world of such components. Component models that rely on (variations of)

66

F. Arbab

object oriented programming (e.g., components as fortiﬁed collections of objects) and its composition mechanism of method invocation must, on the one hand, ameliorate its inherent endogenous rigidity (e.g., by intercepting, interpreting, retargeting, or suppressing messages), and on the other hand yield quite brittle compositions. Composition of two components, in such models, does not by itself yield another component. Abstract Behavior Types presented in this paper oﬀer a simpler and far more ﬂexible model of components — and of their composition. An ABT is a mathematical construct that deﬁnes and/or constrains the behavior of an entity without any mention of operations or data types that may be used to realize that behavior. This puts the ABT model at a higher-level of abstraction than ADTs and makes it more suitable for components. The endogenous nature of their composition means that it is not possible for a third party, e.g., an entity in the environment, to compose two objects (or two ADTs) “against their own will” so to speak. In contrast, the composition of any two ABTs is always well-deﬁned and yields another ABT. The building blocks in the mathematical construction of the ABT model are the (generally) inﬁnite streams that represent the externally observable sequences of I/O events that occur at an entity’s interaction points (e.g., ports) through which it exchanges data with its environment. Such inﬁnite structures, and thus the ABT model, naturally lend themselves to coalgebraic techniques and the coinduction reasoning principle. The ABT model supports a much looser coupling than is possible with ADT and is inherently amenable to exogenous coordination. We advocate both of these as highly desirable, if not essential, properties for component based systems. The ABT model provides a simple formal foundation for deﬁnition and composition of components. However, direct composition of component ABTs does not generally provide much of an opportunity to systematically wield exogenous coordination. Reo is a channel-based exogenous coordination model that can be used as a glue language for dynamic compositional construction of component connectors in (non-)distributed and/or mobile systems. Connector construction in Reo can be seen as an application of the ABT model. A channel in Reo is just a special kind of an atomic connector (i.e., component): whereas components and connectors oﬀer one or more ports to exchange information with their environment, a channel is an ABT that oﬀers exactly two ports (i.e., its channel-ends) for interaction with its environment. Because all Reo connectors are ABTs, the semantics of channel composition in Reo can be deﬁned in terms of ABT composition.

Acknowledgment I am thankful for the fruitful discussions and the collaboration of all my colleagues at CWI, especially J. Rutten, M. Bonsangue, and F. de Boer, who have contributed to the ideas behind abstract behavior types. I am grateful for the attention and the creative inﬂuence of the participants in the ACG seminar se-

Abstract Behavior Types: A Foundation Model for Components

67

ries of J. de Bakker at CWI, where various aspects of Reo were presented and discussed in 2001 and 2002. I immensely appreciate the work of my colleagues involved in the development and implementation of Reo. I am particularly grateful for J. Rutten’s keen interest in Reo and his inspiring work on a coalgebraic formal semantics for it.

References 1. F. Arbab. The IWIM model for coordination of concurrent activities. In Paolo Ciancarini and Chris Hankin, editors, Coordination Languages and Models, volume 1061 of Lecture Notes in Computer Science, pages 34–56. Springer-Verlag, April 1996. 2. F. Arbab. What do you mean, coordination? Bulletin of the Dutch Association for Theoretical Computer Science, NVTI, pages 11–22, 1998. Available on-line http://www.cwi.nl/NVTI/Nieuwsbrief/nieuwsbrief.html. 3. F. Arbab. A channel-based coordination model for component composition. Technical Report SEN-R0203, Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands, February 2002. 4. F. Arbab. Reo: A channel-based coordination model for component composition. Mathematical Structures in Computer Science, 2003. 5. F. Arbab, F. S. de Boer, M. M. Bonsangue, and J. V. Guillen Scholten. MoCha: A framework for coordination using mobile channels. Technical Report SEN-R0128, Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands, December 2001. 6. F. Arbab, F.S. de Boer, and M.M. Bonsangue. A coordination language for mobile components. In Proc. ACM SAC’00, 2000. 7. F. Arbab and F. Mavaddat. Coordination through channel composition. In F. Arbab and C. Talcott, editors, Coordination Languages and Models: Proc. Coordination 2002, volume 2315 of Lecture Notes in Computer Science, pages 21–38. Springer-Verlag, April 2002. 8. F. Arbab and J. J. M. M. Rutten. A coinductive calculus of component connectors. Technical Report SEN-R0216, Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands, September 2002. 9. Farhad Arbab, F. S. de Boer, and M. M. Bonsangue. A logical interface description language for components. In Antonio Porto and Gruia-Catalin Roman, editors, Coordination Languages and Models: Proc. Coordination 2000, volume 1906 of Lecture Notes in Computer Science, pages 249–266. Springer-Verlag, September 2000. 10. J.W. de Bakker and J.N. Kok. Towards a Uniform Topological Treatment of Streams and Functions on Streams. In W. Brauer, editor, Proceedings of the 12th International Colloquium on Automata, Languages and Programming, volume 194 of Lecture Notes in Computer Science, pages 140–148, Nafplion, July 1985. Springer-Verlag. 11. L. Barbosa. Components as Coalgebras. PhD thesis, Universidade do Minho, Braga, Portugal, 2001. 12. M.M. Bonsangue, F. Arbab, J.W. de Bakker, J.J.M.M. Rutten, A. Scutell´ a, and G. Zavattaro. A transition system semantics for the control-driven coordination language manifold. Theoretical Computer Science, 240:3–47, 2000.

68

F. Arbab

13. M. Broy. A logical basis for component-based system engineering. Technical report, Technische Universit¨ at M¨ unchen, Nov. 2000. 14. M. Broy and K. Stolen. Speciﬁcation and development of interactive systems, volume 62 of Monographs in Computer Science. Springer, 2001. 15. J. Buck, S. Ha, E. A. Lee, and D. G. Messerschmitt. Ptolemy: a framework for simulating and prototyping heterogeneous systems. International Journal of Computer Simulation, special issue on Simulation Software Development(3), January 1990. 16. CORBA. See: http://www.omg.org. 17. F. S. de Boer and M. M. Bonsangue. A compositional model for conﬂuent dynamic data-ﬂow networks. In M. Nielsen and B. Rovan, editors, Proc. International Symposium of the Mathematical Foundations of Computer Science (MFCS), volume 1893 of Lecture Notes in Computer Science, pages 212–221. Springer-Verlag, August-September 2000. 18. Enterprise JavaBeans. See: http://java.sun.com/products/ejb. 19. D. Gelernter and N. Carriero. Coordination languages and their signiﬁcance. Communication of the ACM, 35(2):97–107, February 1992. 20. J. Gore. Object Structures: Building Object-Oriented Software Components. Addison Wesley, 1996. 21. R. Grimes. Professional DCOM Programming. Wrox Press, 1997. 22. H.P. Gumm and T. Schr¨ oder. Covarieties and complete covarieties. In [29], 1998. 23. H. Barringer, R. Kuiper, and A. Pnueli. A really abstract current model and its temporal logic. In Proceedings of Thirteenth Annual ACM Symposium on principles of Programming Languages, pages 173–183. ACM, 1986. 24. R. Hennicker and M. Wirsing. A formal method for the systematic reuse of speciﬁcation components. In Methods of Programming, volume 544 of LNCS, pages 49–75. Springer Verlag, 1991. 25. F. Huber, A. Rausch, and B. Rumpe. Modeling dynamic component interfaces. In M. Singh, B. Meyer, J. Gil, and R. Mitchell, editors, Proc. Technology of ObjectOriented Languages and Systems (TOOLS’98), pages 58–70. IEEE Computer Society, 1998. 26. B. Jacobs. Behaviour-reﬁnement of object-oriented speciﬁcations with coinductive correctness proofs. Report CSI-R9618, Computing Science Institute, University of Nijmegen, 1996. Also in the proceedings of TAPSOFT’97. 27. B. Jacobs. Coalgebraic speciﬁcations and models of deterministic hybrid systems. In M. Wirsing and M. Nivat, editors, Algebraic Methods and Software Technology, number 1101 in Lecture Notes in Computer Science, pages 520–535. SpringerVerlag, 1996. 28. B. Jacobs. Inheritance and cofree constructions. In P. Cointe, editor, European Conference on Object-Oriented Programming, number 1098 in Lecture Notes in Computer Science, pages 210–231. Springer-Verlag, 1996. 29. B. Jacobs, L. Moss, H. Reichel, and J.J.M.M. Rutten, editors. Proceedings of the ﬁrst international workshop on Coalgebraic Methods in Computer Science (CMCS ’98), volume 11 of Electronic Notes in Theoretical Computer Science. Elsevier Science B.V., 1998. Available at URL: www.elsevier.nl/locate/entcs. 30. B. Jacobs and J.J.M.M. Rutten. A tutorial on (co)algebras and (co)induction. Bulletin of EATCS, 62:222–259, 1997. Available on-line http://www.cs.kun.nl/˜bart/PAPERS/JR.ps.Z. 31. Jini. See: http://www.sun.com/jini.

Abstract Behavior Types: A Foundation Model for Components

69

32. J.N. Kok. Semantic Models for Parallel Computation in Data Flow, Logic- and Object-Oriented Programming. PhD thesis, Vrije Universiteit, Amsterdam, May 1989. 33. E. A. Lee and T. M. Parks. Dataﬂow process networks. In Proceedings of the IEEE, volume 83, pages 773–801, May 1995. 34. Edward A. Lee and David G. Messerschmitt. An overview of the ptolemy project. Technical report, Dept. of Electrical Engineering and Computer Sciences, University of California at Berkeley, 1993. 35. S. Li et al. Professional Jini. Mass Market Paperback, 2000. 36. V. Matena and B. Stearns. Applying Enterprise JavaBeans: Component-Based Development for the J2EE Platform. Java Series, Enterprise Edition. AddisonWesley, 2000. 37. B. Meyer. Eiﬀel: The Language. Prentice Hall, 1992. 38. B. Meyer. Reusable Software: The Base Object-Oriented Component Libraries. Prentice Hall, 1994. 39. R. Milner. Elements of interaction. Communications of the ACM, 36(1):78–89, January 1993. 40. R. Milner, J. Parrow, and D. Walker. A calculus of mobile processes, parts I and II. Information and Computation, 100(1):1–77, 1992. 41. Lawrence S. Moss. Coalgebraic logic. Annals of Pure and Applied Logic, 96(1– 3):277–317, 1999. 42. Lawrence S. Moss and Norman Danner. On the foundations of corecursion. Logic Journal of the IGPL, 5(2):231–257, 1997. 43. O. Nierstrasz and F. Achermann. A calculus for modeling software components. In F. S. de Boer, M. M. Bonsangue, S. Graf, and W.-P. de Roever, editors, Proc. First International Symposium on Formal Methods for Components and Objects (FMCO ’02), LNCS. Springer, 2003. (this volume). 44. S. Oaks and H. Wong. Jini in a Nutshell. O’Reilly & Associates, 2000. 45. G.A. Papadopoulos and F. Arbab. Coordination models and languages. In M. Zelkowitz, editor, Advances in Computers – The Engineering of Large Systems, volume 46, pages 329–400. Academic Press, 1998. 46. D. Pattinson and M. Wirsing. Making components move: A separation of concerns approach. In F. S. de Boer, M. M. Bonsangue, S. Graf, and W.-P. de Roever, editors, Proc. First International Symposium on Formal Methods for Components and Objects (FMCO ’02), LNCS. Springer, 2003. (this volume). 47. H. Reichel. An approach to object semantics based on terminal coalgebras. Mathematical Structures in Computer Science, 5:129–152, 1995. 48. J. J. M. M. Rutten. Elements of stream calculus (an extensive exercise in coinduction. In S. Brookes and M. Mislove, editors, Proc. of 17th Conf. on Mathematical Foundations of Programming Semantics, Aarhus, Denmark, 23–26 May 2001, volume 45 of Electronic Notes in Theoretical Computer Science. Elsevier, Amsterdam, 2001. 49. J.J.M.M. Rutten. Universal coalgebra: A theory of systems. Technical Report CS-R9652, Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands, 1996. Available on-line http://www.cwi.nl/ftp/CWIreports/AP/CS-R9652.ps.Z. 50. J.J.M.M. Rutten. Automata and coinduction (an exercise in coalgebra). Report SEN-R9803, CWI, 1998. Available at URL: www.cwi.nl. Also in the proceedings of CONCUR ’98, LNCS 1466, 1998, pp. 194–218.

70

F. Arbab

51. J.J.M.M. Rutten. Automata, power series, and coinduction: taking input derivatives seriously (extended abstract). Report SEN-R9901, CWI, 1999. Available at URL: www.cwi.nl. Also in the proceedings of ICALP ’99, LNCS 1644, 1999, pp. 645–654. 52. J.J.M.M. Rutten. Coalgebra, concurrency, and control. Report SEN-R9921, CWI, 1999. Available at URL: www.cwi.nl. Extended abstract in: Discrete Event Systems, R. Boel and G. Stremersch (eds.), Kluwer, 2000. 53. J.J.M.M. Rutten. Universal coalgebra: a theory of systems. Theoretical Computer Science, 249(1):3–80, 2000. 54. Davide Sangiorgi. Asynchronous process calculi: the ﬁrst-order and higher-order paradigms (tutorial). Theoretical Computer Science, 253, 2001. 55. Jon Siegel. CORBA: Fundamentals and Programming. John Wiley & Sons Inc., New York, 1 edition, 1996. 56. Alan Snyder. Encapsulation and inheritance in object-oriented programming languages. In OOPSLA ’86, pages 38–45, September 1986. 57. M. Wirsing, R. Hennicker, and R. Breu. Reusable speciﬁcation components. Technical Report MIP-8817, Passau University, 1988.

Understanding UML: A Formal Semantics of Concurrency and Communication in Real-Time UML Werner Damm1 , Bernhard Josko1 , Amir Pnueli2 , and Angelika Votintseva1

2

1 OFFIS, Oldenburg, Germany {damm,josko,votintseva}@offis.de The Weizmann Institute of Science, Rehovot, Israel [email protected]

Abstract. We deﬁne a subset krtUML of UML which is rich enough to express all behavioural modelling entities of UML used for real-time applications, covering such aspects as active objects, dynamic object creation and destruction, dynamically changing communication topologies in inter-object communication, asynchronous signal based communication, synchronous communication using operation calls, and shared memory communication through global attributes. We deﬁne a formal interleaving semantics for this kernel language by associating with each model M ∈ krtUML a symbolic transition system STS(M ). We outline how to compile industrial real-time UML models making use of generalisation hierarchies, weak- and strong aggregation, and hierarchical statemachines into krtUML, and propose modelling guidelines for real-time applications of UML. This work provides the semantical foundation for formal veriﬁcation of real-time UML models described in the companion paper [11].

1

Introduction

The establishment of a real-time proﬁle for UML [25], the proposal for a UML action language [24], and the installation of a special interest group shared between INCOSE and OMG to develop a proﬁle for UML addressing speciﬁcation of real-time systems at the system-level all reﬂect the pressure put on standardisation bodies to give a rigorous foundation to the increasing level of usage of UML to develop hard real-time systems. Its increased use also for safety critical applications mandates the need to complement these modelling oriented activities with an agreement on the formal semantics of the employed modelling constructs, as a prerequisite for rigorous

This research was partially supported by the German Research Council (DFG) within the priority program Integration of Speciﬁcation Techniques with Engineering Applications under grant DA 206/7-3 and by the Information Society DG of the European Commission within the project IST-2001-33522 OMEGA (Correct Development of Real-Time Embedded Systems).

F.S. de Boer et al. (Eds.): FMCO 2002, LNCS 2852, pp. 71–98, 2003. c Springer-Verlag Berlin Heidelberg 2003

72

W. Damm et al.

formal analysis methods, such as formal veriﬁcation of compliance to requirements. This need has been perceived by the research community, leading to a substantial body of formalisation of various subsets of UML, discussed in detail in Section 5 of this paper. The precise UML group has in a series of papers [5,6,7] been proposing a meta-modelling based approach, which however lacks the capability to address dynamics aspects at the level of detail required for formal veriﬁcation. Approaches based on translation into existing formalisms, such as e.g the π-calculus [26,27], ASMs [23], CASL [30], Object-Z [18] fall short of covering the rich range of behavioural modelling constructs covered in this paper. Closest to our work addressing the intricacies of understanding active objects are [29,30]. Our approach takes into account functional aspects of real-time systems, considering discrete time model with two levels of granularity. In this paper we focus our investigation on the semantic foundation of such critical features of real-time applications as concurrency (including the speciﬁcation of the time points for interferences) and two types of inter-object communication — synchronous, via operation calls, and asynchronous, via signal event emission. The described approach beneﬁts from numerous discussions with industrial users employing UML tools for the development of real-time systems, e.g. the partners of the IST projects Omega1 and AIT-Wooddes2 . The IST project Omega has developed an agreed speciﬁcation rtUML of those modelling concepts from UML required to support industrial users in their application development (Deliverable IST/33522/WP1.1/D1.1.1, [10]), subsuming such concepts as inheritance, polymorphism, weak and strong aggregation, hierarchical state machines, rich action language, active, passive, and reactive objects, etc., taking into account detailed issues such as navigability, visibility, changeability and ordering of association end-points, and allowing unbounded multiplicity of these. We propose a two-stage approach to give a formal semantics to rtUML: A precompilation step translates rtUML models into a suﬃciently compact sublanguage krtUML, eliminating the need at the kernel level to address the various facets of associations, inheritance, polymorphism, and hierarchical state-machines. We then give a formal semantics of krtUML, using the formalism of symbolic transition systems [22]. In this semantic framework, the state-space of the transition system is given by valuations of a set of typed system variables, and initial states and the transition relation are deﬁned using ﬁrst-order predicate logic. We show how to capture a complete snapshot of the dynamic execution state of a UML model, using unbounded arrays of object conﬁgurations to maintain the current status of all objects, and a pending request table modelling the status of all submitted, but not yet served operation calls. Object conﬁgurations include information on the valuation of the object’s attributes, the state-conﬁguration of it’s state-machine, as well as the pending events collected in an event-queue. Due to space restrictions, this paper focusses on the deﬁnition and formal semantics of krtUML, and only sketches some ideas of the precompilation phase. 1 2

IST-2001-33522, http://www-omega.imag.fr/index.php IST-1999-10069, http://wooddes.intranet.gr

Understanding UML: A Formal Semantics

73

We refer the reader to [10] for a full description of this step, as well as for the speciﬁcation of rtUML. The paper is organized as follows. Section 2 gives a formal deﬁnition of the constituents of a krtUML model. Section 3, the heart of this paper, develops the STS-based semantics, motivating and introducing in consecutive sections the system variables spanning the state-space of the transition systems, and the transition relation itself. Section 4 highlights aspects of the pre-compilation step, addressing inheritance and aggregation. Section 5 discusses related work.

2

The krtUML Language

In developing krtUML, we strived to maintain in puriﬁed form those ingredients of UML relating to the interaction of active objects. Intuitively, an active object (i.e., an instance of an active class) is like an event-driven task, which processes its incoming requests in a ﬁrst-in-ﬁrst-out fashion. It comes equipped with a dispatcher, which picks the top-level event for the event-queue, and dispatches it for processing to either its own state-machine, or to one of the passive reactive objects associated with this active object, inducing a so-called run-tocompletion step. We generalize this concept in Section 4 by proposing to group one active object and a collection of passive server objects into what we call components 3 . Within a component, all passive objects delegate event-handling to the one active object of the component; pre-compilation will capture this delegation relation by allowing to refer through my ac to the active object responsible for event-handling of a passive object. While the semantical model is rich enough to support communication through shared attributes, operation calls, and signals, we restrict our communication model so that all inter-component communications are purely asynchronous, i.e. via signal events. Our kernel language thus still caters for the diﬀerence between active and passive objects. All objects are assumed to be reactive, that is their behaviour can be made dependent on the current state of the system. We support so-called triggered operations, i.e. operation calls, whose return value depends on the current state of the system, as distinguished from what we call primitive operations, the body of which is deﬁned by a program in the supported action language. Since primitive operations only involve services of an object within the same component, pre-compilation can eliminate all calls to primitive operations by inlining (assuming, that the call-depth of primitive operations is bounded). In contrast, for triggered operations the willingness of the object to accept a particular operation call in a given state is expressed within the state-machine, by labeling transitions emerging from the state with the operation name as triggering guard, in the same style as the willingness of the object to react to a given signal event is speciﬁed by using this signal as triggering guard. Reﬂecting the wish to make the return value of triggered operations dependent on the object state, 3

In this paper, we use the notion of components which is a restriction of the more general concept from the standard UML. Namely, we consider only a kind of components containing exactly one active object.

74

W. Damm et al.

its “body” is “spread out” over the state-machine itself: the acceptance of a call will induce a run-to-completion step, hence the transition-labels passed during this run-to-completion step determine the response for this particular invocation of the triggered operation. Pre-compilation will have ﬂattened the hierarchical state-machines of rtUML into the ﬂat state-machines considered in our kernel language. It will also have split compound transition annotations, hence within the kernel language, only atomic actions and triggering guards (signal/operation names possibly with conditions) are allowed as labels of transitions. We now elaborate on the formal deﬁnition of krtUML models. Note that the diﬀerent ingredients are mutually dependent, hence we collect them in one formal deﬁnition. Deﬁnition 1 (krtUML model). A krtUML model M = (T, F, Sig, <, C, croot , A) consists of the following elements: •

T ⊇ {void, IB, IN}: A set of basic types comprising at least booleans and natural numbers.

•

F: A set of typed predeﬁned primitive functions.

•

Sig: A ﬁnite set of signals. Every instance of a signal is called signal event, or event for brevity.

•

< ⊂ Sig × Sig: A generalisation relation on signals, i.e. the transitive closure <+ is irreﬂexive, where ev1 < ev2 denotes that ev2 is a generalisation of ev1 . In the following, we use ≤ to denote the reﬂexive transitive closure of <.

•

C: A ﬁnite, non-empty set of classes. A class c = (c.isActive, c.attr, c.ops, c.sm) consists of: - c.isActive: A predicate. Class c ∈ C is called active iﬀ c.isActive = true. - c.attr: A ﬁnite set of typed attributes, which may not be of type void. - c.ops: A ﬁnite set of typed triggered operations. - c.sm: A c-state-machine as explained in (v) below in terms of c-actions over c-expressions. Each class contains two speciﬁc implicit attributes (introduced by the preprocessing): self ∈ c.attr keeping the reference to the object itself, and my ac ∈ c.attr specifying the event-handling object associated with class c.

•

croot ∈ C: The class of the root object (serving to specify system initialisation as deﬁned in Deﬁnition 7).

•

A ⊂ C: A subset of active classes called actors and used to denote external objects (part of the environment).

Understanding UML: A Formal Semantics

75

krtUML allows for some set of base types T, as well as a set F of functions operating on them, including, in particular, booleans and natural numbers together with all logical and arithmetical operators. Signals as well as operations may have parameters of well-deﬁned types. Note that we support explicitly generalisation hierarchies on signals (while generalisation hierarchies on objects are eliminated during pre-compilation). We now elaborate on the elements of krtUML model deﬁned so far, and start by deﬁning the supported types. Here we clear distinguish between base types and reference types (visible on the UML level), as well as a third category of types catering for implicit attributes representing association end-points, which typically hold a number of references depending on their multiplicity. By choosing to type these uniformly with functions from the naturals to classes, we cater for unbounded multiplicity. Operationally, we hence view such implicit attributes as unbounded arrays, with each index pointing to an associated object of a given class, or containing a nil-pointer. Deﬁnition 1 (Continued). (i) Typing: A krtUML model M deﬁnes the set of types T(M ) =df T ∪ TC ∪ Tas where TC =df {Tc | c ∈ C} is the set of reference types and Tas =df {IN → Tc | c ∈ C} the set of association types, which will be used to represent all kinds of associations described in [10] (i.e., composition, aggregation and neighbour). For each type τ ∈ T(M ), we assume existence of a designated element nilτ ∈ τ as a default value. We use ‘type’ to denote the type of attributes, functions etc. as follows: • For each class c ∈ C and each attribute a ∈ c.attr, type(a) ∈ T(M ) denotes the type of a ∈ c.attr, where type(self) = Tc ∈ TC and type(c.my ac) ∈ TC . •

For each class c ∈ C and each triggered operation op ∈ c.ops, typepar (op) = T1 × · · · × Tn denotes the parameter type where Ti ∈ T(M ) is the type of the i-th parameter and typer (op) ∈ T(M ) denotes the type of the reply value (typer (op) = void if op does not yield a return value). The type of op is deﬁned as type(op) = typepar (op) → typer (op).

•

For each f ∈ F, typepar (f ) = T1 × · · · × Tn denotes the parameter type where Ti ∈ T(M ) is the type of the i-th parameter and typer (f ) denotes the value type of f . The type of f is type(f ) = typepar (f ) → typer (f ).

•

For each ev ∈ Sig, typepar (ev) = T1 × · · · × Tn denotes the parameter type of ev where Ti ∈ T(M ) is the type of the i-th parameter.

We next introduce the expression language, supporting navigation expressions, accessing objects through association end-points, and closing this under application of base-type functions (including equality and boolean operations). Expressions are terms deﬁned in the scope of a class that can be used in transition guards orprimitive actions of this class.

76

W. Damm et al.

Deﬁnition 1 (Continued). (ii) Expressions: For a class c ∈ C, a c-expression ‘expr’ is deﬁned inductively as follows: •

•

•

Navigation expression: expr ::= r.a, where r ∈ c.attr with type(r) = Tc0 ∈ TC and a ∈ c0 .attr. We set type(expr) =df type(a). Note, that we only consider “ﬂat” navigation expressions in krtUML, where r can also refer to the object itself (if r = self). Association access: expr ::= expr1 [expr2 ], where expr1 and expr2 are c-expressions type(expr1 ) = (IN → Tc ) ∈ Tas and type(expr2 ) ∈ IN. We set type(expr) =df Tc . Function application: expr ::= f (expr1 , . . . , exprn ), where expr1 , . . . , exprn are c-expressions, f ∈ F, and type(expri ) matches the type of the i-th parameter of f , 0 < i ≤ n. We deﬁne type(expr) = typer (f ).

In the following deﬁnition of c-guards, c-actions and c-state-machines, ‘expr’, ‘expr1 ’, and ‘expr2 ’ denote c-expressions. Guards can be just boolean expressions, or express the willingness to accept a signal event or an operation call, possibly conjoined with a boolean condition. Deﬁnition 1 (Continued). (iii) Guards: For a class c ∈ C, a triggering guard to be used in the state-machine of class c ∈ C, c-guard for short, is one of the following: • Signal trigger: ev[expr], where ev ∈ Sig and type(expr) = IB. • Call trigger: op[expr], where op ∈ c.ops and type(expr) = IB. • Condition: [expr], where type(expr) = IB. We support a rich action language, allowing for object-creation and destruction, operation calls, event emission, and assignments of attributes and association end-points. The expression passed in an object creation is intended to pass the identity of the active-object responsible for event-handling. Reply actions serve to deﬁne the return value of a triggered operation. Deﬁnition 1 (Continued). (iv) Actions: A (primitive) action to be used in the state-machine of class c ∈ C, c-action for short, is one of the following: • Object creation: r.a := createc (expr), with r ∈ c.attr, type(r) = Tc0 ∈ TC , a ∈ c0 .attr and type(a) = Tc ∈ TC , and type(expr) = type(c .my ac). • Object creation (into association place): r.a[expr1 ] := createc (expr2 ), with r ∈ c.attr, type(r) = Tc0 ∈ TC , a ∈ c0 .attr, type(a) = (IN → Tc ) ∈ Tas , type(expr1 ) = IN, and type(expr2 ) = type(c .my ac).

Understanding UML: A Formal Semantics

77

•

Attribute assignment: r.a := expr, with r ∈ c.attr, type(r) = Tc0 ∈ TC , a ∈ c0 .attr, and type(a) = type(expr).

•

Association place assignment: r.a[expr1 ] := expr2 , with r ∈ c.attr, type(r) = Tc0 ∈ TC , a ∈ c0 .attr, type(expr1 ) = IN, type(a) = (IN → Tc ∈ Tas ), and type(expr2 ) = Tc .

•

Event emission: r.send(ev, expr1 , . . . , exprn ), with r ∈ c.attr and type(r) ∈ TC , ev ∈ Sig, n and (×i=0 type(expri )) = typepar (ev).

•

Operation call (ignoring reply value): r.call(op, expr1 , . . . , exprn ), with r ∈ c.attr, type(r) ∈ TC , op ∈ type(r).ops, n and (×i=0 type(expri )) = typepar (op).

•

Operation call (assigning value): r.a := r .call(op, expr1 , . . . , exprn ), with r ∈ c.attr, type(r) = Tc0 ∈ TC , a ∈ c0 .attr, and r ∈ c.attr, n type(r ) ∈ TC , op ∈ type(r ).ops, and (×i=0 type(expri )) = typepar (op), and type(a) = typer (op).

•

Operation call (assigning value into association place): r.a[expr0 ] := r .call(op, expr1 , . . . , exprn ), with r ∈ c.attr, type(r) = Tc0 ∈ TC , a ∈ c0 .attr, and r ∈ c.attr, n type(r ) ∈ TC , op ∈ type(r ).ops, and (×i=0 type(expri )) = typepar (op), and type(a) = (IN → c ) ∈ Tas , type(expr0 ) = IN, and typer (op) = c .

•

Setting reply value: replyτ (expr), with τ ∈ T ∪ TC and type(expr) = τ .

•

Object destruction: destroy(expr), with type(expr) ∈ TC .

Triggering Guards and Actions appear as decorations of transitions of the statemachine of a class. We assume a designated destruction state. Pre-compilation will extend the user-deﬁned state-machine by pre-ﬁxing the initial state with a sequence of transitions modelling constructor actions, while the destruction state is the unique entry point into a section added by pre-compilation modelling destructor-code. Pre-compilation also transfers hierarchical statecharts into ﬂat state-machines, each extended by a destruction state having no incoming transitions. Deﬁnition 1 (Continued). (v) State-machines: A c-state-machine for a class c ∈ TC is a tuple c.sm = (c.Q, c.q0 , c.qx , c.tr) where • c.Q is a ﬁnite set of states. •

c.q0 ∈ c.Q is the initial state.

•

c.qx ∈ c.Q is the destruction state, which is used to mark the beginning of the destructor’s actions.

78

W. Damm et al. •

c.tr ⊆ c.Q × ({γ | γ is a c-guard or c-action}) × c.Q is the transition relation.

We will use krtUML to denote the set of all krtUML models. Note that on the krtUML level, there is intentionally no inheritance relation on classes, since for each class c ∈ C, inheritance is explained by the introduction of uplink - and downlink -neighbour associations uplinkc , downlink ∈ c.attr for each superclass c of c in the preprocessing step. The uplink-association is used to model static polymorphism, whereas downlink-association allows to capture dynamic one. Further note that association access is restricted to accessing a single index, i.e. on the krtUML level, there are no operations like iteration over associations or adding references. We assume that such operations are also explained in terms of primitive actions by the preprocessing. The identiﬁcation of actors is not considered necessary from a semantical point of view, since actors should be treated as every other active class. But the information whether an object is an actor instance can be exploited in formal veriﬁcation: these objects need not necessarily be encoded like ordinary objects but can be interpreted as an assumption about environment behaviour, i.e. the expected sequences of input stimuli. In the following, we assume that the preprocessing step as outlined in Subsection 4.1 establishes the following set of requirements regarding the sets of attributes and the state-machines of a krtUML model, which we rely on in Section 3 when explaining the semantics. (i) All attribute and triggered operation names of all classes are pairwise different, for example qualiﬁed by a class name like c::a, and all states of all state-machines are pairwise diﬀerent. (ii) For each class c ∈ C, c.attr contains the attribute c::my ac to store the reference to the responsible active object such that c::my ac is of type Tc and c .isActive = true. (iii) Values of the implicit attributes c::self and c::my ac are assigned once at the initialization of the corresponding object and do not change during the life-time of the object. (iv) For each triggered operation op ∈ c.ops, c ∈ C, there are attributes c::oppi ∈ c.attr, 1 ≤ i ≤ n to hold local copies of the parameters, typed s.t. (c::opp1 , . . . , c::oppn ) = typepar (op) (v) For each ev ∈ Sig which c ∈ C is willing to receive, i.e. there is a transition (q, ev[expr], q ) ∈ c.tr, there are attributes c::evpi ∈ c.attr, 1 ≤ i ≤ n to hold local copies of the signal parameters, typed s.t (c::evp1 , . . . , c::evpn ) = typepar (ev).

3

krtUML Semantics

We will give the semantics of krtUML in terms of symbolic transition systems, proposed in [22] under the name Synchronous Transition Systems. Separate sub-

Understanding UML: A Formal Semantics

79

sections derive from types of krtUML models the type structure of related symbolic transition systems, and introduce the system variables required to represent a snapshot in the dynamic execution of a krtUML model. We then elaborate the way snapshots can evolve, deﬁning for each of the possible cases a transition predicate. Finally, we deﬁne the predicate characterizing initial snapshots, and collect all pieces of the transition relation into a full predicative deﬁnition of the transition relation, leading to a deﬁnition of the symbolic transition system associated with krtUML model. 3.1

Symbolic Transition Systems

We ﬁrst introduce the semantic model of symbolic transition systems, which allow for a purely syntactical description of a transition system by ﬁrst-order logic predicates over a set of typed system variables. Deﬁnition 2 (STS). A symbolic transition system (STS) S = (V, Θ, ρ) consists of V, a ﬁnite set of typed system variables, Θ, a ﬁrst-order predicate over variables in V characterizing the initial states, and ρ, a transition predicate, that is a ﬁrst-order predicate over V, V , referring to both primed and unprimed versions of the system variables (their current and next states). An STS induces a transition system on the set of interpretations of its variables as follows. Deﬁnition 3 (Runs of an STS). Let S = (V, Θ, ρ) be an ST S and T the set of types of variables in V. Let Dτ be a semantic domain for each τ ∈ T. (i) A snapshot s:V→

Dτ

τ ∈T

of S is a type-consistent interpretation of V, assigning to each variable v ∈ V a value s(v) over its domain. Σ denotes the set of snapshots of S. (ii) A snapshot s ∈ Σ inductively deﬁnes the value [[expr]](s) for ﬁrst-order predicates ‘expr’ over V and the value [[expr]](s, s ) for ﬁrst-order predicates ‘expr’ over V, V , where s provides the interpretation of unprimed and s the interpretation of primed variables in ‘expr’. (iii) A snapshot s ∈ Σ is called initial, iﬀ [[Θ]](s) = true. (iv) Let s, s ∈ Σ be snapshots of S. Snapshot s is called S-successor of s, iﬀ [[ρ]](s, s ) = true. (v) A computation, or run, of S is an inﬁnite sequence of snapshots r = s0 s1 s2 . . . , satisfying the following requirements: • Initiation: s0 is initial. •

Consecution: Snapshot sj+1 is an S-successor of sj , for each j ∈ IN0 .

80

W. Damm et al.

(vi) The set of all computations of S is denoted as runs(S). We use r(i) to denote the i-th snapshot of a run r ∈ runs(S) and r/i =df r(i) r(i + 1) r(i + 2) . . . to denote the inﬁnite suﬃx starting at r(i), i ∈ IN0 . 3.2

System Variables for the krtUML Semantics

We motivate our choice of types and system variables using snapshots related to the Automated Rail Car System described in [15], a model of autonomous rail-bound cars which transport passengers between terminals and which adhere to a simple arrive- and departure protocol to allocate and de-allocate platforms inside the terminal. We refer the reader to [15] for details.

Fig. 1. System Conﬁguration: A variable of type Tsconf contains one object conﬁguration for every object identiﬁer in OC . The example of an object conﬁguration oconf for the object (Car, 5) is shown enlarged.

Figure 1 depicts the way, how an object-conﬁguration is captured. It shows enlarged the entry of an object of class Car, currently executing. The current state-machine conﬁguration is illustrated by a state-machine, where in fact only the current state is stored. An object onﬁguration not only gives the current valuation of all its attributes as well as its current state conﬁguration, but also maintains the current object status (elaborated below), the event-queue (for active objects only), and a dispatcher status (for active objects only) used to enforce a single thread of control within the objects grouped into one component. The semantic entity representing a single class is a (potentially unbounded) array of object conﬁgurations, with each entry corresponding to a single instance of this class. The object status reﬂects the life-cycle of an object (see Figure 2). Prior to creation, objects are perceived as being dormant. Creation of a new object instance will pick a dormant index of the corresponding class, and awake the object to realities of life. During life, objects become suspended when waiting for completion of an operation call, and idle, (except for the special case discussed below) when becoming stable, i.e. when a run-to-completion step terminates. This happens when reaching a state, where all outgoing transitions are

Understanding UML: A Formal Semantics

81

either guarded by signal triggers (of the form ev[expr]) or call triggers (of the form op[expr]), or conditions (of the form [expr]) which are evaluated to false. In the particular case of accepting destruction, the object status will switch to dying, remaining in this status until its last run-to-completion step induced from the objects’ destructor is ﬁnally completed. From then on, the object status will remain dead. Note, that destruction of an aggregate object (w.r.t. the composition association, deﬁned in rtUML) induces destruction of all its parts, hence dying may be a long and painful process. Our semantics thus allows to observe nastities such as sending events to dying objects, as well as detecting dangling references. alive queue empty and no pending calls create dormant

locally enabled transition

idle take event or accept trig. op.

become stable destroy

executing initiate trig. op. call

dying

destruction completed

dead

pick up result

suspended

Fig. 2. Object life-cycle.

For the rest of the current section, let M = (T, F, Sig, <, C, croot , A) be a krtUML model. We now deﬁne for the semantic types employed in the deﬁnition of the associated symbolic transition system, as well as the semantic domain of all semantic types. The type-system of semantic types subsumes all types of the krtUML model. Deﬁnition 4 (Object Reference Types and Domains). For each basic type τ ∈ T, we assume the existence of a corresponding semantic type Tτ with domain Dτ . For each type Tc ∈ TC , we denote by Oc or TTc the corresponding semantic type and choose DOc =df {c} × IN as its domain. We call OC with domain DOC =df c∈C DOc , the object reference type resp. domain. For each object type Oc , we assume existence of a designated element nilc ∈ DOc to serve as a default value. For each each association type τ = (IN → Tc ) ∈ Tas , Dτ =df (IN → DOc ) is the domain of Tτ . We now deﬁne the semantic type of system conﬁgurations and its associated domain, by ﬁrst deﬁning the semantic type of object conﬁgurations. Deﬁnition 5 (Object and System Conﬁguration). (i) An object conﬁguration oconf = (status, ac, sc, eq, ds) consists of the following elements:

82

W. Damm et al. •

An object status ‘status’ of type Tobjstatus with associated semantic domain DTobjstatus =df {dormant, idle, executing, suspended, dying, dead}.

• •

An object attribute conﬁguration ‘ac’ of type Tac =df c∈C (c.attr → TT(M ) ). An object state-machine conﬁguration ‘sc’ of type Tsc with associated semantic domain DTsc =df c.Q. c∈C

•

∗ The event queue eq of type Teq =df Teqe , i.e. a sequence of entries Ttypepar (ev) . (dest, ev, par) of type Teqe =df OC × Sig × ev∈Sig

For an event-queue entry, ‘dest’ denotes the destination, ‘ev’ the event type (i.e. signal name), and ‘par’ the event parameters. We will use ε to denote empty event queue. • A dispatch reference ds of type Tds =df OC , i.e. a reference to some object of any class which is used to denote the object currently processing an event. Thus the type of an object conﬁguration of M is Toconf (M ) =df Tobjstatus × Tac × Tsc × Teq . × Tds (ii) The type of a system conﬁguration is Tsconf (M ) =df OC → Toconf (M ). (iii) We will call a component to be a set Cm(o) = {o |o .my ac = o} of objects assigned to the same event dispatcher o. The symbolic transition system uses the variable sconf : Tsconf to maintain the object-conﬁguration of all objects of M . Note that, in general, the assignment of an event dispatcher to a reactive object can be user deﬁned. In [10], a default assignment is given derived from the composition association.

Fig. 3. Pending Request Table: The pending request table is a system variable of type Tprt . It contains one entry for every object identiﬁer in OC .

We collect the status of all pending operation calls within a pending request table. An example on Figure 3 shows enlarged the entry for calls from an object

Understanding UML: A Formal Semantics

83

of class Car. Currently the call of triggered operation engage for a Cruiser is pending. Here we exploit the fact, that all objects become suspended on calling an operation. We can thus maintain the status of all operation calls in a table indexed by sender objects resp. actors. Each entry in the pending request table maintains the identity of the receiver, the name of the requested operation, the list of parameters, a result-ﬁeld, and status information. The life-cycle of an entry in the pending request table is depicted in Figure 4. Whenever the object owning the entry emits a new operation call, the status of the entry switches to pending. It will remain in this status until the receiving object is willing to serve the call, which causes the status to switch to busy. Once the run-to-completion step induced from accepting the call is terminated, the result of the call is entered into the result ﬁeld of the entry, and its status changes to completed. This will allow the calling object to pick up the result and resume computation, causing the status of the entry to become unused.

unused

caller calls trig. op.

pending

callee accepts call

busy

callee becomes stable

completed

caller picks up result

Fig. 4. Life-cycle of a triggered operation call.

Deﬁnition 6 (Pending Request Table). (i) A pending request table entry opreq = (dest, op, status, result, params) maintains: • The receiver of a triggered operation call ‘dest’ of type Tdest with associated semantic domain DTdest =df OC . • The triggered operation identiﬁer ’op’ of type Top with associated se mantic domain DTop =df c.ops. c∈C •

The triggered operation status ’status’ of type Topstatus with semantic domain DTopstatus =df {unused, pending, busy, completed}.

•

The result (or reply) ‘result’ of type Tres with associated semantic domain typer (op). DTres =df c∈C op∈c.ops

•

The parameters ‘params’ of type Tpar with associated semantic domain typepar (op). DTpar =df c∈C op∈c.ops

84

W. Damm et al.

Thus the type of a pending request table entry is Topreq (M ) =df Tdest × Top × Topstatus × Tres × Tpar . (ii) The type of the pending request table is Tprt (M ) =df OC → Topreq (M ).

The symbolic transition system uses the variable prt : Tprt to maintain the operation requests of all objects of M . Furthermore, we need a boolean ﬂag sysfail, which is used to indicate an undeﬁned state of the system if e.g., it is tried to read the attribute of object reference nil or if the type of the reply action does not match the type of the currently processed triggered operation. Performing some arithmetic computations can also raise this ﬂag in failure situations (e.g., division by 0). Initially, sysfail is set to false and it remains set, once it changed to true. 3.3

The Transition Predicate

Intuitively, there is a transition between two snapshots s, s if there exists exactly one object o ∈ OC whose conﬁguration changes by one of the following reasons: •

• • •

Object o is idle and an event is dispatched to it by its active object or an event with destination o is discarded since it is not enabled in o’s state-machine. (Coarse-granularity ﬂow of control is kept by elements ds of active objects’ conﬁgurations.) Object o is idle and accepts a triggered operation call. (Fine-granularity ﬂow of control is kept by elements dest of the pending request table.) Object o is executing or dying, unstable, and takes a transition of its statemachine and thereby executing an action. (No changes in the ﬂow of control.) Object o is suspended and picks up the result of a triggered operation call which has been completed by the callee. (Fine-granularity ﬂow of control kept by dest in prt.)

The system may remain in snapshot s if no object is executing (implying that pending request table is empty) and all event queues are empty. In the following, we formalize each of the above conditions separately as ﬁrstorder logic predicates which are then used to construct the transition predicate of the semantics S(M ). For brevity, we use the following abbreviations for o ∈ OC in the deﬁnitions of predicates over sconf and prt: • • • •

o.status ≡df sconf(o).status and analogously for sc, ds, eq. o.a ≡df sconf(o)(a), i.e. the value of attribute a. o.a.b ≡df sconf(sconf(o)(a))(b), for attributes b of reference type. For an event or operation parameter tuple e, we use o.evp := e to denote simultaneous assignment of the i-th components of e to their corresponding attributes evpi in o.

Understanding UML: A Formal Semantics

85

A primed abbreviation indicates that the primed system variable is to be used, for example o.a ≡ sconf (o).a. For an event-queue q = e1 e2 . . . en ∈ DTeq we introduce the following abbreviations: • • •

head(q) =df e1 denotes the ﬁrst entry of the queue if q = ε. tail(q) =df e2 . . . en denotes q with the ﬁrst entry removed and ε if n < 2. enqueue(e, q) =df q e denotes the result of appending entry e : Teqe to q.

For brevity we assume that boolean expressions expr are evaluated to ⊥ if it is for example tried to read an attribute via a reference with value nil. Note that in the following incremental deﬁnition of the transition predicate, we use an assigment symbol “:=” which has to be processed as explicated in Deﬁnition 7 to yield the ﬁnal transition predicate. Informally, this symbol indicates that there is no diﬀerence between the current and next states of the system variables other than speciﬁed explicitly in the sequence of the “:=”-expressions (or their constituents). We will use ⊕ to denote logical XORoperator: a ⊕ b =df (a ∨ b) ∧ ¬(a ∧ b). We ﬁrst deﬁne for each object o ∈ Oc the predicate stable(o) in the current system conﬁguration as follows4 : stable(o) =df ∀ (q, γs , q ) ∈ c.tr : q = o.sc =⇒ ((γs ≡ “ev[expr1 ]” ∧ sysfail := (sysfail ∨ expr1 = ⊥)) ∨ (γs ≡ “op[expr2 ]” ∧ sysfail := (sysfail ∨ expr2 = ⊥)) ∨ (γs ≡ “[expr3 ]” ∧ ¬expr3 ∧ sysfail := (sysfail ∨ expr3 = ⊥))) Getting an Event. Formally, an event ev1 with destination o can be dispatched to o from the event queue of its active object, if no other object of o’s active object is currently processing an event and if a transition (q, γ, q ) guarded by a superclass ev of ev1 is enabled, i.e. originating at the current state q (cf. Figure 5): ρget event =df γ ≡ “ev[expr]” ∧ o.my ac.ds = nil ∧ expr = true ∧ sysfail := (sysfail ∨ expr = ⊥) = ε ∧ head(o.my ac.eq).dest = o ∧ o.my ac.eq ∧ o.my ac.eq := tail(o.my ac.eq) ∧ (∃ ev1 ∈ Sig : ∧ head(o.my ac.eq).ev = ev1 ∧ ev1 ≤ ev ∧ (¬stable(o) =⇒ (o.my ac.ds := o ∧ o.status := executing)) ∧ o.evp := head(o.my ac.eq).par) 4

Here and later on: γ ≡ “ev[expr]” (γ ≡ “op[expr]” or γ ≡ “[expr]”) means that the label γ of the current transition (q, γ, q ) is of the form ev[expr] (op[expr] or [expr], resp.), i.e. a signal trigger (a call trigger or a condition, resp., cf. Deﬁnition 1 (iii) ).

86

W. Damm et al.

sconf(o)

(c2,i)

...

...

my_ac ep1 ep2 sc

...

(c2,i) eqi nil eqi

(c2,i) ? ? q

(O,ev,evp1,evp2, ...)

.. . tail(eq i)

q0 q

...

get_event

my_ac eq ds

O=(c1,n) status idle

sconf´(o)

(c2,i)

ev[expr]/

O=(c1,n) status exec

...

my_ac ep1 ep2 Sc

...

(c2,i) evp1 evp2 q´

q´

my_ac eq ds

(c2,i) eqi (c1,n) eqi

.. . tail(eq i)

q0 q

ev[expr]/

q´

Fig. 5. Transition relation: ρget event .

Element o.my ac.ds, when not equal to nil, locks its component for processing a signal event. It can be released (and the component can start to process the following event, i.e. new run-to-completion step) only when all computations within the component are completed. Note that we exploit the fact, that the syntactic category of boolean expression used in the deﬁnition of krtUML models is subsumed in the expression language of the ﬁrst-order logic used to deﬁne transition predicates. In particular the above deﬁned abbreviations apply to expressions of transition predicates thus providing the intended relation to sconf. Accepting a Triggered Operation. Object o can accept a triggered operation call op if a transition (q, γ, q ) with guard op is enabled in the current state q and some object o1 has called op of o: ρaccept op =df γ ≡ “op[expr]” ∧ expr = true ∧ sysfail := (sysfail ∨ expr = ⊥) ∧ (∃ o1 ∈ OC : prt(o1 ).dest = o ∧ prt(o1 ).op = op ∧ prt(o1 ).status = pending ∧ (¬stable(o) =⇒ prt(o1 ).status := busy ∧ o.status := executing) ∧ (stable(o) =⇒ prt(o1 ).status := completed) ∧ prt(o1 ).result := nil ∧ o.opp := prt(o1 ).opp ) Note that an object can call a trigger operation only from an object of the same component because of the restrictions on the inter-component communication. Thus, o.my ac.ds = o.my ac.ds = o1 during the execution of operations within one RTC-step (the change of the control between objects at this level of communication is captured by prt(o).dest with prt(o).status ). Skipping Guards. Object o can take a transition guarded with a boolean expression only, if the expression evaluates to true: ρskip guard =df γ ≡ “[expr]” ∧ expr = true ∧ sysfail := (sysfail ∨ expr = ⊥)

Understanding UML: A Formal Semantics

87

Discarding Events. If there is an event for object o in the queue of o’s active object but o is not willing to accept it, i.e. if no transition with a matching signal is enabled, then the event is simply discarded: ρdiscard event =df o.my ac.ds = nil = ε ∧ head(o.my ac.eq).dest = o ∧ o.my ac.eq ∧ o.my ac.eq := tail(o.my ac.eq) ∧ (∀ (q, ev1 [expr], q ) ∈ c.tr : ≤ head(o.my ac.eq).ev) (expr = false ∨ ev1 ∧ sysfail := (sysfail ∨ expr = ⊥)) Note that triggered operation calls are not discarded, but remain until the callee accepts the call. Executing Actions. Object o can execute an action if the current transition (q, γ, q ) is enabled and annotated with the action. Below we distinguish two types of actions — operation calls and other actions — treating them in two separated subformulas. These subformulas will be combined with diﬀerent contexts — conditions on their performance — in the ﬁnal transition predicate. An assignment action simply assigns a value to the destination. An event-sending action causes a new event to be appended to the queue of the destination’s active object. A reply action causes the parameter value to be written into the reply ﬁeld of the pending request table at o1 if o processes the call from another object o1 ; otherwise system failure is indicated. A destroy action causes the destination’s state-machine conﬁguration to be changed s.t. qx is the current state and the status is “dying”. Then the subsequent steps will execute the actions of the destructor. Killing a dying or dead object causes a system failure: ρnon op action =df

(γ ≡ “r.a := expr” ∧ (expr = ⊥ =⇒ o.r.a := expr) ∧ (sysfail := (sysfail ∨ o.r = nil ∨ expr = ⊥))) ∨(γ ≡ “r.send(ev, expr1 , . . . , exprn )” n ∧ sysfail := (sysfail ∨ o.r = nil ∨ expri = ⊥) i=0

∧ o.r.my ac.eq := enqueue(o.r.my ac.eq, (o.r, ev, (expr1 , . . . , exprn )))) ∨(γ ≡ “replyτ (expr)” ∧ [(∃ o1 ∈ OC : prt(o1 ).dest = o ∧ prt(o1 ).status = busy =⇒ prt(o1 ).result := expr ∧ sysfail := (sysfail ∨ τ = typer (o1 ) ∨ expr = ⊥)) ⊕ sysfail := true])

88

W. Damm et al.

∨ (γ ≡ “destroy(expr)” = nil ∧ [(expr = ⊥ ∧ ∃ o1 ∈ OC : o1 = expr ∧ o1 .my ac = o.my ac ∧ (o1 .status ∈ {dormant, dying, dead} =⇒ [o1 .sc := qx ∧ (¬stable(o) =⇒ o1 .status := dying) ∧ (stable(o) =⇒ o1 .status := dead)))] ⊕ sysfail := true]) An operation call action suspends object o and conﬁgures o’s entry of the pending request table s.t. it denotes the callee, the called triggered operation, and the parameters. Initially the status of the operation is “pending”. A creation action is handled like a triggered operation since the caller should block until an object of the desired class is readily created with all inherited parts and all aggregated parts: ρinit opcall or

create

=df (γ ≡ “r.call(op, expr1 , . . . , exprn )” ∨ γ ≡ “r1 .a := r.call(op, expr1 , . . . , exprn )”) ∧ o.r.my ac = o.my ac ∧ sysfail := (sysfail ∨ o.r = nil ∨

n

expri = ⊥

i=1

∨ o.r.my ac = o.my ac) ∧ (o.status := suspended ∧ prt(o).dest := o.r ∧ prt(o).op := op ∧ prt(o).status := pending ∧ prt(o).result := nil ∧ prt(o).opp := (expr1 , . . . , exprn )) ∨(γ ≡ “r.a := createc1 (expr)” ∧ o.my ac = expr ∧ = expr ∨ sysfail := (sysfail ∨ expr = ⊥ ∨ o.my ac (expr = o1 ∈ OC ∧ o1 .status ∈ {dormant, dying, dead})) ∧ (∃ o1 ∈ Oc1 \ {nilc1 } : o1 .status = dormant ∧ o1 .status := idle ∧ (¬c1 .isActive =⇒ o1 .my ac := expr) ∧ (c1 .isActive =⇒ o1 .my ac := o1 ) ∧ o.r.a := o1 ∧ o.status := suspended ∧ prt(o).dest := o1 ∧ prt(o).op := createc1

∧ prt(o).status := pending ∧ prt(o).result := nil ∧ prt(o).params := nil)

Understanding UML: A Formal Semantics

89

Becoming Stable. If object o becomes stable, some bookkeeping takes place. If o was processing an event, the dispatch reference of its active object is reset. If o was executing a triggered operation, the pending request table status is set to “completed ” to event completion to the caller. In both cases, o becomes idle. If o is executing the run-to-completion step starting at qx , then it becomes dead: ρbecoming

stable

=df (stable(o) =⇒ [o.my ac.ds = o =⇒ (o.my ac.ds := nil ∧ o.status := idle)] ∧ [∀ o1 ∈ OC : prt(o1 ).dest = o ∧ prt(o1 ).status = busy =⇒ (prt(o1 ).status := completed ∧ o.status := idle)]) ∧ (o.status = dying =⇒ o.status := dead)

Picking Up a Result. Object o can pick up the result of a previous triggered operation call if the callee has set the status of o’s pending request table entry to “completed ”: ρpick

up result

=df prt(o).status = completed =⇒ prt (o) := nil ∧ (¬stable(o) =⇒ o.status := executing) ∧ ((γ ≡ “r1 .a := r0 .call(op, expr1 , . . . , exprn )” ∧ ¬o.r1 = nil) =⇒ o.r1 .a := prt(o).result) ∧ (sysfail := (sysfail ∨ o.r1 = nil)

The complete execution of an example of a triggered operation engage() is illustrated in Figure 6. The ﬁrst row of the tables show the relevant part of the system conﬁguration at time t , just after c has entered the call into the pending request table. Note that c has not yet taken the transition, it remains in its previous state. The second row shows time t , just after the Cruiser m has accepted the call. At time t , m has just completed its run-to-completion step, i.e. written the result, changed the operation’s status to “completed”, and become idle. This is an indicator for c to pick up the result at time t , i.e. read the reply value from the table, clear the table entry, and now take the transition. c is executing and continues its run-to-completion step, assuming that c does not become stable. 3.4

The STS Semantics of a krtUML Model

Putting all speciﬁcations of diﬀerent kinds of transitions together we deﬁne the semantics of krtUML as a symbolic transition system over the three system variables (from Subsection 3.2) with the initial condition and combined transition relation speciﬁed in the following deﬁnition.

90

W. Damm et al.

c:Car

itsCar itsCrs

m:Cruiser disengaged

dep

/itsCruiser.call(engage)

crs>

disengage/

engage/reply(0)

engaged

m.status

m.sc

status

ret

par

idle

disengaged

prt[c]’: m engage

pending

nil

nil

sconf’’: suspended dep executing disengaged

prt[c]’’: m engage

busy

nil

nil

sconf’’’: suspended dep

idle

engaged

prt[c]’’’: m engage completed

0

nil

sconf’’’’:

idle

engaged

prt[c]’’’’: nil

nil

nil

c.status

c.sc

sconf’: suspended dep

executing

crs

dest

op

nil

nil

Fig. 6. Triggered Operation Call. Changing status of the caller c, callee m, and the called operation engage in the pending request table between the beginning (unprimed variables, not depicted here) and the end (at time t ) of the operation call: the values of selected elements of sconf and prt.

Deﬁnition 7 (krtUML Model Semantics). Let M = (T, F, Sig, <, C, croot , A) be a krtUML model. The semantics of M is the STS STS(M ) = (V, Θ, ρ), where System Variables: V =df {sconf : Tsconf (M ), prt : Tprt (M ), sysfail : IB}. Initial condition: Initially a single object of class croot exists and has status “executing”. All other objects are dormant, and all attributes have default values: Θ =df ∃ o0 ∈ Ocroot \ {nilcroot } : (o0 .status = executing ∧ o0 .ds = o0 ∧ o0 .sc = croot .q0 ∧ o0 .eq = ε ∧ (∀ o1 = (c1 , n1 ) ∈ OC \ {o0 } : o1 .status = dormant ∧ o1 .sc = c1 .q0 ∧ o1 .ds = nil ∧ o1 .eq = ε)) ∧ ∀ o = (c, n) ∈ OC : o.c::self = o ∧ (∀ a ∈ c.attr : o.a = niltype(a) ) The unique single object of class croot which is alive at the beginning of a run r is called the root object of r. Transition relation: The intermediate predicate ρ0 composes the above introduced subpredicates as follows: ρ0 =df ∀ o ∈ OC : o.status = executing ∧ o.eq = ε ∨ ¬sysf ail ∧ ∃ o = (c, n) ∈ OC ∃ (q, γ, q ) ∈ c.tr :

Understanding UML: A Formal Semantics

91

o.sc = q ∧ o.sc := q ∧ ( [o.status = idle ∧ (ρget event ⊕ ρaccept op )] ∨ [(o.status = executing ∨ o.status = dying) ∧ (ρskip guard ∨ ρnon op action )] ∨ [o.status = suspended ∧ ρpick up result ]) ∧ ρbecoming stable ∨ o.sc := o.sc ∧ ([o.status = idle ∧ ρdiscard event ] ∨ [o.status = executing ∧ ρinit opcall or create ]) The ﬁnal transition relation ρ is obtained from ρ0 by adding a frame axiom which requires that only those places of s are allowed to change in the transition to s , which get new values by an assignment “:=” in ρ0 , and changing the assignments to “=”. The semantics of a krtUML model M is given as the set runs(STS(M )) of all computations in M . It is easy to see that ρ eﬀectively restricts activity to at most one object, resulting in an interleaving of actions from diﬀerent objects. The following consequence from Deﬁnition 3 and Deﬁnition 7 formalises the main properties of the described krtUML semantics. Consequence: Let M be a krtUML model, r ∈ runs(STS(M )), (sconf, prt, sysfail) ∈ r, and o = o¯ ∈ OC . Then (i) (Level of the Computation Concurrency) sconf(o).status = sconf(¯ o).status = executing ⇐⇒ o ∈ Cm(o1 ), o¯ ∈ = o2 — only objects from diﬀerent components can be exeCm(o2 ) ∧ o1 cuting at the same time. (ii) (Component Interference Points) sconf(o).my ac.ds = nil ⇐⇒ (∀ˆ o ∈ OC : sconf(ˆ o).my ac = sconf(o).my ac ⇒ sconf(ˆ o).status ∈ {idle, dead, dying}). An object o can accept an event only if other objects from its component are not currently executing.

4

Assessing the Expressiveness of krtUML

In this section we indicate how to reduce richer UML models in rtUML as supported in the IST project Omega [10] to the krtUML subset deﬁned in Section 2. Besides, we explain the choice of the design decision behind the formal semantics. 4.1

Translating rtUML to krtUML

UML deﬁnes associations and association end-points to capture relations between classes. Semantically, association-end points maintain pointers to objects accessible through this association end-point (subject to restrictions on visibility

92

W. Damm et al.

and navigability). Our precompilation introduces these as what we call implicit attributes, and translates code invoked when creating compound objects for establishing links employing a set of implicit operations such as ‘add to association end’. Note the introduction of the special type Tas provided for such attributes in the krtUML model. In particular, pre-compilation will create implicit attributes for maintaining knowledge about all (possibly dynamically created) component objects5 of a strong aggregation (also called composition); it will include calls for creation of component objects with bounded multiplicity in the constructor code of the aggregate object; it will contain calls for destroying every existing component object within the destructor code of the aggregate object. Regarding generalisation of objects, we create private instances of all predecessors in the generalisation hierarchy (much as the creation of a compound objects induces creation of its components) to keep all operations and statecharts overwritten in the specialised objects. This allows to capture both static and dynamic polymorphisms using implicit attributes uplink and downlink to navigate across these instances to ﬁnd e.g. the deﬁnition of operations matching a call. We do not require any restrictions on the statechart inheritance: a sub-class might have state-machine overwritten independently from that of the corresponding super-class. All private copies maintain their own object-conﬁguration, hence e.g. accepting a triggered operation will only change the state-conﬁguration of that state-machine corresponding to the object oﬀering the operation in the generalisation hierarchy. The statechart inheritance described in [10] can be considered as a particular case. Another precompilation step transfers hierarchical UML statecharts from rtUML to ﬂat state-machines of krtUML without changing its behavior. The states in a ﬂattened state-machine correspond to state conﬁgurations (a set of states) from the original statechart extended with the history function (keeping information for the history connectors). Besides, for the statechart of each reactive class c we add the following kinds of auxiliary states: •

•

•

5

One or several “creation” states q0 , . . . , qn (n ≥ 0), where q0 has the outgoing transition guarded by triggered operation createc and followed by the constructor code, ending with the initial state of the original (hierarchical) statechart. Only the statechart of the root-class does not contain any triggered operation at its “creation” transitions. A “destruction” state qx with outgoing transitions containing the destructor code. Then every state in the ﬂattened state-machine containing termination vertice (from the original statechart) has an outgoing transition to some auxiliary state without triggering guard and with action destroy(self); Several “internal” states necessary to split complex transitions, e.g. transitions containing non-primitive actions.

Note the diﬀerence between a component object, speciﬁed by the composition association as a “part” of an aggregate object and used at the rtUML level, and the notion of component as a group of one active and several passive objects, used at the krtUML level.

Understanding UML: A Formal Semantics

4.2

93

The Choice of rtUML Communication Scheme

Certain transformations in the pre-compilation steps are based on modelling assumptions. In this paper we only elaborate on the concept of components as introduced in Deﬁnition 5 (iii). When targeting distributed system-implementations of real-time systems, synchronous operation calls clearly cannot be used for component communication. Indeed, any estimation of worst-case execution time would have to cater for a waiting delay until the receiving component is able to accept a call, which itself may be blocked while awaiting serving of an operation call by yet a third component. We thus assume a modeling style, where inter-component communication is restricted to signal-based communication. To exploit this, we allow the grouping of objects into components; within a component, no restrictions are placed as to inter-object communication. Based on the pragmatics of active objects in UML, we mandate, that each such componentgroup contains exactly one active object, and allow to include an arbitrary number of passive objects in the group. Active objects are assumed to be reactive, and reactive passive objects are required to delegate their event-handling to the one active object within the group.

my_ac my_ac

eq

car:Car itsCar

itsCar

term:Terminal itsTerm

my_ac

itsCruiser

itsHnd

crs:Cruiser

my_ac

eq

itsTerm

itsHnd

hnd:CarHandler

itsPmgr

mgr:PlatformMgr

Comp.1

Comp.2

Fig. 7. UML Components: A snapshot of a model part shows active objects car and term (with their event queues) and passive objects crs, hnd, and mgr. Reactive objects car, crs, and hnd are denoted by associated schematic state-machines. Active objects car and term designate their components Comp.1 and Comp.2, respectively.

Figures 7 and 8 illustrate the concepts of components and intercomponent communication using the Automated Rail Cars System example from [15]. The graphical representation of a snapshot of a model on Figure 7 shows objects on the krtUML level. Each reactive object has a link to an active object via my ac which is assumed to be constant for the object’s lifetime. Objects referring to the same active object form a component. Figure 7 shows two components with a single link across a component-boundary. All event-handling is delegated to the component’s active object, which keeps all events in its event queue. When

94

W. Damm et al.

the event has reached the top of the queue, the active object may decide to take the event from the queue and dispatch it to the destination. This is indicated in Figure 8 by light-gray arrows. The semantics in Section 3 is explained from the perspective of the destination.

DepartReq dispatch

my_ac

my_ac

eq

car:Car itsCar

itsCar

term:Terminal itsTerm

my_ac

itsCruiser

itsHnd

crs:Cruiser

my_ac

eq

itsTerm

itsHnd

hnd:CarHandler

itsPmgr

mgr:PlatformMgr

Comp.1

Comp.2

Fig. 8. Event communication: Sending an event of DepartReq from car to hnd in fact enters the event into the event queue of term, which is the active object associated with hnd.

The semantics enforces, that at most a single thread of control is active within one component. We feel, that deviating from this modelling paradigm, and in particular allowing multiple threads to execute within one object could easily cause modelling errors not acceptable for hard real-time applications.

5

Related Works

All attempts to deﬁne UML semantics can be classiﬁed into diﬀerent orthogonal dimensions. One direction in the semantics classiﬁcation is the level of UML coverage. Many people have been trying to build the semantics of individual diagrams of the UML – e.g., [20,4] etc. on state-machines, [12] on collaboration diagrams, [13,16] etc. on class diagrams, [28] on use cases, [3] on activity diagrams – or just to give formal foundations for action language (e.g., [24,2]). Because all diagrams are only views on one and the same model, the attempts to give semantics for separated UML diagrams fail in producing the right semantics for the entire UML. In our approach a symbolic transition system represents both static and dynamic aspects. The combination of statics and dynamics is also given in [29] which considers the problem of deﬁning active classes with associated state-machines. It gives a very ﬁne interleaving semantics for state-machines in terms of transition systems. In diﬀerence to our approach, the authors do not give precise semantics for state-machines, for event queue handling, consider a

Understanding UML: A Formal Semantics

95

limited inheritance, and they treat only ﬂat UML state-machines without action semantics. Another coverage level relates to the problems with possible concurrency as well as aspects of objects communication, which have been uncovered in [29] and not addressed in the original UML 1.x documents itself. Such open problems are typical for so called loose semantics introduced in [16], where the aspects of concurrency and object communication are not ﬁxed to some design decision, but cover diﬀerent implementations. Such loose semantics is not suitable for formal veriﬁcation. Our paper tries to overcome this problem by ﬁxing one detailed semantics as an example of the feasibility of UML semantic for veriﬁcation purposes. From other side, there are a number of UML modelling and/or veriﬁcation tools implementing precise semantics by translating UML models to programming language or model checker internal formats ([17,9,1,21]). These tools have diﬀerent limitations on the supported UML features and do not provide formal description of the implemented semantics or it is just technical translations. H. Hußmann [16] proposes the third dimension for the classiﬁcation of attempts towards the UML formal semantics, dividing approaches into the following groups: 1) Naive set-theoretic approach. M. Richters and M. Gogolla [31] have suggested to use simple set-theoretic interpretation for UML class diagrams. In this approach, the semantics of a class diagram is described as a set of hypergraphs, corresponding to a conﬁguration of objects. This approach has the low level of abstraction, where the concepts of UML itself are more abstract than the formal semantics given to it. This kind of semantics is mostly used for the formal deﬁnition of OCL constraints within UML models. We do not consider OCL in our approach. 2) Metamodelling semantics. This group of approaches is based on the application of a “bootstrapping” principle [7], where the semantics of UML is described using a small subset of UML as a core based on static semantics only. The approach of the pUML group to the UML semantics is given in [6,5,2]. Essentially, an algebraic speciﬁcation is used to describe legal (local) snapshots of the system without treating actions, whereas our approach gives a formal semantics for dynamic behaviour taking into account primitive action semantics as well. The study of A. Kleppe and J. Warmer [19] is based on the pUML OO meta modelling approach. In addition, it takes into account that static and dynamic viewpoints on the system can not be separated. But the formal semantics for state-machines is not really deﬁned, the set of primitive actions is very restrictive, and the transporting mechanism for signal inter-object communication is not speciﬁed. In our approach, we give a formal semantics for actual state-machines (not their unfolding into actions) with a larger set of primitive actions. We also resolved open problems with concurrency. 3) Translation semantics. An approach, which tries to keep the right abstraction level, deﬁnes translation from UML class diagrams to traditional speciﬁcation languages (Z [14], Object-Z [18], CASL [30] etc.). For example, G. Reggio et al. [30] proposed a general schema of the UML semantics by using an exten-

96

W. Damm et al.

sion of the algebraic language CASL for describing individual diagrams (class diagrams and state-machines) and then their semantics are composed to get the semantics of the overall model. Also other UML diagram types have been translated to formal notations, e.g., using Abstract State Machines ([4,3,23,8]). E. B¨ orger et al. [4] deﬁned the dynamic semantics of UML in terms of ASM extended by new construct to cover UML state-machine features. The model covers the event-handling and the run-to-completion step, and formalises object interaction by combining control and data ﬂow features. However, the authors did not give a complete solution to solve transition conﬂicts and it is not clear how ﬁrable transitions are selected. The semantics implemented by UML-tool vendors via code generation or model simulation can be also classiﬁed to this group of approaches (among other: [17,9,1]). Diﬀerently from these approaches, our study provides one formalism (STS) for both static and dynamic semantics, which also contains action language. 4) Combination of the approaches mentioned above. An example of combination of several approaches can be found in [23]. In this research, static semantics is deﬁned using meta-modelling mechanism of UML, the execution semantics is expressed as ASM programs. The study covers all features contained in the class diagrams, and in the body of the operations (quite thorough set of action types). The aspects of inter-object communications were not really covered and the semantics of UML statecharts was not addressed, although it can be accompanied by the complementary papers [3] and [4]. But these articles consider state-machines separated from the rest of UML, whereas our approach provides one semantics for class diagrams and statecharts.

6

Conclusion

With respect to the approaches sketched above, the main novelty of our approach is that it resolves uncovered problems with concurrency and object communication by giving a formal semantics for a chosen concrete decision. W. Damm and B. Westphal [11] have shown that this semantics can be used for formal veriﬁcation. In our approach we allow that both active and passive objects can be reactive, thus considering event communication between all objects. We also capture two diﬀerent kinds of inter-object communication – synchronous (via triggered operation calls) and asynchronous (via signal events). Thus, we have provided the semantical foundation for a rich sublanguage of UML which is expressive enough to deal with industrial UML models for real-time applications. Our partners from Verimag have proposed extensions of the semantical model focussed on real-time, in particular taking into account the need to support annotations for real-time scheduling. Ongoing work within Omega builds on the semantical foundation layed down in this paper to develop a veriﬁcation environment for real-time UML.

Acknowledgements We gratefully acknowledge the contribution of our Omega partners in ﬁnetuning the semantics.

Understanding UML: A Formal Semantics

97

References 1. Telelogic AB. Telelogic Tau, 2003. http://www.telelogic.com/products/tau/index.cfm. 2. J.M. Alvarez, T. Clark, A. Evans, and P. Sammut. An Action Semantics for MML. In Proc. UML 2001, 2001. http://www.cs.york.ac.uk/puml/mmf/AlvarezUML2001.pdf. 3. E. B¨ orger, A. Cavarra, and E. Riccobene. An ASM Semantics for UML Activity Diagrams. In T. Rus, editor, Proc. AMAST 2000, volume 1816 of LNCS, pages 293–308. Springer-Verlag, 2000. 4. E. B¨ orger, A. Cavarra, and E. Riccobene. Modeling the Dynamics of UML State Machines. In Y. Gurevich, Ph.W. Kutter, M. Odersky, and L. Thiele, editors, Abstract State Machines, Theory and Applications, International Workshop, ASM 2000, Proceedings, volume 1912 of LNCS, pages 223–241. Springer-Verlag, 2000. DBLP, http://dblp.uni-trier.de. 5. T. Clark, A. Evans, and S. Kent. The Metamodelling Language Calculus: Foundation Semantics for UML. In Proc. FASE 2001, pages 17–31, 2001. www.dcs.kcl.ac.uk/staﬀ/tony/docs/MMLCalculus.ps. 6. T. Clark, A. Evans, S. Kent, S. Brodsky, and S. Cook. A Feasibility Study in Rearchitecting UML as a Family of Languages Using a Precise OO Meta-Modelling Approach, version 1.0, September 2000. Available from http://www.puml.org. 7. T. Clark, A. Evans, S. Kent, and P. Sammut. The MMF Approach to Engineering Object-Oriented Design Languages. In Proc. Workshop on Language Descriptions, Tools and Applications (LDTA2001), 2001. Available via http://www.puml.org. 8. K. Compton, J. Huggins, and W. Shen. A Semantic Model for the State Machine in the UML. In G. Reggio, A. Knapp, B. Rumpe, B. Selic, and R. Wieringa, editors, Dynamic Behaviour in UML Models: Semantic Questions, Workshop Proceedings, UML 2000 Workshop, Bericht 0006, pages 25–31. Ludwig-Maximilians-Universit¨ at M¨ unchen, Institut f¨ ur Informatik, October 2000. http://www.kettering.edu/∼jhuggins/papers/uml2000.ps. 9. Rational Software Corporation. Rational Rose Family, 2003. http://www.rational.com/products/rose/index.jsp. 10. W. Damm, B. Josko, A. Pnueli, and A. Votintseva. A Formal Semantics for a UML Kernel Language. Omega Technical report, part 1 of the deliverable D1.1.2, Project IST-2001-33522 OMEGA, January 2003. Available from http://www-omega.imag.fr/doc/d1000009 6/D112 KL.pdf. 11. W. Damm and B. Westphal. Live and Let Die: LSC-based Veriﬁcation of UMLModels. In Proceedings FMCO’02, 2003. (to appear). 12. G. Engels, J.H. Hausmann, R. Heckel, and S. Sauer. Dynamic Meta Modeling: A Graphical Approach to the Operational Semantics of Behavioral Diagrams in UML. In Proceed. of the 3d International Conference on the UML 2000, October 2000. 13. A. Evans, R. France, K. Lano, and B. Rumpe. The UML as a Formal Modeling Notation. In The Unifed Modeling Language: the ﬁrst international workshop, June 1998. Springer-Verlag, 1999. 14. A.S. Evans and A.N. Clark. Foundations of the Uniﬁed Modeling Language. In 2nd Northern Formal Methods Workshop, Ilkley, electronic Workshops in Computing. Springer-Verlag, 1998. http://www.cs.york.ac.uk/puml/papers/nfmw97.ps.

98

W. Damm et al.

15. D. Harel and E. Gery. Executable Object Modeling with Statecharts. IEEE Computer, 30(7):31–42, 1997. 16. H. Hußmann. Loose Semantics for UML, OCL. In Proceedings 6th World Conference on Integrated Design and Process Technology (IDPT 2002). Society for Design and Process Science, June 2002. 17. I-Logix Inc. Rhapsody, 2002. http://www.ilogix.com/products/rhapsody/index.cfm. 18. S.-K. Kim and D. Carrington. Formalizing the UML Class Diagrams Using ObjectZ. In France and Rumpe, editors, Proc. UML’99, volume 1723 of LNCS, pages 83–98. Springer-Verlag, 1999. 19. A. Kleppe and J. Warmer. Uniﬁcation of Static and Dynamic Semantics of UML, 2001. http://www.klasse.nl/english/uml/uniﬁcation-report.pdf. 20. G. Kwon. Rewrite Rules and Operational Semantics for Model Checking UML Statcharts. In Proceed. of the 3d International Conference on the UML 2000, University of York, October 2000. 21. J. Lilius and I.P. Paltor. vUML: a Tool for Verifying UML Models. Turku Centre for Computer Science, Abo Akademi University, Finland. Technical Report. 22. Z. Manna and A. Pnueli. The Temporal Logic of Reactive and Concurrent Systems: Speciﬁcation. Springer-Verlag, New York, 1991. 23. I. Ober. Harmonizing Design Languages with Object-Oriented Extensions and an Executable Semantics, PhD Thesis. Institut National Polytechnique de Toulouse, France, April 2001. 24. Object Management Group. UML 1.4 with Action Semantics, Final Adopted Speciﬁcation, ptc/02-01-09, January 2002. Available from http://www.kc.com/as site/home.html. 25. Object Management Group. UML Proﬁle for Schedulability, Performance, and Time Speciﬁcation, ptc/02-03-02 OMG Adopted Speciﬁcation, March 2002. Available from http://cgi.omg.org/docs/ptc/02-03-02.pdf. ¨ 26. G. Overgaard. Formal Speciﬁcation of Object-Oriented Meta-Modelling. In T.Maibaum, editor, Proceedings Fundamental Approaches to Software Engineering, FASE, number 1783 in LNCS. Springer-Verlag, 2000. ¨ 27. G. Overgaard. Using the BOOM Framework for Formal Speciﬁcation of the UML. In Proceedings of Deﬁning Precise Semantics for UML, 2000. ¨ 28. G. Overgaard and K. Palmkvist. A Formal Approach to Use Cases and Their Relationships. In UML 1998, 1998. 29. G. Reggio, E. Astesiano, C. Choppy, and H. Hußmann. Analyzing UML Active Classes and Associated State Machines - A Lightweight Formal Approach. In FEAS 2000, 2000. ftp://ftp.disi.unige.it/pub/person/ReggioG/Reggio99a.ps. 30. G. Reggio, M. Cerioli, and E. Astesiano. Towards a Rigorous Semantics of UML Supporting Its Multiview Approach. In FASE 2001, 2001. ftp://ftp.disi.unige.it/pub/person/CerioliM/FASE2001.pdf. 31. M. Richters and M.Gogolla. On Formalizing the UML Object Constraint Language OCL. In T.-W. Ling, S. Ram, and M.L. Lee, editors, Proc. 17th International Conference Conceptual Modelling (ER’98), volume 1507 of LNCS, pages 449–464. Springer-Verlag, 1998.

Live and Let Die: LSC-Based Veriﬁcation of UML-Models Werner Damm and Bernd Westphal Carl von Ossietzky Universit¨ at Oldenburg Department f¨ ur Informatik PO Box 2503, 26111 Oldenburg, Germany {damm,westphal}@informatik.uni-oldenburg.de

Abstract. We present a strategy for automatic formal veriﬁcation of Live Sequence Chart (LSC) speciﬁcations against UML models in the semantics of [7] employing the symmetry-based technique of Query Reduction [18,34,44] and the abstraction technique Data-type Reduction [34]. Altogether this allows for automatic formal veriﬁcation without providing ﬁnite bounds on the numbers of objects created during a run of the system. Our presentation is grounded on a speciﬁc formal interpretation of LSCs for the UML domain in terms of [7] which is rich enough to in particular express properties about objects which are created only during activation of the LSC.

1

Introduction

The increasing use of UML or specialised sublanguages thereof in the domain of safety-critical systems design raises a need for formal veriﬁcation techniques. A necessary pre-requisite is on the one hand a formal semantics of a UML sublanguage suﬃciently rich for behavioural description as provided by [7] and on the other hand a formal foundation of one of UML’s speciﬁcation languages for inter-object communication like Sequence or Collaboration Diagrams. Previous eﬀorts towards automatic formal veriﬁcation of a signiﬁcant sublanguage of UML concentrate on diﬀerent subsets of the state-machine language and consider only a single object or an explicitly given ﬁnite set of objects, i.e. do not address dynamic creation or destruction of objects during runtime [9,27,4,40,41,39,28] or don’t elaborate on this topic [12]. Recent achievements [43] implement object creation and destruction explicitly in the input language of the employed formal veriﬁcation tool based on “switching on and oﬀ” objects like in [7] or translate the UML model into an

This research was partially supported by the German Research Council (DFG) within the priority program Integration of Speciﬁcation Techniques with Engineering Applications under grant DA 206/7-3 and by the Information Society DG of the European Commission within the project IST-2001-33522 OMEGA (Correct Development of Real-Time Embedded Systems).

F.S. de Boer et al. (Eds.): FMCO 2002, LNCS 2852, pp. 99–135, 2003. c Springer-Verlag Berlin Heidelberg 2003

100

W. Damm and B. Westphal

intermediate language [37] which provides constructs for this kind of dynamics s.t. the problem of choosing a ﬁnite representation is shifted to the translationstep from the intermediate language to the employed formal veriﬁcation tool. Both approaches presuppose a ﬁnite bound on the number of objects alive in each snapshot of a run as long as the target is a ﬁnite-state formal veriﬁcation tool1 . In the following we present a technique which allows to overcome these limitations under certain premises even for ﬁnite-state methods. The speciﬁcation languages used in previous approaches range from temporal logic expressions over variable names on the level of the underlying modelchecker’s input language [41,39,28] to temporal logic (resp. patterns) on the UML model level [43,12]. The tools presented in [27,40] provide automatic solving of “drive to collaboration” tasks, i.e. to verify for UML with real-time information whether a given system is able to show the behaviour described by collaboration diagrams. We propose to adopt the language of Live Sequence Diagrams [5] (LSC) for UML as the speciﬁcation language for inter-object communication. The LSC language is a superset of UML’s Sequence Diagram language – thus appealing for the UML designer – and explicitly designed to overcome the limitations in expressiveness of Sequence Diagrams as discussed in [5]. Our deﬁnition of LSCs for UML is in particular designed to express properties over instances which are created during a run of the system, and even during the activation of the LSC, by interpreting instance lines as universally or existentially quantiﬁed logical variables, thus a system satisﬁes an LSC if all runs satisfy all instantiations of the quantiﬁcation resp. if there exists a run which satisﬁes an instantiation. Hence the whole speciﬁcation can be discharged by carrying out numerous separate concrete veriﬁcation tasks, each a binding of concrete object instances to instance lines [25,42]. The observable communication comprises events and so called triggered operations, i.e. operations whose behaviour is deﬁned by a state-machine, and is integrated into the fully abstract LSC semantics of [24,26]. The authors of [30] present an alternative approach to explain binding of instances to instance lines with the same underlying intuition, but in addition allow to quantify single instance lines. The description is tailored for the application in their play-in/play-out tool [14], that is, for observing or “playing-out” a complete system. Our presentation is in contrast chosen to be able to apply the theory of symmetry reduction and data-type reduction to consider only a reduced system for automatic formal veriﬁcation. The most closely related approach for temporal logic patterns in the domain of object-oriented systems is the (textual) Bandera Speciﬁcation Language [3] of the Bandera Java veriﬁcation toolset, which allows to express similar quantiﬁcations. 1

Note that these obstacles are raised by aiming at automatic formal veriﬁcation, they naturally do not apply in general to proposals for formal semantics of UML, which in contrast use methods which intentionally do not require ﬁnite bounds and don’t explicitly represent “not existing” objects, e.g. [15,23,36,35].

Live and Let Die: LSC-Based Veriﬁcation of UML-Models

101

The numerous veriﬁcation tasks obtained by binding objects to instance lines in the system are a prominent application of a technique for which the authors of [44] coined the term “Query Reduction”, since not the state-space of the veriﬁed transition system is reduced, but the number of concrete bindings to be proven. A small representative set implies the (possibly inﬁnite) whole set of properties by symmetry. This way to exploit symmetry was ﬁrst demonstrated by the author of [31,34] for general temporal-logic properties of the form of a universal quantiﬁcation over a symmetric type. Then it is suﬃcient to prove only a representative set of concrete bindings since all other bindings are implied by symmetry. This technique applies to systems where the state of replicated components is kept in an array data-structure indexed by a symmetric type and to properties which claim that for all indices i a property φ0 (i) holds, thus in particular to our interpretation of LSCs. The idea to exploit in formal veriﬁcation the symmetries of a system caused by replicated components, like processors in a cache-coherency protocol, actually dates back to 1993, when the authors of [10] and [18] independently discovered that symmetries of transition systems can be exploited to prove certain properties on the quotient graph by the equivalence relation induced by symmetry instead of on the full transition system. The authors of [18] even provided a set of criteria which allows to declare and syntactically check symmetric data types in the system description language of the MurΦ model-checker [19]. A disadvantage of the quotient graph approach is that the set of properties is restricted to safety properties independent from individual identities like “none of the symmetric components of the system runs into a deadlock” [18] or to properties which are itself symmetric, e.g. identical under permutation of indices [10]. The dSPIN [16] variant of the SPIN model-checker is an application of this kind of symmetry reduction in software-veriﬁcation exploiting heap symmetries — system states which diﬀer only in the allocation of objects into memory places on the heap are equivalent on the program level in languages like Java — and analogously process (allocation) symmetries [17]. The published results yet comprise only checking for absence of deadlock. As mentioned before, the direct eﬀect of query reduction is just not a reduction of the transition graph, although indirectly a reduction may be obtained by standard techniques like cone-of-inﬂuence reduction which apply more eﬀectively on the concretely bound properties and may render tasks feasible, which are far too complex in the original form. Yet cone-of-inﬂuence reduction alone does not address the problem that the state-space of a UML model is in general inﬁnite if there are no ﬁnite bounds on the number of objects. Therefore we propose to apply the over-abstraction technique Data-type Reduction [34] which by heuristics abstracts away all objects which are not explicitly referenced in the concrete binding of object instances to LSC instance lines from the view of the bound objects s.t. these remaining objects can in particular not determine the actual number of objects in the system.

102

W. Damm and B. Westphal

Thus there is no requirement for a ﬁnite bound on the number of simultaneously alive objects. This technique also supports reasoning about parameterised systems: if a property can be proven for an abstraction constructed for an arbitrary concrete choice of parameters, than for any choice of larger parameters the abstraction also satisﬁes the property since it is also an abstraction for the larger parameters. Note that the length of the event queue is a priori still unbounded in a UML design, thus for the scope of this paper we assume a ﬁnite upper bound on the length of event queues to reach the domain of automatic techniques for ﬁnite state veriﬁcation. For the category of so called mode separated models, [6] presents an exact abstraction which eliminates queues from the model and yields a ﬁnite representation. The remainder of the paper is organised as follows. In section 2 we introduce signatures, expressions, and interpretations to be able to deﬁne symbolic transition systems (STS) [29], our computational model, and to deﬁne linear temporal logic (LTL) over expressions which provides the ground for the presentation of the general semantics of LSCs and the specialisation of the LSC language for the context of UML in terms of [7] in Section 3. In section 4, we provide the theory of query reduction, contribute the yet missing proofs, show how it applies to LSCs in the context of UML, and brieﬂy introduce a running example for the subsequent sections. Section 5 presents the theory of data-type-reduction together with yet missing proofs and discusses the common class of “interference” false-negatives caused by the data-type-reduction abstraction. Section 6 discusses brieﬂy how interference could be avo