B-Prolog
B-Prolog is a high-performance implementation of the standard Prolog language with several extended features including matching clauses, action rules for event handling, finite-domain constraint solving, arrays and hash tables, declarative loops, and tabling. First released in 1994, B-Prolog is now a widely used CLP system. The constraint solver of B-Prolog was ranked top in two categories in the Second International Solvers Competition,[1] and it also took the second place in P class in the second ASP solver competition [2] and the second place overall in the third ASP solver competition.[3] B-Prolog underpins the PRISM system, a logic-based probabilistic reasoning and learning system. B-Prolog is a commercial product, but it can be used for learning and non-profit research purposes free of charge (since version 7.8 for individual users, including commercial individual users, B-Prolog is free of charge [4]).
Matching clauses
A matching clause is a form of a clause where the determinacy and input/output unifications are denoted explicitly. The compiler translates matching clauses into matching trees and generates indexes for all input arguments. The compilation of matching clauses is much simpler than that of normal Prolog clauses because no complex program analysis or specialization is necessary; and the generated code tends to be more compact and faster. The B-Prolog compiler and most of the library predicates are written in matching clauses.
A matching clause takes the following form:
H, G => B
where H is an atomic formula, G and B are two sequences of atomic formulas. H is called the head, G the guard, and B the body of the clause. No call in G can bind variables in H and all calls in G must be in-line tests. In other words, the guard must be flat. The following gives an example predicate in matching clauses that merges two sorted lists:
merge([],Ys,Zs) => Zs=Ys.
merge(Xs,[],Zs) => Zs=Xs.
merge([X|Xs],[Y|Ys],Zs),X<Y => Zs=[X|ZsT],merge(Xs,[Y|Ys],ZsT).
merge(Xs,[Y|Ys],Zs) => Zs=[Y|ZsT],merge(Xs,Ys,ZsT).
The cons [Y|Ys] occurs in both the head and the body of the third clause. To avoid reconstructing the term, we can rewrite the clause into the following:
merge([X|Xs],Ys,Zs),Ys=[Y|_],X<Y => Zs=[X|ZsT],merge(Xs,Ys,ZsT).
The call Ys=[Y|_] in the guard matches Ys against the pattern [Y|_].
Action rules
The lack of a facility for programming "active" sub-goals that can be reactive to the environment has been considered one of the weaknesses of logic programming. To overcome this, B-Prolog provides a simple and yet powerful language, called Action Rules (AR), for programming agents. An agent is a subgoal that can be delayed and can later be activated by events. Each time an agent is activated, some action may be executed. Agents are a more general notion than delay constructs in early Prolog systems and processes in concurrent logic programming languages in the sense that agents can be responsive to various kinds of events including instantiation, domain, time, and user-defined events.
An action rule takes the following
H, G, {E} => B
where H is a pattern for agents, G is a sequence of conditions on the agents, E is a set of patterns for events that can activate the agents, and B is a sequence of actions performed by the agents when they are activated. When the event pattern E together with the enclosing braces is missing, an action rule degenerates into a matching clause.
A set of built-in events is provided for programming constraint propagators and interactive graphical user interfaces. For example, ins(X) is an event that is posted when the variable X is instantiated. A user program can create and post its own events and define agents to handle them. A user-defined event takes the form of event(X,O) where X is a variable, called a suspension variable, that connects the event with its handling agents, and O is a Prolog term that contains the information to be transmitted to the agents. The built-in post(E) posts the event E.
Consider the following examples:
echo(X),{event(X,Mes)}=>writeln(Mes).
ping(T),{time(T)} => writeln(ping).
The agent echo(X) echoes whatever message it receives. For example,
?-echo(X),post(event(X,hello)),post(event(X,world)).
outputs the message hello followed by world. The agent ping(T) responds to time events from the timer T. Each time it receives a time event, it prints the message ping. For example,
?-timer(T,1000),ping(T),repeat,fail.
creates a timer that posts a time event every second and creates an agent ping(T) to respond to the events. The loop after the agent is needed to make the agent perpetual.
AR has been found useful for programming simple concurrency, implementing constraint propagators, and developing interactive graphical user interfaces. It has served as an intermediate language for compiling Constraint Handling Rules (CHR) and Answer Set Programs (ASP).
CLP(FD)
Like many Prolog-based finite-domain constraint solvers, B-Prolog's finite-domain solver was heavily influenced by the CHIP system. The first fully-fledged solver was released with B-Prolog version 2.1 in March 1997. That solver was implemented in an early version of AR, called delay clauses. During the past decade, the implementation language AR has been extended to support a rich class of domain events (ins(X),bound(X),dom(X,E), and dom_any(X,E)) for programming constraint propagators and the system has been enriched with new domains (Boolean, trees, and finite sets), global constraints, and specialized fast constraint propagators. Recently, the two built-ins in/2 and notin/2 have been extended to allow positive and negative table (also called extensional) constraints.
Thanks to the employment of AR as the implementation language, the constraint solving part of B-Prolog is relatively small (3800 lines of Prolog code and 6000 lines of C code, including comments and spaces) but its performance is very competitive. The AR language is open to the user for implementing problem-specific propagators. For example, the following defines a propagator for maintaining arc consistency for the constraint X+Y #= C. Whenever an inner element Ey is excluded from the domain of Y, this propagator is triggered to exclude Ex, the counterpart of Ey, from the domain of X. For the constraint X+Y #= C, we need to generate two propagators, namely, 'X_in_C_Y_ac'(X,Y,C) and 'X_in_C_Y_ac'(Y,X,C), to maintain the arc consistency. In addition to these two propagators, we also need to generate propagators for maintaining interval consistency since no dom(Y,Ey) event is posted if the excluded value happens to be a bound. The constraint needs to be preprocessed to make it arc consistent before the propagators
are generated.
'X_in_C_Y_ac'(X,Y,C),var(X),var(Y),
{dom(Y,Ey)}
=>
Ex is C-Ey,
domain_set_false(X,Ex).
'X_in_C_Y_ac'(X,Y,C) => true.
Arrays and the array subscript notation
In B-Prolog, the maximum arity of a structure is 65535. This entails that a structure can be used as a one-dimensional array, and a multi-dimensional array can be represented as a structure of structures. To facilitate creating arrays, B-Prolog provides a built-in, called new_array(X,Dims), where X must be an uninstantiated variable and Dims a list of positive integers that specifies the dimensions of the array. For example, the call new_array(X,[10,20]) binds X to a two dimensional array whose first dimension has 10 elements and second dimension has 20 elements. All the array elements are initialized to be free variables.
The built-in predicate arg/3 can be used to access array elements, but it requires a temporary variable to store the result, and a chain of calls to access an element of a multi-dimensional array. To facilitate accessing array elements, B-Prolog supports the array subscript notation X[I1,...,In], where X is a structure and each Ii is an integer expression. This common notation for accessing arrays is, however, not part of the standard Prolog syntax. To accommodate this notation, the parser is modified to insert a token ^ between a variable token and [. So, the notation X[I1,...,In] is just a shorthand for X^[I1,...,In]. This notation is interpreted as an array access when it occurs in an arithmetic expression, a constraint, or as an argument of a call to @=/2. In any other context, it is treated as the term itself. The array subscript notation can also be used to access elements of lists. For example, the nth/3 predicate can be defined as follows:
nth(I,L,E) :- E @= L[I].
Loops with foreach and list comprehension
Prolog relies on recursion to describe loops. The lack of powerful loop constructs has arguably made Prolog less acceptable to beginners and less productive to experienced programmers because it is often tedious to define small auxiliary recursive predicates for loops. The emergence of constraint programming constructs such as CLP(FD) has further revealed this weakness of Prolog as a modeling language. B-Prolog provides a built-in, called foreach, for iterating over collections and the list comprehension notation for constructing lists.
The foreach built-in has a very simple syntax and semantics. For example,
foreach(A in [a,b], I in 1..2, write((A,I)))
outputs four tuples (a,1), (a,2), (b,1), and (b,2). Syntactically, foreach is a variable-length call whose last argument specifies a goal to be executed for each combination of values in a sequence of collections. A foreach call may also give a list of variables that are local to each iteration and a list of accumulators that can be used to accumulate values from each iteration. With accumulators, we can use foreach to describe recurrences for computing aggregates. Recurrences have to be read procedurally and thus do not fit well with Prolog. For this reason, we adopt the list comprehension notation from functional languages. A list comprehension is a list whose first element has the functor ':'. A list of this form is interpreted as a list comprehension in calls to @=/2 and arithmetic constraints. For example, the query
X @= [(A,I) : A in [a,b], I in 1..2]
binds X to the list [(a,1),(a,2),(b,1),(b,2)]. A list comprehension is treated as a foreach call with an accumulator in the implementation.
Calls to foreach and list comprehensions are translated into tail-recursive predicates. Therefore, there is no or little penalty of using these constructs compared with using recursion.
The loop constructs considerably enhance the modeling power of CLP(FD). The following gives a program for the N-queens problem in B-Prolog:
queens(N):-
length(Qs,N),
Qs :: 1..N,
foreach(I in 1..N-1, J in I+1..N,
(Qs[I] #\= Qs[J],
abs(Qs[I]-Qs[J]) #\= J-I)),
labeling([ff],Qs),
writeln(Qs).
The array notation on lists helps shorten the description. Without it, the foreach loop in the program would have to be written as follows:
foreach(I in 1..N-1, J in I+1..N,[Qi,Qj],
(nth(Qs,I,Qi),
nth(Qs,J,Qj),
Qi #\= Qj,
abs(Qi-Qj) #\= J-I)),
where Qi and Qj are declared local to each iteration. The following gives a program for the N-queens problem, which uses a Boolean variable for each square on the board.
bool_queens(N):-
new_array(Qs,[N,N]),
Vars @= [Qs[I,J] : I in 1..N, J in 1..N],
Vars :: 0..1,
foreach(I in 1..N, % one queen in each row
sum([Qs[I,J] : J in 1..N]) #= 1),
foreach(J in 1..N, % one queen in each column
sum([Qs[I,J] : I in 1..N]) #= 1),
foreach(K in 1-N..N-1, % at most one queen in each left-down diag
sum([Qs[I,J] : I in 1..N, J in 1..N, I-J=:=K]) #=< 1),
foreach(K in 2..2*N, % at most one queen in each left-up diag
sum([Qs[I,J] : I in 1..N, J in 1..N, I+J=:=K]) #=< 1),
labeling(Vars),
foreach(I in 1..N,[Row],
(Row @= [Qs[I,J] : J in 1..N], writeln(Row))).
Tabling
Tabling has been found increasingly important for not only helping beginners write workable declarative programs but also developing real-world applications such as natural language processing, model checking, and machine learning applications. B-Prolog implements a tabling mechanism, called linear tabling, which is based on iterative computation of looping subgoals rather than suspension of them to compute the fixed points. The PRISM system, which heavily relies on tabling, has been the main driving force for the design and implementation of B-Prolog's tabling system.
The idea of tabling is to memorize the answers to tabled calls and use the answers to resolve subsequent variant calls. In B-Prolog, as in XSB, tabled predicates are declared explicitly by declarations in the following form:
:-table P1/N1,...,Pk/Nk.
For example, the following tabled predicate defines the transitive closure of a relation as given by edge/2.
:-table path/2.
path(X,Y):-edge(X,Y).
path(X,Y):-path(X,Z),edge(Z,Y).
With tabling, any query to the program is guaranteed to terminate as long as the term sizes are bounded.
By default, all the arguments of a tabled call are used in variant checking and all answers are tabled for a tabled predicate. B-Prolog supports table modes, which allow the system to use only input arguments in variant checking and table answers selectively. The table mode declaration
:-table p(M1,...,Mn):C.
instructs the system how to do tabling on p/n, where C, called a cardinality limit, is an integer which limits the number of answers to be tabled, and each Mi is a mode which can be min, max, + (input), or - (output). An argument with the mode min or max is assumed to be output. If the cardinality limit C is 1, it can be omitted with the preceding ':'.
Table modes are very useful for declarative description of dynamic programming problems. For example, the following program encodes the Dijkstra's algorithm for finding a path with the minimum weight between a pair of nodes.
:-table sp(+,+,-,min).
sp(X,Y,[(X,Y)],W) :-
edge(X,Y,W).
sp(X,Y,[(X,Z)|Path],W) :-
edge(X,Z,W1),
sp(Z,Y,Path,W2),
W is W1+W2.
The table mode states that only one path with the minimum weight is tabled for each pair of nodes.
References
- Results of the Second International Competition of CSP and Max-CSP Solvers
- http://www.cs.kuleuven.be/~dtai/events/ASP-competition/index.shtml
- BPSolver’s Solutions to the Third ASP Competition Problems | Association for Logic Programming
- "Archived copy". Archived from the original on 2014-03-09. Retrieved 2013-01-30.CS1 maint: archived copy as title (link)