Path: ...!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.prolog
Subject: Re: When do two Prolog terms marry? (Was: The issue with free speech)
Date: Mon, 14 Oct 2024 19:22:08 +0200
Message-ID: <vejjvu$dleb$1@solani.org>
References: <db8a6771-3e54-485b-b391-310658dd6f52n@googlegroups.com>
 <d9588b9c-edcc-4f8b-85d2-7487b5556798n@googlegroups.com>
 <ve6v8n$7df2$1@solani.org> <ve6vbr$7df2$2@solani.org>
 <ve718e$7ejh$1@solani.org> <vejjj4$dlal$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 14 Oct 2024 17:22:06 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="447947"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.19
Cancel-Lock: sha1:I1SKqzv5vrAqnZPdgj9w5iq9WYA=
X-User-ID: eJwFwQcBwEAIBDBLjAP6cpj+JTQxdfYOuDns7Ii4+J4DRCoc3EVBMycisarQLNJH8z5gjzNbNyrRN+t+PyTHFT4=
In-Reply-To: <vejjj4$dlal$1@solani.org>
Bytes: 4067
Lines: 106

Amazingly simple and falling back again on Richard O'Keefes
subsumes/2. How to implement subsumes/2 directly is
for example found here:

%   File   : METUTL.PL
%   Author : R.A.O'Keefe
%   Updated: 15 September 1984
%   Purpose: meta-logical operations as described in my note
http://www.picat-lang.org/bprolog/publib/metutl.html

subsumes/2 has the advantages that it doesn't need
cyclic term capable unification to be implemented,
since it has no problems in refuting:

?- subsumes(X, f(X)).
fail.

It can be also used to easily bootstrap subsumes_term/2:

subsumes_term(X,Y) :-
    \+ \+ subsumes(X,Y).

Putting the two together we can define:

marry(X, Y) :-
    subsumes_term(X, Y),
    subsumes(Y, X).

Lets see some test cases:

?- marry(f(X,Y,Z,T), f(A,B,C,D)).
X = A, Y = B, Z = C, T = D.
?- marry(f(X,Y,Z,T), f(A,B,Z,D)).
X = A, Y = B, T = D.
?- marry(f(A,Y,Z,T), f(A,B,Z,D)).
Y = B, T = D.
?- marry(f(A,Y,Z,T), f(A,B,C,Z)).
fail.
?- marry(f(X,A,Z,T), f(A,B,Z,D)).
fail.

What can we do with it? I recently made
distinct/1 working based on marry/2:

d(_,_).
d(a,a).
d(_,_).

?- findall(X-Y,d(X,Y),L).
L = [_70340-_70341, a-a, _70346-_70347].

?- findall(X-Y,distinct(d(X,Y)),L).
L = [_71298-_71299, a-a].

Which is pretty cool!

Mild Shock schrieb:
> Now I was struggling giving this predicate
> a better name. Namely variant_term bootstrapped
> as follows:
> 
> variant_term(X, Y) :-
>     subsumes_term(X, Y),
>     subsumes_term(Y, X).
> 
> Why does it need a better name? Well because it
> is not really the variant, as realized by
> for example SWI-Prolog's (=@=):
> 
> For example I find:
> 
> ?- variant_term(f(X,Y,Z,T), f(A,B,C,D)).
> true.
> ?- variant_term(f(X,Y,Z,T), f(A,B,Z,D)).
> true.
> ?- variant_term(f(A,Y,Z,T), f(A,B,Z,D)).
> true.
> ?- variant_term(f(A,Y,Z,T), f(A,B,C,Z)).
> fail.
> ?- variant_term(f(X,A,Z,T), f(A,B,Z,D)).
> fail.
> 
> The first 3 test cases match what variant/2
> usually does. But the last 2 test cases don't
> match what variant/2 usually does.
> 
> So how can characterize the behaviour of
> this weak variant. I came up with this observation:
> 
> - A weak variant takes has variables that appear
>    in the left hand side and in the right hand side,
>    i.e. common variables, only obtaining an identity
>    relation.
> 
> - Othewise variables that are either specific to
>    the right hand side or that are either specific
>    to the left hand side, are associated by a
>    bijection relation.
> 
> I came up with names like "twin", "sibling" for
> this relation. But I got also inspired by the
> fact that builtins:variant/2 from Scryer Prolog
> 
> leaves bindings. So looking for a name similar
> like "unify", but only its weak variant and it
> leaves a binding trace. My idea is to use "marry"!