Mini guida Prolog – Parte VIII: il predicato predefinito “cut”

Assegnato un particolare goal, Prolog ricerca all’interno del proprio database in maniera sequenziale partendo dall’inizio le clausole la cui head unifica con il goal corrente. Se tali clausole non esistono allora il goal fallisce, altrimenti ne viene selezionata la prima (ma viene annotato il punto di scelta aperto) ed il sistema tenta di dimostrarne il relativo body. Come risultato della eventuale valutazione positiva del goal l’interprete fornisce all’utente tutte le sostituzioni che si sono rese necessarie nei diversi passi della risoluzione, rendendosi disponibile ad operare una riconsiderazione dei punti di scelta rimasti aperti (backtracking). Questo, in sintesi, il procedimento di dimostrazione Prolog.

Il meccanismo di backtracking, ovvero la riconsiderazione dei punti di scelta rimasti aperti durante la dimostrazione, è tuttavia una delle trappole più insidiose per chi (magari con poca esperienza e abituato a lavorare con linguaggi procedurali essenzialmente basati sulla logica if-then-else) si appresti a scrivere le clausole di una teoria Prolog.

Si consideri ad esempio il semplice problema delle determinazione del massimo tra due interi, che in Java sarebbe risolto dal seguente metodo:

public int max(int a,int b) {
    if(a > b)
        return(a);
    else
        return(b);
}

ed un suo primo (ma errato) corrispondente predicato max/3:

max(A,B,A) :- A > B.
max(A,B,B).

il quale è in grado di generare la risposta corretta per il goal:

?- max(1,2,X).

ma non per il goal:

?- max(2,1,X).

che infatti restituisce due diverse soluzioni X / 2 (corretta) e X / 1 (errata), poiché la seconda clausola del predicato max/3 viene comunque riconsiderata durante un backtracking.

Occorre infatti informare l’interprete del fatto che qualora A sia maggiore di B non deve essere presa in considerazione alcuna alternativa durante la valutazione del predicato corrente (e solo per il predicato corrente, non per l’intera risoluzione), e questo viene fatto utilizzando il predicato predefinito cut (rappresentato dal punto esclamativo ! in quasi tutte le implementazioni di Prolog):

max(A,B,A) :- A > B, !.
max(A,B,B).

Un analogo problema si pone durante la formulazione del calcolo del fattoriale, che infatti deve essere scritto come:

fact(0,1) :- !.
fact(N,X) :- M is N – 1, fact(M,Y), X is Y * N.

altrimenti si incorre in una ricorsione infinita.