Any analysis of higher-order languages must grapple with thetri-facetted nature of lambda. In one construct, the fundamentalcontrol, environment and data structures of a language meet andintertwine. With the control facet tamed nearly two decades ago, thiswork brings the environment facet to heel, defining the environmentproblem and developing its solution: environment analysis. Environmentanalysis allows a compiler to reason about the equivalence ofenvironments, i.e., name-to-value mappings, that arise during aprogram's execution. In this dissertation, two differenttechniques-abstract counting and abstract frame strings-make thispossible. A third technique, abstract garbage collection, makes bothof these techniques more precise and, counter to intuition, oftenfaster as well. An array of optimizations and even deeper analyseswhich depend upon environment analysis provide motivation for thiswork.In an abstract interpretation, a single abstract entity represents aset of concrete entities.When the entities under scrutiny arebindings-single name-to-value mappings, the atoms of environment-thendetermining when the equality of two abstract bindings infers theequality of their concrete counterparts is the crux of environmentanalysis. Abstract counting does this by tracking the size ofrepresented sets, looking for singletons, in order to apply thefollowing principle: If {x} = {y}, then x = y.Abstract frame strings enable environmental reasoning by staticallytracking the possible stack change between the births of twoenvironments; when this change is effectively empty, the environmentsare equivalent. Abstract garbage collection improves precision byintermittently removing unreachable environment structure duringabstract interpretation.
PDF
download
878987797
028-85220240
