the halting problem and background compilation?

Question

I'm trying to figure out how I could write an autocompletion algorithm for Lua, but since as with many scripting languages it lacks a static type system I think I need background compilation, but during background compilation it's easy to hit the halting problem so I was wondering if anyone has solved this sort of thing before, and what are the standard strategies for solving compilation and halting?

Answer 1

Autocompletion based on static text analysis sounds more reasonable than trying to compile in the background. Most text editors that provide autocomplete use this method, although it isn't as accurate.

To do so, you can parse the document looking for names and recording the scope they belong to. As the point moves through the document, your autocomplete notes the scope it is currently in and provides the names that should be available at that point.

As LUA is global scope by default, you may end up with a fairly polluted namespace if your programmers aren't using the "local" keyword to narrow scopes.

Answer 2

You can

• actually execute the code to see what kind of object is represented by a particular variable, and cut the execution in the middle if it takes too long
• guess what type would the actual variable have, if Lua had types. This means you'd have to create a type system, which is a nontrivial task (you have to be enough restrictive to allow reasoning about the object model, and enough permissive for enough Lua programs actually conform to your model). However, all the shiny new javascript engines try to do this, AFAIK, so you could look there for pointers.
• just guess from the syntax. For example, emacs completion, which only looks for the same prefixes, works like charm in cases where other IDEs usually fail (C++ templates)