Advanced Compilation Techniques for Logic Programming = Técnicas Avanzadas de Compilación para Programación Lógica

Morales Caballero, José Francisco (2010). Advanced Compilation Techniques for Logic Programming = Técnicas Avanzadas de Compilación para Programación Lógica . Tesis (Doctoral), Facultad de Informática (UPM) [antigua denominación].

Descripción

Título: Advanced Compilation Techniques for Logic Programming = Técnicas Avanzadas de Compilación para Programación Lógica
Autor/es:
  • Morales Caballero, José Francisco
Director/es:
  • Carro Liñares, Manuel
  • Hermenegildo Salinas, Manuel de
Tipo de Documento: Tesis (Doctoral)
Fecha: Marzo 2010
Materias:
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Lenguajes y Sistemas Informáticos e Ingeniería del Software
Licencias Creative Commons: Reconocimiento - No comercial - Compartir igual

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (2MB) | Vista Previa

Resumen

Declarative programming languages allow the expression of programs in a language that is closer to the problem than to the implementation details. Regardless the generality of that definition, a more clear idea of declarativeness is proposed by Lloyd[Llo94], who proposes that programs are theories in some suitable logic, and computation is deduction from the theory. In logic programming, where Prolog is one of the most popular incarnations of that paradigm, the theory is that of logical deduction. Efficient implementations able to compete with many other high-level languages, and its flexibility, made Prolog a very good framework to develop new ideas, such as constraint programming, and multi-paradigm programming merging functional programming, object oriented programming, and imperative programming. Although the state of the art of Prolog implementations is highly optimized for the kind of search problems it is designed, and it can compete with many language implementations for other paradigms — both logic, functional, and imperative — its dynamism and declarative nature imposes a considerable efficiency gap. An ambitious goal for Prolog implementations, shared with many other declarative languages, is closing this gap while not sacrificing expressivity. The objective of this thesis is the development and improvement of advanced techniques for compilation of Prolog, orthogonal to many extensions such as constraint logic programming [JM87], Prolog with tabling [War92], CHR over Prolog [SF08]. The main contributions presented in this thesis can be summarized as: An optimizing compiler of Prolog, where selected predicates can be compiled to C, and designed to accept high-level information, obtained from automatic analysis, and expressed in a standardized language of assertions. An automatic approach to the generation of abstract machines, where the instruction set, and the bytecode and data representation can be defined individually. Description of the full instruction set of a Prolog abstract machine in a Prolog dialect extended with state-changes (as mutable variables), amenable to program transformations. Representation of tagged words in the higher-level language, exploring many alternatives for the 32 and 64 bit cases. A parametric framework to generate variations of abstract machines, to explore optimizations in general or targeting a particular set of programs. Study of the combination of the source-level and low-level optimization compilation techniques in a real test case for embedded devices. Los lenguajes de programación declarativos permiten expresar programas en un lenguaje que es más cercano al problema que a los detalles de implementación. A pesar de la genericidad de esta definición, Lloyd propone una noción más clara de la declaratividad [Llo94], definiendo los programas como teorías en una lógica adecuada y la computación deducción en base a la teoría. Prolog es uno de los lenguajes de programación del paradigma lógico más importantes, cuya teoría es la de la deducción lógica. Implementaciones eficientes capaces de competir con muchos otros lenguajes de alto nivel y su flexibilidad, han hecho de Prolog un importante punto de partida para desarrollar nuevas ideas, como la programación con restricciones y multi-paradigma, mezclando programación funcional, orientada a objetos e imperativa. Aunque el estado del arte de las implementaciones de Prolog esta altamente optimizado para el tipo de problemas de busqueda para los que este está diseñado y que puede competir con muchas implementaciones de otros paradigmas — tanto lógico, funcional, como imperativo — su naturaleza caracteristicas dinámicas y declarativas imponen una considerable limitación en eficiencia. Un ambicioso objetivo para las implementaciones de Prolog, compartido por muchos otros lenguajes declarativos, consiste en el desarrollo de téctnicas que superen esta limitación sin sacrificar la expresividad del lenguaje. El objetivo de esta tesis es el desarrollo y mejora de técnicas avanzadas de compilacion para Prolog, en principio ortogonales a extensiones como la programación lógica con restricciones [JM87], Prolog con tabulación [War92] o CHR sobre Prolog [SF08]. Las principales contribuciones presentadas en esta tesis pueden resumirse en: Un compilador optimizante de Prolog, donde predicados seleccionados son compilados a C y diseñado para aceptar información de alto nivel, obtenida mediante análisis automático y expresada en un lenguaje estandarizado de aserciones. Un enfoce automático a la generación de máquinas abstractas, donde el conjunto de instrucciones y la representación de código de byte y datos son definidas de forma individual. Una descripción del conjunto de instrucciones completo de una máquina abstract para Prolog, en un dialecto de Prolog extendido para manejar cambios de estado (en forma de variables mutables) y adecuado para realizar transformaciones automáticas de programa. Una representación de tagged words (palabras con etiquetas) en un lenguaje de alto nivel, explorando variantes para los casos de 32 y 64 bit. Un marco de trabajo paramétrico para la generación de variaciones de máquinas abstractas, para explorar optimizaciones de forma general o enfocadas a un conjunto particular de programas. Un estudio de la combinación de técnicas de compilación optimizante en código fuente y en código de bajo nivel, en un caso de prueba real para sistemas ubícuos.

Más información

ID de Registro: 7778
Identificador DC: http://oa.upm.es/7778/
Identificador OAI: oai:oa.upm.es:7778
Depositado por: Archivo Digital UPM
Depositado el: 27 Jun 2011 06:55
Ultima Modificación: 20 Abr 2016 16:48
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM