Programación lógica
| ||||||
Programación lógica. Consiste en la aplicación del corpus de conocimiento sobre lógica para el diseño de lenguajes de programación; no debe confundirse con la disciplina de la lógica computacional. La programación lógica es un tipo de paradigmas de programación dentro del paradigma de programación declarativa. El resto de los subparadigmas de programación dentro de la programación declarativa son: programación funcional, programación basada en restricciones, programas DSL (de dominio específico) e híbridos. La programación lógica gira en torno al concepto de predicado, o relación entre elementos. La programación funcional se basa en el concepto de función (que no es más que una evolución de los predicados), de corte más matemático.
Sumario
Antecedentes
Históricamente, los ordenadores se han programado utilizando lenguajes muy cercanos a las peculiaridades de la propia máquina: operaciones aritméticas simples, instrucciones de acceso a memoria, etc. Un programa escrito de esta manera puede ocultar totalmente su propósito a la comprensión de un ser humano, incluso uno entrenado. Hoy día, estos lenguajes pertenecientes al paradigma de la Programación imperativa han evolucionado de manera que ya no son tan crípticos.
En cambio, la lógica matemática es la manera más sencilla, para el intelecto humano, de expresar formalmente problemas complejos y de resolverlos mediante la aplicación de reglas, hipótesis y teoremas. De ahí que el concepto de "programación lógica" resulte atractivo en diversos campos donde la programación tradicional es un fracaso. La lógica ha estado muy relacionada históricamente con las computadoras y los lenguajes de programación. Presentemos algunos ejemplos:
- Los circuitos de las computadoras son diseñados con la ayuda del álgebra booleana (George Boole)
- Datos y expresiones booleanos son usados en casi todos los lenguajes de programación para el control de acciones del programa.
- Proposiciones lógicas se han usado para describir formalmente la semántica de los lenguajes de programación, según el método axiomático que tuvo a Floyd y Hoare como iniciadores.
- Enunciados lógicos se usan para especificaciones formales que describen el comportamiento de un programa, lo que permite realizar sobre estas pruebas de corrección.
- Las computadoras han sido empleadas para implementar los principios de la lógica matemática, a través de sistemas de deducción automática y demostradores de teoremas.
- Enunciados lógicos vistos como un lenguaje de programación y ejecutados en la computadora.
Estos trabajos, iniciados por Robinson, Colmenaner y Kowalsky, condujeron al lenguaje Prolog.
La programación lógica implica forzosamente al uso de hechos y relaciones para representar la información y al de deducciones para responder a consultas. Las consultas permiten conocer informaciones sobre las relaciones. Estos dos aspectos reflejan una división de labores entre los programadores y un lenguaje para la programación lógica. El programador proporciona las reglas y los hechos, mientras que el lenguaje usa la deducción para dar respuesta a consultas. Esta división de labores es usualmente representado por la ecuación: algoritmo = lógica + control
La lógica se refiere a los hechos y reglas que especifican lo que realiza el algoritmo, y el control se refiere a cómo puede implementarse el algoritmo mediante la aplicación de reglas en un orden particular. El programador proporciona la parte lógica y el lenguaje de programación proporciona el control. Las consultas en los programas lógicos pueden usarse de dos formas: 1. Para determinar si un determinado conjunto de valores pertenece a una relación, en las cuales el intérprete responde Si, en caso de pertenecer la tupla, y Fracaso en caso de fracasar la deducción de una respuesta Si. 2. Para determinar una instancia de valores para cada una de las variables presentes en la consulta, que pueda deducirse a partir de las reglas y hechos del programa lógico.
A partir de 1970 se desarrollaron en la Universidad de Edimburg intérpretes eficientes de Prolog que aumentaron el interés en los sistemas de Programación Lógica. Campos de aplicación La programación lógica encuentra su hábitat natural en aplicaciones de inteligencia artificial o relacionadas:
- Sistemas expertos, donde un sistema de información imita las recomendaciones de un experto sobre algún dominio de conocimiento.
- Demostración automática de teoremas, donde un programa genera nuevos teoremas sobre una teoría existente.
- Reconocimiento de lenguaje natural, donde un programa es capaz de comprender (con limitaciones) la información contenida en una expresión lingüística humana.
- Etc.
La programación lógica también se utiliza en aplicaciones más "mundanas" pero de manera muy limitada, ya que la programación tradicional es más adecuada a tareas de propósito general.
Fundamentos
La mayoría de los lenguajes de programación lógica se basan en la teoría lógica de primer orden, aunque también incorporan algunos comportamientos de orden superior. En este sentido, destacan los lenguajes funcionales, ya que se basan en el cálculo lambda, que es la única teoría lógica de orden superior que es demostradamente computable (hasta el momento).
Lógica de primer orden
El cálculo de predicados de primer orden consta de un alfabeto y de dos clases de expresiones definidas a partir de los símbolos de este alfabeto, los términos y las fórmulas. El alfabeto del lenguaje consta de los siguientes conjuntos:
- V={ x, y, z, ....} cuyos elementos se denominan símbolos de variables (individuales).
- F={ f, g, h, ….} , donde cada elemento f es un símbolo funcional n-ario (n ≥ 0), por ejemplo sucesor(x). Si n = 0 el símbolo de función se denomina símbolo de constante. Las constantes m{as empleadas son true y false.
- R={ R, S, .....} , donde cada elemento R es un símbolo de relación n-aria ( n ≥ 0). Si n = 0 el símbolo de relación se denomina símbolo de constante proposicional o proposición.
d) Un conjunto finito de símbolos denominados operadores lógicos:
- : denominado negación,
- ∧ : denominado conjunción,
- ∨ : denominado disyunción,
- ⇒ : denominado implicación,
- ⇔: denominado bicondicional
y los operadores de cuantificación o cuantificadores:
- ∀(.) (denominado cuantificador universal) y
- ∃(.) (denominado cuantificador existencial).
Símbolos auxiliares de escritura. Términos Sea t una sucesión lineal finita de símbolos del alfabeto de L, entonces:
* Si t es una variable, entonces es un término. * Si f es un símbolo de función n-aria (n ≥ 0) y tl,t2,...,tn son términos,entonces f( tl,t2, ,tn) un término.
Ejemplos x, a, f(x), g(a, f(b)) son términos
En consideraciones posteriores jugará un papel importante una clase de términos denominados listas, que en la programación lógica se presenta con la notación: [ t1, t2, ..., tn ]
con cabeza t1 el car y cola [ t2, ..., tn].
La lista [X|Y] se denomina una lista patrón o un esquema de lista que denota cualquier lista con un primer elemento X y resto Y.
Ejemplos [1, 2, 3] [a, 3, [3], [[3]]] [[X, Y|[2,3]] [[X|Y], Z, [X|W]]
Fórmulas.
- Si R es un símbolo relacional n-ario ( n ≥ 0 ) y tl,t2,...,tn son términos, entonces R(t1,t2,...,tn) es una fórmula elemental o átomo.
- Si A es una fórmula elemental, entonces A es una fórmula.
- Si A es una fórmula, entonces A es una fórmula.
- Si A y B son fórmulas, entonces [A ∨ B], [A ∧ B], [A=>B] y [A <=> B] son fórmulas.
- Si A es una fórmula, entonces ∀(x)A y ∃(x)A son fórmulas.
- En ∀(x)A (∃(x)A), A se denomina el alcance del cuantificador ∀(x) (∃(x)).
- Si x es una variable que ocurre en la fórmula A, entonces se dice que x está acotada o ligada en A, si A es el alcance del cuantificador ∀(x) (∃ (x)).
Si x es una variable que ocurre en la fórmula A, entonces se dice que x es libre en A si x no está acotada en A.
Si x no ocurre libre en A, entonces ∀(x)A (∃(x)A) es simplemente la fórmula A. Una fórmula es una fórmula cerrada o un enunciado si no contiene ocurrencia alguna de variable libre. Si tiene ocurrencia de variables libres se llama predicado. El cálculo de predicados posee un grupo de reglas de inferencia que permite deducciones a partir de axiomas y teoremas previamente demostrados. La esencia de la programación lógica es consistir de una colección de enunciados asumidos como axiomas y derivar un hecho deseado aplicando reglas de inferencia de forma automática. Un lenguaje de programación lógica es un sistema notacional para escribir enunciados lógicos junto con algoritmos para implementar reglas de inferencia.
” El conjunto de enunciados lógicos que son asumidos como axiomas constituyen el programa lógico.” Los enunciados que deben ser derivados, que pueden ser vistos como entradas que desencadenan el cálculo son las demandas o metas.
Por ello los sistemas de programación lógica son llamadas bases de datos deductivas, en el sentido de volúmenes de datos que consisten de un conjunto de enunciados y un sistema de deducción que responde a demandas En qué consiste (ejemplo) La programación lógica permite formalizar hechos del mundo real, por ejemplo:
las aves vuelan los pingüinos no vuelan "pichurri" es un ave "sandokan" es un perro "alegría" es un ave
y también reglas o restricciones:
una mascota vuela si es un ave y no es un pingüino
Ante dicho "programa" es posible establecer hipótesis que no son más que preguntas o incógnitas, por ejemplo:
¿ "pichurri" vuela ? ¿ qué mascotas vuelan ?....
Gracias a que la lógica de primer orden es computable, el ordenador será capaz de verificar la hipótesis, es decir, responder a las incógnitas:
Es cierto que "pichurri" vuela. "pichurri" y "alegría" vuelan.
Obsérvese que el programa lógico no solamente es capaz de responder si una determinada hipótesis es verdadera o falsa. También es capaz de determinar que valores de la incógnita hacen cierta la hipótesis. Este ejemplo es claramente académico. Sin embargo, consideremos el siguiente ejemplo: el sistema de control de semáforos de una ciudad. El estado de cada uno de los semáforos (verde, rojo o ámbar) constituye los hechos del mundo real. El programa en sí consiste en unas pocas reglas de sentido común: determinados semáforos no pueden permanecer simultáneamente en verde, un semáforo solamente puede transitar de verde a ámbar y de ámbar a rojo, etc. La hipótesis es el estado en el que deberían estar cada uno de los semáforos en el siguiente instante de tiempo. Éste es un ejemplo imposible de resolver mediante programación tradicional, ya que la lógica subyacente al comportamiento de los semáforos en su conjunto queda enmascarada por simples órdenes imperativas del tipo "cambiar color de tal o cual semáforo".
Entornos de desarrollo
El lenguaje de programación lógica por excelencia es Prolog, que cuenta con diversas variantes. La más importante es la programación lógica con restricciones (véase artículo sobre programación con restricciones), que posibilita la resolución de ecuaciones lineales además de la demostración de hipótesis.
Bibliografía
Las siguientes referencias bibliográficas corresponden a literatura en inglés:
- Foundations of Logic Programming, J.W. Lloyd, Springer-Verlag, 1991.
- Essentials of Logic Programming, C. Hogger, Clarendon Press, Oxford, 1990.
- Logic for Computer Science: Foundations of Automatic Theorem Proving, J.H. Gallier, John Wiley and Sons, 1987.
Existen pocas referencias a literatura en castellano:
- Lógica Informática, J. Cuena, Editorial Alianza, 1985.
- Programación Lógica. Teoría y Práctica, P. Julián, M. Alpuente, Pearson Prentice Hall, 2007.
Este último sea posiblemente el mejor libro de programación lógica en español, ya que también contiene las bases de lógica matemática.
Véase también
- Paradigma de programación.
- Programación con restricciones.
- Programación funcional.
- Lógica matemática.
