[ANN] Chuck type inferencer

Lex Spoon lex at cc.gatech.edu
Fri May 28 21:46:18 UTC 2004

Tim Rowledge <tim at sumeru.stanford.edu> wrote:
> "Lex Spoon" <lex at cc.gatech.edu> wrote:
> > The major memory requirement, it turns out, is that AutoChuck is keeping
> > around parse trees for every method.  So I'm trying to eithre get rid of
> > that requirement or make the parse trees take less memory.
> It might be useful to recall one of Eliot's battle cries -
> "CompiledMethods are flattened parsetrees" 

It is very tempting to try and use the compiled methods themselves as
the compressed parse trees.  That would mean there is zero overhead from
"keeping around parse trees".  However, I don't know if I will implement
this idea myself.   There is one very annoying issue: the decompiler
does not always produce *exactly* the parse tree that was compiled to
begin with.

One option that could be taken is to treat the decompressed parse trees
as the "real" parse trees.  However, then one faces difficulties in
hooking up to the user-level tools.  If a user highlights some code and
asks for the type of it, then the highlighted expression had better
actually exist in the parse trees!  Also, when the inferencer reports a
result, it gives a derivation of that result.  All of the expressions
mentioned in the derivation should, again, be expressions that exist in
the code.  In short, I want Chuck to be useful for program understanding
tools, and such tools need to operate in the same universe of code that
the programmers are in.

It may be possible to tweak the compiler and decompiler until they are
symmetric.  I really don't know; it would take a careful analysis of the
compiler and decompiler to do it, though, and I'd rather avoid this.

That leaves one major option: include a tree diff alongside each
compiled method.  To get the user-visible parse tree, one could then
decompile the compiled method, and then apply the tree diff to the
result.  The diffs should be small; in fact, most methods will probably
decompile exactly, and thus the diffs would not require much memory. 
This looks like an excellent solution that will very clearly work,
except for one tiny detail: I know absolutely nothing about tree diff
algorithms and would have to go do some hefty studying before
implementing one!

In summary, if anyone wants to try one of the above ideas to make
compiled methods behave *exactly* like compressed parse trees, I will
heartily try it out.  For now, I plan to simply do a dumb flattening of
the trees into a binary form, however, which seems to produce plenty of
space savings by itself after just a couple of hours of coding.


More information about the Squeak-dev mailing list