Specialisation of Prolog and FCP programs using abstract interpretation (Q1108783)

This paper presents an approach to specializing logic programs which is based on abstract interpretation. Program specialization involves two stages, the construction of an abstract computation tree and a program construction stage. For the tree construction stage, abstract OLDT resolution is defined and used to construct a complete and finite tree corresponding to a given logic program and a goal. In the program construction stage, a specialized program is extracted from this tree. We focus on two logic programming languages: sequential Prolog and flat concurrent Prolog. Although the procedural reading of concurrent logic programs is very different from that of sequential programs, the techniques presented provide a uniform approach to the specialization of both languages. We present the results for Prolog rigorously, and extend them less formally to flat concurrent Prolog. There are two main advantages of basing program specialization on abstract interpretation. Firstly, termination can be ensured by using abstract interpretations over finite domains, while performing a complete flow analysis of the program. Secondly, correctness of the specialized program is closely related to well-defined consistency conditions on the concrete and abstract interpretations.