B-Prolog fue una implementación de alto rendimiento del lenguaje Prolog estándar con varias características extendidas, incluyendo cláusulas de coincidencia, reglas de acción para el manejo de eventos, resolución de restricciones de dominio finito, matrices y tablas hash, bucles declarativos y tabulado. 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 en 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 se puede utilizar 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 en la que la determinación y las unificaciones de entrada/salida se denotan explícitamente. El compilador traduce las cláusulas de coincidencia en á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 porque no se necesita ningún análisis de programa complejo ni especialización; y 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 toma la siguiente forma:
H , G => Bdonde 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 a Gpuede vincular variables a Hy todas las llamadas a Gdeben ser pruebas en línea. En otras palabras, la guarda debe ser plana. A continuación se muestra un predicado de ejemplo 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 ).El contras [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 función para programar subobjetivos "activos" que puedan reaccionar ante el entorno se ha considerado una de las debilidades de la programación lógica. Para superar esto, B-Prolog proporciona un lenguaje simple pero potente, llamado Reglas de Acción (AR), para programar agentes. Un agente es un subobjetivo que puede retrasarse y luego activarse mediante eventos. Cada vez que se activa un agente, se puede ejecutar alguna acción. Los agentes son una noción más general que las construcciones de retraso en los primeros sistemas Prolog y procesos en lenguajes de programación lógica concurrente en el sentido de que los agentes pueden responder a varios 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 } => Bdonde Hes un patrón para los agentes, Ges una secuencia de condiciones para los agentes, Ees un conjunto de patrones para eventos que pueden activar los agentes y Bes una secuencia de acciones que realizan los agentes cuando se activan. Cuando Efalta el patrón de evento junto 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 la programación de propagadores de restricciones e interfaces gráficas de usuario interactivas. Por ejemplo, ins(X)es un evento que se publica cuando Xse crea una instancia de la variable. Un programa de usuario puede crear y publicar sus propios eventos y definir agentes para manejarlos. Un evento definido por el usuario toma la forma de 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 integrado post(E)publica el evento E.
Consideremos los siguientes ejemplos:
eco ( X ),{ evento ( X , Mes )} => writeln ( Mes ). ping ( T ),{ tiempo ( T )} => writeln ( ping ).El agente echo(X)repite cualquier mensaje que recibe. Por ejemplo,
?- echo ( X ), post ( evento ( X , hola )), post ( evento ( X , mundo )).genera 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 , falla .Crea un temporizador que publica un evento de tiempo cada segundo y crea un agente ping(T)para responder a los eventos. El bucle después del agente es necesario para que el agente sea perpetuo.
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 fue fuertemente influenciado por el sistema CHIP . El primer solucionador completamente desarrollado fue lanzado con la versión 2.1 de B-Prolog en marzo de 1997. Ese solucionador fue implementado 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 soportar 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 (booleanos, á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 empleo 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, incluidos 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, lo siguiente define un propagador para mantener la consistencia del arco para la restricción X+Y #= C. Siempre que se excluye un elemento interno Eydel 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 del arco. Además de estos dos propagadores, también necesitamos generar propagadores para mantener la consistencia del intervalo ya que no dom(Y,Ey)se publica ningún evento si el valor excluido resulta ser un límite. La restricción necesita ser preprocesada para que sea consistente con el 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 se puede utilizar como una matriz unidimensional y una matriz multidimensional se puede representar como una estructura de estructuras. Para facilitar la creación de matrices, B-Prolog proporciona una función integrada, denominada new_array(X,Dims), donde Xdebe ser una variable no instanciada y Dimsuna lista de números enteros positivos que especifica las dimensiones de la matriz. Por ejemplo, la llamada new_array(X,[10,20])se vincula Xa una matriz bidimensional cuya primera dimensión tiene 10 elementos y la segunda dimensión tiene 20 elementos. Todos los elementos de la matriz se inicializan para que sean variables libres.
El predicado incorporado arg/3se puede utilizar para acceder a los elementos de una matriz, 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 los elementos de la matriz, B-Prolog admite la notación de subíndice de matriz X[I1,...,In], donde Xes una estructura y each 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 adaptarse a esta notación, el analizador se modifica para insertar un token ^entre una variable token 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 una matriz cuando se produce 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 utilizar para acceder a los elementos de las listas. Por ejemplo, el nth/3predicado se puede definir de la siguiente manera:
n-ésimo ( I , L , E ) :- E @= L [ I ].Prolog se basa en la recursión para describir bucles. La falta de construcciones de bucles potentes ha hecho que Prolog sea menos aceptable para principiantes y menos productivo para programadores experimentados porque suele ser tedioso definir pequeños predicados recursivos auxiliares para bucles. La aparición de construcciones de programación de restricciones como CLP(FD) ha revelado 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.
El foreachcódigo incorporado tiene una sintaxis y una semántica muy simples. Por ejemplo,
foreach ( A en [ a , b ], I en 1..2 , escribe (( 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 para 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 de manera procedimental y, por lo tanto, no se adaptan bien a Prolog. Por esta razón, adoptamos la notación de comprensión de lista 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 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 foreachlistas por comprensión se traducen en predicados recursivos de cola. Por lo tanto, el uso de estas construcciones no implica ninguna penalización, o ésta es mínima, en comparación con el uso de la recursión.
Las construcciones de bucle mejoran considerablemente el poder de modelado de CLP(FD). A continuación se presenta un programa para el problema de N-reinas en B-Prolog:
reinas ( N ):- longitud ( Qs , N ), Qs :: 1. . N , foreach ( I en 1. . N - 1 , J en I + 1. . N , ( Qs [ I ] #\= Qs [ J ], abs ( Qs [ I ] - Qs [ J ]) #\= J - I )), etiquetado ([ ff ], Qs ), writeln ( Qs ).La notación de matriz en las listas ayuda a abreviar 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 N reinas, que utiliza una variable booleana para cada cuadrado 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 , foreach ( I en 1. . N , % una reina en cada fila suma ([ Qs [ I , J ] : J en 1. . N ]) #= 1 ), foreach ( J en 1. . N , % una reina en cada columna suma ([ Qs [ I , J ] : I en 1. . N ]) #= 1 ), foreach ( K en 1 - N .. N - 1 , % como máximo una reina en cada diagrama de izquierda a abajo suma ([ Qs [ I , J ] : I en 1. . N , J en 1. . N , I - J =:= K ]) #=< 1 ), foreach ( K en 2..2 * N , % como máximo una reina en cada diagrama de izquierda a arriba suma ([ Qs [ I , J ] : I en 1. . N , J en 1. . N , I + J =:= K ]) #=< 1 ), etiquetado ( Vars ), foreach ( I en 1. . N ,[ Fila ], ( Fila @= [ Qs [I , J ] : J en 1. . N ], writeln ( Fila ))).Se ha descubierto que el uso de tablas es cada vez más importante no solo para ayudar a los principiantes a escribir programas declarativos viables, sino también para desarrollar aplicaciones del mundo real, como el procesamiento del lenguaje natural, la verificación de modelos y las aplicaciones de aprendizaje automático. B-Prolog implementa un mecanismo de tablas, llamado 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 del uso de tablas, ha sido la principal fuerza impulsora del diseño y la implementación del sistema de tablas de B-Prolog.
La idea de la tabulación es memorizar las respuestas a las llamadas tabuladas y usar las respuestas para resolver llamadas variantes posteriores. En B-Prolog, al igual que en XSB, los predicados tabulados se declaran explícitamente mediante declaraciones en el siguiente formato:
:- tabla P1 / N1 ,..., Pk / Nk .Por ejemplo, el siguiente predicado tabulado define el cierre transitivo de una relación como lo da edge/2.
:- ruta de la tabla / 2. ruta ( X , Y ):- borde ( X , Y ). ruta ( X , Y ):- ruta ( X , Z ), borde ( Z , Y ).Con la tablación, se garantiza que cualquier consulta al programa finalizará siempre que los tamaños de los términos estén limitados.
De manera predeterminada, todos los argumentos de una llamada en tabla se utilizan en la verificación de variantes y todas las respuestas se incluyen en la tabla para un predicado en tabla. B-Prolog admite modos de tabla, que permiten que el sistema utilice solo argumentos de entrada en la verificación de variantes y en la tabla de respuestas de manera 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 la cantidad de respuestas que se tabularán, y cada uno Mies un modo que puede ser min, max, +(entrada) o -(salida). Se supone que un argumento con el modo mino maxes la salida. Si el límite de cardinalidad Ces 1, se puede omitir con el ' :' precedente.
Los modos de tabla 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 una ruta con el peso mínimo entre un par de nodos.
:- tabla sp ( + , + , - , min ). sp ( X , Y ,[( X , Y )], W ) :- arista ( X , Y , W ). sp ( X , Y ,[( X , Z )| Ruta ], W ) :- arista ( X , Z , W1 ), sp ( Z , Y , Ruta , W2 ), W es W1 + W2 .El modo de tabla establece que solo se muestra una ruta con el peso mínimo para cada par de nodos.