© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Control Generation by Program Transformation
Jonathan C. Martin and Andy King
Technical Report 5-04, University of Kent, Computing Laboratory, University of Kent, Canterbury, CT2 7NF, March 2004.Abstract
The objective of control generation in logic programming is to derive a computation rule for a program that is efficient and yet does not compromise program correctness. Progress in solving this fundamental problem in logic programming has been slow and, to date, only partial solutions have been proposed. Previously proposed schemes are either inefficient, incomplete (incorrect) or difficult to apply for programs consisting of many components (the scheme is not modular). This paper shows how the control generation problem can be tackled by program transformation. The transform relies on information about the depths of derivations to derive delay declarations which orchestrate the control. To prove correctness of the transform, the notion of semi-delay recurrency is introduced, which generalises previous ideas in the termination literature for reasoning about logic programs with delay declarations. In contrast to previous work, semi-delay recurrency does not require an atom to be completely resolved before another is selected for reduction. This enhancement permits the transformation to introduce control which is both flexible and efficient.
Download publication 488 kbytes (PostScript)
Bibtex Record
@techreport{1868,
author = {Jonathan C. Martin and Andy King},
title = {Control {G}eneration by {P}rogram {T}ransformation},
month = {March},
year = {2004},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2004/1868},
publication_type = {techreport},
submission_id = {6985_1081337712},
number = {5-04},
address = {University of Kent, Canterbury, CT2 7NF},
institution = {University of Kent, Computing Laboratory},
}