Picat style matching

Request For Comments
65

Good to hear! In my experience it is close to a game changer. Notably the resulting exceptions from lack of a matching clause/rule and the fact that insufficiently instantiated arguments do not run the wrong clause is very valuable. I easily dare to state that development and maintenance of Prolog code got a lot better.

And, as shown here and confirmed by you, “vendor lock in” is no reason not to use it as term expansion can make this available in any ISO compliant Prolog implementation (well, term expansion is not in all Prolog systems and is not covered by ISO, it is around in all major systems though). The impact on performance and clause indexing from such an implementation may vary.

P.s. I’m open to new insights, sync and cleanup the way it works.

2 Likes
66

Thanks Jan. Would it be possible to obtain or design a few test suite cases that check that enough corner cases are covered? Our implementation is intentionally a source-to-source transformation and it performs some optimizations and we still need to figure out if they are sound. Ideally, it would be awesome to have, side by side, Picat and Prolog examples and document any difference between Neng-Fa Zhou’s Picat semantics.

As you know the Ciao model pushes a slightly different approach: add program assertions to a more or less standard Prolog program and let the analyzer tell you if some determinism, etc. condition is violated (descriptive). The SSU syntax looks very handy but it is prescriptive and we need to be careful (in Ciao) about how/when to combine them. But definitely it is a tool! If possible it is worth having it as a language extension, like DCGs, so that programmers can use it when they feel it is convenient.

1 Like
67

I’m afraid there are no real test cases. There is in the meanwhile a lot of library code that uses SSU and that is part of the test suite. The docs are at Single Sided Unification rules. Not much can go wrong the way SWI-Prolog implements it: it simply checks nothing is trailed after the head unification is complete and if this is correct it commits to the current clause. If there are guards (Head, Guard => Body), the cut is moved to after the Guard).

I guess you can generate test cases and use SWI-Prolog as a wizard?

Section 5.6.1 on the page above (“Single Sided Unification Guards”) documents a dubious choice. Comments on that aspect are welcome. Otherwise there are IMO not that many choices. One could argue to follow Picat and not throw an exception if no rule matches. In my experience that is the most valuable part though. I’m happy to reconsider the exact exception as well as the term rule used for this (which I dislike, but nothing betters was proposed). One could also consider disallowing unification against the head in the Guard. Picat also allows for that (AFAIK) and I fail to see a good way to implement such a restriction.

68

Erlang explicitly lists side-effect-free predicates that can be used in their guards. Too restrictive and anyway serving a slightly different purpose, but mentioning it here for posterity. Please forgive me if I already brought this up before.

Erlang guard sequences and expressions

EDIT: by too restrictive I mean that at the very least the programmer should be able to define a predicate (at run time?) and use it in the guard.

70

Exciting! Would it be possible to post the expansion code here? I’m trying to implement => in Tau Prolog (in userland), and it’d be nice to have a second opinion.

71

Since CHR is also single sided unification in head. In effect, the picat => is a bit like the procedural usage of CHR.

For example,

fac(N, F) :-
    fac(N, 1, F).

fac(1, F0, F) <=>
    F = F0.
fac(N, F0, F) <=>
    integer(N), N > 1
    | 
    F1 is F0*N,
    N2 is N - 1,
    fac(N2, F1, F).
fac(_, _, _) <=>
     throw(error('No rule matches',_)).

?- fac(5,F).
F = 120.

?- fac(5,121).
false.

?- fac(a, X).
ERROR: Unknown error term: 'No rule matches'
ERROR: In:
ERROR:   [13] throw(error('No rule matches',_118596))
ERROR:    [9] toplevel_call(user:user: ...) at c:/program files/swipl/boot/toplevel.pl:1117
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

?- fac(-1, X).
ERROR: Unknown error term: 'No rule matches'
ERROR: In:
ERROR:   [13] throw(error('No rule matches',_122452))
ERROR:    [9] toplevel_call(user:user: ...) at c:/program files/swipl/boot/toplevel.pl:1117
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

?- fac(_, X).
ERROR: Unknown error term: 'No rule matches'
ERROR: In:
ERROR:   [13] throw(error('No rule matches',_126352))
ERROR:    [9] toplevel_call(user:user: ...) at c:/program files/swipl/boot/toplevel.pl:1117
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

It seems that any picat => like program can be mechanically converted to CHR program.

2 Likes
72

I like the Picat style matching, but what about lambda?

The current pattern matching in library(yall) is not single sided.

For example,

%% wrong
?- Ls = [c(X), a, c(1)], include([c(1)]>>true, Ls, Ls2).
Ls = [c(1),a,c(1)],
X = 1,
Ls2 = [c(1),c(1)].

%% correct
?- Ls = [c(X), a, c(1)], include([C]>>subsumes_term(c(1), C), Ls, Ls2).
Ls = [c($VAR(X)),a,c(1)],
Ls2 = [c(1)].

It would be nice if lambda also provides the Picat style matching.

73

The first one, a/1, produces only one result, which I understand. The second and the third, b/1 and c/1, produce two results, which is exactly what I need right now.

a(X)
 => X = 1.

a(X)
 => X = 2.

b(X)
 => X = 1 ;
    X = 2.

c(X)
 => b(X).

This is the intended behavior, isn’t it? I am just asking. FWIW, I like it.

74

Yes. That is how it works. => causes the head unification to be pattern matching (i.e., no variables from the goal are instantiated) and acts as a !. After that, normal Prolog non-determinism holds.

1 Like
75

One problem I have with => is that these two predicates behave differently if called with an uninstantiated variable:

p(X, X) => true.
p(_, _) => false.

q(X, Y), X = Y => true.
q(_, _) => false.

?- p(1, X).
false.

?- q(1, X).
X = 1

I suppose that this is because q/2 violates the “should not instantiate in the head or guards”, but it feels inconsistent.

76

True. If I recall well, also Picat does not enforce this. I couldn’t find a good way to enforce a well behaved guard. The => rules make it a lot easier to write good functional code, but it does not enforce it :frowning:

77

It’s not clear to me how to write “good functional code” for something as simple as equality. Maybe this?

q2(X, Y), nonvar(X), nonvar(Y), X = Y => true.
q2(_, _), nonvar(X), nonvar(Y) => false.

Probably should be \+ ground(X), \+ ground(Y).

Which isn’t going to be as efficient.

And changing X=Y to \+ \+ X=Y produces even less sensible results.

78

Not sure about it but my first feeling was (and still is): no side effects, and no further instantiation should be allowed in the guard. This would also mean that dif/2 is not allowed. But all that sounds way too strict, for no obvious benefit.

Either way, can you explain briefly what do you mean exactly, “good functional code for equality”? How is it different from ==/2? I see the unification in the guard in your q2/2 but I am not sure how you mean to use this.

79

When the ?=> does a cut, can it detect if a unification has happened (the trail stack has grown)?

80

I guess it depends what you want to express. Other options are =@=/2 or subsumes_term/2. All smells very much that you are trying to define a good old Prolog relation though and => tries to make that hard.

Yes, but things only get dubious when the guard binds variables in the head, not if it binds internal variables introduced in the guard itself. => merely makes it more natural to write code as (1) examine input, (2) commit and finally (3) create bindings so we don’t get the commonly seen

max(X,Y,Y) :- Y >= X, !.
max(X,_,X).
1 Like
81

Here’s my attempt to define a “compare” function using Picat-style, and it behaves more-or-less as I’d expect if one of the arguments is uninstantiated:

comp(X,X,Comp) => Comp = '='.
comp(X,Y,Comp), X > Y => Comp = '>'.
comp(_,_,Comp) => Comp = '<'.

But if I want to use full term ordering:

comp2(X,X,Comp) => Comp = '='.
comp2(X,Y,Comp), X @> Y => Comp = '>'.
comp2(_,_,Comp) => Comp = '<'.

?- comp2(f(a), g(_), Comp).
Comp = (<).  % this is what I'd expect

?- comp2(f(X), f(a), Comp).
Comp = (<).  % I suppose this is OK, but it could also have Comp='=',X=a as a solution

From a “functional” point of view, the queries with comp2/3 have no meaning because uninstantiated variables aren’t part of functional programming. But uninstantiated variables can be used to get the “results” of functional computations. If I’m careful, then there’s no problem; but if I accidentally call comp2/2 with the wrong kind of arguments, it produces weird results.

Picat-style has the nice property that if none of the clauses match, I get an error. It would be nice if I also get an error if the arguments aren’t sufficiently instantiated – and I think that can be done by the “cut” checking that the trail hasn’t changed (that is, the head+guards haven’t caused anything to become instantiated).

EDIT:

Consider also these two variants, which ought to be equivalent to the code above:

comp3(X,Y,Comp), X=Y => Comp='='.
comp3(X,Y,Comp), X@>Y => Comp='>'.
comp3(_,_,Comp)       => Comp='<'.

comp4(X,Y,Comp), X@>Y => Comp='>'.
comp4(X,Y,Comp), X@<Y => Comp='<'.
comp4(_,_,Comp),      => Comp='='.
82

According to the => style handling, variables are just data, so

 p(X), var(X) => ...

is completely fine. I think that is ok. In fact, the trigger for considering to add => was code analysis where one often wishes to match structures, but you do not want normal unification, e.g.

 optimize((member(E,L),!)), Opt) => Opt = memberchk(E,L).

Which you do not want to match against (Var,!).

This is one of the ugly edges: the unification is moved into the head and subsequently subject to single sided unification … Using ==/2 is conceptually cleaner.

2 Likes
83

That situation also arises when writing term_expansion/2 and goal_expansion/2 rules. So, I’d like something like => but that doesn’t throw an exception if there’s no match, and also that can be compatible with other clauses written with :-.

A workaround exists, of course; instead of writing

goal_expansion(#(A,B,C) = #(D,E,F), Goal) =>
    Goal = ( A=D, B=E, C=F).

I could write this (which is more-or-less what => expands to):

goal_expansion(Goal0, Goal) :-
    subsumes_term((#(A,B,C) = #(D,E,F)), Goal0),
    Goal0       = (#(A,B,C) = #(D,E,F)),
    Goal = (A=D, B=E, C=F).
84

We are also playing with the Picat style matching in Ciao Prolog and have serious doubts about no-match exception. For some cases it looks an excellent idea (indeed this is how our extension works now) but some cases (like mixing ?=>, =>, and asking for all solutions) it has bugs (which I think are also in SWI’s implementation). Besides those bugs, it looks that => without no-match exceptions is more “compositional” (you can mix :-, -->, => clauses more freely, etc.).

It seems also (at least in our extension) that it is possible to simulate one behavior or the other by writing one last clause to each predicate:

% last clause to avoid no-match exception (if your extension implements it)
foo(_,_) => fail.

% last clause to simulate no-match exception (if your extension do not have it)
foo(_,_) => throw(...).

I wonder if Neng-Fa Zhou wrote somewhere (probably we could ask him) why his => rules do not include the no-match exception (since they seem useful and are trivial to implement).

85

This doesn’t work with multifile predicates, such as goal_expansion/2, which is a predicate that benefits from single-sided unification.

A partial solution might be to add a predicate that’s the equivalent of

ssu(Generic, Specific) :-
    subsumes_term(Generic, Specific),
    Generic = Specific.

although it’s also nice to have the “guard” part of =>.