Object-oriented programming

Structural subtyping is an important notion for effective static type analysis; it can be defined either axiomatically by a collection of subtyping rules, or by means of set inclusion between type interpretations, following the semantic subtyping approach, which is more intuitive, and allows simpler proofs of the expected properties of the subtyping relation.

In object-oriented programming, recursive types typically correspond to inductively defined data structures, and subtyping is defined axiomatically; however, in object-oriented languages objects can also be cyclic, but inductive types cannot represent them as precisely as happens for coinductive types.

We study semantic subtyping between coinductive types with records and unions, which are particularly interesting for object-oriented programming, show cases where it allows more precise type analysis, and develop a sound and complete effective algorithm for deciding it. To our knowledge, this is the first proposal for a sound and complete algorithm for semantic subtyping between coinductive types.

Small-step operational semantics is the most commonly employed formalism for proving type soundness of statically typed programming languages, because of its ability to distinguish stuck from non-terminating computations, as opposed to big-step operational semantics.

Despite this, big-step operational semantics is more abstract, and more useful for specifying interpreters.

In previous work we have proposed a new proof technique to prove type soundness of a Java-like language expressed in terms of its big-step operational semantics. However the presented proof is rather involved, since it requires showing that the set of proof trees defining the semantic judgment forms a complete metric space when equipped with a specific distance function. In this paper we propose a more direct and abstract approach that exploits a standard and general compactness property of the metric space of values, that allows approximation of the coinductive big-step semantics in terms of the small-step one; in this way type soundness can be proved by standard mathematical induction.

In previous work we have presented coFJ, an extension to Featherweight Java that promotes coinductive programming, a sub-paradigm expressly devised to ease high-level programming and reasoning with cyclic data structures. The coFJ language supports cyclic objects and regularly corecursive methods, that is, methods whose invocation terminates not only when the corresponding call trace is finite (as happens with ordinary recursion), but also when such a trace is infinite but cyclic, that is, can be specified by a regular term, or, equivalently, by a finite set of recursive syntactic equations. In coFJ it is not easy to ensure that the invocation of a corecursive method will return a well-defined value, since the recursive equations corresponding to the regular trace of the recursive calls may not admit a (unique) solution; in such cases we say that the value returned by the method call is undetermined. In this paper we propose two new contributions. First, we design a simpler construct for defining corecursive methods and, correspondingly, provide a more intuitive operational semantics. For this coFJ variant, we are able to define a type system that allows the user to specify that certain corecursive methods cannot return an undetermined value; in this way, it is possible to prevent unsafe use of such a value. The operational semantics and the type system of coFJ are fully formalized, and the soundness of the type system is proved.

It is well known that big-step operational semantics are not suitable for proving soundness of type systems, because of their inability to distinguish stuck from non-terminating computations. We show how this problem can be solved by interpreting coinductively the rules for the standard big-step operational semantics of a Java-like language, thus making the claim of soundness more intuitive: whenever a program is well-typed, its coinductive operational semantics returns a value. Indeed, coinduction allows non-terminating computations to return values; this is proved by showing that the set of proof trees defining the semantic judgment forms a complete metric space when equipped with a proper distance function. In this way, we are able to prove soundness of a nominal type system w.r.t. the coinductive semantics. Since the coinductive semantics is sound w.r.t. the usual small-step operational semantics, the standard claim of soundness can be easily deduced.

In previous work we have shown that more precise type analysis can be achieved by exploiting union types and static single assignment (SSA) intermediate representation (IR) of code. In this paper we exploit static single information (SSI), an extension of SSA proposed in literature and adopted by some compilers, to allow assignments of more precise types to variables in conditional branches. In particular, SSI can be exploited rather easily and effectively to infer more precise types in dynamic object-oriented languages, where explicit runtime typechecking is frequently used. We show how the use of SSI form can be smoothly integrated with abstract compilation, our approach to static type analysis. In particular, we define abstract compilation based on union and nominal types for a simple dynamic object-oriented language in SSI form with a runtime typechecking operator, to show how precise type inference can be.

Corecursive FeatherWeight Java (coFJ) is a recently proposed extension of the calculus FeatherWeight Java (FJ), supporting cyclic objects and regular recursion, and explicitly designed to promote a novel programming paradigm inspired by coinductive Logic Programming (coLP), based on coinductive, rather than inductive, interpretation of recursive function definitions. We present a slightly modified version of coFJ where the application of a coinductive hypothesis can trigger the evaluation of a specific expression at declaration, rather than at use site. Following an approach inspired by abstract compilation, we then show how coFJ can be directly translated into coLP, when coinductive SLD is extended with a similar feature for explicitly solving a goal when a coinductive hypothesis is applied. Such a translation is quite compact and, besides showing the direct relation between coFJ and coinductive Prolog, provides a first prototypical but simple and effective implementation of coFJ.

Despite cyclic data structures occur often in many application domains, object-oriented programming languages provide poor abstraction mechanisms for dealing with cyclic objects. Such a deficiency is reflected also in the research on theoretical foundation of object-oriented languages; for instance, Featherweigh Java (FJ), which is one of the most widespread object-oriented calculi, does not allow creation and manipulation of cyclic objects. We propose an extension to Featherweight Java, called coFJ, where it is possible to define cyclic objects, {abstractly corresponding to regular terms}, and where an abstraction mechanism, called regular corecursion, is provided for supporting implementation of coinductive operations on cyclic objects. We formally define the operational semantics of coFJ, and provide a handful of examples showing the expressive power of regular corecursion; such a mechanism promotes a novel programming style particularly well-suited for implementing cyclic data structures, and for supporting coinductive reasoning.

This paper further investigates the potential and practical applicability of abstract compilation in two different directions. First, we formally define an abstract compilation scheme for precise prediction of uncaught exceptions for a simple Java-like language; besides the usual user declared checked exceptions, the analysis covers the runtime ClassCastException. Second, we present a general implementation schema for abstract compilation based on coinductive CLP with variance annotation of user-defined predicates, and propose an implementation based on a Prolog prototype meta-interpreter, parametric in the solver for the subtyping constraints.

In recent work we have proposed a novel approach to define idealized type systems for object-oriented languages, based on abstract compilation of programs into Horn formulas which are interpreted w.r.t. the coinductive (that is, the greatest) Herbrand model. In this paper we investigate how this approach can be applied also in the presence of imperative features. This is made possible by con- sidering a natural translation of Static Single Assignment intermediate form programs into Horn formulas, where phi functions correspond to union types.

We define a coinductive semantics for a simple Java-like language by simply interpreting coinductively the rules of a standard big-step operational semantics. We prove that such a semantics is sound w.r.t. the usual small-step operational semantics, and then prove soundness of a conventional nominal type system w.r.t. the coinductive semantics. From these two results, soundness of the type system w.r.t. the small-step semantics can be easily deduced. This new proposed approach not only opens up new possibilities for proving type soundness, but also provides useful insights on the connection between coinductive big-step operational semantics and type systems.

Coinductive abstract compilation is a novel technique, which has been recently introduced for defining precise type systems for object- oriented languages. In this approach, type inference consists in translating the program to be analyzed into a Horn formula f, and in resolving a certain goal w.r.t. the coinductive (that is, the greatest) Herbrand model of f. Type systems defined in this way are idealized, since types and, con- sequently, goal derivations, are not finitely representable. Hence, sound implementable approximations have to rely on the notions of regular types and derivations, and of subtyping and subsumption between types and atoms, respectively. In this paper we address the problem of defining a sound and complete axiomatization of a subtyping relation between coinductive object and union types, defined as set inclusion between type interpretations. Besides being an important theoretical result, completeness is useful for reasoning about possible implementations of the subtyping relation, when restricted to regular types.

This paper further investigates the potential and practical applicability of abstract compilation in two different directions. First, we formally define an abstract compilation scheme for precise prediction of uncaught exceptions for a simple Java-like language; besides the usual user declared checked exceptions, the analysis covers the runtime ClassCastException. Second, we present a general implementation schema for abstract compilation based on coinductive CLP with variance annotation of user-defined predicates, and propose an implementation based on a Prolog prototype meta-interpreter, parametric in the solver for the subtyping constraints.

Coinductive abstract compilation is a novel technique, which has been recently introduced, for defining precise type systems for object-oriented languages. In this approach, type inference consists in translating the program to be analyzed into a Horn formula f, and in resolving a certain goal w.r.t. the coinductive (that is, the greatest) Herbrand model of f. Type systems defined in this way are idealized, since types and, consequently, goal derivations, are not finitely representable. Hence, sound implementable approximations have to rely on the notions of regular types and derivations, and of subtyping and subsumption between types and atoms, respectively. In this paper we address the problem of defining a complete subtyping relation <= between types built on object and union type constructors: we interpret types as sets of values, and investigate on a definition of subtyping such that t_1 <= t_2 is derivable whenever the interpretation of t_1 is contained in the interpretation of t_2. Besides being an important theoretical result, completeness is useful for reasoning about possible implementations of the subtyping relation, when restricted to regular types.

In recent work we have shown how it is possible to define very precise type systems for object-oriented languages by abstractly compiling a program into a Horn formula f. Then type inference amounts to resolving a certain goal w.r.t. the coinductive (that is, the greatest) Herbrand model of f. Type systems defined in this way are idealized, since in the most interesting instantiations both the terms of the coinductive Herbrand universe and goal derivations cannot be finitely represented. However, sound and quite expressive approximations can be implemented by considering only regular terms and derivations. In doing so, it is essential to introduce a proper subtyping relation formalizing the notion of approximation between types. In this paper we study a subtyping relation on coinductive terms built on union and object type constructors. We define an interpretation of types as set of values induced by a quite intuitive relation of membership of values to types, and prove that the definition of subtyping is sound w.r.t. subset inclusion between type interpretations. The proof of soundness has allowed us to simplify the notion of contractive derivation and to discover that the previously given definition of subtyping did not cover all possible representations of the empty type.

We propose a novel general approach for defining expressive type systems for object-oriented languages, based on abstract compilation of programs into coinductive constraint logic programs defined on a specific constraint domain X called type domain. In this way, type checking and type inference amount to resolving a certain goal w.r.t. the coinductive (that is, the greatest) Herbrand model of a logic program (that is, a Horn formula) with constraints over a fixed type domain X. In particular, we show an interesting instantiation where the constraint predicates of X are syntactic equality and subtyping over coinductive object and union types. The corresponding type system is so expressive to allow verification of simple properties like data structure invariants. Finally, we show a prototype implementation, written in Prolog, of the inference engine for coinductive CLP(X), which is parametric in the solver for the type domain X.

The Common Language Infrastructure (CLI) is a virtual machine expressly designed for implementing statically typed languages such as C#, therefore programs written in dynamically typed languages are typically much slower than C# when executed on .NET. Recent developments show that Just In Time (JIT) compilers can exploit runtime type information to generate quite efficient code. Unfortunately, writing a JIT compiler is far from being simple. In this paper we report our positive experience with automatic generation of JIT compilers as supported by the PyPy infrastructure, by focusing on JIT compilation for .NET. Following this approach, we have in fact added a second layer of JIT compilation, by allowing dynamic generation of more efficient .NET bytecode, which in turn can be compiled to machine code by the .NET JIT compiler. The main and novel contribution of this paper is to show that this two-layers JIT technique is effective, since programs written in dynamic languages can run on .NET as fast as (and in some cases even faster than) the equivalent C# programs. The practicality of the approach is demonstrated by showing some promising experiments done with benchmarks written in a simple dynamic language.

We propose a novel approach to constraint-based type inference based on coinductive logic programming. That is, constraint generation corresponds to translation into a conjunction of Horn clauses P, and constraint satisfaction is defined in terms of the maximal coinductive Herbrand model of P. We illustrate the approach by formally defining this translation for a small object-oriented language similar to Featherweight Java, where type annotations in field and method declarations can be omitted. In this way, we obtain a very precise type inference and provide new insights into the challenging problem of type inference for object-oriented programs. Since the approach is deliberately declarative, we define in fact a formal specification for a general class of algorithms, which can be a useful road maps to researchers. Moreover, despite we consider here a particular language, the methodology could be used in general for providing abstract specifications of type inference for different kinds of programming languages.

We propose a novel approach based on coinductive logic to specify type systems of programming languages. The approach consists in encoding programs in Horn formulas which are interpreted w.r.t. their coinductive Herbrand model. We illustrate the approach by first specifying a standard type system for a small object-oriented language similar to Featherweight Java. Then we define an idealized type system for a variant of the language where type annotations can be omitted. The type system involves infinite terms and proof trees not representable in a finite way, thus providing a theoretical limit to type inference of object-oriented programs, since only sound approximations of the system can be implemented. Approximation is naturally captured by the notions of subtyping and subsumption; indeed, rather than increasing the expressive power of the system, as it usually happens, here subtyping is needed for approximating infinite non regular types and proof trees with regular ones.

Writing an optimizing static compiler for dynamic languages is not an easy task, since quite complex static analysis is required. On the other hand, recent developments show that JIT compilers can exploit runtime type information to generate quite efficient code. Unfortunately, writing a JIT compiler is far from being simple. In this paper we report our positive experience with automatic generation of JIT compilers as supported by the PyPy infrastructure, by focusing on JIT compilation for .NET. The paper presents two main and novel contributions: we show that partial evaluation can be used in practice for generating a JIT compiler, and we experiment with the potentiality offered by the ability to add a further level of JIT compilation on top of .NET. The practicality of the approach is demonstrated by showing some promising experiments done with benchmarks written in a simple dynamic language.

This paper proposes a solution to the problem of semi-automatic porting of Java programs. In particular, our work aims at the design of tools able to aid users to adapt Java code in a type-safe way, when an application has to migrate to new libraries which are not fully compatible with the legacy ones. To achieve this, we propose an approach based on an integration of the two type-theoretic notions of subtyping and type isomorphism with ontology matching. While the former notions are needed to ensure flexible adaptation in the presence of type-safety, the latter supports the user to preserve the semantics of the program to be adapted.

Although coinductive logic programming (Co-LP) has proved to have several applications, including verification of infinitary properties, model checking and bisimilarity proofs, type inference via Co-LP has not been properly investigated yet. In this paper we show a novel approach to solve the problem of type inference in the context of Java-like languages, that is, object-oriented languages based on nominal subtyping. The proposed approach follows a generic scheme: first, the program P to be analyzed is translated into an approximating logic program P' and a goal G; then, the solution of the type inference problem corresponds to find an instantiation of the goal G which belongs to the greatest model of P', that is, the coinductive model of P'. Operationally, this corresponds to find a co-SLD derivation of G in P', according to the operational semantics of Co-LP recently defined by Simon et al. [ICLP06,ICALP07]. A complete formalization of an instantiation of this scheme is considered for a simple object-oriented language and a corresponding type soundness theorem is stated. A prototype implementation based on a meta-interpreter of co-SLD has been implemented. Finally, we address scalability issues of the approach, by sketching an instantiation able to deal with a much more expressive object-oriented language.

We define a framework of components based on Java-like languages, where components are binary mixin modules. Basic components can be obtained from a collection of classes by compiling such classes in isolation; for allowing that, requirements in the form of type constraints are associated with each class. Requirements are specified by the user who, however, is assisted by the compiler that can generate missing constraints essential to guarantee type safety. Basic components can be composed together by using a set of expressive typed operators; thanks to soundness results, such a composition is always type safe. The framework is designed as a separate layer that can be instantiated on top of any Java-like language; to show the effectiveness of the approach, an instantiation on a small Java subset is provided, together with a prototype implementation. Besides safety, the approach achieves great flexibility in reusing components for two reasons: (1) type constraints generated for a single component exactly capture all possible contexts where it can be safely used; (2) composition of components is not limited to conventional linking, but is achieved by means of a set of powerful operators typical of mixin modules.

We present a translation from Fickle, a small object-oriented language allowing objects to change their class at runtime, into Java. The translation is provenly correct in the sense that it preserves the static and dynamic semantics. Moreover, it is compatible with separate compilation, since the translation of a Fickle class does not depend on the implementation of used classes. Based on the formal system, we have developed an implementation. The translation turned out to be a more subtle problem than we expected. In this article, we discuss four possible approaches we considered for the design of the translation and to justify our choice, we present formally the translation and proof of preservation of the static and dynamic semantics, and discuss the prototype implementation. Moreover, we outline an alternative translation based on generics that avoids most of the casts (but not all) needed in the previous translation. The language Fickle has undergone and is still undergoing several phases of development. In this article we are discussing the translation of FickleII.

In languages like C++, Java and C#, typechecking algorithms require methods to be annotated with their parameter and result types, which are either fixed or constrained by a bound. We show that, surprisingly enough, it is possible to infer the polymorphic type of a method where parameter and result types are left unspecified, as happens in most functional languages. These types intuitively capture the (less restrictive) requirements on arguments needed to safely apply the method. We formalize our ideas on a minimal Java subset, for which we define a type system with polymorphic types and prove its soundness. We then describe an algorithm for type inference and prove its soundness and completeness. A prototype implementing inference of polymorphic types is available.

Although the C-based interpreter of Python is reasonably fast, implementations on the CLI or the JVM platforms offers some advantages in terms of robustness and interoperability. Unfortunately, because the CLI and JVM are primarily designed to execute statically typed, object-oriented languages, most dynamic language implementations cannot use the native bytecodes for common operations like method calls and exception handling; as a result, they are not able to take full advantage of the power offered by the CLI and JVM. We describe a different approach that attempts to preserve the flexibility of Python, while still allowing for efficient execution. This is achieved by limiting the use of the more dynamic features of Python to an initial, bootstrapping phase. This phase is used to construct a final RPython (Restricted Python) program that is actually executed. RPython is a proper subset of Python, is statically typed, and does not allow dynamic modification of class or method definitions; however, it can still take advantage of Python features such as mixins and first-class methods and classes. This paper presents an overview of RPython, including its design and its translation to both CLI and JVM bytecode. We show how the bootstrapping phase can be used to implement advanced features, like extensible classes and generative programming. We also discuss what work remains before RPython is truly ready for general use, and compare the performance of RPython with that of other approaches.

We define a framework of components based on Java-like languages, where components are binary mixin modules. Basic components can be obtained from a collection of classes by compiling such classes in isolation; for allowing that, requirements in the form of type constraints are associated with each class. Requirements are specified by the user who, however, is assisted by the compiler which can generate missing constraints essential to guarantee type safety. Basic components can be composed together by using a set of expressive typed operators; thanks to soundness results, such a composition is always type safe. The framework is designed as a separate layer which can be instantiated on top of any Java-like language; a prototype implementation is available for a small Java subset. Besides safety, the approach achieves great flexibility in reusing components for two reasons: (1) type constraints generated for a single component exactly capture all possible contexts where it can be safely used; (2) composition of components is not limited to conventional linking, but is achieved by means of a set of powerful operators typical of mixin modules.

We present SmartJavaMod, a language of mixin modules supporting compositional compilation, and constructed on top of the Java language. More in detail, this means that basic modules are collections of Java classes which can be typechecked in isolation, inferring constraints on missing classes and allowing safe reuse of the module in as many contexts as possible. Furthermore, it is possible to write structured module expressions by means of a set of module operators, and a type system at the module level ensures type safety, in the sense that we can always reduce a module expression to a well-formed collection of Java classes. What we obtain is a module language which is extremely flexible and allows the encoding (without any need of enriching the core level, that is, the Java language) of a variety of constructs supporting software reuse and extensibility.

We define compositional compilation as the ability to typecheck source code fragments in isolation, generate corresponding binaries, and link together fragments whose mutual assumptions are satisfied, without reinspecting the code. Even though compositional compilation is a highly desirable feature, in Java-like languages it can hardly be achieved. This is due to the fact that the bytecode generated for a fragment (say, a class) is not uniquely determined by its source code, but also depends on the compilation context. We propose a way to obtain compositional compilation for Java, by introducing a polymorphic form of bytecode containing type variables (ranging over class names) and equipped with a set of constraints involving type variables. Thus, polymorphic bytecode provides a representation for all the (standard) bytecode that can be obtained by replacing type variables with classes satisfying the associated constraints. We illustrate our proposal by developing a typing and a linking algorithm. The typing algorithm compiles a class in isolation generating the corresponding polymorphic bytecode fragment and constraints on the classes it depends on. The linking algorithm takes a collection of polymorphic bytecode fragments, checks their mutual consistency, and possibly simplifies and specializes them. In particular, linking a self-contained collection of fragments either fails, or produces standard bytecode (the same as what would have been produced by standard compilation of all fragments).

We define compositional compilation as the ability to typecheck source code fragments in isolation, generate corresponding binaries, and link together fragments whose mutual assumptions are satisfied, without reinspecting the code. Even though compositional compilation is a highly desirable feature, in Java-like languages it can hardly be achieved. This is due to the fact that the bytecode generated for a fragment (say, a class) is not uniquely determined by its source code, but also depends on the compilation context. We propose a way to obtain compositional compilation for Java, by introducing a polymorphic form of bytecode containing type variables (ranging over class names) and equipped with a set of constraints involving type variables. Thus, polymorphic bytecode provides a representation for all the (standard) bytecode that can be obtained by replacing type variables with classes satisfying the associated constraints. We illustrate our proposal by developing a typing and a linking algorithm. The typing algorithm compiles a class in isolation generating the corresponding polymorphic bytecode fragment and constraints on the classes it depends on. The linking algorithm takes a collection of polymorphic bytecode fragments, checks their mutual consistency, and possibly simplifies and specializes them. In particular, linking a self-contained collection of fragments either fails, or produces standard bytecode (the same as what would have been produced by standard compilation of all fragments).

We define an algorithm for smarter recompilation of a small but significant Java-like language; such an algorithm is inspired by a type system previously defined by Ancona and Zucca. In comparison with all previous type systems for Java-like languages, this system enjoys the principal typings property, and is based on the two novel notions of local type assumption and entailment of type environments. The former allows the user to specify minimal requirements on the source fragments which need to be compiled in isolation, whereas the latter syntactically captures the concept of stronger type assumption. One of the most important practical advantages of this system is a better support for selective recompilation; indeed, it is possible to define an algorithm directly driven by the typing rules which is able to avoid the unnecessary recompilation steps which are usually performed by the Java compilers. The algorithm is smarter in the sense that it never forces useless recompilations, that is, recompilations which would generate the same binary fragment obtained from the previous compilation of the same source fragment. Finally, we show that the algorithm can actually speed up the overall recompilation process, since checking for recompilation is always strictly less expensive than recompiling the same fragment.

The contribution of the paper is twofold. First, we provide a general notion of type system supporting separate compilation and inter-checking, and a formal definition of soundess and completeness of inter-checking w.r.t. global compilation. These properties are important in practice since they allow selective recompilation. In particular, we show that they are guaranteed when the type system has principal typings and provides sound and complete entailment relation between type environments and types. The second contribution is more specific, and is an instantiation of the notion of type system previously defined for Featherweight Java [IgarashiEtAl99] with method overloading and field hiding. The aim is to show that it is possible to define type systems for Java-like languages, which, differently from those used by standard compilers, have principal typings, hence can be used as a basis for selective recompilation.

In this paper we present Jam, an extension of the Java language supporting mixins, that is, parametric heir classes. A mixin declaration in Jam is similar to a Java heir class declaration, except that it does not extend a fixed parent class, but simply specifies the set of fields and methods a generic parent should provide. In this way, the same mixin can be instantiated on many parent classes, producing different heirs, thus avoiding code duplication and largely improving modularity and reuse. Moreover, as happens for classes and interfaces, mixin names are reference types, and all the classes obtained by instantiating the same mixin are considered subtypes of the corresponding type, hence can be handled in a uniform way through the common interface. This possibility allows a programming style where different ingredients are “mixed” together in defining a class; this paradigm is somewhat similar to that based on multiple inheritance, but avoids its complication. The language has been designed with the main objective in mind to obtain, rather than a new theoretical language, a working and smooth extension of Java. That means, on the design side, that we have faced the challenging problem of integrating the Java overall principles and complex type system with this new notion; on the implementation side, that we have developed a Jam to Java translator which makes Jam sources executable on every Java Virtual Machine.

We define and implement a formal system supporting separate compilation for a small but significant Java-like language. This system is proved to be stronger than the standard compilation of both Java and C#, in the sense that it better supports software reuse by avoiding unnecessary recompilation steps after code modification which are usually performed by using the standard compilers. This is achieved by introducing the notion of local type assumption allowing the user to specify weaker requirements on the source fragments which need to be compiled in isolation. Another important property satisfied by our system is compositionality, which corresponds to the intuition that if a set of fragments can be separately compiled and such fragments are compatible, then it is possible to compile all the fragments together as a unique program and obtain the same result.

In this paper we present a simple calculus (called CJE) in order to fully investigate the exception mechanism of Java (in particular its interaction with inheritance). We first define a type system for the calculus, called FULL, directly driven by the Java Language Specification and prove its soundness; then, we show that this type system uses redundant types and we formally capture this fact by defining equivalence relations on types and by proving that the static semantics of CJE programs is preserved under these equivalences; furthermore, for each type we show that there exists the smallest equivalent type. Finally, we propose a simplification of the Java specification concerning throws clause which minimally affects the expressive power of the language.

We define a type system modeling true separate compilation for a small but significant Java subset, in the sense that a single class declaration can be intra-checked (following the Cardelli's terminology) and compiled providing a minimal set of type requirements on missing classes. These requirements are specified by a local type environment associated with each single class, while in the existing formal definitions of the Java type system classes are typed in a global type environment containing all the type information on a closed program. We also provide formal rules for static inter-checking and relate our approach with compilation of closed programs, by proving that we get the same results.

We define a formal notion, called compilation schema, allowing to specify different possibilities for performing the overall process of Java compilation, which includes type-checking of source fragments with generation of corresponding binary code, type-checking of binary fragments, extraction of type information from fragments and definition of dependencies among them. We consider three compilation schemata of interest for Java, that is, minimal, SDK and safe, which correspond to a minimal set of checks, the checks performed by the SDK implementation, and all the checks needed to prevent run-time linkage errors, respectively. In order to demonstrate our approach, we define a kernel model for Java separate compilation and execution, consisting in a small Java subset, and a simple corresponding binary language for which we provide an operational semantics including run-time verification. We define a safe compilation schema for this language and formally prove type safety.

We present a translation from Fickle (a Java-like language allowing objects that can change their class at run-time) into plain Java. The translation, which maps any Fickle class into a Java class, is driven by an invariant that relates the Fickle object to its Java counterpart. The translation, which is proven to preserve both the static and the dynamic semantics of the language, is an enhanced version of a previous proposal by the same authors.

We present JavaMod, a true module system constructed on top of a Java-like language. More in detail, this means that basic modules are collections of Java classes and specify in their interface the imported and exported classes with their types; furthermore, it is possible to write structured module expressions by means of a set of module operators and a type system at the module level ensures type safety. In designing such a type system, one has to face non trivial problems, notably the fact that a module M which extends an imported class C can be correctly combined only with modules exporting a class C which, besides providing the expected services, causes no interferences with its subclasses defined in M. What we obtain is a module language which is extremely flexible and allows to express (without any need of enriching the syntax of the core level, that is, the Java language), for instance, generic types as in Pizza and GJ, mixin classes (that is, subclasses parametric in the direct superclass) and mutually recursive class definitions split in independent modules.

Java supports separate type-checking in the sense that compilation can be invoked on a single source fragment, and this may enforce type-checking of other either source or binary fragments existing in the environment. However, the Java specification does not define precise rules on how this process should be performed, therefore the outcome of compilation may strongly depend on the particular compiler implementation. Furthermore, rules adopted by standard Java compilers, as SDK and Jikes, can produce binary fragments whose execution throws linking related errors. We introduce a simple framework which allows to formally express the process of separate compilation and the related formal notion of type safety. Moreover, we define, for a small subset of Java, a type system for separate compilation which we conjecture to be safe.

We present a translation from Fickle (a Java-like language allowing dynamic object re-classification, that is, objects that can change their class at run-time) into plain Java. The translation is proved to preserve static and dynamic semantics; moreover, it is shown to be effective, in the sense that the translation of a Fickle class does not depend on the implementation of used classes, hence can be done in a separate way, that is, without having their sources, exactly as it happens for Java compilation. The aim is to demonstrate that an extension of Java supporting dynamic object re-classification could be fully compatible with the existing Java environment.

In this paper we present a simple calculus (called CJE) in order to fully investigate the exception mechanism of Java, and in particular its interaction with inheritance, which turns out to be non trivial. Moreover, we show that the type system for the calculus directly driven by the Java Language Specification (called FULL) uses too many types, in the sense that there are different types which provide exactly the same information. Hence, we obtain from FULL a simplified type system called MIN where equivalent types have been identified. We show that this is useful both for type-checking optimization and for clarifying the static semantics of the language. The two type systems are proved to satisfy the subject reduction property.

Overloading allows several function definitions for the same name, distinguished primarily through different argument types; it is typically resolved at compile-time. Inheritance allows subclasses to define more special versions of the same function; it is typically resolved at run-time. Modern object-oriented languages incorporate both features, usually in a type-safe manner. However, the combination of these features sometimes turns out to have surprising, and even counterintuitive, effects. We discuss why we consider these effects inappropriate, and suggest alternatives. We explore the design space by isolating the main issues involved and analyzing their interplay and suggest a formal framework describing static overloading resolution and dynamic function selection, abstracting from other language features. We believe that our framework clarifies the thought process going on at language design level. We introduce a notion of soundness and completeness of an overloading resolution policy w.r.t. the underlying dynamic semantics, and a way of comparing the flexibility of different resolution policies. We apply these concepts to some non-trivial issues raised in concrete languages. We also argue that the semantics of overloading and inheritance is “clean” only if it can be understood through a copy semantics, whereby programs are transformed to equivalent programs without subclasses, and the effect of inheritance is obtained through copying.

In this paper we present Jam, an extension of the Java language supporting mixins, also called parametric heir classes. A mixin declaration in Jam is similar to a Java heir class declaration, apart that mixins do not extend a fixed parent class, but simply specify the set of fields and methods a generic parent should provide. In this way, the same mixin can be instantiated on many parent classes, producing different heir classes, thus avoiding code duplication and largely improving modularity and reuse. Moreover, as happens for classes and interfaces, mixin names are reference types, and all the classes obtained instantiating the same mixin are considered subtypes of the corresponding type, hence can be handled in a uniform way through the common interface. This possibility allows a programming style where different ingredients are "mixed" together in defining a class; this paradigm is partly similar to that based on multiple inheritance, but avoids its complication. The language has been designed with the main objective in mind to obtain, rather than a new theoretical language, a working and smooth extension of Java. That means, on the design side, that we have faced the challenging problem of integrating the Java overall principles and complex type system with this new notion; on the implementation side, that we have developed a Jam to Java translator which makes Jam sources executable on every Java Virtual Machine.

In this paper we present a simple calculus (called CJE) corresponding to a small functional fragment of Java supporting exceptions. We provide a reduction semantics for the calculus together with two equivalent type systems; the former corresponds to the standard specication and its formalization, whereas the latter can be considered an optimization of the former where only the minimal type information about classes/interfaces and methods are collected in order to type-check a program. The two type systems are proved to be equivalent and a subject reduction theorem is given.

The combination of overloading and inheritance in Java introduces questions about function selection, and makes some function calls ambiguous. We believe that the approach taken by Java designers is counterintuitive. We explore an alternative, and argue that it is more intuitive and agrees with the Java rules for the cases where Java considers the function calls unambiguous, but gives meaning to more calls than Java does.

We define an extension of CASL, the standard language for algebraic specification, with a late binding mechanism. More precisely, we introduce a special kind of functions called methods, for which, differently to what happens for usual functions, overloading resolution is delayed at evaluation time and not required to be conservative. The extension consists, at the semantic level, in the definition of an institution LB supporting late binding which is defined on top of the standard subsorted institution of CASL and, at the linguistic level, in the enrichment of the CASL language with appropriate constructs for dealing with methods.

We define a specification formalism (formally, an institution) which provides a notion of dynamic type (the type which is associated to a term by a particular evaluation) and late binding (the fact that the function version to be invoked in a function application depends on the dynamic type of one or more arguments). Hence, it constitutes a natural formal framework for modeling object-oriented and other dynamically-typed languages and a basis for adding to them a specification level. In this respect, the main novelty is the capability of writing axioms related to a given type which are not required to hold for subtypes, hence can be “overridden” in further refinements, thus lifting at the specification level the possibility of reusing code which is offered by the object-oriented approach.

In this thesis we present two formal frameworks for modeling modular languages. Following a modular approach, we separate the module and the core level of a modular language. On the linguistic side, this corresponds to define a kernel module language parametric in the underlying core language. On the semantic side, this corresponds to build a model part (in the sense of institutions), on top of a standard module framework. The standard module framework is a model part, too, satisfying some additional properties and intended as the formal counterpart of the core language. The first formal framework we propose deals with the notion of state, an essential component of modules in imperative languages. The second one is concerned with a notion of module, called mixin, which includes those of generic module and abstract class. In both cases, we present two canonical constructions yielding a formal framework where models denote modules with state and mixins, respectively, and we define a set of primitive operations over them.

We show that many different overriding operators present in programming languages can be expressed, adopting a mixin-based framework, in terms of three basic operators. In particular we propose two orthogonal classifications: strong (the overridden definition is canceled) or weak (the overridden definition still remains significant, as in Smalltalk's super feature), and preferential (priority to one of the two arguments) or general. We formalize the relation between all these versions. Our analysis and results are not bound to a particular language, since they are formulated within an algebraic framework for mixin modules which can be instantiated over different core languages.

We address the problem of providing a rigorous formal model for classes of objects and the variety of inheritance relations. Classes are modelled by a new structure, called d-oid, which corresponds to see objects as data with state. The approach we take is a rather abstract one and so we model representation independent configurations of an object system by algebras, object identities by so called tracking map, and method calls as transformations of algebras. Seeing classes as d-oids allows us to define a hierarchy of inheritance relations, modelled by relations between d-oids and corresponding to different liberty levels in redefining methods. The classification we present distinguish essentially three levels of inheritance: minimal, regular and conservative.