Advanced techniques for approximating variable aliasing in logic programs
Anno Langen · University of Southern California Digital Library · 2017
During the execution of a Logic Program, two program variables are aliased if they are bound to terms that share a common variable. Information about variable aliasing is essential for certain optimizations, notably for exploiting Independent And-Parallelism. It can also be used to improve the accuracy of the analysis of other run-time properties of the variable binding, such as groundness, freeness, linearity, and term structure, that are essential to other optimizations. The general problem of deciding whether variables can possibly be aliased at some point in a program is undecidable. Thus, any algorithm for deriving information about variable aliasing must necessarily produce an approximation. This dissertation presents several results that advance the accuracy and efficiency of the approximation of variable aliasing in Logic Programs. We use the framework of abstract interpretation to provide a formal basis for the approximation of run-time properties. We present a novel domain for approximating variable aliasing, compare it with previous and alternative proposals, and demonstrate its feasibility. We present a new evaluation technique, called condensing, within the framework of abstract interpretation, and discuss its advantages and limitations. We present a version of semantics of Logic Programs that uses only a single operation to model the parameter unification on entry and exit. Some previous semantic definitions of Logic Programs have been obscured by the need to standardize the variable names of the call and procedure head apart. We have encapsulated the proper treatment of variable names into a single operation outside of the semantic definitions, which became more lucid as a result. Finally, we apply our analysis to a particular approach to Independent And-Parallelism. Specifically, we show how variable aliasing analysis improves the generation of control expressions that use simple run-time tests to schedule goals for parallel execution. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089-0182.)