Ph.D Thesis | |

Ph.D Student | Zibin Yoav |
---|---|

Subject | Efficient Algorithms for the Runtime Environment of Object Oriented Languages |

Department | Department 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 *log^{2}
*n*) time and *O*(*n*) space, where *n *is the input size. This result improves upon the *O*(*n*^{2}
log *n*) time and *O*(*n*^{2}) 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.