PDF de programación - Otros lenguajes lógicos además de Prolog

Otros lenguajes lógicos además de Prolog



Inteligencia en redes de comunicaciones



Otros Lenguajes Lógicos

además de Prolog



Eduardo Fernández Matamala

Inteligencia en Redes de Comunicación



La programación lógica es aquel tipo de programación que permite al software

“razonar”, esto es, hacer razonamientos, por ejemplo, de tipo deductivo o inductivo.
Dada una base de datos consistente en un conjunto de entidades, propiedades de esas
entidades y relaciones de unas entidades con otras, el sistema es capaz de hacer
razonamientos. Básicamente, este proceso se expresa de la siguiente forma:



Resultados = reglas + hechos



Donde entendemos que “hechos” es el conjunto de datos que conoce el sistema a
priori(o que va adquiriendo a lo largo de su ejecución) y “reglas” son un conjunto de
operaciones que se pueden aplicar a dichos datos para sacar un resultado lógico.



Algunos campos donde este tipo de lenguajes es aplicado son en la
implementación de Sistemas Expertos (programas que generan una respuesta o una
recomendación sobre el tema para el que están implementados) o para la Generación de
Nuevos Teoremas (dadas una serie de reglas, generan teoremas)


Lenguajes Lógicos

ALF (Another logical framework)


Este lenguaje combina la programación lógica con la programación funcional
(funcional – basado en la evaluación de expresiones y funciones matemáticas más que
en la utilización de comandos como <alloc>, <malloc>…).

Al igual que Prolog, ALF esta basado en “cláusulas de Horn” (por eso es

programación lógica) pero también en funciones y ecuaciones (y por esto es también



- 1 -

Eduardo Fernández Matamala

Otros lenguajes lógicos además de Prolog



Inteligencia en redes de comunicaciones

programación funcional). En ALF, se puede mezclar expresiones y ecuaciones; puedes
poner una expresión funcional como si fuese un predicado y cualquier predicado puede
ser introducido como condición en cualquier ecuación.


La base del procesamiento de ALF es “resolution-narrowing-rewriting-
rejection”. ALF usa reglas de resolución para evaluar los literales y reglas de
“estrechamiento”( “narrowing”) para evaluar las expresiones funcionales. Esto lo hace
buscando en un árbol, que es una representación del lenguaje. Como el proceso de
“narrowing” puede ser largo, se usan técnicas de “leftmost-innermost basic narrowing”,
que son más eficientes (“el final de la expresión que se evalúa primero siempre es un
cierre de paréntesis, el primer cierre y después de evaluar esta expresión, se sustituye
todo él por el resultado al que se ha llegado, y se sigue procesando el siguiente
paréntesis”). Además, las expresiones sufren un proceso de reescritura (“rewriting”)
antes de ser procesadas por las reglas de “narrowing” y las ecuaciones cuyos dos lados
de la igualdad no tengan el mismo nodo como origen son rechazadas (“rejected”). Estos
dos pasos previos, hacen que la búsqueda sea mucho más eficiente. Además ALF usa
”backtracking” con búsqueda en profundidad en el árbol de derivaciones.



Ejemplo de “narrowing”:

Se definen las reglas: s(M)+N=s(M+N)) ; 0+N=N ;
Tenemos la expression: X + s(0) = s(s(0))
Primer paso de narrowing:

Si X=s(Y) S(Y+s(0)) = s(s(0))
Segundo paso de narrowing: (unificación)

Y+s(0) = s(0) Y=0 Solución: X=s(0)



Los programas escritos en ALF, se compilan y dan lugar a una serie de
instrucciones de una máquina virtual basada en Warren Abstract Machine (WAM) con
múltiples extensiones para soportar “narrowing and rewriting”. Actualmente, esta
máquina virtual es un emulador y su implementación está basada en C.


sus funciones y modificarlo a su gusto.


librería predefinida, en el que se define lo que es un vector y suspropiedades.


Este lenguaje es “open Source”, por lo que cualquier usuario puedo introducir

Aquí tenemos un ejemplo de este lenguaje. En este caso, es un archivo de la



- 2 -

Eduardo Fernández Matamala

Otros lenguajes lógicos además de Prolog



Inteligencia en redes de comunicaciones

Como curiosidad, se puede destacar que este lenguaje no funciona en un entorno

Ejemplo: Máximo Común Divisor



Gödel es un lenguaje en el que las sentencias lógicas llevan un orden y en el que


Gödel programming language


existe el polimorfismo.

Está basado en módulos (que aceptan polimorfismo) y en tipos de datos (soporta

enteros y racionales con una precisión infinita, y número en coma flotante) y tiene una
amplia librería de módulos predefinidos.


Es un buen lenguaje para tareas de meta-programación, tales como compilación,
depuración, análisis, verificación o transformación de programas, ya que es mucho más
declarativo que Prolog, por ejemplo.


Windows.


MODULE GCD.

IMPORT Integers.

PREDICATE Gcd : Integer * Integer * Integer.

Gcd(i,j,d) <-
CommonDivisor(i,j,d) &
~ SOME [e] (CommonDivisor(i,j,e) & e > d).

PREDICATE CommonDivisor : Integer * Integer * Integer.

CommonDivisor(i,j,d) <-
IF (i = 0 \/ j = 0)
THEN
d = Max(Abs(i),Abs(j))
ELSE
1 =< d =< Min(Abs(i),Abs(j)) &
i Mod d = 0 &
j Mod d = 0.



- 3 -

Eduardo Fernández Matamala

Otros lenguajes lógicos además de Prolog



Inteligencia en redes de comunicaciones

Mercury programming language


Mercury es un lenguaje de alto nivel (es decir, no se preocupa de problemas
como la reserva y liberación de memoria) derivado de Prolog, pero con una
implementación que le hace ser más útil para representar y tratar problemas del mundo
real. Combina toda la expresividad del lenguaje declarativo con avanzadas técnicas de
análisis estático y detección de errores. Es un lenguaje compilado, lo que le permite
detectar numerosos errores antes de poder ejecutar la aplicación. El compilador
“traduce” el programa de lenguaje Mercury a C, que es un lenguaje portable a cualquier
plataforma. Además, al igual que el lenguaje de Gödel, Mercury es un lenguaje que
utiliza módulos, lo que da una gran modularidad en el desarrollo de aplicaciones,
solventando así uno de los mayores problemas a los que se enfrentaban los lenguajes de
programación lógicos.



Las principales características de Mercury son:

• Es puramente declarativo los predicados y funciones en Mercury

siempre obtienen conclusiones lógicas

• La comunicación con el programa es mediante una librería de funciones
que necesitan como parámetro el estado anterior del “mundo” además del
resto de parámetros que considere el usuario necesario y dan como salida
el nuevo estado del “mundo” además de otros resultados específicos.

• La declaración de tipos en Mercury se hace de manera lógica:


:- type maybe(T) ---> yes(T) ; no.


• Se puede predeterminar el número de veces que se va a llamar a un

predicado dentro del programa.

:- pred factorial(int::in, int::out) is det.



“det” indica una vez, “semidet” como mucho una vez, “multi” al menos
una vez y “nondet” un número arbitrario de veces
El compilador comprobará que se cumple y, en caso contrario, rechazará
el programa

• Mercury tiene un sistema modular. Los programas consisten en la
composición de uno o más módulos. Cada módulo tiene una sección
llamada <interface> donde se declaran todos los tipos, funciones y
predicados que se pueden exportar a otros módulos y otra sección
<implementation> donde están
las entidades
exportadas así como definiciones de tipos y predicados no exportables,
locales al módulo.

las definiciones de

• El compilador genera código muy eficiente


La última versión estable de Mercury es la 0.11.0, aunque ya hay una versión



beta estable, la 0.11.1 (2004-06-30)


Ejemplo: HolaMundo



- 4 -

Eduardo Fernández Matamala

Otros lenguajes lógicos además de Prolog



Inteligencia en redes de comunicaciones

:- module hello_world.

:- interface.
:- import_module io.

:- pred main(io__state, io__state).
:- mode main(di, uo) is det.

:- implementation.
main -->
io__write_string("Hello, World!\n").



Lista de lenguajes lógicos


Otro ejemplo: Problema de las 9 Reinas



Código En Mercury aquí
Código generado por el compilador Mercury aquí

Es una implementación de Prolog, pero que soporta una arquitectura

• ACE, PALS: And/Or-Parallel Implementation of Prolog

multiprocesador
http://www.cs.nmsu.edu/lldap/NewSite/bugrep.htm

• Actor Prolog

http://www.cplire.ru/Lab144/


• ALF

http://www.cs.chalmers.se/Cs/Research/Logic/alf/guide.html


• CLP(FD)
Otra extensión de Prolog, especializado en los problemas CSPs (Constraint
Satisfaction Problem)
De forma general, podemos decir que un programa en CLP(FD) consta de tres
partes: “generación de variables” (donde también se especifica su domino),
“definición de restricciones” (sobre las variables) y “labeling”, donde se instancian
las variables por enumeración.

Ejemplo: SEND MORE MONEY puzzle


sendmory(Vars):-
Vars=[S,E,N,D,M,O,R,Y], % variable generation
Vars :: 0..9,
alldifferent(Vars), % constraint generation
S #\= 0,
M #\= 0,
1000*S+100*E+10*N+D
+ 1000*M+100*O+10*R+E
#= 10000*M+1000*O+100*N+10*E+Y,
labeling(Vars). % labeling


• cu-Prolog



- 5 -

Eduardo Fernández