Prolog: éviter les points de choix redondants (non déterministes) avec et sans opérateur de coupure

Question

Premièrement, j'ai lu tous les autres articles sur SO concernant l'utilisation des coupes dans Prolog et je vois clairement les problèmes liés à leur utilisation. Cependant, il y a encore un peu de clarté pour moi et j'aimerais régler cela une fois pour toutes.

Dans l'exemple trivial ci-dessous, nous parcourons récursivement une liste et vérifions si tous les 2 éléments sont égaux à un. Ce faisant, le processus récursif peut se retrouver dans l'un des cas de base suivants: soit une liste vide, soit une liste avec un seul élément.

base([]). 
base([_]). 
base([_,H|T]) :- H =:= 1, base(T). 

Lorsqu'il est exécuté:

?- time(base([1])). 
    % 0 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 0 Lips) 
    true ; 
    % 2 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 99502 Lips) 
    false. 

?- time(base([3,1,3])). 
    % 2 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 304044 Lips) 
    true ; 
    % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 122632 Lips) 
    false. 

Dans de telles situations, j'ai toujours utilisé un opérateur de coupe explicite dans le cas 2 de base (à savoir celui qui représente un élément gauche dans la liste) comme ci-dessous pour faire disparaître avec le point de choix redondant.

base([]). 
base([_]) :- !. 
base([_,H|T]) :- H =:= 1, base(T). 

Maintenant, nous obtenons:

?- time(base([1])). 
    % 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 49419 Lips) 
    true. 

?- time(base([3,1,3])). 
    % 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 388500 Lips) 
    true. 

Je comprends que le comportement de cette coupe est spécifique à la position de la règle et peut être considéré comme une mauvaise pratique.

Passant cependant, on peut repositionner les cas comme suit:

base([_,H|T]) :- H =:= 1, base(T). 
base([_]). 
base([]). 

qui aussi en finir avec le point de choix redondant sans utiliser une coupure, mais bien sûr, nous simplement décaler le point de choix requêtes avec des listes avec une quantité égale de chiffres comme ci-dessous:

?- time(base([3,1])). 
% 2 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 99157 Lips) 
true ; 
% 2 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 96632 Lips) 
false. 

Donc, ce n'est évidemment pas une solution non plus. Nous pourrions cependant adapter cet ordre de règles avec une coupe comme ci-dessous:

base([_,H|T]) :- H =:= 1, base(T), !. 
base([_]). 
base([]). 

car cela ne laisserait en fait aucun point de choix. En regardant certaines requêtes:

?- time(base([3])). 
% 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 157679 Lips) 
true. 

?- time(base([3,1])). 
% 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 138447 Lips) 
true. 

?- time(base([3,1,3])). 
% 3 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 393649 Lips) 
true. 

Cependant, encore une fois, ne fonctionne que le comportement de cette coupe correctement à cause de l'ordre des règles. Si quelqu'un repositionner les cas de base arrière à la forme originale, comme indiqué ci-dessous:

base([]). 
base([_]). 
base([_,H|T]) :- H =:= 1, base(T), !. 

nous toujours obtenir le comportement indésirable:

?- time(base([1])). 
    % 0 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 0 Lips) 
    true ; 
    % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 119546 Lips) 
    false. 

Dans ce genre de scénarios, j'ai toujours utilisé la seule coupe dans le second cas, je suis le seul à avoir lu mon code et je me suis habitué à ça. Cependant, on m'a dit dans une de mes réponses sur un autre post SO que ce n'est pas recommandé d'utiliser l'opérateur de coupe et que je devrais essayer de l'éviter autant que possible.

Cela me amène à ma question biparti:

• Si une coupe, quelle que soit la position de la règle dans laquelle il est présent, ne change comportement, mais pas la solution (comme dans les exemples ci-dessus), est-ce encore considéré comme une mauvaise pratique? Si je veux supprimer un point de choix redondant typique comme dans les exemples ci-dessus afin de rendre un prédicat complètement déterministe, y a-t-il une autre façon, recommandée, d'y parvenir plutôt que d'utiliser des coupes?

Merci d'avance!

Answer 1

toujours essayer difficile d'éviter !/0. Presque invariablement, !/0 détruit complètement la sémantique déclarative de votre programme.

Tout ce qui peut être exprimé par le modèle correspondant doit être exprimé par correspondance de motif. Dans votre exemple:

 
every_second([]). 
every_second([_|Ls]) :- 
     every_second_(Ls). 

every_second_([]). 
every_second_([1|Rest]) :- every_second(Rest). 

Comme dans votre version impure, aucun point de choix restent que ce soit pour les exemples que vous posté:

 
?- every_second([1]). 
true. 

?- every_second([3,1]). 
true. 

?- every_second([3,1,3]). 
true. 

Notez également que dans cette version, tous les prédicats sont complètement pur et utilisable dans tous   directions. La relation fonctionne aussi pour les plus   générale requête et génère réponses, tout comme nous attendons d'une relation logique:

 
?- every_second(Ls). 
Ls = [] ; 
Ls = [_G774] ; 
Ls = [_G774, 1] ; 
Ls = [_G774, 1, _G780] ; 
Ls = [_G774, 1, _G780, 1] . 

Aucune des versions vous avez publié peut le faire, en raison de l'impur ou non -déclaratifs prédicats (!/0, (=:=)/2) que vous utilisez! Lorsque vous raisonnez à propos de listes, vous pouvez presque toujours utiliser la correspondance de modèle seule pour distinguer les cas. Si cela n'est pas possible, utilisez par exemple if_/3 pour la pureté logique tout en conservant des performances acceptables.

Answer 2

L'astuce est « curryfication » sur nombre de unbounds dans la règle:

base([]). 
base([_|Q]) :- base2(Q). 

base2([]). 
base2([H|Q]) :- H =:= 1, base(Q). 

Cependant, il est une mauvaise règle de dire des coupes sont mauvaises. En fait, mon préféré sera:

base([]) :- !. 
base([_]) :- !. 
base([_,H|Q]) :- !, H =:= 1, base(Q). 

chose à propos de cet exemple de primes(++):

primes([5]). 
primes([7]). 
primes([11]). 

vs

primes([5]) :- !. 
primes([7]) :- !. 
primes([11]) :- !.