Preview

Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS)

Advanced search

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.

About the Author

I. E. Bronshteyn
ISP RAS, Moscow
Russian Federation


References

1. V. Savitskij, D. Sidorov. Inkremental'nyj analiz iskhodnogo koda na yazykakh C/C++ [Incremental source code analysis for C/C++ languages]. Trudy ISP RАN [The Proceedings of ISP RAS], 2012, vol. 22, pp. 119—129 (in Russian).

2. TIOBE Programming Community Index for April 2013. http://tinyurl.com/cgjbmjc

3. Gramps Bug Report 005023.

4. http://www.gramps-project.org/bugs/view.php?id=5023

5. O. Agesen. The Cartesian Product Algorithm. ECOOP’95 Proceedings of the 9th European Conference on Object-Oriented Programming (1995).

6. J. Palsberg, M. Schwartzbach. Object-Oriented Type Inference. In OOPSLA’91 Object-Oriented Programming Systems, Languages and Applications, pp. 146—161, Phoenix, Arizona, Oct. 1991.

7. M. Salib. Starkiller: a static type inferencer and compiler for Python. The Master of Engineering degree thesis. Massachusetts Institute of Technology, 2004.

8. B. Alpern, M. Wegman, K. Zadeck. Detecting equality of values in programs. In Conference Record of the 15th ACM Symposium on Principles of Programming Languages (Jan. 1988), ACM, New York, pp. 1—11.

9. Abstract Syntax Trees: ast module. http://docs.python.org/2/library/ast.html


Review

For citations:


Bronshteyn I.E. Type inference for Python programming language. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2013;24. (In Russ.)



Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)