Lenguaje de programación lógica prólogo. Prolog: un increíble lenguaje de programación Descripción de Prolog

La aparición de Prologue se debió al desarrollo de la lógica, las matemáticas y la programación. Este último jugó el papel más importante. Los especialistas en lógica y matemáticas intentaron poner la programación en el "camino correcto", pero el desarrollo de la tecnología de la información mostró un resultado completamente diferente.

La programación imperativa pragmática resultó ser más prometedora. "Prolog" tuvo éxito como lenguaje de programación, pero no se convirtió en la base de la inteligencia artificial.

Programación clásica versus lógica

Una persona toma decisiones difíciles de forma lógica y razonable. Casi sin pensar, una persona actúa sabiamente. Si no tomamos en cuenta decisiones que requieren recopilar información, analizarla y realizar cálculos complejos, entonces cualquier resultado es rápido, preciso y razonable.

Este hecho siempre ha dado una razón ilusoria para considerar la creación de una herramienta para la toma de decisiones como una cuestión sencilla. Con la llegada de Prologue, parecía que la cuestión de la inteligencia artificial era una cuestión de tecnología, y al Homo sapiens se le ocurrieron tres leyes de la robótica. Sin embargo, la inteligencia artificial siguió siendo un fantasma y las tres leyes de la robótica resultaron ser sacadas de un cuento de hadas: "haz esto, no sé qué".

La programación en el sentido clásico de la palabra (a menudo se utilizan los términos "procedimental", "imperativo" o "funcional") se ha desarrollado y superado con éxito los "tiempos convulsos" de los años 80 y 90, cuando existían innumerables lenguajes de programación.

La lucha de manifestación entre “Pascal” y “Si” duró mucho tiempo y fue brutal, pero terminó de manera neutral y silenciosa. Lo que queda es la idea de un buen lenguaje de programación y varias implementaciones exitosas del mismo.

Esto no quiere decir que Prolog como lenguaje de programación no haya evolucionado. Pero no logró los objetivos declarados. Hoy no sólo podemos decir, sino también justificar: “Prólogo” es un lenguaje académico para:

• Objetivos de aprendizaje;
• lógica de predicados;
• matemáticas;
• aplicación estrecha.

Es dudoso que esta afirmación pueda ser refutada. La inteligencia artificial no sólo se utiliza ampliamente, sino que también es un acontecimiento muy grave que cambia radicalmente la estructura social y la imagen del mundo.

La programación en el lenguaje Prolog para inteligencia artificial no se llevó a cabo: durante más de cuarenta años de historia del lenguaje, no ha habido un solo evento radicalmente nuevo que sea relevante para la conciencia pública y que indique lo contrario.

La realidad objetiva es ésta: no es tanto el más fuerte el que sobrevive, sino lo que tiene demanda y es relevante.

"Prolog" es un lenguaje de programación declarativo

Tener una herramienta para describir hechos y reglas es bueno, pero ¿cuál es el punto? Los hechos y las reglas encajan perfectamente en una base de datos normal. Un programador clásico calificado proporciona un diálogo interactivo para el usuario y este último resuelve sus problemas.

Si es necesario, el programador perfecciona el diálogo y el usuario complementa la base de datos con hechos y reglas. Una opción absolutamente funcional y probada durante décadas para implementar una gran cantidad de problemas ya resueltos y solucionables.

Una presentación declarativa de hechos y reglas en cualquier implementación del lenguaje de programación Prolog es una convención, un intento de formalizar la realidad en su estado intelectual. La programación convencional no toca el intelecto. La programación clásica se conforma con el puesto: descripción y procesamiento de datos. Hay muchos problemas aquí, pero hay muchas soluciones brillantes que funcionan.

"Prolog" como lenguaje de programación son los hechos:

• madre (María, Natasha); - María - la madre de Natasha;
• papá (Evgeniy, Marina); - Evgeniy es el padre de Marina.

Aquí un dato salta a la vista: “María” y “Marina” son nombres diferentes. Nada le impide agregar el hecho:

• papá (Eugene, María); - Evgeniy es el papá de María.

Estas descripciones dan vida a las reglas:

• padre(x,y)<- папа (x, y);
• padre(x,y)<- мама (x, y);

Pero no nos permiten concluir que papá es el padre de Marina y Marina es la madre de María. Este problema se puede resolver; puedes agregar una regla más, agregar un hecho más. Pero ¿cuántas de estas acciones deberían tomarse en una situación real?

De hecho, "Prolog" como lenguaje de programación es un ejemplo de declaración de hechos y reglas, pero no de la lógica a la que está acostumbrada la conciencia de un programador clásico. "Prolog" se posiciona como un lenguaje de lógica de predicados, pero es posible aprender a programar en él solo a través de ejemplos y descripciones de muestra de los desarrolladores de una implementación específica del lenguaje.

La familia del prólogo

Francia es considerada el lugar de nacimiento de Prologue y 1973 es el año de nacimiento. El interés por el idioma se renovaba periódicamente, pero disminuía con una estabilidad envidiable. El lema del idioma: “¡La lógica de predicados es elemental! Esta es una manera de explicar cómo funciona el pensamiento” - y siguió siendo el lema.

Cualquier implementación del lenguaje de programación Prolog siguió estrictamente la lógica de predicados, pero siempre incluyó ideas clásicas de programación procedimental. Es más correcto decir "imperativo", ya que este término se utiliza con más formalidad que el de procedimiento, funcional, orientado a objetos u otro.

Cualquier programación trata sobre datos y su procesamiento. Las construcciones del lenguaje deben describir el problema que se está resolviendo con la mayor precisión posible, razón por la cual todas las implementaciones conocidas de Prolog: Turbo Prolog, Win Prolog, SWI Prolog, GNU Prolog, Visual Prolog y otras contienen, además de construcciones declarativas, expresiones imperativas ordinarias.

Se cree que la familia Prologue se desarrolla en organizaciones académicas y de investigación y, por lo tanto, sólo se puede hablar de ella como un lenguaje común en un sentido conceptual. Sin embargo, se puede considerar el hecho mismo de que el concepto de "Prolog" está vivo y en desarrollo: este lenguaje tiene un alcance y tiene demanda en una cierta gama de tareas.

La base de la inteligencia artificial

El interés por la inteligencia artificial nunca ha decaído, simplemente empiezan a hablar de ello cuando surge la próxima ocasión, pero Prolog nunca se ha asociado con la inteligencia artificial más que con un lenguaje de programación clásico común y corriente.

A finales de los años 80 surgió un proyecto intelectual real, relevante y popular “La máquina inventadora”. Hubo un intento real de utilizar Prolog para formalizar una enorme base de conocimientos prácticos (datos) sobre invenciones, leyes físicas, químicas y de otro tipo.

El resultado no se logró; hubo que escribir demasiados hechos y reglas en Prolog como lenguaje de programación, que eran de carácter imperativo banal. Mientras tanto, muchos productos de software exitosos se implementaron en paralelo en lenguajes comunes.

A principios de los años 90, se implementó con éxito un proyecto de un sistema intelectual real que simulaba el comportamiento de un niño menor de 3 años en una computadora de la UE. Ni siquiera se consideró la opción de utilizar Prolog.

Este sistema intelectual no sólo "descubrió" qué eran mamá y papá, y en qué se diferenciaban María de Marina, sino que también, sin mucho esfuerzo, saltó de forma independiente de los conocimientos adquiridos sobre estos temas a las pelotas y sus diferencias con los cubos, a los colores de objetos y... (!) a las matemáticas elementales: las operaciones aritméticas simples resultaron estar dentro de sus capacidades basándose en los conocimientos adquiridos al resolver problemas completamente diferentes.

No se puede decir que la programación clásica esté por delante de Prolog en términos de dominio del territorio de la inteligencia artificial, pero da resultados reales.

En cuanto a la inteligencia como tarea, aparentemente la cuestión aquí no radica en el lenguaje, sino en la idea de implementación. Si el ensamblador de 1991 pudo “convertirse en la base” de un sistema inteligente de inteligencia situacional, entonces la cuestión claramente no reside en el lenguaje de implementación, sino en la idea.

Esta lección cubre los conceptos básicos del lenguaje Prolog. Entonces, en esta lección aprenderemos los conceptos básicos de escribir programas en Prolog.

Primero, recordemos Forma normal de Backus-Naur (BNF), que fue creado para una descripción formal de la sintaxis de los lenguajes de programación en 1960. Sus autores son John Backus y Peter Naur.

Entonces, El BNF ha adoptado las siguientes designaciones:

El símbolo::= leído como "un-priorato"("esto es"). A la izquierda del símbolo está el concepto que se explica, a la derecha está la estructura explicativa. Por ejemplo,

<Имя> ::= <Идентификатор>

Las partes de una expresión utilizadas para indicar una estructura sintáctica de un idioma se colocan entre corchetes angulares; en nuestro ejemplo es<Имя>Y<Идентификатор> .

Símbolo | medio "o" lógico y se utiliza para distinguir entre diferentes explicaciones alternativas igualmente válidas de un concepto definido.

Con este símbolo puede, por ejemplo, definir un dígito decimal:

<цифра> ::= 0|1|2|3|4|5|6|7|8|9

Si parte de una construcción está entre corchetes, esto significa que es opcional, es decir. puede faltar.

Así que graba

<Целое число> ::= [-]<Положительное целое число>

dice que un número entero puede explicarse como un número entero positivo que puede o no estar precedido por un signo menos.

El símbolo * indica que la construcción sintáctica que tiene delante se puede repetir un número arbitrario de veces (comenzando desde cero en adelante). En lugar del símbolo *, a veces se utilizan llaves ((, )), que son esencialmente equivalentes a él.

Definamos nuevamente un número entero positivo usando la notación BNF:

<Положительное целое число> ::= <цифра>[<цифра>]*.

Lo que significa que un número entero positivo consta de uno o más dígitos.

Estructura del programa en lenguaje Prolog

Un programa de lenguaje estándar consiste en siguientes secciones :

1. Constantes

Sección opcional de definición de constantes.

2. Dominios

Sección de descripción del dominio (similar a la descripción del tipo de datos).

En Turbo Prolog puedes seleccionar tipos de datos simples:
char - tipo de carácter
entero - entero
real - número real
cadena es una secuencia de caracteres de tipo char, que está entre comillas
símbolo: una secuencia de letras del alfabeto latino, números y guiones bajos, que comienza con una letra minúscula (luego sin comillas) o entre comillas (luego con una letra mayúscula)

3. Predicados

Sección para describir predicados (similar a la sección para describir procedimientos y funciones); Es esencialmente una plantilla para escribir hechos en la sección de Cláusulas.

4. Cláusulas

Declaraciones (analógicas: cuerpo del programa principal).

5. Meta

La declaración objetivo es "meta".

Tarea de prólogo 2_1: Inicie el compilador. Cree un nuevo archivo y escriba el código del programa que imprime la respuesta a la pregunta. “¿A María le gustan las manzanas?”(Responde verdadero o falso). El código está a continuación:

dominios a= símbolo predicados le gusta (a, a) cláusulas le gusta (maría, manzanas) .

dominios a=símbolo predicados le gusta (a,a) cláusulas le gusta (maría,manzanas).

Vaya a la ventana de diálogo (menú Ejecutar) e ingrese la consulta:

le gusta (maría, manzanas)

le gusta (maría, manzanas)

Como resultado, la respuesta verdadera debería aparecer en la ventana.

Hechos y reglas

Un programa escrito en Prolog a menudo se llama base de conocimientos.

La base de conocimientos de Prolog consta de propuestas, es decir. declaraciones, cada una de las cuales termina con un punto.

Hay dos tipos de ofertas: datos Y normas.

Las oraciones regla tienen la forma:

R:- B1,… , Bn.

donde A es título o cabeza oraciones, y B1,..., Bn son cuerpo.

Hecho generalmente afirma, que algunas cosas se han hecho entre objetos actitud Y comprende :

• relación
• objeto u objetos encerrados entre paréntesis (argumentos)
• termina con un punto (.)

Hecho de ejemplo:

le gusta (bill, perros) .

le gusta (bill, perros).

donde los me gusta son un hecho
bill, perros: argumentos de hecho entre los cuales se cumple la relación (me gusta)

Porque la relación en lógica matemática generalmente se llama predicados , entonces a veces usaremos el concepto "predicado" en lugar de "hecho" o "normas".

De este modo, el predicado (hecho) puede consistir en ya sea solo por el nombre, o del nombre y la siguiente secuencia de parámetros (argumentos), que están entre paréntesis.

Si un hecho consta sólo de un título, entonces podemos decir que el hecho es una frase cuyo cuerpo está vacío .

Un argumento de hecho o predicado puede ser constante, variable o objeto compuesto; la llamada terreno(n-ubicación) hecho.

La diferencia entre una constante y una variable: una constante obtiene su valor en la sección de descripción constante, mientras variable inicializado mientras el programa se está ejecutando.

En TProlog nombre del predicado o hecho puede contener: letras latinas, números, guiones bajos y comenzar con una letra o guión bajo.

En el siguiente ejemplo, coloque el cursor sobre partes de las estructuras y aparecerá información sobre herramientas:

le gusta (bill, perros). - A Bill le encantan los perros.
pájaro (vorobej). El pájaro es un gorrión.

Así, en el ejemplo, me gusta es el nombre de un predicado de dos argumentos (hecho) con la constante de cadena " bill " como primer argumento y " dogs " como segundo argumento.

Los argumentos con valores conocidos o constantes deben comenzar con letras minúsculas.

Tarea de prólogo 2_2: Se proporciona el comienzo del programa (sección dominios y predicados) para la base de datos. "La edad del niño". Compile datos para el programa basándose en los datos de las secciones indicadas y la siguiente información: Iván tiene 2 años, Alex tiene 3 años, María tiene 5 años.

dominios a= símbolo b= entero predicados edad(a, b) cláusulas edad(...,... ) . ... (...,...) . ... (...,...) .

dominios a=símbolo b=entero predicados edad(a,b) cláusulas edad(...,...). ...(...,...). ...(...,...).

Escriba el código del programa en el compilador.

Objetivos

Objetivo es una declaración del problema que el programa debe resolver. El objetivo también sirve como “desencadenante” para iniciar el programa.

Turbo Prolog utiliza ambos, que están contenidos en el programa y que se ingresan desde el teclado después de iniciar el programa. Aquí hay dos opciones:

1. Si el objetivo es hecho, luego Turbo-Prolog responde Verdadero(verdad o FALSO(mentir):

Me gusta el objetivo (María, X).

Literal: ¿Qué le gusta a María?

Importante: Las variables comienzan con letras mayúsculas.

* El concepto de variable en Prolog se analizará en .

De este modo, objetivo consta de predicados interrelacionados. Su estructura es exactamente la misma que la de un hecho. Aquellos. objetivo A menudo coincide con una regla o un hecho..

Entonces, nuestro ejemplo puede ser tanto un hecho como un objetivo:

le gusta (maría,manzanas). — María ama las manzanas Y ¿A María le gustan las manzanas?

Algoritmo para compilar un programa.

El programa para el compilador TProlog consta de las secciones analizadas en el ejemplo:

cláusulas le gusta (maría, manzanas). le gusta (maría, naranjas). color(manzanas,rojo).

Datos

Me gusta el objetivo (maría, X), escribir ("maría lyubit", X).

objetivo me gusta(maría,X),escribir("maría lyubit ", X).

Pedido

El resultado un ejemplo sería: "manzanas mary lyubit".

En este ejemplo, el objetivo está escrito en forma de sección META directamente en el programa, pero debe tener en cuenta que la mayoría de las veces los objetivos que requieren una respuesta lógica (verdadero o falso) se escriben en la ventana de diálogo (el objetivo entonces no está escrito en el programa)

ciclo sin fin

En el ejemplo descrito anteriormente, el resultado devuelve sólo el valor del primero de tres hechos:

cláusulas me gusta (maría, manzanas). le gusta (maría, naranjas). color(manzanas, rojas) . Me gusta el objetivo (maría, X), escribir ("maría lyubit", X).

cláusulas le gusta (maría, manzanas). le gusta (maría, naranjas). color(manzanas,rojo). objetivo me gusta(maría,X),escribir("maría lyubit ", X).

El resultado son sólo manzanas. Aunque todavía quedan naranjas.

Para generar todos los valores, debe organizar ciclo sin fin que en el código parece una declaración de error establecida al final de la sección OBJETIVO

La sección de cárcel del mismo ejemplo, pero con un bucle infinito, se vería así:

objetivo me gusta (maría, X), escribir ("maría lyubit", X), nl, fallar.

Me gusta el objetivo (maría, X), escribir ("maría lyubit", X), nl, fallar.

nl: significa pasar a la siguiente línea (cada valor se imprime en una nueva línea).
Resultado:
"manzanas mary lyubit".
"naranjas mary lyubit".

Código completo del programa:

dominios a= símbolo predicados le gusta (a, a) cláusulas le gusta (maría, manzanas) . le gusta (maría, naranjas). color(manzanas, rojas) . objetivo me gusta (maría, X), escribir ("maría lyubit", X), nl, fallar.

dominios a=símbolo predicados le gusta (a,a) cláusulas le gusta (maría,manzanas). le gusta (maría, naranjas). color(manzanas,rojo). Me gusta el objetivo (maría, X), escribir ("maría lyubit", X), nl, fallar.

Veamos otro ejemplo.

Ejemplo: Compilar una base de datos para el poema. "La casa que construyó Jack".
Cree diferentes consultas a la base de datos (ejecute algunas consultas en la ventana de Diálogo y la otra parte en la sección Objetivo del programa).

Código de programa sin solicitudes:

dominios a= símbolo predicados construido (a, a) almacenado (a, a) roba (a, a) atrapa (a, a) charla (a, a) ordeña (a, a) regaña (a, a) despierta ( a, a) cláusulas construidas (gato, casa). almacenado (trigo, closet_at-home). roba (bird_tit, trigo). capturas (gato, pájaro_tit). charlatanes (gato, pájaro_tit). charlatanes (perro, gato). leches (vieja, vaca). regaña (pastor, anciana). despierta (dos_gallos, pastor).

dominios a=símbolo predicados construidos (a,a) almacenados (a,a) roba (a,a) atrapa (a,a) charla (a,a) ordeña (a,a) regaña (a,a) despierta ( a ,a) cláusulas construidas (gato, casa). almacenado (trigo, closet_at-home). roba (bird_tit, trigo). capturas (gato, pájaro_tit). charlatanes (gato, pájaro_tit). charlatanes (perro, gato). leches (vieja, vaca). regaña (pastor, anciana). despierta (dos_gallos, pastor).

Ejecutar consultas en la ventana de diálogo:

Construida (X, casa). /*¿Quién construyó la casa?*/

Respuesta: X=Jack

? – atrapa (gato, Y) /*¿A quién atrapa el gato?*/

Respuesta: Y= pájaro_tit

? – almacenado (X, armario_en-casa), roba (X,Y). /*Qué se guarda en el armario de casa y quién lo roba*/

Respuesta: X = trigo, Y = pájaro_tit

Ejecución de consultas en la sección Objetivo:

objetivo postroil(X, casa), escribir (X), nl, fallar.

objetivo postroil(X,casa),escribir(X),nl,fallar.

Tarea de prólogo 2_3:

1. Crear una base de datos “Nombres del día y aficiones de los amigos”.

• ¿De quién es el onomástico en septiembre?
• ¿Cuándo es el onomástico de Iván?
• ¿A quién le encanta bailar?
• ¿Quién ama los libros y los deportes?
• ¿Qué le gusta a Pedro?

dominios a= símbolo b= entero predicados cumpleaños(a, b, a) me gusta(a, a) cláusulas cumpleaños(nataly, 8, septiembre). cumpleaños(yana, 25 de agosto). cumpleaños(nina, 28, septiembre). cumpleaños(peter, 2, agosto). cumpleaños(ivan, 12 de agosto). Me gusta(nataly, libros). le gusta(nataly, deporte) . Me gusta (yana, libros). le gusta(yana, baila) . le gusta (peter, música). le gusta(peter, baila) . Me gusta (ivan, deporte). Me gusta (ivan, libros). Meta /* cumpleaños(X,Y,septiembre),write(X," rodilas ", Y, " sentyabrya"),nl,fail.*/

dominios a=símbolo b=entero predicados cumpleaños(a,b,a) me gusta(a,a) cláusulas cumpleaños(nataly, 8, septiembre). cumpleaños(yana, 25 de agosto). cumpleaños(nina, 28, septiembre). cumpleaños(Pedro, 2 de agosto). cumpleaños(iván, 12 de agosto). le gusta(nataly, libros). le gusta(nataly, deporte). le gusta(yana, libros). le gusta(yana, baila). le gusta(peter, música). le gusta(peter, baila). le gusta(ivan, deporte). le gusta(ivan, libros). Objetivo /* cumpleaños(X,Y,septiembre),escribir(X," rodilas ", Y, " sentyabrya"),nl,fail.*/ … , escribir(…), nl, fallar.

Tarea de prólogo 2_4:

1. Crear una base de datos "Asignaturas y profesores", que contiene información sobre el nombre de la asignatura, cargo y apellido del docente, número de semestre, reporte.
2. Cree consultas a la base de datos basándose en lo siguiente:

• ¿En qué materias es el examen?
• ¿Qué materia y cuándo enseña el profesor asociado de Frost?
• ¿Qué tipo de informes?
• ¿Quién lee el PRZ y cuándo?

dominios a= símbolo b= entero predicados enseñar(a, a, a, b) vedomost(a, a) cláusulas enseñar(prz, assistent, ivanova, 2). enseñar(toi, docente, morozov, 4) . enseñar(mpi, docente, petrova, 5). vedomost(toi, examen) . vedomost(prz, zach) . vedomost(mpi, examen) . Meta /* vedomost(X,examen),write("examen po predmetu ", X),nl,fail. */..., escribir (...), nl, fallar.

dominios a=símbolo b=predicados enteros enseñan(a,a,a,b) vedomost(a,a) cláusulas enseñan(prz, assistent,ivanova,2). enseñar(toi, docente, morozov,4). enseñar(mpi,docente, petrova, 5). vedomost(toi, examen). vedomost(prz, zach). vedomost(mpi, examen). Objetivo /* vedomost(X,examen),write("examen po predmetu ", X),nl,fail. */…, escribir(…), nl, fallar.

* Para mayor comodidad, después de ejecutar la siguiente solicitud, coméntela (/* ... */) y comience a escribir el código para la siguiente solicitud.

* Al utilizar materiales, un enlace a

Funcional;

Procesal;

Orientado a objetos;

Declarativo (relacional).

Programa escrito en Idioma funcional, expresa un algoritmo para resolver un problema en términos de los valores que devuelven las funciones. Por tanto, un programa representa un conjunto de funciones, cada una de las cuales devuelve sólo un valor de un determinado tipo. El trabajo del programa (el algoritmo para resolver el problema) es una llamada secuencial de funciones. Los lenguajes funcionales incluyen C.

Programa escrito en lenguaje procesal, expresa un algoritmo para resolver un problema en términos de acciones (procedimientos) que deben realizarse. La diferencia entre un procedimiento y una función es que un procedimiento puede devolver cualquier cantidad de valores, incluido ninguno. Así, el funcionamiento del programa es una llamada secuencial de procedimientos. Los lenguajes procesales incluyen Pascal, Basic, etc. Cabe señalar que en cualquier lenguaje de procedimiento es posible definir y utilizar funciones, y en un lenguaje funcional, procedimientos (funciones que no devuelven valores, generalmente definidas con el modificador void).

Programa escrito en lenguaje orientado a objetos, es un conjunto de objetos que interactúan entre sí enviando mensajes. Cada objeto se caracteriza por un componente informativo (un conjunto de atributos) y un componente conductual (un conjunto de eventos y métodos). El trabajo del programa es un intercambio secuencial de mensajes (métodos de llamada) entre objetos. Los lenguajes orientados a objetos incluyen Object Pascal, Visual Basic, C++, Java, etc. Cabe señalar que cualquier lenguaje orientado a objetos tiene la posibilidad de programación procedimental.

Lo que es común a todas las categorías de idiomas enumeradas es que el programa describe lo que se debe hacer y cómo resolver el problema, es decir, Se describe la secuencia de resolución del problema.

Programa escrito en lenguaje declarativo, es una descripción del área temática a través de un conjunto de relaciones (relación en inglés) entre objetos (entidades) y la formulación de la meta (tarea) a resolver. A diferencia de los lenguajes enumerados anteriormente, dicho programa no describe explícitamente la secuencia de acciones necesarias para resolver un problema. Como regla general, el procedimiento para encontrar una solución se realiza automáticamente utilizando el aparato matemático o lógico apropiado que subyace al lenguaje y se implementa en su intérprete específico 1 (compilador 2). Los lenguajes declarativos incluyen Prolog, SQL, etc. Por tanto, la ventaja indudable de los lenguajes declarativos es la concentración de la atención del desarrollador en lo que se debe hacer y no en cómo.

Otra clasificación de lenguajes de programación se basa en estilo de programación :

- imperativo– un programa es una secuencia de declaraciones (comandos ejecutados por una computadora), con la ayuda de las cuales el programador debe explicar a la computadora cómo resolver un problema(lenguajes de programación funcionales, procedimentales y orientados a objetos);

- declarativo– un programa es un conjunto de declaraciones que describen un área temática o una situación actual, con la ayuda de las cuales el programador debe describir, lo que hay que resolver (encontrar)– el sistema de programación imperativo buscará una solución.

Existe una clasificación muy conocida de los lenguajes de programación según su proximidad al lenguaje de máquina o al lenguaje humano natural. Los que están más cerca de la computadora se denominan lenguajes de bajo nivel (Assembler), y los que están más cerca de los humanos se denominan lenguajes de alto nivel (Basic, Pascal, Java, etc.). En este sentido, los lenguajes declarativos pueden denominarse lenguajes de nivel superalto o de más alto nivel, ya que están muy cerca del lenguaje humano y del pensamiento humano.

En 1965, en “Una lógica orientada a máquinas basada en el principio de resolución”, 3 publicado en el número 12 del Journal of the ACM, J. Robinson presentó un método para buscar automáticamente pruebas de teoremas en el cálculo de predicados de primer orden, llamado "principio de resolución". De hecho, la idea de este método fue propuesta por Herbrand en 1931, cuando aún no existían las computadoras (Herbrand, “Une Methode de Demostración”, These, París, 1931). Robinson modificó este método para que fuera adecuado para uso automático (computador) y desarrolló un algoritmo de unificación eficaz que constituye la base de su método.

La idea de utilizar la lógica como lenguaje de programación se originó a principios de los años 1970. Los primeros investigadores que desarrollaron esta idea fueron Robert Kowalski de Edimburgo (base teórica, artículos de 1971 y 1974), Maarten van Emden de Edimburgo (sistema de demostración experimental) y Alain Colmeroe Colmerauer) de Marsella (realización, 1973). En 1973, un "grupo de inteligencia artificial" dirigido por Alain Colmeroe creó un programa en la Universidad de Marsella diseñado para demostrar teoremas. Este programa se ha utilizado para construir sistemas de procesamiento de textos en lenguaje natural. El programa de demostración de teoremas se llamó Prolog (en francés PROgrammation en LOGique) y sirvió como prototipo de Prolog. Hay leyendas que dicen que la autora de este nombre fue la esposa de Alain Colmeroe. El programa fue escrito en Fortran y se ejecutó bastante lentamente.

La popularización de Prolog se vio facilitada en gran medida por:

Una implementación eficiente (intérprete/compilador) de este lenguaje para la computadora DEC-10 realizada por David D.H. Warren de Edimburgo en 1977 sirvió como prototipo para muchas implementaciones posteriores de Prolog. Curiosamente, el compilador fue escrito en el propio Prolog. Esta implementación de Prolog, conocida como la "versión de Edimburgo", se convirtió efectivamente en el primer y único estándar del lenguaje;

Desarrollo de una versión para ordenadores personales por Clark y McCabe (Gran Bretaña) en 1980;

Proyecto japonés para crear ordenadores de V generación. A finales de 1978, el Ministerio de Comercio Exterior e Industria (MFTI) de Japón encargó al Instituto de Tecnología Informática de Tokio (ICOT) 4, creado especialmente para este fin, el desarrollo de un proyecto de ordenadores inteligentes. Se suponía que el corazón de estas computadoras no era un procesador aritmético, sino uno especialmente optimizado para trabajar con programas similares a Prologue.

En 1995 se publicó la norma oficial ISO 5 /IEC 6 del lenguaje Prolog (ISO/IEC 13211-1 “Tecnologías de la información - Lenguajes de programación - Prolog - Parte 1: Núcleo general" - “Tecnologías de la información. Lenguajes de programación. Prolog . Parte 1. Núcleo general").

Hoy en día existen bastantes implementaciones de Prolog. Los más famosos son los siguientes: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, MProlog, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic iis Workbench, Strawberry Prolog, SWI-Prolog, Turbo Prolog (PDC Prolog, Visual Prolog), UNSW Prolog, etc. En nuestro país se desarrollaron versiones de Prolog como Prolog-D (S. Grigoriev), Actor Prolog (A. Morozov) y Flang (A. Mantsivoda, V. Petukhin). .

5. Defina los conceptos: "", "", "".

9. ¿Qué se entiende por “ ” y “ ” de la lista?

Y considere soluciones a los problemas más simples en Prolog.

Antes de comenzar, me gustaría responder brevemente a las preguntas urgentes de nuestros lectores:
- ¿Dónde se utiliza realmente Prolog?
- Estos proyectos existen, algunos se citaron en los comentarios al primer artículo. Es importante que la mayoría de los programadores escriban en Prolog no por desesperanza, sino porque les gusta Prolog. Después de todo, Prolog no se puede utilizar para ninguna tarea, como crear una interfaz de usuario o manipular archivos.

¿Por qué hay pocos proyectos de este tipo?
- Porque hay muy pocos programadores que conocen Prolog, no sólo porque la gente no lo ha estudiado, sino porque no lo ha estudiado lo suficiente como para escribir programas completos. La razón principal es que la gente no entiende claramente en qué situaciones es mejor utilizarlo. A menudo se puede ver que los fervientes partidarios de Prolog escriben todo en él, incluidos los controladores de teclado y mouse, razón por la cual el código resulta incluso peor que en C.

¿Por qué no existe una comunidad Prolog?
- Es. Tal es la especificidad del lenguaje que es muy popular en el entorno académico (la mayoría de los sistemas Prolog se escriben en varias universidades y, por el contrario, casi cualquier universidad escribe su propio Prolog), por lo que se puede decir que la aplicabilidad de la lengua sufre. Vale la pena señalar que la comunidad es pequeña, pero muy leal: casi todos los lenguajes conocidos se reflejan en lenguajes modernos (Lisp, ML -> F#, Scala; Smalltalk -> Java, Scala (agentes), scripting -> Ruby), a diferencia de Prologue.

Creo que es suficiente razonamiento filosófico y podemos comenzar con ejemplos reales :)

Al final, como es habitual, aguarda una tarea por un premio.

Ejemplo número 1: búsqueda de números perfectos

Para este ejemplo necesitaremos el predicado is/2. X es 3 + 1 * 2- calcula la expresión de la derecha y la coloca en la variable de la izquierda, esto no es una tarea (!), sino una afirmación de que X = 7. En pocas palabras, la frase X = 7, X = 3 no tiene solución porque X no puede ser 7 y 3 al mismo tiempo.
También necesitamos una solución al problema del tema anterior. La tarea era escribir un predicado que generara todos los números naturales seguidos, aquí está la solución:
enteros(0). enteros(X) :- enteros(Y), X es Y + 1.
En realidad, esta es una versión declarativa del predicado estándar entero/1, que verifica que el argumento sea un número entero. El problema con el predicado estándar es que funciona correctamente para la consulta: - entero (1) y no funciona para la consulta entero (X).

Tarea: escriba un programa que encuentre todos los números perfectos.
La solución es obvia, revisamos todos los números enteros y comprobamos si son perfectos, esta estrategia se aplica muy bien a los lenguajes imperativos, nosotros mismos no nos damos cuenta de cómo inmediatamente buscamos un algoritmo para encontrar una solución, en lugar de analizar el problema. En Prolog, no debemos intentar describir la búsqueda de una solución a un problema, sino intentar describir la formulación del problema, para ello, siga la regla:

No intente describir instrucciones para encontrar una solución, asuma que ya ha encontrado una solución y su tarea es sólo comprobar que se ha encontrado una solución.

Por extraño que parezca, esta estrategia funciona muy bien.
%% Definición declarativa de números naturales ints(0). ints(X) :- ints(Y), X es Y + 1. %% Un número perfecto es 1) un número natural 2) la suma de los divisores es igual al número número_perfecto(X) :- ints(X) , Y es X - 1, calculasum_divisors_till(Sum, X, Y), Sum = X. %% Comprobando la suma de divisores 1er argumento Suma, 2do - el número para el cual estamos buscando divisores, %% 3er - el número hacia arriba para lo cual buscamos divisores calculasum_divisors_till(0, _NumberToDivide , 0). calculasum_divisors_till(Sum, NumberToDivide, Till):- Hasta > 0, Rem es NumberToDivide mod Till, Rem = 0, Ts es Till - 1, calculasum_divisors_till(SumPrev, NumberToDivide, Ts), Sum es SumPrev + Till. calcularsum_divisors_till(Sum, NumberToDivide, Till): - Hasta > 0, Rem es NumberToDivide mod Till, Rem > 0, Ts es Hasta - 1, calcularsum_divisors_till(Sum, NumberToDivide, Ts).

Insertamos el texto fuente en el archivo, iniciamos el intérprete y lo compilamos (mediante la solicitud: -compile("ruta_al_archivo/perfect_numbers.pl"). Escribimos la solicitud :- número_perfecto(X). y el intérprete produce una respuesta cuando presiona ";" da lo siguiente. Tenga en cuenta que la solicitud puede ser :- número_perfecto(X), X > 6. Entonces todas las respuestas serán mayores que 6. Por supuesto, el programa no funciona de manera óptima, la prueba en sí se puede simplificar usando divisores simples, pruébelo.

Ejemplo No. 2: generación de permutaciones.

Para plantear y resolver este problema necesitaremos el concepto de listas. Las listas no son los conceptos básicos del lenguaje; se puede establecer una analogía directa entre listas y listas enlazadas en C. Volvamos a la definición de un término como estructura de datos recursiva.
%% Defina una lista vacía como una lista nula de objetos (nula). %% Definamos una lista de un elemento 1 lista (t (1, nil)). %% Definir una lista de elementos 1, 2, 3 list(t(1, t(2, t(3, nil)))). %% Describamos, por ejemplo, el procedimiento de búsqueda en la lista %% 1. el resultado está en el encabezado de la lista (1er elemento) %% _ - significa una variable insignificante para nosotros miembro(X, t(Y, _ )) :- X = Y. %% 2. el resultado no es el primer elemento, pero está contenido en la cola de la lista después del primer elemento member(X, t(_, Tail)) :- member(X, Cola).

Como muchos dirían, la recursividad ordinaria y para que las listas no parezcan nada especiales en Prolog hay azúcar sintáctico para ellas: se puede escribir nil , t(1, nil) - , t(1, t(2, nil)) - , t( 1, Sublista) - , t(1, t(2, Sublista)) - . Se recomienda utilizar azúcar sintáctico para las listas, porque los nombres internos de los términos pueden diferir (la mayoría de las veces el término se llama ".").
%% 1. el resultado está al principio de la lista (primer elemento) miembro (X,). %% 2. el resultado no es el primer elemento, pero está contenido al final de la lista después del primer elemento member(X, [_| Tail]):- member(X, Tail).
Volvamos al problema original de generar permutaciones. Todo el mundo recuerda perfectamente que el número de permutaciones es n!, pero encarga esta tarea a la mayoría de los programadores y todos recordarán y dirán frenéticamente que escribieron esto en la escuela y olvidaron cómo hacer la búsqueda. En promedio, el algoritmo aparece después del esfuerzo y el tormento en unos 20 minutos. Si conoce Prolog, este algoritmo se puede escribir en 2 minutos o no escribirse en absoluto :)

¿Cómo solucionarlo en Prolog? Utilicemos la regla de no encontrar una solución, sino comprobar que se ha encontrado una solución. Predicado permanente (Fuente, Permutación)- donde Fuente es la lista original, Permutación es una permutación.

%% Si la lista original está vacía, entonces hay una permutación de la lista vacía permanente (,). %% El primer elemento de la permutación debe estar contenido en la lista fuente, %% y debe excluirse inmediatamente de la lista original, %% los elementos restantes deben ser una permutación de la %% lista original restante permanente(Fuente,) :- member_list_exclude(Elemento, Fuente, FuenteExcluida), permanente(FuenteExcluida, Cola). %% Comprobando que el elemento está contenido en la lista y que la 2.ª lista es una lista sin elemento %% El nombre del predicado member_list_exclude coincide con el orden de los argumentos %% El 1.º es un elemento, el 2.º es una lista, el 3.º es un lista sin miembros member_list_exclude (X, , L). member_list_exclude(X, , ) :- member_list_exclude(X, L, Ls).
Pedido :-permanente(, X) genera todas las permutaciones. Curiosamente, las consultas son simétricas. :-permanente(X, ) respecto a los argumentos, aunque esta solicitud se congela y para que funcione es necesario intercambiar member_list_exclude y perm en perm.

Ejemplo No. 3: generación de combinaciones.

En términos de facilidad de implementación, generar combinaciones es similar a generar permutaciones. Necesitamos el predicado miembro/2: el elemento pertenece a la lista. Supongamos que tenemos 2 listas: la primera es la lista original, la segunda es la combinación deseada, debemos verificar la exactitud de la combinación. Los elementos combinados están ordenados en el orden de la lista original.

Miembro(X, ). miembro (X, [_|L]): - miembro (X, L). combinar(, ).

%% Opción 1: El primer elemento de la combinación está contenido en la lista original comb(, ):- comb(List, Tail). %% Opción 2: la combinación es una combinación válida de la cola de la lista, %% es decir, el primer elemento de la lista original no está contenido en la combinación comb([_|List], Tail):- comb( Lista, Cola).

Ejemplo No. 4: clasificación.

Consideremos este ejemplo con cierto detalle e intentemos optimizar la solución principal. El proceso de escritura en Prolog es el siguiente: 1) descripción inicial del problema y obtención de una solución exhaustiva 2) optimización lógica reorganizando los predicados a la derecha 3) optimización lógica introduciendo comprobaciones simplificadas o eliminando condiciones innecesarias 4) introduciendo heurísticas y optimizando casos individuales mediante corte. Opción 1. Clasificación ingenua

Clasificar(, ).< Ms. find_result(result(M, _), result(Ms, Exclude), result(Ms, Exclude)):- Ms =< M.
ordenar (Lista,): - min_list_exclude (Min, Lista, Excluir), ordenar (Excluir, OrdenarRest). %% Excluimos recursivamente el número mínimo, si hay un número en la lista, lo excluimos min_list_exclude(M, [M],). min_list_exclude(Min, , ExcludeRes): - min_list_exclude(Ms, L, Exclude), find_result(resultado(M, L), resultado(Ms, ), resultado(Min, ExcludeRes)). %% Predicado adicional para determinar un par con una clave mínima find_result(resultado(M, L), resultado(Ms, _), resultado(M, L)):- M
Puedes ver que la complejidad de este algoritmo es cuadrática y el principal problema es que buscamos el elemento mínimo cada vez sin almacenar ninguna información útil.

Tenga en cuenta también que estamos intentando determinar cuál es el primer elemento de la matriz ordenada. Opción 2. Clasificación rápida.

Veamos el problema desde el segundo lado e intentemos determinar la ubicación del primer elemento de la lista en la matriz ordenada (aplicar recursividad a la matriz original).< T, split(T,R, Less,Great). split(T, ,Less, ) :- M >ordenar_b(, ). sort_b(, Lista): - dividir(T, R, Menos, Excelente), sort_b(Menos, MenosOrdenación), sort_b(Excelente, GranOrdenación), agregar(MenosOrdenación,, Lista). %% Dividimos el array en 2 arrays más grandes y más pequeños split(_, ,, ). dividir(T,,, Genial):- M
= T, dividir(T,R, Menos,Excelente). %% Pega 2 listas append(, M, M). agregar (, Derecha,): - agregar (Izquierda, Derecha, Res).

Puede ver que hemos mejorado los resultados de clasificación, ya que la clasificación rápida es obviamente más rápida que la clasificación por burbujas. Para mejorar aún más los resultados, podemos recordar la ordenación por combinación, que en cualquier caso da O(n lg n), pero desafortunadamente esta ordenación solo es aplicable a matrices y no a las listas enlazadas con las que estamos trabajando. La única opción para utilizar una estructura de datos adicional para el almacenamiento es un árbol.

Opción 3: ordenar mediante un árbol binario. Para este tipo de clasificación, convertimos la lista original en un árbol binario y luego, recorriendo el árbol por la izquierda, obtenemos una matriz ordenada. Representaremos el árbol mediante un término recursivo..
árbol (Objeto, Subárbol izquierdo, Subárbol derecho)< X, plus(X, R, ResR). sort_t(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). append_list(, L, L). append_list(, R, ) :- append_list(L, R, T). tree_list(nil, ). tree_list(tree(X, L, R), List) :- tree_list(L, ListL), tree_list(R, ListR), append_list(ListL, , List).

sort_tree(, nulo). sort_tree(, Árbol):- sort_tree(L, LTree), más(X, LTree, Árbol). %% Agregar un elemento al árbol plus(X, nil, tree(X, nil, nil)). más(X, árbol(O, L, R), árbol(O, ResL, R)) :- O >= X, más(X, L, ResL). más (X, árbol (O, L, R), árbol (O, L, ResR)): - O

El problema de utilizar un árbol binario es el mismo que el de utilizar la clasificación rápida. El método no garantiza un rendimiento óptimo. En el caso de un árbol binario, el árbol puede estar desequilibrado y el procedimiento para agregarle un elemento puede ser lineal en lugar de logarítmico. Los procedimientos de equilibrio de árboles se realizan específicamente para este propósito; a continuación, como referencia, se proporcionará un algoritmo que utiliza un árbol AVL.

sort_btree(X, Y) :- sort_tree(X, Árbol), tree_list(Árbol, Y). lista_árbol(nulo,). lista_árbol(árbol(X, L, R, _), Lista):- lista_árbol(L, ListaL), lista_árbol(R, ListaR), agregar(ListaL, Lista). sort_tree(, nulo). sort_tree(, Árbol):- sort_tree(L, LTree), plus_tree(X, LTree, Árbol). construct_tree(A, AL, AR, árbol(A, AL, AR, ADepth)):- diff(AL, AR, _, ADepth). diff(AL, AR, ADiff, ADepth): - Depth_tree(ALs, AL), Depth_tree(ARs, AR), ADiff es ALs - ARs, max_int(ALs, ARs, AD), ADepth es AD + 1. max_int(A , B, A):- A > B. max_int(A, B, B):- A =< B. append(, L, L). append(, R, ) :- append(L, R, T). depth_tree(0, nil). depth_tree(X, tree(_, _, _, X)). plus_tree(X, nil, tree(X, nil, nil, 1)). plus_tree(X, tree(O, L, R, _), Res) :- O >= X, plus_tree(X, L, ResL), diff(ResL, R, Diff, Dep), balance_tree(árbol(O, ResL, R, Dep), Diff, Res). plus_tree(X, árbol(O, L, R, _), Res):- O< X, plus_tree(X, R, ResR), diff(L, ResR, Diff, Dep), balance_tree(tree(O, L, ResR, Dep), Diff, Res). %% No rotations balance_tree(Tree, ADiff, Tree) :- ADiff < 2, ADiff >-2. %% Pequeña rotación a la derecha balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result):- ADiff > 1, diff(BL, BR, BDiff, _), BDiff > = 0, construct_tree(A, BR, AR, ASubTree), construct_tree(B, BL, ASubTree, Resultado). %% Gran rotación a la derecha balance_tree(árbol(A, árbol(B, BL, BR, _), AR, _), ADiff, Resultado):- ADiff > 1, diff(BL, BR, BDiff, _), BDiff< 0, BR = tree(C, CL, CR, _), construct_tree(B, BL, CL, BSubTree), construct_tree(A, CR, AR, ASubTree), construct_tree(C, BSubTree, ASubTree, Result). %% Small left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff =< 0, construct_tree(A, AL, BL, ASubTree), construct_tree(B, ASubTree, BR, Result). %% Big left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff >0, BL = árbol(C, CL, CR, _), construct_tree(B, CR, BR, BSubTree), construct_tree(A, AL, CL, ASubTree), construct_tree(C, ASubTree, BSubTree, Resultado).
Este ejemplo no es lo suficientemente expresivo para implementarlo en Prolog, aunque da una idea de programas de tamaño mediano. Para la capacitación, puede implementar el ordenamiento por burbujas o el ordenamiento por inserción, lo dejaremos a discreción del lector.

Ejemplo No. 5 - Problema de transfusión.

Para nuestro próximo problema, considere el problema de estado clásico; este problema refleja mucho mejor los beneficios de usar Prolog. Planteamiento general del problema: dados unos recipientes con agua, es necesario obtener una determinada cantidad de agua en un determinado recipiente mediante vertido. Por ejemplo, tomemos 3 jarras con capacidad de 12 litros, 8 litros, 5 litros, llenamos la 1ª por completo, es decir, con 12 litros y nos ponemos la tarea de obtener 6 litros. Primero, intenta resolver este problema escolar con un bolígrafo y una hoja de papel. :)

Antes de generar varios algoritmos e intentar aplicarlos al problema, primero reescribamos las condiciones en términos de Prolog. Describamos la capacitancia como un término. sosud(Id., Capacidad Máxima, Capacidad Actual), describimos el estado del sistema como una lista de capacidades. Ejemplo . Ahora describamos la solicitud:

%% solve_pr_wo(Estado inicial, Objetivo, Pasos). :- solve_pr_wo(, sosud(X, _, 6), Pasos).

Tenga en cuenta que Goal = sosud(_, _, 6), es decir, no nos importa la capacidad del recipiente, lo principal es que contenga exactamente 6 litros.

Ahora que lo sabemos todo, describamos el método. cheques soluciones, suponiendo que los pasos se especifican en la variable Pasos.

%% No se requiere ningún paso para obtener el estado, %% significa que uno de los buques está en la lista solve_pr_wo(Estado, Objetivo,): - miembro(Objetivo, Estado). %% El primer paso es verter de Sosud a Sosud2 y obtener el estado %% del primer recipiente ResSosud y del segundo ResSosud2. %% Ejemplo específico de un paso: %% mv(sosud(1, 12, 12) -> sosud(2, 8, 0), sosud(1, 12, 4) -> sosud(2, 8, 8)) . solve_pr_wo(Estado, Objetivo,):- %% En primer lugar, verificar en el dominio que los buques están realmente %% contenidos en el estado actual y que no son iguales entre sí miembro(Sosud, Estado), miembro(Sosud2, Estado ), not(Sosud = Sosud2), %% Realizar la transfusión en sí, aquí %% están involucradas las 4 variables de paso mv(Sosud, Sosud2, ResSosud, ResSosud2), %% Reemplazar el estado de los vasos en la lista de estados en girar reemplazar(Sosud, State, ResSosud, State2), reemplazar (Sosud2, State2, ResSosud2, StateX), %% Se deben realizar pasos adicionales utilizando la recursión solve_pr_wo(StateX, Goal, Steps). %% En realidad, el reemplazo habitual de un elemento en la lista es %% reemplazar(ElementToReplace, InList, ElementToReplaceWith, OutList). reemplazar(S, , X, ). reemplazar (S,, X,): - reemplazar (S, L, X, Ls). %% Procedimiento de transfusión: 2 opciones %% el vaso de origen se agotará o el vaso de destino estará lleno %% Vaciado del primer vaso en el segundo mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2) , sosud(Id1, Max1, 0 ), sosud(Id2, Max2, Actual3)) :- Actual >< Max2. %% Переливание из первого сосуда до краев второго mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current >0, Actual3 es Actual2 + Actual - Max2, Actual3 >= 0.

Además, puede parecer que comprobar el dominio no es necesario, porque si los pasos para la transfusión son correctos, entonces no es necesario comprobar lo que describen. De hecho, la integridad de la verificación mejora seriamente las posibilidades de que el programa funcione correctamente. Sería más correcto decir esto: con una verificación excesiva, el programa funcionará, a veces incluso más optimizado que sin ella, pero con una verificación insuficiente, el programa producirá resultados completamente incorrectos o se congelará para algunos datos de entrada.

Bueno, la descripción del programa está escrita: puedes ejecutarlo. No se sorprenda si el programa no funciona, simplemente se congelará :) Esto no es tan malo como podría parecer, porque si el programa no se hubiera congelado, habría dado la respuesta correcta. Necesitamos descubrir por qué se congeló, y aquí nos ayudará comprender cómo Prolog desarrolla las reglas para encontrar una solución. De hecho, no es necesario tener una cabeza capaz de recordar hasta 10 puntos de retorno para comprender que la próxima vez que solve_pr_wo -> llama a solve_pr_wo recursivamente, llama a 2 miembros/2 predicados, que siempre producen el mismo primer y segundo recipiente. (el predicado not causa retroceso y no permite al miembro seleccionar el 1er y el 1er buque). Es decir, el algoritmo fluye constantemente del 1º al 2º y viceversa.

Para resolver este absurdo lo que inmediatamente me viene a la mente es prohibir hacer la misma acción 2 veces, es decir tener un historial de estados y si el estado ya se ha encontrado, entonces prohibir que vuelva a suceder. Resulta que estamos reduciendo el conjunto de estrategias de transfusión aceptables, excluyendo la repetición. De hecho, al reducir el conjunto de estrategias, no limitamos el conjunto de estados admisibles del sistema, es decir, soluciones, lo cual no es difícil de probar.

Versión completa del programa con una impresión de estados y un predicado único para llamar a la solución:

Lista_escritura(). write_list() :- writeln(X), write_list(L). solución:- solve_pr(, sosud(_, _, 6), , Pasos), write_list(Pasos). reemplazar(S, , X, ). reemplazar (S,, X,): - reemplazar (S, L, X, Ls). %% consideraremos la estrategia de transfusión no los pasos en sí, sino simplemente los estados finales %% conociendo los estados inicial y final, no es difícil adivinar qué paso se realizó solve_pr(Estado, Objetivo, _, ) :- miembro( Meta, Estado). solve_pr(Estado, Meta, Historia,): - miembro(Sosud, Estado), miembro(Sosud2, Estado), no(Sosud = Sosud2), mv(Sosud, Sosud2, ResSosud, ResSosud2), reemplazar(Sosud, Estado, ResSosud , Estado2), reemplazar(Sosud2, Estado2, ResSosud2, EstadoX), %%% la misma verificación del estado final no(miembro(EstadoX, )), solve_pr(EstadoX, Meta, , Pasos). %% mv(sosud(_Id, Max, Actual), sosud(_Id2, Max2, Current2), ...,...). %% Vaciando el primer vaso en el segundo mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > 0, Actual3 es Actual2 + Actual, Actual3 =< Max2. %% Переливание из первого сосуда до краев второго mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current >0, Actual3 es Actual2 + Actual - Max2, Actual3 >= 0.

¡Todo funciona ahora! Como ejercicio, puedes modificar el programa para que encuentre transfusiones en el número óptimo de pasos. Puedes experimentar con estos problemas.

Comentario: Los fervientes partidarios de la programación imperativa notarán que todo lo que hicimos fue iterar sobre todos los estados con retornos (primer pasaje en profundidad), sin usar heurísticas, y tendrán toda la razón. El hecho es que en Prolog es necesario pensar no por la fuerza bruta, sino describiendo el problema y describiendo cómo verificar la solución, y siempre es necesario volver a la imperatividad de los cálculos para la optimización, si es necesario. La dualidad de la naturaleza no es un inconveniente, sino un plus. También vale la pena señalar que los sistemas Prolog grandes están muy bien adaptados para encontrar estados con retornos.

Conclusión

Me gustaría señalar que los problemas discutidos en este artículo son estudios para programación en Prolog. Dado que la mayoría de ellos tienen entre 10 y 15 líneas, el programador de Prolog puede reproducirlos desde la memoria si se revisan con suficiente frecuencia. Y definitivamente vale la pena volver a ellos, ya que te recuerdan el arte de la programación (al igual que la ordenación rápida en C). Más adelante se analizarán tareas más complejas y más aplicadas para el uso diario.

Al final hay 2 rompecabezas por un premio.:

1. Como saben, en lo funcional y lógico, intentan por todos los medios evitar programas con efectos secundarios, envolverlos en mónadas y proponer conceptos especiales. El problema estándar es un problema del mundo externo, por ejemplo, escribir datos en un archivo es imposible revertir la escritura en un archivo o cancelar el envío de varios bytes a través de un socket y, por lo tanto, la marcha atrás no funcionará del todo correctamente. Sólo hay un consejo: no utilice Prolog para estos fines. Pero hay predicados que son muy buenos y específicos de Prolog, pero que tienen un efecto secundario. Ejemplo afirmar (asserta, afirmarz): agrega una regla (hecho) simple a la base de reglas (hecho). Ejemplo afirmar (principal (3)): agrega el hecho de que 3 es un número primo y consulta :-primer(X), ahora generará 3, incluso si el programa original está vacío.

   Tarea: escribir una versión declarativa afirmar, es decir, cuando el programa de retroceso regresa, el hecho no debe permanecer en la memoria, sino que debe funcionar como una suposición lógica.

   ejemplo de trabajo: ¡La consulta c(X) debería producir un número 4 para el siguiente programa!
   a(X) :- b(Y), X es Y + 1 . c(X) :- my_assert(b(3)), a(X). c(X) :- b(X).

2. En la lógica matemática clásica, se presta mucha más atención a 2 teorías que a todas las demás: esta teoría de conjuntos Y teoría de predicados. Existe una cierta conexión entre ellos, uno se expresa a través del otro y viceversa. Por ejemplo, un predicado es un conjunto de valores para los cuales es verdadero y viceversa, un conjunto es un predicado de pertenencia. La teoría tradicional de bases de datos relacionales opera sobre conjuntos, mientras que Prolog opera sobre predicados. En general, la tarea es expresar una operación absolutamente tradicional de la teoría de conjuntos: operación de tomar el conjunto de todos los subconjuntos.

   Tarea: dado algún predicado unario a/1 (en el caso general, el conjunto de elementos no es limitado, puede ser infinito), escriba un predicado subconjunto_a/1, que producirá subconjuntos que constan de elementos del conjunto a.

   Ejemplo: la consulta subset_a(X) devuelve X = , X = , X = , X = (el orden no es importante):
   un(1). un(2). subconjunto_a(X):- ....?

Gracias por su atención.

Etiquetas: Agregar etiquetas