Prólogo

Aunque Prolog se usa ampliamente en investigación y educación, ^{[ 20 ]} Prolog y otros lenguajes de programación lógica no han tenido un impacto significativo en la industria informática en general. ^{[ 21 ]} La mayoría de las aplicaciones son pequeñas para los estándares industriales, y pocas superan las 100 000 líneas de código. ^{[ 21 ] [ 22 ]} La programación a gran escala se considera compleja porque no todos los compiladores de Prolog admiten módulos, y existen problemas de compatibilidad entre los sistemas de módulos de los principales compiladores de Prolog. ^{[ 23 ]} La portabilidad del código Prolog entre implementaciones también ha sido un problema, pero los desarrollos desde 2007 han significado que: "la portabilidad dentro de la familia de implementaciones de Prolog derivadas de Edinburgh/Quintus es lo suficientemente buena como para permitir el mantenimiento de aplicaciones portátiles del mundo real". ^{[ 24 ]}

El software desarrollado en Prolog ha sido criticado por su elevado coste de rendimiento en comparación con los lenguajes de programación convencionales. En particular, la estrategia de evaluación no determinista de Prolog puede resultar problemática al programar cálculos deterministas, o incluso al utilizar el "no determinismo indiferente" (donde se toma una única decisión en lugar de recorrer todas las posibilidades). Es posible que sea necesario utilizar cortes y otras construcciones del lenguaje para lograr un rendimiento deseable, lo que anula una de las principales ventajas de Prolog: la capacidad de ejecutar programas "hacia adelante y hacia atrás". ^{[ 25 ]}

Prolog no es puramente declarativo: debido a construcciones como el operador de corte , se requiere una lectura procedimental de un programa Prolog para comprenderlo. ^{[ 26 ]} El orden de las cláusulas en un programa Prolog es significativo, ya que la estrategia de ejecución del lenguaje depende de él. ^{[ 27 ]} Otros lenguajes de programación lógica, como Datalog , son verdaderamente declarativos, pero restringen el lenguaje. Como resultado, muchos programas prácticos de Prolog se escriben para ajustarse al orden de búsqueda en profundidad de Prolog , en lugar de ser programas lógicos puramente declarativos. ^{[ 25 ]}

Prolog se ha utilizado en Watson . Watson utiliza el software DeepQA de IBM y el marco Apache UIMA (Arquitectura de Gestión de Información No Estructurada). El sistema fue escrito en varios lenguajes, incluidos Java, C++ y Prolog, y se ejecuta en el sistema operativo SUSE Linux Enterprise Server 11 utilizando el marco Apache Hadoop para proporcionar computación distribuida. Prolog se utiliza para la coincidencia de patrones sobre árboles de análisis de lenguaje natural. Los desarrolladores han declarado: "Necesitábamos un lenguaje en el que pudiéramos expresar convenientemente reglas de coincidencia de patrones sobre los árboles de análisis y otras anotaciones (como resultados de reconocimiento de entidades nombradas), y una tecnología que pudiera ejecutar estas reglas de manera muy eficiente. Descubrimos que Prolog era la opción ideal para el lenguaje debido a su simplicidad y expresividad ". ^{[ 11 ]} Prolog se está utilizando en la plataforma de desarrollo de bajo código GeneXus , que se centra en la IA. La base de datos de grafos de código abierto TerminusDB está implementada en Prolog. ^{[ 28 ]} TerminusDB está diseñada para construir y curar grafos de conocimiento de forma colaborativa .

El único tipo de dato de Prolog es el término . Los términos pueden ser átomos , números , variables o términos compuestos . ^{[ nota 1 ]}

• Un átomo es un nombre de símbolo que comienza con una letra minúscula o está entre comillas. Ejemplos de átomos incluyen x, red, 'Taco', 'some atom', y 'p(a)'.
• Los números pueden ser decimales o enteros . La mayoría de los sistemas Prolog principales admiten números enteros de longitud arbitraria.
• Las variables se representan mediante una cadena de caracteres compuesta por letras, números y guiones bajos, que comienza con una letra mayúscula o un guion bajo. En lógica, las variables se asemejan mucho a las variables genéricas, ya que sirven como marcadores de posición para términos arbitrarios.
• Un término compuesto se compone de un átomo llamado "functor" y varios "argumentos", que también son términos. Los términos compuestos se escriben normalmente como un functor seguido de una lista de argumentos separados por comas, que se encuentra entre paréntesis. El número de argumentos se denomina aridad del término . Un átomo puede considerarse un término compuesto con aridad cero. Un ejemplo de término compuesto es person_friends(zelda,[tom,jim]).

Casos especiales de términos compuestos:

• Una lista es una colección ordenada de términos. Se denota mediante corchetes con los términos separados por comas, o en el caso de una lista vacía, por []. Por ejemplo, [1,2,3,4]o [red,green,blue].
• Cadenas : Una secuencia de caracteres rodeada de comillas es equivalente a una lista de códigos de caracteres (numéricos), una lista de caracteres (átomos de longitud 1) o un átomo, dependiendo del valor del indicador de Prolog double_quotes. Por ejemplo, "to be, or not to be". ^{[ 29 ]}

Los programas Prolog describen relaciones, definidas mediante cláusulas. El Prolog puro se limita a las cláusulas Horn . Se utilizan dos tipos de cláusulas Horn para definir programas Prolog: reglas y hechos. Una regla tiene la forma

Cabeza :- Cuerpo .

y se lee como "La cabeza es verdadera si el cuerpo es verdadero". El cuerpo de una regla consta de llamadas a predicados, que se denominan objetivos de la regla. El operador lógico integrado (es decir, un operador,/2 de aridad 2 con nombre ) denota la conjunción de objetivos, y denota la disyunción . Las conjunciones y disyunciones solo pueden aparecer en el cuerpo, no en la cabeza de una regla.,;/2

Las cláusulas con cuerpo vacío se denominan hechos . Un ejemplo de hecho es:

humano ( Sócrates ).

lo cual es equivalente a la regla:

humano ( sócrates ) : verdadero .

El predicado incorporado true/0siempre es verdadero.

Dado lo anterior, cabe preguntarse:

¿Sócrates era humano?

¿- humano ( Sócrates )? Sí

¿Qué son los humanos?

¿- humano ( X ). X = Sócrates

Las cláusulas con cuerpo se denominan reglas . Un ejemplo de regla es:

mortal ( X ) :- humano ( X ).

Si añadimos esa regla y nos preguntamos: ¿qué cosas son mortales?

¿- mortal ( X ). X = Sócrates

Un predicado (o definición de procedimiento ) es un conjunto de cláusulas cuyos encabezados tienen el mismo nombre y aridad. Usamos la notación nombre/aridad para referirnos a los predicados. Un programa lógico es un conjunto de predicados. Por ejemplo, el siguiente programa Prolog, que define algunas relaciones familiares, tiene cuatro predicados:

madre_hija ( trude , sally ).padre_hijo ( tom , sally ). padre_hijo ( tom , erica ). padre_hijo ( mike , tom ).hermano ( X , Y ) :- padre_hijo ( Z , X ), padre_hijo ( Z , Y ), no ( X = Y ).padre_hijo ( X , Y ) :- padre_hijo ( X , Y ). padre_hijo ( X , Y ) :- madre_hijo ( X , Y ).

El predicado father_child/2tiene tres cláusulas, todas las cuales son hechos, y el predicado parent_child/2tiene dos cláusulas, ambas son reglas.

Debido a la naturaleza relacional de muchos predicados integrados, estos suelen utilizarse en varias direcciones. Por ejemplo, length/2se puede usar para determinar la longitud de una lista ( length(List, L), dada una lista List), para generar un esqueleto de lista de una longitud dada ( length(X, 5)), y para generar ambos esqueletos de lista y sus longitudes juntas ( length(X, L)). De manera similar, append/3se puede usar tanto para concatenar dos listas ( append(ListA, ListB, X)dadas las listas ListAy ListB), como para dividir una lista dada en partes ( append(X, Y, List), dada una lista List). Por esta razón, un conjunto relativamente pequeño de predicados de biblioteca es suficiente para muchos programas Prolog.

Como lenguaje de propósito general, Prolog también proporciona varios predicados integrados para realizar actividades rutinarias como entrada/salida , uso de gráficos y comunicación con el sistema operativo. Estos predicados no tienen un significado relacional y solo son útiles por los efectos secundarios que producen en el sistema. Por ejemplo, el predicado write/1muestra un término en la pantalla.

Los algoritmos iterativos pueden implementarse mediante predicados recursivos . ^{[ 30 ]}

Consideremos el parent_child/2predicado definido en el programa de relación familiar anterior. El siguiente programa Prolog define la relación de ancestros :

ancestro ( X , Y ) :- padre_hijo ( X , Y ). ancestro ( X , Y ) :- padre_hijo ( X , Z ), ancestro ( Z , Y ).

Expresa que X es un ancestro de Y si X es padre de Y o si X es padre de un ancestro de Y. Es recursiva porque se define en términos de sí misma (hay una llamada al predicado ancestor/2en el cuerpo de la segunda cláusula).

La ejecución de un programa Prolog se inicia cuando el usuario introduce un único objetivo, denominado consulta. Lógicamente, el motor Prolog intenta encontrar una refutación de la consulta negada. El método de resolución utilizado por Prolog se denomina resolución SLD . Si la consulta negada puede refutarse, se deduce que la consulta, con las asignaciones de variables adecuadas, es una consecuencia lógica del programa. En ese caso, se informan al usuario todas las asignaciones de variables generadas y se considera que la consulta ha tenido éxito. Operacionalmente, la estrategia de ejecución de Prolog puede considerarse una generalización de las llamadas a funciones en otros lenguajes, con la diferencia de que varias cabeceras de cláusula pueden coincidir con una llamada dada. En ese caso, el sistema crea un punto de decisión, unifica el objetivo con la cabecera de cláusula de la primera alternativa y continúa con los objetivos de dicha primera alternativa. Si algún objetivo falla durante la ejecución del programa, se deshacen todas las asignaciones de variables realizadas desde la creación del último punto de decisión, y la ejecución continúa con la siguiente alternativa de dicho punto de decisión. Esta estrategia de ejecución se denomina retroceso cronológico . Por ejemplo, dado el programa de relaciones familiares definido anteriormente, la siguiente consulta se evaluará como verdadera:

¿ Hermano/a ( Sally , Erica )? Sí

Esto se obtiene de la siguiente manera: Inicialmente, la única cabecera de cláusula que coincide con la consulta sibling(sally, erica)es la primera, por lo que probar la consulta es equivalente a probar el cuerpo de esa cláusula con las vinculaciones de variables apropiadas, es decir, la conjunción (parent_child(Z, sally), parent_child(Z, erica)). El siguiente objetivo a probar es el más a la izquierda de esta conjunción, es decir, parent_child(Z, sally). Dos cabeceras de cláusula coinciden con este objetivo. El sistema crea un punto de elección y prueba la primera alternativa, cuyo cuerpo es father_child(Z, sally). Este objetivo se puede probar usando el hecho father_child(tom, sally), por lo que se genera la vinculación Z = tom, y el siguiente objetivo a probar es la segunda parte de la conjunción anterior: parent_child(tom, erica). Nuevamente, esto se puede probar mediante el hecho correspondiente. Dado que todos los objetivos se pudieron probar, la consulta tiene éxito. Como la consulta no contenía variables, no se informan vinculaciones al usuario. Una consulta con variables, como:

?- padre_hijo ( Padre , Hijo ).

Enumera todas las respuestas válidas en el método de retroceso.

Observe que, con el código descrito anteriormente, la consulta ?- sibling(sally, sally).también se ejecuta correctamente. Si se desea, se pueden añadir objetivos adicionales para describir las restricciones pertinentes.

El predicado integrado de Prolog \+/1proporciona la negación como fallo , lo que permite un razonamiento no monótono . El objetivo \+ illegal(X)en la regla

legal ( X ) :- \+ ilegal ( X ).

se evalúa de la siguiente manera: Prolog intenta probar illegal(X). Si se encuentra una prueba para ese objetivo, el objetivo original (es decir, \+ illegal(X)) falla. Si no se encuentra ninguna prueba, el objetivo original tiene éxito. Por lo tanto, el \+/1operador de prefijo se llama operador de "no demostrable", ya que la consulta ?- \+ Goal.tiene éxito si el Objetivo no es demostrable. Este tipo de negación es correcta si su argumento es "ground" (es decir, no contiene variables). La corrección se pierde si el argumento contiene variables y el procedimiento de prueba está completo. En particular, la consulta ?- legal(X).ahora no se puede usar para enumerar todas las cosas que son legales.

Ejemplo de una consulta básica en un par de dialectos populares de Prolog:

Esta comparación muestra que el mensaje ("?-" frente a "|  ?-") y el estado de resolución ("true." frente a "yes", "false." frente a "no") pueden diferir de una implementación de Prolog a otra.

Cualquier cálculo puede expresarse de forma declarativa como una secuencia de transiciones de estado. Por ejemplo, un compilador optimizador con tres pasadas de optimización podría implementarse como una relación entre un programa inicial y su forma optimizada:

programa_optimizado ( Prog0 , Prog ) :- optimización_paso_1 ( Prog0 , Prog1 ), optimización_paso_2 ( Prog1 , Prog2 ), optimización_paso_3 ( Prog2 , Prog ).

o, de forma equivalente, utilizando la notación DCG :

programa_optimizado --> optimización_pass_1 , optimización_pass_2 , optimización_pass_3 .

El algoritmo de ordenación Quicksort relaciona una lista con su versión ordenada:

partición ([], _ , [], []). partición ([ X | Xs ], Pivote , Pequeños , Grandes ) :- ( X @< Pivote -> Pequeños = [ X | Resto ], partición ( Xs , Pivote , Resto , Grandes ) ; Grandes = [ X | Resto ], partición ( Xs , Pivote , Pequeños , Resto ) ).quicksort ([]) --> []. quicksort ([ X | Xs ]) --> { partición ( Xs , X , Más pequeño , Más grande ) }, quicksort ( Más pequeño ), [ X ], quicksort ( Más grande ).

La norma técnica Prolog de la Organización Internacional de Normalización (ISO) consta de dos partes. ISO/IEC 13211-1, ^{[ 39 ] [ 46 ]} publicada en 1995, tiene como objetivo estandarizar las prácticas existentes de las numerosas implementaciones de los elementos centrales de Prolog. Ha aclarado aspectos del lenguaje que antes eran ambiguos y conduce a programas portátiles. Existen tres correcciones: Cor.1:2007, ^{[ 47 ]} Cor.2:2012, ^{[ 48 ]} y Cor.3:2017. ^{[ 49 ]} ISO/IEC 13211-2, ^{[ 39 ]} publicada en 2000, añade soporte para módulos a la norma. La norma es mantenida por el grupo de trabajo ISO/IEC JTC1 / SC22 /WG17 ^{[ 50 ]} . ANSI X3J17 es el Grupo Asesor Técnico de EE. UU. para la norma. ^{[ 51 ]}

Para mayor eficiencia, el código Prolog se compila típicamente a código máquina abstracto, a menudo influenciado por el conjunto de instrucciones de la máquina abstracta Warren basada en registros. ^{[ 52 ]} Algunas implementaciones emplean interpretación abstracta para derivar información de tipo y modo de predicados en tiempo de compilación, o compilan a código máquina real para alto rendimiento. ^{[ 53 ]} El diseño de métodos de implementación eficientes para código Prolog es un campo de investigación activa en la comunidad de programación lógica, y en algunas implementaciones se emplean varios otros métodos de ejecución. Estos incluyen la binarización de cláusulas y máquinas virtuales basadas en pila .

Los sistemas Prolog suelen implementar un método de optimización bien conocido llamado optimización de llamadas de cola para predicados deterministas que presentan recursión de cola o, más generalmente, llamadas de cola: el marco de pila de una cláusula se descarta antes de realizar una llamada en una posición de cola. Por lo tanto, los predicados recursivos de cola deterministas se ejecutan con espacio de pila constante, como los bucles en otros lenguajes.

Encontrar cláusulas que sean unificables con un término en una consulta es lineal con respecto al número de cláusulas. La indexación de términos utiliza una estructura de datos que permite búsquedas en tiempo sublineal . ^{[ 54 ]} La indexación solo afecta el rendimiento del programa, no la semántica. La mayoría de los Prologs solo utilizan la indexación en el primer término, ya que la indexación en todos los términos es costosa, pero las técnicas basadas en palabras codificadas en campos o palabras clave superpuestas proporcionan una indexación rápida en toda la consulta y el encabezado. ^{[ 55 ] [ 56 ]}

Algunos sistemas Prolog, como WIN-PROLOG y SWI-Prolog, ahora implementan funciones hash para gestionar grandes conjuntos de datos de forma más eficiente. Esto suele traducirse en mejoras de rendimiento muy significativas al trabajar con grandes corpus como WordNet .

Algunos sistemas Prolog ( B-Prolog , XSB , SWI-Prolog , YAP y Ciao ) implementan un método de memorización llamado tabulación , que libera al usuario de almacenar manualmente los resultados intermedios. La tabulación implica una compensación entre espacio y tiempo ; el tiempo de ejecución puede reducirse utilizando más memoria para almacenar los resultados intermedios: ^{[ 57 ] [ 58 ]}

Los subobjetivos encontrados en la evaluación de una consulta se almacenan en una tabla, junto con las respuestas a dichos subobjetivos. Si un subobjetivo se vuelve a encontrar, la evaluación reutiliza la información de la tabla en lugar de volver a realizar la resolución contra las cláusulas del programa. ^{[ 59 ]}

El tabulador puede extenderse en diversas direcciones. Puede admitir predicados recursivos mediante resolución SLG o tabulador lineal. En un sistema Prolog multihilo, los resultados del tabulador podrían mantenerse privados para un hilo o compartirse entre todos los hilos. Y en el tabulador incremental, el tabulador podría reaccionar a los cambios.

Durante el proyecto de Sistemas Informáticos de Quinta Generación , se intentó implementar Prolog en hardware con el objetivo de lograr una ejecución más rápida con arquitecturas dedicadas. ^{[ 60 ] [ 61 ] [ 62 ]} Además, Prolog tiene varias propiedades que pueden permitir una aceleración mediante la ejecución paralela. ^{[ 63 ]} Un enfoque más reciente ha sido compilar programas Prolog restringidos en una matriz de puertas programables en campo (FPGA) . ^{[ 64 ]} Sin embargo, el rápido progreso en hardware de propósito general ha superado sistemáticamente a las arquitecturas más especializadas.

En 1982, las computadoras operaban a una velocidad de entre 10 000 y 100 000 inferencias lógicas por segundo (LIPS). El FGCS planeaba producir computadoras que operaran a entre 0,1 y 1 GLIPS. ^{[ 65 ]} Los documentos del Instituto de Tecnología Informática de Nueva Generación estimaban que 1 LIP requería aproximadamente 100 operaciones en una computadora convencional. El plan era producir, al final del proyecto (en 1992), una máquina con 1000 procesadores que alcanzara 1 GLIPS, lo que implicaba al menos 1 MLIPS por procesador. ^{[ 66 ]}

Sega implementó Prolog para su uso con la Sega AI Computer , lanzada para el mercado japonés en 1986. Prolog se utilizó para leer entradas de lenguaje natural , en idioma japonés , a través de un panel táctil . ^{[ 67 ]}

Prolog es un lenguaje sin tipado. Los intentos de introducir y extender Prolog con tipos comenzaron en la década de 1980, ^{[ 68 ] [ 69 ]} y continúan hasta 2008.. ^{[ 70 ]} La información de tipo es útil no solo para la seguridad de tipos sino también para razonar sobre programas Prolog. ^{[ 71 ]}

La sintaxis de Prolog no especifica qué argumentos de un predicado son entradas y cuáles son salidas. ^{[ 72 ]} Sin embargo, esta información es importante y se recomienda incluirla en los comentarios. ^{[ 73 ]} Los modos proporcionan información valiosa al razonar sobre programas Prolog ^{[ 71 ]} y también pueden usarse para acelerar la ejecución. ^{[ 74 ]}

La programación lógica de restricciones extiende Prolog para incluir conceptos de satisfacción de restricciones . ^{[ 75 ] [ 76 ]} Un programa de lógica de restricciones permite restricciones en el cuerpo de las cláusulas, como: Es adecuado para problemas de optimización combinatoria a gran escala ^{[ 77 ]} y, por lo tanto, es útil para aplicaciones en entornos industriales, como la programación de horarios y la planificación de la producción automatizadas . La mayoría de los sistemas Prolog incluyen al menos un solucionador de restricciones para dominios finitos, y a menudo también solucionadores para otros dominios como los números racionales .A(X,Y) :- X+Y>0.

Flora-2 es un sistema de representación del conocimiento y razonamiento orientado a objetos basado en F-logic e incorpora HiLog , lógica transaccional y razonamiento derrotable .

Logtalk es un lenguaje de programación lógica orientado a objetos que puede utilizar la mayoría de las implementaciones de Prolog como compilador. Como lenguaje multiparadigma, incluye soporte tanto para prototipos como para clases.

Oblog es una pequeña extensión portátil y orientada a objetos para Prolog, creada por Margaret McDougall de EdCAAD, Universidad de Edimburgo.

Objlog era un lenguaje basado en marcos que combinaba objetos y Prolog II, desarrollado por el CNRS de Marsella, Francia.

Prolog++ fue desarrollado por Logic Programming Associates y lanzado por primera vez en 1989 para PC con MS-DOS. Posteriormente se añadió compatibilidad con otras plataformas y se lanzó una segunda versión en 1995. En 1994, la editorial Addison-Wesley publicó un libro sobre Prolog++ escrito por Chris Moss.

Visual Prolog es un lenguaje multiparadigma con interfaces, clases, implementaciones y expresiones de objetos.

Los sistemas Prolog que proporcionan una biblioteca gráfica son SWI-Prolog , ^{[ 78 ]} Visual Prolog , WIN-PROLOG y B-Prolog .

Prolog-MPI es una extensión de código abierto de SWI-Prolog para computación distribuida sobre la Interfaz de Paso de Mensajes . ^{[ 79 ]} También existen varios lenguajes de programación Prolog concurrentes. ^{[ 80 ]}

Algunas implementaciones de Prolog, en particular Visual Prolog , SWI-Prolog y Ciao , admiten programación web del lado del servidor con soporte para protocolos web, HTML y XML . ^{[ 81 ]} También hay extensiones para admitir formatos web semánticos como Resource Description Framework y Web Ontology Language . ^{[ 82 ] [ 83 ]} Prolog también se ha sugerido como un lenguaje del lado del cliente . ^{[ 84 ]} Además, Visual Prolog admite JSON-RPC y Websockets .

• F-logic extiende Prolog con marcos/objetos para la representación del conocimiento .
• La lógica transaccional extiende Prolog con una teoría lógica de operadores de actualización que modifican el estado. Posee una semántica tanto basada en modelos como procedimental.
• OW Prolog se ha creado para solucionar la falta de gráficos e interfaz de Prolog.

• El lenguaje Gödel es una implementación fuertemente tipada de programación lógica con restricciones concurrentes . Está construido sobre SICStus Prolog .
• Visual Prolog , antes conocido como PDC Prolog y Turbo Prolog, es un dialecto de Prolog fuertemente tipado y orientado a objetos , muy diferente del Prolog estándar. Como Turbo Prolog, fue comercializado por Borland, pero actualmente es desarrollado y comercializado por la empresa danesa Prolog Development Center (PDC), que lo creó originalmente.
• Datalog es un subconjunto de Prolog. Se limita a relaciones que pueden ser estratificadas y no permite términos compuestos. A diferencia de Prolog, Datalog no es Turing-completo .
• Mercury es una rama de Prolog orientada a la ingeniería de software en general, con un sistema de tipos estático y polimórfico, así como un sistema de modos y determinismo.
• GraphTalk es una implementación propietaria de la Máquina Abstracta de Warren, con propiedades adicionales orientadas a objetos.
• En cierto modo, Prolog es un subconjunto de Planner . Las ideas de Planner se desarrollaron posteriormente en Scientific Community Metaphor .
• AgentSpeak es una variante de Prolog para programar el comportamiento de los agentes en sistemas multiagente .
• Erlang nació con una implementación basada en Prolog y conserva gran parte de la sintaxis unificada de Prolog.
• Pilog es un lenguaje declarativo construido sobre PicoLisp , que tiene la semántica de Prolog, pero utiliza la sintaxis de Lisp.
• λProlog es una extensión del núcleo de Prolog que presenta tipado polimórfico, programación modular y programación de orden superior, incluyendo soporte directo para términos con operadores de enlace de variables a través de la denominada sintaxis de árbol λ y unificación de patrones de orden superior.