Prolog que sont les accumulateurs et la fonction membre \ +

Question

J'ai cherché des didacticiels sur ce que sont les accumulateurs et ce qu'ils font, mais toutes les explications semblent être très compliquées et ne me donnent pas vraiment une image suffisamment claire de leur fonctionnement pour que je puisse les utiliser de celui-ci. Je semble comprendre que les accumulateurs s'accrochent à quelque chose comme un nombre qui peut ensuite être appelé par d'autres morceaux de code et changé. Le problème est que même si je comprends ce qu'est un accumulateur et que je sache quand j'en ai besoin, je ne sais pas trop comment l'utiliser.

Je veux dire d'après les tutoriels que j'ai vus, parfois l'accumulateur semble être une liste vide, tandis que d'autres fois, il semble être «0» me laissant me demander ce qui peut être exactement considéré comme un accumulateur et ce qui ne peut pas. Quelqu'un peut-il m'expliquer en termes simples comment exactement un accumulateur peut être utilisé?

Également pour la deuxième partie de ma question, il me semble avoir remarqué que des gens l'utilisaient beaucoup dans leurs codes de prologue:

\+member

J'ai réussi à déduire que cela a quelque chose à voir avec les listes car je le vois toujours être utilisé dans une ligne de code qui fait quelque chose à une liste, mais après avoir cherché autour de moi, j'ai trouvé que ce que signifie + membre est " Négation comme échec - non prouvable "même si je ne comprends pas vraiment ce que cela signifie ou même si cette personne avait raison. Encore une fois, quelqu'un peut-il m'expliquer ce que fait exactement le + membre et à quoi il peut servir tout en essayant de garder votre explication simple, les gros mots me confondent xD.

Merci beaucoup pour toute aide concernant ces deux questions.

Answer 1

Premièrement, \+ est la négation d'un objectif. Il réussit, lorsque le but qui le suit échoue. Par exemple:

?- member(3, [1,2,3]). # 3 is a member of the List
true.

?- member(4, [1,2,3]). # 4 is not a member
false.

?- \+member(4, [1,2,3]). # succeeds, because 'member' fails
true.

?- \+member(3, [1,2,3]).
false.

?- atom_chars('hi', C).
C = [h, i].

?- atom_chars('hi', [h, i]).
true.

?- atom_chars('hello', [h, i]).
false.

?- \+atom_chars('hello', [h, i]).
true.

Deuxièmement, un accumulateur est un moyen d'enfiler un état via une récursivité, pour tirer parti de l'optimisation de la récursivité de queue.

Considérez ces deux méthodes équivalentes de calcul d'une factorielle:

?- [user].
|: fact_simple(0, 1).
|: fact_simple(N, F) :- 
         N1 is N-1, 
         fact_simple(N1, F1), 
         F is N*F1.
|: % user://2 compiled 0.00 sec, 440 bytes
true.

?- fact_simple(6, F).
F = 720 .

[user].
|: fact_acc(N, F) :- fact_acc(N, 1, F).
|: fact_acc(0, Acc, Acc).
|: fact_acc(N, Acc0, F) :- 
         N1 is N-1, 
         Acc is Acc0 * N, 
         fact_acc(N1, Acc, F).
|: % user://4 compiled 0.00 sec, 1,912 bytes
true.

?- fact_acc(6, F).
F = 720 .

La première version s'appelle juste dans la récursion, attend que le sous-appel se termine. alors seulement, il multiplie sa valeur N avec le résultat du sous-appel.

La deuxième version utilise à la place un accumulateur (Acc). Notez que 1 n'est pas l'accumulateur, mais sa valeur initiale. Après cela, chaque appel au prédicat multiplie sa valeur N avec l'accumulateur et lorsque la récursivité atteint son cas de base, la valeur de l'accumulateur est déjà la valeur finale.

La question n'est pas vraiment «que peut être l'accumulateur? (0 ou la liste vide ou quoi que ce soit). C'est juste un moyen d'accumuler des valeurs «au fur et à mesure» et de ne jamais revenir au prédicat appelant. De cette façon, le système Prolog n'a pas besoin de constituer une pile d'appels toujours croissante.

Notez cependant que dans cet exemple, l'ordre des multiplications est naturellement inversé. Cela n'a pas d'importance pour la multiplication, mais pour d'autres valeurs (comme les listes), il faut s'en occuper.

fact_simple faisait la multiplication en tant que 1 * 2 * 3 * 4 * 5 * 6, tandis que fact_acc l'avait comme 1 * 6 * 5 * 4 * 3 * 2. Si ce n'est pas clair, faites une trace des deux!