Non-leftmost Unfolding in Partial Evaluation of Logic Programs with Impure Predicates

Elvira Albert, German Puebla, John Patrick Gallagher

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

Partial evaluation of logic programs which contain impure predicates poses non-trivial challenges. Impure predicates include those which produce side-effects, raise errors (or exceptions), and those whose truth value varies according to the degree of instantiation of arguments. In particular, non-leftmost unfolding steps can result in incorrect results since the independence of the computation rule no longer holds in the presence of impure predicates. Existing proposals allow non-leftmost unfolding steps, but at the cost of accuracy: bindings and failure are not propagated backwards to predicates which are potentially impure. In this work we propose a partial evaluation scheme which substantially reduces the situations in which such backpropagation has to be avoided. With this aim, our partial deducer takes into account the information about purity of predicates expressed in terms of assertions. This allows achieving some optimizations which are not feasible using existing partial evaluation techniques. We argue that our proposal goes beyond existing ones in that it is a) accurate, since the classification of pure vs impure is done at the level of atoms instead of predicates, b) extensible, as the information about purity can be added to programs using assertions without having to modify the partial deducer itself, and c) automatic, since (backwards) analysis can be used to automatically infer the required assertions. Our approach has been implemented in the context of Ciaopp, the abstract interpretation-based preprocessor of the Ciao logic programming system.
OriginalsprogEngelsk
TitelLogic Based Program Synthesis and Transformation, 15th International Symposium, LOPSTR 2005
RedaktørerPatricia M. Hill
Antal sider17
ForlagSpringer
Publikationsdato2006
Sider115-132
ISBN (Trykt)3-540-32654-5
StatusUdgivet - 2006
Begivenhed15th International Symposium Logic Based Program Synthesis and Transformation - London, Storbritannien
Varighed: 7 sep. 20059 sep. 2005
Konferencens nummer: 15

Konference

Konference15th International Symposium Logic Based Program Synthesis and Transformation
Nummer15
LandStorbritannien
ByLondon
Periode07/09/200509/09/2005
NavnLecture Notes in Computer Science
Vol/bind3901
ISSN0302-9743

Citer dette

Albert, E., Puebla, G., & Gallagher, J. P. (2006). Non-leftmost Unfolding in Partial Evaluation of Logic Programs with Impure Predicates. I P. M. Hill (red.), Logic Based Program Synthesis and Transformation, 15th International Symposium, LOPSTR 2005 (s. 115-132). Springer. Lecture Notes in Computer Science, Bind. 3901