miércoles, 27 de febrero de 2013

Programación Lógica


Por cortesía de Mente Errabunda;

Se puede tomar al gran filósofo Aristóteles (384-322 a.C.) con su teoría silogística como el gran precursor de la lógica matemática y en consecuencia de la programación lógica. La teoría silogística, que estudia una clase particular de implicaciones con dos premisas y una conclusión, también fue tratada por filósofos contemporáneos de Aristóteles y fue largamente estudiada en siglos posteriores, aunque no se produjeron innovaciones de interés hasta el siglo XVII con los trabajos realizados por Descartes y Leibnitz. Dos siglos después George Boole dio un paso importante en el sistema de razonamiento aristotélico poniendo en relación la lógica y el algebra. Los trabajos de Boole fueron modificados y ampliados mas tarde por lógicos y matemáticos como Jevon, Pierce, Schroeder y Huntington entre otros. Se llega así a finales del siglo XIX y principios del XX con la revolución en el fundamento de las matemáticas gracias a los trabajos de Frege, Cantor, Peano, Russell y Whitehead entre otros que marcan el periodo más apasionante y de mayor actividad en la historia de la lógica matemática.

En el primer tercio del siglo XX y tras la publicación de los “Principia Matemática” por parte de Russell y Whitehead continuo la actividad frenética de innovación de la mano de investigadores de la talla de Post, Hilbert, Ackerman, Broker, Godel y por supuesto Skolem y Herbrand. Llegada la mitad del siglo XX, de manera paralela al desarrollo de la lógica, se produce un espectacular avance de las llamadas “maquinas de calcular”, avance sobre el que reflexiona Alan Turing en un artículo titulado: “¿Pueden pensar las máquinas?”, publicada en 1950 y que constituye el punto de partida del área que revoluciona los sistemas inteligentes, conocida como inteligencia artificial. En los años siguientes a la publicación del artículo de Turing, avanzó bastante la demostración automática con trabajos como los de Gilmore, Davis, Putnam y Prawitz, tomando siempre como referencia los trabajos de Skolem y Herbrand relacionados con la lógica de primer orden.

Un hito importante en la historia de la demostración automática la marco Robinson en 1965 con la presentación de su método de resolución, punto de partida para los trabajos de otros investigadores como Chang, Lee, Loveland y Wos. No obstante no es hasta la primera mitad de los años 1970, con los trabajos de Kowalsky y el primer lenguaje de programación Prolog de Colmerauer, cuando nace la programación lógica como rama de la demostración automática con personalidad propia. En palabras de Kowalski y Hogger se mencionaba en ese entonces: “La programación lógica puede ser brevemente definida como el uso de la lógica simbólica para la representación de problemas y sus bases de conocimiento asociadas, junto con el control de la inferencia lógica para la solución efectiva de esos problemas”

La programación lógica, junto con la funcional, forma parte de lo que se conoce como programación declarativa. En los lenguajes tradicionales, la programación consiste en indicar cómo resolver un problema mediante sentencias agrupadas en un algoritmo; en la programación lógica, se trabaja de una forma descriptiva, estableciendo relaciones entre entidades, indicando no cómo, sino qué hacer. La ecuación de Robert Kowalski de la Universidad de Edimburgo, establece la idea esencial de la programación lógica: “programa=lógica+control”. Es decir, un programa se construye especificando conocimiento en un lenguaje formal, tal como la lógica de primer orden, y el problema se resuelve mediante un mecanismo de inferencia o control que actúa sobre dicho programa.

La 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. Se ha convertido en el pilar de una nueva generación de lenguajes de programación. Junto con la programación funcional forma parte de lo que se conoce como programación declarativa. La programación declarativa 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. En los lenguajes tradicionales se intenta resolver un problema mediante sentencias, en la programación lógica se trabaja de forma descriptiva, estableciendo relaciones, y no indicando un cómo sino un qué hacer. Es decir el programa que se quiera diseñar se construye especificando un conocimiento en un lenguaje formal y para resolverlo se utiliza la inferencia o control que actúa sobre el mismo.

Históricamente, las computadoras 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. Actualmente, estos lenguajes pertenecientes al paradigma de la programación imperativa han evolucionado de manera que ya no son tan críticos. 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 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, por lo menos hasta el momento. El lenguaje de programación lógica por excelencia es el “PROLOG”, que cuenta con diversas variantes. La más importante es la programación lógica con restricciones, que posibilita la resolución de ecuaciones lineales además de la demostración de hipótesis.

La programación lógica permite formalizar hechos del mundo real, por ejemplo: (1) las aves vuelan; (2) los pingüinos no vuelan; (3) “calita” es un ave; (4) “aceituno” es un perro; (5) “alegría” es un ave. Además formaliza reglas o restricciones: (1) una mascota vuela si es un ave y no es un pingüino. Ante dicha regla o “programa” es posible establecer hipótesis que no son más que preguntas o incógnitas, por ejemplo: (1) ¿”aceituno” vuela?; (2) ¿qué mascotas vuelan?. Gracias a que la lógica de primer orden es computable, la computadora será capaz de verificar la hipótesis, es decir, responder a las incógnitas: (1) Es cierto que “calita” vuela; (2) “calita” y “alegría” vuelan. Observe 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.

El anterior ejemplo es claramente académico y quizá un poco complicado de entender. Sin embargo, considere el siguiente ejemplo relacionado con el sistema de control de semáforos de la ciudad de La Paz. 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 cuantas 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 bastante complicado 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”.

La programación lógica encuentra su hábitat natural en aplicaciones de inteligencia artificial u otras aplicaciones relacionadas, entre las que destacan: (1) Sistemas expertos, donde un sistema de información imita las recomendaciones de un experto sobre algún dominio de conocimiento. (2) Demostración automática de teoremas, donde un programa genera nuevos teoremas sobre una teoría existente. (3) Reconocimiento de lenguaje natural, donde un programa es capaz de comprender (con limitaciones) la información contenida en una expresión lingüística humana. 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 dichas tareas de propósito general.

No hay comentarios: