Tim Rowledge tim@sumeru.stanford.edu wrote:
"Lex Spoon" lex@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.
-Lex