Jong-hoon (David) An
Avik Chaudhuri
Jeffrey S. Foster
Michael Hicks
Abstract
There have been several efforts to bring static type inference to object-oriented dynamic languages such as Ruby, Python, and Perl. In our experience, however, such type inference systems are extremely difficult to develop, because dynamic languages are typically complex, poorly specified, and include features, such as eval and reflection, that are hard to analyze.
In this paper, we introduce constraint-based dynamic type inference, a technique that infers static types based on dynamic program executions. In our approach, we wrap each run-time value to associate it with a type variable, and the wrapper generates constraints on this type variable when the wrapped value is used. This technique avoids many of the often overly conservative approximations of static tools, as constraints are generated based on how values are used during actual program runs. Using wrappers is also easy to implement, since we need only write a constraint resolution algorithm and a transformation to introduce the wrappers. The best part is that we can eat our cake, too: our algorithm will infer sound types as long as it observes every path through each method body---note that the number of such paths may be dramatically smaller than the number of paths through the program as a whole.
We have developed Rubydust, an implementation of our algorithm for Ruby. Rubydust takes advantage of Ruby's dynamic features to implement wrappers as a language library. We applied Rubydust to a number of small programs and found it to be both easy to use and useful: Rubydust discovered 1 real type error, and all other inferred types were correct and readable.
Supplemental Material
- Rahul Agarwal and Scott D. Stoller. Type Inference for Parameterized Race-Free Java. In VMCAI, 2004.Google Scholar
- O. Agesen, J. Palsberg, and M.I. Schwartzbach. Type Inference of SELF. ECOOP, 1993. Google ScholarDigital Library
- Jong-hoon (David) An, Avik Chaudhuri, and Jeffrey S. Foster. Static Typing for Ruby on Rails. In ASE, 2009.Google Scholar
- 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, 2005. Google ScholarDigital Library
- Shay Artzi, Adam Kiezun, David Glasser, and Michael D. Ernst. Combined static and dynamic mutability analysis. In ASE, 2007. Google ScholarDigital Library
- John Aycock. Aggressive Type Inference. In International Python Conference, 2000.Google Scholar
- Christoph Csallner, Nikolai Tillmann, and Yannis Smaragdakis. Dysy: dynamic symbolic execution for invariant inference. In ICSE, 2008. Google ScholarDigital Library
- Michael D. Ernst, Jeff H. Perkins, Philip J. Guo, Stephen McCamant, Carlos Pacheco, Matthew S. Tschantz, and Chen Xiao. The Daikon system for dynamic detection of likely invariants. Sci. Comput. Program., 69(1--3), 2007. Google ScholarDigital Library
- Michael Furr, Jong-hoon (David) An, and Jeffrey S. Foster. Profile-guided static typing for dynamic scripting languages. In OOPSLA, 2009. Google ScholarDigital Library
- Michael Furr, Jong-hoon (David) An, Jeffrey S. Foster, and Michael Hicks. The Ruby Intermediate Language. In Dynamic Language Symposium, 2009. Google ScholarDigital Library
- Michael Furr, Jong-hoon (David) An, Jeffrey S. Foster, and Michael Hicks. Static Type Inference for Ruby. In OOPS Track, SAC, 2009. 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
- Philip J. Guo, Jeff H. Perkins, Stephen McCamant, and Michael D. Ernst. Dynamic inference of abstract types. In ISSTA, 2006. Google ScholarDigital Library
- Yit Phang Khoo, Bor-Yuh Evan Chang, and Jeffrey S. Foster. Mixing type checking and symbolic execution. In PLDI, 2010. Google ScholarDigital Library
- Kristian Kristensen. Ecstatic -- Type Inference for Ruby Using the Cartesian Product Algorithm. Master's thesis, Aalborg University, 2007.Google Scholar
- Robin Milner. A Theory of Type Polymorphism in Programming. Journal of Computer and System Sciences, 17, 1978.Google Scholar
- Jason Morrison. Type Inference in Ruby. Google Summer of Code Project, 2006.Google Scholar
- Jeremy W. Nimmer and Michael D. Ernst. Invariant Inference for Static Checking: An Empirical Evaluation. In FSE, 2002. Google ScholarDigital Library
- Pascal Rapicault, Mireille Blay-Fornarino, Stéphane Ducasse, and Anne-Marie Dery. Dynamic type inference to support object-oriented reenginerring in Smalltalk. In ECOOP Workshops, 1998. Google ScholarDigital Library
- rcov. rcov: code coverage for ruby, 2010. http://eigenclass. org/hiki/rcov.Google Scholar
- James Rose, Nikhil Swamy, and Michael Hicks. Dynamic inference of polymorphic lock types. Sci. Comput. Program., 58(3), 2005. Google ScholarDigital Library
- Ruby Quiz, 2010. http://www.rubyquiz.com.Google Scholar
- Michael Salib. Starkiller: A Static Type Inferencer and Compiler for Python. Master's thesis, MIT, 2004.Google Scholar
- Jeremy G. Siek and Walid Taha. Gradual typing for functional languages. In Scheme and Functional Programming Workshop, 2006.Google Scholar
- Satish Thatte. Quasi-static typing. In POPL, 1990. Google ScholarDigital Library
- Peter Thiemann. Towards a type system for analyzing javascript programs. In ESOP, 2005. Google ScholarDigital Library
- Dave Thomas, Chad Fowler, and Andy Hunt. Programming Ruby: The Pragmatic Programmers' Guide. Pragmatic Bookshelf, 2004. Google ScholarDigital Library
- Sam Tobin-Hochstadt and Matthias Felleisen. The Design and Implementation of Typed Scheme. In POPL, 2008. Google ScholarDigital Library
- David A. Wheeler. Sloccount, August 2004. http://www. dwheeler.com/sloccount/.Google Scholar
- A. K. Wright and R. Cartwright. A practical soft type system for Scheme. ACM TOPLAS, 19(1), 1997. Google ScholarDigital Library
- Jinlin Yang, David Evans, Deepali Bhardwaj, Thirumalesh Bhat, and Manuvir Das. Perracotta: mining temporal API rules from imperfect traces. In ICSE, 2006. Google ScholarDigital Library
Index Terms
- Dynamic inference of static types for ruby
Recommendations
SimTyper: sound type inference for Ruby using type equality prediction
Many researchers have explored type inference for dynamic languages. However, traditional type inference computes most general types which, for complex type systems—which are often needed to type dynamic languages—can be verbose, complex, and difficult ...
Sound, heuristic type annotation inference for Ruby
DLS 2020: Proceedings of the 16th ACM SIGPLAN International Symposium on Dynamic LanguagesMany researchers have explored retrofitting static type systems to dynamic languages. This raises the question of how to add type annotations to code that was previously untyped. One obvious solution is type inference. However, in complex type systems, ...
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 ...
Comments