SICStus Prolog 4.1 released and My SICStus Prolog page
SICStus Prolog version 4.1 was released yesterday (20091211). 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 following constructs are implemented in SICStus version 4.1:
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 doloops has made me appreciate Prolog in a new way. Very inspiring!
Two missing construct in SICStus (compared to the ECLiPSe implementation) are
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
Here is a simple comparison of the assignment models mentioned above.
The ECLiPSe version (using []indices):
Here is the corresponding code in SICStus:
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
I am especially happy about that the FlatZinc solver now shows statistics, e.g.
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):
Explanation:
One very useful feature is that it is quite good at detecting variables not properly declared in the doloops (and singletons elsewhere); one has to use
Another nice feature is the "balloon help", where the SICStus documentation is presented (click in the yellow area for more information).
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 3040 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).
For the past weeks I have tested the beta version of this release. In these tests I focused mainly on the following:
 the doloops (for loops)
 support for MiniZinc version 1.0
 and somewhat SPIDER (the new IDE)
clpfd
part. These models can be downloaded at My SICStus Prolog page. See below for more about these models.
doloops
SICStus Prolog's support for doloops 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, IterSpec2An 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,NextRest],[NextRest],[_]) 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], [NextRest],[_]), 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 doloops 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 doloops). 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 doloops. 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: 64This 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. Usesolutions(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.
SPIDER
I did just briefly tested SPIDER, the Eclipsebased 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 doloops (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 3040 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).
 3_jugs.pl: 3 jugs problem (as a flow problem)
 a_round_of_golf.pl: A Round of Golf puzzle (Dell Logic Puzzles)
 abbots_puzzle.pl: Abbott's puzzle (Dudeney)
 added_corner.pl: Added corner puzzle
 alldifferent_except_0.pl: Decomposition of global constraint
alldifferent_except_0
 alldifferent_cst.pl: Decomposition of global constraint
alldifferent_cst
 alldifferent_modulo.pl: Decomposition of global constraint
alldifferent_modulo
 all_differ_from_at_least_k_pos.pl: Decomposition of global constraint
all_differ_from_at_least_k_pos
 all_equal.pl: Decomposition of global constraint
all_equal
 all_interval.pl: All interval problem (series), (CSPLib problem 7)
 all_min_dist.pl: Decomposition of global constraint
all_min_dist
 allpartitions.pl: All partitions
 alpha.pl: Standard alphametic problem (a.k.a crypto)
 among.pl: Decomposition of global constraint
among
 among_seq.pl: Decomposition of global constraint
among_seq
 arch_friends.pl: Arch friends (Dell Logic Puzzles)
 assignment.pl: Some assignment problems.
 averbach_1.2.pl: Example 1.2 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
 averbach_1.4.pl: Example 1.4 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
 babysitting.pl: Babysitting puzzle (Dell Logic Problem)
 bin_packing.pl: Bin packing problems
 bin_packing2.pl: (Decomposition of the) global
constraint bin_packing
(not exactly like the traditional bin packing))  breaking_news.pl: Breaking news puzzle (Dell Logic Puzzles)
 build_a_house.pl: Build a house (simple scheduling)
 building_blocks.pl: Building blocks puzzle (for a more genral solution see labeled_dice.pl below)
 bus_schedule.pl: Simple bus scheduling (Taha)
 calculs_d_enfer.pl: Calculs d'enfer, an alphametic puzzle
 changes.pl: Coin changes
 circling_squares.pl: Circling squares (Dudeney)
 circuit.pl: Decomposition of global constraint
circuit
(SICStus has a built incircuit
)  clique.pl: Decomposition of global constraint
clique
 clock_triplet.pl: Clock triplet (Dean Clark, via Martin Gardner)
 coins3.pl: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro (ECLiPSe)
 coins_grid.pl: Coins grid problem (Tony Hurlimann)
 contracting_costs.pl: Contracting costs (Sam Loyd)
 covering_opl.pl: Set covering, selecting workers (from OPL example covering.mod)
 crew.pl: Crew Scheduling (via Gecode)
 crossword2.pl: Crossword solving (simple standard constraint programming example)
 crypta.pl: crypta, alphametic problem (standard Prolog/CLP benchmark)
 crypto.pl: crypto, alphametic problem (standard Prolog/CLP benchmark)
 cumulative_test.pl: Test of the built in
cumulative
constraint  curious_set_of_integers.pl: Curious set of integers (Gardner)
 cur_num.pl: Curious number (Dudeney)
 debruijn.pl: de Bruijn sequences
 devils_word.pl: Devil's word (sum of ASCII character of a word)
 diet1.pl: Simple diet optimization problem
 dinner.pl: Dinner problem
 discrete_tomography.pl: Discrete tomography
 distribute.pl: Decomposition of global constraint
distribute
 donald_gerald.pl: DONALD + GERALD = ROBERT (alphametic problem)
 einav_puzzle.pl: Solving the A programming puzzle from Einav
 eq10.pl: Eq 10, standard benchmark problem
 eq20.pl: Eq 20, standard benchmark problem
 exactly.pl: Decomposition of global constraint
exactly
 exodus.pl: Exodus puzzle (Dell Logic Puzzles)
 fancy.pl: Mr Greenguest puzzle (Fancy dress puzzle)
 fill_a_pix.pl: Fillapix puzzle.
 five_brigands.pl: Five brigands problem (Dudeney)
 four_islands.pl: Four islands problem (Dell Logic Puzzles)
 fractions.pl: Fractions, alphametic problem (standard Prolog benchmark)
 furniture_moving.pl: Simple scheduling problem (using cumulative/2).
 futoshiki.pl: Futoshiki puzzle (yet another Japanese grid puzzle)
 general_store.pl: General store problem (Sam Loyd)
 global_contiguity.pl: Decomposition of global constraint
global contiguity
 hamming_distance.pl: Hamming distance
 heterosquare.pl: Heterosquare problem
 hidato.pl: Hidato puzzle
 huey_dewey_louie.pl: Huey, Dewey, Louie, logical problem from Marriott & Stuckey "Programming in Constraints"
 inverse.pl: Decomposition of global constraint
inverse
 isbn.pl: Some explorations in ISBN13
 jobs_puzzle.pl: Jobs puzzle (a classic automated reasoning problem)
 just_forgotten.pl: Just forgotten puzzle (Enigma 1517)
 kakuro.pl: Kakuro grid puzzle
 K4P2GracefulGraph2.pl: K4P2 Graceful Graph
 kenken2.pl: Kenken grid puzzle
 killer_sudoku.pl: Killer Sudoku
 knapsack_investments.pl: Knapsack problem with investments (Lundgren, Rönnqvist, Värbrand: "Optimeringslära")
 knights_path.pl: Knights_path problem
 labeled_dice.pl: Labeled dice puzzle, more general approach (and contains the building_blocks.ecl as an instance). From Jim Orlin "Colored letters, labeled dice: a logic puzzle"
 langford.pl: Langford's number problem (CSP lib problem 24)
 latin_squares.pl: Latin squares
 least_diff.pl: Alphametic problem, smallest difference of two five digit numbers where are digits must be different.
 lecture_series.pl: Lecture seres (Dell Logic Puzzles)
 lectures.pl: Lectures, schedule problem from Biggs "Discrete Mathematics"
 lichtenstein_coloring.pl: Coloring problem: Lichtenstein's communes and exclaves
 magic_hexagon.pl: Magic hexagon (CSPLib, problem 23)
 magic_sequence.pl: Magic sequence (CSP lib problem)
 mamas_age.pl: Mama's age problem (Dudeney)
 mankell.pl: Generating all (mis) spelling of "Henrik Mankell" and "Kjellerstrand"
 map_coloring.pl: Simple map coloring example
 marathon2.pl: arathon Marathon puzzle (XPress example), CP model)
 minesweeper.pl: Minesweeper (with 14 problems, some from Gecode collections)
 miss_manners.pl: Miss Manners' seating problem (standard benchmark for rule engines). Includes problems of size 16, 64, and 128 guests.
 monks_and_doors.pl: Monks and doors
 mr_smith.pl: Mr Smith problem
 music_men.pl: Music men problem
 nadel.pl: B.A. Nadel's construction problem
 olympic.pl: Olympic puzzle (standard Prolog puzzle)
 pandigital_numbers.pl: Pandigital numbers
 pert.pl: Simple PERT problem (van Hentenryck)
 photo_problem.pl: Photo problem (Mozart/Oz)
 pigeon_hole.pl: Pigeon hole problem
 place_number_puzzle.pl: Place number puzzle
 post_office_problem2.pl: Post office problem (Winston)
 pythagoras.pl: Pythagoras number
 quasigroup_completion.pl: Quasigroup completion
 rabbits.pl: Rabbits problem (Van Hentenryck, OPL book)
 remainders.pl: Remainders problem (Kordemsky)
 remarkable_sequence.pl: Remarkable sequence (Coelho & Cotta "Prolog by Example" via Alma0)
 safe_cracking.pl: Safe cracking (Mozart/Oz)
 send_more_money_any_base.pl: SEND+MORE=MONEY (in any base)
 scheduling_speakers.pl: Scheduling speakers (Rina Dechter)
 send_most_money.pl: Alphametic puzzle SEND + MOST = MONEY, where we maximize MONEY (and finds all solutions)
 sequence.pl: Decomposition of global constraint
sequence
 seseman.pl: Seseman convent puzzle
 set_covering.pl: Set covering (placing firestations, Winston)
 set_covering2.pl: Set covering (placing security telephones on a campus, Taha)
 set_covering3.pl: Set covering (selecting senators for a committee, Murty)
 set_covering4.pl: Set covering and set partition (Lundgren, Rönnqvist, Värbrand: "Optimeringslära")
 set_covering_deployment.pl: Set covering deployment problem (placing armies in the Roman Empire)
 set_covering_skiena.pl: Set covering (Skiena)
 set_partition.pl: Set partition problem
 ski_assignment.pl: Ski assignment problem
 sliding_sum.pl: Decomposition of global constraint
sliding sum
 smuggler_knapsack.pl: Smuggler's knapsack (Marriott & Stuckey)
 stable_marriage.pl: Stable marriage problem (examples from Van Hentenryck's OPL book, and MathWorld)
 steiner.pl: Steiner triplets (using boolean list as set representation)
 strimko2.pl: Strimko puzzle (Latin squares with "streams")
 stuckey_seesaw.pl: Seesaw problem (Marriott & Stuckey "Programming with Constraints")
 subset_sum.pl: Subset sum problem (Murty)
 sudoku.pl: Sudoku puzzle, an "allloop" version (contains all 91 problems from Gecode's Sudoku problem set: 9x9, 16x16, and 25x25 problems)
 survo_puzzle.pl: Survo puzzle
 talisman_square.pl: Talisman square
 timpkin.pl: Mrs Timkin's Age (Dudeney)
 to_num.pl: Converts array <> number
 torn_numbers.pl: Torn Numbers problem (Dudeney)
 tourist_site_competition.pl: Tourist site competition (P. Flener)
 traffic_lights.pl: Traffic lights problem (CSPLib problem 16)
 trains.pl: Trains problem (simple example of
table/2
from SWI Prolog manual)  tsp.pl: Traveling salesperson problem, using loops and circuit (examples from Ulf Nilsson, SICStus' example tsp.pl, and the GLPK model tsp.mod)
 tunapalooza.pl: Tunalalooza puzzle (Dell Logic Puzzles)
 twin_letters.pl: Twin letters (Mozart/Oz)
 volsay1.pl: Volsay production problem (Van Hentenryck, The OPL Book)
 volsay2.pl: Volsay production problem (Van Hentenryck, The OPL Book), slightly different from volsay1.pl
 warehouse.pl: Warehouse location problem (OPL example)
 who_killed_agatha.pl: Who killed agatha? (a.k.a. The Dreadsbury Mansion Murder Mystery, an automated reasoning problem)
 xkcd.pl: Knapsack problem from xkcd
 young_tableaux.pl: Young tableaux and partitions