Michael Hicks

University of Maryland

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 talk, I will present constraint-based dynamic type inference, a technique that infers static types based on dynamic program executions. In this 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: our algorithm will infer sound types as long as it observes every path through each method body---note that the total 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.


This is joint work with Jeff Foster, Avik Chaudhuri, and David An (done while all were at the University of Maryland, College Park).



Michael W. Hicks is an associate professor in the Computer Science department and UMIACS at the University of Maryland, College Park.

His research focuses on using programming languages and analyses to improve the security, reliability, and availability of software.

Noteworthy among his research accomplishments is the development of analysis and compilation tools for enabling software to be safely updated while it runs. He has explored the design of new programming languages and analysis tools for automatically discovering or remediating software flaws and security vulnerabilities.  He is also interested in human-computer interaction, particularly as it relates to the use of software tools, and in distributed systems design and evaluation, particularly when adaptivity and security are system goals.


B17 Upson Hall

Thursday, October 13, 2011

Refreshments at 3:45pm in the Upson 4th Floor Atrium


Computer Science


Spring 2011


Dynamic Inference

of Static Types for Ruby