Prólogo B

B-Prolog fue una implementación de alto rendimiento del lenguaje Prolog estándar con varias características extendidas que incluían cláusulas de coincidencia, reglas de acción para el manejo de eventos, resolución de restricciones de dominio finito, arreglos y tablas hash, bucles declarativos y tabulación. Lanzado por primera vez en 1994, B-Prolog es ahora un sistema CLP ampliamente utilizado . El solucionador de restricciones de B-Prolog fue clasificado en primer lugar en dos categorías en la Segunda Competencia Internacional de Solucionadores [ ^{1 ]} y también obtuvo el segundo lugar en la clase P en la segunda competencia de solucionadores ASP ^{[ 2 ] y} el segundo lugar general en la tercera competencia de solucionadores ASP ^{[ 3 ]} . B-Prolog sustenta el sistema PRISM , un sistema de aprendizaje y razonamiento probabilístico basado en lógica. B-Prolog es un producto comercial, pero puede usarse para fines de aprendizaje e investigación sin fines de lucro de forma gratuita (desde la versión 7.8 para usuarios individuales, incluidos los usuarios individuales comerciales, B-Prolog es gratuito ^{[ 4 ]} ). B-Prolog ya no se desarrolla activamente, pero constituye la base del lenguaje de programación Picat.

Una cláusula de coincidencia es una forma de cláusula donde la determinación y las unificaciones de entrada/salida se denotan explícitamente. El compilador traduce las cláusulas de coincidencia a árboles de coincidencia y genera índices para todos los argumentos de entrada. La compilación de cláusulas de coincidencia es mucho más sencilla que la de las cláusulas Prolog normales, ya que no requiere un análisis complejo del programa ni una especialización; además, el código generado tiende a ser más compacto y rápido. El compilador B-Prolog y la mayoría de los predicados de la biblioteca están escritos en cláusulas de coincidencia.

Una cláusula coincidente adopta la siguiente forma:

H , G => B

donde Hes una fórmula atómica , Gy Bson dos secuencias de fórmulas atómicas. Hse denomina cabeza, Gguarda y Bcuerpo de la cláusula. Ninguna llamada en Gpuede vincular variables en Hy todas las llamadas en Gdeben ser pruebas en línea. En otras palabras, la guarda debe ser plana. El siguiente ejemplo proporciona un predicado en cláusulas coincidentes que fusiona dos listas ordenadas:

fusionar ([], Ys , Zs ) => Zs = Ys . fusionar ( Xs ,[], Zs ) => Zs = Xs . fusionar ([ X | Xs ],[ Y | Ys ], Zs ), X < Y => Zs = [ X | ZsT ], fusionar ( Xs ,[ Y | Ys ], ZsT ). fusionar ( Xs ,[ Y | Ys ], Zs ) => Zs = [ Y | ZsT ], fusionar ( Xs , Ys , ZsT ).

La cons [Y|Ys]aparece tanto en el núcleo como en el cuerpo de la tercera cláusula. Para evitar reconstruir el término, podemos reescribir la cláusula de la siguiente manera:

fusionar ([ X | Xs ], Ys , Zs ), Ys = [ Y | _ ], X < Y => Zs = [ X | ZsT ], fusionar ( Xs , Ys , ZsT ).

La llamada Ys=[Y|_]en la guardia coincide Yscon el patrón [Y|_].

La falta de una herramienta para programar subobjetivos "activos" que puedan reaccionar al entorno se ha considerado una de las debilidades de la programación lógica. Para superar esto, B-Prolog proporciona un lenguaje sencillo pero potente, llamado Reglas de Acción (RA), para programar agentes. Un agente es un subobjetivo que puede retrasarse y activarse posteriormente mediante eventos. Cada vez que se activa un agente, se puede ejecutar alguna acción. Los agentes son un concepto más general que las construcciones de retardo en los primeros sistemas Prolog y los procesos en los lenguajes de programación lógica concurrente, en el sentido de que los agentes pueden responder a diversos tipos de eventos, incluidos los de instanciación, dominio, tiempo y eventos definidos por el usuario.

Una regla de acción toma lo siguiente

H , G , { E } => B

donde Hes un patrón para los agentes, Ges una secuencia de condiciones sobre los agentes, Ees un conjunto de patrones para los eventos que pueden activar a los agentes, y Bes una secuencia de acciones realizadas por los agentes cuando se activan. Cuando falta el patrón de evento Ejunto con las llaves que lo encierran, una regla de acción degenera en una cláusula coincidente.

Se proporciona un conjunto de eventos integrados para programar propagadores de restricciones e interfaces gráficas de usuario interactivas. Por ejemplo, ins(X)es un evento que se publica cuando Xse instancia la variable. Un programa de usuario puede crear y publicar sus propios eventos y definir agentes para manejarlos. Un evento definido por el usuario tiene la forma event(X,O)donde Xes una variable, llamada variable de suspensión, que conecta el evento con sus agentes de manejo, y Oes un término de Prolog que contiene la información que se transmitirá a los agentes. El evento integrado post(E)publica el evento E.

Consideremos los siguientes ejemplos:

echo ( X ),{ evento ( X , Mes )} => writeln ( Mes ). ping ( T ),{ tiempo ( T )} => writeln ( ping ).

El agente echo(X)repite cualquier mensaje que reciba. Por ejemplo,

?- echo ( X ), post ( evento ( X , hola )), post ( evento ( X , mundo )).

imprime el mensaje helloseguido de world. El agente ping(T)responde a los eventos de tiempo del temporizador T. Cada vez que recibe un evento de tiempo, imprime el mensaje ping. Por ejemplo,

?- temporizador ( T , 1000 ), ping ( T ), repetir , fallar .

Crea un temporizador que registra un evento de tiempo cada segundo y crea un agente ping(T)para responder a dichos eventos. El bucle posterior al agente es necesario para que este funcione de forma continua.

Se ha comprobado que AR es útil para programar concurrencia simple, implementar propagadores de restricciones y desarrollar interfaces gráficas de usuario interactivas. Ha servido como lenguaje intermedio para compilar reglas de manejo de restricciones (CHR) y programas de conjuntos de respuestas (ASP).

Al igual que muchos solucionadores de restricciones de dominio finito basados ​​en Prolog, el solucionador de dominio finito de B-Prolog estuvo fuertemente influenciado por el sistema CHIP . El primer solucionador completo se lanzó con la versión 2.1 de B-Prolog en marzo de 1997. Ese solucionador se implementó en una versión temprana de AR, llamada cláusulas de retardo. Durante la última década, el lenguaje de implementación AR se ha extendido para admitir una rica clase de eventos de dominio ( ins(X), bound(X), dom(X,E), y dom_any(X,E)) para programar propagadores de restricciones y el sistema se ha enriquecido con nuevos dominios (booleano, árboles y conjuntos finitos), restricciones globales y propagadores de restricciones rápidos especializados. Recientemente, los dos integrados in/2y notin/2se han extendido para permitir restricciones de tabla positivas y negativas (también llamadas extensionales).

Gracias al uso de AR como lenguaje de implementación, la parte de resolución de restricciones de B-Prolog es relativamente pequeña (3800 líneas de código Prolog y 6000 líneas de código C, incluyendo comentarios y espacios), pero su rendimiento es muy competitivo. El lenguaje AR está abierto al usuario para implementar propagadores específicos del problema. Por ejemplo, el siguiente define un propagador para mantener la consistencia de arco para la restricción X+Y #= C. Siempre que un elemento interno Eyse excluye del dominio de Y, este propagador se activa para excluir Ex, la contraparte de Ey, del dominio de X. Para la restricción X+Y #= C, necesitamos generar dos propagadores, a saber, 'X_in_C_Y_ac'(X,Y,C)y 'X_in_C_Y_ac'(Y,X,C), para mantener la consistencia de arco. Además de estos dos propagadores, también necesitamos generar propagadores para mantener la consistencia de intervalo, ya que no dom(Y,Ey)se publica ningún evento si el valor excluido resulta ser un límite. La restricción debe ser preprocesada para hacerla consistente de arco antes de que se generen los propagadores.

'X_in_C_Y_ac' ( X , Y , C ), var ( X ), var ( Y ), { dom ( Y , Ey )} => Ex es C - Ey , domain_set_false ( X , Ex ). 'X_in_C_Y_ac' ( X , Y , C ) => verdadero .

En B-Prolog, la aridad máxima de una estructura es 65535. Esto implica que una estructura puede usarse como un arreglo unidimensional, y un arreglo multidimensional puede representarse como una estructura de estructuras. Para facilitar la creación de arreglos, B-Prolog proporciona una función integrada, llamada new_array(X,Dims), donde Xdebe ser una variable sin instanciar y Dimsuna lista de enteros positivos que especifica las dimensiones del arreglo. Por ejemplo, la llamada new_array(X,[10,20])enlaza Xa un arreglo bidimensional cuya primera dimensión tiene 10 elementos y la segunda dimensión tiene 20 elementos. Todos los elementos del arreglo se inicializan como variables libres.

El predicado integrado arg/3se puede usar para acceder a elementos de matrices, pero requiere una variable temporal para almacenar el resultado y una cadena de llamadas para acceder a un elemento de una matriz multidimensional. Para facilitar el acceso a elementos de matrices, B-Prolog admite la notación de subíndice de matriz X[I1,...,In], donde Xes una estructura y cada Iies una expresión entera. Sin embargo, esta notación común para acceder a matrices no forma parte de la sintaxis estándar de Prolog. Para acomodar esta notación, el analizador se modifica para insertar un token ^entre un token de variable y [. Por lo tanto, la notación X[I1,...,In]es solo una abreviatura de X^[I1,...,In]. Esta notación se interpreta como un acceso a matriz cuando aparece en una expresión aritmética, una restricción o como un argumento de una llamada a @=/2. En cualquier otro contexto, se trata como el término en sí. La notación de subíndice de matriz también se puede usar para acceder a elementos de listas. Por ejemplo, el nth/3predicado se puede definir de la siguiente manera:

nth ( I , L , E ) :- E @= L [ I ].

Prolog se basa en la recursión para describir bucles. La falta de construcciones de bucle potentes ha hecho que Prolog sea menos atractivo para principiantes y menos productivo para programadores experimentados, ya que a menudo resulta tedioso definir pequeños predicados recursivos auxiliares para los bucles. La aparición de construcciones de programación con restricciones , como CLP(FD), ha puesto de manifiesto aún más esta debilidad de Prolog como lenguaje de modelado. B-Prolog proporciona una función integrada, llamada foreach, para iterar sobre colecciones y la notación de comprensión de listas para construir listas.

La foreachfunción integrada tiene una sintaxis y semántica muy simples. Por ejemplo,

para cada ( A en [ a , b ], I en 1..2 , escribir (( A , I )))

genera cuatro tuplas (a,1), (a,2), (b,1), y (b,2). Sintácticamente, foreaches una llamada de longitud variable cuyo último argumento especifica un objetivo que se ejecutará para cada combinación de valores en una secuencia de colecciones. Una foreachllamada también puede dar una lista de variables que son locales a cada iteración y una lista de acumuladores que se pueden usar para acumular valores de cada iteración. Con los acumuladores, podemos usar foreachpara describir recurrencias para calcular agregados. Las recurrencias deben leerse procedimentalmente y, por lo tanto, no se adaptan bien a Prolog. Por esta razón, adoptamos la notación de comprensión de listas de los lenguajes funcionales. Una comprensión de lista es una lista cuyo primer elemento tiene el functor ' :'. Una lista de esta forma se interpreta como una comprensión de lista en las llamadas a @=/2y restricciones aritméticas. Por ejemplo, la consulta

X @= [( A , I ) : A en [ a , b ], I en 1..2 ]

se vincula Xa la lista [(a,1),(a,2),(b,1),(b,2)]. Una comprensión de lista se trata como una foreachllamada con un acumulador en la implementación.

Las llamadas a foreachlas comprensiones de listas se traducen en predicados recursivos de cola. Por lo tanto, el uso de estas construcciones conlleva una penalización mínima o nula en comparación con el uso de la recursión.

Las estructuras de bucle mejoran considerablemente la capacidad de modelado de CLP(FD). A continuación se presenta un programa para el problema de las N-reinas en B-Prolog:

reinas ( N ):- longitud ( Qs , N ), Qs :: 1. . N , para cada ( I en 1. . N - 1 , J en I + 1. . N , ( Qs [ I ] #\= Qs [ J ], abs ( Qs [ I ] - Qs [ J ]) #\= J - I )), etiquetando ([ ff ], Qs ), escribir ( Qs ).

La notación de arreglos en las listas ayuda a acortar la descripción. Sin ella, el foreachbucle del programa tendría que escribirse de la siguiente manera:

foreach ( I en 1. . N - 1 , J en I + 1. . N ,[ Qi , Qj ], ( enésimo ( Qs , I , Qi ), enésimo ( Qs , J , Qj ), Qi #\= Qj , abs ( Qi - Qj ) #\= J - I )),

donde Qiy Qjse declaran locales para cada iteración. A continuación se presenta un programa para el problema de las N-reinas, que utiliza una variable booleana para cada casilla del tablero.

bool_queens ( N ):- new_array ( Qs ,[ N , N ]), Vars @= [ Qs [ I , J ] : I en 1. . N , J en 1. . N ], Vars :: 0..1 , para cada ( I en 1. . N , % una reina en cada fila sum ([ Qs [ I , J ] : J en 1. . N ]) #= 1 ), para cada ( J en 1. . N , % una reina en cada columna sum ([ Qs [ I , J ] : I en 1. . N ]) #= 1 ), para cada ( K en 1 - N .. N - 1 , % como máximo una reina en cada diagonal hacia abajo a la izquierda sum ([ Qs [ I , J ] : I en 1. . N , J en 1. . N , I - J =:= K ]) #=< 1 ), para cada ( K en 2..2 * N , % como máximo una reina en cada diagonal hacia arriba a la izquierda sum ([ Qs [ I , J ] : I en 1. . N , J en 1. . N , I + J =:= K ]) #=< 1 ), etiquetando ( Vars ), para cada ( I en 1. . N ,[ Fila ], ( Fila @= [ Qs [I , J ] : J en 1. . N ], escribir ( Fila ))).

Se ha constatado que el uso de tablas es cada vez más importante, no solo para ayudar a los principiantes a escribir programas declarativos funcionales, sino también para desarrollar aplicaciones prácticas como el procesamiento del lenguaje natural, la verificación de modelos y el aprendizaje automático. B-Prolog implementa un mecanismo de tablas, denominado tablas lineales, que se basa en el cálculo iterativo de subobjetivos en bucle, en lugar de suspenderlos para calcular los puntos fijos. El sistema PRISM, que depende en gran medida de las tablas, ha sido la principal fuente de inspiración para el diseño e implementación del sistema de tablas de B-Prolog.

La idea de usar tablas consiste en memorizar las respuestas a las llamadas tabuladas y utilizarlas para resolver las llamadas variantes subsiguientes. En B-Prolog, al igual que en XSB, los predicados tabulados se declaran explícitamente mediante declaraciones de la siguiente forma:

:- tabla P1 / N1 ,..., Pk / Nk .

Por ejemplo, el siguiente predicado tabulado define el cierre transitivo de una relación como se indica en edge/2.

:- ruta de tabla / 2. ruta ( X , Y ):- arista ( X , Y ). ruta ( X , Y ):- ruta ( X , Z ), arista ( Z , Y ).

Con el uso de tablas, se garantiza que cualquier consulta al programa finalizará siempre que se respeten los límites de tamaño de los términos.

Por defecto, todos los argumentos de una llamada tabulada se utilizan en la comprobación de variantes y todas las respuestas se tabulan para un predicado tabulado. B-Prolog admite modos de tabla, que permiten al sistema utilizar solo los argumentos de entrada en la comprobación de variantes y tabular las respuestas de forma selectiva. La declaración del modo de tabla

:- tabla p ( M1 ,..., Mn ) : C .

indica al sistema cómo realizar la tabulación en p/n, donde C, llamado límite de cardinalidad , es un entero que limita el número de respuestas a tabular, y cada Mies un modo que puede ser min, max, +(entrada) o -(salida). Se asume que un argumento con el modo mino maxes una salida. Si el límite de cardinalidad Ces 1, se puede omitir con el ' :' precedente.

Las tablas son muy útiles para la descripción declarativa de problemas de programación dinámica. Por ejemplo, el siguiente programa codifica el algoritmo de Dijkstra para encontrar un camino con el peso mínimo entre un par de nodos.

:- tabla sp ( + , + , - , min ). sp ( X , Y ,[( X , Y )], W ) :- borde ( X , Y , W ). sp ( X , Y ,[( X , Z )| Camino ], W ) :- borde ( X , Z , W1 ), sp ( Z , Y , Camino , W2 ), W es W1 + W2 .

El modo de tabla indica que solo se tabula una ruta con el peso mínimo para cada par de nodos.

• Comparación de implementaciones de Prolog
• Sintaxis y semántica de Prolog

• Sitio web oficial
• Cómo resolverlo con B-Prolog
• Características del lenguaje y arquitectura de B-Prolog
• Comparación del rendimiento de los sistemas Prolog y CLP(FD)
• Rendimiento de Logtalk