Measuring polymorphism in python programs

ABSTRACT

Following the increased popularity of dynamic languages and their increased use in critical software, there have been many proposals to retrofit static type system to these languages to improve possibilities to catch bugs and improve performance. A key question for any type system is whether the types should be structural, for more expressiveness, or nominal, to carry more meaning for the programmer. For retrofitted type systems, it seems the current trend is using structural types. This paper attempts to answer the question to what extent this extra expressiveness is needed, and how the possible polymorphism in dynamic code is used in practise. We study polymorphism in 36 real-world open source Python programs and approximate to what extent nominal and structural types could be used to type these programs. The study is based on collecting traces from multiple runs of the programs and analysing the polymorphic degrees of targets at more than 7 million call-sites. Our results show that while polymorphism is used in all programs, the programs are to a great extent monomorphic. The polymorphism found is evenly distributed across libraries and program-specific code and occur both during program start-up and normal execution. Most programs contain a few ``megamorphic'' call-sites where receiver types vary widely. The non-monomorphic parts of the programs can to some extent be typed with nominal or structural types, but none of the approaches can type entire programs.

References

1. O. Agesen, “The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism”, Proc. ECOOP’95, pp 2–26, 1995.
2. B. ˚ Akerblom, J. Stendahl, M. Tumlin and T. Wrigstad, “Tracing Dynamic Features in Python Programs”, Proc. MSR’14, 2014.
3. J.D. An, A. Chaudhuri, J.S. Foster, and M. Hicks, “Dynamic inference of static types for Ruby”, In POPL’11, pp 459–472, 2011.
4. D. Ancona, M. Ancona, A. Cuni, and N. Matsakis. “RPython: Reconciling Dynamically and Statically Typed OO Languages”, In DLS’07, 2007.
5. J. Aycock, “Aggressive Type Inference”, pp 11–20, Proc. of the 8th International Python Conference, 2000.
6. G. Bracha and D. Griswold, “Strongtalk: Typechecking Smalltalk in a Production Environment”, In Proc. OOPSLA’93, pp. 215–230, 1993.
7. F. Brito e Abreu, “The MOOD Metrics Set,” Proc. ECOOP’95 Workshop on Metrics, 1995.
8. O. Calla´u, R. Robbes, É. Tanter, and D. Röthlisberger, “How Developers Use the Dynamic Features of Programming Languages: The Case of Smalltalk”, In MSR’11, 2011.
9. B. Cannon, “Localized Type Inference of Atomic Types in Python”, Master Thesis, California Polytechnic State University, San Luis Obispo, 2005.
10. L. Cardelli, and P. Wegner, “On understanding types, data abstraction, and polymorphism”, ACM Computing Surveys Volume 17, pp 471-222, 1985.
11. R. Chugh, D. Herman, and R. Jhala, “Dependent Types for JavaScript”, In SIGPLAN Not., Vol 47, No. 10 Oct 2012.
12. L. P. Deutsch and A. M. Schiffman, “Efficient Implementation of the Smalltalk-80 System”, In POPL 1984.
13. L. Damas and R. Milner, “Principal Type-schemes for Functional Programs”, In POPL’82, pp. 207–212, 1982.
14. Facebook, Inc., “Specification for Hack”, Facebook, Inc., https://github.com/hhvm/hack-langspec, 2015.
15. M. Furr, J.D. An, J.S. Foster, and M. Hicks, “Static type inference for Ruby”, In the 2009 ACM Symposium on Applied Computing, 2009.
16. J. O. Graver and R. E. Johnson, “A Type System for Smalltalk”, In Proc. POPL’90, pp. 136–150, 1990.
17. B. Hackett and S. Guo, “Fast and Precise Hybrid Type Inference for JavaScript”, In PLDI’12, pp. 239–250, 2012.
18. P. Heidegger and P. Thiemann, “Recency types for analyzing scripting languages”, In ECOOP’10, pp. 200–224, 2010.
19. A. Holkner and J. Harland, “Evaluating the Dynamic Behaviour of Python Applications”, In ACSC’09, pp. 19-28, 2009.
20. U. Hölzle and C. Chambers and D. Ungar, “Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches”, In ECOOP ’91, LNCS 512, July, 1991.
21. S. Karabuk and F.H. Grant, “A common medium for programming operations-research models”. IEEE Software, 24(5):39-47, 2007.
22. D. E. Knuth: “An Empirical Study of FORTRAN Programs. Software”, Practice and Experience, 1(2): 105-133, 1971.
23. A. Lamaison, “Inferring Useful Static Types for Duck Typed Languages”, Ph.D. Thesis, Imperial College, London, U.K., 2012.
24. S.Lebresne, G.Richards, J. Östlund, T.Wrigstad, J.Vitek, “Understanding the dynamics of JavaScript”, In Script to Program Evolution, 2009.
25. J. McCauley. “About POX”. 2013. http://www.noxrepo.org/pox/about-pox/
26. J. Palsberg and M. I. Schwartzbach, “Object-Oriented Type Inference”, In OOPSLA’91, pp. 146–161, 1991.
27. G. Richards, S. Lebresne, B. Burg and J. Vitek, “An Analysis of the Dynamic Behavior of JavaScript Programs”, In PLDI’10, 2010.
28. G. van Rossum and F.L. Drake, “PYTHON 2.6 Reference Manual”, CreateSpace, Paramount, CA, 2009.
29. M. Salib, “Faster than C: Static type inference with Starkiller”, In PyCon Proceedings, Washington DC, 2004.
30. Securities and Exchange Commission. Release Nos. 33-9117; 34-61858; File No. S7-08-10. 2010. http://www.sec.gov/rules/proposed/2010/33-9117.pdf
31. J. Siek, and W. Taha, “Gradual Typing for Objects”, in Proc. ECOOP’07, Berlin, Germany, July 2007.
32. SourceForge, http://sourceforge.net/.
33. C. Strachey, “Fundamental Concepts in Programming Languages”, in Higher Order Symbol. Comput., pp. 11–49, 2000.
34. N. Suzuki, “Inferring types in smalltalk”, in Proceedings POPL’81, pp. 187–199, New York, USA, 1981.
35. P. Thiemann, “Towards a type system for analyzing JavaScript programs”, in Proceedings of ESOP’05, pp. 408–422, 2005.
36. S. Tobin-Hochstadt and M. Felleisen, “Interlanguage migration: from scripts to programs”, in DLS’06, 2006.
37. L. Tratt, “Dynamically Typed Languages”, Advances in Computers 77. Vol, pp. 149-184, ed. Marvin V. Zelkowitz, 2009.

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features