Jason Morrison SoC 2006: Type Inference in Ruby

Blogging the Summer of Code

May 30, 2006 at 08:13pm

Hola, folks!

This is where I will talk about my participation with the Google Summer of Code program, working on Code Completion with Type Inference for Ruby Development Tools.

I’ll be blogging my plans and development as well as interesting relevant articles that I find.

I’d love to hear what you think!

Python Type Inference at Lambda the Ultimate

May 30, 2006 at 08:26pm

An interesting smattering of links about various approaches to type inference in dynamic languages is discussed over at Lambda the Ultimate.

Book: Eclipse: Building Commercial-Quality Plug-ins

Jun 05, 2006 at 09:26am

Eclipse: Building Commercial-Quality Plug-ins by Eric Clayberg and Dan Rubel looks to be an excellent reference for plugin development, so long as you pick up the 2nd edition, published this year and covering Eclipse 3.2.

If anyone has this book, what has your opinion been? I’ll post back with what I think after I locate a copy.

Inference Framework and Basic Inference Methods

Jun 15, 2006 at 10:42pm

Last week, Chris and I met up and discussed some starting points for digging into RDT and JRuby to begin implementing some real code that produces type inference results! His experience as RDT developer was immensely helpful, and he pointed me to several very helpful examples in the RDT codebase that I’ve looked to for examples.

Prior to this, I’d been getting acquainted with the RDT and JRuby codebases. This was no small feat, and rather daunting at first – with well over 10,000 lines of code in RDT alone, it was tough to find the right spots to focus on. Thanks, Chris!

Two methods for inferring type that I will be looking at this summer include S. Alexander Spoon’s DDP: Demand-Driven Analysis with Goal Pruning and statistical type inference (STI), similar to the method used in the jEdit Ruby plugin.

Hooking up the Harness

The first step in I’ve taken is to create TypeInferenceVisitor, a subclass of InOrderVisitor which visits the nodes of an AST produced by JRuby in the order they appear in the source. In conjunction with a parse harness I wrote based on RDT test code, I can point my visitor at Ruby code and start sifting through results.

Identifying Variables

The first step towards assigning type information to variables is uniquely identifying the variables. For the time being, I will consider variables to be unique by name within their scope. This fails in an example such as:

def foo
  x = 5        # x is a Fixnum
  puts x       # x is a Fixnum
  x = "Hello!" # x is a String
  puts x       # x is a String
end

where variables of a given name have differing types for subregions of a scope. I’ll save this for later.

Variable references are stored in a Map inside the TypeInferenceVisitor, keyed on the variable’s scope and name, and mapping to a structure that holds the type inference information.

Type Inferences

There are many ways in which type information may be gleaned. My intent is to set up a framework where multiple sources of type information guesses can be stored, along with confidence levels. For example, a local assignment of a variable to a constant yields a very high confidence in the variable’s type:

x = 5 # 5 is a Fixnum, so x is a Fixnum.

A local assignment of a variable to another variable confers the type of the rvalue to the lvalue:

x = 5 # x is identified as a Fixnum
y = x # y is also clearly a Fixnum

In the course of traversing a given AST, when AsgnNodes are encountered, the TypeInferenceVisitor will make a guess at the type the variable is being assigned, and associate it with that variable. This inference will contain some sense of how it was generated, the likely type(s) of the variable, and a confidence for its guess(es).

public Interface ITypeInference {
  /** Maps each type guess to a confidence level */
  public Map<String,Integer> typeGuesses;
}

For example, x = 5 would attach a ConstTypeInference to the x variable, signalling that the type of x was inferred based upon a constant assignment. This would have a high confidence, since the type of 5 is definitively known.

An inference based on local assignment, such as the x = 5; y = x example, holds a reference to the ITypeInference information assigned to y, so that if it is updated later in the traversal, its assignee x will benefit from this.

Inferences based on function calls are trickier, though may benefit from some shortcuts. Assigning a variable to the result of a function is the first step outside of purely locally-scoped data flow, a topic central to the DDP algorithm. However, basic class instantiations are easy to glean type information from:

x = Foo.new # It is very likely that x is of type Foo

Final Notes

Although they will not provide robust type information for complex Ruby programs, this handful of methods is giving decent results for analyzing trivial programs with basic relationships. More importantly, they are concrete inference methods that are helping to shape the framework in which I put them. Though it’s been a slow start, the work so far has been immensely fun! I’ll post back soon.

Thinking out loud about block local variables

Jun 17, 2006 at 01:49pm

While designing the code to associate variable references with a scope, I came across what seems to be an ambiguity in Ruby scoping for blocks. If a block local variable does not conflict with the surrounding scope, it exists only for the scope of the block. Parsed by JRuby, the block local variable is a DVarNode.

If the block local variable name overlaps with a variable from the surrounding scope, the block uses the local variable for its operation. Parsed by JRuby, references to the variable name inside and outside of the block are LocalVarNode instances.

Block parameters are handled the same way as block local variables.

Investigating further, it seems this behavior is well-known and scheduled to be handled in more detail in Ruby 2.0.

# block_scoping_ambiguity_1.rb
1. x = "outside"  # LocalAsgnNode
2. puts x         # LocalVarNode  # prints "outside" 
3. 1.times do                           
4.   x = "inside" # LocalAsgnNode       
5.   puts x       # LocalVarNode  # prints "inside" 
6. end                                  
7. puts x         # LocalVarNode  # prints "inside" 

# block_scoping_ambiguity_2.rb          
1. 1.times do                           
2.   x = "inside" # DAsgnNode           
3.   puts x       # DVarNode      # prints "inside" 
4. end
5. puts x         # VCallNode     # results in: undefined local variable or method 'x'

Ruby Grammarians

Jun 17, 2006 at 01:49pm

The Ruby grammarians are working towards an ANTLR grammar for Ruby.

One interesting implementation is Rubyfront, which is able to parse the core libs and all (non-RHTML) Rails code.

At this point, I don’t see a need to use a parser other than the one included in JRuby – it’s providing me with very usable information! Nevertheless, it’s great to see interest in this area.

Local Assignment Inference

Jun 20, 2006 at 12:49am

...is in place. The neat thing is that it’s generated by visiting the AST, not source-level regular expressions.

Ruby Input

v = 5          # Constant
x = 5.to_s     # Known method call result
y = 6.to_f     # Known method call result
z = "hello"    # Constant
q = z.chomp    # Known method call result
w = Regexp.new # Assignment to constructor

Output

Instantiating new TypeInferenceVisitor
with root node org.jruby.ast.BlockNode@ :0
Associating a type to Variable v: [Fixnum,]
Associating a type to Variable x: [String,]
Associating a type to Variable y: [Float,]
Associating a type to Variable z: [String,]
Associating a type to Variable q: [String,]
Associating a type to Variable w: [Regexp,]

Random Though: Collaborative Type Inference

Jun 19, 2006 at 10:06pm

A thought occurred to me while grocery shopping today. Consider all copies of an editor being connected to a central online database. Given an expression:

a = b.c

and following values:

1. Type of a or b
2. Name of method c

inferences can be made about the type of the unknown object. These inferences would be requested by some sort of querying tool in the editor (code completion, object inspector, etc.), and the best guess(es) of the editor are both shown to the programmer and fed into the database.

Based on the programmer’s reaction to the guess, the link is strengthened or weakened. For example, it would be weakened, if the programmer requested method suggestions via code completion and proceeded to fill out a method that does not correspond to the guessed type or otherwise indicated that the variable is of a different type (information that could also be fed to the database, if the programmer chooses to be so helpful).

The link would be strengthened if the programmer acknowledges the type guess in some way, such as by choosing a method that belongs to the guessed type.

Subsequent requests for type inference can make use of the online database’s information, perhaps coupled with other algorithms, possibly resolved by Bayesian classification.

While the idea’s practicality may be a stretch, this may provide an interesting experiment for my AI in Data Mining class this coming fall.

Shift to On-Demand Inquiry

Jun 20, 2006 at 10:13pm

Upon further reflection (read: helpful feedback from señor mentor), establishing a scope stack and attaching variable references to their appropriate scope may be too costly for realtime inference queries. Besides, global information is not usually needed for the type of queries that will typically be issued, such as the type of a single variable.

Switching to a demand-driven approach has both lightened the cost and helped me focus. All inferences mentioned yesterday are now derived by request, rather than through a comprehensive AST visit.

Additionally, they are wrapped up in green-is-go JUnit tests! Note the newly added link on the sidebar to the Subversion repository. If you are interested in following along, Eclipse workspace setup instructions are available on the RDT wiki . Just replace the SVN URL mentioned with my branch and look at org.rubypeople.rdt.internal.ti.TypeInferrerTest.

Addendum: Still trying to digest all of DDP as the most applicable TI approach for this situation, but I think today’s shift is a step in the right direction.

Data for Code Completion and a Hackish Idea

Jun 21, 2006 at 10:30pm

Amidst all this type-inferring, I remembered that establishing the type of an expression (what I am considering “lvalue completion”, such as x='foo';y = x.←INVOKE COMPLETION HERE) is not the only step on the road to code completion. Of course, other things must happen too, but the realization was that these other things are helpful in their own right.

These other things are largely just a matter of collecting data from ri and providing it in a format useful to the code completion framework, and are useful for rvalue completion in the form of x = ←INVOKE COMPLETION HERE:

• Methods available on Kernel, or things-you-can-just-kind-of-type-anywhere.
• A list of native Ruby classes.
• A list of methods for all of those classes.

Adding classes defined in ClassNodes in project scripts would be a nice next step for this. After that, so would listing methods found in DefnNodes and DefsNodes.

Also, had an interesting idea today. It deserves a separate post.

Food For Thought

Jun 21, 2006 at 10:48pm

Consider this:

Additional functionality into the code completion framework so that a user may specify their type to find methods. Sort of a “quick ri.” Let’s say you type

my_var.←INVOKE CC WITH CTRL+SPACE HERE

and the TI engine cannot infer a type. You type {CTRL+SPACE} again and begin matching against a list of types RDT knows about. You type “Str” and String gets highlighted in the list:

       ...................
my_var.|>String<         |
       | StringCheese    |
       | StringentReqDoc |
       ```````````````````

You type {CTRL+SPACE} a third time to indicate you would like to see methods on String and are presented with methods available on a String instance:

my_var.←Methods for String instances now available.

The keyboard shortcuts might need some adjusting, but what do you think? Useful? Useless? Worth pursuing?

Disclaimer: I am by no means giving up on pursuing type inference – it’s the fascinating problem that got me hooked on this project! However, I wonder if this feature would be useful, especially in conjunction with a strong TI engine.

Quick progress check

Jun 21, 2006 at 10:15pm

I realized today that I have made a decent amount of progress with respect to my proposal. I hadn’t thought about this in a while, being neck-deep in wrangling JRuby AST nodes and wringing type data from them.

1. Goal 1 on my development timeline (See proposal.), mapping source offsets to an AST node, is mostly complete!
2. My work on building a scope stack and identifying variables into them can likely be reused for goal 2 in the timeline, highlighting occurences of variables.
3. I’ve recently looked towards providing the data against native classes for goal 3.1 (scope completion, or rvalue completion) as I think this would be very useful, especially given the (relatively) little effort it should take to produce.

I am happy with my progress so far. Of course, getting more accomplished is always better, but there are only so many hours in the day, and there is a lot of learning that goes on along with the development :)

Highlighting references

Jun 30, 2006 at 07:02pm

Just a quick aside from the type inference work, I’ve been working on providing reference highlighting functionality as discussed in my proposal; putting the cursor inside of an element, and having Eclipse highlight the other locations where the element is referenced.

Summer of Code at RubyConf 2006

Jul 06, 2006 at 07:40am

I received an email from David Black of Ruby Central earlier this week informing me that Ruby Central will sponsor their SOCers to come to RubyConf 2006 and present our projects.

This is a wonderful gesture on the part of Ruby Central – you folks rock! Hot on the heels of my first conference experience (which was fantastic), I look forward to meeting many fellow Rubyists this coming October.

Type Feedback

Jul 07, 2006 at 12:41pm

At the outset of this project, I briefly considered using runtime type annotations to provide information to a type inference engine in RDT. That is, to execute a the Ruby program in question (likely in an IO sandboxed environment to prevent Bad Things from inadvertently happening), collecting type information for variables and expressions at runtime, and piping this information back for use at development time.

Though I decided against pursuing this idea, it’s interesting to see that there is research in this area, apparently named type feedback!

Type Feedback vs. Concrete Type Inference: A Comparison of Optimization Techniques for Object-Oriented Languages by Ole Agesen and Urs Hölzle.

Aggressive Type Inference

Jul 07, 2006 at 12:57pm

In Aggressive Type Inference, John Aycock discussed his work with type inference used to translate Python code into Perl. In it, he discusses several examples of where type inference through static analysis falls short for dynamic languages, as well as why several assumptions may be made that minimize the relevance of this shortcoming. Much of what he says rings true with my intents and it is very interesting to see evidence backing up the validity of these assumptions.

He submits the following key idea underlying aggressive type inference (ATI):

Giving people a dynamically-typed language does not mean that they write dynamically-typed programs.

Aycock also analyzes several multiple real-world codebases to support it.

He also used an interesting approach to analyzing builtin functions, by providing a skeletal version in source that is sufficient to provide type information. An example in Ruby:

class String
  def to_i
    return 123
  end

  def to_f
    return 5.678
  end
end

Running the inference engine against this source would provide accurate return types for builtins String#to_i and String#to_f. Interesting, and keeps the inference strategy unified across user and builtin routines.

Mark Occurrences

Jul 20, 2006 at 01:34am

It’s been so long! Sorry for the lack of posting lately; I’ve been mocking up and tossing out model after model of data flow analysis in an attempt to nail down the relationship between data flow and method definition in Ruby in a less-than-kludgy manner – but that’s for another post.

The gist of what I’ve been hacking out when I feel the need to keep all the theory at bay is:

Occurrences, marked! More tomorrow, including:

• Locals and arguments (shown above)
• Locals into block scope
• Instance variables
• Global variables
• Symbols
• Class definitions and references
• Why it will probably be a while before method invocations and definitions are marked (hint: receiver class inference.)

and an explanation of what I’ll be pursuing with the data flow analysis.

As always, if you’d like to check it out, feel the love by hopping over to the svn repo and issuing an svn co.

To see what’s there as of this writing, use your SVN time machine via -r 1532. Until next time!

Update: Annotations come at no extra cost!

The one where more occurrences get marked and subsequently hit the big screen

Jul 21, 2006 at 05:59pm

So, here’s the lowdown on Mark Occurrences. The following items are currently being marked:

• Local variables
• Instance variables
• Class variables
• Global variables
• Method arguments
• Block arguments
• Classes (definitions and references)
• Modules (definitions and references)
• Symbols

What will be marked in the future, but isn’t now:

• Method invocations and definitions
• Method exit points
• Things scoped with ”::”

The next thing dished up will be respecting the Mark Occurrences preferences.

Method exit points are likely the next thing after that, followed by :: scoped items, and finally method invocations and definitions.

Check it out! (AVI)

Type Inference versus Class Inference

Jul 21, 2006 at 06:22pm

Something I would like to discuss is the impedance between class inference (sometimes referred to as static class inference) and type inference in a language, such as Ruby, that supports open classes and metaclasses. In the following code:

stringy_number = "5" 
stringy_number.to_i

it is clear that stringy_number is an instance of String. Slightly less obvious is the set of methods available on this instance, although that information is readily accessible by inspecting RI or introspecting from within an interpreter, say like:

# Simplistic script for scraping methods
# Holy methods, Batman...
# ... 440,470 methods located on my system!
ObjectSpace.each_object do |obj|
  obj.methods.each do |method_name|
    arity = obj.class.method(method_name.to_sym).arity
    puts "#{obj.to_s},#{method_name},#{arity}" 
  end
end

Less clear are methods injected into the String class or even String instances at runtime.

class String
  def jumble
    split('').sort_by { rand }.join
  end
end

str = "Hello" 
class << str
  def double
    self * 2
  end
end

Or methods injected into String’s superclasses, or methods mixed into String or its superclasses or an instance. (Oh my!)

module StringCheese
  def pull_apart
    split('')
  end
end

string_cheese = "Cheddar and Mozzarella!\n" 

class << string_cheese
  include StringCheese
end

string_cheese.chomp.pull_apart

As much as I love string cheese, this makes type inference a bit more difficult than identifying the base class and enumerating its methods. Fortunately, the data flow analysis for determining which method definitions flow into which instances is quite similar to the flow analysis used by DDP and friends to determine which concrete types flow into an instance. In the near future, I hope to document an algorithm that takes into account both of these (actually, an instance’s methods that come from instantiating a concrete type are just a sub-case of the larger method flow analysis) and respects the relationships between instances, classes, and metaclasses.

More to come!

Delicious Links

Jul 24, 2006 at 02:35pm

I’ve added to the sidebar a list of links that I bookmark on Del.icio.us related to type inference. You can also grab the RSS directly.

Fresh and Clean Meta, Identifying Elements in Scope

Aug 09, 2006 at 07:56pm

First things first – it looks a bit different around here! (Unless you’re reading from your aggregator, in which case, it looks just about the samearound here!) I’ve upgraded to Rails 1.1.5, as everyone running a public-facing Rails app should do, and upgraded to Typo 4.0.0 while I was at it. Kudos to the Typo team – blowing away my current directory and replacing it with a pristine install from RubyForge, all I needed to do was restore database.yml, rake migrate, and was good to go!

Almost… my modified theme didn’t quite hold up to the change, so I’ll be running Scribbish until I get a few spare moments to touch it up.

But on to RDT progress! The blog has been a bit quiet lately, as I took a week’s vacation to New York. Relaxed and refreshed, I’m back and ready for a whole heap of productive code hackery in the final two weeks.

Notably, I am close to completing the part of the code completion feature that provides elements available to the current scope:

• Locals and method arguments, if inside a method
• Instance and class variables
• Class and Module names
• Instance and class variables for superclasses and mixins

About one more day, and this should be ready in the type_inference branch.

End of SoC, but not RDT-TI

Aug 22, 2006 at 11:42am

Yesterday marked the completion of the Summer of Code. It’s been a blast! I would like to thank my mentor Chris Williams, members of the RDT and JRuby projects, Ruby Central, and the folks at Google who made the Summer of Code possible. This is a fantastic program, and everyone involved has been immensely helpful. I have enjoyed this opportunity immensely, and look forward to making a continuing contribution to RDT and FOSS.

Since my last post, I’ve been working on a new implementation of the type inferrer that finds what types flow into a given expression through method invocations. This includes tracing types flowing into a method through its parameters, and types flowing out of a method through its return values. This handles many simple cases and provides usable type inference for a subset of Ruby, particularly one that does not make use of class_eval, instance_eval, and friends. These cases, however, are on the radar.

I’ve also given thought to a set of heuristics for evaluating the code near the cursor during code completion to determine whether scope completion (identifying variables and methods available in scope) or type inference is required and, if so, the expression to be examined. These rules also include doctoring up source code before attempting to parse and traverse the AST so that code completion may be requested from syntactically invalid files, such as when a class definition has not been closed before the end-of-file.

My next steps involve cleaning up my code post-SoC, and working with Chris to merge my contributions into trunk. After that, I will focus on:

• Refining DataFlowTypeInferrer to cover more cases:
  • Re-opened classes
  • Methods inserted into classes or instances outside class definitions
  • Implicit method returns
• Investigating the use of the search functionality provided by existing RDT code to provide a fast, indexed search to the TI algorithm to improve speed.
• Discussing code completion in RadRails:
  • Instance variables in templates
  • Discovering fields on ActiveRecord objects
  • Method completions for dynamic finders

Ruby introspection

Sep 12, 2006 at 03:27pm

In the “note-to-self” deparment: Mauricio Fernandez posted an article on scouring method information from within Ruby.

RubyConf 2006

Oct 19, 2006 at 10:47am

I’m off to RubyConf 2006! I’m looking forward to meeting a ton of great Rubyists and presenting my Summer of Code work on Sunday afternoon. More to come!

Talk at RubyConf2006

Oct 22, 2006 at 04:39pm

Hey folks – for those of you coming here from my talk at RubyConf, here is some introductory material.

My slides are available in PowerPoint or PDF .

Ruby Development Tools is the project to which I am contributing.

S. Alexander Spoon’s algorithm for Demand-Driven Type Inference with Goal Pruning is discussed at his site.

More to come when I touch down!

Ruby Type Inference AWAKENS

Feb 07, 2007 10:20am

So I pretty much disappeared once fall classes started again, but I’ve been itching to work on Ruby TI all the while. A few ideas have been floating around, and are coalescing more now that I am taking Languages Processors/Compiler Construction with Axel Schreiner and learning my LL from my LR (from my GLR from my PEG from my…). Anyhow, I’m keeping some notes (redirects to backpack for now), I’d love to hear if you have anything to add!

My current topic of investigation at Ruby-Grammarians.