Prolog: evitare punti di scelta ridondanti (non determinismo) con e senza operatore di taglio

Question

In primo luogo, ho letto tutti gli altri post su SO relativi all'uso dei tagli in Prolog e sicuramente vedremo i problemi relativi al loro utilizzo. Tuttavia, c'è ancora un po 'di chiarezza per me e mi piacerebbe risolvere questo una volta per tutte.

Nell'esempio banale di seguito, ripetiamo ricorsivamente un elenco e controlliamo se ogni 2 ° elemento è uguale a uno. Nel fare ciò, il processo ricorsivo può finire in uno dei seguenti casi di base: rimane una lista vuota o una lista con un singolo elemento.

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

Quando eseguito:

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

In tali situazioni, ho sempre usato un operatore taglio esplicito nel caso 2a base (cioè quella che rappresenta un elemento di sinistra della tabella) come di seguito per eliminare con il punto di scelta ridondante.

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

Ora otteniamo:

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

Capisco che il comportamento di questo taglio è specifico per la posizione della regola e può essere considerato come cattiva pratica.

Passando tuttavia, si potrebbe riposizionare i casi come segue:

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

che sarebbe anche eliminare il punto scelta ridondante senza utilizzare un taglio, ma naturalmente, avremmo semplicemente spostare il punto di scelta per domande con elenchi con una quantità pari di cifre come di seguito:

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

Quindi, ovviamente, non è nemmeno una soluzione. Potremmo tuttavia adattare questo ordine di regole con un taglio come segue:

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

poiché in questo modo non sarebbero presenti punti di scelta. Alcune domande:

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

Tuttavia, ancora una volta, il comportamento di questo taglio funziona correttamente solo a causa dell'ordine delle regole. Se qualcuno riposizionare i casi di base torna alla forma originale come illustrato di seguito:

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

ci sarebbe ancora ottenere il comportamento indesiderato:

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

In questo genere di situazioni, ho sempre usato il singolo taglio nel secondo caso base, dato che sono l'unico ad aver letto il mio codice e mi sono abituato. Tuttavia, mi è stato detto in una delle mie risposte su un altro post SO che questo non è raccomandato dall'uso dell'operatore di taglio e che dovrei cercare di evitarlo il più possibile.

Questo mi porta alla mia domanda bipartita:

• Se un taglio, indipendentemente dalla posizione della norma in cui è presente, non cambia comportamento, ma non la soluzione(come negli esempi sopra), è ancora considerato una cattiva pratica?

• Se desidero eliminare un punto di scelta ridondante tipico come quello negli esempi sopra, al fine di rendere un predicato completamente deterministico, c'è qualche altro, consigliato, modo di realizzare questo piuttosto che usare i tagli?

Grazie in anticipo!

Answer 1

sempre si sforzano di evitare !/0. Quasi invariabilmente, !/0 distrugge completamente la semantica dichiarativa del tuo programma.

Tutto ciò che può essere espresso dal pattern matching dovrebbe essere espressa da pattern matching. Nel tuo esempio:

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

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

Come nella versione impura, senza punti di scelta restano di sorta per gli esempi in cui hai postato:

 
?- every_second([1]). 
true. 

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

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

Si noti inoltre che in questa versione, tutti i predicati sono completamente puro e fruibile in tutte le   indicazioni. La relazione funziona anche per il più   generale query e genera risposte, proprio come ci si aspetta da una relazione logica:

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

Nessuna delle versioni in cui hai postato può fare questo, a causa della impura o non -prediti dichiarativi (!/0, (=:=)/2) che usi!

Quando si ragiona sugli elenchi, è quasi sempre possibile utilizzare la corrispondenza del modello da solo per distinguere i casi. Se ciò non è possibile, utilizzare ad esempio if_/3 per la purezza logica mantenendo comunque prestazioni accettabili.

Answer 2

Il trucco è "accattivarsi" over numero di unbounds nella regola:

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

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

Tuttavia, si tratta di una cattiva regola per dire tagli sono cattivi. In realtà, il mio preferito sarà:

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

cosa su questo esempio di primes(++):

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

vs

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