A Formal Foundation for Concurrent Object Oriented Programming

Radu Grosu

In this thesis we develop a novel, implicitly typed lambda-calculus for objects, by viewing these as extendible case-functions rather than as extendible records.

This novel view, allows to unify the concepts of function, object and process into one concept, that of a functional entity which is self contained and provided with a uniform communication protocol. We use this view to give a formal foundation for both sequential and concurrent object oriented languages. In the later case, we view objects as case-functions communicating asynchronously over unbounded channels.

Our calculus is a conservative extension of the polymorphic type system of Aiken and Wimmers, to include case-function extension and lazy data types. Its soundness is proven with respect to a semantical model based on ideals. Subtyping and case-function extension play a central role in our modeling of generalization/specialization and inheritance. To model self and self-class, our calculus includes recursive types. These are also necessary to model streams and provide the theoretical background for passing streams themselves as messages. We use higher order streams to express mobile systems. For the study of mobile systems we additionally devise a network calculus on the top of the lambda calculus.

The implicitly typed lambda-calculus is accompanied with a decidable type inference algorithm, which always delivers the least type of a term (if this exists). An implementation of this algorithm was written in Common Lisp.

Available: Pdf

BibTeX: @phdthesis{Gro94, author = {R. Grosu}, school = {Technische Universit{\"a}t M{\"u}nchen}, title = {A Formal Foundation for Concurrent Object Oriented Programming}, year = {1994}, note = {Technical Report {TUM-I9444}} }