Type Inference in a Declarationless, Object-Oriented Language

Citation

Holstege, Eric J. (1982) Type Inference in a Declarationless, Object-Oriented Language. Master's thesis, California Institute of Technology. doi:10.7907/sa4t-bn94. https://resolver.caltech.edu/CaltechTHESIS:04112012-080413185

Abstract

In recent years, two developments in the design of programming languages have yielded significant improvements in a number of areas from the standard FBAPP programming model. These are the object-oriented paradigm, and variable polymorphism.

The object-oriented programming model allows the specification, hence restriction of the operations allowed on a data structure, something not possible with the more traditional PASCAL-style record structuring. This ability to encapsulate data from the outside world gives a greater security and error avoidance in very large software projects involving many programmers.

In addition, the object-oriented style is conceptually easy to program in, providing a useful framework for the subdivision of large problems into manageable pieces. This property is essential for the rapid and reliable implementation of large software systems.

Variable polymorphism refers to the ability of variables to change types at runtime. This is in contradistinction to typelessness (as in BLISS) where variables have no types associated with them. In most common languages, the programmer must declare the types of all the variables he uses; these types are then static throughout the execution of the program. Declarations allow the compiler to produce efficient code and to identify errors whose detection must other-wise be deferred until runtime; however, they sacrifices a good deal of the generality which is possible with less stringent variable binding schemes. On the other hand, languages which don't require declarations, and which allow variables to change types, such as SNOBOL and LISP, provide this generality by virtue of their extremely late binding, but thereby sacrifice efficiency.

SMALLTALK is perhaps the purest language which embodies both object-orientedness and declarationlessness. Unfortunately, these two features, while of great benefit in increasing programmer productivity and program reliability, suffer heavily from the point of view of runtime efficiency.

The project is to investigate ways to obtain the undeniable advantages of polymorphism and object-orientedness, without sacrificing runtime efficiency. More specifically, the goal is to build a compiler for a dialect of SMALLTALK for the VAX under UNIX (Berkeley 4.1bsd), which incorporates data-flow type inference algorithms enabling it to produce executable programs of an efficiency comparable to that of programs produced by compilers for more traditional but less powerful languages.

The optimization methods are described, test results are examined, and indications of future directions are given.

Thesis Files