B-Prolog

B-Prolog was 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, and it also took the second place in P class in the second ASP solver competition and the second place overall in the third ASP solver competition. 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 ). B-Prolog is not anymore actively developed, but it forms the basis for the Picat programming language.

B-Prolog was 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, and it also took the second place in P class in the second ASP solver competition and the second place overall in the third ASP solver competition. 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 ). B-Prolog is not anymore actively developed, but it forms the basis for the Picat programming language. 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 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 Zs=[X|ZsT],merge(Xs,Ys,ZsT). The call Ys=[Y|_] in the guard matches Ys against the pattern [Y|_] . 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). 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)} 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]. 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]) #= -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

External links

Official website How to Solve it With B-Prolog The Language Features and Architecture of B-Prolog Performance comparison of Prolog and CLP(FD) systems Logtalk performance

Text derived from https://en.wikipedia.org/w/index.php?oldid=1313136093 under CC BY-SA 4.0; modifications have been made.