Fast type reconstruction for dynamically typed programming languages

Type inference and type reconstruction derive static types for pro-gram elements that have no static type associated with them. They have a wide range of usage, such as helping to eliminate the bur-den of manually specifying types, verifying whether a program is type-safe, helping to produce more optimized code or helping to understand programs. While type inference and type reconstruction is an active field of research, most existing techniques are interested foremost in the precision of their approaches, at the expense of exe-cution speed. As a result, existing approaches are not suited to give direct feedback in development environments, where interactivity dictates very fast approaches. This paper presents a type recon-struction algorithm for variables that is extremely fast (in the order of milliseconds) and reasonably precise (75 percent). The system is implemented as a byte-code evaluator in several Smalltalk envi-ronments, and its execution speed and precision are validated on a number of concrete case studies