Picat functions in constraints

Question

In an introductory exercise, my goal is to generate patterns of 0, 1 values, subject to various constraints. While the code below works fine with the built-in sum/1 function, it fails (invalid_constraint_expression) with the hand crafted sum1/1 version.

import cp.
main => fill_0_1(4).

fill_0_1(CodeLen) =>
    Codes = new_array(CodeLen),
    Codes :: 0 .. 1,

    sum1([Codes[I] : I in 1..CodeLen]) #= 3,
    solve(Codes),
    printf("%w\n", Codes).

sum1(FDVars) = N =>
    N := 0,
    foreach (V in FDVars)
        N := N + V
    end.

What's the correct way to create sum1?

Answer 1

The problem with your definition of sum1/1 is that you are mixing decision variables (defined with ::) with "plain" non-decision variables (using :=). This don't work since you cannot re-assign the value of a decision variable (the variable N in your example).

Also, unfortunately, you cannot use functions when defining constraints. It don't work to return a value of a decision variable (i.e. using #=).

Here's how I would do it. It's a little more complex since it supports when the decision variable are in a list and when they are in an array (as in your example). If it's an array (checked by array(X)) then we have to convert it to a list, since the [H|T] stuff only works on lists, not arrays. The definition itself is a "standard" definition of sum from logic programming using an accumulator.

% If X is an array, convert it to a list and then call sum2/3 
sum2(X,Sum), array(X) =>
  sum2(X.to_list,0,Sum).

% X is a list.
sum2(X,Sum), list(X) =>
  sum2(X,0,Sum).

% sum2/3 with the accumulator
sum2([],Sum1,Sum2) ?=> Sum1 #= Sum2.
sum2([H|T],Sum0,Sum) ?=> 
  Sum1 #= Sum0 + H,
  sum2(T,Sum1,Sum).

A further comment: Note that the guard conditions in the head (array(X) and list(X)) only works with the Picat style of defining the predicates (?=> and =>) and not the Horn clause style (:-, introduced in v3.0), which means that one cannot rely on matching in the head of the predicates. Thus this don't work when using Picat style:

   sum2([],Sum,Sum) ?=> true. % Matching in head don't work using Picat style.

The two Sum variables must instead be distinct in the head, and are then made equal in the body (using #=), i.e.

   sum2([],Sum1,Sum2) ?=> Sum1 #= Sum2.

Here's a variant - still recursive - that works for both lists and arrays without converting to lists. The main difference it that it use an index (Ix) to access the value in the array/list X. It has two accumulators: one for the index (Ix) which is decremented for each step, and one for the intermediate sum (Sum0).

sum4(X,Sum) ?=> 
  sum4(X,X.len,0,Sum).

sum4(X,1,Sum0,Sum) ?=> Sum #= Sum0 + X[1].
sum4(X,Ix,Sum0,Sum) ?=>
   Ix > 1,
   Sum1 #= X[Ix] + Sum0,
   sum4(X,Ix-1,Sum1,Sum).

Update: Here's a little more general version of this, and it has the similar form as sum2/2-3 above: fold2(X,Predicate,Init,Result). The input parameters is the list/array X, a predicate Pred (of arity 3, see below for examples), and an initial value Init; the output parameter is the result Result. Here' we can

fold2([],_P,Res0,Res) ?=> Res #= Res0.
fold2([X|T],P,Res0,Res) ?=>
  call(P,Res0,X,Res1),
  fold2(T,P,Res1,Res).  

Now we can defined both sum/2 as well as prod/2 (for product of the elements in a list/array) like this, again checking if it's an array or list.

% Multiplication
mult(X,Y,Z) =>
  Z #= X * Y.

% Addition
add(X,Y,Z) =>
  Z #= X + Y.

% Define sum/2 for array
sum5(X,Sum), array(X) ?=>
  fold2(X.to_list,add,0,Sum).

% sum/2 for list
sum5(X,Sum), list(X) ?=>
  fold2(X,add,0,Sum)

% Define prod/2 for array
prod5(X,Prod), array(X) ?=>
  fold2(X.to_list,add,1,Prod).

% prod2/2 for list
prod5(X,Prod), list(X) ?=>
  fold2(X,add,1,Prod).