Smalltalk is an excellent programming language which does not have any static types; to declare a variable, you simply write its name down, and the compiler trusts that you will use it properly. Many people, including myself, prefer this style of programming. One cost of this approach, however, is that program text can be harder to decipher. Static types provide a kind of documentation that is not available in Smalltalk.
Unless, that is, one has a good type inferencer. Chuck is a project that aims to improve the readability of Smalltalk programs by using type inference. Type inference can find types in programs even when the program's author was not constrained by a type checker to begin with. The inferred types can then be presented to the user and to other static analysis tool such as compilers and dead code removers.
Type inference in Smalltalk-like languages has been studied since at least 1981, when Norihisa Suzuki published a type inference algorithm for Smalltalk-80. Chuck's algorithm DDP is unusual, however, in two ways: it is demand-driven and prunes subgoals. A demand-driven algorithm is architected around the notion of "goals", where each goal is either answered directly ("what is the type of 47?"), or via subgoals ("what is the type of x+y?"). The advantage of this approach is that, whenever too many goals are being studied, it is possible to "prune" some of the goals by giving them obvious but poor answers ("the type could be anything"); the analysis can then procede, and it may still find good answers to other questions. Pruning in this fashion does not appear possible in the competing approaches of abstract interpretation and of constraint solving; such approaches must completely solve any subproblems they generate.
To my knowledge, DDP is the first type inference algorithm that is effective on larger programs (100+ kloc) in Smalltalk-like languages, while still giving context-sensitive results.
In addition, the following peer-reviewed conference papers have been published about DDP and Chuck:
For full citation information on these documents, see lexspoon.bib.
ChuckDemo.zip is a pre-loaded Squeak image that lets you download Chuck and play with it immediately. To use it, you will also need to download a Squeak VM for your platform.
The source code of Chuck is available via the Chuck Project on SqueakMap and via the development package universe. Thus in Squeak, you can load it via the standard package loaders. The development version of the code is on SqueakSource.
If you find this project interesting, then the following might interest you as well: