Abstract
Many popular scripting languages such as Ruby, Python, and Perl include highly dynamic language constructs, such as an eval method that evaluates a string as program text. While these constructs allow terse and expressive code, they have traditionally obstructed static analysis. In this paper we present PRuby, an extension to Diamondback Ruby (DRuby), a static type inference system for Ruby. PRuby augments DRuby with a novel dynamic analysis and transformation that allows us to precisely type uses of highly dynamic constructs. PRuby's analysis proceeds in three steps. First, we use run-time instrumentation to gather per-application profiles of dynamic feature usage. Next, we replace dynamic features with statically analyzable alternatives based on the profile. We also add instrumentation to safely handle cases when subsequent runs do not match the profile. Finally, we run DRuby's static type inference on the transformed code to enforce type safety.
We used PRuby to gather profiles for a benchmark suite of sample Ruby programs. We found that dynamic features are pervasive throughout the benchmarks and the libraries they include, but that most uses of these features are highly constrained and hence can be effectively profiled. Using the profiles to guide type inference, we found that DRuby can generally statically type our benchmarks modulo some refactoring, and we discovered several previously unknown type errors. These results suggest that profiling and transformation is a lightweight but highly effective approach to bring static typing to highly dynamic languages.
- M. Abadi, L. Cardelli, B. Pierce, and G. Plotkin. Dynamic typing in a statically typed language. ACM TOPLAS, 13 (2): 237--268, 1991. Google ScholarDigital Library
- Davide Ancona, Massimo Ancona, Antonio Cuni, and Nicholas Matsakis. RPython: Reconciling Dynamically and Statically Typed OO Languages. In DLS, 2007. Google ScholarDigital Library
- Christopher Anderson, Paola Giannini, and Sophia Drossopoulou. Towards Type Inference for JavaScript. In ECOOP, pages 428--452, 2005. Google ScholarDigital Library
- John Aycock. Aggressive Type Inference. In Proceedings of the 8th International Python Conference, pages 11--20, 2000.Google Scholar
- M.D. Bond, N. Nethercote, S.W. Kent, S.Z. Guyer, and K.S. McKinley. Tracking bad apples: reporting the origin of null and undefined value errors. In Proceedings of the 2007 OOPSLA conference, pages 405--422. ACM New York, NY, USA, 2007. Google ScholarDigital Library
- M. Braux and J. Noyé. Towards partially evaluating reflection in Java. In PEPM, pages 2--11, 2000. Google ScholarDigital Library
- Brett Cannon. Localized Type Inference of Atomic Types in Python. Master's thesis, California Polytechnic State University, San Luis Obispo, 2005.Google Scholar
- Robert Cartwright and Mike Fagan. Soft typing. In PLDI, pages 278--292, 1991. Google ScholarDigital Library
- Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach. Precise Analysis of String Expressions. In SAS, pages 1--18, 2003. Google ScholarDigital Library
- Ravi Chugh, Jeff Meister, Ranjit Jhala, and Sorin Lerner. Staged information flow for javascript. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, Dublin, Ireland, June 2009. To appear. Google ScholarDigital Library
- David Flanagan and Yukihiro Matsumoto. The Ruby Programming Language. O'Reilly Media, Inc, 2008. Google ScholarDigital Library
- Michael Furr, Jong-hoon (David) An, and Jeffrey S. Foster. Profile-guided static typing for dynamic scripting languages. Technical Report CS-TR-4935, University of Maryland, 2009a. http://www.cs.umd.edu/projects/PL/druby.Google ScholarDigital Library
- Michael Furr, Jong-hoon (David) An, Jeffrey S. Foster, and Michael Hicks. The Ruby Intermediate Language. In Dynamic Language Symposium, Orlando, Florida, October 2009b. Google ScholarDigital Library
- Michael Furr, Jong-hoon (David) An, Jeffrey S. Foster, and Michael Hicks. Static Type Inference for Ruby. In OOPS Track, SAC, 2009c. Google ScholarDigital Library
- Carl Gould, Zhendong Su, and Premkumar Devanbu. Static Checking of Dynamically Generated Queries in Database Applications. In ICSE, pages 645--654, 2004. Google ScholarDigital Library
- Justin O. Graver and Ralph E. Johnson. A type system for Smalltalk. In PLDI, pages 136--150, 1990. Google ScholarDigital Library
- J. Gronski, K. Knowles, A. Tomb, S.N. Freund, and C. Flanagan. Sage: Hybrid Checking for Flexible Specifications. Scheme and Functional Programming, 2006.Google Scholar
- Lars T Hansen. Evolutionary Programming and Gradual Typing in ECMAScript 4 (Tutorial), November 2007.Google Scholar
- D. Herman, A. Tomb, and C. Flanagan. Space-efficient gradual typing. Trends in Functional Programming, 2007.Google Scholar
- M. Hirzel, A. Diwan, and M. Hind. Pointer Analysis in the Presence of Dynamic Class Loading. In ECOOP, 2004.Google ScholarCross Ref
- Kristian Kristensen. Ecstatic - Type Inference for Ruby Using the Cartesian Product Algorithm. Master's thesis, Aalborg University, 2007.Google Scholar
- Benjamin Livshits, John Whaley, and Monica S. Lam. Reflection Analysis for Java. In ASPLS, 2005.Google Scholar
- I. Pechtchanski and V. Sarkar. Dynamic optimistic interprocedural analysis: a framework and an application. In OOPSLA, pages 195--210, 2001. Google ScholarDigital Library
- Michael Salib. Starkiller: A Static Type Inferencer and Compiler for Python. Master's thesis, MIT, 2004.Google Scholar
- Jason Sawin and Atanas Rountev. Improved static resolution of dynamic class loading in Java. In IEEE International Working Conference on Source Code Analysis and Manipulation, pages 143--154, 2007. Google ScholarDigital Library
- Jeremy Siek and Walid Taha. Gradual typing for objects. In ECOOP, pages 2--27, 2007. Google ScholarDigital Library
- Jeremy G. Siek and Walid Taha. Gradual typing for functional languages. In Scheme and Functional Programming Workshop, September 2006.Google Scholar
- V.C. Sreedhar, M. Burke, and J.D. Choi. A framework for interprocedural optimization in the presence of dynamic class loading. In PLDI, pages 196--207, 2000. Google ScholarDigital Library
- Strongtalk. Strongtalk, 2008. http://www.strongtalk.org/.Google Scholar
- Satish Thatte. Quasi-static typing. In POPL, pages 367--381, 1990. Google ScholarDigital Library
- Peter Thiemann. Towards partial evaluation of full scheme. In Reflection 96, pages 95--106, 1996.Google Scholar
- Peter Thiemann. Towards a type system for analyzing javascript programs. In ESOP, pages 408--422, 2005. Google ScholarDigital Library
- Dave Thomas, Chad Fowler, and Andy Hunt. Programming Ruby: The Pragmatic Programmers' Guide. Pragmatic Bookshelf, 2nd edition, 2004. Google ScholarDigital Library
- F. Tip, C. Laffra, P.F. Sweeney, and D. Streeter. Practical experience with an application extractor for Java. In OOPSLA, pages 292--305, 1999. Google ScholarDigital Library
- Sam Tobin-Hochstadt and Matthias Felleisen. The Design and Implementation of Typed Scheme. In POPL, pages 395--406, 2008. Google ScholarDigital Library
- David A. Wheeler. Sloccount, 2008. http://www.dwheeler.com/sloccount/.Google Scholar
- Roel Wuyts. RoelTyper, May 2007. http://decomp.ulb.ac.be/roelwuyts/smalltalk/roeltyper/.Google Scholar
Index Terms
- Profile-guided static typing for dynamic scripting languages
Recommendations
Static type inference for Ruby
SAC '09: Proceedings of the 2009 ACM symposium on Applied ComputingMany general-purpose, object-oriented scripting languages are dynamically typed, which provides flexibility but leaves the programmer without the benefits of static typing, including early error detection and the documentation provided by type ...
Profile-guided static typing for dynamic scripting languages
OOPSLA '09: Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applicationsMany popular scripting languages such as Ruby, Python, and Perl include highly dynamic language constructs, such as an eval method that evaluates a string as program text. While these constructs allow terse and expressive code, they have traditionally ...
Just-in-time static type checking for dynamic languages
PLDI '16Dynamic languages such as Ruby, Python, and JavaScript have many compelling benefits, but the lack of static types means subtle errors can remain latent in code for a long time. While many researchers have developed various systems to bring some of the ...
Comments