<< Volver atrás

Tesis:

Diseño, semántica e implementación de Babel: un lenguaje que integra la programación funcional y lógica

  • Autor: MORENO NAVARRO, Juan José

  • Título: Diseño, semántica e implementación de Babel: un lenguaje que integra la programación funcional y lógica

  • Fecha: 1989

  • Materia: MATEMÁTICAS. Teseo;CIENCIAS DE LA COMPUTACIÓN. Teseo;LENGUAJES DE PROGRAMACIÓN. Teseo;TEORÍA DE LA PROGRAMACIÓN. Teseo

  • Escuela: FACULTAD DE INFORMATICA

  • Departamentos: SIN DEPARTAMENTO DEFINIDO

  • Acceso electrónico:

  • Director/a 1º: RODRIGUEZ ARTALEJO, Mario

  • Resumen: El interés no puramente académico de los lenguajes de programación declarativos (funcionales y lógicos) se ha incrementado enormemente desde que la tecnología VLSI ha demostrado las posibilidades reales de construir máquinas paralelas capaces de ejecutar programas declarativos eficientemente. También el creciente progreso actual de las técnicas de implementación en máquinas convencionales también ha ayudado a despertar el interés por esta clase de lenguajes. Ni prolog ni son lenguajes funcionales disfrutan de todos los beneficios de la programación declarativa. Durante los últimos años se han realizado una serie de intentos para diseñar lenguajes de programación declarativos que integren los paradigmas funcional y lógico. La consecución de esta integración es algo muy deseable, ya que el lenguaje resultante podría explotar ampliamente las facilidades de la lógica (funciones, predicados e igualdad), permitiendo a sus usuarios usarlas separadamente o mezclarlas de la forma mas apropiada para una aplicación en particular. En esta tesis se presenta y estudia el lenguaje de programación experimental Babel, designado para conseguir la integración de la programación funcional (como la usada en hope, standard ml o Miranda) y la programación lógica (como la usada en prolog) de una forma simple, flexible y matemáticamente bien fundamentada. El lenguaje sigue una disciplina de constructores, muy adecuado para acomodar términos prolog y patrones tipo hope. Desde el punto de vista sintáctico, Babel combina prolog puro con una notación funcional sin tipos ni funciones de orden superior. Por otro lado, el lenguaje usa narrowing como base de una semántica de reducción perezosa, que incluye tanto reescritura como resolución sld, soportando cómputos con estructuras de datos potencialmente infinitas. Hay también una semántica declarativa, basada en dominios de scott, que aporta una noción de mínimo modelo de herbrand para los programas babel. Se desarrollan ambas semánticas probando resultandos de corrección y completitud estableciendo la esperada equivalencia entre ambas. También se ilustran las características del lenguaje a través de numerosos ejemplos de programación. Se ha argumentado que la implementación del narrowing no es una tarea fácil y que seria mejor reducirlo a resolución sld para aprovechar las técnicas de implementación conocidas para prolog. Nuestra idea es que se puedan usar las muy eficientes técnicas existentes para los lenguajes funcionales. Se ha diseñado una extensión de una máquina funcional por de reducción de grafos. Con facilidades para manejar backtraking y unificación siguiendo las ideas de la maquina abstracta de warren para prolog. De esta forma, se obtiene una maquina abstracta para narrowing para una versión secuencial e innermost de Babel. Pensamos que nuestra aproximación permite realizar implementaciones eficientes del lenguaje. El trabajo también incluye un interprete prolog para Babel