Intellisense for dynamic languages

intellisense, programming-languages

Solution

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

Problem

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?

Original source