Main

April 11, 2018

The Picat book: Constraint Solving and Planning with Picat

This blog post should have be written years ago, literal years ago. But for different reasons - among them family reasons - it wasn't. Sorry about that.

The Picat system is - still - one of my favourite Constraint Modeling system, and in fact in 2015 we (Neng-Fa Zhou, Jonathan Fruman and I) wrote a book about Picat: Constraint Solving and Planning with Picat (Springer, 2015, ISBN: softcover 9783319258812 , e-book 9783319258836). Springer page.





During this time, I've also written a few papers about Picat, mostly together with Neng-Fa Zhou. See a full list at my Google Scholar page. Among these papers is my first CP conference paper: Optimizing SAT Encodings for Arithmetic Constraints.

My Picat page now contains over 800 programs / models, including constraint models, planning models, and just fun stuff.

And for my Swedish readers, here's the mandatory Bokus link for the book: https://www.bokus.com/bok/9783319258812/constraint-solving-and-planning-with-picat/.

Posted by hakank at 07:36 PM |

September 29, 2013

A first look at Picat programming language

For easy reference, here are the links to My Picat page and to my GitHub repo /picat.

Picat is a new programming language created by Neng-Fa Zhou and Jonathan Fruhman. The specification was published in December 2012. The first official (beta) release was in May 2013. Right from the beginning I liked this language and in this blog post I hope to show why. I should also say that the code shown here are not just for Constraint Programming, but also traditional backtracking (a la Prolog), tabling (memoization), imperative constructs etc, i.e. what makes Picat Picat.

The name Picat is an acronym and is explained in the quote below, borrowed from the Picat site:
Picat is a general-purpose language that incorporates features from logic programming, functional programming, and scripting languages. The letters in the name summarize Picat's features:
  • Pattern-matching: A predicate defines a relation, and can have zero, one, or multiple answers. A function is a special kind of a predicate that always succeeds with one answer. Picat is a rule-based language. Predicates and functions are defined with pattern-matching rules.
  • Imperative: Picat provides assignment and loop statements for programming everyday things. An assignable variable mimics multiple logic variables, each of which holds a value at a different stage of computation. Assignments are useful for computing aggregates and are used with the foreach loop for implementing list comprehensions.
  • Constraints: Picat supports constraint programming. Given a set of variables, each of which has a domain of possible values, and a set of constraints that limit the acceptable set of assignments of values to variables, the goal is to find an assignment of values to the variables that satisfies all of the constraints. The Picat system provides modules for different solvers with the same interface.
  • Actors: Actors are event-driven calls. Picat provides action rules for describing event-driven behaviors of actors. Events are posted through channels. An actor can be attached to a channel in order to watch and to process its events. In the future, Picat will treat threads as channels, and allow the use of action rules to program concurrent threads.
  • Tabling: Tabling can be used to store the results of certain calculations in memory, allowing the program to do a quick table lookup instead of repeatedly calculating a value. As computer memory grows, tabling is becoming increasingly important for offering dynamic programming solutions for many problems such as planning problems.
Of these general features, I have mostly tested pattern-matching, imperative programming constructs, constraints (of course!) and tabling, but have not played much with actors directly and will not mention them much here.

Some general Picat links: Let's start with some simple examples to show these features.

Constraints

First we show how to use constraints with send_more_money.pi, and we clearly see the influences of Prolog: 
import cp.

sendmore(Digits) =>
   Digits = [S,E,N,D,M,O,R,Y],
   Digits in 0..9,

   all_different(Digits),
   S #> 0,
   M #> 0,
          1000*S + 100*E + 10*N + D
   +      1000*M + 100*O + 10*R + E
   #= 10000*M + 1000*O + 100*N + 10*E + Y,
        
   solve(Digits).
Except for the => it looks very much like Prolog, right? I explain the => and how it's different from Prolog's :- later on and will also mention some other similarities/differences from/with Prolog.

Another mandatory example is sudoku.pi where we see more differences between traditional Prolog, i.e. the foreach loop: 
import cp.
import util.

go =>
   time2(sudoku(1)).

sudoku(ProblemName) =>
	problem(ProblemName, Board),
	print_board(Board),
	sudoku(3, Board),
	print_board(Board).

sudoku(N, Board) =>
   N2 = N*N,

   Vars = array_matrix_to_list(Board),
   Vars in 1..N2,

   foreach(Row in Board) all_different(Row) end,
   foreach(Column in transpose(Board)) all_different(Column) end.
   foreach(I in 1..N..N2, J in 1..N..N2)
      all_different([Board[I+K,J+L] : K in 0..N-1, L in 0..N-1])
   end,

   solve([ff,down], Vars).

print_board(Board) =>
   N = Board.length,
   foreach(I in 1..N)
      foreach(J in 1..N)
         X = Board[I,J],
         if var(X) then printf("  _") else printf("  %w", X) end
      end,
      nl
   end,
   nl.

problem(1, Data) => 
Data = [
    [_, _, 2, _, _, 5, _, 7, 9],
    [1, _, 5, _, _, 3, _, _, _],
    [_, _, _, _, _, _, 6, _, _],
    [_, 1, _, 4, _, _, 9, _, _],
    [_, 9, _, _, _, _, _, 8, _],
    [_, _, 4, _, _, 9, _, 1, _],
    [_, _, 9, _, _, _, _, _, _],
    [_, _, _, 1, _, _, 3, _, 6],
    [6, 8, _, 3, _, _, 4, _, _]].
What I have understood, these loops constructs was one of the reasons that Neng-Fa Zhou wanted to created a new language, since he wasn't satisfied with the foreach loops he implemented in B-Prolog. [You can compare many of my Picat models/programs with the one I implemented in B-Prolog earlier this year. See my B-Prolog page, e.g. sudoku.pl.] One thing that differs between Picat's foreach loops compared to B-Prolog's (as well as ECLiPSe's and SICStus Prolog's) is that the user don't have to explicitly declare the local (or global) variables which makes it simpler to use and read.

I will describe more CP in Picat below, but first I will describe some other Picat features.

Tabling

Tabling here refers to memoization ("caching the results"). A simple example of tabling is to start with this the standard recursive definition of a Fibonacci number: 
table
fibt(0)=1.
fibt(1)=1.
fibt(N)=F,N>1 => F=fibt(N-1)+fibt(N-2).
This is normally very slow for larger numbers because of the massive number of recursive steps needed. Using the table declaration before the predicate will automatically cache the calculated values and is used in subsequent calls.

An example of it's use is in euler2.pi (Project Euler #2), where the object is to find the sum of all even-valued terms in the sequence which do not exceed four million. Here is one way of implementing this, using list comprehension:q 
euler2 => 
   writeln(sum([F : N in 1..100, F = fibt(N), F < 4000000, F mod 2 =:= 0])).
Finding this sum takes 0.015s (with the overload of starting Picat etc). If we don't table the values then it's much (much!) slower: fibt(100) is 573147844013817084101 (~5.73e+20), which is about the number of recursions steps needed. By the way, here we see that Picat supports big integers as well.

Please note that tabling might in some cases be slower because of the memory overhead involved, so you have to be careful and test it.

Another example of tabling is for dynamic programming, for example calculating the edit distance. This example is from Picat's picat-lang.org/download/exs.pi: 
% computing the minimal editing distance
% of two given lists
table(+,+,min)
edit([],[],D) => D=0.
edit([X|Xs],[X|Ys],D) =>   % copy
    edit(Xs,Ys,D).
edit(Xs,[_Y|Ys],D) ?=>      % insert
    edit(Xs,Ys,D1),
    D=D1+1.
edit([_X|Xs],Ys,D) =>       % delete
    edit(Xs,Ys,D1),
    D=D1+1.
Another example is shortest distance (also from exs.pi): 
% mode-directed tabling
% finding shortest paths on a graph given by the relation edge/3.
table(+,+,-,min) 
sp(X,Y,Path,W) ?=>
    Path=[(X,Y)],
    edge(X,Y,W).
sp(X,Y,Path,W) =>
    Path=[(X,Z)|PathR],
    edge(X,Z,W1),
    sp(Z,Y,PathR,W2),
    W=W1+W2.

index(+,-,-) (+,+,-)
edge(1,2,1).
edge(1,3,2).
edge(2,3,3).
edge(3,2,4).

Imperative programming

Regarding loops, we have already seen the foreach loop in the Sudoku example. Picat has more imperative programming constructs: while loops and assignments.

The Fibonacci example shown above (Project Euler #2, using the list comprehension) has the drawback of a hard coded limit that checks all N in the range 1..100; this range was found by some experimentation and it's not the smallest range. In Picat it's also possible to use a while loop for this (though not as nice looking as the list comprehension version). This is traditional imperative programming. It also shows an example of (re)assignments using the := operator: 
euler2b => 
  I = 1,
  Sum = I,
  F = fibt(I),
  while (F < 4000000) 
     if F mod 2 == 0 then
        Sum := Sum + F
     end,
     I := I + 1,
     F := fibt(I)
  end,
  writeln(Sum).
This version also calculates the solution in 0.015s.

More Constraint Programming

Here are some more examples of CP in Picat.

Element constraint

In Picat, as in B-Prolog (and in many other CP systems), the element constraint (List[Ith]=Value) has to be written explicitly using the predicate element(Ith, List, Value) when Ith is a decision variables. However, if Ith is a plain integer, in Picat it can be stated more naturally as List[Ith] = Value or List[Ith] #= Value if List is a list of decision variables.

Older readers of this blog might remember that I sometimes whine how hard it is to write matrix element in different CP systems, and this applies to Picat as well. For example, in circuit.pi I would like to use this construct but it's not allowed: 
foreach(I in 2..N)
  % this is not allowed
  Z[I] = X[Z[I-1]]
end
Instead, one have to rewrite it. Here's my version: 
import cp. 

% ...

foreach(I in 2..N)
   Z1 #= Z[I-1],
   element(Z1,X,X2),
   Z[I] #= X2
end,
In stable_marriage.pi a more general version, matrix_element, is used: 
matrix_element(X, I, J, Val) =>
  element(I, X, Row),
  element(J, Row, Val).
This version (using two element) can be very good sometimes, but depending on the type of the variables some of these variants might be used; sometimes I have to test them all. Also, they are never active at the same time, but deactivated by comments (as shown in the example): 
import cp.

% ...

matrix_element(X, I, J, Val) =>
  element(I, X, Row),
  element(J, Row, Val).

% matrix_element(X, I, J, Val) =>
%   nth(I, X, Row),
%   element(J, Row, Val).

% matrix_element(X, I, J, Val) =>
%   freeze(I, (nth(I, X, Row),freeze(J,nth(J,Row,Val)))).

% matrix_element(X, I, J, Val) =>
%   freeze(I, (element(I, X, Row),freeze(J,element(J,Row,Val)))).
The freeze(X, Call) predicate delays the call to Call until X becomes a non-variable term.

alldifferent_except_0

Picat supports reifications with the nice syntax I expect from a high level CP system. Note that #/\ is "and" for FD variables. Here is the alldifferent_except_0 constraint (see alldifferent_except_0.pi for the full model): 
import cp.

alldifferent_except_0(Xs) =>
   foreach(I in 1..Xs.length, J in 1..I-1)
      (Xs[I] #!= 0 #/\ Xs[J] #!= 0) #=> (Xs[I] #!= Xs[J])
    end.

N-queens

Below are some different implementations of N-queens, taken from nqueens.pi. 
import cp.

queens3(N, Q) =>
   Q=new_list(N),
   Q in 1..N,
   all_different(Q),
   all_different([$Q[I]-I : I in 1..N]),
   all_different([$Q[I]+I : I in 1..N]),
   solve([ff],Q).

% Using all_distinct instead
queens3b(N, Q) =>
    Q=new_list(N),
    Q in 1..N,
    all_distinct(Q),
    all_distinct([$Q[I]-I : I in 1..N]),
    all_distinct([$Q[I]+I : I in 1..N]),
    solve([ff],Q).

queens4(N, Q) =>
   Q = new_list(N),
   Q in 1..N,
   foreach(A in [-1,0,1])
      all_different([$Q[I]+I*A : I in 1..N])
   end,
   solve([ff],Q).
Note that in queens3 we have to use $Q[I]-I (i.e. prepended with a $) since since it's an expression that should be evaluated ("escaped").

Now we can do some benchmark on different variants (the model nqueens.pi also includes some variants not shown here) with different N for some of the variants. This is merely to show a use of the meta predicates (time2, once, and call). 
go3 => 
   Ps = [queens3=1000, queens3b=1000, queens4=100,queens5=100, queens6=13],
   foreach(P=N in Ps) 
      printf("%w(%d)\n", P, N),
      time2(once(call(P,N,Q))),
      writeln(Q),
      nl
   end.
queens3(1000) takes 4s and 2 backtracks, queens3b takes 9.9s and 0 backtracks. Not extremely fast, but quite good.

While we're at it, here is one way of benchmarking the time and number of backtracks for one of the methods (predicate queen3_all in nqueens.pi) for getting all the solutions for N from 2 to 14. statistics/2 is used to get the number of backtracks and run time for each run: 
go2 => 
   foreach(N in 2..14) 
      statistics(backtracks, Backtracks),
      statistics(runtime, [_, _Runtime1]),
      queens3_all(N, Solutions),
      Len=Solutions.length,
      statistics(backtracks, Backtracks2),
      B = Backtracks2 - Backtracks,
      Backtracks := Backtracks2,
      statistics(runtime, [_, Runtime2]),
      writef("N:%3d %10d solutions (%d backtracks, %d millis)\n", N, Len, B, Runtime2)
   end.
The result: 
N:  2          0 solutions (1 backtracks, 0 millis)
N:  3          0 solutions (2 backtracks,k 0 millis)
N:  4          2 solutions (5 backtracks, 0 millis)
N:  5         10 solutions (13 backtracks, 0 millis)
N:  6          4 solutions (39 backtracks, 0 millis)
N:  7         40 solutions (107 backtracks, 0 millis)
N:  8         92 solutions (383 backtracks, 0 millis)
N:  9        352 solutions (1477 backtracks, 4 millis)
N: 10        724 solutions (5715 backtracks, 4 millis)
N: 11       2680 solutions (24475 backtracks, 48 millis)
N: 12      14200 solutions (116081 backtracks, 232 millis)
N: 13      73712 solutions (588949 backtracks, 1340 millis)
N: 14     365596 solutions (3195965 backtracks, 7472 millis)

Magic square

This is a magic squares implementation in Picat, taken from magic_square.pi. One thing to notice is the use of rows(), columns(), diagonal1(), and diagonal2() from the util module. 
import cp.
import utils.

magic2(N,Square) =>
   writef("\n\nN: %d\n", N),
   NN = N*N,
   Sum = N*(NN+1)//2,% magical sum
   writef("Sum = %d\n", Sum),

   Square = new_array(N,N),
   Square in 1..NN,

   all_different(Square),

   foreach(Row in Square.rows()) Sum #= sum(Rows) end,
   foreach(Column in Square.columns()) Sum #= sum(Column) end,

   % diagonal sums
   Sum #= sum(Square.diagonal1()),
   Sum #= sum(Square.diagonal2()),

   % Symmetry breaking
   Square[1,1] #< Square[1,N],
   Square[1,1] #< Square[N,N],
   Square[1,1] #< Square[N,1],
   Square[1,N] #< Square[N,1],

   solve([ffd,updown],Square),

   print_square(Square).

Magic sequence

Another standard CP problem is magic_sequence.pi: 
import cp.

magic_sequence(N, Sequence) =>
   writef("\n%d: ",N),
   Sequence = new_list(N),
   Sequence in 0..N-1,
   foreach(I in 0..N-1) count(I,Sequence,#=,Sequence[I+1]) end,
   N #= sum(Sequence),
   Integers = [ I : I in 0..N-1],
   N = scalar_product(Integers, Sequence),
   solve([ff], Sequence).

scalar_product(A, X) = Product => 
   Product #= sum([S : I in 1..A.length, S #= A[I]*X[I]]).
Note that I tend to use count(Var, Vars, Relation, N) instead of the built-in global_cardinality(List, Pairs) since it's more natural for me.

Least diff problem, optimization

The Least diff problem is a simple optimization problem in Picat: Minimize the difference between ABCDE-FGHIJ where the letters A..J are distinct integers (in the domain 0..9). 
import cp.

least_diff(L,Diff) =>
  L = [A,B,C,D,E,  F,G,H,I,J],
  L in 0..9,

  all_different(L),

  X #= 10000*A + 1000*B + 100*C + 10*D + E,
  Y #= 10000*F + 1000*G + 100*H + 10*I + J,

  Diff #= X - Y,
  Diff #> 0,
  solve([$min(Diff)], L).
The interesting part is the objective $min(Diff) (note the "$") which defines the objective value.

For more advanced models one can use the $report(Goal) to show the progress of the objective. Here is an example from einav_puzzle.pi: 
   solve($[min(TotalSum), report(printf("Found %d\n", TotalSum)), ffd],Vars),
Without report(Goal) the solution is only shown after the solver has finished the search which may take considerable time.

Global constraint table

Picat has a table constraint: the in construct (in is also used to define the domain of a decision variables). Here is a simple example using table constraint: traffic_lights.pi (CSPLib #16) which use the list Allowed to state which combinations are allowed. 
import cp.

traffic_lights_table(V, P) =>
  N  = 4,
  % allowed/1 as a table (translated)
  Allowed = [(1,1,3,3),
                (2,1,4,1),
                (3,3,1,1),
                (4,1,2,1)],
   
   V = new_list(N),
   V in 1..N,
   P = new_list(N), 
   P in 1..N,
   foreach(I in 1..N, J in 1..N)
      JJ = (1+I) mod N,
      if J #= JJ then
         VI = V[I], PI = P[I],
         VJ = V[J], PJ = P[J],
         % Table constraint
         (VI, PI, VJ, PJ) in Allowed
      end
   end,
   Vars = V ++ P,
   solve(Vars).
The use of in - as a table constraint - requires that the values are integers so we have to translate to/from integers in this version. The model (traffic_lights.pi) also contain some other approaches of this problem that don't use the table constraint.

Another example of table constraint is hidato.pi (though it's not very efficient).

Global constraints

Picat supports the most common global constraints as shown in the list below. See Picat Guide, section 11.5 for details.
  • all_different(List)
  • all_distinct(List)
  • assignment(List) (a.k.a. inverse)
  • circuit(List)
  • count(Value,List,Rel,N)
  • cumulative(Starts,Durations,Resources, Limit)
  • diffn(RectangleList)
  • disjunctive_tasks(Tasks)
  • element(I,List, V)
  • global_cardinality(List, Pairs) (I tend to use this not so much since it's not as natural as using count/4)
  • neqs(NegList)
  • serialized(Starts,Durations)
  • subcircuit(List)
  • in used as the global constraint table (not to be confused with tabling=
In the module cp_utils.pi, I have also defined some other useful decompositions of global constraints:
  • matrix_element (some different versions)
  • to_num
  • latin_square
  • increasing
  • decreasing
  • scalar_product (with a relation)
  • alldifferent_except_0
  • nvalue
  • nvalues
  • global_cardinality(Array, GccList)
  • lex2, lex2eq, lex_less, lex_lesseq, lex_greater, lex_greatereq, lex_less2 (alternative hack)
Labeling: Most of the standard variable and value heuristics are supported, though I miss random variants. Some of the examples above show how to label the variables in the solve predicate. Here the ff is first-fail variable labeling, and down means that a variable is labeled from the largest value to the smallest. 
solve([ff,down], Vars)
See the Picat Guide documentation for more description of the options to solve and other solver options.

Pattern matching

Pattern matching is Picat is more influenced by the pattern matching in functional programming than by Prolog's unification. This may confuse some programmers with a Prolog background.

Here is a definition of quick sort which shows some of the pattern matching constructs of Picat, and also shows how to define functions, i.e. predicates with return value. 
qsort([])    = L => L = [].
qsort([H|T]) = L => L = qsort([E : E in T, E =< H]) ++ [H] ++
                        qsort([E : E in T, E > H]).
The two functions drop and take (standard in functional programming) can be defined as: 
drop(Xs,0) = Xs.
drop([],_N) = [].
drop([_X|Xs],N) = drop(Xs,N-1).

take(_Xs,0) = [].
take([],_N) = [].
take([X|Xs],N) = [X] ++ take(Xs,N-1).
Reverse can be defined as: 
reverse(L1,L2) => my_rev(L1,L2,[]).
my_rev([],L2,L3) => L2 = L3.
my_rev([X|Xs],L2,Acc) => my_rev(Xs,L2,[X|Acc]).
As will be mentioned again below, the matching between different variables - or part of variables - is often done in the body and not in the rule part. Here is an example from 99_problems.pi showing that (the problem is "% P09 (**): Pack consecutive duplicates of list elements into sublists.") 
% pack(L1,L2) :- the list L2 is obtained from the list L1 by packing
%    repeated occurrences of elements into separate sublists.
%    (list,list) (+,?)

pack([],Y) => Y = [].
pack([X|Xs],[Z|Zs]) => transfer(X,Xs,Ys,Z), pack(Ys,Zs).
pack(X1,Z1) => X1=[X|Xs],Z1=[Z|Zs],transfer(X,Xs,Ys,Z), pack(Ys,Zs).
There are more comments about pattern matching below.

Nondeterminism and other Prolog influences (and differences)

Some of the examples above show clear influences from Prolog. Here we list some more influences (and differences).

Picat has - as Prolog has - support for nondeterminism using a backtracking mechanisn to test different predicates as will be seen below. This is a really great feature in Picat and is one of the reason I like Picat so much. Or rather: it is the combination of the backtracking possibility together with the imperative features, support for constraint programming etc that I really like in Picat.

member

The nondeterministic member predicate in Picat works as in Prolog, i.e. can be used both as a test for membership and also for generating all the elements: 
Picat> member(2, [1,2,3])
yes
Picat> member(4, [1,2,3])
no
Picat> member(X, [1,2,3])
   X=1;
   X=2;
   X=3;
   no
As in Prolog we can get the next solution with a ; (semicolon) in the Picat shell.

This double nature version of member can be defined in Picat as: 
member(X,[Y|_]) ?=> X=Y.
member(X,[_|L]) => member(X,L)
In this definition we see two features of Picat:
  • pattern matching: the pattern [Y|_] matches any list and "extracts" the first elements Y to be matched against X in the first clause.
  • backtracking: The first rule is defined as a backtrackable rule using ?=> (the prepending "?" is the marker for backtrackable rules) and makes the call nondeterministic. The last rule in a definition should be stated as non-backtrackable, i.e. => (without the ?).
This predicate now works in the same way as the built-in member/2.

Predicate facts

Predicate facts are bodyless definitions akin to Prolog's "data definition" (but be careful to take this too literary).

Predicate facts are prepended by index declararion to make them accessible as data (and this is one difference from Prolog). For example, here is a stripped down version of the transitive closure example transitive_closure.pi (ported from B-Prolog program transitiveRight.pl): 
top ?=> 
    reach(X,Y),
    writeln([X,Y]),
    fail.
top => true.

% Transitive closure right
table
reach(X,Y) ?=> edge(X,Y).
reach(X,Y)  => edge(X,Z),reach(Z,Y).

% the graph
index(-,-)
edge(1,2).
edge(1,3).
edge(2,4).
edge(2,5).
edge(3,6).
% ....
Note the use table to cache the reach predicate. In this simple example it is not needed, but for other applications it might be a great advantage.

append

append in Picat is also nondeterministic as in Prolog. Here is an example where we get the different X and Y that makes up the list [1,2,3,4]. Collecting all the results is done with findall which will be discussed a little more below: 
Picat> Z=findall([X,Y], append(X, Y, [1,2,3,4]))    
Z = [[[],[1,2,3,4]],[[1],[2,3,4]],[[1,2],[3,4]],[[1,2,3],[4]],[[1,2,3,4],[]]]
As with member, we can define it on our own: 
append(Xs,Ys,Zs) ?=> Xs=[], Ys=Zs.
append(Xs,Ys,Zs) => Xs=[X|XsR], append(XsR,Ys,Zs).

findall

As we saw an example above findall in Picat works much as in Prolog. One difference is that findall in Picat is a function, i.e. returns a value and that is why it was assigned to the Z variable above.

Other nondeterministics predicates

Here are the built-in nondeterministic predicates in Picat. They are mostly wrappers to the underlying B-Prolog predicates.
  • between(From, To, X)
  • append(X,Y,Z)
  • append(W,X,Y,Z)
  • member(Term, List)
  • select(X, List, ResList)
  • find(String, Substring, From, To)
  • find_ignore_case(String, Substring, From, To)
  • repeat
  • permutation(List, Perm)
  • nth(I, List, Val)
  • indomain(Var) (CP)
  • indomain_down(Var) (CP)
  • solve(Vars) (CP)
  • solve(Options, Vars) (CP)
  • statistics(Name,Value)
One can also note that - in contrast to Prolog - length is a "plain" predicate and do not creates a list. It just returns the length of the list (array, structure). (For defining av new list one have to use new_list(Length) instead.)

The nondeterministic predicates are great when they are needed, but don't overuse them. The Picat documentation generally recommend to write functions rather than predicates since functions are easier to debug since they return exactly one value.

An advince to Prolog addicts

In general, Prolog addicts should be a little careful when trying to direct write Prolog code in Picat. Sometimes it work very well to write it as in Prolog (with some minor modifications) but sometimes it don't work. The biggest gotcha is probably pattern matching - as mentioned above - which look much like Prolog's unification but is more like the pattern matching used in functional languages such as Haskell.

SAT-solver

Picat also support solving problems using a SAT solver using almost exactly the same code as using the CP solver. The only thing one might need to change is 
import cp.
to 
import sat.
However, the SAT solver don't support all the global constraints from the CP solver, but it might be worth testing sometimes, since it can be very fast compared to a CP approach. [Still, I tend to rely on CP since then I can get all the solutions - or two - which is not possible with the SAT solver used in Picat.]

Also, I haven't use the SAT solver very much. See Neng-Fa's (and others) use at Projects sections, e.g. numberlink_b.pi and mqueens.pi (it is one of the problems from the CP-2013 Model and Solve Competition).

Planning

One of the things I really like in Picat is that it is now easy to implement certain planning problems. I first wrote a small planning module (bplan.pi, inspired by Hector J. Levesque's version "Thinking as Computation", a rather new Prolog AI book). Neng-Fa later build a much richer module planner with a lot of different variants both optimality versions (best_plan*) and non-optimality versions, both bounded and unbounded, and both with and without costs.

The planning module is quite simple to use:
  • Define the action predicates (the legal moves): action(FromState, ToState, Move, Cost)
  • Define the initialization state (the first FromState)
  • Define the goal state(s)/definition: final(State) that check if the goal state has been reached.
  • call the plan* predicate with the appropriate arguments
A simple example is the M12 problem (test_planner_M12.pi) which has
  • two actions: merge (perfect shuffle) and reverse
  • initial state (the problem instance), e.g. [8,11,6,1,10,9,4,3,12,7,2,5]
  • the goal state: [1,2,3,4,5,6,7,8,9,10,11,12]
Here is the code for the planner part. Using the table directive is often a booster in these kind of planning problems, but not always: 
go =>
  Init = [8,11,6,1,10,9,4,3,12,7,2,5],
  time(best_plan_downward(Init, Plan)),
  writeln(Plan),
  writeln(len=Plan.length),
  nl.

final(Goal) => Goal=[1,2,3,4,5,6,7,8,9,10,11,12].

table
% merge move
action([M1,M12,M2,M11,M3,M10,M4,M9,M5,M8,M6,M7], To, M, Cost) ?=>
   Cost=1, M=m,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12],Cost=1.
% reverse move
action([M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1], To,M, Cost) => 
   Cost=1, M=r,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12],Cost=1.
As mentioned above, it's important to declare the first action with ?=> so it is backtrackable, i.e. that if that clause fails it will backtrack and test the next rule.

Picat finds the shortest solution (27 steps) in 1.8s: [m,m,m,r,m,m,m,r,m,m,m,m,r,m,r,m,r,m,m,r,m,m,r,m,m,m,r] where "m" refers to the merge action/move, and "r" to the reverse action/move.

For a maze problem, the action (move) is simply defined as 
action(From,To,Move,Cost) => 
   maze(From,To),
   Move = [From,To],
   Cost = 1.
where maze(From,To) defines which nodes that are connected. And that is about as simple as it could be.



For these kind of "straight" planning problems it's - IMHO - much easier to use this approach in Picat that using Constraint Programming. However, if the problem has a lot of extra constraints then CP might be both easier to write and faster.

My other planning models are here, mostly quite simple standard problems. Neng-Fa has written more advanced programs, shown at the Projects page. One neat example is his solution of the Doubleclock problem from the CP-2013 competition: doubleclock.pi which solves each of the five problem instances in about 0.1s (except for #4 which takes 0.6s).

File handling

Here is an example that use file handling (and some string handling) in Picat. It's the Project Euler problem #96 where the object is to sum the 3-digit number found in the top left corners of fifty Sudoku problems. See euler96.pi for the full encoding. 
import util.
import cp.

% ...

euler96 =>
  Sudokus = read_file("sudoku.txt"),
  Total = 0,
  foreach(S in Sudokus) 
     Solved = sudoku(3, S),
     Total := Total + [Solved[1,J].to_string() :
                        J in 1..3].flatten().parse_term()
  end,
  println(Total),
  nl.

convert(Sudoku) = [[ R.to_integer() : R in Row] : Row in Sudoku].

sudoku(N, Board) = Board2 =>
  % see above

read_file(File) = Sudokus => 
   FD = open(File),
   Sudokus = [],
   Sudoku = [],
   C = 0,
   while (not at_end_of_stream(FD))
      Line = read_line(FD),
      if once(find(Line, "Grid",1,_To)) then
         if C > 0 then Sudokus := Sudokus ++ [Sudoku.convert()] end,
          Sudoku := [],
          C := C + 1
      else
          Sudoku := Sudoku ++ [Line]
      end
   end,
   % the last
   Sudokus := Sudokus ++ [Sudoku.convert()],
   close(FD).
It solves the problem in 0.03s.

This way of handling files is much easier than in standard Prolog, but perhaps not as easy as in more agile programming languages. However, Picat also have some "slurp" variants that reads the complete file into a variable: read_file_bytes, read_file_lines, and read_file_terms.

Structure and Map (hash table)

Picat has a construct for creating a structure - new_struct (a kind of poor mans OOP "object"), though I don't use this much. Here is a small example: 
Picat> S = new_struct(point,3), Name = S.name, Len = S.length
S = point(_3b0,_3b4,_3b8)
Name = point
Len = 3
A data structure that I use much more is the inevitable map (hash table): 
Picat> M = new_map([one=1,two=2]), M.put(three,3), One = M.get(one)
Here is a longer example (from one_dimensional_cellular_automata.pi) which use a map (Seen) to detect fixpoint and cycles in the evolution of the patterns, i.e. if we seen the pattern before. It use new_map() for creating the map, has_key(S) for checking if pattern S already exists in the map, and put(S,1) to add the pattern S to the map. Also note the definition of the rules as predicate facts. 
go =>
     %    _ # # # _ # # _ # _ # _ # _ # _ _ # _ _
     S = [0,1,1,1,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0,0],
     All = ca(S),
     foreach(A in All) println(A.convert()) end,
     writeln(len=All.length),
     nl.

convert(L) = Res =>
    B = "_#",
    Res = [B[L[I]+1] : I in 1..L.length].

ca(S) = All => 
   Len = S.length,
   All := [S],
   Seen = new_map(), % detect fixpoint and cycle
   while (not Seen.has_key(S))
      Seen.put(S,1),
      T = [S[1]] ++ [rule(sublist(S,I-1,I+1)) : I in 2..Len-1] ++ [S[Len]],
      All := All ++ [T],
      S := T
   end.

% the rules
index(+)
rule([0,0,0]) = 0. % 
rule([0,0,1]) = 0. %
rule([0,1,0]) = 0. % Dies without enough neighbours
rule([0,1,1]) = 1. % Needs one neighbour to survive
rule([1,0,0]) = 0. %
rule([1,0,1]) = 1. % Two neighbours giving birth
rule([1,1,0]) = 1. % Needs one neighbour to survive
rule([1,1,1]) = 0. % Starved to death.

Strings

There are some support for strings in Picat, such as
  • ++ (for list/string concatenation)
  • atom_chars(Atom)
  • find(String, Substring,From,To) (nondet)
  • find_ignore_case(String, Substring,From,To)
  • join(Tokens)
  • join(Tokens,Separator)
  • number_chars(Num)
  • parse_term(String)
  • split(String)
  • split(String, Separators)
  • to_atom(String)
  • to_binary_string(Int)
  • to_lowercase(String)
  • to_uppercase(String)
  • to_string(Term)
Unfortunately there is not yet any support for regular expressions (I use regexps quite much in other programming languages for my "daily programming") and I hope that will come soon enough. However, since a string is (just) an array of characters much of the general list handling can be used for manipulating strings.

Other features in Picat

Picat has many other features not much mentioned in this blog post, for example:
  • debugging and trace, akin to Prolog's debug facilities
  • os module for handling files and directories (see above for some file reading)
  • math module for standard math functions. I tend to use only primes(Int), prime(Int) and the random* predicates from this module.
There are also many other useful predicates that is not mentioned here. See the Picat User's Guide for more about these.

Missing in Picat

Since Picat is such a new programming language there are some missing features that will - hopefully - come later, though I don't know the exact time lines.

MIP solver

A forthcoming project is to add a MIP solver to Picat.

C/Java interface

Another planned project is to add C and/or Java interface to Picat. Then it will probably be easier to add features such as regular expressions, http/tcpip access etc.

Some other utilities

Here are some few utilities that I tend to use.

Get N solutions, given a goal Goal

Sometimes one just want to find some specificed number of solutions, for example for debugging purposes. There is not built-in support for this in Picat, so I've written this following simple ersatz predicate. It use the global get_global_map for putting and checking the number of solutions so far; if the number of solutions are not yet reached it fails which give a new solution. 
get_n_solutions(Goal, N) =>
  printf("Get %d solutions:\n", N),
  get_global_map().put(solcount,1), 
  time2(Goal), % run the Goal
  C = get_global_map().get(solcount),
  if C < N then get_global_map().put(solcount,C+1), fail end.

Running Picat, start parameters

When running Picat programs/models, I often want to test with different predicates. Picat just support one start parameter, main, which is called by the picat executable. Let's call the program program1.pi to the discussion more concrete. 
main => go.

go =>
  println("This is a Picat program.").

go2 =>
  println("This is another predicate.").
When running the Picat program like this: 
  $ picat program1.pi
Picat checks if the predicate main is defined and if so calls it, which in this case calls the go predicate.

However, there is no current support of calling the go2 predicate (i.e. predicates not defined in the main predicate) via the command line. Therefore I've done this Linux shell script (picat_run) for that. Note: you should to change the path in PICAT_ME. 
#!/bin/sh
#
# This is just a wrapper for running the 
#    picat run_program.pi picat_program arg1 [arg2]
#
PICAT_ME=/home/hakank/picat/me
RUN_PROGRAM=${PICAT_ME}/run_program.pi
if [ "$#" -eq 1 ]; then
   picat $RUN_PROGRAM $@ go
else
   picat $RUN_PROGRAM $@
fi
If running without a parameter it runs with the go predicate (which is my default predicate name).

The shell program runs the Picat program run_program.pi, simply defined as: 
main([Program|Goals]) =>
   println(program=Program),
   % compile and load the program
   cl(Program), 
   foreach(Goal in Goals) 
     nl,
     % convert the goal string to an atom
     G = parse_term(Goal), 
     println(goal=Goal),
     G.call()
   end.
Using this we can now run the go2 predicate: 
  $ picat_run program1.pi go2
The magic is done with cl(Program) (which compiles and loads the program) and parse_term(Goal) which converts the Goal (the parameter string from the command line) to an atom G which is then called via call.

Right now this can use only handle simple predicates (with constants as arguments), but cannot execute code that involves variables etc. I hope that later version of Picat will have this as a built-in parameter.

Project Euler benchmark

Whenever a new version of Picat is out, I test and benchmark it with my 50 Euler programs. Here is one way of testing this (test_euler.pi) 
go =>
  Skip1 = ["euler67.pi","euler.pi","euler_utils.pi","test_euler.pi",
           "euler51.pi","euler66.pi","euler96.pi"],
  Skip = new_map([(S=1) : S in Skip1]), 
  Timeout = 10000, % 10s timeout
  Programs = [PP : PP in listdir("."), 
              match(PP, "euler"), 
              match(PP, ".pi")].sort(),
  Fails = [],
  foreach(P in Programs) 
     if not Skip.has_key(P) then
       printf("Testing %w\n", P),
       cl(P),
       time_out(time(go), Timeout, Status),
       println(status=Status),
       if status==Timeout then
           Fails := Fails ++ [P]
       end,
       nl
     end
  end,
  println(fails=Fails),
  nl.

match(String, Substring) => once(find(String,Substring,_,_)).
The interesting part is in bold, i.e. the loading and testing the program as well as the timeout check.

To be honest, I often do these tests with another program instead, which also checks that the the correct answers are shown and also reports different other things. Since I don't want to display the solutions to the Project Euler problems this program is not public. Sorry about that.

FlatZinc solver

Neng-Fa started to write a FlatZinc solver (originally a translation of his FlatZinc solver i B-Prolog) some weeks before the MiniZinc Challenge and I helped a bit with testing and added some functionality. Interestingly, Picat was the only logic programming based submission this year. However, it didn't go very well: in fact we came last in all the different categories. Well, it was fun doint this and to be in the challenge. The FlatZinc solver can be downloaded from the Projects page.

My contributions to Picat

Picat was originally created by Neng-Fa Zhou and Jonathan Fruhman. After the release in May this year, I have done some contributions to the code as well as bug reports, suggestions etc, and are now sometimes mentioned as one of the Picat developers/collaborators. Note that I just develop things in Picat, not in the C or B-Prolog level. Some of the modules I've contributed that are in the Picat distribution are:
  • util.pi: One of the utilities modules
  • picat_lib_aux.pi: Utilities used by other modules
  • apl_util.pi: Utilities inspired by the languages APL and K. Most of this is as a proof-of-concept.
  • set_util.pi: Set utilities (ported from Neng-Fa's set utilities in B-Prolog)
Also, many of the Project Euler programs above #20 at the Project page are mine. See also my own collection where I have different variants for the problems below #20.

And see below for a list of the almost 400 public Picat programs/models I've done so far.

Models

Here are all my current public Picat models/programs. They are also available from my Picat page and my GitHub repo. I have categorized them in different groups since I guess that Picat might attract different target groups.

Constraint Programming

Here are models that mainly use Constraint Programming (import cp.).

Project Euler problem

Here are some solutions for the Project Euler problems:
Total time for running all problems #1..#50 is < 14 seconds (on my Linux Ubuntu 12.04, 8 core Intel i7 CPU 930@2.80GHz). Some programs contains several alternative solutions.

test_euler.pi: Simple Picat program for testing all the Project Euler programs (#1..#50).

Rosetta Code problem

Picat solutions for some Rosetta Code problems.

Miscellaneous problem

Here are some other programs, modules, utilities, e.g. standard Prolog/GOFAI examples etc.

Posted by hakank at 08:10 PM |