prolog - visit - what is code and logic programming

Usos declarativos de memberchk/2

Question

memberchk/2 es un predicado comúnmente definido que se define en términos de member/2 así:

memberchk(X, Xs) :-
   once(member(X, Xs)).

Por lo tanto, solo tiene éxito para la primera respuesta del member/2 . Su significado procesal completo no encaja en una relación pura. Como ejemplo de su comportamiento no relacional considérese

?- memberchk(b, [X,b]), X = a.
false.

?- X = a, memberchk(b, [X,b]).
X = a.

Por otro lado, en muchos casos se memberchk/2 con argumentos suficientemente ejemplificados , donde se puede ver como una aproximación eficiente de una relación pura.

Una de esas relaciones puras detrás es memberd/2 (usando if_/3 ):

memberd(E, [X|Xs]) :-
   if_(E = X, true, memberd(E, Xs) ).

¿Hay alguna otra relación pura que pueda ser aproximada por memberchk/2 para casos suficientemente ejemplificados?

En otras palabras: ¿es memberd/2 un reemplazo completo y declarativo para memberchk/2 o todavía hay casos legítimos en los que memberchk/2 no puede ser reemplazado por memberd/2 ?

Answer 1

Aquí hay un ejemplo de uso bien conocido del member/2 que no puede ser representado por memberd/2 : bridge.pl el problema de programación de puentes dado por Pascal Van Hentenryck.

En la fase de configuración se utiliza el member/2 :

setup(K,Ende,Disj):-
    jobs(L),
    make_vars(L,K),
    member([stop,_,Ende],K),
    ....

Así que aquí, efectivamente, el primer elemento en la lista de tres elementos se usa para seleccionar una tarea particular, mientras que memberd/2 usa todo el elemento para la comparación. Como consecuencia, esta setup/3 deja abiertos muchos puntos de elección (en realidad, 219). Algunos (como SICStus) utilizan memberchk/2 en esa situación, lo que memberchk/2 en riesgo la no monotonicidad.

Usando el siguiente reemplazo puro, se evitan todos los puntos de elección.

member3l([N,D,A], Plan) :-
   tmember(l3_t(N,D,A),  Plan).

l3_t(N,D,A, X, T) :-
   X = [Ni|_],
   if_(N = Ni, ( X=[N,D,A], T = true ), T = false ).

tmember(P_2, [X|Xs]) :-
   if_( call(P_2, X), true, tmember(P_2, Xs) ).

Alternativamente usando la library(lambda) :

member3li([N,Nd,Na], Plan) :-
   tmember([N,Nd,Na]+/X^T^
       (  X=[Nk|_],
          if_( Nk = N, ( X=[N,Nd,Na], T = true ), T = false ) ),
      Plan).

Otros usos de tmember/2 :

old_member(X, Xs) :-
   tmember( X+/E^T^( X = E, T = true ; T = false ), Xs).

old_memberd(X, Xs) :-
   tmember(=(X), Xs).

Aquí hay una representación más compacta:

member3l([N,D,A], Plan) :-
   tmember({N,D,A}+/[Ni,Di,Ai]^cond_t(N = Ni, [D,A] = [Di,Ai] ), Plan).

Usando library(lambda) y cond_t/3 :

cond_t(If_1, Then_0, T) :-
   if_(If_1, ( Then_0, T = true ), T = false ).

Answer 2

La siguiente respuesta no se relaciona directamente con la pregunta original con respecto a memberchk/2 ; en cambio, es un seguimiento de esta respuesta anterior que definió el meta-predicate tmember/2 .

Proponemos generalizar el idioma tmember/2 así:

t_non_empty_suffix(P_3, [X|Xs]) :-
   if_(call(P_3,Xs,X), true, t_non_empty_suffix(P_3,Xs)).

Sobre la base de t_non_empty_suffix/2 y Prolog lambdas , podemos definir tmemberX/2 así:

:- use_module(library(lambda)). tmemberX(P_2, Xs) :- t_non_empty_suffix(P_2+/_^call(P_2), Xs).

Los siguientes old_memberX/2 y old_memberdX/2 usan tmemberX/2 lugar de tmember/2 :

old_memberX(X, Xs) :-
   tmemberX(X+/E^T^( X = E, T = true ; T = false ), Xs).

old_memberdX(X, Xs) :-
   tmemberX(=(X), Xs).

Comparemos old_member/2 con old_memberX/2 ...

?- old_member(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

... y old_memberd/2 a old_memberdX/2 !

?- old_memberd(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

¡DE ACUERDO! ¿Qué hay de definir old_member / old_memberd directamente basado en t_non_empty_suffix/2 ?

old_memberSFX(X, Xs) :-
   t_non_empty_suffix(X+/_^E^T^( X = E, T = true ; T = false ), Xs).

old_memberdSFX(X, Xs) :-
   t_non_empty_suffix(X+/_^E^( X = E ), Xs).

Ejecutando consultas anteriores con estos predicados obtenemos:

?- old_memberSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

¡Bien! Los mismos resultados que antes.

Vamos a profundizar un poco más! Como caso de t_non_empty_suffix/2 para t_non_empty_suffix/2 considere duplicate_in/2 .
Usando t_non_empty_suffix/2 , Prolog lambdas , (=)/3 , y memberd_t/3 definimos:

'',''(P_1, Q_1, T) :-
   if_(P_1, call(Q_1,T), T = false).

duplicate_in(X, Xs) :-
   t_non_empty_suffix(X+/Es^E^( X = E, memberd_t(E, Es) ), Xs).

Consulta de muestra:

?- duplicate_in(X, [1,2,3,2,3,4,3,4,5]). X = 2 % [1,2,3,2,3,4,3,4,5] (2 occurs twice) ; X = 3 % [1,2,3,2,3,4,3,4,5] (3 occurs thrice) ; X = 4 % [1,2,3,2,3,4,3,4,5] (4 occurs twice) ; false.

Answer 3

memberb / 2 es un ejemplo típico de negación constructiva. Puede dar la vuelta al requisito y, por ejemplo, requerir:

?- ~ member(X, [a,b,c]).
dif(X, a),
dif(X, b),
dif(X, c)

Donde ~ sería la negación constructiva. Para una discusión sobre cómo se relaciona la negación constructiva con if_ vea, por ejemplo, here .

La desventaja de las definiciones inductivas totalmente declarativas, para memberd / 2 o por ejemplo, es que la separación de Prolog (;) / 2 no puede simplificar las restricciones, y que Prolog no tiene un formato que simplifique también las restricciones tales como diff / 2 .

De modo que al final, cuando lo haga correctamente con las limitaciones limitadas (;) y 2, obtendrá en el mejor de los casos soluciones completas que contienen muchas restricciones redundantes cuando observa los conjuntos de soluciones completos que produciría el intérprete.

Aquí hay un ejemplo en Jekejeke Prolog, requiere la extensión Minlog para que el predicado diff / 2 esté disponible:

:- use_module(library(term/diff)).
:- use_module(library(basic/lists)).
test(Y) :- diff(X, a), member(Y, [a,X]).

?- test(X).
X = a ;
diff([X], [a])

Las dos respuestas anteriores básicamente dicen que X = a o ~(X = a) que en la mayoría de las lógicas es lo mismo que una respuesta única.

Necesitaría un intérprete de Prolog, que en algunos puntos trabaja orientado. Y tal vez algunos operadores que forzarían un procesamiento orientado a conjuntos. Pero podría romper el código tradicional de Prolog. Probablemente no solo puede colarse definiciones totalmente declarativas en el código que se basó en definiciones no tan declarativas.

Adiós