« Gecode 3.2.2 released | Main | The Global Constraint Catalog has been updated »

SICStus Prolog 4.1 released and My SICStus Prolog page

SICStus Prolog version 4.1 was released yesterday (2009-12-11). Congratulations to the SICStus team! See here for a summary of the news in this version.

For the past weeks I have tested the beta version of this release. In these tests I focused mainly on the following:
  • the do-loops (for loops)
  • support for MiniZinc version 1.0
  • and somewhat SPIDER (the new IDE)
I did report some findings in the beta version, but most of the time I have been creating SICStus models and just learning the system, especially the clpfd part. These models can be downloaded at My SICStus Prolog page. See below for more about these models.

do-loops

SICStus Prolog's support for do-loops is based on Joachim Schimpf's paper Logical Loops (link to CiteSeer). These constructs where first implemented in the ECLiPSe Constraint Programming System (which I wrote about in Constraint programming in ECLiPSe Constraint Programming System).

The following constructs are implemented in SICStus version 4.1: 
fromto(First,In,Out,Last)
foreach(X,List)
foreacharg(X,Struct)
foreacharg(X,Struct,Idx)
for(I,MinExpr,MaxExpr)
count(I,Min,Max)
param(Var)
IterSpec1, IterSpec2
An example: quasigroup_completion.pl is a simple model that demonstrates the foreach loop, the constraints makes it a latin square given the hints in the Problem matrix: 
solve(ProblemNum) :-
        problem(ProblemNum, Problem),
        format('\nProblem ~d\n',[ProblemNum]),
        length(Problem, N),
        append(Problem, Vars),
        domain(Vars, 1, N),

        ( foreach(Row, Problem)
        do
          all_different(Row,[consistency(domain)])
        ),

        transpose(Problem, ProblemTransposed),
        ( foreach(Column, ProblemTransposed)
        do
          all_different(Column,[consistency(domain)])
        ),

        labeling([], Vars),
        pretty_print(Problem),nl,
        fd_statistics.

problem(1, [[1, _, _, _, 4],  
            [_, 5, _, _, _],
            [4, _, _, 2, _],
            [_, 4, _, _, _],
            [_, _, 5, _, 1]]).
Some other examples are from the Bin Loading model bin_packing.pl. First is an example of a constraint that requires a (reversed) ordered array. 
% load the bins in order:
% first bin must be loaded, and the list must be ordered
element(1, BinLoads, BinLoads1),
BinLoads1 #> 0,
( fromto(BinLoads,[This,Next|Rest],[Next|Rest],[_])
do
  This #>= Next
),
Next is how to sum occurrences of the loaded bins, using fromto to count the number of loaded bins (Loaded is a reified binary variable): 
% calculate number of loaded bins 
% (which we later will minimize)
( foreach(Load2,BinLoads),
  fromto(0,In,Out,NumLoadedBins),
  param(BinCapacity)
do
  Loaded in 0..1,
  Load2 #> 0 #<=> Loaded #= 1,
  indomain(Loaded),
  Out #= In + Loaded
),
A slighly more general version of ordering an array is the predicate my_ordered from young_tableaux.pl: 
my_ordered(P,List) :-
        ( fromto(List, [This,Next | Rest], [Next|Rest],[_]),
          param(P)
        do
          call(P,This,Next)
        ).
where a comparison operator is used in the call, e.g. my_ordered(#>=,P) to sort in reversed order.

Most of my models use these do loop constructs. As you can see of from the models I'm not a Prolog guy by profession, even though the language has fascinated me for a long time. SICStus' (and also ECLiPSe's) new approach of using for do-loops has made me appreciate Prolog in a new way. Very inspiring!

Two missing construct in SICStus (compared to the ECLiPSe implementation) are for(...) * for(...) and multifor. When writing the ECLiPSe models I used these two quite often, for example in the ECLiPSe model assignment.ecl. Also, SICStus don't support the syntactic sugar of array/matrix access with [] (note, this feature is not related to do-loops). When I first realized that they where missing in SICStus, I thought that it would be a hard job of converting my ECLiPSe models to SICStus. Instead, these omissions was - to my surprise - quite a revelation.

My ECLiPSe models was mostly just a translation of the MiniZinc/Comet models I've written before, i.e. array/matrix based models where array access and loops such as forall(i in 1..n) () is used all the time. Not surprising, my first SICStus models was then just a conversion of these array/matrix access to nth1 or element constraints to simulate the ECLiPSe constructs. But it was not at all satisfactory; in fact, it was quite ugly sometimes, and also quite hard to understand. Instead I started to think about the problem again and found better ways of stating the problem, thus used much less of these constructs. Compare the above mentioned model with the SICStus version assignment.pl which in my view is more elegant than my ECLiPSe version.

Here is a simple comparison of the assignment models mentioned above.

The ECLiPSe version (using []-indices): 
% exacly one assignment per row, all rows must be assigned
( for(I,1,Rows), param(X,Cols) do
      sum(X[I,1..Cols]) #= 1
),
% zero or one assignments per column
( for(J,1,Cols), param(X,Rows) do
      sum(X[1..Rows,J]) #=< 1
),
% calculate TotalCost
(for(I,1,Rows) * for(J,1,Cols), 
 fromto(0,In,Out,TotalCost),
 param(X,Cost) do 
     Out #= In + X[I,J]*Cost[I,J]
),
As we see, this is heavily influenced by the MiniZinc/Comet way of coding.

Here is the corresponding code in SICStus: 
% exacly one assignment per row, all rows must be assigned
( foreach(Row, X) do
      sum(Row,#=,1)
),
% zero or one assignments per column
transpose(X, Columns),
( foreach(Column, Columns) do
      sum(Column,#=<,1)
),
% calculate TotalCost
append(Cost, CostFlattened),
scalar_product(CostFlattened,Vars,#=,TotalCost),
(Almost the same code could be written in ECLiPSe as well; this is more about showing how my approach of coding has changed.)

However, I have not been able to completely free myself from the matrix approach; sometimes it was simply too hard, and sometimes I was just lazy.

A final note: The example directory of library(clpfd) now contains many examples of do-loops. Some of the older examples has also been rewritten using these constructs.

Support for MiniZinc/FlatZinc verion 1.0

One other quite large part of the testing was of the support of MiniZinc/FlatZinc version 1.0 (the earlier SICStus version supported just version 0.9). The solver is often very fast, but I did not do any systematic comparison with other solvers using the beta version.

I am especially happy about that the FlatZinc solver now shows statistics, e.g. 
% runtime:      80 ms
% solvetime:    10 ms
% solutions:    1
% constraints:  22
% backtracks:   1
% prunings:     64
This makes it easier to compare it to other solvers.

There are a number of ways of running a MiniZinc model or FlatZinc file (see the documentation). Here is how I normally run the MiniZinc models from the command line (via my Perl wrapper program):

mzn2fzn -G sicstus minesweeper_3.mzn && sicstus --goal "use_module(library(zinc)), on_exception(E,zinc:fzn_run_file('minesweeper_3.fzn',[solutions(1),statistics(true),timeout(30000)]), write(user_error,E)), halt."

Explanation:
  • statistics(true): show the statistics
  • solutions(1): just show one solution. Use solutions(all) for all solutions
  • timeout(30000): time out in milliseconds (here 30 seconds)
  • the on_exception wrapper, so errors don't give the prompt. Note: There may be some strange results if the timeout from library(timeout) is used at the same time.
Note: "set vars" and "float vars" are not supported in this version.

SPIDER

I did just briefly tested SPIDER, the Eclipse-based development environment for SICStus, and I honestly don't know how much I will use it instead of good old Emacs. However, where I a professional SICStus Prolog programmer, I would surely use it all the time since it has a lot of very good features especially crafted for SICStus.

One very useful feature is that it is quite good at detecting variables not properly declared in the do-loops (and singletons elsewhere); one has to use param for using a variable in inner loops. SPIDER is very good at detecting errors when such param values are missing (as well as other errors). For many models I have just started SPIDER to check if there where such bugs.

Another nice feature is the "balloon help", where the SICStus documentation is presented (click in the yellow area for more information).

My SICStus Prolog models

As always when starting learning a new constraint programming system, I started with my learning models, this time mostly by translating the ECLiPSe models. It first took quite a long time, since I missed some constructs I was used to in ECLiPSe (see above). But after a time it was rather easy to do it more like a SICStus approach, and now I really like writing in SICStus. Still, there are some models where this direct translations shows (and I'm not very proud of these models).

Also, I would like to thank Mats Carlsson and Magnus Ågren of the SICStus team for some great help with some of the first models.

So, I have now done almost all my ECLiPSe models in SICStus, except for those using floats or some where the SICStus' distributed examples are much better. SICStus don't support "set vars", so I used boolean lists instead, see for example steiner.pl and clique.pl. Also, there are some 30-40 models not done in written ECLiPSe, and hopefully more is to come. All these models can be seen at My SICStus Prolog page.

These models contains comments of the problem, e.g. references and also links to other of my models implementing the problem (in other constraint programming systems).

Posted by hakank on December 12, 2009 07:48 PM |