Prolog Cosa sono gli accumulatori e la funzione membro +

Question

Ho cercato tutorial su ciò che sono gli accumulatori e su ciò che fanno, tuttavia tutte le spiegazioni sembrano essere molto troppo complicate e non mi danno un quadro abbastanza chiaro di come funzionano in modo da poterlo usare. Mi sembra di capire che gli accumulatori si aggrappano a qualcosa come un numero che può quindi essere chiamato da altri pezzi di codice e cambiati. Il problema è sebbene capisco cosa sia un accumulatore e so quando ne ho bisogno, non sono troppo sicuro di come usarlo effettivamente.

Intendo dai tutorial che ho visto, a volte l'accumulatore sembra essere un elenco vuoto, mentre altre volte sembra essere "0" lasciandomi chiedermi cosa può essere considerato esattamente un accumulatore e cosa non può. Qualcuno può spiegarmi in termini semplici come si può usare esattamente un accumulatore?

Anche per la seconda parte della mia domanda, mi sembra di aver notato persone che usano molto nei loro codici Prolog:

\+member

Sono riuscito a dedurre che ha qualcosa a che fare con gli elenchi poiché vedo sempre che è usato all'interno di una riga di codice che fa qualcosa in un elenco, tuttavia dopo aver cercato in giro ho scoperto che ciò che +membro significa effettivamente "negazione come fallimento - Non dimostrabile "Anche se non capisco davvero cosa significhi o anche se quella persona fosse corretta. Ancora una volta, qualcuno può spiegarmi cosa fa esattamente +membro e per cosa può essere usato mentre cerca di mantenere la tua spiegazione semplice e grandi parole confonami xD.

Grazie mille per qualsiasi aiuto riguardo a queste due questioni.

Answer 1

Primo, \+ è la negazione di un obiettivo. Ci riesce, quando l'obiettivo lo segue fallisce. Per esempio:

?- 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.

In secondo luogo, un accumulatore è un modo per infilare lo stato attraverso una ricorsione, per sfruttare l'ottimizzazione della ricorsione della coda.

Considera questi due modi equivalenti di calcolare un fattoriale:

?- [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 prima versione si chiama solo nella ricorsione, attende che la sottocall si completa. Solo allora moltiplica il suo N-Value con il risultato della subcall.

La seconda versione impiega invece un accumulatore (Acc). Notare che 1 non è l'accumulatore, ma è il valore iniziale. Dopodiché, ogni chiamata al predicato si moltiplica N-Value con l'accumulatore e quando la ricorsione raggiunge il caso di base il valore dell'accumulatore è già il valore finale.

La domanda non è davvero "Cosa può essere l'accumulatore? (0 o l'elenco vuoto o altro). È solo un modo per accumulare valori "mentre vai" e non tornare mai al predicato di chiamata. In questo modo, il sistema Prolog non deve costruire uno stack di chiamate in continua crescita.

Si noti, tuttavia, che in questo esempio l'ordine delle moltiplicazioni è naturalmente invertito. Non importa per la moltiplicazione, ma per altri valori (come elenchi), ci si deve occuparsi.

fact_simple ha fatto la moltiplicazione come 1 * 2 * 3 * 4 * 5 * 6, mentre fact_acc ce l'aveva come 1 * 6 * 5 * 4 * 3 * 2. Se non è chiaro, fai una traccia di entrambi!