Title: Conjunctive partial deduction: foundations, control, algorithms, and experiments
Authors: De Schreye, Danny ×
Glück, R
Jørgensen, Jesper
Leuschel, Michael
Martens, Bern
Sørensen, Morten Heine #
Issue Date: Nov-1999
Publisher: Elsevier science inc
Series Title: Journal of logic programming vol:41 issue:2-3 pages:231-277
Abstract: Partial deduction in the Lloyd-Shepherdson framework cannot achieve certain optimisations which are possible by unfold/fold transformations. We introduce conjunctive partial deduction, an extension of partial deduction accommodating such optimisations, e.g., tupling and deforestation, We first present a framework for conjunctive partial deduction, extending the Lloyd-Shepherdson framework by considering conjunctions of atoms (instead of individual atoms) for specialisation and renaming. Correctness results are given for the framework with respect to computed answer semantics, least Herbrand model semantics, and finite failure semantics, Maintaining the well-known distinction between local and global control, we describe a basic algorithm for conjunctive partial deduction, and refine it into a concrete algorithm for which we prove termination, The problem of finding suitable renamings which remove redundant arguments turns out to be important, so we give an independent technique for this. A fully automatic implementation has been undertaken, which always terminates, Differences between the abstract semantics and Prolog's left-to-right execution motivate deviations from the abstract technique in the actual implementation, which we discuss. The implementation has been tested on an extensive set of benchmarks which demonstrate that conjunctive partial deduction indeed pays off, surpassing conventional partial deduction on a range of small to medium-size programs, while remaining manageable in an automatic and terminating system. (C) 1999 Elsevier Science Inc. All rights reserved.
ISSN: 0743-1066
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
Department of Teacher Training - UC Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
1-s2.0-S0743106699000308-main.pdf Published 380KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science