Augmenting Type Inference with Lightweight Heuristics

Nevena Milojković. Augmenting Type Inference with Lightweight Heuristics. PhD thesis, University of Bern, June 2017. Details.


Static type information facilitates program comprehension and analysis. Yet, such information is absent in dynamically-typed languages, and that increases the time needed for software maintenance. Type inference algorithms may provide type information to developers, but in order to be fast and assist in development phase, they sacrifice the precision for speed. One of the biggest obstacles for their precision is polymorphism presence. In this thesis we first analyse the prevalence of polymorphism in object-oriented software, to assess the criticality it imposes on simple type inference. We find that polymorphism is omnipresent in object-oriented code, and that static analysis in dynamically-typed languages is also hampered by the usage of cross-hierarchy polymorphism, i.e., duck typing. As this big obstacle for static code analysis cannot be bypassed, we propose the need for lightweight heuristics to tackle the problem of imprecision of simple type inference algorithms. Four lightweight heuristics are employed to improve the performance of two simple and fast type inference approaches. These heuristics are founded on the source code and run-time information that are easy to collect without interrupting the workflow of a developer. The heuristics are evaluated and compared with the underlying algorithms based on their inference time and precision. All of them show a significant improvement when compared to the basic algorithm. They introduce a negligible overhead on the inference time, thus we deem them usable during regular coding tasks.

Posted by scg at 5 July 2017, 6:15 pm link
Last changed by admin on 21 April 2009