Efficient local unfolding with ancestor stacks for full prolog

Puebla Sánchez, Alvaro Germán and Albert Albiol, Elvira and Hermenegildo, Manuel V. (2005). Efficient local unfolding with ancestor stacks for full prolog. In: "14th International Symposium, LOPSTR 2004", August 26-28, 2004, Verona, Italy. ISBN 978-3-540-26655-6.


Title: Efficient local unfolding with ancestor stacks for full prolog
  • Puebla Sánchez, Alvaro Germán
  • Albert Albiol, Elvira
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 14th International Symposium, LOPSTR 2004
Event Dates: August 26-28, 2004
Event Location: Verona, Italy
Title of Book: Logic-Based Program Synthesis and Transformation
Date: 2005
ISBN: 978-3-540-26655-6
Volume: 3573
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 (996kB) | Preview


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 efnciency, the most successful unfolding rules used nowadays are based on structural orders applied over (covering) ancestors, i.e., a subsequence of the atoms selected during a derivation. 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 structural order and allows a stack-based implementation without losing any opportunities for specialization. Regarding the second issue, we propose assertion-based techniques which allow our approach to deal with real programs that include (Prolog) built-ins and external predicates in a very extensible manner. 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: 14361
DC Identifier: https://oa.upm.es/14361/
OAI Identifier: oai:oa.upm.es:14361
Official URL: http://link.springer.com/chapter/10.1007%2F11506676_10
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 26 Jan 2013 07:02
Last Modified: 21 Apr 2016 13:59
  • 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