Download Integración de los paradigmas lógico y funcional
Document related concepts
Transcript
Integración de los paradigmas lógico y funcional Daniel Jiménez García Índice Introducción 1. I. II. III. Métodos de integración 2. I. II. III. Metodologías Narrowing Metodologías y Lenguajes Lenguajes 3. I. II. 4. 5. Paradigmas lógico y funcional Motivaciones Objetivos Curry λ-Prolog Conclusiones Bibliografía 1. Introducción 1.1 Paradigmas lógico y funcional Programación funcional: Definición de funciones mediante ecuaciones Mecanismo operacional: reescritura Selección de una estrategia de reducción (Ej: evaluación perezosa en Haskell) 1.1 Paradigmas lógico y funcional Programación lógica: Definición de relaciones mediante formulas lógicas (cláusulas de Horn) Mecanismo operacional: unificación + resolución 1.1 Paradigmas lógico y funcional Programación funcional: Polimorfismo Fuertemente tipados Cómputo determinista Funciones de orden superior Manejo de datos infinitos Programación lógica: Indeterminismo Variable lógica Sin tipos Funciones de primer orden Datos finitos 1.2 Motivaciones ¿Qué ventajas puede tener integrar ambos paradigmas? Establecer un nexo entre la programación lógica y la funcional Facilitar la enseñanza de la programación declarativa Obtener un lenguaje con las mejores características de ambos paradigmas 1.3 Objetivo Cada estilo tiene algo que ofrecer al otro: Los lenguajes lógicos poseen la lógica de la unificación y de las variables lógicas Los lenguajes funcionales poseen la lógica de la igualdad y de las funciones Objetivo: combinar las mejores características de los ambos paradigmas 1.3 Objetivo Algunas de las ventajas que podemos esperar: Potencia de las variables lógicas y unificación Eficiencia de un lenguaje funcional Empleo de tipos y orden superior de un lenguaje funcional Evitar ciertas características impuras de Prolog, como el corte Apto para aplicaciones de ambos campos 2. Métodos de integración 2.1 Metodologías Básicamente tenemos 2 formas de integración: Introducir el lenguaje lógico dentro de uno funcional, trasladando cada predicado a una función. Definir un nuevo lenguaje donde el mecanismo operacional conste de unificación + resolución y reescritura 2.1 Metodologías Dentro del primer grupo aparecen las primeras propuestas como LOGLISP o SUPER. Estas propuestas no cuentan con el beneplácito general y tienen un problema: Modelar la variable lógica y sacar partido al indeterminismo que conlleva Es dentro del 2º grupo donde se concentran la mayoría de las propuestas. De nuevo contamos con varias opciones. 2.1 Metodologías 1. Considerar un programa como la unión de un conjunto de ecuaciones y cláusulas de Horn. La semántica extiende la lógica con la igualdad. El mecanismo operacional puede: Extender resolución → ¡espacio de búsqueda enorme! Extender la unificación sintáctica para obtener unificación semántica (es decir, tenemos en cuenta el tipo de la variable) → ¡resultó ser muy limitado! 2.1 Metodologías 2. Considerar las cláusulas de Horn como un conjunto de reglas de reescritura, de forma que podamos utilizar el mecanismo de reducción (ya sea perezosa o impaciente). Las funciones deben esperar a que estén lo suficientemente instanciadas. Residuación = reducción + congelación de funciones Dentro de esta filosofía podemos encontrar ejemplos de lenguajes como: FUNLOG L&O LIFE 2.1 Metodologías 3. Considerar H como un conjunto de reglas de escritura, y extender el concepto de reducción mediante la unificación: Narrowing = reducción + unificación Mediante esta herramienta podemos simular la resolución si consideramos las cláusulas de Horn como reglas de reescritura Podemos encontrar lenguajes como: BABEL TOY CURRY 2.2 Narrowing El procedimiento de narrowing puede verse como una extensión de la reducción utilizando la unificación. Por ejemplo, dadas las siguientes reglas: sum(0,Y) = Y sum(s(X),Y) = s(sum(X,Y)) sum(Z,W) puede reducirse vía narrowing a: W con la sustitución {Z/0} s(sum(V,W)) con la sustitución {Z/s(V)} Esto no podría realizarse con reducción, pues sum(Z,W) no empareja con la parte izquierda de ninguna regla 2.2 Narrowing El narrowing “tal cual”, tiene un grado de indeterminismo muy alto, debido a los dos grados de libertad que tiene asociados: Elección del subtérmino(redex) a reducir Elección de la regla Estos grados de libertad también aparecen en reescritura, pero en el narrowing se acentúan debido a la posibilidad de instanciar variables. La consecuencia es un espacio de búsqueda muy amplio. Se ha tratado de reducirlo mediante diferentes estrategias como (entre otras muchas): Narrowing perezoso Narrowing necesario 2.2 Narrowing En general las estrategias se pueden clasificar por la selección del termino a reducir que realizan: Dar prioridad a los subtérminos(redexes) mas internos: narrowing innermost. Estas estrategias se suelen llamar impacientes o voraces. Dar prioridad a los subtérminos(redexes) mas externos: narrowing outermost. Las estrategias de narrowing perezoso y narrowing necesario entrarían dentro de este grupo 2.2 Narrowing Narrowing perezoso Reduce las expresiones comenzando por las posiciones mas externas sobre las que se puede dar un paso de narrowing. Los pasos sobre posiciones mas internas solamente se realizan si son demandados y contribuyen a un paso de narrowing posterior sobre una posición mas externa 2.2 Narrowing * Narrowing perezoso Utiliza un mecanismo de unificación lineal, que difiere del estándar en que: una colisión entre un símbolo constructor y uno de operación, no se ve como un fracaso, sino como una demanda de una mayor evaluación de f (el símbolo de operación). Un símbolo de función se dice de operación si lo define alguna regla del programa, en otro caso es un constructor. 2.2 Narrowing Narrowing necesario El narrowing perezoso puede computar redexes que no son necesarios. El narrowing necesario se introdujo para evitar este problema: El narrowing necesario se basa en la selección de las posiciones necesarias más externas de un término, de modo que solamente se dan pasos inevitables para el cómputo de un resultado. 2.3 Metodologías y lenguajes Mecanismo operacional Lenguajes SLD + narrowing Alf, SLOG Traducción a Prolog (flattening) K-Leaf, Europa Resolución con unificación semántica (SLD-E) LPG SLD + residuación LeFun, Oz Needed narrowing + residuación Curry Lazy narrowing Babel, Toy 3. Lenguajes 3.1 CURRY El desarrollo de Curry es fruto de una iniciativa internacional que busca proporcionar una plataforma común para la investigación, enseñanza y aplicación de los lenguajes lógicos y funcionales. Integra características de los paradigmas: Funcional: funciones de orden superior, expresiones anidadas y evaluación perezosa. Lógico: variable lógica, estructuras de datos parciales, algoritmo de búsqueda intrínseco. Concurrente: evaluación concurrente de restricciones con sincronización en las variables lógicas. Además incorpora los dos principales mecanismos operacionales desarrollados en la integración lógicofuncional: el narrowing y la residuación. 3.1 CURRY Fruto de esto, tenemos ciertas ventajas sobre los lenguajes “puros”: Sobre los funcionales puros, tiene las ventajas del mecanismo de búsqueda y el procesamiento con información parcial. Sobre los lógicos puros, tiene la ventaja de una evaluación mas eficiente. Aparte de las comentadas anteriormente, encontramos otras características en el lenguaje, como: Entrada/Salida declarativa (monádica). Sistema de tipos con polimorfismo. Posibilidad de controlar el proceso de búsqueda, contando con varias estrategias predefinidas. La entidad operacional son las funciones definidas mediante ecuaciones (los predicados se consideran restricciones o funciones booleanas). 3.1 CURRY Semántica operacional Curry va calculando pares σ|e donde σ es una sustitución y e una expresión. Un par σ|e es una respuesta, si e es un dato (ej: una lista, un entero, etc). Si la expresión contiene variables libres, esta se reducirá a una disyunción de pares {σ1|e1, … σn|en}. En cada paso del proceso, se efectúa una reducción sobre una de las expresiones no resueltas.(Por ejemplo la primera por la izq) Si el paso es determinista la expresión se reduce a una nueva. Si el paso es indeterminista, el par se sustituirá por una disyunción de pares. 3.1 CURRY Por ejemplo, si tenemos las reglas: f0=2 f1=3 Al evaluar la expresión f 1, la respuesta será 3 Al evaluar la expresión f x, obtendremos la disyunción de pares: {x = 0}2 | {x=1}3 Luego vemos que las 2 expresiones están resueltas y devolvemos como resultado ambos pares 3.1 CURRY Debido a la existencia de variables libres, puede ocurrir que nos encontremos una en una posición que demande un valor (como en los argumentos de una función). Aquí tenemos dos formas de proceder: Retrasar el calculo de esa función hasta instanciar la variable (residuación) Sustituir la variables por los diferentes valores requeridos en esa posición, si fuese posible, y aplicar reducción (narrowing). El uso de una u otra alternativa dependerá de la expresión y las reglas definidas en el programa 3.1 CURRY Por ejemplo, supongamos las reglas: f0=2 f1=3 Para evaluar f x, aplicaríamos narrowing como ya vimos anteriormente Si tuviéramos una expresión aritmética, como 2+x, tendríamos que aplicar residuación. Supongamos la expresión 2+x=y && f x = y. La primera ecuación se suspendería y la segunda provocaría la aparición de dos pares: {x = 0}2+0=y && 2=y | {x = 1}2+1=y && 3=y Siguiendo la traza del primero, en el siguiente paso se unificaría y, resultando {x=0,y=2}2+0=2, que se evaluaría en el siguiente paso obteniendo {x=0,y=2}2=2, que finalmente se evaluaría, resolviendo por completo la expresión. La otra expresión se evaluaría igualmente obteniendo las dos soluciones a la expresión inicial. 3.2 λ-PROLOG λ-Prolog es un lenguaje de programación fundamentalmente lógico, pero que extiende a prolog con ciertas características nuevas. La estructura lógica puede verse como una extensión de la estructura de prolog en dos dimensiones: La extensión de primer orden a orden superior permite trabajar con variables de este tipo, cuantificadores y λ-términos La extensión de cláusulas de Horn a formulas hereditarias de Harrop permite el anidamiento de implicaciones y cuantificadores universales (lo que nos lleva a la programación modular, tipos abstractos de datos y razonamiento sobre hipótesis) 3.2 λ-PROLOG Encontramos las siguientes características nuevas respecto a prolog: Sistema de tipos polimórfico Notación parcializada Programación de orden superior Programación modular Uso de cuantificadores Tipos abstractos de datos Uso de λ-términos y lo que es más importante su unificación 3.2 λ-PROLOG Definición de tipos: Se realiza de manera similar a lo visto en Haskell, teniendo en cuenta que el tipo lógico se escribe “o”: type append list A -> list A -> list A -> o. type miembro A -> List A -> o. type suma int -> int -> int. Definición de listas: Difieren de los visto en Prolog, pues usan nil para referirse a la lista vacía y :: como constructor: type append list A -> list A -> list A -> o. append nil L L. append (X :: L) L2 (X :: L3) :- append L L2 L3. 3.2 λ-PROLOG Ejemplo de programación con funciones de orden superior: type map (A->B->o)->list A->list B->o. map P nil nil. map P (X::L) (Y:K) :- P X Y, map P L K. Donde la función puede ser un λ-término: type edad persona->int->o. edad pepe 23. edad ana 24. Edad jose 23. λPROLOG> map (λx. λy. (edad x y)) K (23::24::nil). K == (pepe::ana::nil); K == (jose::ana::nil). *Aunque la sintaxis sería x\t en lugar de λx.t 3.2 λ-PROLOG Ejemplo del uso de la unificación de segundo orden: Supongamos las siguientes reglas: type mapfun (A->B)->list A->list B->o. mapfun F nil nil. mapfun F (X::L) ((F X):K) :- mapfun F L K. type g int->int->int type a,b in Podemos escribir: λPROLOG> mapfun (λx.(g a x)) (a::b::nil) L. L == ((g a a)::(g a b)::nil). Mediante la unificación podemos reconstruir la función: λPROLOG> mapfun F (a::b::nil) ((g a a)::(g a b)::nil). F == (λx.(g a x)). 4. Conclusiones 4. Conclusiones Potencialmente ofrecen: Un soporte adecuado para el desarrollo rápido y a bajo coste de herramientas correctas Pero la realidad es que estos lenguajes no están suficientemente difundidos ni han logrado imponerse a nivel industrial. 4. Conclusiones Esto se debe, entre otras razones, a: Ausencia de un lenguaje lógico-funcional estándar o aceptado ampliamente por la comunidad. Carácter experimental de muchas implementaciones existentes Carencia de herramientas potentes que: Optimicen dichas implementaciones Asistan al programador 4. Conclusiones Hoy día, Curry es un lenguaje sobre el que hay un gran movimiento. Gran parte de los cursos y publicaciones sobre programación lógico-funcional lo usan como referencia y es usado en gran variedad de proyectos. Esto quizás se debe a la intención desde su concepción, de lograr convertirse en el lenguaje estándar de la programación lógico-funcional. Toy es otro de los lenguajes que siguen vivos (la versión 2.2.2 ha sido lanzada el 6-3-2006), y suele ser elegido lenguaje de referencia junto con Curry en bastantes cursos sobre programación lógico-funcional 4. Conclusiones Oz es otro de los lenguajes que cuentan con una comunidad activa alrededor, gracias en gran parte a Mozart, una plataforma de desarrollo de aplicaciones inteligentes y distribuidas sobre este lenguaje. Otros lenguajes como lambda-prolog mantienen un “nicho de aplicaciones”, como puede ser la demostración de teoremas, en los que son ampliamente utilizados. Por último decir que podemos encontrar un gran número de lenguajes, pero muchos de ellos no pasan de tener un carácter experimental con pocas aplicaciones y usos reales. 5. Bibliografía 5. Bibliografía Programación lógico-funcional Notas para la asignatura Programación declarativa avanzada. Blas C. Ruiz Jiménez Curso de doctorado: Programación en Internet con lenguajes declarativos multiparadigma. Pascual Julián Iranzo, Universidad de Castilla-La Mancha Programación Declarativa Multiparadigma. Francisco Javier López Fraguas, Universidad Complutense de Madrid A unified computation model for declarative programming. María Alpuente, Universidad Politécnica de Valencia 5. Bibliografía Programación lógico-funcional http://www.informatik.uni-kiel.de/~mh/FLP/ Michael Hanus, Universidad de Kiel (Alemania). Narrowing y residuación Depuración declarativa de programas lógico funcionales. Tesis de Fco José Correa Zabala, Universidad Politécnica de Valencia http://web.cecs.pdx.edu/~antoy/research/narrowi ng/FAQ.html Sergio Antoy, Portland State University. 5. Bibliografía Curry http://www.informatik.uni-kiel.de/%7Ecurry/ Universidad de Kiel Curry, an integrated functional logic language. Michael Hanus y asociados Curry, a tutorial introduction. Michael Hanus y Sergio Antoy λ-PROLOG λ-PROLOG, an introduction to the language and its logic. Dale Miller École Politecnique http://www.lix.polytechnique.fr/~dale/lProlog/ Dale Miller 5. Bibliografía Otros lenguajes Toy, a multiparadigm declarative language. Rafael Caballero, Jaime Sánchez y asociados, Universidad Complutense de Madrid http://www.fdi.ucm.es/profesor/fernan/toy/ Fernando Sáenz Pérez, Universidad Complutense de Madrid http://www.mozart-oz.org/ Life, a natural language for natural language. Hassan Aït-Kaci, Patrick Lincoln