Concrete Type Inference for Squeak


- Summary:

In this work we describe the design and implementation of a type inference
engine that is able to precisely deduce concrete types for some Squeak
expressions. The inference is done by performing an abstract interpretation
over the domain of concrete types; in other words, we simulate the execution
of a program using concrete types instead of regular values. This idea is
taken from the work done in Self by Ole Agesen, where he presents type
inference as a combined data and control flow problem. We embrace the
analogy between run-time and inference-time as our major guideline, trying
to emulate in inference time what really happens in runtime. We did not only
use this analogy to explain how we solved different problems, but we also
reflect it in the design and implementation of our engine (you will see
classes like TiInterpreter, TiCompiler, TiPrimitive, TiClass, etc).


- Now some details:

What is a concrete type?

The concrete type of an object is made up by its class and the concrete
types of its instance variables. For example:

    1 type = <SmallInteger>
    'hello' type = <String>
    (1.0 at 1.0) type = <Point x: <Float> y: <Float>>
    (1 at 1 corner: 100 at 100) type = <Rectangle origin: <Point x: <SmallInteger>
y: <SmallInteger>> corner: <Point x: <SmallInteger> y: <SmallInteger>>>

[Small Exercise: With this definition, what is the type of Smalltalk (the
system dictionary)? And the type of the class Point?]

Obtaining the concrete type of an object is not big deal... after all, you
*have* the object. The interesting part comes when you want to know the
concrete type of an arbitrary expression (a variable, a message send, etc).
Please note that an expression does not have a concrete type but a *set* of
concrete types. Each of the elements of this set comes from a different
execution path. For example, the type of the expression #(1.0 'two') at:
anInteger is {<Float> <String>} (assuming the variable anInteger has type
<SmallInteger> or <LargePositiveInteger>).


- If you are really interested:

If you want to find out more about this engine, you can download the english
copy of my thesis from
http://typeinference.swiki.net/.uploads/TiThesis-1.pdf.  It is a translation
from the spanish original done in record time by my advisor Leandro Caniglia
(thanks Leandro!!). You can also download a demo image for Squeak 2.8 from
http://typeinference.swiki.net/.uploads/TiDemoImage.zip or the basic change
sets from http://typeinference.swiki.net/.uploads/TiEngineChangeSets.zip.
These change sets should work on the last Squeak releases (from 2.5 to
3.1alpha).

I will also present this work at ESUG 2001 and its future directions at the
Doctoral Symposium. I would really like to continue this work. Thanks to
the guys from the Software Composition Group (especially Stephane Ducasse)
this might come true. Thanks Stef for all your support!!

Hope to see you at ESUG!!

--
Francisco Garau