ECOOP '99 - Object-Oriented Programming: 13th European Conference Lisbon, Portugal, June 14-18, 1999 Proceedings

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

Author: Rachid Guerraoui

34 downloads 636 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





 







closeAccount



createAccount



 T5 noSuchAccount



newAccount



  closeAccount  close







 open



closeAccount



 



initialDeposit







newAccount







openAccount



} Fig. 2. Cooperative Object class specifying the Bank interface.



For instance, according to the IDL of Fig. 1, the service findAccount is mapped onto three places: findAccount for the SIP, findAccount for the SOP and findAccount for the SEP. The invocation of one service results in one token holding all in and inout parameters being deposited in its SIP. The role of the ObCS net is to process this parameter token in some way, and eventually deposit a result token (holding the result of the service, plus all out or inout parameters) in the SOP, thus completing the processing of the invocation. An invocation that raises an exception at some point will instead result in an exception token being deposited in the SEP. Fig. 2 illustrates both the graphic syntax of a Cooperative Object class and the textual annotations that are necessary to complete its description. These textual annotations are: • The list of the interfaces that the CO class specifies (keyword specifies). In this case, the BankSpec class specifies the Bank interface.



 Formal Specification and Prototyping of CORBA Systems



•



•



485



The description of the places’ type: for instance, the Accounts place holds tuples of the form <string, BankAccount>, i.e. the name of a bank account, and the associated reference to a BankAccount object. The type for the input, output and exception ports needs not be stated, since it is deduced from the signature of the associated service. For example, the type of the newAccount input port is <string, float>, and the type of its output port is . The description of the transitions’ preconditions and actions: Empty actions default to no action, and empty preconditions default to true. Only the transitions with non-default precondition or action need to be stated in the textual part.



The picture also illustrate the notation for inhibitor arcs (ended with a circle instead of an arrow) and for test arcs (ended with a barred arrow). The BankSpec class describes a sensible behavior for the bank entity. For example, it states that an Account reference can be retrieved (through the findAccount service) only after an account with the same name has been created (through the newAccount service) and before it has been closed (through the closeAccount service). It also specifies under which conditions exception might be raised (for instance a nameAlreadyExists exception is raised when the newAccount service is called with a name parameter that matches a previously registered name). Such behavioral constraints could have been modeled just as well using a conventional ADT-based specification. However, the description of more subtle behaviors requires a formalism expressive enough to encompass concurrency and synchronization constraints. In order for the invocation of services to proceed in a sound way, the ObCS structure must respect a set of constraints. Informally, an object will provide either a result or an exception for each invocation, and will only provide results if it has been previously invoked. With respect to the ObCS, the arrival of one token in the SIP will eventually result later in exactly one token being deposited either in the SOP or in the SEP. These structural constraint on the ObCS are easily expressed in terms of Petri nets theory, and can be checked automatically. The formal description of these structural constraints can be found in [7], where the notion of Operation Control Structure (OpCS) is also defined. Informally, the OpCS of a service is a subnet encompassing it’s SIP, SEP and SOP. The OpCS of the newAccount service is especially noticeable: unlike the other two services (findAccount and closeAccount), it is not made of atomic transitions, but of a subnet encompassing the createAccount and open transitions. This feature allows for internal concurrency within a BankSpec instance: While an invocation of newAccount is being processed (i.e. when the newAccount place holds one token), other incoming invocations of findAccount or closeAccount can be serviced (if the marking of the Account place permits it). Moreover, several invocations of newAccount can be serviced concurrently (this will result in the newAccount place holding several tokens). Finally, when the service invocation returns (by setting the reference to the newly created BankAccountSpec object in the newAccount return port), the BankSpec



 486



R. Bastide, O. Sy, P. Palanque



object continues an internal processing, namely to initialize the BankAccountSpec object with its initial balance (transition initialDeposit). This faithfully models the way actual banks proceed in the creation of new customer accounts (at least in France): If a customer goes to a bank to create an account with an initial deposit, the account will be created immediately, but it will take some time before the account is actually credited with the initial deposit. If the account’s balance is accessed in the meantime, it will be zero. The BankSpec also takes care that an account is not closed before the initial deposit is performed (inhibitor arc between openAccount and close). Mapping for parameter-passing modes. The semantics for the three parameterpassing modes of CORBA IDL is clear. • in parameters are values provided by the caller, that the service may use at its own will; • out parameters are values computed by the service, and returned to the caller; • inout parameters are values transformed by the service, i.e. provided by the caller and returned to it after being processed. Inout parameters require a special treatment in the OpCS structure: in order to ensure that any inout parameter is properly transmitted from the Service Input Port to the Service Output Port, a sufficient condition is to check that the parameter name appears on every arc connected to each place of the OpCS. Inter-object invocations in transitions. We want to be able to model CORBA systems, and not only isolated CORBA servers. Actually, the behavior of one class in isolation will often be of little interest, and will only become meaningful when we can describe how an instance of the class may interact with other instances of other classes in the system. CORBA objects interact with one another by invoking services defined by the IDL interfaces they support. The Cooperative Object formalism supports this form of cooperation by allowing the action of a transition to be the invocation of a service. The operational semantics of such an invocation transition is a client / server protocol that can be formally defined in terms of Petri nets. This client server protocol we use has been first presented in [27] for basic Petri nets, extended to object-oriented high-level Petri nets in [3], and is presented in [31]. The fact that not only the internal behavior of objects, but also their communication protocol is defined in terms of Petri nets allow us to reason about systems of cooperating objects, and not only on isolated instances. The theoretical details of how this client-server protocol is adapted to the semantics of CORBA inter-object communication are given in [7]. Mapping for exceptions. CORBA IDL allows specifying exceptions that may be raised during the processing of an invocation. An exception is an object of a specific data-type, and can hold information on the causes of its occurrence or other useful data. When an exception is raised, the normal processing of the service is cancelled, the result, out and inout parameters of the service are undefined, an exception object is instantiated and only this object is transmitted to the client of the invocation.



 Formal Specification and Prototyping of CORBA Systems



487



In order to specify properly the behavior of a CORBA system, our formalism needs to address two concerns: • Define under which conditions an exception may be raised during the processing of an invocation, and what corrective actions are eventually needed in the server object to restore a consistent state. • Define what action a client object needs to take if a service invocation results in an exception instead of providing the expected result. The first point is tackled by exception transitions: Exception transitions are labeled by the name of the exception data-type that is raised. They can have input and output arcs from any place of the OpCS of one service, but necessarily have exactly one output arc connected to the SEP of this service. The occurrence of an exception transition models the fact that an exceptional condition has occurred during the processing of an invocation, and that this processing cannot be carried any further. The T5 transition in Fig. 2 is an exception transition. It models the fact that an account needs to be known by the bank before being closed. The second point is tackled by: • a simple syntactic extension of the graphic syntax of invocation transitions (called emission rules), not illustrated in our case study, • a straightforward extension of the client-server protocol described in [7], acknowledging the fact that an invocation can have two different outcomes: a normal outcome, providing the expected results, or an exception outcome, providing no result other than the exception raised by the server. class BankAccountSpec specifies BankAccount { place closed  = { <0> }; place open ; transition transferFunds { precondition { (amount + balance) >= 0; } action { newBalance = amount + balance; } } transition t5 { precondition { (amount + balance) < 0; }



 488



R. Bastide, O. Sy, P. Palanque  T1 accountIsClosed



close 



closed







T2











T3



transfer



T4



balance close



T5 InsufficientFunds















open



open



T6



 transfer 







open











balance



 transferFunds



transfer







} Fig. 3. CO class specifying the BankAccount interface.



The behavioral specification of bank accounts is shown in Fig. 3. This CO class specifies the BankAccount interface and implicitly specifies the Account interface since the two are related through inheritance. Several new syntactic constructs are illustrated in this class: • Places can be provided with an initial marking, stating their content right after an instance of this class is created. In this case, an account is created in the closed state, with an initial balance of 0, as stated by the definition of the closed place. • The transferFunds and T5 transitions are in structural conflict. This conflict is deterministically solved by the preconditions of these two transitions, which are mutually exclusive. Thus, the InsufficientFunds exception is raised when the current balance is lower than the amount that one tries to withdraw. Note that (for the sake of brevity), the specification detailed in the BankSpec and BankAccountSpec classes offers no provision for reopening a closed account. This could be achieved, for instance, by providing a subclass of BankSpec with additional services to transfer the balance from a closed account to a newly created account.



5 Prototyping CORBA Systems A well-known advantage of Petri nets is their executability. This is highly beneficial to our approach, since as soon as a behavioral specification is provided in terms of CO classes, this specification can be interpreted to provide additional insights on the possible evolutions of the system.



 Formal Specification and Prototyping of CORBA Systems



489



Cooperative Object class



IDL text



IDL compiler



PetShop Interactive Environment



IDL repository



Legend



ObCS



Inheritance



Server skeleton



Client stub



Code generation Bidirectional CORBA invocations Edition Access for DII / DSI Prototype generator Third-Party CORBA object



Standalone server prototype



ORB



Fig. 4. Architecture of the PetShop environment



Our approach is supported by a tool called PetShop (Fig. 4), which includes a distributed implementation of the high-level Petri net interpreter described in [5], rewritten in Java. The implementation is such that: • An interpreted ObCS can invoke (from an invocation transition) a service of a “third party” CORBA server running outside of the environment; • Conversely, an external CORBA client can call a service of a Cooperative Object, regardless of the fact that this service invocation will be performed by interpretation of the CO ObCS. This offers complete interoperability between the CORBA world and our formalism, and enables us to work in realistic settings, where we possess the complete behavioral specification of some objects only, but where we can nonetheless access objects provided by other sources, of which we know only the CORBA IDL. In this section, we describe how the PetShop CASE tool fits into the CORBA program development cycle. As a whole, PetShop completely supports the following phases • Editing of the behavioral specification as a Cooperative Object class; • IDL generation; • Cooperative object class analysis; • Interactive interpretation of models;



 490



R. Bastide, O. Sy, P. Palanque



• Prototype generation. Cooperative object class editing. The Petri net editor provides the graphical interface for both the editing of the textual part and the ObCS part of each CO class. As the ObCS can specify several IDL interfaces, the tool also provides access to existing IDL interfaces and allows for the creation of new IDL interfaces. IDL generation. The original goal of our approach is to add behavior to IDL. A frequent design activity is to start from pre-defined IDLs (such as the ones provided in the definition of the CorbaServices [23]) and to write a behavioral specification for it. The designer can also start from scratch and generate CORBA IDL matching a given behavioral specification. Cooperative object class analysis. As Cooperative Objects are a subclass of Petri nets, the analysis module allows proving some interesting properties of the nets such as invariants, conflicts (structural properties), liveness, boundedness, home state (behavioral properties). We wish to use Petri net analysis techniques not only to prove properties on an isolated object, but also to analyze constructs specific to object-oriented systems. For example, when two IDL interfaces are related through inheritance, some form of behavioral inheritance needs to be respected for CO classes that specify these interfaces [35]. We also want to analyze the co-operation between several CO instances, to check properties of a system of interacting objects. This is possible since the client-server protocol presented in [7] is described in terms of Petri nets, which allows generating a single static Petri net from the ObCS of classes in a system [3], [31]. This global net can be used to prove properties of the system as a whole. Interactive interpretation of models. One of the well-known advantages of Petri nets is their executability. This feature is exploited in the PetShop tool, that offers the well known advantages of interpreted environments in terms of flexibility, interactivity and ease of use ([19], [21])[21]. PetShop allows an interpreted object to seamlessly access "real" third-party CORBA servers, or to be accessed as a server from other CORBA objects developed independently and maybe in a different programming language. In our implementation, each edited net is executed using the ObCS interpreter described in [5]: the editor itself acts as a client/server program. As a result, as soon as a net is edited, an instance of the ObCS starts executing. The interpreted instance is accessed using the dynamic CORBA mechanisms of Dynamic Invocation Interface (DII) and Dynamic Skeleton Interface (DSI). This allows us to test the behavior in a CORBA runtime environment and make real distributed experiments between CORBA objects hosted by the same or different computers. The environment allows for graphic debugging of the interpreted net, by examining or modifying its marking, or even modifying its control structure dynamically. Prototyping Distributed System. In the last phase of development, the programmer is interested in shipping a finished stand-alone CORBA object that can be run without the support of the CASE tool. For that reason PetShop can generate a prototype and



 Formal Specification and Prototyping of CORBA Systems



491



launch instances of the prototypes. Those instances are “almost functional” implementations, in the sense that only behavioral requirements are dealt with. Other “quality of service” requirements, such as performance, persistence, replication or fault-tolerance, have to be taken care of in a completely functional implementation. The generated prototype is still an interpreted high-level Petri net, but does not have graphical features, like graphic debugging or live editing capabilities, which allows it to perform faster, and to function on machines that lack graphic abilities.



6 Conclusion and Future Work The approach presented here is motivated by the momentum gained by CORBA as a standard for distributed object systems, and by the evidence that some form of abstract behavioral modeling supporting the CORBA object model can be of great help in the development life-cycle of such systems. Several aspects of the CORBA/Cooperative Objects integration are not presented here, for space reasons: among these are the support for unidirectional service invocation ( oneway services in IDL), or the provision for IDL constructs such as constants and context information. Among the works in progress on our approach are the following: • Use of Petri net analysis techniques: Our approach has a strong operational bias: we accept to trade full analysis possibilities in favor of modeling power. However, we do not give up the potential for analysis potential of Petri nets altogether. Currently, our tool includes the usual Petri net analysis algorithms (such as P and T-Invariants, liveness, boundedness, siphons and traps) that operate on the ObCS underlying net, i.e. the ObCS where all variables and data types are removed. We are currently in the process of assessing which of the analysis result for basic Petri net are preserved in the high-level ObCS. We are also investigating analysis techniques especially devised for high-level nets. • Analysis of object-oriented features: we wish to use Petri net analysis techniques not only prove properties on an isolated object, but also to analyze constructs specific to object-oriented systems. For example, when two IDL interfaces are related through inheritance, some form of behavioral inheritance needs to be respected for CO classes that specify these interfaces [35]. We also want to analyze the cooperation between several CO instances, to check properties of a system of interacting objects. • Test generation: Another ongoing research is the ability to generate test suites from the Cooperative Object class definition. The tool supporting our can generate a prototypes that are “almost functional” implementations or CORBA-IDL interfaces, in the sense that only behavioral requirements are dealt with. Other “quality of service” requirements, such as performance, persistence, replication or fault-tolerance, have to be taken care of in a fully functional implementation. The idea is that the CO class can serve as the formal specification of the class, and that programmers will implement the



 492



R. Bastide, O. Sy, P. Palanque



specification in some programming language, implementing the other qualityof service requirements. This implementation needs to be tested for conformance against the original CO-based specification and the CO specification can be used to generate a test suite for the implementation.



Acknowledgements The work presented here is funded by CNET, the National Research Center for the French telecommunications agency (France Telecom) under grant number 98 1B 059. The final goal of the project is to provide a fully integrated CASE tool supporting our approach of behavioral specification of distributed object systems using high-level Petri nets.



References 1. Agha, Gul, and De Cindio, Fiorella. "Workshop on Object-Oriented Programming and Models of Concurrency." 16th International Conference on Applications and Theory of Petri Nets, ATPN’95, Torino, Italy, June 26-30, 1995. Gul Agha, and Fiorella De Cindio, organizers. (1995) 2. Agha, Gul, De Cindio, Fiorella, and Yonezawa, Akinori. "2nd International Workshop on Object-Oriented Programming and Models of Concurrency." 17th International Conference on Applications and Theory of Petri Nets, ATPN’96, Osaka, Japan, June 24, 1996. Gul Agha, Fiorella De Cindio, and Akinori Yonezawa, editors. (1996) 3. Bastide, Rémi. "Objets Coopératifs : Un Formalisme Pour La Modélisation Des Systèmes Concurrents." Ph.D. thesis, Université Toulouse III (1992). 4. Bastide, Rémi, and Palanque, Philippe. "Cooperative Objects: a Concurrent, Petri-Net Based Object-Oriented Language." Systems Engineering in the Service of Humans, IEEE-SMC’93, Le Touquet, France, October 15-20, 1993. IEEE Press (1993) 5. Bastide, Rémi, and Palanque, Philippe. "A Petri-Net Based Environment for the Design of Event-Driven Interfaces." 16th International Conference on Applications and Theory of Petri Nets, ATPN’95, Torino, Italy, June 1995 . Giorgio De Michelis, and Michel Diaz, Volume editors. Lecture Notes in Computer Science, no. 935. Springer (1995) 66-83. 6. Bastide, Rémi, and Palanque, Philippe. "Modeling a Groupware Editing Tool With Cooperative Objects." Concurrent Object-Oriented Programming and Petri Nets. Gul A. Agha, and Fiorella De Cindio, editors. Wien: Springer-Verlag (1998) 7. Bastide, Rémi, Palanque, Philippe, Sy, Ousmane, Le, Duc-Hoa, and Navarre, David. "PetriNet Based Behavioural Specification of CORBA Systems." 20th International Conference on Applications and Theory of Petri Nets, ATPN’99, Williamsburg, VA, USA, June 21-25, 1999. (1999)



 Formal Specification and Prototyping of CORBA Systems



493



8. Bryan, Doug. "Exactness and Clarity in a Component-Based Specification Language." Object-Oriented Behavioral Specifications. Haim Kilov, and William Harvey, editors. NewYork: Kluwer Academic Publishers (1996) 1-15. 9. Bryant, Antony, and Evans, Andy. "A Formal Basis for Specifying Object Behaviour." Object-Oriented Behavioral Specifications. Haim Kilov, and William Harvey, editors. NewYork: Kluwer Academic Publishers (1996) 17-30. 10. Genrich, H. J., and Lautenbach, K. "System Modelling With High-Level Petri Nets." Theoretical Computer Science. Vol. 13. North-Holland (1981) 109-36. 11. Goguen, J. A., Thatcher, J. W., and Wagner, E. G. "Current Trends in Programming Methodology." An Initial Algebra Approach to the Specification, Correctness and Implementation of Abstract Data Types.Prentice-Hall (1978) 80-149. 12. Guttag, John V., James J. Horning, S. J. Garland, A. Jones, and J. M. Wing. Larch: Languages and Tools for Formal Specification Springer-Verlag, New-York (1993). 13. Harel, David, and Gery, Eran. "Executable Object Modeling With Statecharts." IEEE Computer 30, no. 7 (1997) 31-42. 14. Jensen, Kurt. Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. 2nd edition ed., Vol. 2 Springer-Verlag (1996). 15. Kilov, Haïm, and William Harvey, editors. Object-Oriented Behavioral Specifications Kluwer Academic Publishers (1996). 16. Lakos, Charles. "A General Systematic Approach to Arc Extensions for Coloured Petri Nets." 15th International Conference on Applications and Theory of Petri Nets, ATPN’94, June 1995. Lecture Notes in Computer Science, no. 815. Springer (1995) 338-57. 17. Lakos, Charles, and Keen, C. D. "LOOPN++: a New Language for Object-Oriented Petri Nets." European Simulation Multiconference, Barcelona, Spain, June 1994. (1994) 18. Leavens, Gary T., and Yoonsik Cheon. Extending CORBA IDL to Specify Behavior With LARCH, TR #93-20. Iowa State University, Department of Computer Science, 1995. 19. Merle, Philippe, Gransart, Christophe, Geib, Jean-Marc, and Laukien, Marc. "The CorbaScript Language." ORBOS OMG Meeting on Scripting Languages, Helsinki, Finland, July 27-31 1998. (1998) 20. Meyer, Bertrand. "Systematic Concurrent Object-Oriented Programming." Communications of the ACM 36, no. 9 (1993) 56-80. 21. Netscape Communications Inc. CORBA Component Scripting OMG TC Revised Joint Submission. Orbos/98-07-02, Framingham, MA (1998). 22. Object Management Group. The Common Object Request Broker: Architecture and Specification. CORBA IIOP 2.2 /98-02-01, Framingham, MA (1998). 23. ———. Common Object Services Specification /98-07-05, Framingham, MA (1998). 24. Peterson, James Lyle. Petri Net Theory and the Modeling of Systems Prentice-Hall (1981). 25. Prinz, Andreas. "Describing Behaviour in Interfaces." Formal Methods for Open ObjectBased Distributed Systems. Elie Najm, and Jean Bernard Stefani, editors. Chapman & Hall (1997) 36-43.



 494



R. Bastide, O. Sy, P. Palanque



26. Puntigam, F. "Types for Active Objects Based on Trace Semantics." Formal Methods for Open Object-Based Distributed Systems. Elie Najm, and Jean Bernard Stefani, editors. Chapman & Hall (1997) 4-19. 27. Ramamoorthy, C. V., and Ho, G. S. "Performance Evaluation of Asynchronous Concurrent Systems." IEEE Transactions of Software Enginnering 6, no. 5 (1980) 440-449. 28. Rational Software Corporation. UML Notation Guide. 1.1 ed.1997. 29. ———. UML Semantics. 1.1 ed.1997. 30. Sankar, Sriram. "Introducing Formal Methods to Software Engineers Through OMG's CORBA Environment and Interface Definition Language." Algebraic Methodology and Software Technology, 5th International Conference, AMAST ’96, Munich, Germany, July 15, 1996. Martin Wirsing, and Maurice Nivat, Editors. ed. Lecture Notes In Computer Science, no. 1101. Springer (1996) 52-61. 31. Sibertin-Blanc, Christophe. "Cooperative Nets." 15th International Conference on Applications and Theory of Petri Nets, ATPN’94, June 1995. Lecture Notes in Computer Science, no. 815. Springer (1995) 471-90. 32. Siegel, Jon. "OMG Overview: CORBA and the OMA in Enterprise Computing." Communications of the ACM 41, no. 10 (1998) 37-43. 33. Sivaprasad, Gowri Sankar. Larch/CORBA: Specifying the Behavior of CORBA-IDL Interfaces, TR #95-27a. Iowa State University, Department of Computer Science, 1995. 34. Valk, Rüdiger. "Petri Nets As Token Objects: an Introduction to Elementary Object Nets." 19th International Conference on Applications and Theory of Petri Nets, ATPN’98, Lissabon, Portugal, June 1998. Springer (1998) 35. van der Aalst, W. M. P., and Basten, T. "Life-Cycle Inheritance, a Petri-Net Based Approach." 18th International Conference on Applications and Theory of Petri Nets, ATPN’97, Toulouse, France, June 1997. Pierre Azéma, and Gianfranco Balbo, editors. Lecture Notes in Computer Science, no. 1248. Springer (1997) 62-81.



 A Process Algebraic Specification of the New Asynchronous CORBA Messaging Service? Mauro Gaspari and Gianluigi Zavattaro Department of Computer Science, University of Bologna Mura Anteo Zamboni 7, 40127 Bologna, Italy {gaspari,zavattar}@cs.unibo.it



Abstract. CORBA (The Common Object Request Broker Architecture) has to continually evolve in order to cope with the changes of requirement of applications which become larger and more distributed. For this reason new features are being added to the CORBA specification, for instance the last proposal for a revised CORBA Messaging Service includes two new asynchronous models of request invocation. Since these new features will be added in the next CORBA implementations a relevant issue is to study their operational behaviour from different perspectives in order to facilitate the task of implementors. This paper addresses this issue providing an analysis of the CORBA Messaging Service which includes the new asynchronous features. In particular we illustrate how CORBA models for request invocation can be mapped into a message passing architecture based on the actor model. For this purpose we exploit an algebra of actors which supports some of the main features of the abstract Object Model of the Object Management Group, such as object identity and an explicit notion of state. This approach allows us to discuss and compare different models of request invocation in a standard process algebraic perspective for instance we show how different notions of equivalence, such as standard and asynchronous bisimulation, can be adapted to reason about CORBA.



1



Introduction



CORBA (The Common Object Request Broker Architecture) is the objectoriented standard for integrating applications running in heterogeneous distributed environments developed by the Object Management Group (OMG). One of the main limitations in the CORBA specification concerning the ability to cope with large scale distributed systems has been the lack of support for asynchronous models of request invocation. This hole has been recognized by OMG in the Messaging Service RFP [13] and in the next version of CORBA [32] new features will be provided in order to overcome this limitation. The proposal for a revised CORBA messaging service was submitted one year ago by a group of companies which are members of the OMG consortium [14]. This new proposal ?



This paper has been partially supported by the Italian Ministry of Universities (MURST).



Rachid Guerraoui (Ed.): ECOOP’99, LNCS 1628, pp. 495–518, 1999. c Springer-Verlag Berlin Heidelberg 1999 



 496



M. Gaspari, G. Zavattaro



extends the synchronous models of request invocation which were supported in CORBA 2.2 [16] with two new asynchronous models: callback and polling. Since these new features will be added in the next CORBA implementations a relevant issue is to study their operational behaviour from different perspectives in order to facilitate the task of implementors. This paper addresses this issue providing an analysis of the CORBA Messaging Service which includes the new asynchronous features. In particular we illustrate how CORBA models for request invocation can be mapped into a message passing architecture based on the actor model. For this purpose we exploit an algebra of actors [10,11,9] which supports some of the main features of the abstract Object Model of the Object Management Group, such as object identity and an explicit notion of state. This approach allows us to discuss and compare different models of request invocation in a standard process algebraic perspective where a nice, easy-tounderstand specification style is supported. Thus we can reuse standard results of the theory of concurrency for reasoning on CORBA models of request invocation. For instance we show how different notions of equivalence, such as standard and asynchronous bisimulation, can be adapted to reason about CORBA. The paper is organized as follows. Section 2 briefly describes the CORBA messaging facilities and the underlying object model. In Section 3 we introduce our algebra of actors. In Section 4 we specify the CORBA models for request invocation in the algebra of actors and we introduce a framework for reasoning on CORBA requests. In Section 5 we illustrate our approach for reasoning on a simple CORBA program. We conclude the paper by discussing related works and drawing conclusions.



2



The New CORBA Messaging Service



CORBA has been designed to support the integration of a wide variety of object systems providing solutions to the many technical problems that arise in this context. For this reason the CORBA architecture is quite complex and includes several components to deal with open systems and interoperability, for instance, the Interface Definition Language (IDL), the Dynamic Invocation Interface (DII), and, the Object Adapters [32]. CORBA clients can make requests exploiting an OMG IDL typed stub (a procedure which executes a single operation - the request - depending on the interface of the target object) or the dynamic invocation interface (an interface which is independent from the target object interface). Requests are sent through the Objects Request Broker (ORB) which is responsible for all of the mechanisms needed for transmitting them to the right destination. In particular the Object Adapter mediates between CORBA objects and the programming language used for the server implementation. Although the CORBA architecture deals with all the interoperability issues presented above, a client exploits an interface which is completely independent concerning these details. Clients making their requests have only to consider the address of the server, the interface of the server (the operation supported by the



 A Process Algebraic Specification of CORBA



497



server object) and the selection of an adequate protocol for request invocation. Moreover the semantics of the dynamic or the stub interface for invoking a request is the same and the server receiving a message cannot tell how the request was invoked. All these considerations suggest that a more abstract model can be used for reasoning on CORBA messaging facilities where all the low level aspects are hidden. This is the role of the CORBA concrete object model [16] based on the abstract OMG object model [12]. The abstract OMG object model defines basic concepts such as objects, operations, types and interfaces and it is common to all the OMG technologies. The CORBA concrete object model is summarized below.



2.1



The CORBA Object Model



The concrete object model of CORBA [16] distinguishes between clients (requestors of services) and servers (providers of services). In the following we adopt this concrete model for reasoning on messaging facilities of CORBA with the main restriction of considering an untyped world. This implies that we will not deal with subtyping and inheritance issues but we will only concentrate on dynamic issues concerning the execution of requests. We summarize here some of the main aspects of this model considering an untyped scenario where we also abstract away from the concepts of exceptions and request context. The reader interested in complete specification of the CORBA concrete object model can refer to [12]. – Each object has an identifier (its name) that provides a means to refer to the object and it is used for dispatching requests. The name (identity) is immutable and persists as long as the object exists. – Clients (the requestors of services) are conceptually distinguished from servers (the providers of services). – Server objects have a local memory and a behaviour that defines the meaningful operations. They are encapsulated entities accessible through a set of operations: the object interface. – Clients send requests to server objects. – Requests include an operation, a target object, a request identifier and zero or more parameters. One possible outcome for a request is returning to the client the result. – When a client issues a request a method of the target object is called. A method specifies how a server executes the requested service. The input parameters are those of the request and the result is sent back to the requestor. The execution of a method may change the state of a server. – From a client’s point of view objects can only be created and destroyed as an outcome of issuing requests.



 498



2.2



M. Gaspari, G. Zavattaro



CORBA Models of Request Invocation



According to the new proposal for the CORBA Messaging Service, clients perform requests exploiting synchronous or asynchronous operations. CORBA requests are objects that include all the information that should be transmitted to the server. In the CORBA DII requests must be created explicitly before being transmitted to the server object. In the following we do not consider all the details concerning the creation of new requests and we provide an abstract representation of them. We represent requests as records and we extract some of the most significant parameters, making them directly available in the operation. Usually a request contains additional flags specifying different semantics for the associated operation. For instance a flag specifies if an operation is blocking or not blocking. For the limited scope of this paper we will not consider all the possible combinations of requests and flags and we will restrict our study to the operational behaviour described below. We will use a notation based on the Dynamic Invocation Interface which is more adequate for our operational purposes. Models of Request Invocation of CORBA 2.2 The models of request invocation of the current version of CORBA are: – Synchronous: INVOKE(Server,Request,Result) A client performing this request waits until the server sends the answer. The result is placed in the Result argument. This is similar to a remote procedure call. – Oneway: ONEWAY(Server,Request) This invocation returns the control to the caller object, the request is transmitted and there is no response. – Deferred Synchronous: SEND(Server,Request) This invocation transmits the request to the server and returns the control to the caller object without waiting for the operation to finish. To get the result the calling object can perform the get response operation having the same request identifier as an argument. GET RESPONSE(Server,Request,Result) this operation gets the first answer of the request, if it is ready otherwise it blocks waiting for the result. The result is placed in the Result argument. CORBA also includes a GET NEXT RESPONSE primitive to retrieve other possible results; this feature will not be modelled in this paper. New Asynchronous Models of Request Invocation The proposal for a new CORBA messaging facility extends CORBA 2.2 with two new asynchronous models of request invocation. – Callback SENDC(Server,Request,Callback) When a client invokes this operation it sends the request to a server object and it creates a reply handler object. The answer will be processed by this object and Callback represents its behaviour.



 A Process Algebraic Specification of CORBA



499



– Polling SENDP(Server,Request,Poller) When a client invokes this operation the address of a local poller object is returned in Poller. This object will be used to retrieve the answer exploiting the POLL GET RESPONSE operation. A poller object is also able to execute an IS READY operation which returns true if and only if the answer is available in the poller object. 2.3



A Process Algebraic Framework for CORBA



We provide a formal framework for all the above models of request invocation following a process algebraic approach. Process algebras, like CCS [22] and CSP [18], have been developed as formalisms for the study of concurrent systems. Initially, process algebras allowed interprocess communication via a static structure of channels between processes. Mobility, one of the basic features of modern object oriented systems (where new objects can be created at run time and/or moved in different locations), was not easily representable in these formalisms. Note that the CORBA callback and polling models of request invocation need a more dynamic structure of channels. The π-calculus [25] can be considered as the main attempt in order to overcome these limitations. In fact, it has been introduced as a calculus for mobile processes, i.e., processes with a dynamically changing linkage structure. The π–calculus has been developed taking into account a synchronous handshake communication mechanism between processes. More recently, in [19,7] also an asynchronous fragment of the π–calculus has been studied in order to analyze also the asynchronous communication mechanism and its similarities/differences with the synchronous one [27]. There have been several attempts to adopt the π-calculus and its asynchronous version, for modelling interaction in the context of concurrent object oriented programming languages [23,33,28], but these approaches do not provide the concepts of state of a process or of object identity as a first class entities. On the other hand, the actor model [17,2] directly deals with many features of the OMG Core Object Model such as object identity, state and operations associated to objects that characterize their behaviour; an actor has the same structural and interaction properties as a CORBA object if we restrict to an untyped world. For this reason we exploit a new formalism for our modelling purposes, an algebra of actors [11,10,9], which has been designed as a compromise between the standard process algebras, such as the π-calculus [24], and the actor model. This process algebra supports an high level specification style which allows the user to describe how CORBA models of request invocation can be mapped into sequences of message-passing primitives. 2.4



The Actor Model



The actor model was introduced by Carl Hewitt about 20 years ago [17]. Actors are self-contained agents with a state and a behaviour which is a function of



 500



M. Gaspari, G. Zavattaro



incoming communications. Each actor has a unique name (mail address) determined at the time of its creation. This name is used to specify the recipient of a message supporting object identity [20], a property of an object which distinguishes this object from all the others. Object identity is a typical feature of object-oriented programming languages and it is used as a basic dispatching mechanism in message passing. This property is not easily embeddable in formalisms such as CCS [22] (or asynchronous π-calculus [19,7]), where message dispatching is performed by means of channels. In these formalisms the association address-process is not unique: a process may have several ports (channels) from which it receives messages and the same channel can be accessed by different processes. Actors communicate by asynchronous and reliable message passing, i.e., whenever a message is sent it must eventually be received by the target actor. Actors exploit an implicit receive mechanism. A receive operation is explicit when it appears in programs, while it is implicit when it does not correspond to an operation in the programming language and it is performed implicitly at certain points of the computation. An implicit receive mechanism is common in object-oriented programming where objects can be seen as passive entities which react to messages or to method invocation. Actors make use of three basic primitives which are asynchronous and nonblocking: create, to create new actors; send, to send messages to other actors; and become, to change the behaviour of an actor [2].



3



An Algebra of Actors



Let A be a countable set of actor names: a, b, c, ai , bi ,. . . will range over A and L, L0 , L00 ,. . . will range over its (finite) power set Pfin (A) (i.e., L, L0 , L00 ⊆fin A). Let V be a set of values (with A ⊂ V) containing, e.g., true, false, and let X , ranged over by x , y, z ,. . ., be a set of value variables that are bound to values at run-time. We assume value expressions e built from actor names, value constants, value variables, the expressions self , state, and message, and any operator symbol we wish. In the examples we will use standard operators on sequences: 1st , 2nd, rest , empty. We will denote values by v, v 0 , v 00 ,. . . when they appear as contents of a message and with s, s 0 , s 00 ,. . . when they represent the state of an actor. [[e]]as gives the value of e in V assuming that a and s are substituted for self and state inside e; e.g. [[self ]]as = a and [[state]]as = s. The special expression message represents the contents of the last received message. Whenever a message is received, its contents is substituted for each occurrence of the expression message in the receiving actor. Let C be a set of actor behaviours identifiers: C , C 0 , . . . will range over C. We suppose that every identifier C is equipped with a corresponding behaviour def definition C = P where P is a program, that is a term defined by the following abstract syntax: P :: = become(C , e).P | send(e1 , e2 ).P | create(b, C , e).P | √ e1 :P1 + . . . + en :Pn |



 A Process Algebraic Specification of CORBA



501



Observe that we allow recursive behaviours to be defined, for example we could √ def have C = become(C , state). . Actor terms are defined by the following abstract syntax: A :: = a Cs | a [P]s | ha, vi | A|A | A\a | 0 An actor can be idle or active. An idle actor a Cs (composed by a behaviour C, a name a, and a state s) is ready to receive a message. When a message is received the actor becomes active. Active actors are denoted by a [P]s where P is the program that is executed. The actor a will not receive new messages until it becomes idle (by performing a become primitive). Sometimes the state s is omitted when empty (i.e. s = ∅). A program P is a sequence of actor primitives (become, send and create) and guarded choices e1 :P1 +. . .+en :Pn √ terminating in the null program (which is usually omitted). An actor term is the parallel composition of (active and idle) actors and messages. A message is denoted by a term ha, vi where v is the contents and a the name of the actor the message is sent to. Also a restriction operator A\a is used in order to allow the definition of local actor names (A\L is used as a shorthand for A\a1 \ . . . \an if L = {a1 , . . . , an }) while 0 is the usual empty term. The actor primitives and the guarded choice are described below. – send: The program send(e1 , e2).P sends a message with contents e2 to the actor indicated by e1 : a



τ



[send(e1, e2 ).P]s −→



a



[P]s | h[[e1 ]]as , [[e2]]asi



where τ represents an internal invisible step of computation. – become: The program become(C, e).P0 changes the state of the actual actor from active to idle: a



τ



[become(C, e).P0]s −→ (d [P0 {a/self }]s)\d | a C[[e]]as



with d fresh



The primitive become is the only one that permits to change the state according to the expression e; we sometimes omit e if the state is left unchanged (i.e. e = state). The continuation P0 is executed by the new actor d [P0 {a/self }]s. This actor will never receive other messages (i.e. it is unreachable) as its name d cannot be known to any other actor. Indeed, the expression self , which is the only one that returns the value d, is changed in order to refer to the name a of the initial actor. – create: The program create(b, C, e).P0 creates a new idle actor having state s and behaviour C:



 502



M. Gaspari, G. Zavattaro a



τ



[create(b, C, e).P0]s −→ (a [P0 {d/b}]s | d C[[e]]as )\d



with d fresh



The new actor receives a fresh name d. This new name is initially known only to the creating actor, in fact a restriction on the new name d is introduced. – e1 :P1 + . . . + en :Pn: In the agent e1 :P1 + . . . + en :Pn, the expressions ei are supposed to be boolean expressions with value true or false. The branch Pi can be chosen only if the value of the corresponding expression ei is true: a



τ



[e1 :P1 + . . . + en:Pn]s −→



a



[Pi ]s



if [[ei ]]as = true



The function n returns the set of the actor names appearing in an expression, a program, or an actor term. Given the actor term A, the set n(A) is partitioned in fn(A) (the free names in A) and bn(A) (the bound names in A) where the bound names are defined as those names a appearing in A only under the scope of some restriction on a. We use act(A) to denote the set of the names of the actors in A. An actor term is well formed if and only if it does not contain two distinct actors with the same name. In the following we will consider only well formed agents, and we will use Γ to denote the set of well formed terms (A, B, D, E, F,. . . will range only over Γ ). We model the operational semantics of our language following the approach of Milner [23] which consists in separating the laws which govern the static relation among actors (for instance A|B is equivalent to B|A) from the laws which rules their interaction. This is achieved by defining a static structural equivalence relation over syntactic terms and a dynamic relation by means of a labelled transition system [29]. Definition 1. - Structural congruence, is the smallest congruence relation over actor terms (≡) satisfying: √ (v) 0\a ≡ 0 (i) a [ ]s ≡ 0 (ii) A|0 ≡ A (vi) (A\a)\b ≡ (A\b)\a (iii) A|B ≡ B|A (vii) (A|B)\a ≡ A|(B\a) where a 6∈ fn(A) (iv) (A|B)|D ≡ A|(B|D) (viii) A\a ≡ A{b/a}\b where b is fresh Definition 2. - Computations. A transition system modelling computations α in the actor algebra is represented by the triple (Γ, T , {→ | α ∈ T }). T = {τ } ∪ {av, avL | a ∈ A, v ∈ V, L ⊆fin A} is a set of labels, where τ is the invisible action standing for internal autonomous steps of computation; av and avL respectively represent the receiving and the emission of the message with receiver a and contents v. The set L in the label av L represents the set of actor names α in the expression v which were initially under the scope of some restriction. → is the minimal transition relation satisfying the axioms and rules presented in Table 1.



 A Process Algebraic Specification of CORBA



503



Table 1. Operational semantics. a



Send



τ



[send (e1, e2 ).P ]s −→



Create



av∅



a a



τ



[become(C , e).P 0]s −→ (d [P 0 {a/self }]s )\d | a C[[e]]as d fresh τ



[create(b, C , e).P 0]s −→ (a [P 0 {d /b}]s | d C[[e]]as )\d a



Receive Guard



[P ]s | h[[e1]]as , [[e2]]as i



ha, v i −→ 0



Deliver Become



a



a



av



Cs −→



a



[P {v /message}]s τ



[e1:P1 + . . . + en :Pn ]s −→



a



[Pi ]s



d fresh def



if C = P if [[ei ]]as = true



α



A −→ A0



Res



α



A\a −→ A0\a A −→ A0



a 6∈ n(α)



avL



Open



A\b



avL∪{b}



−→



A0



α



A −→ A0



Par



α



A|B −→ A |B A −→ A0



Cong



if α = avL then a 6∈ act (B ) ∧ L ∩ fn(B ) = ∅



B −→ B 0



av



Sync



0



a 6= b ∧ b ∈ n(v )



av L



τ



A|B −→ (A0 |B 0) \ L B≡A



α



A −→ A0 α



B −→ B



A0 ≡ B 0 0



The rules Send, Become, Create and Guard have been already discussed. Rule Deliver states that the term ha, vi (representing a message v sent to the actor a) is able to deliver its contents to the receiver by performing the action av ∅. The corresponding receiving action labelled with av can be performed by the actor a when it is idle (rule Receive). Note here the use of the expression message which is replaced by the content of the incoming message v in the program P. The other rules are simply adaptation to our calculus of the standard laws for the π–calculus. The most interesting difference is due to the fact that in our calculus, more than one restriction can be extended by one single delivering operation. In fact, in our case the contents of a message is an expression instead of a unique name. This is the reason why we have added the set L to the label av L. Another difference is in the rule Par : the actor term A|B can deliver a message inferred by A (i.e., execute an emission action avL), only if B does not contain the target actor (see side condition a 6∈ act (B)). The fact that an output label can be performed by an agent only if it does not contain the target actor introduces in our calculus an interesting strong form of



 504



M. Gaspari, G. Zavattaro



unique receptiveness property. Indeed, the operational semantics not only forces that a message can be consumed uniquely by its receptor, but also ensures that external actors are neither able to observe the presence of a pending message sent to another actor. We will show in the remainder of the paper nice features of our calculus related to this property. 3.1



Equivalence of Actor Terms



As already stated, one of the advantages of having introduced a semantics for actors based on a labelled transition system is that standard observational semantics for process algebras can be used. In this section we investigate two of them based on the notion of bisimulation: the weak bisimulation [22] (only bisimulation in the following) and the asynchronous weak bisimulation [19,5] (only asynchronous bisimulation in the following) which is the corresponding equivalence for languages based on asynchronous communication. In order to define equivalences which do not take into account the τ steps, we recall the notion of weak transition which allows to contract successive τ -steps: τ



τ



P =⇒ P 0 iff P(−→)? P 0 α τ α τ P =⇒ P 0 iff exists P 00 and P 000 s.t. P =⇒ P 00 −→ P 000 =⇒ P 0 (for α 6= τ ) τ



Observe that given P =⇒ P 0 P 0 can be simply P if no τ transition is performed. Definition 3. - Bisimulation. A symmetric relation R on actor terms (R ⊆ Γ × Γ ) is a bisimulation if (A, B) ∈ R implies: α



α



– if A −→ A0 then there exists B 0 such that B =⇒ B 0 and (A0 , B 0 ) ∈ R. Two actors A and B are bisimilar, written A ≈ B, if there exists a bisimulation R such that (A, B) ∈ R. Observe that we are dealing with the standard weak bisimulation in which a τ step can be simulated by simply making no action. This kind of bisimulation is not a congruence in the presence of a general choice composition operator; in our case, the unique composition operators for actor terms are the parallel A|A0 and the restriction A \ a operators, and it is not difficult to see that the bisimulation equivalence we have defined is a congruence w.r.t. these operators (i.e., if A ≈ B then for every actor term D and actor name a, A|D ≈ B|D and A \ a ≈ B \ a). Example 1. Consider the actor term A = a Double which receives messages represented as pairs (b, v) where the first argument is an actor name and the second argument is an integer, and sends to the actor b the integer 2 ∗ v. This behaviour is defined formally below: def



Double = send(1st (message), 2 ∗ 2nd(message)).become(Double) Suppose now that we want to build an interface that receives messages and



 A Process Algebraic Specification of CORBA



505



forward them to an actor which duplicates them. This job is performed by the actor term: B=



a



Forward | b Double



where the behaviour Forward is: def



Forward = send(b, message).become(Forward) The actor terms A and B are not bisimilar because the term B has two addresses that can be reached from the outside (the action bv cannot be observed in the term A). In order to make the actor b Double unreachable from the outside, we can think to introduce the following restriction on the actor name b: B 0 = (a Forward | b Double)\b As the action bv is no more observable, we have that B 0 ≈ A. In order to prove this equivalence, it is enough to see that the forward operation is composed of only unobservable τ labelled steps. For languages based on asynchronous communication a new notion of asynchronous bisimulation has been introduced in [19] and formally analyzed in [5]. The basic difference between the asynchronous bisimulation and the standard (synchronous) one, is that in the asynchronous case, the action of removing a message and immediately reintroducing it, is considered as unobservable. This difference reflects the idea that an observer cannot synchronise with the observed system but can only send messages and look at what may come out of it. Definition 4. - Asynchronous bisimulation. A symmetric relation R on actor terms (R ⊆ Γ ×Γ ) is an asynchronous bisimulation if (A, B) ∈ R implies: α



α



– if A −→ A0 where α 6= av then there exists B 0 such that B =⇒ B 0 and (A0 , B 0 ) ∈ R. av av – if A −→ A0 then there exists B 0 such that B =⇒ B 0 and (A0 , B 0 ) ∈ R or τ 0 0 0 B =⇒ B and (A , B |ha, vi) ∈ R. Two actors A and B are asynchronous bisimilar, written A ≈a B, if there exists an asynchronous bisimulation R such that (A, B) ∈ R. As for the standard bisimulation, it is not difficult to prove that also the asynchronous bisimulation is a congruence. It is clear from the definition that the asynchronous bisimulation is coarser with respect to the standard bisimulation, i.e., if A ≈ B then also A ≈a B. For example, the equivalences described in the example 1 hold also if we take into account ≈a instead of ≈. The following example shows the need to move to the asynchronous bisimulation in order to formally analyze interesting aspects of the actor model. Example 2. We consider two actors implementing two different communication medias: a queue and an ether, i.e., an unordered set (mailbox) of messages [22]. The behaviours of the two actors are defined as follows:



 506



M. Gaspari, G. Zavattaro def



QUEUE = (1st (message) = get ∧ empty(state)):



send(self , message). become(QUEUE )+ (1st (message) = get ∧ ¬empty(state)): become(QUEUE , rest (state)). send(2nd(message), 1st (state))+ (1st (message) = put ): become(QUEUE , insert last (2nd(message), state)) def



ETHER = (1st (message) = get ∧ empty(state)):



send(self , message). become(ETHER)+ (1st (message) = get ∧ ¬empty(state)): become(ETHER, rest (state)). send(2nd(message), 1st (state))+ (1st (message) = put ): become(ETHER, insert rand(2nd(message), state))



The two actor programs are assumed to receive messages with the following structure: (put , item) or (get , sender ). The two programs differ only for the functions insert last and insert rand, the first inserts a message at the end of a sequence and the second in a random position. The property of arrival-order non-determinism in message delivery holding in the actor model, suggests that there is no way to distinguish between the behaviour of the ETHER and the QUEUE . Indeed, an external observer has no way to force a particular order of reception of the data to introduce in the buffer, so we can always consider that data are received by the QUEUE in the same order as they are stored in the ETHER. Formally, we have that this equivalence is not captured by the standard bisimulation as it requires that each input operation should be matched exactly by an equivalent input operation, that is, the ETHER and the QUEUE are forced to consume data in the same order. In order to capture the above equivalence we need to move to the asynchronous bisimulation; indeed, it is not difficult to prove that b ETHER ≈a b QUEUE for any actor name b. We do not report the complete proof for this equivalence, because standard, but we only point out some interesting related aspects. When we exploit the asynchronous bisimulation we can assume that an input operation consuming a message with contents (put , d) performed by b ETHER could be matched by b QUEUE by performing no action, provided that the agent b QUEUE |hb, (put , d)i is equivalent to the term reached by the actor b ETHER. In order to prove this, we observe that b ETHER{d } ≈a b QUEUE|hb, (put , d)i. It is interesting to observe that this equivalence holds due to the previously described unique repectiveness property, indicating that no external actor can observe the presence of the pending message hb, (put , d)i. Example 3. The actor model does not provide an explicit primitive for receiving only data having a certain structure or a certain contents. In fact an actor



 A Process Algebraic Specification of CORBA



507



can read a message only when it is idle and each available message can be read independently from its sender or its contents. On the other hand, in real applications it is often necessary to specify the kind of data that are needed to be received in a particular point of the computation. In this example we use the asynchronous bisimulation to prove the correctness of the implementation of a new command that explicitly permits to receive only messages containing a particular identifier. As we want to have more information than the identifier inside the contents of the message, we consider that the messages are records with a field id, containing the identifier, and possibly other fields that we left unspecified. In general we denote a record r by (f1 :e1 , . . . , fn :en ) and the selection of the value in the field fi is written as r .fi . We consider a new primitive receive(e, x ) which forces to receive only a message with the value e in the field id. Formally, we extend the syntax of the language by allowing also programs of the following kind: P :: = receive(e, x ).P having the following operational semantics: a



av



[receive(e, x ).P]s −→ a [P{v/x }]s



if v.id = [[e]]as



We present an implementation of the new primitive in the initial algebra which preserves the asynchronous bisimulation semantics; in other words, we prove that for every actor containing such a new primitive, there exists an equivalent term which does not contain any receive commands. Our idea for implementing the program receive(e, x ).P by a term of the algebra denoted by [[receive(e, x ).P]] is to define a behaviour which executes the program P only if the message has the desired id; otherwise it resends the received message and becomes idle waiting for another one: def



[[receive(e, x ).P]] = become(REC , state) where: def



REC = (message.id = e): P{message/x } + (message.id 6= e): send(self , message). become(REC , state) The correctness of our mapping is proven by the fact that the equivalence a [receive(e, x ).P]s ≈a a [[[receive(e, x ).P]]]s holds for every a and s. On the other hand, the standard (synchronous) bisimulation is not preserved. This is because the implementation uses the technique of immediately reintroducing the received messages (when the sender is different from e) that, as stated above, is observed by the standard bisimulation and not by the asynchronous one. One feature of this implementation is that the encoding of a receive command could introduce a busy waiting; for example, if only messages without the desired id are received by the actor, the messages are repeatedly received and resent. Even if the encoding could introduce this divergent behaviour, asynchronous bisimulation is preserved because it is not divergence sensitive.



 508



4



M. Gaspari, G. Zavattaro



A Specification of the CORBA Messaging Service



The actor model and the algebra presented in the previous sections provide an abstract representation of the CORE OMG object model in an untyped scenario. The further extension to our algebra is to add the distinction between clients and servers objects and an adequate abstract syntax for the CORBA models of requests invocation. 4.1



CORBA Clients



CORBA clients are represented as actors performing sequences of requests. To this aim we extend the syntax for the behaviour of our actor algebra by introducing also: P :: = INVOKE (a, e, x ).P | ONEWAY (a, e).P | SEND(a, e).P | GET RESPONSE (a, e, x ).P | SENDC (a, e, P 0 ).P | SENDP(a, e, b).P | IS READY (b, e, x ).P | POLL GET RESPONSE (b, e, x ).P Several kinds of parameters are considered: a indicates the name of the actor representing the server the client is asking for the service, e is a record that describes the request, x is the value variable that will contain the results returned by the server, P 0 is the program that the callback object will perform after having received the result of the request in the case of SENDC , and b is the name of the poller object in the case of SENDP. According to this extended syntax an actor can perform the CORBA primitives specified above and the primitives of the actor algebra. We assume that a CORBA client can only perform CORBA primitives. 4.2



CORBA Servers



CORBA servers are represented as actors that reply to the client requests according to the specification of the provided services. As already stated, requests are described as records; we suppose that these records contain at least three fields: id that contains an identifier that uniquely characterizes the request, to that indicates the name of the object to which the server has to send the results of the request, and client which is filled with the name of the client asking for the service. It is interesting to note that the fileds to and client are not in general the same. For example, in the case of the asynchronous invocations SENDC and SENDP the client will ask to the server to send the results to the callback or to the poller object respectively and not to itself. We assume the existence of a function f (a, e) that, given a server a and a request e, returns the results that the server will compute. We suppose that f (a, e) is a record that contains the field id filled with the identifier of the current request. Usually servers are idle waiting for requests: whenever a request is delivered to a server, it deterministically computes the answer, sends the result to the correct destination and possibly modifies its state.



 A Process Algebraic Specification of CORBA



509



Idle servers are denoted by a Ss where a is the name of the server, S its behaviour, and s its state. The behaviour of a server can be defined formally as follows: τ



ha, ei | a Ss =⇒ hb, vi | A



iff b = e.to, v = f (a, e) and A =



a



Ss 0



where s 0 is the new state of the server which is a function of the previous state s and of the request e. In this way we provide a specification of CORBA servers which is independent from the model of request invocation used by clients. We also abstract from the server interface, and we assume that a server is able to execute a set of operations and that the name of the method and its arguments are transmitted in the request. 4.3



CORBA Models of Request Invocation



We present a characterization of the possible request invocations, giving the indication of how a client behaves in each possible case. – INVOKE. The program INVOKE (a, e, x ).P implements the synchronous model of request invocation of CORBA, basically it is a remote procedure call where a is the name of the server object, e is the request containing the operation and the arguments and x is the result that can be used in the rest of the program P. We implement this primitive by a term [[INVOKE (a, e, x ).P]] which is defined by exploiting the send and the receive operations of the actor algebra. When the answer (which is a record with the corresponding field id) is received, the program P can be executed. def



[[INVOKE (a, e, x ).P]] = send(a, e).receive(e.id, x ).P Here we suppose that e.to = self (i.e. the name of the client actor) in order to be sure that the results are sent back to the correct client. – ONEWAY. According to this model of request invocation the answer of the server will never be consumed by the client. We model this by creating a new empty actor to which the server will send the results of the request. √ def [[ONEWAY (a, e).P]] = create(b, ).send(a, e).P Here we suppose that e.to = b in order to ensure that the server will send to the new empty actor its results. In this way the produced results will be consumed by the new object that performs a sort of garbage collection. – SEND. This is the deferred synchronous model of request invocation. The request SEND(a, e) is transmitted to the server object through the ORB and then the client retrieves the answer exploiting GET RESPONSE (a, e, x ) which binds the variable x to the result of the request. def



[[SEND(a, e).P]] = send(a, e).P



 510



M. Gaspari, G. Zavattaro



Here we suppose that e.to = self . The answer will be consumed at the moment the client performs a GET RESPONSE ; in order to ask for the result of the correct request e, we use its unique identifier e.id as handler: def



[[GET RESPONSE (a, e, x ).P]] = receive(e.id, x ).P – SENDC. This is an asynchronous model of invocation: SENDC (a, e, P 0 ) creates a callback object that will manage the answer executing the program P 0 after having received the result of the request, and sends the request and the address of the callback object to the server object through the ORB. Finally it executes the rest of the program. def



[[SENDC (a, e, P 0 ).P]] = create(d, CALLBACKeP 0 ). send(a, e).P Here we suppose that e.to = d and that the behaviour CALLBACKeP 0 is defined as follows: def



CALLBACKeP 0 = (message.id = e.id): P 0 {message/answer } + (message.id 6= e.id): send(self , message). become(CALLBACKeP 0 , state) where answer is a special expression used inside the program P in order to denote the content of the message that the callback object will receive from the server. Note that in this case the to field of the request is set to the address of the callback object d. – SENDP. The polling model of request invocation creates a poller object that will be used by the client to retrieve the answers. def



[[SENDP(a, e, b).P]] = create(b, POLLERe , (empty, empty)).send(a, e).P Here we suppose e.to = b as in this case the server will have to send the response to the poller actor. The state of the poller actor is a pair, initialized to (empty, empty), that contains two kinds of information. The first is the name of the client actor that is introduced in the state of the poller whenever the client asks for the results that are not yet received by the poller object. The second element is used to store the results produced by the servers. The client has the possibility to interact with the poller object by means of two primitives that are compiled as follows: [[IS READY (b, e, x ).P]]



def



= send(b, is ready). receive(e.id, x ).P



def



[[POLL GET RESPONSE (b, e, x ).P]] = send(b, poll get response). receive(e.id, x ).P Finally, we can describe the behaviour of the poller as follows:



 A Process Algebraic Specification of CORBA



511



def



POLLERe = (message.id = e.id)and(1st (state) = empty): become(POLLERe , (empty, message)) + (message.id = e.id)and(1st (state) 6= empty): send(1st (state), message) + (message = is ready)and(2nd(state) = empty): send(e.client , false).become(POLLERe , state) + (message = is ready)and(2nd(state) 6= empty): send(e.client , true).become(POLLERe , state) + (message = poll get response)and(2nd(state) = empty): become(POLLERe , (e.client , empty)) + (message = poll get response)and(2nd(state) 6= empty): send(e.client , 2nd(state)) This is a static specification of the poller object. A poller object always sends answers to the original client, e.g., the client which sent the SENDP request. This feature can be used to prove properties of this model of request invocation, for instance the equivalence presented in the next section. A more dynamic specification of the poller object is also possible and it will be the subject of future work. 4.4



Some Properties



After having mapped the different kinds of request invocation to our algebra of actors, we can use the equivalences we have introduced in the previous section in order to prove formally some interesting, even if simple, properties. First of all we consider the standard synchronous INVOKE and the deferred synchronous SEND. The difference between these two requests is that INVOKE blocks a client until a result is received, while SEND does not block a client and the result will be received at the moment the corresponding GET RESPONSE operation is executed. The blocking behaviour of the INVOKE can be simply simulated also in the case of the deferred synchronous invocation by performing the GET RESPONSE primitive after the SEND primitive. This is formalized by the following equivalence: b



[INVOKE (a, e, x ).P]s ≈a b [SEND(a, e).GET RESPONSE (a, e, x ).P]s Also a stronger equivalence result holds: the two terms obtained by substituting each CORBA primitive according to the corresponding definition are syntactically equals. More interesting is to show that the synchronous INVOKE mechanism can be simulated also by using the asynchronous primitives SENDC and SENDP. In the case of SENDC , the idea is that the client blocks after having asked for the service, until the callback object forwards the results. To this aim we force



 512



M. Gaspari, G. Zavattaro



the callback object to perform the operation send(e.client , x ) where e.client is the name of the client and x is the variable that will be bound to the results produced by the server. This is formalized by the following equivalence: [INVOKE (a, e, x ).P]s | a Ss 0 ≈a b [SENDC (a, e, send(e.client , answer )).receive(e.id, x ).P]s | a Ss 0 b



In this case we have to take into account configurations composed of both the client and the server. In this way, the communication between them is not observable; indeed, if an external actor can observe the contents of the exchanged messages, it is easy to discriminate between the INVOKE and the SENDC mechanisms as the contents e of the two kinds of request are different (e.g. the contents of the field e.to). The above equivalence can be proven by recalling the equivalence in the Example 1, and observing that the CALLBACK object, which is dynamically created, behaves like the Forward actor defined in that example. Moreover, the CALLBACK object is not visible to the outside because the name of new created actors is local to the actor itself and the parent actor. A new feature with respect to the Example 1 is that in this case the restriction is on the name of the object performing the forward operation and not on the client name. Note also that the above equivalence does not hold exploiting the CORBA primitives only. We have to resort to the low level message passing operations of the actor algebra when we specify the behaviour of the callback object. A similar idea can be used in the case of the SENDP primitive where the command POLL GET RESPONSE can be used in order to retrieve the results via the poller object. This is formalized by the following equivalence: [INVOKE (a, e, x ).P]s | a Ss 0 ≈a b [SENDP(a, e, b).POLL GET REQUEST (b, e, x ).P]s | a Ss 0 b



In this case, the forward operation is performed by the POLLER object, which will receive a new restricted name at the moment the SENDP operation is executed.



5



A CORBA Programming Example



We illustrate our approach showing how a specification of a client behaviour can be extracted from a simple CORBA program. We assume to have defined a server which is able to compute the result of mathematical formulas. We also assume a display object which is able to show the answer to the user. We assume the following OMG IDL interfaces: interface Compute { string compute (in string formula); };



 A Process Algebraic Specification of CORBA



513



interface Display { void display (in string message); };



Here we suppose that formulas and results are represented as strings. We define an user interface client which takes a formula from the user, asks the server to compute it, waits for the answer and finally sends the answer to the display object. We illustrate our example exploiting the CORBA Scripting Language (CORBAScript) [8], an interpreted scripting language dedicated to CORBA environments. CORBAScript provides an high level interface to implement CORBA clients and tools, hiding some of the specific mechanisms of CORBA. For example in CORBAScript the access to an IDL interface is simply done by providing its IDL interface identifier as illustrated below. server = Compute("IOR:...."); display = Display("IOR:....."); answer = server.compute("Formula"); display.display(answer);



Here we suppose that Formula is the string representing the formula to compute. We use an IOR (Interoperability Object Reference) to access the CORBA objects. The IOR is a unique reference to a CORBA object and thus can be modelled as an actor name. The variables server and display are references to CORBA objects, and the operations display.display and server.compute are synchronous requests invocations (i.e., INVOKE ). This situation is modelled by the following client program in the algebra of actors where we assume that server and display are the names of actors implementing the two servers. def



UICLIENT1 = message = compute: INVOKE (server , Formula, x ). INVOKE (display, x , y). become(UICLIENT1 , state) + message = other : P A drawback of this kind of interaction between the client and the mathematical server, is that the client is blocked on the call INVOKE(server,Formula,x) waiting for the results. In this way, the user interface program is not able to accept the other input which activates the generic program P. This problem can be solved by using the new asynchronous request invocation mechanisms. We represent this alternative approach in the algebra of actors only, because CORBAScript does not yet support the asynchronous messaging facilities. def



UICLIENT2 = message = compute: SENDC (server , Formula, INVOKE (display, answer , y)). become(UICLIENT2 , state) + message = other : P



 514



M. Gaspari, G. Zavattaro



Here the client performs an asynchronous request and thus it does not block and it is able to deal with the other inputs activating the generic program P. The display request is performed by the callback object created at the time the SENDC primitive is executed. Now, it is interesting to compare formally the two above client descriptions. The result we have obtained is that the two different approaches are equivalent: b b



[UICLIENT1]s | [UICLIENT2]s |



server



≈a



server



Ss 0 |



display



Ds 00



Ss 0 |



display



Ds 00



where the actors server Ss 0 and display Ds 00 , representing the mathematical and the displaying servers respectively, are defined according to the indication reported in Section 4.2. This equivalence can be proven following the same lines described in Section 4.4. The most interesting aspect to observe is that the second client is able to start the execution of P even if the request has not been considered by the mathematical server yet. The execution of P is started whenever an other input is received from the client. In order to simulate the same behaviour, also the first client has to perform the same input action. This can happen only if the two server invocations have been completely executed. Even if this behaviour is different, it does not permit to distinguish between the two above agents; indeed, the two reached actors are equivalent: b



[P]s |



(b [P]s | c CALLBACKs 000



Ss 0 | display Ds 00 ≈a | hserver , request i) \ c | server



server



Ss 0 |



display



Ds 00



This equivalence holds because the CALLBACK object, the message containing the request for the server, as also the messages that will be exchanged among the servers and the CALLBACK object, are not observable to the outside. It is interesting to observe that in this case we have not followed the previous general way to implement the INVOKE primitive using the callback mechanism. Indeed, here the callback object is not a forwarder, but it is responsible for the execution of the displaying request. The approach used in this case is more efficient, because the client does not block waiting for the answer of the server forwarded by the callback object, but it directly delegates the execution of the continuation to the callback.



6



Related Work



Najm and Stefani [26] present a notion of computational model for open distributed processing which can also be exploited for modelling the new features of CORBA for instance the quality of service [14]. Since their model is based on



 A Process Algebraic Specification of CORBA



515



rewriting logic and they do not deal with the issue of modelling asynchronous requests, their work can be considered complementary to our work. An interesting point could be to analyse if their proposal for modelling quality of service can be successfully used in an asynchronous context. Bastide et al. [6] propose to extend the interface definition of CORBA distributed objects by a specification of their behaviour expressed exploiting high level petri nets. Although our goal was different, e.g., to provide a formal representation of CORBA clients which interact exploiting the new CORBA asynchronous messaging service, the algebra of actors could also be used to provide a formal account of CORBA services. In the past few years, several advances have been achieved on the semantics of actors, dealing with aspects of communication and concurrency [4,3,30,31,21], but these papers do not investigate the relationships of the actor model with traditional process algebras, even though recently Robin Milner [24] suggested that it may be worthwhile to work in this direction. We believe that our approach is complementary to previous approaches to the semantics of actors, providing a new framework to discuss concurrency related aspects in this context. The reader interested in a more detailed comparison with other calculi can refer to [11,10,9].



7



Conclusion



The main result presented in this paper is the development of a process algebraic specification of the new CORBA models for request invocation. The specification is based on an algebra of actors that enjoys a clean formal definition and a rich algebraic theory, inspired from the π-calculus, while preserving a basic object-oriented features such as object identity, asynchronous message passing, an implicit receive mechanism and support for dynamic object creation. This approach allows us to reuse standard results of the theory of concurrency for reasoning on CORBA models of request invocation. The algebra of actors is well suited to specify most of the aspects of CORBA which concern interaction of objects, their creation and their deletion. Thus CORBA services which define these features [15], such as the Life Cycle Service, the Concurrency Service, the Transaction Service or the Naming Service are good candidates for being modelled with our algebra and they will be target of our future work. Moreover other CORBA services which describe internal aspects of the involved objects can also be modelled defining their interfaces and their functionalities in an abstract way. For example we have followed this approach in the formal definition of a CORBA server in Section 4.2. CORBA Exceptions can be also modelled as messages of the process algebra provided that they are included in the server specification. Namely, the specification of the CORBA server that we have presented in Section 4.2 must be extended considering that one of the possible outcomes of a request invocation can be an exception.



 516



M. Gaspari, G. Zavattaro



On the other hand, aspects such as types [12], quality of service and objects by value [32] have not an immediate mapping in our algebra. Thus a formal specification of all the CORBA features is not feasible with the current version of our algebra, and a significant extension is required to achieve this ambitious goal. A less ambitious goal will be to provide a specification of the CORBAScript [8] language which is more abstract and hides most of the low-level mechanisms of CORBA. Neverthenless, we still claim that a more formal description of interaction aspects of the CORBA services will be useful both to CORBA implementors and programmers. Finally, a number of additional research items still need to be carried out in this research. For instance: a study of how typing and inheritance issues, such as in [1] can be integrated in our framework to have a more real model of CORBA; the formulation of algebraic laws that characterize the equivalences of CORBA programs, for example an axiomatization for the asynchronous bisimulation and its application to CORBA; and the definition of a framework for formal reasoning about CORBA programs, e.g., following the style of the Hennessy and Milner logic [22].



Acknowledgements We would like to thank the anonymous referees for their detailed reports, and we acknowledge also interesting discussions with Carolyn Talcott as also her comments on a previous version of this paper.



References 1. M. Abadi and L. Cardelli. An Imperative Object Calculus. Theory and Practice of Object Systems, 1(3):151–166, 1995. 2. G. Agha. Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press, Cambridge, MA, 1986. 3. G. Agha, I. Mason, S. F. Smith, and C. Talcott. A Foundation for Actor Computation. Journal of Functional Programming, 7(1):1–69, January 1997. 4. G. Agha, I.A. Mason, S. Smith, and C. Talcott. Towards a Theory of Actor Computation. In Proc. of CONCUR’92, volume 630 of Lecture Notes in Computer Science, pages 564–579. Springer Verlag, 1992. 5. R. Amadio, I. Castellani, and D. Sangiorgi. On Bisimulations for the Asynchronous π-Calculus. Theoretical Computer Science, 195(2):291–324, 1998. 6. R. Bastide, O. Sy, and P. Palanque. Formal Specification and Prototyping of CORBA Systems. In Proc. of ECOOP99, Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1999. This volume. 7. G. Boudol. Asynchrony and the π−calculus. Technical Report INRIA-92-1702, INRIA Sophia-Antipolis., 1992. 8. Laboratoire d’Informatique Fondamentale de Lille and Object Oriented Concepts Inc. CORBA Scripting Language. Technical Report orbos/98-12-09, Object Management Group, 1998. 9. M. Gaspari. Concurrency and knowledge-level communication in agent languages. Artificial Intelligence, 105(1-2):1–45, 1998.



 A Process Algebraic Specification of CORBA



517



10. M. Gaspari and G. Zavattaro. An actor algebra for specifying distributed systems: the hurried philosophers case study. In G. Agha and F. Decindio, editors, Concurrent Object-Oriented Programming and Petri Nets, Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1998. To appear. 11. Mauro Gaspari and Gianluigi Zavattaro. An algebra of actors. In Proc. 3nd IFIP Conf. on Formal Methods for Open Object-Based Distributed Systems (FMOODS), pages 3–18. Kluwer Academic Publishers, Feb 1999. 12. Object Management Group. OMG Architecture Guide: The OMG Object Model. Technical report, Object Management Group, 1992. 13. Object Management Group. Messaging Service RFP. Technical Report orbos/9603-16, Object Management Group, Framingham, MA, 1996. 14. Object Management Group. CORBA Messaging Joint Revised Submission. Technical Report orbos/98-05-05, Object Management Group, Framingham, MA, 1998. 15. Object Management Group. CORBA Services. Technical Report formal/98-12-09, Object Management Group, 1998. 16. Object Management Group. The Common Object Request Brocker: Architecture and Specification. Object Management Group, 1998. 17. C. Hewitt. Viewing control structures as patterns of passing messages. Artificial Intelligence, 8(3):323–364, 1977. 18. CAR. Hoare. Communicating Sequential Processes. Prentice Hall, 1985. 19. K. Honda and M. Tokoro. An Object Calculus for Asynchronous Communication. In The Fifth European Conference on Object-Oriented Programming, volume 512 of Lecture Notes in Computer Science, pages 141–162. Springer-Verlag, Berlin, 1991. 20. S.N. Khoshafian and G.P. Copeland. Object Identity. In Proc. OOPSLA ’86, pages 406–416, September 1986. 21. I.A. Mason and C. Talcott. A Semantically Sound Actor Translation. In Proc. of ICALP’97, Lecture Notes in Computer Science. Springer Verlag, 1997. 22. R. Milner. Communication and Concurrency. Prentice Hall, 1989. 23. R. Milner. Functions as processes. Mathematical Structures in Computer Science, 2(2):119–141, 1992. 24. R. Milner. Elements of interaction. Communications of the ACM, 36(1):79–89, January 1993. 25. R. Milner, J. Parrow, and D. Walker. A calculus of mobile processes I and II. Information and Computation, 100(1):1–40 – 41–77, 1992. 26. E. Najm and JB. Stefani. Computational Models for Open Distributed Systems. In H. Bowman and J. Derrick, editors, Proc. 2nd IFIP Conf. on Formal Methods for Open Object-Based Distributed Systems (FMOODS), pages 157–176, Canterbury, UK, 1997. Chapmann & Hall. 27. C. Palamidessi. Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus. In Proc. ACM Symposium on Principles of Programming Languages (POPL), pages 256–265, 1997. 28. B. C. Pierce and D. N. Turner. Concurrent Objects in a Process Calculus. In invited lecture at Theory and Practice of Parallel Programming (TPPP), volume 907 of Lecture Notes in Computer Science, pages 187–215, Sendai, Japan, nov 1994. Springer-Verlag, Berlin. 29. G. Plotkin. A structural approach to operational semantics. Technical Report DAIMI FN-19, Department of Computer Science, Aarhus University, Denmark, 1981. 30. C. Talcott. Interaction Semantics for Components of Distributed Systems. In Proc. FMOODS’96, pages 154–169. Chapmann & Hall, 1996.



 518



M. Gaspari, G. Zavattaro



31. C. L. Talcott. An actor rewriting theory. In J. Meseguer, editor, Proc. 1st Intl. Workshop on Rewriting Logic and its Applications, number 4 in Electronic Notes in Theoretical Computer Science, pages 360–383. North Holland, 1996. 32. S. Vinoski. New Features for CORBA 3.0. Communications of the ACM, 41(10), October 1998. 33. D. Walker. Objects in the π−calculus. Information and Computation, 116(2):253– 271, 1995.



 Object-Oriented Programming: Regaining the Excitement Andrew P. Black Oregon Graduate Institute of Science & Technology Portland, Oregon, USA 



Abstract. This paper is based on a speech delivered at the ECOOP’98 Conference Banquet. It is not a literal transcription of my talk, since no recording was made, but has been reconstructed ex post facto based upon my speaker’s notes and my memory. I have also taken the opportunity to add some headings and references.



Distinguished Chairmen, Members of the Conference Committee, Representatives of the sponsoring organizations, distinguished Professors, conference participants, and friends: Good evening. It’s customary to start this kind of talk with a joke, at least in part to give the audience a chance to become accustomed to my strange accent before I start to say anything interesting, but I’m going to skip that tonight because I think that we have already heard quite enough jokes for one evening. To set the record straight from the very first, I should make it clear that I do not work for IBM, nor have I worked for IBM in the past. Although I did once spend a very enjoyable year at IBM’s Yorktown Heights Research Laboratory, IBM was very clear that I didn’t work for them, even though I did turn up every day and they did pay me: I believe that the distinction had something to do with social security tax or health insurance. I should also point out, particularly for the benefit of those of you around the corner who cannot see me, that yes, I am wearing a tie, but no, I don’t use a mainframe. I used to use a mainframe, but one day the mainframe broke and all of the little beads came off. [At this point the reader will have to imagine a large broken abacus frame with bent wires and missing beads.]



1



Inventing the Future of Object Technology



The right thing to do in a talk of this nature is to predict the future of object technology, but prediction is hard, and predicting the future is especially hard! Alan Kay once said: “The best way to predict the future is to invent it”. And he was remarkably accurate. Let me read you a quote from over 20 years ago.



Rachid Guerraoui (Ed.): ECOOP’99, LNCS 1628, pp. 519–528, 1999. c Springer-Verlag Berlin Heidelberg 1999 



 520



A.P. Black



In the 1990’s there will be millions of personal computers. They will be the size of notebooks of today, have high resolution flat screen reflective displays, weigh less than 10 pounds, have 10 to 20 times the computing and storage capacity of an Alto. Let’s call them Dynabooks. The purchase price will be about that of a color television set of the era... Though the Dynabook will have considerable local storage and do most computing locally, it will spend a large percentage of its time hooked to various large, global information utilities which will permit communication with others of ideas, data, working models as well as the daily chit-chat that organizations need in order to function. This is from Alan’s paper “The Early History of Smalltalk”[5], in which Alan quotes an internal Xerox PARC memo from around 1976. I recommend that paper most highly: if you find any wisdom in my remarks this evening, please attribute it to Alan Kay and not to me. My goal tonight is to challenge you to put the excitement back into objectorientation, and to recapture some of the dynamism of those early Smalltalk days. Is this possible? Or has object-orientation become like structured programming: the right idea, but no longer the focus of innovation, exactly because everyone is already doing it. For example, we don’t have a European Conference on Structured Programming every year. I don’t think that object-orientation is yet at that point. There are still many hard problems to solve: scale and encapsulation are two that I will mention briefly tonight.



2



Programming Language Contributions Relevant to Object-Orientation



The programming language research community has historically been a great source of innovation. I believe that we should challenge ourselves to recapture that atmosphere of innovation; to help us on our way, I will take a brief look at some of the ideas that have been “brought to market” by influential programming languages over the last forty years. I’m not claiming that the listed languages invented the concepts in every case, but rather that these languages were among the first to popularize them. 2.1



Lisp (late 1950s)



Lisp was a startling language for its time: I believe that Lisp is one of Alan Kay’s “almost new things”. It contributed: – heap allocation and garbage collection, – interpreted execution, and – conditional expressions.



 Object-Oriented Programming: Regaining the Excitement



2.2



521



Algol 60



Another “almost new thing”, in contrast to the “better old things” of COBOL and FORTRAN. Its contributions include: – – – –



– – – – –



a semi-formal, concise definition, grammars as a descriptive technique, block structure, recursion—but not the word “recursion”; - recursion introduced the distinction between program text (or “static instance”) and its execution (or “dynamic instance”). This distinction is the kernel of the idea that became Simula Objects [7]. Algol 60 also introduced declarations, call-by-name, “own” variables, the extension of the concept of expression to non-numeric values, - Boolean expressions, and - “designational expressions”, and the idea of “Security”, which we would probably today call semantic integrity.



Security is the principle that a program must either be rejected as incorrect by compile-time or run-time checks, or its behavior must be understandable by reasoning based entirely on the language semantics, independent of the implementation [2,7]. However, no language is perfect. Two “non-contributions” of Algol 60 were: – that the non-numeric expressions that Algol 60 chose to include were labels, not procedures; and that – input/output was relegated to a library. 2.3



Algol W, Pascal and Simula 67



Contributions: – – – – – – –



quasi-parallel execution (previously introduced in Knuth’s SOL); user-definable types; static inheritance (Simula’s prefix classes); use of prefix classes to provide “language dialects” Sum types, also known as variant types, or discriminated unions; the combination of data and operations in a single language construct; and the idea that binding of a value to a name requires only type compatibility, not type identity.



Non-contributions: – Explicit reference variables, and – Pascal’s sacrifice of the security of Algol 60 by the variant record construct. This last innovation is perhaps one of the reasons that Tony Hoare said of Algol 60: “here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors”[2].



 522



2.4



A.P. Black



Algol 68



Contributions: – unification of statement and expression, that is, making the distinction between them one of type, rather than one of context-free syntax; – the void type; – coercion; – environment enquiries; – conceptual minimality, for example, - the use of references to eliminate the notion of variable, and - the use of procedures to eliminate call-by-name; and – obtaining an extensible syntax—then an important goal—by means of the definition of new operators, and by that means alone. Non-contributions: – 2-level grammars as a descriptive technique, and – once again, breaching security, this time by requiring that the programmer not export a stack-allocated variable outside of its scope, which is not something for which implementations can easily check. 2.5



CLU, Alphard, Modula (1974-78)



Contributions: – – – –



2.6



encapsulation, named scopes (i.e., the module concept), parametric polymorphism, and F-bounded polymorphism (CLU’s where clauses) - but it’s not clear that the CLU designers realized at the time what they had invented. Emerald (1984-6)



Contributions: – safe, static subtyping, – F-bounded polymorphism (in the interpretation of conformity in where clauses)[4] - but we also did not yet know that it would be given this name, – mobile objects, – location-independent invocation, – object constructors (which I believe are relevant to Ole Lehrmann Madsen’s quest to integrate prototype and class-based programming styles), – separation of type from implementation, and – the “open world” assumption This last is the idea that new objects and new classes (superclasses as well as subclasses) can be added to a system at any time, so that we don’t have to shut down and recompile the internet.



 Object-Oriented Programming: Regaining the Excitement



2.7



523



Later Developments



What has happened since then? – multi-paradigm languages (LIFE, Leda, etc.) – higher-order functional languages with object-oriented concepts (Objective CAML, Haskel with its type classes, etc.) These are interesting, but not earth-shaking. And then, of course, we have Java. What are Java’s advances over Emerald? The major one is of course replacing word pair brackets (like do ... end) with curly braces {}, but we should not overlook typed byte-code and byte-code verification. The latter means that one can obtain a class that someone else has compiled and be sure that it is type-safe. This is a real advance, although proof-carrying code [6] may well be a more elegant and more widely applicable way of achieving the same effect.



3



A Research Agenda



To summarize this historical review, I believe that Programming Language Research has made major contributions to the state of computing today, but that recently the focus of research has moved away from pure OO towards hybrid languages and applications. These are interesting topics, but I do not believe that we have completed the development of object-orientation itself. 3.1



Objects Demonstrate Recursive Structure



My prescription is that we should re-examine the core of object-orientation. Going back to Smalltalk, we find that there are two key ideas: – that objects localize data structures and the code that operates on them in the same place; and – that objects, using the words of Alan Kay again: are a recursion on the idea of computer itself. Kay writes: “The basic principle of recursive design is to make the parts have the same power as the whole”. Rather than dividing the computer into “lesser stuffs”, like data structures and procedures, we should divide it into lots of little computers that communicate together. This enables us to postpone representation decisions almost indefinitely (and those are the decisions that are almost always the cause of our troubles). This sounds like a model for distributed computing to me. The World Wide Web is the largest and most successful distributed objectoriented system ever built—but what a poor system it is! For example, where is location independent naming? And how does one introduce a new class? The



 524



A.P. Black



answer to the latter question is that we persuade the W3 consortium to call an international meeting to get agreement on a new protocol! I propose that we take a long hard look at Kay’s three basic laws of objectoriented programming. 1. Everything is an object. 2. Objects communicate by sending and receiving messages (in term of objects). 3. Objects have their own memory (in terms of objects). 3.2



Information Hiding



Notice that there is nothing in the concept of little computers communicating with each other and protecting their own data that speaks of how to make information hiding decisions. Recall that the first key idea behind objects is “localization”, not “encapsulation”. Parnas’ idea of information hiding is a strong and powerful idea in program structuring: implementations of abstractions should hide as much as possible about themselves (but no more)! Hence, there are two parts to each information hiding decision: we must specify not only what to hide, but also from whom. The weakness of most encapsulation mechanisms is that they typically give the programmer fairly good control on the what, but very little on the whom. Java gives us three sets for whom: methods in this object, methods in objects that subclass from this object, and the rest of the world. But this is inadequate. I will give just two examples. – Think about allowing accessor and updater methods access to a slot, but prohibiting that access to other methods in the same object. – Think about a persistent system: how can programmers evolve the contents of an object in the store if they can’t access its fields? Don’t be misled into thinking that this last class of access somehow takes place “outside” of the system; our goal should be to describe the whole world as objects, and to use the reflective properties of those objects to examine and change their structure and their protocol. To put it another way: I want objects to take over the world, so I’m not prepared to start by excluding our own programming environments from the set of things that I can describe with objects. To the contrary: we should be using the reflective properties of objects to build our environments. Rather than the “all or nothing” encapsulation paradigm, what we need is a concept of encapsulation that is much closer to what operating system workers have thought of as “protection mechanisms”. For example, one programmer might take on several different roles in relation to the same object: she may be a maintenance programmer, then a user, and maybe later an administrator, and under those roles, the objects “in the programmer’s hand” should have different access rights to various parts of the target object.



 Object-Oriented Programming: Regaining the Excitement



3.3



525



Objects as an Integrative Paradigm



The third research direction that I would like to propose is that of objects as an integrative paradigm. The OO model is strong enough to capture functional and procedural styles of programming, but doing this naively is likely to result in “write only programs”. Let me explain. Many “idioms” can be written and not read. For example, I have used the functional style to build a Smalltalk Interval class in which the step and the limit slots hold blocks that are the step function and the limit predicate. Smalltalk programmers will be taken by surprise by such code. The reverse is also true: I can build objects in ML, but ML programmers will not be able to read the resulting code. Consequently, I do believe that multi-paradigm languages have a place, but I also believe that the non-OO features should be mapped onto objects. For example, functions should be objects with the convention that they have exactly one operation called ◦ (meaning “apply”). Nevertheless, it is important that the new features should be given an appropriate and readable syntax. The approach that I am advocating should enable us to retain semantic simplicity and avoid unpleasant interactions between features. During Tuesday’s Panel session, one of the questioners stated that his “old professor” (I do hate that phrase, now that I am one) said that: Programming language people think that they can solve a problem by designing a language to express it. I believe that this professor was right, and that such “language people” are also right! The reason is that language shapes thought: first we shape the tool, and then the tool shapes us. So it is vital that the tool be well-made. Category theory in mathematics is a good example: by exposing similarities between different branches of mathematics, some proofs that were obscure and difficult become self-evident. Lazy functional languages bring some of that clarity to programming certain kinds of problems. Does clarity come from having to force your problem into the mold of the language? Only if it works! Sometimes, the struggle to force your problem into a notation that does not seem appropriate can yield great insight; sometimes it is a waste of time. 3.4



Scale



The final challenge is scaling, but we must ask: in what dimension? The answer is: – in space, that is, wide area distribution; – in time, that is, Persistent Object Systems; – and, of course, in their combination.



 526



A.P. Black



Scaling in Space. Systems like Emerald that successfully handle distribution in the small do so by seeking to hide the distinction between local and remote objects. But the failure modes of local and remote objects are inherently different, and performance is radically reduced by distribution. This means that object placement is absolutely critical to application performance—and the tools that are currently available to automate or even understand placement are minimal. Another problem is how to replicate an object and still preserve its “object nature”. The systems community has spent 20 years working on replication, and we now know how to implement reliable and resilient systems from replicated communicating objects. But once we have done so, how can we treat the resulting subsystem as a single object, in order to hide its internal structure from its clients? A student (Mark Immel) and I presented one solution to this problem at ECOOP’93 [1], but I can’t believe that it is the only solution, or even that it is necessarily a very good one. I encourage you to work on this problem. Scaling in Time. I will defer to the experts who will be giving tomorrow morning’s invited lecture on Persistence in Java—Malcolm Atkinson and Mick Jordan—by mentioning only briefly some of the issues that must be resolved: – – – – –



4



compilation distributed in time; explicit support for versioning; safe and unsafe evolution of types; new interfaces for old objects; and new objects for old interfaces.



Summary



The Programming Language Research community has contributed massively to our progress in object-orientation to date. But recently, the pace of innovation seems to have slowed: we are making better old things, but I don’t see the almost new things. My message is the following. – Go back to the roots of object-orientation: - build little computational engines that communicate with one another to mimic the real world that we seek to model. – Use objects as an integrative paradigm: - build a semantic model that will serve for concurrent, functional, objectoriented and, if possible, constraint-based and logic programming; but - remember that the purpose of a program is to be read; and - that idioms reduce readability whereas well-designed language constructs enhance it. – Deal with the hard problems: scale, persistence, and their cross-product.



 Object-Oriented Programming: Regaining the Excitement



527



– Take encapsulation seriously, perhaps learning from the OS community. But I have to caution you to be careful of what you learn from the Operating Systems Community. At today’s conference, I am reminded of the 1983 ACM Symposium on Operating Systems Principles, which took place at the Mt. Washington Hotel at Bretton Woods in New Hampshire. This is the same hotel that was the site of the famous Bretton Woods monetary conference, which was held there toward the close of the Second World War. Although the plumbing hadn’t been touched since, it was a wonderfully atmospheric old hotel. I should add that it has since been completely renovated. I was young Assistant Professor, presenting my first paper at a conference, and was somewhat overawed by all of the “grand old men” of operating systems; the conference has been called the Symposium for OS Principals, and that is only partially a joke. I remember two things about the conference. The first is that it marked one of the early replicated failures of a replicated resilient system. The Grapevine nameservice had recently been built at Xerox PARC, and was the subject of a paper [9,8] to be presented at the conference that celebrated how, by supporting multiple servers that exchanged updates between them, the service had proved resilient to failure of one or even several of the individual servers. Unfortunately, all of the servers ran the same code on the same hardware, so when a particular packet was sent to the first server, triggered a bug, and caused the server to crash, the client responded by re-sending the same packet to the second server, and crashing that, and so on up the replication chain. As I recall, this packet was sent just at the time that all of the principals who might have diagnosed the problem had left Palo Alto to travel to Bretton Woods. The second thing that I recall about this conference is that it had shared “resources” in the form of bathrooms between adjacent pairs of rooms. It also had multiple processors, in the form of the occupants of the two rooms. Thus, to avoid collision, both processors had to correctly execute the bathroom door locking protocol. At breakfast on the first morning of the conference, many of these notable OS wizards were missing. It turned out that they had deadlocked contending for the bathrooms and the hotel staff had to be called to execute a manual reset. Thank you for listening so patiently; I hope that you enjoy the rest of your evening and the remainder of the conference.



 528



A.P. Black



References 1. Andrew P. Black and Mark P. Immel. Encapsulating plurality. In Proceedings of European Conference on Object-Oriented Programming, volume 707 of Lecture Notes in Computer Science, pages 57–79. Springer-Verlag, July 1993. 2. Charles Antony Richard Hoare. Hints on programming language design. Invited address at ACM SIGACT/SIGPLAN Symposium on Principles of Programming languages, (Reprinted in Horowitz [3], pages 35–40), October 1973. 3. Ellis Horowitz, editor. Programming Languages: A Grand Tour. Computer Science Press, third edition, 1987. 4. Norman Hutchinson. Emerald: An Object-Oriented Language for Distributed Programming. PhD thesis, University of Washington, Department of Computer Science, January 1987. 5. Alan C. Kay. The early history of Smalltalk. In Preprints of the Second ACM SIGPLAN History of Programming Languages Conference (HOPL–II), pages 69– 98, Cambridge, Massachusetts, March 1993. ACM SIGPLAN. 6. G. C. Necula and P. Lee. Safe, untrusted agents using proof-carrying code. In G. Vigna, editor, Mobile Agents and Security, volume 1419 of Lecture Notes in Computer Science, pages 61–91. Springer-Verlag, 1998. 7. Kristen Nygaard and Ole-Johan Dahl. The development of the SIMULA languages. In Richard L. Wexelblat, editor, History of Programming Languages, chapter IX, pages 439–493. Academic Press, 1981. 8. Michael D. Schroeder, Andrew D. Birell, and Roger M. Needham. Experience with Grapevine: The growth of a distributed system. ACM Transactions on Computer Systems, 2(1):3–23, February 1984. 9. Michael D. Schroeder, Andrew D.Birrell, and Roger M. Needham. Experience with Grapevine: The growth of a distributed system (Summary). In Proceedings of the Ninth ACM Symposium on Operating Systems Principles, pages 141–142. ACM SIGOPS, October 1983.



 Author Index Atul Adya . . . . . . . . . . . . . . . . . . . . . . . 230 Ole Agesen . . . . . . . . . . . . . . . . . . . . . . 258 R´emi Bastide . . . . . . . . . . . . . . . . . . . . 474 Elisa Bertino . . . . . . . . . . . . . . . . . . . . . 416 Andrew P. Black . . . . . . . . . . . . . . . . . 519 Viviana Bono . . . . . . . . . . . . . . . . . . . . . 43 John Boyland . . . . . . . . . . . . . . . . . . . . 205 Miguel Castro . . . . . . . . . . . . . . . . . . . .230 Craig Chambers . . . . . . . . . . . . . . . . . 279 Charles Consel . . . . . . . . . . . . . . . . . . . 367 Krzysztof Czarnecki . . . . . . . . . . . . . . . 18 David Detlefs . . . . . . . . . . . . . . . . . . . . 258 Sylvia Dieckman . . . . . . . . . . . . . . . . . . 92 Ulrich W. Eisenecker . . . . . . . . . . . . . . 18 Erik Ernst . . . . . . . . . . . . . . . . . . . . . . . . 67 Mauro Gaspari . . . . . . . . . . . . . . . . . . . 495 Aaron Greenhouse . . . . . . . . . . . . . . . 205 Giovanna Guerrini . . . . . . . . . . . . . . . 416 Brant Hashii . . . . . . . . . . . . . . . . . . . . . 449 Jifeng He . . . . . . . . . . . . . . . . . . . . . . . . . . .1 C.A.R Hoare . . . . . . . . . . . . . . . . . . . . . . . 1 Urs H¨olzle . . . . . . . . . . . . . . . . . . . . 92, 135 Wade Holst . . . . . . . . . . . . . . . . . . . . . . 304 Atsushi Igarashi . . . . . . . . . . . . . . . . . .161



Thomas K¨ uhne . . . . . . . . . . . . . . . . . . 329 Julia L. Lawall . . . . . . . . . . . . . . . . . . . 367 Raimondas Lencevicius . . . . . . . . . . .135 Yuri Leontiev . . . . . . . . . . . . . . . . . . . . 304 Barbara Liskov . . . . . . . . . . . . . . . . . . 230 Isabella Merlo . . . . . . . . . . . . . . . . . . . .416 Marco Mesiti . . . . . . . . . . . . . . . . . . . . 416 Todd Millstein . . . . . . . . . . . . . . . . . . . 279 Gilles Muller . . . . . . . . . . . . . . . . . . . . . 367 Philippe Palanque . . . . . . . . . . . . . . . 474 Raju Pandey . . . . . . . . . . . . . . . . . . . . . 449 Candy Pang . . . . . . . . . . . . . . . . . . . . . 304 Amit Patel . . . . . . . . . . . . . . . . . . . . . . . . 43 Wim De Pauw . . . . . . . . . . . . . . . . . . . 116 Benjamin C. Pierce . . . . . . . . . . . . . . 161 Ulrik Pagh Schultz . . . . . . . . . . . . . . . 367 Manuel Serrano . . . . . . . . . . . . . . . . . . 391 Gary Sevitski . . . . . . . . . . . . . . . . . . . . 116 Vitaly Shmatikov . . . . . . . . . . . . . . . . . 43 Liuba Shrira . . . . . . . . . . . . . . . . . . . . . 230 Ambuj K. Singh . . . . . . . . . . . . . . . . . 135 Ousmane Sy . . . . . . . . . . . . . . . . . . . . . 474 Duane Szafron . . . . . . . . . . . . . . . . . . . 304 Mads Torgersen . . . . . . . . . . . . . . . . . . 186 Jim Waldo . . . . . . . . . . . . . . . . . . . . . . . 441



G¨ unter Kniesel . . . . . . . . . . . . . . . . . . . 351 Gianluigi Zavattaro . . . . . . . . . . . . . . 495 Kresten Krab Thorup . . . . . . . . . . . . 186


	        	    
    		
    		    
    		    
    		
		    			
    
		
	    
		
		Object-Oriented Technology. ECOOP'99 Workshop Reader: ECOOP'99 Workshops, Panels, and Posters, Lisbon, Portugal, June 14-18, 1999 Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP 2004 - Object-Oriented Programming: 18th European Conference, Oslo, Norway, June 14-18, 2004, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP '97 - Object-Oriented Programming: 11th European Conference, Jyväskylä, Finland, June 9 - 13, 1997, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP 2001 - Object-Oriented Programming: 15th European Conference, Budapest, Hungary, June 18-22, 2001, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Advances in Artificial Life: 9th European Conference, ECAL 2007, Lisbon, Portugal, September 10-14, 2007, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Logics in Artificial Intelligence: 9th European Conference, JELIA 2004, Lisbon, Portugal, September 27-30, 2004, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Proceedings of the International Conference on Semigroups : Braga, Portugal, 18-23 June 1999
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Genetic Programming: Second European Workshop, EuroGP'99, Göteborg, Sweden, May 26-27, 1999, Proceedings: European Workshop, EuroGP '99, Goteborg, ... 2nd
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Active Networks: First International Working Conference, IWAN'99, Berlin, Germany, June 30 - July 2, 1999, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP 2000 - Object-Oriented Programming: 14th European Conference, Sophia, Antipolis and Cannes, France, June 12-16, 2000 Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP '96 - Object-Oriented Programming: 10th European Conference, Linz, Austria, July 8-12, 1996. Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP '92. European Conference on Object-Oriented Programming: Utrecht, The Netherlands, June 29 - July 3, 1992. Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP '93 - Object-Oriented Programming: 7th European Conference, Kaiserslautern, Germany, July 26-30, 1993. Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP '94 - Object-Oriented Programming: 8th European Conference, Bologna, Italy, July 4-8, 1994. Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP 2005 - Object-Oriented Programming: 19th European Conference, Glasgow, UK, July 25-29, 2005. Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP 2006 - Object-Oriented Programming: 20th European Conference, Nantes, France, July 3-7, 2006, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP 2003 - Object-Oriented Programming: 17th European Conference, Darmstadt, Germany, July 21-25, 2003. Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP 2008 - Object-Oriented Programming: 22nd European Conference Paphos, Cyprus, July 7-11, 2008, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		ECOOP '95, Object-Oriented Programming: European Conference on Object-oriented Programming: 9th European Conference, Aarhus, Denmark, August 7-11,
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Multimedia Applications, Services and Techniques - ECMAST'99: 4th European Conference, Madrid, Spain, May 26-28, 1999, Proceedings: ECMAST '99 ... 4th
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Field Programmable Logic and Application: 13th International Conference, FPL 2003, Lisbon, Portugal, September 1-3, 2003, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Symbolic and Quantitative Approaches to Reasoning and Uncertainty: European Conference, ECSQARU'99, London, UK, July 5-9, 1999, Proceedings: European
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Progress in Artificial Intelligence: 9th Portuguese Conference on Artificial Intelligence, EPIA '99, Evora, Portugal, September 21-24, 1999, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Distributed Computing: 13th International Symposium, DISC'99, Bratislava, Slovak Republic, September 27-29, 1999, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Distributed Computing: 15th International Conference, DISC 2001, Lisbon, Portugal, October 3-5, 2001. Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Circuit Cellar (June 1999)
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Visual Information and Information Systems: Third International Conference, VISUAL'99, Amsterdam, The Netherlands, June 2-4, 1999, Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Proceedings of the European Computing Conference 2
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Interoperating Geographic Information Systems: Second International Conference, INTEROP'99, Zurich, Switzerland, March 10-12, 1999 Proceedings
	    
	
	
	    Read more
	
    
		    			
    
		
	    
		
		Principles of Data Mining and Knowledge Discovery: Third European Conference, PKDD'99 Prague, Czech Republic, September 15-18, 1999 Proceedings
	    
	
	
	    Read more


	
            
                
                    Recommend Documents
                
		
		    						    
    
	
	    
	
    
    
	
	    
		Object-Oriented Technology. ECOOP'99 Workshop Reader: ECOOP'99 Workshops, Panels, and Posters, Lisbon, Portugal, June 14-18, 1999 Proceedings	    
	
	
	    Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen

1743

 3

Berlin Heidelberg New Yo...
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		ECOOP 2004 - Object-Oriented Programming: 18th European Conference, Oslo, Norway, June 14-18, 2004, Proceedings	    
	
	
	    Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris ...
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		ECOOP '97 - Object-Oriented Programming: 11th European Conference, Jyväskylä, Finland, June 9 - 13, 1997, Proceedings	    
	
	
	    
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		ECOOP 2001 - Object-Oriented Programming: 15th European Conference, Budapest, Hungary, June 18-22, 2001, Proceedings	    
	
	
	    Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen

2072

 3

Berlin Heidelberg New Yo...
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		Advances in Artificial Life: 9th European Conference, ECAL 2007, Lisbon, Portugal, September 10-14, 2007, Proceedings	    
	
	
	    Lecture Notes in Artificial Intelligence Edited by J. G. Carbonell and J. Siekmann

Subseries of Lecture Notes in Comput...
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		Logics in Artificial Intelligence: 9th European Conference, JELIA 2004, Lisbon, Portugal, September 27-30, 2004, Proceedings	    
	
	
	    Lecture Notes in Artificial Intelligence Edited by J. G. Carbonell and J. Siekmann

Subseries of Lecture Notes in Comput...
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		Proceedings of the International Conference on Semigroups : Braga, Portugal, 18-23 June 1999	    
	
	
	    PROCEEDI NGS OF THE I NTERNATIONAL CONFERENCE ON

SEMIGROUPS

 This page is intentionally left blank

 PROCEEDINGS OF TH...
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		Genetic Programming: Second European Workshop, EuroGP'99, Göteborg, Sweden, May 26-27, 1999, Proceedings: European Workshop, EuroGP '99, Goteborg, ... 2nd	    
	
	
	    Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen

1598

 3

Berlin Heidelberg New Yo...
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		Active Networks: First International Working Conference, IWAN'99, Berlin, Germany, June 30 - July 2, 1999, Proceedings	    
	
	
	    Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen

 3 Berlin Heidelberg New York Barc...
	
    
    
    
						    
    
	
	    
	
    
    
	
	    
		ECOOP 2000 - Object-Oriented Programming: 14th European Conference, Sophia, Antipolis and Cannes, France, June 12-16, 2000 Proceedings	    
	
	
	    Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen

1850

 3

Berlin Heidelberg New Yo...