La programación lógica es especialmente adecuada para problemas de satisfacción de restricciones (NB, no es lo único para lo que es bueno).
Los programas que emplean el paradigma lógico son muy altos en la escala declarativa (con lenguaje ensamblador o C en el otro extremo, imperativo). Como tales, son muy adecuados para la representación del conocimiento y la respuesta a preguntas. Considere el siguiente Prolog muy simple:
/ * Algunos conocimientos básicos * / / * niño madre padre * / padres (sonny, nancy, bobby). padres (mandy, nancy, bobby). padres (miley, nancy, bobby). padres (nancy, macey, harry). padres (bobby, jenny, billy). hombre (sonny) hombre (bobby). hombre (harry) hombre (billy). mujer (nancy) hembra (mandy) hembra (macey) hembra (jenny) hembra (miley) amores (sonny, juegos). amores (bobby, juegos). amores (bobby, dulces). amores (mandy, dulces). / * Alguna lógica * / hermanos (X, Y): - padres (X, M, F), padres (Y, M, F), X / = Y. hermana de (S, X): - hermanos (S, X), hembra (S). hermano de (B, X): - hermanos (B, X), hombre (B).
Ahora podemos hacer preguntas.
- ¿Qué algoritmo de extracción de características es adecuado para el reconocimiento facial basado en video?
- ¿Dónde puedo encontrar una comprensión realmente fácil y rápida de todas las estructuras de datos y algoritmos?
- Cómo multiplicar elementos de matriz sin usar bucle
- ¿Cómo se compara la recomendación de amigos de Facebook con las personas de LinkedIn que quizás conozcas?
- ¿Cómo se les ocurrió el algoritmo de MD5?
/ * ¿Quién es la hermana de sonny? * / ? - hermana de (X, sonny). X = mandy / * ¿Sonny es el hermano de mandy? * / ? - hermano de (sonny, mandy). cierto / * ¿Quién es un hermano de miley al que le gustan los dulces? * / ? - sisterof (S, miley), likes (S, candy). S = mandy
Como puede verse, “descifra” lógicamente el valor de las incógnitas.
Una aplicación exitosa que emplea Prolog es Watson, la computadora de preguntas y respuestas de IBM (compañía). Ver
Paul Fodor, Adam Lally, David Ferrucci. La interfaz de Prolog a la arquitectura de gestión de información no estructurada.
http://arxiv.org/abs/0809.0680
para detalles.
A pedido de Toby Thain (en comentarios), aquí hay un ejemplo menos trivial.
Escribamos un analizador para autómatas deterministas generales de estado finito (DFA).
Cada estado en un DFA está numerado del 0
al número máximo de estados. Para analizar una oración en un idioma, escribimos el idioma como una lista de términos L
El resultado del análisis se representa comenzando en el estado initial(S)
denotado por initial(S)
, y luego viajando al siguiente estado desde S
acuerdo con L
y las reglas del lenguaje.
analizar (L): - inicial (S), viaje (S, L).
Las reglas para viajar son un conjunto de “transiciones”, denotadas por trans(From, X, To)
, que representa pasar del estado From
estado To
, pasando por el símbolo X
del lenguaje.
Quitamos el primer símbolo de la oración que estamos analizando, aplicamos la transición (si existe) y viajamos al nuevo estado después de la transición.
recorrido (X, [A | B]): - trans (X, A, Y), recorrido (Y, B).
Cuando nuestra oración está vacía, deberíamos estar en el estado final indicado por la terminal(S)
; en este caso, X
recorrido (X, []): - terminal (X).
¡Hemos terminado! Pongamos esto en uso. Necesitamos hacer reglas para un idioma. Consideremos b*a+b(a|b)*
. El diagrama de transición se ve así:
Entonces tenemos tres estados, donde el estado inicial es 0
y el estado terminal es 2
(el círculo doble). Las reglas se codifican fácilmente:
trans (0, a, 1). / * Debemos tener 'a' para llegar al estado # 1 * / trans (0, b, 0). / * Podemos tener 'b' en el estado # 0 * / trans (1, a, 1). / * Podemos tener 'a' en el estado # 1 * / trans (1, b, 2). / * Debemos tener 'b' para llegar al estado # 2 * / trans (2, a, 2). / * Podemos tener 'a' en el estado # 2 * / trans (2, b, 2). / * Podemos tener 'b' en el estado # 2 * /
Y, por supuesto, definimos los nodos inicial y terminal:
inicial (0). terminal 2).
Y hemos definido el lenguaje. Ahora podemos analizar. Aquí hay ejemplos
? - parse ([b, b, b, a, a, b, a, b, b]). cierto ? - analizar ([b, b, a, a]). falso
Y claramente estos son correctos.