Prolog - różnice między cięciem czerwonym a zielonym krojem

Question

Zacząłem uczyć się prologu i chciałem, aby cale rzeczy były wyraźniejsze. Czytałem, że "zielone cięcie nie zmienia deklaratywnego znaczenia programu, natomiast czerwone cięcie". Ale znaczenie tego programu nie jest naprawdę czysto deklaratywne (tylko z faktu, że prolog faktycznie wycofuje się ze wszystkich opcji).

Oto przykład:

p(1). 
p(2) :- !. 
p(3). 

to zostało powiedziane, że jest to zielony cięty. Ale jeśli to uruchomię:

p(X), X =:= 3. 

Otrzymam "prawdziwy" bez cięcia i "fałszywy" z nacięciem. więc, za czym tęsknię?

Z góry dziękuję.

Answer 1

cięcie jest bardzo prosta do interpretacji operacyjnie, lub jeśli wolisz, proceduralnie. Ponieważ jednak większość literatury na temat programowania logicznego i Prologu ma tendencyjność do deklaratywnego znaczenia programów Prolog (z dobrych powodów), pojawiają się trudności w wyjaśnieniu cięcia. Jedną z prób naprawienia tego jest cięcie "kolorystyczne" w zależności od ich efektów.

Oto moja próba uczynienia wszystkiego jeszcze mniej jasnym.

Znaczenie operacyjny cięcia,

1. Od SWI-Prolog's reference manual. „Odrzuć wszystkie punkty wybór utworzone od momentu wjazdu na orzeczenie, w którym pojawi się cut Innymi słowy, zobowiązać się do klauzuli, w której pojawia się cut i odrzucić punkty wyboru, które zostały utworzone przez cele po lewej stronie cięcia w obecnej klauzuli. "

2. Od "The Art of Prolog" by Sterling and Shapiro. "Celem uda i zobowiązuje Prolog do wszystkich dokonanych wyborów, ponieważ cel nadrzędny został zunifikowany z głową klauzuli cięcie występuje w [podkreślenie nie moje] Chociaż definicja ta jest kompletna i dokładne, jego konsekwencje i implikacje nie zawsze są intuicyjnie jasne lub oczywiste. "

3. Od "The Craft of Prolog" by O'Keefe. „[Cięcie] śliwki stos punktów wyboru tam, gdzie to było, gdy orzecznik który leksykalnie zawiera cięcie nazwano Innym sposobem powiedzenia to, że cięcie uda i zobowiązuje Prolog do Wszystkie wybory dokonane ponieważ cel nadrzędny nazwano [znowu nacisk nie kopalnię]”

proponuję przeczytać sekcje dotyczące cięcia i jego zastosowań przynajmniej z dwóch książek cytowanych powyżej. Z pewnością pomoże ci zrozumieć, co się właściwie dzieje.

Jedna powszechna dyskusja dotyczy różnicy pomiędzy znajdowaniem rozwiązań a odpowiedziami a dowodami. My (użytkownicy, programiści) zazwyczaj chcemy uzyskać odpowiedzi. Wynikiem oceny predykatów Prologu są rozwiązania. Jednak to, czego faktycznie szuka Prolog, to proofów.

Aby wziąć przykład. Masz bazę danych p(1). p(2). p(3).. Teraz chcę zapytać Prolog „Czy istnieje p(X) taka, że ​​X =:= 3,

?- p(X), X =:= 3. 
X = 3. 

uzyskać pojedynczy rozwiązanie, X = 3 też uzyskać odpowiedź do Twojego pytania. Tak, istnieje taka p(X), a X oznacza 3, a są wyraźnie ma więcej odpowiedzi.

(Spróbuj zapytanie ?- p(X), X =:= 2.. Czy to zachowywać identycznie do oryginalnego zapytania?)

Dowód drzewa widać (w modzie) poprzez śledzenie zapytanie:

?- trace(p/1), trace(=:=). 
%   p/1: [call,redo,exit,fail] 
%   (=:=)/2: [call,redo,exit,fail] 
true. 

[debug] ?- p(X), X =:= 3. 
T Call: (7) p(_G1004) 
T Exit: (7) p(1) 
T Call: (7) 1=:=3 
T Fail: (7) 1=:=3 
T Redo: (7) p(_G1004) 
T Exit: (7) p(2) 
T Call: (7) 2=:=3 
T Fail: (7) 2=:=3 
T Redo: (7) p(_G1004) 
T Exit: (7) p(3) 
T Call: (7) 3=:=3 
T Exit: (7) 3=:=3 
X = 3. 

Zasadniczo, każdy z klauzulami p/1 się starał po kolei. Pierwsze dwa nie dają dowodu, ponieważ drugi subgoal koniunkcji się nie udaje. Wyszukiwanie dowodu jest kontynuowane za każdym razem od ostatniego punktu wyboru (następna klauzula p/1). Ten ostatni można udowodnić, a otrzymasz rozwiązanie i odpowiedź na zapytanie.

Teraz umieszczasz cięcie w ciele drugiej klauzuli p/1: p(1). p(2) :- !. p(3).. Mówisz Prologowi (pod względem definicji 3. od góry), "kiedy szukanie dowodu osiąga drugą klauzulę p/1, tej, która jednoczy swój argument z 2, przycina stos punktów wyboru do miejsca, w którym był, gdy p/1 nazywa." Po wywołaniu p/1 nie było punktów wyboru. Tak więc, gdy X =:= 3 zawiedzie, poszukiwanie dowodu jest kompletne, koniunkcja nie może zostać udowodniona, nie ma rozwiązań i nie otrzymujesz odpowiedzi.

(Spróbuj zapytanie ?- p(X), X =:= 2.. Czy jest identyczne do tego samego zapytania, kiedy nie ma cięcie?)

teraz do kolorach ..... W kontekście połączeniu p(X), X =:= 3., to wyciąć przycięte rozwiązanie i dowód. Nie dostałeś odpowiedzi, której się spodziewałeś. To cięcie jest czerwone.

Byłoby miło, gdybyśmy mogli powiedzieć Prologowi, że mamy na myśli cięcie w kolorze zielonym lub czerwonym (lub zielonym lub grue lub czerwonym lub niebieskim), ale Prolog nie pozwala nam tego zrobić. "Kolor" jest konsekwencją zamierzonego znaczenia programu (intencja programisty) i operacyjnych (proceduralnych) efektów cięcia.

Ale naprawdę, spróbuj zdobyć książkę i przeczytaj sekcję o cięciach. A może nawet dwie książki.