Independence in CLP Languages

García de la Banda, M. and Hermenegildo, Manuel V. and Marriott, K. (2000). Independence in CLP Languages. "ACM transactions on programming languages and systems", v. 22 (n. 2); pp. 269-339. ISSN 0164-0925.


Title: Independence in CLP Languages
  • García de la Banda, M.
  • Hermenegildo, Manuel V.
  • Marriott, K.
Item Type: Article
Título de Revista/Publicación: ACM transactions on programming languages and systems
Date: March 2000
ISSN: 0164-0925
Volume: 22
Freetext Keywords: Constraint logic programming, Independence, Parallelism, Programación lógica de restricciones, Paralelismo
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview


Studying independence of goals has proven very useful in the context of logic programming. In particular, it has provided a formal basis for powerful automatic parallelization tools, since independence ensures that two goals may be evaluated in parallel while preserving correctness and eciency. We extend the concept of independence to constraint logic programs (CLP) and prove that it also ensures the correctness and eciency of the parallel evaluation of independent goals. Independence for CLP languages is more complex than for logic programming as search space preservation is necessary but no longer sucient for ensuring correctness and eciency. Two additional issues arise. The rst is that the cost of constraint solving may depend upon the order constraints are encountered. The second is the need to handle dynamic scheduling. We clarify these issues by proposing various types of search independence and constraint solver independence, and show how they can be combined to allow dierent optimizations, from parallelism to intelligent backtracking. Sucient conditions for independence which can be evaluated \a priori" at run-time are also proposed. Our study also yields new insights into independence in logic programming languages. In particular, we show that search space preservation is not only a sucient but also a necessary condition for ensuring correctness and eciency of parallel execution.

More information

Item ID: 13471
DC Identifier:
OAI Identifier:
DOI: 10.1145/349214.349224
Official URL:
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 03 Oct 2012 06:42
Last Modified: 21 Apr 2016 12:47
  • 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