On the determination of extended classes and some other problems in Java programming language

This thesis is a part of a more general work concerning the problem of identifier binding in Java. Java is concerned here as most general of languages admitting both inheritance and inner classes. The problem of identifier binding consist in assigning the proper meaning to the occurrences of identifiers either at compile time or at run time. At the compile time we distinguish between defining and applied occurrences. The meaning of a defining occurrence of an identifier is the definition which the identifier is connected with. Each applied occurrence of an identifier must be bound to the proper defining occurrence. If we restrict our problem to the variable identifiers then at the compile time we will be interested in types of these variables. But at runtime we will be interested first of all in the location of the variable in the memory, and in most cases in the value of the variable. Since a type of the variable can be read from the declaration of this variable we can say that at compile time each variable is bound to its declaration while at runtime each variable is bound to the location in memory, which was reserved specially for this variable. Now consider class identifiers. During compilation we are interested in binding each applied occurrence of class identifier to the declaration of the corresponding class. Then during runtime, while creating an object of a class K, we are looking for an environment which will be used for binding the nonlocal variables occurrences within methods of the class K. Unexpectedly it turned out that the problem of binding class identifiers is especially difficult during the compilation of a program. The source of the difficulty is the fact that in Java the extended class may be denoted not only by stand alone class identifier but also by qualified type, which is a sequence of class identifiers separated by dots. We must deal here with the mutually recursive definition of binding. Binding of qualified types uses the inheritance function, while the definition of this function uses the binding of qualified type. The problem reduces to inventing the proper order of computing of the inheritance function as it will be shown in sections 3.1 and 4.1. The additional problems are checking of well-formedness of a program and the detection and correction of eventual errors. The structure of the thesis is as follows. The first chapter “Introduction” exposes the problem through a series of examples. The next chapter formulates the problem of identification of direct superclass in the language of a graph of classes of a given program. Chapter 3 presents a non-deterministic algorithm and the proof of correctness. In the subsequent chapter a deterministic algorithm is presented and analyzed. Chapter 5 analyzes earlier work on the problem and in particular the work of A.Igarashi and B.Pierce. The structure of the chapter is as follows: The section 5.2 presents the calculus of Igarashi and Pierce. Examples are given showing that the calculus is inconsistent. We are giving a simple remedy to it. In the section 5.3 we translate the inference rules of the IPET calculus in such a way that the phrase "the meaning of the type X in the environment P is the class T" is now expressed by the formula bind(X in P) = T and we show that the function bind calculated by the algorithm of the sectiion 3.1 is a model of the IPET calculus. Next section 5.4 shows that there is another concept Bind of binding function and that Bind is modeling the IPET calculus as well. In the section 5.5 we show that the intersection of two models needs not be a model. In this way one should abandon the hope that by adding the, metatheoretic, phrase, "take the least model" of the models of IPET calculus the task of identifying the direct superclass of classes of a Java program may be completed. The last chapter exposes the application of the results obtained above during compilation and latter during the execution of programs.