Intellisense for dynamic languages

Question

I am looking for various approaches for supporting some level of intellisense on a dynamically typed language. Since intellisense information is based on type information, there are inherent difficulties in implementing this for dynamic languages.

Do you know any algorithms or methods to implement it?

Answer 1

You need to write an abstract interpreter that executes the code with type values. So you step with your abstract interpreter trough the AST and record for each variable the sent messages or known types. And when you are done, you infer the possible types using structural type equivalence (aka duck typing).

PS: in addition to type inference you might want to take a look at "How Program History Can Improve Code Completion" by Romain Robbes, is explains how to further improve auto completion in dynamic languages with most-recently-used information and collaborative filtering.

So here is how abstract interpretation works for a code snippet like

def groups(array,&block)
  groups = Hash.new
  array.each { |ea| 
    key = block.call(ea)
    groups[key] = [] unless groups.include? key
    groups[key] << ea
  }
  return groups
end

you would start with

array = { :messages => [], :types => [] }
block = { :messages => [], :types => [] }

and then

array = { :messages => [], :types => [] }
block = { :messages => [], :types => [] }
groups = { :messages => [], :types => [Hash] }

and then

array = { :messages => [:each], :types => [] }
block = { :messages => [], :types => [] }
groups = { :messages => [], :types => [Hash] }

and then

array = { :messages => [:each], :types => [] }
block = { :messages => [:call], :types => [] }
groups = { :messages => [], :types => [Hash] }
key = {  :messages => [], :types => [] }

and then

array = { :messages => [:each], :types => [] }
block = { :messages => [:call], :types => [] }
groups = { :messages => [:include?,:[]], :types => [Hash] }
group_elements = { :messages => [], :types => [Array] }
key = { :messages => [], :types => [] }

and then

array = { :messages => [:each], :types => [] }
block = { :messages => [:call], :types => [] }
groups = { :messages => [:include?,:[]], :types => [Hash] }
group_elements = { :messages => [:<<], :types => [Array] }
key = { :messages => [], :types => [] }

so eventually we can infer that

• array is possibly an Enumerable
• block is possibly a Proc
• groups is a Hash with Array elements
• key is any object

Answer 2

I would download the sources of the Groovy plugin for eclipse, it has intellisense (as much as possible), and think Groovy is a good sample of a dyanamic language with dynamic typing