Higher-Order and Symbolic Computation, 14(2/3)143-172
Regular Tree Languages as an Abstract Domain in Program SpecialisationJohn P. Gallagher, Department of Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol BS8 1UB, UK. john@cs.bris.ac.uk
Julio C. Peralta, Department of Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol BS8 1UB, UK
|
Abstract: On-line partial evaluation algorithms include a
generalisation step, which is needed to ensure termination. In partial
evaluation of logic and functional programs, the usual generalisation
operation is the most specific generalisation (msg) of
expressions. This can cause loss of information, which is especially
serious in programs whose computations first build some internal data
structure that is then used to control a subsequent phase of
execution--a common pattern of computation. If the size of the
intermediate data is unbounded at partial evaluation time then the msg
will lose almost all information about its structure. Hence subsequent
phases of computation cannot be effectively specialised. In this paper the problem is tackled by introducing regular tree languages into a partial evaluation algorithm. A regular tree language is a set of terms defined by tree automata or tree grammars. In the algorithm, regular tree approximations of sets of terms encountered during partial evaluation are constructed. The critical point is that when generalisation is performed, the upper bound on regular tree languages can be combined with the msg, thus preserving recursive information about term structure. This approach also allows the specialisation of programs with respect to goals whose arguments range over regular tree languages. The algorithm is presented as an instance of Leuschel's framework for abstract specialisation of logic programs. This provides a generic algorithm parameterised by an abstract domain--regular trees in this case. The correctness requirements from his framework are established. The extension of the algorithm to propagate regular approximations of answers as well as calls is also presented, increasing the amount of specialisation that can be obtained. Finally a technique for increasing precision based on "wrapper functions" is introduced. Keywords: program specialisation, partial evaluation, regular tree languages |
This article can be downloaded [here].
![[picture of journal cover]](../LISP.JPG)