School of Computing

Generating efficient, terminating logic programs

J.M. Martin and A.M. King

In Proceedings of the Seventh International Joint Conference on Theory and Practice of Software Development, volume 1214 of Lecture Notes in Computer Science, pages 173-184. Springer Verlag, April 1997.

Abstract

The objective of control generation in logic programming is to automatically derive a computation rule for a program that is efficient and yet does not compromise program correctness. Progress in solving this important problem has been slow and, to date, only partial solutions have been proposed where the generated programs are either incorrect or inefficient. We show how the control generation problem can be tackled with a simple automatic transformation that relies on information about the depths of derivations. To prove correctness of our transform we introduce the notion of a semi delay recurrent program which generalises previous ideas in the termination literature for reasoning about logic programs with dynamic selection rules.

Download publication 136 kbytes (PostScript)

Bibtex Record

@inproceedings{216,
author = {J.M. Martin and A.M. King},
title = {Generating Efficient, Terminating Logic Programs},
month = {April},
year = {1997},
pages = {173-184},
keywords = {Termination, Control Generation, Abstract Interpretation},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1997/216},
    booktitle = {Proceedings of the Seventh International Joint Conference on Theory and Practice of Software Development},
    publisher = {Springer Verlag},
    volume = {1214 of Lecture Notes in Computer Science},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 12/03/2012 17:02