|
Michele Bugliesi and Santiago M. Pericas-Geertsen
Type inference for variant object types
Inform. & Comput., 2000
Existing type systems for object calculi are based
on invariant subtyping. Subtyping invariance is
required for soundness of static typing in the
presence of method overrides, but it is often in the
way of the expressive power of the type
system. Flexibility of static typing can be
recovered in different ways: in first-order systems,
by the adoption of object types with
variance annotations, in second-order
systems by resorting to Self types. Type
inference is known to be P-complete for first-order
systems of finite and recursive object types, and
NP-complete for a restricted version of Self
types. The complexity of type inference for systems
with variance annotations is yet unknown. This paper
presents a new object type system based on the
notion of Split types, a form of object
types where every method is assigned two types,
namely, an update type and a select type. The
subtyping relation that arises for Split types is
variant and, as a result, subtyping can be
performed both in width and in
depth. The new type system generalizes all
the existing first-order type systems for objects,
including systems based on variance
annotations. Interestingly, the additional
expressive power does not affect the complexity of
the type inference problem, as we show by presenting
an O(n^3) inference algorithm.
[ bib |
.ps |
.pdf ]
Back
This file has been generated by
bibtex2html 1.61
Copyright notice: The documents contained
in these pages are included by the contributing authors as a means to
ensure timely dissemination of scholarly and technical work on a
non-commercial basis. Copyright and all rights therein are maintained
by the authors or by other copyright holders, notwithstanding that
they have offered their works here electronically. It is understood that all persons copying this information will
adhere to the terms and constraints invoked by each author's
copyright. These works
may not be reposted without the explicit permission of the copyright
holder.
If you experience problems downloading any of the files above,
it is most likely because your browser does not handle compressed
files correctly.
In particular, Netscape might save the file in the compressed
gz-format with extension .ps or
.pdf (indicating postscript or PDF, resp.). You can work around this by saving the file,
renaming it to .ps.gz or .pdf.gz, and then
uncrompress it.
|
