Dan Ingalls Dan.Ingalls@disney.com wrote:
Lex -
- Ability to execute statements straight out of a parse tree. Or at
the least, the ability to generate a block from a parse tree which can later be evaluated. (blocks and methods are very similar in the abstract, but they aren't in Squeak). It just seems like this should be possible, due to the nature of what a parse tree is.
I presume you already use this in your type inferencer, since it allows you to execute an existing method in the space of the types of its parameters and receiver, to produce the type of the result. So I'm strongly in favor of this capability.
Yes, I started with this approach. It breaks down eventually, however, because it has trouble with cyclical dependencies, and cyclical dependencies are too common to just be swept under the rug: for example, recursive methods need them.
So the most recent system begins by extracting an explicit dependency graph for the types, and then iteratively updating the types the way data flow algorithms do. Initially, nodes for literals are assigned a type for the particular literal, and all other nodes are assigned _|_ ("bottom", the type with no values). Then, the nodes are repeatedly updated according to the dependency graph -- if the graph says that node A is a supertype of node B, and node A currently has a type assigned which is smaller than B, then merge B's type into A's type and keep going. (note, OO adds a quirk compared to similar algorithms in other languages: if A's type grows, then new mehtods might be invoked, and so the dependency graph can grow as the algorithm runs!). Eventually this process ends and you have a set of types which is internally consistent.
The key problem is in finding what detail to maintain in the types and in the particular nodes; for example, you can certainly have more than one type node per parse-tree node, to correspond to different contexts the parse-tree node might be used in. But how do you choose what contexts to use and when? You have to make a lot of good choices to get a workable tool out of this, and I haven't managed to do it yet. Some inferences run very quickly (2.0+2.0), but others generate > 100 MB of data and lock up my image an hour or so later (2+2 -- how depressing!).
-Lex