Saltar para o conteúdo

Prolog/Comando Cut

Origem: Wikilivros, livros abertos por um mundo aberto.

O comando cut permite indicar ao Prolog quais sub-objetivos já satisfeitos não necessitam ser reconsiderados ao se realizar um backtracking. Isto é, ele aborta o processo de backtracking. O uso do comando cut é importante porque permite que o programa rode mais rápido, sem perder tempo com sub-objetivos que não contribuem para determinar a resposta do objetivo principal. Além disso, o programa ocupará menos memória, pois não será necessário armazenar todos os sub-objetivos considerados (pontos do backtracking). Em alguns casos, o cut evita que o programa entre em laço infinito.

cabeça :- objetivo1, ..., objetivon, !, objetivon+1, ..., objetivon+m

Exemplo (o código abaixo faz a consulta ao banco e para na primeira ocorrência de filho do sexo masculino):

primogenito(X,Y) :- pai(Y,X), masculino(X), !

Um exemplo um pouco mais complicado do uso do cut pode ser visto através do exemplo abaixo:

 f1(X) :- !, a(X), b(X).
 f2(X) :- a(X), !, b(X).
 f3(X) :- a(X), b(X), !.
 a(1).
 a(3).
 a(5).
 a(7).
 b(2).
 b(3).
 b(6).
 b(7).

É imediato verificar que fN() (em que N = 1, 2 ou 3) será verdadeiro ao entrar com os valores 3 ou 7 (e apenas com esses), mas o que ocorre com os comandos abaixo?

 f1(X).
 f2(Y).
 f3(Z).

Em f1(X), o cut não faz nada, já que antes do cut não existe nada.

Em f2(X), após obter-se sucesso com a(1), o cut impede o backtracking, então a falha em b(1) faz com que nenhum valor de X consiga satisfazer f2(X).

Em f3(X), o sucesso de a(1) seguido da falha em b(1) ocorrem antes do cut. O próximo valor que satisfaz a(X) é X=3, e com o sucesso de b(3) obtemos o primeiro valor de f3(X). O cut final interrompe a busca por novos valores.

Outro exemplo:

 g0(X) :- a(X), b(X).
 g0(X) :- c(X).
 g1(X) :- !, a(X), b(X).
 g1(X) :- c(X).
 g2(X) :- a(X), !, b(X).
 g2(X) :- c(X).
 g3(X) :- a(X), b(X), !.
 g3(X) :- c(X).
 a(1).
 a(3).
 a(5).
 a(7).
 b(2).
 b(3).
 b(6).
 b(7).
 c(4).
 c(5).
 c(6).
 c(7).

É simples ver que g0(X) retornará, sucessivamente, os valores 3, 7 (correspondentes à primeira instrução, g0(X) :- a(X), b(X).), 4, 5, 6 e (de novo) 7 (correspondentes à segunda instrução, g0(X) :- c(X). O efeito do cut em g1, g2 e g3, porém, é impedir que após qualquer sucesso, antes do cut, na primeira instrução, a segunda instrução seja executada.

Ou seja, g1(X), g2(X) e g3(X) se comportarão exatamente da mesma forma que, respectivamente, f1(X), f2(X) e f3(X).

No entanto, ao entrar com um valor fixo do argumento, o comportamento de g1, g2 e g3 serão diferentes.

Em g1(4), por causa do cut antes de qualquer instrução, a segunda instrução (g1(X) :- c(X).) será completamente ignorada. Ou seja, g1(4) falha (porque g1(4) :- !, a(4), b(4). tem um sucesso antes do cut e falha logo após).

Por outro lado, g2(4) será um sucesso, mas g2(5) será um fracasso (por causa do sucesso em a(5), antes do cut, seguido do fracasso em b(5)).

Finalmente, g3 será um sucesso para 3, 4, 5, 6 e 7.