Efficient local unfolding with ancestor stacks

Puebla Sánchez, Alvaro Germán and Albert Albiol, Elvira and Hermenegildo, Manuel V. (2011). Efficient local unfolding with ancestor stacks. "Theory and practice of logic programming", v. 11 (n. 1); pp. 1-32. ISSN 1471-0684.


Title: Efficient local unfolding with ancestor stacks
  • Puebla Sánchez, Alvaro Germán
  • Albert Albiol, Elvira
  • Hermenegildo, Manuel V.
Item Type: Article
Título de Revista/Publicación: Theory and practice of logic programming
Date: January 2011
Volume: 11
Freetext Keywords: Partial evaluation, Partial deduction, Logic programming, Prolog, SLD semantics, Local unfolding, Evaluación parcial, Deducción parcial, Programación lógica.
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 (1MB) | Preview


The most successful unfolding rules used nowadays in the partial evaluation of logic programs are based on well quasi orders (wqo) applied over (covering) ancestors, i.e., a subsequence of the atoms selected during a derivation. Ancestor (sub)sequences are used to increase the specialization power of unfolding while still guaranteeing termination and also to reduce the number of atoms for which the wqo has to be checked. Unfortunately, maintaining the structure of the ancestor relation during unfolding introduces significant overhead. We propose an efficient, practical local unfolding rule based on the notion of covering ancestors which can be used in combination with a wqo and allows a stack-based implementation without losing any opportunities for specialization. Using our technique, certain non-leftmost unfoldings are allowed as long as local unfolding is performed, i.e., we cover depth-first strategies. To deal with practical programs, we propose assertion-based techniques which allow our approach to treat programs that include (Prolog) built-ins and external predicates in a very extensible manner, for the case of leftmost unfolding. Finally, we report on our mplementation of these techniques embedded in a practical partial evaluator, which shows that our techniques, in addition to dealing with practical programs, are also significantly more efficient in time and somewhat more efficient in memory than traditional tree-based implementations. To appear in Theory and Practice of Logic Programming (TPLP).

Funding Projects

FP7215483S-CUBEUnspecifiedSoftware Services and Systems Network
Comunidad de MadridS-0505/TIC/0407 PROMESASUnspecifiedUnspecifiedUnspecified

More information

Item ID: 14259
DC Identifier: http://oa.upm.es/14259/
OAI Identifier: oai:oa.upm.es:14259
Deposited by: PAS Almudena Mateos Rodríguez
Deposited on: 11 Jan 2013 08:21
Last Modified: 03 Dec 2014 09:39
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM