Demand-driven type inference with subgoal pruning: Trading precision for scalability

Highly dynamic languages like Smalltalk do not have much static type information immediately available before the program runs. Static types can still be inferred by analysis tools, but historically, such analysis is only effective if context sensitivity is abandoned or if focus is restricted to smaller programs with only tens of thousands of lines of code. This paper presents a new type inference algorithm, DDP, that is effective on larger programs with hun-dreds of thousands of lines of code, and that integrates elegantly with integrated development environments. The approach of the algorithm borrows from the field of knowledge-based systems: it is a demand-driven algorithm that sometimes prunes subgoals. The algorithm is formally described, proven correct, and im-plemented. Experimental results show that the inferred types are usefully precise. A complete program understanding application, Chuck, has been developed that uses DDP type inferences. This work contributes the DDP algorithm itself, a semantics of Smalltalk, a new general approach for analysis algorithms, and experimental analysis of DDP including determination of useful parameter settings. It also contributes an implementation of DDP, a general analysis framework for Smalltalk, and a complete end-user application that uses DDP