Pure Prolog Peano List Intersection

Question

Assume we are only looking at lists of Peano numbers. And lets assume pure_2 Prolog is not pure_1 Prolog with dif/2, but rather with pure_1 Prolog with when/2. Can we implement list intersection?

We would step back and pick up ideas from programming languages Gödel and Nu-Prolog. Thus for any needed if-then-else we would draw on this answer here. What would be:

/* pure_2 Prolog = pure_1 Prolog with when/2 */
intersect(A, B, C) :- ??

Note that nevertheless contrary to Gödel and Nu-Prolog, to adhere to pure_2 Prolog for this equestion here we would be not allowed to use ISO Prolog if-then-else (->;_). But we might use an apartness relation as demanded here.

A test case would be steadfastness:

?- intersect([s(0)], [0], X).
X = []

?- intersect([X], [Y], Z), X = s(0), Y = 0.
X = []

Yes and no. There are some tricks to introduce fast failure. — , Dec 23 '20 at 16:53

MWB · Answer 1 · 2020-12-23T17:28:19.860

(Taking code from this and this)

less(0, s(_)).
less(s(X), s(Y)) :- less(X, Y).

neq(X, Y) :- less(X, Y); less(Y, X).

eq(0, 0).
eq(s(X), s(Y)) :- eq(X, Y).


horn_intersect([],_,[]).
horn_intersect(_,[],[]).

horn_intersect([X|Xs],List2,[X|Ms]) :- in(X,List2),horn_intersect(Xs,List2,Ms).
horn_intersect([X|Xs],List2,Ms)     :- not_in(X,List2),horn_intersect(Xs,List2,Ms).

in(X,[K|_]) :- eq(X, K).
in(X,[K|Ms]) :- neq(X, K),in(X,Ms).

not_in(_,[]).
not_in(X,[K|Ms]) :- neq(X, K),not_in(X,Ms).

Tests:

?- horn_intersect([X], [Y], Z).
X = Y, Y = 0,
Z = [0] ;
X = Y, Y = s(0),
Z = [s(0)] ;
X = Y, Y = s(s(0)),
Z = [s(s(0))] ;
X = Y, Y = s(s(s(0))),
Z = [s(s(s(0)))] ;
X = Y, Y = s(s(s(s(0)))),
Z = [s(s(s(s(0))))] ;
X = Y, Y = s(s(s(s(s(0))))),
Z = [s(s(s(s(s(0)))))] ;
X = Y, Y = s(s(s(s(s(s(0)))))),
Z = [s(s(s(s(s(s(0))))))] ;
X = Y, Y = s(s(s(s(s(s(s(0))))))),
Z = [s(s(s(s(s(s(s(0)))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(0)))))))),
Z = [s(s(s(s(s(s(s(s(0))))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(s(0))))))))),
Z = [s(s(s(s(s(s(s(s(s(...)))))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(s(s(...)))))))))),
Z = [s(s(s(s(s(s(s(s(s(...)))))))))] .

?- horn_intersect(X, Y, Z).
X = Z, Z = [] ;
Y = Z, Z = [] ;
X = Z, Z = [0],
Y = [0|_2472] ;
X = Z, Z = [0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0|...],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0|...],
Y = [0|_2472] .

@MostowskiCollapse new version seems to work. I'd say it's less expressive than Scheme in the forward direction. Of course, Scheme only works forward. — MWB, Dec 23 '20 at 17:29
Mostlikely you cannot do it without dif/2 or when/2. With your new version steadfastness fails: horn_intersect([X],[Y],Z), X=s(0), Y=0. ERROR: Stack limit (1.0Gb) exceeded — , Dec 23 '20 at 22:20

score -1 · Answer 2 · 2020-12-23T22:57:59.433

when/2 and freeze/2 do allow finer control than dif/2. Here is some code that uses when/2 and freeze/2 and that seems to be steadfast and also failfast, and doesn't leave choice points for ground input:

/* reified and delayed equality */
eq(X, Y, R) :- when((nonvar(X), nonvar(Y)), eq2(X, Y, R)).
eq2(0, 0, 1).
eq2(0, s(_), 0).
eq2(s(_), 0, 0).
eq2(s(X), s(Y), R) :- eq(X, Y, R).

/* reified and delayed disjunction */
or(X, Y, R) :- when((nonvar(X), nonvar(Y)), or2(X, Y, R)).
or2(0, 0, 0).
or2(0, 1, 1).
or2(1, 0, 1).
or2(1, 1, 1).

/* reified and delayed membership */
member(_, [], 0).
member(X, [Y|Z], R) :-
   eq(X, Y, H),
   or(H, J, R),
   member(X, Z, J).

/* reified and delayed if-then-else */
ite(B, P, Q) :- freeze(B, ite2(B, P, Q)).
ite2(1, P, _) :- P.
ite2(0, _, Q) :- Q.

/* */
intersect([], _, []).
intersect([X|Y], Z, T) :-
   ite(B, T = [X|R], T = R),
   member(X, Z, B),
   intersect(Y, Z, R).

Here are some example queries that test steadfastness:

?- intersect([s(s(0))], [s(0)], X).
X = []

?- intersect([X], [Y], Z), X = s(s(0)), Y = s(0).
X = s(s(0)),
Y = s(0),
Z = []

Here is an example query that test failfastness:

?- intersect([s(_)], [0], X).
X = []

Here is an example that shows what gets delayed through when/2:

?- intersect([X], [Y], Z).
freeze(_A, ite2(_A, Z = [X], Z = [])),
when((nonvar(X), nonvar(Y)), eq2(X, Y, _D)),
when(nonvar(_D), or2(_D, 0, _A))

The above was tested with Jekejeke Prolog 1.4.6, the library library(term/suspend) needs to be imported to make when/2 available. In SWI-Prolog eq/3 leaves a choice point, but this is the same problem like here.

You can read about nonvar/1 inside the when/2 docu. You will also find that dif/2 can be bootstrapped from when/2. Just check the SWI-Prolog docu for both built-ins. — , Dec 23 '20 at 23:41

Pure Prolog Peano List Intersection

2 Answers2