foreach with predicate

[Leszek Buczkowski]

Hi,

I am new to Picat, although I have had some contact with it in the past. And I would like to share some reflection. What struck me then and now is the disconnect between imperative and prolog programming styles. Consider the following program:

permute_with_insert(As, Bs) ?=>
    As = [],
    Bs = [].
permute_with_insert(As, Bs) =>
    As = [L|Ls0],
    permute_with_insert(Ls0, Ls),
    insert(L, Ls, Bs).

insert(X, Ys, Zs) ?=>
    Zs = [X|Ys].
insert(X, As, Bs) =>
    As = [Y|Ys],
    Bs = [Y|Zs],
    insert(X, Ys, Zs).    

test(N) =>
    foreach (L in findall(P, permute_with_insert(1..N, P)))
      write(L), nl
    end.

main =>
    test(3).

It works fine for test(3) but test(10) generates a stack overflow because it tries to collect all the results before iterating with foreach. Why isn't it possible to iterate over the results provided by the predicate on an ongoing basis? Something like:

test(N) =>
    foreach (L in findnext(P, permute_with_insert(1..N, P)))
      write(L), nl
    end. 

Then foreach could iterate over potentially infinite sequences.   

Cheers,

Leszek

[Hakan Kjellerstrand]

Hi Leszek.

Welcome to Picat!

Here are some comments.

The issue with test(10) is - as you mention - that Picat generates a stack overflow. This can be fixed fairly simply by using garbage_collect/1 to preallocate the appropriate memory. For example,:the following works without any stack overflow:

    main =>
       garbage_collect(100_000_000),
        test(10).

Preallocation memory with garbage_collect/1 can also speed up programs quite considerably, for example when reading large files.or when inserting many elements in a map.

That being said, a foreach loop loops over elements in a list/array which has to be calculated before the loop starts.

If you want to do some "lazy evalutation" in Picat, it's better to use some other approach using logic programming, for example a fail-driven loop such as the following:

   main ?=>

     N = 10,

     permute_with_insert(1..N, P), % generate next permutation
     writeln(P),
     fail, % force a backtrack
     nl.
   main => true.

This will generate and print all permutations of 1..10. fail/0 forces a backtrack to generate the next permutation.

Also, there's no need for garbage_collect/1 here since the permutations are generated and then discarded. You can try with N=100000 and see that the program starts immediately.

In principle, you could even use - or rather misuse - findall/2 and print the permutation directly. However, it will still collect the values so garbage_collect/1 is needed since all permutations are collected in a list.

  main =>

      garbage_collect(100_000_000),

     N = 10,
     _ =findall(_,(permute_with_insert(1..N, P),writeln(P))),
     nl.

(Please note: This is definitely not a recommended use of findall/2, just a showcase of its workings.)

So, it depends on how you want to use the generated data (permutation in this case).

For example - and this is a silly example - if you want to collect the sums of the two first elements in each permutation and then get the total sum of these numbers, then list comprehension might be an alternative:

   main =>
     garbage_collect(100_000_000),
     N = 10,
     S = [sum(L[1..2]) : L in findall(P, permute_with_insert(1..N, P))].sum,
     println(S),
     nl.

Collecting data using a fail-driven loop is a little more elaborated. Here the global map get_global_map() is used:

   main8 ?=>
    N = 10,
    garbage_collect(300_000_000),
    Map = get_global_map(), % The global map
    Map.put(ss,0), % Initialize ss
    permute_with_insert(1..N, P),
    Map.put(ss,Map.get(ss)+sum(P[1..2])), % update the value
    fail, % backtrack
    nl.
  main :-
    Map = get_global_map(),
    println(Map.get(ss)),
    nl.

This latter version using fail-driven loop is faster (0.8s on my fairly old machine) than the one using list comprehension (1.8s), much because the fail-driven loop does not need to handle a huge list.

(By the way there's a built-int function permutation/1 in the util module, which gives all permutations of a list.)

Hope this helps.

/Hakan

[Leszek Buczkowski]

Hi Hakan,

Thanks for useful tips! They will surely come in handy sooner or later.

I've come to a conclusion that it's easier to understand the logic behind Picat when one realizes that imperative programming in Picat is just syntactic sugar on top of Prolog. If foreach loop is translated into simple Prolog clauses, generators with resumption (aka findnext) are not easy to implement.

Another thing that puzzled me today:

I tried once to port to Picat a Prolog solution to the 8-Queen problem:

[listing 1 (not working)]

queens(N, Queens) :-
  Queens = new_list(N),
  place_queens(N, Queens, _, _).

place_queens(0, _, _, _) => true.
place_queens(N, Cs, Us, [_|Ds]) =>
  place_queens(N - 1, Cs, [_|Us], Ds),
  place_queen(N, Cs, Us, Ds).

place_queen(N, [N|_], [N|_], [N|_]) ?=> true.
place_queen(N, [_|Cs], [_|Us], [_|Ds]) =>
  place_queen(N, Cs, Us, Ds).

main :-
  writeln(findall(Queens, queens(8, Queens))).

I could not get it working until I found an explantation in your article from 2014 "Picat: A Logic-based Multi-paradigm Language":

"One difference between Picat’s pattern matching and Prolog’s is that no variables in calls can get bound
during Picat’s pattern matching, and such bindings must be explicitly done in the body of a rule. For example,
the definition of append/3 cannot be stated in Picat as nicely as in Prolog.

append2(Xs,Ys,Zs) ?=> Xs=[], Ys=Zs.
append2(Xs,Ys,Zs) => Xs=[X|XsR], Zs=[X|ZsR], append2(XsR,Ys,ZsR).

This version has the same non-deterministic behavior as in Prolog, but it does not deterministically branches on
the first argument in case it is non-variable."

The working solution was:

[listing 2 (working)]

queens(N, Queens) =>
  Queens = new_list(N),
  place_queens(N, Queens, _, _).

place_queens(0, _, _, _) => true.
place_queens(N, Cs, Us, Ds) =>
  Ds = [_|DsT],
  place_queens(N - 1, Cs, [_|Us], DsT),
  place_queen(N, Cs, Us, DsT).

place_queen(N, Cs, Us, Ds) ?=>
  Cs = [N|_], Us = [N|_], Ds = [N|_].
place_queen(N, Cs, Us, Ds) =>
  Cs = [_|CsT], Us = [_|UsT], Ds = [_|DsT],
  place_queen(N, CsT, UsT, DsT).

main =>
  writeln(findall(Queens, queens(8, Queens))).


Today I discovered that Picat also supports Prolog-style Horn clauses (which made me happy):

[listing 3 (working)]

queens(N, Queens) :-
  Queens = new_list(N),
  place_queens(N, Queens, _, _).

place_queens(0, _, _, _) :- !.
place_queens(N, Cs, Us, [_|Ds]) :-
  place_queens(N - 1, Cs, [_|Us], Ds),
  place_queen(N, Cs, Us, Ds).

place_queen(N, [N|_], [N|_], [N|_]).
place_queen(N, [_|Cs], [_|Us], [_|Ds]) :-
  place_queen(N, Cs, Us, Ds).

main :-
  writeln(findall(Queens, queens(8, Queens))).


So I came to a conclusion that:

- when predicates are defined using => / ?=> variables in calls CANNOT get bound in pattern matching,
- when predicates are defined using :- variables in calls CAN get bound in pattern matching, in the same way as in Prolog.

However, the following example puzzled me again:

member2(X,[Y|_]) ?=> X=Y.
member2(X,[_|L]) => member2(X,L).

I wonder what is the difference compared to the approach in listing 1 that makes member2 work.

In particular: 

member2(X,[_|L]) => member2(X,L).

is not different from:

place_queen(N, [_|Cs], [_|Us], [_|Ds]) =>
  place_queen(N, Cs, Us, Ds).

But putting it into listing 2 in place of:

place_queen(N, Cs, Us, Ds) => 
  Cs = [_|CsT], Us = [_|UsT], Ds = [_|DsT],
  place_queen(N, CsT, UsT, DsT).

results in non-working code.

What is actually the reason for Picat to support both => and :- style,  can you provide any tips when to use each? 

Cheers, Leszek

[Hakan Kjellerstrand]

Hi Leszek.

The reason behind =>/2 and ?=>/2 is that these are explicit for controlling determinism (backtrackability) of a predicate.  Using =>/2 yields no backtracking (is deterministic) whereas ?=>/2 yields non-determinism.  Prolog's :-/2 is always non-deterministic which can give unexpected results sometimes,  and one might been forced to use cut - !/0 - to prohibit certain backtracking.

(Following Picat, SWI-Prolog has implemented a variant of =>/2 for defining non-backtrackable predicates.)

I would say that the difference of handling the binding of variables when using ?=>/=> versus :- is orthogonal to how determinism are handled.

My own usage of =>/?=> vs :- is not very strict, but I tend to use =>/?=> by default (it's in the muscle memory and in my Picat template). But when writing more "advanced" recursive predicates or predicates which uses unification in the head, I switch to :-/2 quite soon, mostly because I don't have to think about the binding issues in the head with ?=>/=>, such as the one you wonder about.

Neng-Fa: Perhaps you  have some more comments on this?

/Hakan

[Neng-Fa Zhou]

I always use => and ?=> because rules are more readable with explicit inputs/outputs and determinism. In addition, such rules are fully indexed and tend to run faster. You cannot mix Prolog-style clauses (:-) with matching rules. In your example, place_queens could be rewritten into the following matching rules:

place_queen(N, [N1|Cs], Us, Ds) ?=> N = N1, Us = [N|_], Ds = [N|_].
place_queen(N, [_|CsT], Us, Ds) =>

  Us = [_|UsT], Ds = [_|DsT],
  place_queen(N, CsT, UsT, DsT).

Cheers,

NF

[Leszek Buczkowski]

In "A User's Guide to Picat" there is a statement:

"The Horn clause *can*  be translated equivalently to the following pattern-matching rule:

p(V1, . . . , Vn) ?=> V1 = $t1, . . ., Vn = $tn, Body.

where the dollar symbols indicate that all of the ti’s are terms, rather than function calls."

Should the word *can* be understood here literally and :- clauses are translated by the compiler to ?=> as described, similarly to how foreach is translated to tail-recursive predicates? Or is *can* rather illustrative and :- clauses are implemented independently of ?=> or even directly use BProlog for their implementation?

--------

Regarding the difference between:

member2(X,[_|L]) => member2(X,L).

and

place_queen(N, [_|Cs], [_|Us], [_|Ds]) :-
  place_queen(N, Cs, Us, Ds).

I realized that despite visual similarity they do different things. member2 deconstructs an existing list while place_queen constructs a new list. Let's compare the following predicates:

member2(X,[Y|_]) ?=> X=Y.
member2(X,[_|L]) => member2(X,L).

member3(X,Z) ?=> Z=[Y|_], X=Y.
member3(X,Z) => Z=[_|L], member3(X,L).

member4(X,[Y|_]) :- X=Y.
member4(X,[_|L]) :- member4(X,L).

I believe member3 and member4 are functionally equivalent (unless there are other subtle differences between :- and ?=>).

And at glance member2 and member3 also do the same:

Picat> member3(X, [1, 2, 3]).
X = 1 ?;
X = 2 ?;
X = 3 ?;

no

Picat> member2(X, [1, 2, 3]).
X = 1 ?;
X = 2 ?;
X = 3 ?;

no

The difference becomes apparent when we start to create a list instead of destructing an existing one:

Picat> member3(1, L).
L = [1|_f558] ?;
L = [_f550,1|_f568] ?;
L = [_f550,_f560,1|_f578] ?;
L = [_f550,_f560,_f570,1|_f588] ?


Picat> member2(1, L).

no

And if I understand correctly, the reason pattern matching works differently than full unification is that unification is undone on backtracking while pattern matching is not. And for this reason the construction of the list L in the call member2(1, L), if it were allowed, would have an unpleasant side effect similar to assert (which is non-backtrackable) rather than reversible unification.

Please correct me if I am wrong.

[Neng-Fa Zhou]

Picat took pattern-matching rules from B-Prolog. Horn clauses can be translated to pattern-matching rules naively as described in the guide. The real implementation does the translation based on modes. You can find the details in this paper.

Cheers,

NF

--
You received this message because you are subscribed to the Google Groups "Picat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to picat-lang+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/picat-lang/2e88ba08-94b7-4417-b33a-29707a143f08n%40googlegroups.com.