B-Prolog - Loops With Foreach and List Comprehension

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, 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 @=, I in 1..2]

binds X to the list . 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 #\= Qs, abs(Qs-Qs) #\= J-I)), labeling(,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,, (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,), Vars @= : I in 1..N, J in 1..N], Vars :: 0..1, foreach(I in 1..N, % one queen in each row sum( : J in 1..N]) #= 1), foreach(J in 1..N, % one queen in each column sum( : I in 1..N]) #= 1), foreach(K in 1-N..N-1, % at most one queen in each left-down diag sum( : 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( : I in 1..N, J in 1..N, I+J=:=K]) #=< 1), labeling(Vars), foreach(I in 1..N,, (Row @= : J in 1..N], writeln(Row))).