Thesis avail: Concrete type inference: delivering OO applications

I am pleased to announce that my dissertation,


      "Concrete Type Inference: Delivering Object-Oriented Applications"


is now available on the www: http://self.smli.com/~agesen/
(abstract included below).


The dissertation will be printed as a Sun Microsystems Labs technical
report so if you prefer a (nicely) bound and free hardcopy over the
PostScript file, please send me your address and I will mail you the
technical report as soon as it is available (2-3 weeks).


Ole Agesen, agesen@cs.stanford.edu
----------------------------------------------------------------------------
Concrete Type Inference: Delivering Object-Oriented Applications


Ole Agesen
agesen@cs.stanford.edu
Ph.D. thesis
Stanford University
December 1995


Abstract:


Types can range from concrete, describing implementations of objects,
to abstract, describing interfaces or other properties of objects.
Object-oriented languages exploit this distinction to allow the same
code to be reused with objects of varying forms. This polymorphism
permits the use of objects with different concrete types, as long as
they have the abstract type required by the context. For example,
list-based and array-based stacks have different concrete types, but
can be interchanged since they both implement the abstract type stack.
Polymorphism adds expressive power, but sacrifices manifest concrete
types in programs (even in statically-typed languages). In turn,
application delivery suffers: lacking concrete type information, it is
impossible to compile as efficiently, to check as thoroughly, and to
eliminate dead code as effectively.


We have designed, implemented, and evaluated an algorithm, the
cartesian product algorithm, that can infer concrete types of
object-oriented programs. It applies the cartesian product to break the
analysis of each polymorphic send into a case analysis; each case
represents a monomorphic combination of actual arguments and can be
analyzed precisely. The cartesian product algorithm improves precision
and efficiency over previous algorithms and deals directly with
inheritance, rather than relying on a preprocessor to expand it away.
Our implementation handles most of the dynamically-typed Self language,
including dynamically-dispatched messages, dynamic and multiple
inheritance, lexically-scoped blocks, and non-local returns, although
it supports the reflective features of Self only partially.


Using the inferred concrete types, a compiler can statically bind and
inline message sends, a browser can follow control-flow through message
sends, an extractor can identify the essential objects for an
application and discard the rest, and a checker can statically
guarantee the absence of message-not-understood errors. Collaborating
with other researchers, we have implemented proof-of-concept versions
of these type-based application delivery tools.


Measurements indicate that type inference performs well. For example,
on a 167 MHz UltraSPARC our type inferencer, written in Self, can
analyze the DeltaBlue constraint solver in 10 seconds (DeltaBlue
consists of 500 lines of source code and uses an additional 900 lines
from libraries). Using the inferred types, our extractor, also written
in Self, takes 4 seconds to produce a shrink-wrapped DeltaBlue
application. The shrink-wrapped application comprises 350 Kb, a 96%
size reduction over the original 10 Mb image. Moreover, using the
inferred types, Hoelzle's Self compiler can compile statically and still
produce native code of quality comparable to the state-of-the-art code
that it generates in its normal dynamic compilation mode. Thus,
concrete type inference enables delivery of object-oriented applications.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.