Abstract
Smalltalk is an object-oriented language designed and implemented by the Learning Research (Group of the Xerox Palo Alto Research Center [2, 5, 14]. Some features of this language are: abstract data classes, information inheritance by a superclass-subclass mechanism, message passing semantics, extremely late binding no type declarations, and automatic storage management. Experience has shown that large complex systems can be written in Smalltalk in quite a short period of time; it is also used to teach programming to children quite effectively. Object-oriented languages like Smalltalk have begun to be accepted as friendly languages for novice programmers on personal computers.
However, Smalltalk has some drawbacks, too. Smalltalk programs are inefficient compared with Lisp or Pascal Late binding is a major reason of this inefficiency; every time a procedure is called, its implementation in the current context has to be found.
Because of late binding, whether there is an implementation of a procedure call or not can only be found at run-time. This may be convenient in the early stages of system development; one can run a partially completed system, and when he discovers a run-time error caused by an unimplemented procedure, he can write the procedure body and proceed the computation from the point where the error was discovered. However, there is no way to guarantee that there will be no run-time errors. We found many "completed" systems which still had such run-time errors.
Another problem is that it is hard for a novice to read Smalltalk programs written by other people. The fact that there are no type declarations and the fact that the bindings are late are major causes of unreadability. All the Smalltalk procedures are so called generic procedures. Each procedure name is associated with several procedure bodies declared in different classes. Depending on the classes of the arguments of a procedure call different procedure bodies are invoked. Since the classes of the arguments may differ according to the context, it is impossible to statically predict the behavior of the procedure calls.
We observed that both inefficiency and unreadability are attributed to late binding; however, early binding can be effectively accomplished if we can tell the classes of the procedure arguments at compile time. In the long run probably Smalltalk needs to have "type" declarations---probably not rigid declarations of Pascal but rather in the form of hints to compilers and programmers. Even without changing the language it would be nice to have a tool that supplies "type" declarations to current Smalltalk or partially specified Smalltalk. This will also lead to efficient compilation.
We thus concluded that we need to introduce "types" to Smalltalk. The introduction of types is more promising in Smalltalk than in similarly declarationless language Lisp, since Smalltalk has a rich user-defined abstract classes. Therefore, the most straightforward approach to introduce types is to associate types of variables to classes that variables denote and to associate types of procedures to mappings from classes to classes. Since a variable may denote objects of different classes, we define the type of a variable to be a union of classes that the variable will ever denote.
The aim of this research is not to implement compilers for Smalltalk with type declarations. We intend to design tools to supply type declarations to current Smalltalk programs. Complete type determination is neither possible nor desirable; people do write Smalltalk programs that take advantage of late bindings. We are, therefore, interested in finding a relatively efficient method that can find types of expressions in a large number of cases.
The problem of statically assigning types to type-declarationless programs is called type-inference problem. We can find a number of work on type inference [3, 4, 7, 9, 11, 15]; these techniques are, however, either too restrictive or too inefficient for our purpose. The only technique implemented, proven to work for non-trivial cases, and used extensively was developed by Milner [7] to determine types for ML language of LCF. Even though ML language is much simpler than Smalltalk, the fact that there exists an efficient, versatile algorithm encouraged us to investigate whether we can extend the method.
The LCF type checker produces a set of equations from procedure declarations and solves them by unification [12], to obtain the types of the procedures; it can run in linear time due to a fast unification algorithm invented recently [10]. We extended Milner's method so that we can treat unions of types; in our method,we create a set of equations and inequalities and solve them by unification and a transitive closure algorithm. This technique is general and can be applied to other data-flow problems.
The advantage of Milner's method and our method is that it reduces the problems to purely mathematical domain so that we can apply various formula manipulation algorithms, without considering the execution order or side-effects. Another advantage is that these methods can handle functions with polymorphic types.
In section 2 we review earlier work on type inference. The brief introduction of the syntax and the semantics of Smalltalk is done in section 3. Then we introduce the "types" into Smalltalk in section 4. We discuss the first part of our algorithm, how to extend LCF type checking algorithm for liberal unions of types, in section 5. Then in section 6 the whole algorithm is presented. Section 7 is concerned with the implementation and experience.
Smalltalk has four major different versions of the language and implementations. The version we used for our experiments is Smalltalk-76.
