Compiler, was Re: Block closures

Lex Spoon lex at cc.gatech.edu
Mon Jul 31 08:23:24 UTC 2000


Dan Ingalls <Dan.Ingalls at disney.com> wrote:
> Lex -
> 
> >	3. 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





More information about the Squeak-dev mailing list