Main

September 24, 2010

SICStus Prolog version 4.1.3 and SPIDER 0.0.23 released

SICStus Prolog version 4.1.3 and SPIDER 0.0.23 (SICStus Prolog IDE) has been released.
From Changes Introduced in Version 4.1.3:

SICStus Prolog version 4.1.3:

New Features
* library(plunit) provides a Prolog unit-test framework.
* CLPFD:
o automaton/9 takes several new options that allow capturing properties of the input string, such as the number of occurrences of given patterns, into domain variables.
o A much more general syntax is allowed for clauses of the form Head +: Body, which define dedicated propagators as indexicals. In particular, propositional combinations of arithmetic constraints are allowed.

Bugs Fixed
* Critical virtual machine bugs.
* Improvements to interrupt handling (SP_event(), SP_signal() and related functionality).
* When running under the SPIDER IDE, I/O operations could fail with SPIO_E_INTERRUPTED.
* When running under the SPIDER IDE, restore/1 would disrupt the debugging session.
* Linking with the SICStus runtime on Linux no longer marks the stack as executable. This would prevent SICStus from starting on some versions of SE Linux.
* Work around OS bugs on Mac OS X 10.5, Mac OS X 10.6 and Linux that sometimes causes SICStus to hang when closing streams.
* Source_info bug for huge interpreted clauses.
* Profiling: profile_reset/1 was broken; problems with multifile.
* library(timeout): time_out/3 would sometimes interrupt I/O or miss a timeout under Windows.
* library(sockets): Some operations would raise an exception when an interrupt occurred, e.g. at ^C.
* CLPQ/CLPR: constants \pi and e were inaccurate.
* CLPFD:
o relation/3, table/[2,3]: bugs with empty and infinite sets.
o Missing propagation in the context of unification.
*
* SPRM 11909 Prologbeans: passing deeply nested terms to and from Prolog could lead to stack overflow in Prologbeans client code (Java, .NET).

Other Changes
* The following I/O predicates are now several times faster: put_code/[1,2], put_byte/[1,2], get_code/[1,2], peek_code/[1,2], get_byte/[1,2], peek_byte/[1,2], and read_line/[1,2].
* JASPER: When creating a se.sics.sicstus.SICStus instance any (Java) system property named se.sics.sicstus.property.NAME will be passed to the created SICStus instance as the (Prolog) system property NAME.
* CLPFD: scalar_product/[4,5] is less prone to integer overflows, and faster in the most common cases.
* Linux: The installer script would sometimes fail to configure support for Java.

New features in SPIDER:

New Features
* Call Hierarchy shows references to a selected predicate or file.
* New key bindings:
Binding Function Mac OS X Binding
ALT-K Compile Prolog Code ALT-K
CTRL-ALT-Q C Open Prolog Toplevel CMD-ALT-Q C
CTRL-ALT-H Call Hierarchy CTRL-ALT-H
* Comments that contain the strings TODO, FIXME or XXX now generate tasks that are visible in the Tasks view.
* New warnings are generated, including
o Warnings when incorrect arguments can be detected. This is done for a number of builtins, including format/[2,3], predicates that takes a stream argument and predicates that take a predicate indicator list or predicate specification.
o Warn for foreign_resource/2 entries with no corresponding foreign/[2,3] and vice versa.
o Warnings for unused module imports.
* The toplevel view shows the working directory of the SICStus process.
* SICStus is now started automatically, by default, for comands like Compile Prolog Code. This can be turned off in the preferences.

December 22, 2009

Some updated SICStus Prolog models

Mats Carlsson (designer and main implementer of SICStus Prolog) was kind enough to send me alternative versions of some of my SICStus Prolog models, which now are included in the models (marked with his name). His versions are - of course - more elegant and faster than mine. Thanks, Mats.

Assignment problem

Model: assignment.pl using the global constraint global_cardinality.
assignment2(Problem) :-
        cost(Problem, Mode, CostRows),
        format('\nProblem ~d\n~w\n', [Problem,Mode]),
        transpose(CostRows, CostCols),
        length(CostRows, R),
        length(CostCols, C),
        length(Vars, R),
        domain(Vars, 1, C),
        (   for(I,1,C),
            foreach(I-Y,Ys)
        do  Y in 0..1
        ),
        global_cardinality(Vars, Ys, [cost(Cost,CostRows)]),
        (Mode==minimize -> Dir=up ; Dir=down),
        labeling([Dir], [Cost]),
        labeling([], Vars), !,
        format('assignment = ~w, cost = ~d\n', [Vars,Cost]),
        fd_statistics, nl.

Bin Packing

Model: bin_packing.pl. Here is the global constraint cumulative used. Note: The representation of the filled bins is however not the same as in my approach.
bin_packing2(Problem) :-
        problem(Problem, StuffUnordered, BinCapacity),
        portray_clause(problem(Problem, StuffUnordered, BinCapacity)),
        length(StuffUnordered, N),
        N1 is N+1,
        (   foreach(H,StuffUnordered),
            foreach(task(S,1,E,H,1),Tasks),
            foreach(NH-S,Tagged),
            foreach(S,Assignment),
            foreach(_-X,Keysorted),
            foreach(X,Vars),
            param(N1)
        do  S in 1..N1,
            E in 2..N1,
            NH is -H
        ),
        keysort(Tagged, Keysorted),
        maximum(Max, Vars),
        cumulative(Tasks, [limit(BinCapacity)]),
        labeling([minimize(Max),step], Vars),
        portray_clause(assignment(Assignment)),
        fd_statistics,
        nl.

Post Office Problem

Model: post_office_problem2.pl. This is a much better way of solving this problem in Prolog than my translation from MiniZinc.
go2 :-
        Days = 7,
        % requirements number workers per day
        Need = [17, 13, 15, 19, 14, 16, 11],
        % Total cost for the 5 day schedule.
        % Base cost per day is 100.
        % Working saturday is 100 extra
        % Working sunday is 200 extra.
        Cost = [500, 600, 800, 800, 800, 800, 700],
        % Decision variables. X[I]: Number of workers starting at day I
        length(X, Days),
        domain(X, 0, 10),
        append(X, X, [_,_,_|Ys]),
        (   foreach(Nd,Need),
            fromto(Ys, Ys1, Ys2, _)
        do  Ys1 = [Y1|Ys2],
            Ys2 = [Y2,Y3,Y4,Y5|_],
            Y1+Y2+Y3+Y4+Y5 #>= Nd
        ),
        scalar_product(Cost, X, #=, Total),
        labeling([minimize(Total),bisect], X),
        format('assignment = ~w, total cost = ~d\n', [X,Total]),
        fd_statistics.
I also corrected a weird (and wrong) way of calculating the total cost in my version (as well as in the MiniZinc model post_office_problem2.mzn).

December 12, 2009

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).

September 23, 2009

MiniZinc Challenge 2009 Results

The result of MiniZinc Challenge 2009 is presented in MiniZinc Challenge 2009 Results:
There were two entrants this year:

* Gecode
* SICStus

In addition, the challenge organisers entered the following three FlatZinc implementations:

* ECLiPSe
* G12/FD
* G12/LazyFD

As per the challenge rules, these entries are not eligible for prizes, but do modify the scoring results.

Summary of Results

fd_search

sicstus 1651.8
eclipse_ic 322.1
gecode 4008.8
g12_fd 2040.6
g12_lazyfd 1376.6

free_search

sicstus 1841.0
gecode 4535.5
g12_fd 1112.4
g12_lazyfd 2511.1


Congratulations to the Gecode team!

April 04, 2009

MiniZinc/FlatZinc support in SICStus Prolog version 4.0.5

The other day I downloaded a demo of SICStus Prolog version 4.0.5, with the sole intention of testing the new support for MiniZinc/FlatZinc. The version I downloaded was for Linux 32 bit glibc 2.7 (my machine use glibc 2.6 but it seems to work well anyway).

The support for MiniZinc/FlatZinc in SICStus Prolog is described more in 10.35 Zinc interface - library(zinc). Some restrictions are described in Notes:
  • Domain variables
    Only variables with finite integer domains are supported. This includes boolean variables which are considered finite integer domain variables with the domain 0..1.
  • Optimization problems
    Only variables with finite integer domains can be optimized in minimize and maximize solve items. The int_float_lin/4 expression as described in the FlatZinc specification is thus not supported.
  • Solve annotations
    • The solve annotations currently supported are int_search/4, bool_search/4, and labelling_ff/0.
    • The FlatZinc specification describes several exploration strategies. Currently, the only supported exploration strategy is "complete".
    • When no solve annotation is given, a most constrained heuristic is used on all problem variables (excluding those that have a var_is_introduced annotation, see below). This corresponds to labeling/2 of library(clpfd) with the option ffc.
    • The choice method "indomain_random" as described in the FlatZinc specification uses random_member/2 of library(random). The random generator of SICStus is initialized using the same seed on each start up, meaning that the same sequence will be tried for "indomain_random" on each start up. This behavior can be changed by setting a different random seed using setrand/1 of library(random).
  • Constraint annotations
    Constraint annotations are currently ignored.
  • Variable annotations
    Variable annotations are currently ignored, except var_is_introduced, which means that the corresponding variable is not considered in any default labeling (such as when no search annotation is given or when the labelling_ff search annotation is given).

Testing

For testing the MiniZinc solver I used exactly the same principle as I do for the ECLiPSe solver, so hooking it up into in my system was very easy. All this is done via a Perl script of my own. It consists of generating a Prolog file, here called prolog_file.pl with the content below . model.mzn is the MiniZinc file to run, and number_of_solutions is the number of solutions to generate (an integer, or all for all solutions).

%
% Generated by mzx.pl
%
:- use_module(library(zinc)).

go :-
   mzn_run_file('model.mzn',
                       [solutions(number_of_solutions)]),
   halt.
And then running the following command (from the Perl program):
sicstus -l prolog_file.pl --goal go.

Findings

Most things works very well and with about the same performance as the ECLiPSe solver. I will investigate some more before (perhaps) buying a private license of SICStus Prolog (or upgrading from my old version 3.9.1 if that is possible). However, I did find some problems.
  • global_cardinality/2
    The support for the builtin global_cardinality/2 is broken. The following error occurs:
    ! Existence error
    ! `global_cardinality/2' is not defined
    
    Example: sudoku_gcc.mzn.

    There is an easy fix which works but is slower that using an builtin support: in the file globals.mzn (in the SICStus Prolog distribution), just use the decomposition variant (the commented) instead.
  • cumulative
    For the model furniture_moving.mzn the following error occurs:
    ! Instantiation error in argument 2 of user:cumulative/2
    ! goal:  cumulative([task(_4769,30,_4771,3,1),task(_4777,10,_4779,1,2),task(_4785,15,_4787,3,3),task(_4793,15,_4795,2,4)],[limit(_4801)])
    
    Note: the model cumulative_test_mats_carlsson.mzn works without problem (this is a simple example from one of Mats Carlsson's lecures).
  • integer overflow
    For the Grocery example (grocery.mzn) an integer overflow error is thrown:
    ! Item ending on line 3:
    ! Representation error in argument 1 of user:range_to_fdset/2
    ! CLPFD integer overflow
    ! goal:  range_to_fdset(1..359425431,_4771)
    
    Notes: MiniZinc's solver also overflows, so this is probably not a big thing. The solvers for Gecode/FlatZinc and ECLiPSe ic handles this problems correctly, though.
  • Statistics
    I have not seen any relevant statistics (e.g. number of failures, nodes, propagations etc) for the SICStus MiniZinc solver. The standard SISCtus Prolog predicate statistics/0 is somewhat useful, but is not what is needed when writing MiniZinc models and comparing with other versions and/or solvers.

    What I have in mind is something like the statistics from Gecode (and Gecode/FlatZinc):
    runtime:       50
    solutions:     1
    propagators:   8
    propagations:  3995
    nodes:         249
    failures:      124
    peak depth:    12
    peak memory:   27 KB
    

Final note

I have contacted the developers of SICStus Prolog about these things. They responsed that the bugs are now fixed and will be included in the next version (4.0.6). They also indicated that more detailed statistics may make it in a later version. That is great!

I have now also added the SICStus Prolog solver on my MiniZinc page.