Type inference for Python programming language

Abstract

The article presents type inference for programs written in Python programming language. At first, type inference algorithms for parametric polymorphism that were described in the scientific literature are reviewed. The algorithms evolved from “basic” algorithm (also known as Palsberg — Schwartzbach algorithm) to Cartesian product algorithm (CPA). It was shown that CPA is both precise and efficient, however it has to be modified to be used on Python code. Afterwards, we present a new algorithm (a modification of CPA) for Python. It is shown how type inference module using the new algorithm analyses various Python language structures: constants (literals), basic Python collections, variable names, assignments, function and class definitions, attribute and index expressions. It is also shown how the algorithm deals with external (non-Python) functions using special annotations that specify output types depending on input types of the function. Afterwards, the results of work on the prototype (module that implements described type inference algorithm) are presented. The paper is concluded by an overview of possible future work directions such as generating a defect trace, i.e. description that specifies how expression got its incorrect types.

Keywords

• python
• вывод типов
• динамическая типизация данных
• статический анализ
• обнаружение дефектов