The derivation of an algorithm for program specialisation

John Gallagher*, Maurice Bruynooghe

*Corresponding author

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstract

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 uses minimal 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.
OriginalsprogEngelsk
TidsskriftNew Generation Computing
Vol/bind9
Udgave nummer3-4
Sider (fra-til)305-333
Antal sider29
ISSN0288-3635
DOI
StatusUdgivet - aug. 1991
Udgivet eksterntJa

Emneord

  • Obstruct Interpretation
  • Partial Evaluation
  • Program Specialisation

Citer dette