Type checking and type inference for object-oriented programming languages
Graver, Justin Owen
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/22894
Description
Title
Type checking and type inference for object-oriented programming languages
Author(s)
Graver, Justin Owen
Issue Date
1989
Doctoral Committee Chair(s)
Johnson, Ralph E.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
