Match on structure, bind whole value

In Erlang I can do something like this:

f(L = [_|_]) -> % code

This will match on any list that has at least one element and bind the whole list to L.

Is there some similar construct available in prolog?

I tried the following on an online playground (I’m on mobile without proper prolog interpreter).

f(A = [_|_], A).

Hoping it would act like identity for any list of length greater than or equal to 1, but it just replied false independent of how I called the predicate. Except for when I use it as a “generator” then it produces results to what I’d expect:

?- f(B, A).
B = (A=[_1514|_1516])
?- f([a], A).
false
?- f([a,b], A).
false

Using a list just for the example, the data that I do in fact expect will be a lot more complex compound terms.


Edit:

As this might also be specific to the online playground I used, it’s this one:

https://swish.swi-prolog.org/

You can’t do both in one go. Either

f(L) :-
    L = [_|_],
    % code using `L`

or

f([X|Xs]) :-
    % code using `[X|Xs]`
1 Like

Thanks, that seems to work in the online playground and I’m pretty sure it will do for the actual usecase later on as well.

If I do it in the head or “later” in the body shouldn’t matter much as I understand it, as prolog would check other clauses due to backtracking anyway?

Correct. And if at some point in the clause you don’t want others to be checked, you can use cut (!), but that is non-logical.

1 Like

True, but there is an efficiency issue.

If you do the test in the head, then Prolog can do some clever things, e.g.:

pred([], ...) :- ...
pred([X|Xs], ...) :- ...

allows the Prolog compiler to generate “indexing” code that so that at runtime it can go directly to the appropriate clause without creating any choice points.

If instead you have

pred([], ...) :- ...
pred(L, ...) :- L = [X|Xs], ...

then the indexing code isn’t generated, so extra choice points are left around.

An unnecessary choice point not only slows things down (by allowing unnecessary backtracking), but also can cause some values to go onto the heap rather than the stack. Adding a “cut” (e.g., pred(X, ...) :- L = [X|Xs], !, ... only partially improves the situation – it’s best to have enough information in the head of the clause to avoid the creation of a choicepoint in the first place.

If you do something like this:

pred([X|Xs], ...) :- ... pred2([X|Xs]), ...

there is a slight inefficiency in creating the 2nd list from [X|Xs] but it’s much less overhead than the gain from the indexing code – [X|Xs] can be as little as a one or two byte code instructions, and can create a cell on the stack, which is automatically removed by tail recursion optimization.
[In theory, a Prolog compiler could detect that the creation of [X|Xs] uses a value from the head, but I’m not aware of any compiler that does this – if you want to know more about the kinds of local and global optimizations that are possible, see Peter van Roy’s thesis on the Aquarius compiler and SWI Prolog deep indexing.]

The bottom line is: put as much structure as you can into the head of a clause and don’t worry about “duplicate” creation of terms.

4 Likes

Yes. Some Prolog systems (AFAIK) do include unification to head arguments that precedes other predicate into their clause indexing and thus the two clauses below are the same from an indexing perspective.

f(X) :- X = [H|T], ...
f([H|T]) :- ...

Others do capture code like f([H|T]]) :- g([H|T]) and avoid a structure copy. Current SWI-Prolog does neither though. I’m not really sure how much there is to be gained by implementing this. As @peter.ludemann claims, duplicating the term and accepting the structure copy is probably the best choice from a performance and logical point of view.

1 Like

I have to say that many times I’ve missed the handling for the first case:

f(X) :- X = [H|T], ...
f([H|T]) :- ...

Not only for lists but also for other terms decomposition in head that don’t prevent indexing.

To be forced to write:

f(p(_,_,_), T) :-
  ...
%% 10 more clauses for other terms

m :-
   X = p(1,2,3),
   f(X, X).

is indeed a pity (at least IMHO).

The Logtalk compiler folds left unifications in a clause body when compiling code in optimized mode. Thus, for the first clause above, you get as head argument [H|T]. This is a useful optimization as left unifications are often generated when compiling grammar rules.

Indexing of this:

Is not extremly difficult. You were about to index the first argument, and you find a variable X. So usually you then have no functor or type to index. But you have the variable X, and you can start analyzing the body of the clause, look what happens with the variable. Such an algorithm is documented here:

Step 2.2.2 of algorithm I of:
http://user.it.uu.se/~kostis/Papers/iclp07.pdf

I have implemented it for Jekejeke Prolog here:

static Object indexValue(int at, Clause clause)
https://github.com/jburse/jekejeke-devel/blob/c3e654b74a60b9d0f2f5b891e8ff0c0c7e6dd021/jekrun/headless/jekpro/model/rope/Index.java#L70

You see that it works here, that choice point elimination, which needs indexing, works fine. Here is a usual append:

app([],X,X).
app([X|Y],Z,[X|T]) :- app(Y,Z,T).

And here is an append with the functor or type to index in the body:

app2(A,X,X) :- A = [].
app2(A,Z,[X|T]) :- A = [X|Y], app2(Y,Z,T).

Here you see that SWI-Prolog cannot eliminate the choice point, since it doesn’t have enough indexing information:

Bildschirmfoto 2020-01-02 um 03.18.16

On the other hand here choice point elimination works fine, even when the a term is moved out of the head:

Bildschirmfoto 2020-01-02 um 03.20.28

Whats not yet working is deep indexing of the term. This is no wonder, since deep indexing does also not yet work in the head of a clause in my Prolog system. But what I would like to do, as an interim benefit, I would like to extend it to nonvar/1 checks.

Currently var/1 checks are also indexed. But nonvar/1 checks have also a few interesting use cases.

Probably true. The implementation should probably be part of improving the weak spot in SWI-Prolog’s indexing code: building efficient indexing for predicates with a small number of clauses (say up to about 10). Above that we are typically dealing with fairly uniform clauses and the current JIT indexing does a pretty good job. Some special few clauses cases have been implemented, but there is quite an important class where indexing is not great. Interesting project, but there is too much more pressing work right now.

The SWI-Prolog DCG compiler does this :slight_smile:

1 Like

Note that the problem is not (only) indexing, but to have the possibility to avoid term rebuilding without to lose indexing. E.g.:

Here we lose indexing but we avoid to rebuild the huge term:

p(g(X), X).
p(A, A) :-
  A = f(Many_Arguments...).
% Many other similar clauses

Here we have indexing but we are forced to rebuild the huge term:

p(g(X), X).
p(f(Many_Arguments...), A) :-
  A = f(Many_Arguments...).
% Many other similar clauses

Here we have both but we are forced to add another argument just to circumvent the limitation:

p(g(X), _, X).
p(f(Many_Arguments...), A, A).
% Many other similar clauses

% To be called with p(In, In, Out).

The motivation for this special kind of indexing was term sharing. But there exist also other motivations when not only (=)/2 is analyzed in the body of a clause but also var/1, functor/3, etc… But concerning (=)/2 in the body of a clause we have:

Before this type of indexing, I had to write:

p(BigTerm, ...) :- ... BigTerm ...

Now I can write and do not loose indexing:

p(Var, ...) :- Var = BigTerm, ... Var ...

Picat has a special solution for that:

p(Var@BigTerm, ...) :- ... Var ...

See here as-pattern operator (@),
4.3 Patterns and Pattern-Matching
http://picat-lang.org/download/picat_guide.pdf

Picat also explains its motivation as term sharing. They write in their guide:

A pattern can contain as-patterns in the form V@Pattern, where V is a new variable in the rule, and Pattern is a non-variable term. The as-pattern V@Pattern is the same as Pattern in pattern matching, but after pattern matching succeeds, V is made to reference the term that matched Pattern. As-patterns can avoid re-constructing existing terms.

But I did not like the Picat solution since it needs term/goal expansion up to function expansion. So I think the (=)/2 solution is the cleaner solution. And the good thing, according to the ICLP07 Paper, its even a known thingy.

For example YAP Prolog could already do it, we also see choice point elimination for this Prolog system. Choice point elimination is only used as a quick check here, whether the body equation indexing works or not, its not the main motivation:

image

Disclaimer: Jekejeke Prolog has different term sharing than other Prolog systems. Even without (=)/2 the term would be shared and not created on the stack. But the clause would get bigger, because I don’t do any common term analysis during clause assert. This would be another approach as well.

I understand. But if those source clauses are encapsulated in a Logtalk object (or category) they would be compiled into clauses with g(X) and f(Many_Arguments...) as first-arguments before calling the backend Prolog compiler on those clauses. Thus, you get indexing without having to rebuild the huge term. Without Logtalk, it’s easy to define a term expansion that removes left unifications from a clause.

AFAIK, XSB does this. I am thinking about doing something like that, in particular I consider to compile body terms that are equivalent to a head term to use the head term. That shouldn’t be particularly hard. With that in place, the source transformation by Logtalk does the job. I first need to make up my mind though.

Doing that in the way you describe changes slightly current semantic:

p1(p(X), A) :-
    A = p(X).

q1 :-
    A = p(3),
    p1(A, B),
    same_term(A, B).

p2(A, A) :-
    A = p(_).

q2 :-
    A = p(3),
    p2(A, B),
    same_term(A, B).

If you do what you are writing above these two examples will behave in the same way (i.e. semantic of p1 will change).

If instead the thing has an effect only on indexing for p2 the current semantic of p1 would be preserved.

True. But, this only applies when using destructive assignment. In the normal Prolog world the difference is not observable. So, the issue is whether there are realistic scenarios where one writes

f(p(X)) :- g(p(X)).

with the intend to make a copy and avoid destructive assignment affecting both terms? If not, it is a mere matter of documenting. From my experience with destructive assignment I don’t think this is a real issue.

1 Like

Isn’t this only an issue when using Declarative Semantics Killer ™ seterg/2 and friends?

Isn’t expecting clause:

p1(p(X), A) :-
    A = p(X).

to have different semantics than the clause:

p1(p(X), p(X)).

terrible practice?

This is exactly my point: i.e. doing things as Jan was considering to do leads to your two clauses to have different semantics.

OTOH as Jan W. is saying the difference is very subtle and seldom make a difference in real code.

Jan B. is instead showing how is possible to have the same benefit without to change current semantic.

As a non-functional property the sharing is observable. You can try the following:

p(A, B, C, D, E) :-
      D = f(E,E,E,E),
      C = f(D,D,D,D),
      B = f(C,C,C,C),
      A = f(B,B,B,B).

If you do a Logtalk source transformation you get a clause of size 4^4+4^3+4^2+4^1 = 340 memory cells. If you don’t do a Logtalk source transformation you get a clause of size 5*4 = 20 memory cells.

Same for the runtime, i.e. the thread time use by calling for example:

?- p(Y,_,_,_,X).    

I didn’t test yet, since I don’t have a souce transformer. Maybe I can add some timing comparison by using a manual transformation. This is observable if the Prolog system doesn’t apply some common subexpression elimination while compiling clauses.

Common subexpressions elimination would possibly need hash calculation and 340 head searches, and would slow down assert and retract, so I don’t have this. Thats why I call it explicit sharing. Its not an automatism. Its something that the programmer can do by using (=)/2.

A modified Logtalk transformation could possibly only move the terms to the head up to some depth. But to not negatively affect deep indexing it would need some good heuristics here. This is not yet a problem in my Prolog system, since I don’t have yet deep indexing.

Edit 02.01.2019:
Here are some timings, pretty much the ratio 340 cell/20 cell from slow to fast:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.16)

/* with sharing */
?- time((between(1,1000000,_),p(Y,_,_,_,X),fail;true)).
% 1,999,999 inferences, 0.266 CPU in 0.254 seconds (104% CPU, 7529408 Lips)
true.

/* without sharing */
?- time((between(1,1000000,_),p2(Y,_,_,_,X),fail;true)).
% 1,999,999 inferences, 3.297 CPU in 3.289 seconds (100% CPU, 606635 Lips)
true.

I used the following manually transformed p/5:

?- listing(p2/5).
p2(f(f(f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A),
 f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A),
 f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A),
 f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A),
 f(A, A, A, A))), f(f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A))), f(f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A),
 f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A),
 f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A))), f(f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)))), f(f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A))), f(f(A, A, A, A), f(A, A, A, A), f(A, A, A, A), 
f(A, A, A, A)), f(A, A, A, A), A).