Files in this item



application/pdf9010868.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


Title:Type checking and type inference for object-oriented programming languages
Author(s):Graver, Justin Owen
Doctoral Committee Chair(s):Johnson, Ralph E.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:Type systems for object-oriented programming languages have been studied a great deal over the past few years. Since Smalltalk was one of the earliest object-oriented languages, it is not surprising that there have been several attempts to provide a type system for it. Unfortunately, none of the attempts have been completely successful. In particular, none of the proposed type systems are both type-safe and capable of type-checking most common Smalltalk programs. Smalltalk violates many of the assumptions on which most object-oriented type systems are based, and a successful type system for Smalltalk is necessarily different from those for other languages.
We have designed a new type system for Smalltalk. The biggest difference between our type system and others is that most type systems for object-oriented programming languages equate classes with types and subclassing with subtyping. In our type system, types are based on classes (i.e. each class defines a type or a family of types) but subclassing has no relationship to subtyping. This is because Smalltalk classes inherit implementation and not specification.
Our type system uses discriminated union types and signature types to describe inclusion polymorphism and describes functional polymorphism (sometimes called parametric polymorphism) using bounded universal quantification and parameterized types. It handles side-effects by basing the definition of the subtype relation on equality of parameterized types. It is type-safe, i.e. it prevents an object from receiving a message it does not understand.
We describe an inter-procedural type-inference algorithm for the type system. Type-inference is important because Smalltalk programmers are used to a typeless language. We wish to retain as much of the "look and feel" of Smalltalk as is possible. The type-inference algorithm computes the general type of a method based on its definition and computes a specific type for a method at each call-site based on site-specific type information.
Because the type system uses class information, it can be used for optimization. Specifically, if methods can be bound to message sends at compile-time then aggressive in-line substitution and inter-procedural optimization can be performed. It has been implemented as part of the TS (Typed Smalltalk) optimizing compiler.
Issue Date:1989
Rights Information:Copyright 1989 Graver, Justin Owen
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9010868
OCLC Identifier:(UMI)AAI9010868

This item appears in the following Collection(s)

Item Statistics