Paradigma de Programación Logica ¶

Contenido¶

1. Introducción
   • Paradigma de programación
   • Historia
   • Filosofía del paradigma.
2. Programación Lógica
   • ¿Qué es?
   • Conceptos claves
   • Ventajas y Desventajas
   • Lenguajes de Programación
   • Aplicaciones

Introducción¶

Paradigma de programación:¶

-Concepts, Techniques, and Models of Computer Programming.

Indica un método mediante el cual se deben resolver uno a varios problemas claramente delimitados.

Representa un enfoque particular o filosofía para diseñar soluciones.

Imperativo vs Declarativo:¶

Dentro de los paradigmas de programación existen 2 grandes gurpos: que son los Declarativos y los Imperativos. Las características principales de ellos se ven en el siguiente gráfico.

Los desarrolladores web, pasan sus días dando instrucciones a las computadoras. Estas instrucciones generalmente implican algo de entrada (ej. una solicitud de una página web), algo de lógica (ej. obtener el contenido correcto de una base de datos) y algo de salida (ej. enviar el contenido al navegador solicitante). Este proceso de decir a un ordenador cómo realizar una tarea, es lo que comúnmente llamamos "programación", pero es sólo un subconjunto de programación: la programación imperativa.

Hay otro tipo de programación, la programación declarativa. Con la programación declarativa decimos a una computadora qué, no cómo realizar una tarea. Describimos el resultado que queremos y los detalles de cómo lograrlo se dejan al intérprete de lenguaje. Este cambio sutil en el enfoque de la programación tiene amplios efectos sobre la forma en la cual construimos software.

Los lenguajes declarativos tienden a desvanecerse en el fondo de la programación, en parte porque están más cerca de cómo interactuamos naturalmente con la gente. Si estás hablando con un amigo y quieres un sándwich, normalmente no le das a tu amigo instrucciones paso a paso sobre cómo preparar el sándwich. Si lo hiciera, se sentiría como la programación de su amigo. En cambio, es mucho más probable que hable sobre el resultado que desea, como "Por favor, hazme un sandwich" (o, tal vez, "Sudo hazme un sandwich"). Si su amigo está dispuesto y es capaz de seguir esta instrucción, entonces traducirán la frase "Hazme un sandwich" en una serie de pasos, como encontrar un pan, quitar dos rebanadas, aplicar coberturas, etc.

Historia¶

Uno de los precursores de la lógica matemática y en consecuencia de la Programación lógica fue Aristóteles (384-322 a.C.) con su teoría silogística. Esta teoría estudia una clase particular de implicaciones con dos premisas y una conclusión. También fue tratada por los filósofos contemporáneos a Aristóteles y largamente estudiada en siglos posteriores, aunque no se produjeron innovaciones de interés hasta el siglo XVII con los trabajos de Descartes y Leibnitz.

Dos siglos después Boole dio un paso importante en el sistema de razonamiento aristotélico poniendo en relación la lógica y el álgebra. Los trabajos de Boole fueron modificados y ampliados mas tarde por los lógicos y matemáticos como Jevon, Pierce, Schroeder y Huntington, entre otros.

Llegamos así a finales del siglo XIX y principios del XX con la revolución de la fundamentacion de las Matemáticas gracias a los trabajos de Frege, Cantor, Peano, Russell, Whitehead, entre otros, que marcan el periodo más apasionante y de mayor actividad en la historia de la lógica matemática.

En la mitad del siglo XX descubrimos que de forma paralela al desarrollo de la lógica se ha producido un espectacular avance de las llamadas “máquinas de calcular”, avance sobre el que reflexiona Alan Turing en un articulo titulado “¿Pueden pensar las máquinas?”, publicado en 1950 y que podemos dar como punto de partida de lo que después se llamará Inteligencia Artificial.

El primer momento en el que se usa la lógica matemática para representar y ejecutar programas es en 1930 cuando aparece como una caracteristica de los cálculos lamba desarrollados por Allonzo Church.

Sin embargo, la primera propuesta para usar la forma causal de la lógica para representar programas de cómputo fue propuesta por Cordell Green en 1969. Esto utilizó una axiomatización de un subconjunto de LISP(es una familia de lenguajes de programación de computadora de tipo multiparadigma con una larga historia y una sintaxis completamente entre paréntesis), junto con una representación de una relación de entrada-salida, para calcular la relación simulando la ejecución del programa en LISP.

Por otro lado, Fyster y Elcock's Absys emplearon una combinación de ecuaciones y cálculos lamba en un lenguaje de programación asercional que no impone restricciones en el orden en que se realizan las operaciones.

A principios de los 70's en la Universidad de Aix-Marseille I (Marsella, Francia) fue ideado un lenguaje de programación por los estudiantes Alain Colmerauer y Philippe Roussel. Éste nació de un proyecto que no tenía como objetivo la traducción de un lenguaje de programación, sino la clasificación algorítmica de lenguajes naturales. Alain Colmerauer y Robert Pasero trabajaban en la parte del procesado del lenguaje natural y Jean Trudel y Philippe Roussel en la parte de deducción e inferencia del sistema. Interesado por el método de resolución SL, Trudel persuadió a Robert Kowalski para que se uniera al proyecto, dando lugar a una versión preliminar del lenguaje Prolog a finales de 1971 y apareciendo la versión definitiva en 1972. Esta primera versión de Prolog fue programada en ALGOL W.

A Finales de los 70's Robert Kowalski crea el método de prueba por refutación que emplea el algoritmo de unificación como mecanismo de base y permite la extracción de respuestas SLD (Selective Linear Definite clause resolution).

Inicialmente se trataba de un lenguaje totalmente interpretado hasta que en 1983, David H.D. Warren desarrolló un compilador capaz de traducir Prolog en un conjunto de instrucciones de una máquina abstracta denominada Warren Abstract Machine, o abreviadamente, WAM. Desde entonces Prolog es un lenguaje semi-interpretado.

Filosofia del paradigma¶

La mayoría de los Lenguajes de Programación 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 Calculo Lambda, es la única teoría lógica de orden superior.

"Aplicación de reglas de la lógica para inferir conclusiones a partir de datos."¶

Programación Lógica¶

¿Qué es?¶

Paradigma de programación basado en la lógica de primer orden. La Programación Lógica estudia el uso de la lógica para el planteamiento de problemas y el control sobre las reglas de inferencia para alcanzar la solución automática.

La Programación Lógica, junto con la funcional, forma parte de lo que se conoce como Programación Declarativa, es decir la programación consiste en indicar como resolver un problema mediante sentencias, en la Programación Lógica, se trabaja en una forma descriptiva, estableciendo relaciones entre entidades, indicando no como, sino que hacer, entonces se dice que la idea esencial de la Programación Lógica es

Se puede ver como una deducción controlada.

Lógica (programador): hechos y reglas para representar conocimiento

Control (interprete): deducción lógica para dar respuestas (soluciones)

La programación lógica intenta resolver lo siguiente:¶

Dado un problema S, saber si la afirmación A es solución o no del problema o en que casos lo es. Además queremos que los métodos sean implantados en maquinas de forma que la resolución del problema se haga de forma automática

La programación lógica: construye base de conocimientos mediante reglas y hechos.

Características del Paradigma¶

• Unificación de términos
• Mecanismos de inferencia automática
• Recursion como estructura de control básica
• Visión lógica de la computación

Lógica Proposicional¶

También llamada lógica de enunciados: toma como elemento básico las frases declarativas simples o proposiciones. Su estructura está dada por:

Es un sistema formal cuyos elementos más simples representan proposiciones, y cuyas constantes lógicas, llamadas conectivas lógicas, representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.

La lógica proposicional trata con sistemas lógicos que carecen de cuantificadores, o variables interpretables como entidades. En lógica proposicional si bien no hay signos para variables de tipo entidad, sí existen signos para variables proposicionales (es decir, que pueden ser interpretadas como proposiciones con un valor de verdad definido), de ahí el nombre proposicional. La lógica proposicional incluye además de variables interpretables como proposiciones simples signos para conectivas lógicas, por lo que dentro de este tipo de lógica puede analizarse la inferencia lógica de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples.

Proposiciones: Elementos de una frase que constituyen por sí solos una unidad de comunicación de conocimientos y pueden ser considerados verdaderos o falsos.

Proposición Simple: “Pepito es humano”.

Proposición Compuesta: “Pepito es hombre y pepita es mujer”.

Lógica de primer orden¶

También llamada lógica de predicados: es un sistema deductivo basado en un Lenguaje Lógico Matemático formal. Su estructura esta dada por:

Incluye proposiciones lógicas, predicados y cuantificadores.

Más expresiva de la Lógica proposicional.

• ¿Qué se afirma? (predicado o relación)
• ¿De quién se afirma? (objeto)

Es un sistema formal diseñado para estudiar la inferencia en los lenguajes de primer orden.1 Los lenguajes de primer orden son, a su vez, lenguajes formales con cuantificadores que alcanzan sólo a variables de individuo, y con predicados y funciones cuyos argumentos son sólo constantes o variables de individuo. La lógica de primer orden tiene el poder expresivo suficiente para definir a prácticamente todas las matemáticas.

Cláusulas de Horn¶

Secuencia de literales que contiene a lo sumo uno de sus literales positivos (disyunción de literales). Esto es un ejemplo de una cláusula de Horn, y abajo se indica una fórmula como esta también puede reescribirse de forma equivalente como una implicación:

• Cláusula ‘definite’: Cláusula de Horn con exactamente un literal positivo.
• Hecho: Cláusula ‘definite’ sin literales negativos.
• Cláusula objetivo: Sin ningún literal positivo. (consulta)

En Prolog Se escribe primero el consecuente luego el antecedente.

Ej: Estructura de clúasulas de Horn

Resolución SLD (Selective Linear Definite clause resolution)¶

El nombre "SLD resolution" fue dado por Maarten van Emden para la regla de inferencia sin nombre introducida por Robert Kowalski. Su nombre deriva de la resolución de SL, que es a la vez sonido y refutación completa de la forma clausal sin restricciones de la lógica. "SLD" significa "SL resolution with Definite clauses".

En ambos, SL y SLD, "L" representa el hecho de que una prueba de resolución se puede restringir a una secuencia lineal de cláusulas:

Donde la "cláusula superior" $C_ {1}$, es una cláusula de entrada, y cada otra cláusula $C_{i + 1} $ es una solución de cuyos padres es la cláusula anterior $C_ {i} $. La prueba es una refutación si la última cláusula $ C_ {l} $, es la cláusula vacía.

En SLD, todas las cláusulas son una secuencia cláusulas objetivo y el otro padre es una cláusula de entrada. En la resolución SL, el otro padre es una cláusula de entrada o una cláusula ancestral anterior en la secuencia.

Tanto en SL como en SLD, "S" representa el único literal resuelto en cualquier cláusula $ C_ {i} $, es aquel que es seleccionado únicamente por una regla de selección o función de selección. En la resolución SL, el literal seleccionado está restringido a uno que ha sido introducido recientemente en la cláusula. En el caso más simple, tal función de selección de último en entrar primero en salir puede especificarse por el orden en el que se escriben los literales, como en Prolog. Sin embargo, la función de selección en la resolución SLD es más general que en la resolución SL y en Prolog. No hay ninguna restricción sobre el literal que se puede seleccionar.

Backtracking¶

En lenguajes de programación como Fortran, Pascal, C o Java, las instrucciones se ejecutan normalmente en orden secuencial, es decir, una a continuación de otra, en el mismo orden en que están escritas, que sólo varía cuando se alcanza una instrucción de control (un bucle, una instrucción condicional o una transferencia).

Los programas en Prolog se componen de cláusulas de Horn que constituyen reglas del tipo "modus ponendo ponens", es decir, "Si es verdad el antecedente, entonces es verdad el consecuente". No obstante, la forma de escribir las cláusulas de Horn es al contrario de lo habitual. Primero se escribe el consecuente y luego el antecedente. El antecedente puede ser una conjunción de condiciones que se denomina secuencia de objetivos. Cada objetivo se separa con una coma y puede considerarse similar a una instrucción o llamada a procedimiento de los lenguajes imperativos. En Prolog no existen instrucciones de control. Su ejecución se basa en dos conceptos: la unificación y el backtracking.

Gracias a la unificación, cada objetivo determina un subconjunto de cláusulas susceptibles de ser ejecutadas. Cada una de ellas se denomina punto de elección. Prolog selecciona el primer punto de elección y sigue ejecutando el programa hasta determinar si el objetivo es verdadero o falso.

En caso de ser falso entra en juego el backtracking, que consiste en deshacer todo lo ejecutado situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección. Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Todos los objetivos terminan su ejecución bien en éxito ("verdadero"), bien en fracaso ("falso").

A continuación veremos un ejemplo de backtracking en caso de que todos los objetivos son falsos.

Selecciona el primer punto de elección.

Si encuentra un objetivo falso realiza backtracking hasta el punto de elección anterior, y continua.

Repite el mismo procedimiento y en caso de no encontrar objetivo verdadero, y no tener más puntos de elección que recorrer devuelve falso como resultado de la consulta.

En caso de que todos alguno de los objetivos sea verdadero este es el recorrido.

Conceptos clave del paradigma¶

Hechos¶

Declaración, cláusula o proposición cierta o falsa, el hecho establece una relación entre objetos.

Son las sentencias más sencillas. Un hecho es una fórmula atómica o átomo: $p(t_{1}, ..., t_{n})$ e indica que se verifica la relación (predicado) p sobre los objetos (términos) $t_{1}, ..., t_{n}$.

Reglas¶

Implicación o inferencia lógica que deduce nuevo conocimiento, la regla permite definir nuevas relaciones apartir de otras ya existentes

Consultas¶

se especifica el problema, la proposición a demostrar o el objetivo Partiendo de que los humanos son mortales y de que Sócrates es humano, deducimos que Pepito es mortal

Recursión¶

La recursividad puede ser tratada de una manera más eficaz si se piensa en que hace el algoritmo recursivo que se piensa aplicar, en vez de cómo hacerlo. Para esto se usará la modularidad, la cual se basa en separar el problema en otros más pequeños y hallar la solución a estos para luego unirlos, como es ususal en la programación lógica.

Lo que se ha estado mostrando hasta ahora es, este sistema de resolver problemas de la programación lógica mediante la modularidad, entonces ¿cómo puede ser aplicada ésta en la recursión?

Si nuestro problema es obtener el área de un cuadrado, lo que se debe hacer no es separar esta área en una de un triángulo o un círculo, sino en las áreas de otros cuadrados, por lo cual se puede dar el valor del área del cuadrado con las medidas mínimas y de ahí empezar a llamar recursivamente la función con medidas mayores a ésta. por ejemplo:

El área de un cuadrado de área de 2 unidades cuadradas es igual a cuatro veces el área de un cuadrado de 1 unidad cuadrada.

Y así se puede obtener resultados de un problema con solo definir los casos base y de ahí realizar las operaciones recursivamente.

En un ámbito más matemático ésta idea puede ser utilizada para resolver operaciones sencillas como es el caso de las sumatorias o factoriales, en general cualquier operación que requiera información del resultado que generan valores inferiores al dado. Un ejemplo de ésto podría ser el hallar las potencias de dos dado el exponente en la función, lo cual puede ser hallado con el siguiente programa de prolog.

Ejemplo:¶

Un conjunto de hechos constituye un programa (la forma más simple de programa lógico) que puede ser visto como una base de datos que describe una situación. Por ejemplo, el Programa 1 refleja la base de datos de las relaciones familiares que se muestran en el siguiente gráfico.

Todos los hechos de este programa son hechos de base (sin variables), pero también se pueden introducir hechos con variables como axiomas,por ejemplo: $suma(0, X, X)$. En ellos, las variables se consideran cuantificadas universalmente. Es decir, ∀$x$ $suma(0, x, x)$.

Al igual que el hecho es_mujer(sarah) establece la verdad de la sentencia "Sarah es mujer", el hecho $suma(0, X, X)$ establece la verdad para cualquier valor que pueda tomar la variable, es decir, nos dice que "para todo término x, la suma de 0 con x es x" . Equivale a un conjunto de hechos de base como serían: $suma(0, 1, 1)$, $suma(0, 2, 2)$, etc.

Una vez que se tiene el programa describiendo una situación, se pueden hacer consultas para obtener información acerca de él. Por ejemplo, podemos hacer consultas al Programa 1 del tipo siguiente:

Ventajas y Desventajas del uso de este paradigma¶

Ventajas¶

Desventajas¶

Lenguajes:¶

Ejemplos en SWI-Prolog Ejemplos listos para ejecutar

• Taller Teórico - Programación Lógica
• Presentación - Programación Lógica

Los siguientes son algunos de los lenguajes de programación que emplean como paradigma la programación lógica.

• Prolog
• Mercury
• CLP (FD)
• CSP (Constraint Satisfaction Problem)
• Lambda Prolog
• Logtalk
• Alma-0
• CLAC(Logical Composition with the Assistance of Computers)
• Gödel
• Curry
• Ace
• PALs
• Actor Prolog

Prolog :¶

Es un Lenguaje de Programación diseñado para representar y utilizar el conocimiento que se tiene sobre un determinado dominio. Los programas en Prolog responden preguntas sobre el tema del cual tienes conocimiento.

La popularidad del lenguaje se debe a su capacidad de deducción y además es un lenguaje fácil de usar por su semántica y sintaxis. Solo busca relaciones entre los objetos creados, las variables y las listas, que son su estructura básica.

Escribir un programa en Prolog consiste en declarar el conocimiento disponible acerca de objetos, además de sus relaciones y sus reglas, en lugar de correr un programa para obtener una solución, se hace una pregunta, el programa revisa la base de datos para encontrar la solución a la pregunta, si existe mas de una solución, Prolog hace un barrido para encontrar soluciones distintas. El propio sistema es el que deduce las respuestas a las preguntas que se le plantean, dichas respuestas las deduce del conocimiento obtenido por el conjunto de reglas dadas.

• Alain Colmerauer y Philippe Roussel (Finales de los 70’s)
• Proviene del francés PROgrammation en LOGique.
• Producción interpretada
• Se basa en Lógica de primer orden
• Es declarativo
• Backtracking

Mercury :¶

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.

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

Se puede predeterminar el número de veces que se va a llamar a un predicado dentro del programa. “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.

• Fergus Henderson, Thomas Conway y Zoltan Somogyi (1995)
• Sintaxis parecida a PROLOG
• Diseñado para resolver “aplicaciones del mundo real” de forma robusta.
• Soporta polimorfismo
• Un programa escrito en Mercury es más rápido que uno equivalente realizado en Prolog.

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.

Godel¶

Gödel es un lenguaje en el que las sentencias lógicas llevan un orden y en el que 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. Como curiosidad, se puede destacar que este lenguaje no funciona en un entorno Windows.

Otros Ejemplos:¶

• Grafos dirigidos en Prolog, busqueda de caminos
• Serie fibonacci en Prolog
• Serie fibonacci en Mercury
• Juego de ahorcado en Prolog

Aplicaciones:¶

1. Desarrollo de aplicaciones de inteligencia artificial.
2. Prueba de teoremas de forma automática, donde un programa genera nuevos teoremas sobre una teoría existente.
3. Construcción de Sistemas expertos, donde un Sistema de información mita las recomendaciones de un experto sobre algún dominio de conocimiento.
4. Procesamiento del lenguaje natural, donde un programa es capaz de comprender (con limitaciones) la información contenida en una expresión lingüística humana.
Acontinuación se presenta un ejemplo simple de procesamiento de lenguaje natural.
5. Consultas lógicas basadas en reglas
   • Búsquedas en bases de datos
   • Sistemas de control de voz

Referencias¶

1. Programación lógica
   • http://programacion-programacionlogica.blogspot.com.co/
   • https://en.wikipedia.org/wiki/Logic_programming
   • https://www.youtube.com/watch?v=SykxWpFwMGs
   • https://cibernetica.wordpress.com/2008/02/22/programacion-logica/
   • http://programacion-programacionlogica.blogspot.com.co/
   • https://es.wikipedia.org/wiki/Programaci%C3%B3n_l%C3%B3gica
   • http://labsys.frc.utn.edu.ar/ppr-2011/Unidad%20V%20-%20Paradigma%20L%C3%B3gico/Unidad%20V%20-%20Paradigma%20LOGICO.pdf
   • https://en.wikipedia.org/wiki/Logic_programming
   • http://www.it.uc3m.es/jvillena/irc/practicas/estudios/Lenguajes_Logicos.pdf
   • https://es.wikipedia.org/wiki/L%C3%B3gica_de_primer_orden
   • https://es.wikipedia.org/wiki/L%C3%B3gica_proposicional
   • https://es.wikipedia.org/wiki/Cl%C3%A1usula_de_Horn
   • Paradigma Imperativo vs Declarativo.
     • https://www.smashingmagazine.com/2014/07/declarative-programming/
   • Apuntes de Programación lógica - Marisa Navarro.
     • http://www.sc.ehu.es/jiwhehum2/prolog/Temario/Tema1.pdf
     • http://www.sc.ehu.es/jiwhehum2/prolog/Temario/Tema2.pdf
     • http://www.sc.ehu.es/jiwhehum2/prolog/Temario/Tema3.pdf
2. Lógica de primer orden
   • https://drive.google.com/file/d/0B7IRdmOoUVf5RFRBN2RJdDNlNm8/view
   • https://drive.google.com/drive/u/1/folders/0B7IRdmOoUVf5V2pxal81X3NQc2M
3. PROLOG
   • http://www.anselm.edu/homepage/mmalita/culpro/index.html
   • https://es.wikipedia.org/wiki/Prolog
4. Mercury
   • https://mercurylang.org/