Incremental analysis of constraint logic programs

Hermenegildo, Manuel V. and Marriott, K. and Puebla Sánchez, Alvaro Germán and Stuckey, P.J. (2000). Incremental analysis of constraint logic programs. "ACM transactions on programming languages and systems", v. 22 (n. 2); pp. 187-223. ISSN 0164-0925.


Title: Incremental analysis of constraint logic programs
  • Hermenegildo, Manuel V.
  • Marriott, K.
  • Puebla Sánchez, Alvaro Germán
  • Stuckey, P.J.
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: Abstract interpretation, Constraint logic programming, Incremental computation, Static analysis, Programación lógica por restricciones, Análisis estático
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


Global analyzers traditionally read and analyze the entire program at once, in a nonincremental way. However, there are many situations which are not well suited to this simple model and which instead require reanalysis of certain parts of a program which has already been analyzed. In these cases, it appears inecient to perform the analysis of the program again from scratch, as needs to be done with current systems. We describe how the xed-point algorithms used in current generic analysis engines for (constraint) logic programming languages can be extended to support incremental analysis. The possible changes to a program are classied into three types: addition, deletion, and arbitrary change. For each one of these, we provide one or more algorithms for identifying the parts of the analysis that must be recomputed and for performing the actual recomputation. The potential benets and drawbacks of these algorithms are discussed. Finally, we present some experimental results obtained with an implementation of the algorithms in the PLAI generic abstract interpretation framework. The results show signicant benets when using the proposed incremental analysis algorithms.

More information

Item ID: 13472
DC Identifier:
OAI Identifier:
DOI: 10.1145/349214.349216
Official URL:
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 03 Oct 2012 06:37
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