Ph.D Thesis

Ph.D StudentZibin Yoav
SubjectEfficient Algorithms for the Runtime Environment of Object
Oriented Languages
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Joseph Gil


The object oriented (OO) paradigm has become the norm for software development. OO languages, such as C++, JAVA, EIFFEL, and SMALLTALK, are used in almost every software project. The OO programming style, and the languages that enable it, have acquired an aura of respectability. OO programming promotes reusability, extendibility, reliability, and portability. All these blessings come however at a cost of runtime efficiency. Better understanding of this cost, and finding ways to reduce it, were the subject of my thesis.

This thesis presents our contributions to the following three fundamental problems in the runtime environment of OO languages: subtyping tests, message dispatching (both single and multiple dispatching), and object layout. It is important to note that although the problems take variations in different languages, these variations are minor in the implementation of these languages. The results will therefore be of general interest, and applicable to many different languages.

Surprisingly, we use our message dispatching techniques in designing the best algorithm for deciding isomorphism of simple types, i.e., whether two non-recursive types using product- and function-type constructors, are isomorphic under the axioms of commutative and associative products, and currying and distributivity of functions over products. We show that this problem can be solved in O(n log2 n) time and O(n) space, where n is the input size. This result improves upon the O(n2 log n) time and O(n2) space bounds of the best previous algorithm. We also describe an O(n) time algorithm for the linear isomorphism problem, which does not include the distributive axiom, thereby improving upon the O(n log n) time of the best previous algorithm for this problem.

The above contributions were published in five conference papers, two of which were also accepted to a journal.