Removing superfluous versions in polyvariant specialization of prolog programs.

Ochoa, Claudio and Puebla Sánchez, Alvaro Germán and Hermenegildo, Manuel V. (2006). Removing superfluous versions in polyvariant specialization of prolog programs.. In: "15th International Symposium, LOPSTR 2005", September 7-9, 2005, London, UK. ISBN 978-3-540-32654-0.

Description

Title: Removing superfluous versions in polyvariant specialization of prolog programs.
Author/s:
  • Ochoa, Claudio
  • Puebla Sánchez, Alvaro Germán
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 15th International Symposium, LOPSTR 2005
Event Dates: September 7-9, 2005
Event Location: London, UK
Title of Book: Logic-Based Program Synthesis and Transformation
Date: 2006
ISBN: 978-3-540-32654-0
Volume: 3901
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

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

Abstract

Polyvariant specialization allows generating múltiple versions of a procedure, which can then be separately optimized for different uses. Since allowing a high degree of polyvariance often results in more optimized code, polyvariant specializers, such as most partial evaluators, can genérate a large number of versions. This can produce unnecessarily large residual programs. Also, large programs can be slower due to cache miss effects. A possible solution to this problem is to introduce a minimization step which identifies sets of equivalent versions, and replace all occurrences of such versions by a single one. In this work we present a unifying view of the problem of superfluous polyvariance. It includes both partial deduction and abstract múltiple specialization. As regards partial deduction, we extend existing approaches in several ways. First, previous work has dealt with puré logic programs and a very limited class of builtins. Herein we propose an extensión to traditional characteristic trees which can be used in the presence of calis to external predicates. This includes all builtins, librarles, other user modules, etc. Second, we propose the possibility of collapsing versions which are not strictly equivalent. This allows trading time for space and can be useful in the context of embedded and pervasive systems. This is done by residualizing certain computations for external predicates which would otherwise be performed at specialization time. Third, we provide an experimental evaluation of the potential gains achievable using minimization which leads to interesting conclusions.

More information

Item ID: 14354
DC Identifier: http://oa.upm.es/14354/
OAI Identifier: oai:oa.upm.es:14354
Official URL: http://link.springer.com/chapter/10.1007%2F11680093_6
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 25 Jan 2013 09:09
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