Non-failure analysis for logic programs

Debray, S.K. and Hermenegildo, Manuel V. (1997). Non-failure analysis for logic programs. In: "The 14th International Conference of logic programing", 8-12 July 1997, Leuven, Belgium. ISBN 9780262640350.

Description

Title: Non-failure analysis for logic programs
Author/s:
  • Debray, S.K.
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: The 14th International Conference of logic programing
Event Dates: 8-12 July 1997
Event Location: Leuven, Belgium
Title of Book: Logic Programming
Date: June 1997
ISBN: 9780262640350
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (307kB) | Preview

Abstract

We provide a method whereby, given mode and (upper approximation) type information, we can detect procedures and goals that can be guaranteed to not fail (i.e., to produce at least one solution or not termínate). The technique is based on an intuitively very simple notion, that of a (set of) tests "covering" the type of a set of variables. We show that the problem of determining a covering is undecidable in general, and give decidability and complexity results for the Herbrand and linear arithmetic constraint systems. We give sound algorithms for determining covering that are precise and efiicient in practice. Based on this information, we show how to identify goals and procedures that can be guaranteed to not fail at runtime. Applications of such non-failure information include programming error detection, program transiormations and parallel execution optimization, avoiding speculative parallelism and estimating lower bounds on the computational costs of goals, which can be used for granularity control. Finally, we report on an implementation of our method and show that better results are obtained than with previously proposed approaches.

More information

Item ID: 14406
DC Identifier: http://oa.upm.es/14406/
OAI Identifier: oai:oa.upm.es:14406
Official URL: http://mitpress.mit.edu/books/logic-programming-1
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 05 Feb 2013 20:03
Last Modified: 20 Jun 2019 08:58
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM