Creol: A type-safe object-oriented model for distributed concurrent systems. (English) Zbl 1118.68031

Summary: Object-oriented distributed computing is becoming increasingly important for critical infrastructure in society. In standard object-oriented models, objects synchronize on method calls. These models may be criticized in the distributed setting for their tight coupling of communication and synchronization; network delays and instabilities may locally result in much waiting and even deadlock. The Creol model targets distributed objects by a looser coupling of method calls and synchronization. Asynchronous method calls and high-level local control structures allow local computation to adapt to network instability. Object variables are typed by interfaces, so communication with remote objects is independent from their implementation. The inheritance and subtyping relations are distinct in Creol. Interfaces form a subtype hierarchy, whereas multiple inheritance is used for code reuse at the class level. This paper presents the Creol syntax, operational semantics, and type system. It is shown that runtime type errors do not occur for well-typed programs.


68M14 Distributed systems
Full Text: DOI


[1] Abadi, M.; Cardelli, L., A theory of objects. monographs in computer science, (1996), Springer Berlin
[2] Ábrahám-Mumm, E.; de Boer, F.S.; de Roever, W.-P.; Steffen, M., Verification for Java’s reentrant multithreading concept, (), 5-20 · Zbl 1077.68552
[3] Agha, G.A., Abstracting interaction patterns: A programming paradigm for open distributed systems, (), 135-153
[4] Agha, G.A.; Mason, I.A.; Smith, S.F.; Talcott, C.L., A foundation for actor computation, J. funct. programming, 7, 1, 1-72, (1997) · Zbl 0870.68091
[5] America, P.; van der Linden, F., A parallel object-oriented language with inheritance and subtyping, (), 161-168
[6] Andrews, G.R., Foundations of multithreaded, parallel, and distributed programming, (2000), Addison-Wesley Reading, MA
[7] Attali, I.; Caromel, D.; Ehmety, S.O., A natural semantics for eiffel dynamic binding, ACM trans. on program. lang. and systems, 18, 6, 711-729, (1996)
[8] Benton, N.; Cardelli, L.; Fournet, C., Modern concurrency abstractions for \(\operatorname{C}^\sharp\), ACM trans. on program. lang. and systems, 26, 5, 769-804, (2004)
[9] Bettini, L.; Bono, V.; Nicola, R.D.; Ferrari, G.L.; Gorla, D.; Loreti, M.; Moggi, E.; Pugliese, R.; Tuosto, E.; Venneri, B., The klaim project: theory and practice, (), 88-150 · Zbl 1179.68027
[10] Bracha, G.; Cook, W., Mixin-based inheritance, (), 303-311
[11] Brinch Hansen, P., Java’s insecure parallelism, ACM SIGPLAN not., 34, 4, 38-45, (April 1999)
[12] Bruce, K.B., Foundations of object-oriented languages: types and semantics, (2002), The MIT Press Cambridge, MA
[13] Bruce, K.B.; Schuett, A.; van Gent, R.; Fiech, A., Polytoil: a type-safe polymorphic object-oriented language, ACM trans. on program. lang. and systems, 25, 2, 225-290, (2003)
[14] Cardelli, L., A semantics of multiple inheritance, Inform. and comput., 76, 2-3, 138-164, (1988) · Zbl 0651.68017
[15] Cardelli, L., A language with distributed scope, Comput. systems, 8, 1, 27-59, (1995)
[16] Caromel, D.; Roudier, Y., Reactive programming in eiffel//, (), 125-147
[17] Carriero, N.; Gelernter, D., Linda in context, Comm. of the ACM, 32, 4, 444-458, (1989)
[18] Cenciarelli, P.; Knapp, A.; Reus, B.; Wirsing, M., An event-based structural operational semantics of multi-threaded Java, (), 157-200
[19] Chambers, C.; Ungar, D.; Chang, B.-W.; Hölzle, U., Parents are shared parts of objects: inheritance and encapsulation in SELF, Lisp and symbolic comput., 4, 3, 207-222, (1991)
[20] Clavel, M.; Durán, F.; Eker, S.; Lincoln, P.; Martí-Oliet, N.; Meseguer, J.; Quesada, J.F., Maude: specification and programming in rewriting logic, Theoret. comput. sci., 285, 187-243, (August 2002)
[21] Cook, W.; Palsberg, J., A denotational semantics of inheritance and its correctness, Inform. and comput., 114, 2, 329-350, (November 1994)
[22] W.R. Cook, W. L. Hill, P. S. Canning, Inheritance is not subtyping, in: 17th ACM Symp. on Principles of Programming Languages (POPL’90), ACM Press, New York, January 1990, pp. 125-135. · Zbl 0837.68061
[23] Cugola, G.; Ghezzi, C., Cjava: introducing concurrent objects in Java, (), 504-514
[24] Dahl, O.-J., Monitors revisited, (), 93-103
[25] O.-J. Dahl, B. Myrhaug, K. Nygaard, (Simula 67) Common base language. Technical report S-2, Norsk Regnesentral (Norwegian Computing Center), Oslo, Norway, May 1968.
[26] W. Damm, B. Josko, A. Pnueli, A. Votintseva, Understanding UML: a formal semantics of concurrency and communication in real-time UML, in: F.S. de Boer, M.M. Bonsangue, S. Graf, W.P. de Roever (Eds.), First Internat. Symp. Formal Methods for Components and Objects (FMCO 2002), Lecture Notes in Computer Science, Vol. 2852, Springer, Berlin, 2003, pp. 71-98. · Zbl 1254.68140
[27] L.G. DeMichiel, R. P. Gabriel, The common lisp object system: an overview, in: J. Bézivin, J.-M. Hullot, P. Cointe, H. Lieberman (Eds.), European Conf. on Object-Oriented Programming (ECOOP’87), Lecture Notes in Computer Science, Vol. 276, Springer, Berlin, 1987, pp. 151-170.
[28] Di Blasio, P.; Fisher, K., A calculus for concurrent objects, (), 655-670
[29] Dijkstra, E.W., Guarded commands, nondeterminacy and formal derivation of programs, Comm. of the ACM, 18, 8, 453-457, (1975) · Zbl 0308.68017
[30] Dijkstra, E.W., A discipline of programming, (1976), Prentice-Hall Englewood Cliffs, NJ · Zbl 0286.00013
[31] J. Dovland, E.B. Johnsen, O. Owe, Verification of concurrent objects with asynchronous method calls, in: Proc. IEEE Internat. Conf. on Software—Science, Technology & Engineering (SwSTE’05), IEEE Computer Society Press, Silver Spring, MD, February 2005, pp. 141-150.
[32] Drossopoulou, S.; Damiani, F.; Dezani-Ciancaglini, M.; Giannini, P., More dynamic object re-classification: \(\operatorname{Fickle}_{\operatorname{II}}\), ACM trans. on program. lang. and systems, 24, 2, 153-191, (2002)
[33] C. Fournet, G. Gonthier, The reflexive chemical abstract machine and the Join-calculus, in: ACM Symp. on Principles ofProgramming Languages (POPL), 1996, pp. 372-385.
[34] Goguen, J.A.; Winkler, T.; Meseguer, J.; Futatsugi, K.; Jouannaud, J.-P., Introducing OBJ, (), 3-167, (Chapter 1)
[35] Gordon, A.D.; Hankin, P.D., A concurrent object calculus: reduction and typing, () · Zbl 0917.68064
[36] J. Gosling, B. Joy, G.L. Steele, G. Bracha, The Java Language Specification, Java Series, second ed., Addison-Wesley, Reading, MA, 2000. · Zbl 0865.68001
[37] Hailpern, B.; Ossher, H., Extending objects to support multiple interfaces and access control, IEEE trans. on software eng., 16, 11, 1247-1257, (1990)
[38] Hoare, C.A.R., Monitors: an operating systems structuring concept, Comm. of the ACM, 17, 10, 549-557, (1974) · Zbl 0308.68029
[39] Hoare, C.A.R., Communicating sequential processes, international series in computer science, (1985), Prentice-Hall Englewood Cliffs, NJ · Zbl 0637.68007
[40] Honda, K.; Tokoro, M., An object calculus for asynchronous communication, (), 133-147
[41] Igarashi, A.; Pierce, B.C.; Wadler, P., Featherweight Java: a minimal core calculus for Java and GJ, ACM trans. program. lang. and systems, 23, 3, 396-450, (2001)
[42] International Telecommunication Union, Open distributed processing—reference model parts 1-4, Technical report, ISO/IEC, Geneva, July 1995.
[43] G.S. Itzstein, M. Jasiunas, On implementing high level concurrency in Java, in: A. Omondi, S. Sedukhin (Eds.), Proc. Eighth Asia-Pacific Computer Systems Architecture Conference (ACSAC 2003), Lecture Notes in Computer Science, Vol. 2823, Springer, Berlin, 2003, pp. 151-165.
[44] Johnsen, E.B.; Owe, O., A compositional formalism for object viewpoints, (), 45-60 · Zbl 1056.68103
[45] Johnsen, E.B.; Owe, O., Object-oriented specification and open distributed systems, (), 137-164 · Zbl 1278.68067
[46] E.B. Johnsen, O. Owe, Inheritance in the presence of asynchronous method calls. in: Proc. 38th Hawaii Internat. Conf. System Sciences (HICSS’05), IEEE Computer Society Press, Silver Spring, MD, January 2005.
[47] E.B. Johnsen, O. Owe, An asynchronous communication model for distributed concurrent objects, Software and Systems Model, 2006, doi: 10.1007/s10270-006-0011-2.
[48] E.B. Johnsen, O. Owe, E.W. Axelsen, A run-time environment for concurrent objects with asynchronous method calls, in: N. Martí-Oliet (Ed.), Proc. Fifth International Workshop on Rewriting Logic and its Applications (WRLA’04), Mar. 2004, Electronic Notes in Theoretical Computer Science, Vol. 117, Elsevier Science Publishers, Amsterdam, January 2005, pp. 375-392. · Zbl 1272.68186
[49] Johnsen, E.B.; Owe, O.; Simplot-Ryl, I., A dynamic class construct for asynchronous concurrent objects, (), 15-30
[50] Kiczales, G.; Lamping, J.; Menhdhekar, A.; Maeda, C.; Lopes, C.; Loingtier, J.-M.; Irwin, J., Aspect-oriented programming, (), 220-242
[51] Krogdahl, S., Multiple inheritance in simula-like languages, Bit, 25, 2, 318-326, (1985) · Zbl 0566.68005
[52] Laneve, C., Inheritance in concurrent objects, (), 326-353 · Zbl 1256.68036
[53] Liskov, B.H.; Shrira, L., Promises: linguistic support for efficient asynchronous procedure calls in distributed systems, (), 260-267
[54] Liskov, B.H.; Wing, J.M., A behavioral notion of subtyping, ACM trans. program. lang. and systems, 16, 6, 1811-1841, (November 1994)
[55] Lucassen, J.M.; Gifford, D.K., Polymorphic effect systems, (), 47-57
[56] Matsuoka, S.; Yonezawa, A., Analysis of inheritance anomaly in object-oriented concurrent programming languages, (), 107-150
[57] Meseguer, J., Conditional rewriting logic as a unified model of concurrency, Theoret. comput. sci., 96, 73-155, (1992) · Zbl 0758.68043
[58] Meseguer, J.; Rosu, G., Rewriting logic semantics: from language specifications to formal analysis tools, (), 1-44 · Zbl 1126.68464
[59] Meyer, B., Object-oriented software construction, (1997), Prentice Hall Englewood Cliffs, NJ · Zbl 0987.68516
[60] Mikhajlov, L.; Sekerinski, E., A study of the fragile base class problem, (), 355-382
[61] G. Milicia, V. Sassone, The inheritance anomaly: ten years after, in: Proc. 2004 ACM Symp. on Applied Computing, ACM Press, New York, 2004, pp. 1267-1274
[62] Milner, R., Communicating and mobile systems: the \(\pi\)-calculus, (May 1999), Cambridge University Press Cambridge
[63] Najm, E.; Stefani, J.-B., A formal semantics for the ODP computational model, Comput. networks and ISDN systems, 27, 1305-1329, (1995)
[64] Nierstrasz, O., A tour of hybrid-A language for programming with active objects, (), 167-182
[65] Odersky, M.; Cremet, V.; Röckl, C.; Zenger, M., A nominal theory of objects with dependent types, (), 201-224
[66] Philippsen, M., A survey on concurrent object-oriented languages, Concurrency: pract. and experience, 12, 10, 917-980, (August 2000)
[67] Pierce, B.C., Types and programming languages, (2002), The MIT Press Cambridge, MA
[68] Pierce, B.C.; Turner, D.N., Pict: a programming language based on the pi-calculus, ()
[69] Rossie, J.G.; Friedman, D.P.; Wand, M., Modeling subobject-based inheritance, (), 248-274
[70] Schärli, N.; Ducasse, S.; Nierstrasz, O.; Black, A.P., Traits: composable units of behaviour, (), 248-274
[71] Snyder, A., Inheritance and the development of encapsulated software systems, (), 165-188
[72] Soundarajan, N.; Fridella, S., Inheritance: from code reuse to reasoning reuse, (), 206-215
[73] Stroustrup, B., Multiple inheritance for C++, Comput. systems, 2, 4, 367-395, (December 1989)
[74] Talpin, J.-P.; Jouvelot, P., Polymorphic type, region and effect inference, J. funct. programming, 2, 3, 245-271, (1992) · Zbl 0817.68099
[75] M. VanHilst, D. Notkin, Using role components to implement collaboration-based designs, in: Proc. Conf. on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA’96), ACM Press, New York, 1996, pp. 359-369.
[76] V.T. Vasconcelos, Typed concurrent objects, in: M. Tokoro, R. Pareschi (Eds.), Proc. of the Eighth European Conf. on Object-Oriented Programming (ECOOP’94), Lecture Notes in Computer Science, Vol. 821, Springer, Berlin, 1994, pp. 100-117.
[77] Walker, D., Objects in the \(\pi\)-calculus, Inform. and comput., 116, 2, 253-271, (February 1995)
[78] Wirfs-Brock, R.J.; Johnson, R.E., Surveying current research in object-oriented design, Comm. of the ACM, 33, 9, 104-124, (1990)
[79] Yokote, Y.; Tokoro, M., Concurrent programming in concurrentsmalltalk, (), 129-158
[80] Yonezawa, A., ABCL: an object-oriented concurrent system, series in computer systems, (1990), The MIT Press Cambridge, MA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.