Download Integración de los paradigmas lógico y funcional

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