Efficient local unfolding with ancestor stacks

Puebla Sánchez, Alvaro Germán and Albert Albiol, Elvira and Hermenegildo, Manuel V. (2005). Efficient local unfolding with ancestor stacks. Monografía (Technical Report). Facultad de Informática (UPM), Madrid, España.


Title: Efficient local unfolding with ancestor stacks
  • Puebla Sánchez, Alvaro Germán
  • Albert Albiol, Elvira
  • Hermenegildo, Manuel V.
Item Type: Monograph (Technical Report)
Date: February 2005
Freetext Keywords: Partial evaluation; Partial deduction; Logic programming; Prolog; SLD semantics; Local unfolding
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 (262kB) | Preview


In spite of the important research efforts in the area, the integration of powerful partial evaluation methods into practical compilers for logic programs is still far from reality. This is related both to 1) efficiency issues and to 2) the complications of dealing with practical programs. Regarding efficiency, the most successful unfolding rules used nowadays are based on well founded orders (wfo) or 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 improve the specialization power of unfolding while still guaranteeing termination and also to reduce the number of atoms for which the wfo or 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 any wfo or 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., any atom of the goal can be selected provided it is one of those that have been more recently introduced in the goal. Regarding dealing 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 implementation of these techniques in a practical partial evaluator, embedded in a state of the art compiler which uses global analysis extensively: the Ciao compiler and, specifically, its preprocessor CiaoPP. The performance analysis of the resulting system 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.

More information

Item ID: 55502
DC Identifier: https://oa.upm.es/55502/
OAI Identifier: oai:oa.upm.es:55502
Official URL: http://cliplab.org/papers/lopstr04-unfolding-tr.pdf
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 20 Jun 2019 05:40
Last Modified: 20 Jun 2019 05:40
  • 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