| Prólogo | |
| Fecha de la primera versión | 1972 |
|---|---|
| Paradigma | Programación lógica |
| Autor | Alain Colmerauer , Philippe Roussel |
| Influenciado por | Planificador ( en ) |
| Extensión de archivo | pl, pro y P |
Prolog es un lenguaje de programación lógica . El nombre Prolog es un acrónimo de PROgrammation in LOGic. Fue creado por Alain Colmerauer y Philippe Roussel alrededor de 1972 en Luminy, Marsella. El objetivo era crear un lenguaje de programación en el que se definieran las reglas lógicas que se esperaban de una solución y dejar que el compilador la transformara en una secuencia de instrucciones. Una de las ganancias esperadas fue una mayor facilidad de mantenimiento de las aplicaciones, la adición o eliminación de reglas a lo largo del tiempo sin necesidad de volver a examinar todas las demás.
Prolog se utiliza en inteligencia artificial y en procesamiento lingüístico informático (principalmente lenguajes naturales ). Sus reglas sintácticas y semánticas son sencillas y consideradas claras (uno de los objetivos perseguidos era proporcionar una herramienta para lingüistas ignorantes de la informática). Los primeros resultados obtenidos con Prolog impulsaron en algún momento, en la década de 1980, la investigación sobre una quinta generación, hardware y software, de computadoras (denominada Quinta generación japonesa debido al importante compromiso del MITI con el proyecto). El esfuerzo realizado fue importante, las consecuencias más modestas, siendo Prolog un idioma entre otros en el rango del programador.
Prolog se basa en el cálculo de predicados de primer orden ; sin embargo, está restringido en su versión inicial a aceptar únicamente cláusulas de Horn (las versiones modernas de Prolog aceptan predicados más complejos, especialmente con el tratamiento de negación por falla ). La ejecución de un programa Prolog es efectivamente una aplicación del teorema de prueba por resolución de primer orden. Los conceptos fundamentales son unificación , recursividad y retroceso . El algoritmo de resolución de Prolog se basa en una extensión de la resolución SLD .
Podemos construir en Prolog una base de conocimiento en un orden indeterminado, ya que solo cuentan las relaciones en presencia y no su secuencia de escritura. Prolog puede entonces resolver una serie de problemas lógicos relacionados con dicha base de conocimiento (noción de base de datos deductiva), un problema similar a la búsqueda de una solución (o varias) en un laberinto de restricciones establecidas.
Prolog no utiliza la escritura de datos en el sentido habitual de los lenguajes de programación . De hecho, no hace una distinción real entre los datos del programa y el programa en sí (principio de programación declarativa y programación funcional). Sus elementos léxicos, llamados términos , abarcan los siguientes tipos.
Los textos constantes constituyen átomos . Un átomo generalmente se compone de una cadena de letras, números y guiones bajos ( _), comenzando con una letra minúscula . Para introducir un átomo no alfanumérico, rodee con apóstrofos: así '+' es un átomo, + un operador).
Las implementaciones actuales de Prolog no distinguen entre enteros y flotantes.
Las variables se especifican mediante un conjunto de letras, números y guiones bajos y comienzan con una letra mayúscula .
Por lo tanto, X3 como Unit_Price son los nombres de las variables admisibles.
Prolog no es un lenguaje de programación imperativo ; por lo tanto, una variable no es un contenedor al que se asigna un valor, sino que representa (como en matemáticas en X> 0 ) el conjunto de valores admisibles para ella dentro del marco de las restricciones.
El campo inicialmente indefinido de la variable se especifica mediante la unificación alrededor de las restricciones. Una vez que se unifica la variable, su valor ya no se puede modificar dentro de la misma rama de evaluación. Sin embargo, el retroceso permite volver a esta unificación en el contexto de la búsqueda de valores admisibles (o nuevos valores admisibles), en el marco de una exploración exhaustiva.
La variable anónima se escribe con un guión bajo (_). Cualquier variable cuyo nombre comience con un guión bajo también es una variable anónima. Es, como la x o la y del álgebra, una variable ficticia que sirve como intermediaria del cálculo.
Prolog solo puede representar datos complejos en términos compuestos . Un término compuesto consta de una cabeza (también llamada functor ), que debe ser un átomo, y parámetros sin restricción de tipo. Sin embargo, el número de parámetros, llamado aridad del término, es significativo. Un término compuesto se identifica por su encabezamiento y su aridad, y generalmente se escribe como functor / aridad.
Ejemplos de términos compuestos:
Una lista no es un tipo de datos aislado, sino que se define mediante una construcción recursiva (utilizando el functor .de aridad 2, por lo que está en el nivel de la representación interna un término compuesto):
El primer elemento, llamado cabeza, es H , seguido por el contenido del resto de la lista, indicado como T o cola. La lista [1, 2, 3] se representaría internamente como '.' ( 1 , '.' ( 2 , '.' ( 3 , []))) Una abreviatura de sintaxis es [ H | T ], que se utiliza principalmente para crear reglas. La totalidad de una lista se puede procesar actuando sobre el primer elemento y luego sobre el resto de la lista, por recursividad , como en LISP .
Para conveniencia del programador, las listas se pueden construir y deconstruir de varias formas.
Las cadenas generalmente se escriben como una secuencia de caracteres rodeados de apóstrofos. A menudo se representan internamente mediante una lista de códigos ASCII.
La programación en Prolog es muy diferente a la programación en un lenguaje imperativo . En Prolog, alimentamos una base de conocimientos de hechos y reglas; entonces es posible realizar solicitudes a la base de conocimientos.
La unidad básica de Prolog es el predicado , que se define como verdadero. Un predicado consta de un encabezado y varios argumentos. Por ejemplo :
chat(tom).Aquí 'gato' es la cabeza y 'tom' es el argumento. Aquí hay algunas solicitudes simples que puede hacer a un intérprete de Prolog basándose en este hecho:
?- chat(tom). oui. ?- chat(X). X = tom; fail.En este segundo ejemplo, a la pregunta 'gato (X)' el intérprete propone la respuesta 'X = tom' unificando la variable 'X' al átomo 'tom'. En Prolog es un acierto . Después de esta primera respuesta, el usuario puede preguntar si hay otras respuestas usando "; »(Símbolo de la disyunción), aquí el intérprete responde que no encuentra ninguna. Esta búsqueda de otras soluciones se basa en un modelo de ejecución no determinista (en el sentido del no determinismo de los autómatas no deterministas) con retroalimentación sobre los diferentes puntos de elección y exploración de alternativas inexploradas.
?- chat(vim). fail.En este último ejemplo, a la pregunta 'chat (vim)' el intérprete responde que no puede probar este hecho, en Prolog es un fracaso. Suponiendo que se conocen todos los hechos ( hipótesis del mundo cerrado ), esto significa que 'vim' no es un gato.
Los predicados generalmente se definen para expresar hechos que el programa conoce sobre el mundo. En la mayoría de los casos, el uso de predicados requiere alguna convención. Por ejemplo, la semántica de los dos predicados siguientes no es inmediata:
pere(marie, pierre). pere(pierre, marie).En ambos casos, 'padre' es la cabeza mientras que 'marie' y 'pierre' son los argumentos. Sin embargo, en el primer caso, Mary aparece primero en la lista de argumentos y en el segundo es Peter (el orden en la lista de argumentos es importante). El primer caso es un ejemplo de una definición en el orden verbo-objeto-sujeto y podría leerse con el auxiliar 'tener': Marie tiene como padre Pierre, y el segundo de verbo-sujeto-objeto y podría leerse con el «ser» auxiliar: Pierre es el padre de María. Como Prolog no comprende el lenguaje natural, ambas versiones son correctas en lo que a él respecta; sin embargo, es importante adoptar estándares de programación consistentes para el mismo programa. En general, es más bien el "ser" auxiliar el que se utiliza.
Por ejemplo, aceptaremos que
famille(pierre, marie, [arthur, bruno, charlotte]).significa que pierre y marie son respectivamente padre y madre de 3 hijos: arthur, bruno y charlotte; "familia" es entonces un predicado de 3 términos, siendo el último una lista de cualquier número (posiblemente cero) de hijos.
Algunos predicados están integrados en el lenguaje y permiten que un programa Prolog realice actividades de rutina (como evaluación numérica, entrada / salida , funcionalidad GUI y , en general, comunicarse con el sistema informático). Por ejemplo, el predicado de escritura se puede utilizar para la visualización de la pantalla. Entonces
write('Bonjour').mostrará la palabra "Hola" en el monitor. Estrictamente hablando, tales predicados no se relacionan con la programación lógica, su funcionalidad se basa exclusivamente en sus efectos secundarios.
Otros predicados integrados en el lenguaje son de naturaleza lógica y se incluyen en las bibliotecas . Se utilizan para simplificar el desarrollo encapsulando el procesamiento genérico, como los algoritmos de procesamiento de listas, por ejemplo.
Finalmente, otros predicados son de orden superior y se utilizan para controlar la ejecución de los intérpretes de Prolog (por ejemplo, adición / eliminación dinámica de reglas y hechos, abandono de puntos de elección, recopilación de los resultados de una consulta).
Nota: sin los predicados predefinidos, Prolog a veces se llama Pure Prolog (de acuerdo con el estándar iso en inglés : definido Prolog).
El segundo tipo de instrucciones en Prolog es la regla. Una regla de ejemplo es:
lumière(on) :- interrupteur(on).El ": -" significa "si"; esta regla indica que la luz (encendida) es verdadera si el interruptor (encendido) es verdadero. Las reglas también pueden usar variables como:
père(X,Y) :- parent(X,Y), mâle(X).para significar que una X es el padre de una Y si X es un padre de Y y X es masculino, donde "," indica una conjunción.
Podríamos tener lo mismo:
parent(X, Y) :- père(X, Y) ; mère(X, Y).para significar que una X es un padre de una Y si X es un padre de Y o X es un padre de Y, donde ";" indica una alternativa.
Un hecho es un caso especial de regla. De hecho, las siguientes dos líneas son equivalentes:
a. a :- true.Cuando el intérprete recibe una solicitud, busca las reglas (incluidos los hechos) cuya parte izquierda se puede unificar con la solicitud, y realiza esta unificación con la primera regla encontrada. Por ejemplo, teniendo este código de Prólogo:
frère_ou_sœur(X,Y) :- parent(Z,X), parent(Z,Y), X \= Y. parent(X,Y) :- père(X,Y). parent(X,Y) :- mère(X,Y). mère(trude, sally). père(tom, sally). père(tom, erica). père(mike, tom).Como resultado, la siguiente solicitud se evalúa como verdadera:
?- frère_ou_sœur(sally, erica). oui.El intérprete logra este resultado al hacer coincidir la regla sibling_or_sister (X, Y) unificando X con sally e Y con erica . Esto significa que la solicitud se puede extender a parent (Z, sally) , parent (Z, erica) . Hacer coincidir esta conjunción se logra observando a todos los posibles padres de Sally . Cependant, parent(trude,sally) ne mène pas à une solution viable, parce que si trude est substitué pour Z , parent(trude,erica) devra être vrai, et aucun fait tel (ou quelque règle qui puisse satisfaire cela) n' está presente. Además, en cambio, tom es sustituido por Z , y sin embargo , erica y sally parecen ser hermanos .
La negación lógica pura no existe en Prolog, nos basamos en la negación por falla , que se nota de manera diferente según las implementaciones de Prolog (adoptaremos la notación por la palabra clave not(prédicat)). En la negación por falla, la negación de un predicado se considera verdadera si la evaluación del predicado conduce a la falla (no es verificable).
En Prolog, la negación por falla se basa en la hipótesis del mundo cerrado: todo lo que es verdadero es conocido o demostrable a partir de lo conocido en un tiempo finito.
Vea el ejemplo a continuación:
parent(jorge, andres). parent(andres, felipe). grandparent(X,Y) :- parent(X, Z), parent(Z, Y). ? grandparent(jorge,_). %true %il y a assez d'information pour dire que jorge a un grandparent connu. % Hypothèse du monde clos → il n'y a pas assez d'informations pour arriver à une conclusion -> false ? grandparent(andres,_). %false %Négation par l'échec appuyé sur l'hypothèse du monde clos ? not(grandparent(andres,_)). %trueProlog es un lenguaje lógico, por lo que, en teoría, no tiene que preocuparse por cómo se ejecuta. Sin embargo, a veces es prudente tener en cuenta cómo funciona el algoritmo de inferencia para evitar que un programa Prolog tarde demasiado.
Por ejemplo, podemos escribir código para contar el número de elementos en una lista.
elems([],0). elems([H|T], X) :- elems(T, Y), X is Y + 1.Simplemente significa:
En este caso, hay una clara distinción entre los casos del antecedente en las reglas. Pero considere el caso en el que necesita decidir si continuar jugando en un casino;
miser(X) :- avoirargent(X). miser(X) :- avoircrédit(X), NOT avoirargent(X).Si tienes dinero, sigues apostando. Si ha perdido todo lo que necesita para pedir prestado, o si no ... no más apuestas. Tener dinero (X) puede ser una función muy cara, por ejemplo, si puede acceder a su cuenta bancaria a través de Internet. Pero ocurre lo mismo con el crédito .
En teoría, las implementaciones de Prolog pueden evaluar estas reglas en cualquier orden, por lo que podría haber escrito;
miser(X) :- avoircrédit(X), NOT avoirargent(X). miser(X) :- avoirargent(X).Lo cual es bueno, porque las dos opciones se excluyen mutuamente. Sin embargo, comprobar si puede obtener un préstamo no es necesario si sabe que tiene el dinero. También en la práctica, las implementaciones de Prolog probarán la regla que escribió primero . Puede usar el operador de corte para decirle al intérprete que omita la segunda opción si la primera es suficiente. Por ejemplo:
miser(X) :- avoirargent(X), !. miser(X) :- avoircrédit(X), NOT avoirargent(X).Esto se llama operador de parada verde . ¡ El ! simplemente le dice al intérprete que deje de buscar una alternativa. Pero nota que si necesita el dinero, él necesita evaluar la segunda regla, y lo hará. Evaluar tener dinero en la segunda regla es bastante inútil porque sabes que no tienes dinero , por la sencilla razón de que, de lo contrario, la segunda regla no se evaluaría. También puede cambiar el código a:
miser(X) :- avoirargent(X), !. miser(X) :- avoircrédit(X).Esto se llama operador de parada roja , porque es peligroso hacerlo. Ahora depende de la ubicación correcta del operador de parada y del orden de las reglas para determinar su significado lógico. Si las reglas se confunden, ahora puede usar su tarjeta de crédito antes de gastar su dinero extra.
En su lugar, escribirías:
miser(X) :- avoirargent(X), ! ; avoircrédit(X).que dice: para apostar X, o tengo este dinero por adelantado o tengo el crédito necesario.
En general, Prolog no impone un estado a los parámetros de un predicado: no son parámetros 'dados' o 'resultados', ni siquiera parámetros 'dados / resultados', su estado es irrelevante a priori y se definirá según las consultas, ya veces se utilizan los predefinidos.
Esto a menudo permite la definición de predicados reversibles: las consultas cerradas, que proporcionan resultados a partir de los datos, se pueden invertir en consultas abiertas, buscando los datos que conducen a un resultado positivo.
la edad (capitán, 45) es verdadera o falsa; age (capitán, X) pregunta cuál es la edad X del capitán, age (X, 45) pregunta cuál X tiene 45 años.Esta posibilidad se utiliza en el generador / aceptador anterior.
Tomemos árboles binarios con nodo f y hoja 0 o 1.
symetrique(0,0). symetrique(1,1). symetrique(f(A,B),f(Y,X)):-symetrique(A,X), symetrique(B,Y).El uso estándar de este predicado es del tipo:
?- symetrique(f(f(0,1),1),R). R = f(1,f(1,0))Pero también podemos tener:
?- symetrique(A,f(f(0,1),1)). A = f(1,f(1,0))Como lenguaje de programación, Prolog se distingue por:
Prolog se centró desde un principio en el campo de las bases de datos relacionales , a las que aporta una gran flexibilidad en cuanto a consultas, tan pronto como son deducibles de los hechos: se convierten así en bases de datos deductivas . Por lo tanto, una base de datos de estilo familiar (Padre, Madre, ListOfChildren) podrá, con algunas reglas, responder varias preguntas de genealogía.
Más allá de eso, Prolog también puede ofrecer un sistema de consultas común a un conjunto de bases de datos interdependientes; al combinar las relaciones básicas disponibles, obtenemos los servicios de una base de datos virtual que combina estas bases de datos, de ahí un considerable enriquecimiento de las posibles solicitudes.
El procesamiento lingüístico es posible en Prolog sobre la base de gramáticas formales .
un ACEPTADOR / GENERADOR
% générateur de phrases acceptables gen(X):- phrase(X), writeln(X), fail; writeln('---------'). % % accepteur % syntaxe phrase([S, V|Suite]):- sujet(S), verbe(V), ( Suite=[]; Suite=[C], complement(C)). sujet(S):- est1(S, pronom); est1(S, nom). verbe(V) :- est1(V, present). complement(C):- est1(C,nom); est1(C,adverbe). % emploi lexique est1(Mot, Cat):- dico(Cat, L),dans(Mot, L). dans(X, [Y|Z]):- X = Y ; dans(X, Z). dico(nom, [andre, marie, pierre, sylvie]). dico(pronom, [il, elle, on]). dico(present, [aime, chante, charme, ennuie, observe]). dico(adverbe, [bien, fort, mal, peu]).DIÁLOGO:
1 ?- phrase([pierre, aime, sylvie]). true . % phrase acceptée 2 ?- phrase([elle, chante]). true . % phrase acceptée 3 ?- phrase([on, danse]). false. % ''danse'' est inconnu 4 ?- phrase([il, X]). X = aime ; X = chante ; X = charme ; X = ennuie ; X = observe ; false. % phrases acceptées (énumérées par relance) 5 ?- gen([il, X]). [il,aime] [il,chante] [il,charme] [il,ennuie] [il,observe] --------- true. % génération en bloc des phrases conformes à la demandeun ANALIZADOR relacionado
% analyse grammaticale % syntaxe analyse([S,V], ph(AS, AV)):- sujet(S, AS), verbe(V, AV). analyse([S, V, C], ph(AS, gv(AV, AC))):- sujet(S, AS), verbe(V, AV), complement(C, AC). sujet(S, sujet(pronom, S)):- est1(S, pronom). sujet(S, sujet(nom, S)) :- est1(S, nom). sujet(S, sujet('???', S)). verbe(V,verbe(present, V)) :- est1(V, present). verbe(V,verbe('???', V)). complement(C, comp(nom, C)):- est1(C,nom). complement(C, comp(adv, C)):- est1(C,adverbe). complement(C, comp('???', C)). % même partie lexique que précédemmentDIÁLOGO:
1 ?- analyse([sylvie, chante], A). A = ph(sujet(nom, sylvie), verbe(present, chante)) . 2 ?- analyse([pierre, aime, sylvie], A). A = ph(sujet(nom, pierre), gv(verbe(present, aime), comp(nom, sylvie))) . 3 ?- analyse([tu, bois], A). A = ph(sujet(???, tu), verbe(???, bois)). 4 ?- analyse([il, chante, faux], A). A = ph(sujet(pronom, il), gv(verbe(present, chante), comp(???, faux))) .dónde los '???' denotar errores o limitaciones del programa.
Las aplicaciones lingüísticas de Prolog se han simplificado y ampliado mediante el uso de DCG ( Definite Clause Grammar (en) ) (Pereira & Warren, 1980).
Desde allí, puede utilizar Prolog para la traducción automática o semiautomática.
Con mayor frecuencia, un analizador simple permitirá el uso de consultas pseudo-naturales para consultar bases de datos relacionales.
Las aplicaciones Prolog interesantes a priori podrían tener tiempos de ejecución excesivos debido a la combinatoria subyacente. Prolog y la programación lógica han dado lugar a un movimiento de programación que combina la mayoría de las características específicas de Prolog y las contribuciones de la programación de restricciones para conducir, con Prolog IV (1996), a la programación de lógica de restricciones (PLC). Eficaz en problemas combinatorios, especialmente en CAD , investigación de operaciones y juegos.
De hecho, se puede, por ejemplo, imponer que n variables que comparten un dominio con n valores son mutuamente excluyentes, lo que reduce el número de casos de n ^ n a n! Por ejemplo, para n = 10, de 10 mil millones a 3.6 millones.
En 1980, el proyecto japonés de 5ª generación (en) había puesto grandes esperanzas en la paralelización de Prolog, que se ha enfrentado al hecho de que Prolog es inspiración gramatical, sus conectores lógicos no son conmutativos. Sin embargo, el uso de las reglas se puede acomodar en un modo de canalización, interrumpible si es necesario. O la regla:
musicienGrec(X) :- musicien(X), grec(X).Tan pronto como Prolog encuentra un músico, puede verificar si es griego, en cuyo caso esta es una primera respuesta. Por tanto, la verificación de la nacionalidad de un músico se puede realizar mientras continúa la búsqueda de otros músicos conocidos por el sistema. Este proceso es tanto más efectivo cuando la búsqueda comienza con el predicado más selectivo: este es el caso si el sistema conoce menos músicos que griegos.
Prolog permite el razonamiento por inducción y, por lo tanto, brinda la posibilidad de verificar conjeturas. Su capacidad para procesar árboles que pueden representar fórmulas permite su uso en álgebra .
Más allá de las aplicaciones puramente de Prolog, la posibilidad de combinar Prolog con lenguajes tradicionales hizo posible a partir de la década de 1985 proporcionar muchas aplicaciones con módulos inteligentes como los módulos expertos. Sobre una base de rendimiento comparable, estos módulos aumentan así la flexibilidad y la relevancia de las aplicaciones.