The derivation of an algorithm for program specialisation

In this paper we develop an algorithm, based on abstract interpretation, for source specialisation of logic programs. This approach is more general than partial evaluation, another technique for source specialisation, and can perform some source specialisations that cannot be done by partial evaluation; examples are specialisations that use information from infinite computations. Our algorithm for program specialisation usesminimal function graphs as a basis. Previous work on minimal function graphs is extended by describing a scheme for constructing a minimal function graph for a simple functional language, and then using that to define a minimal function graph constructor for Prolog. We show how to compute a more precise approximation to the minimal function graph than was obtained in previous work. The efficient computation of minimal function graphs is also discussed. An abstract interpretation based on unfolding paths is then developed for Prolog program specialisation.