Prolog Language
Monotoniczność

Rozumowanie o monotonicznych predykatach

Predykaty monotoniczne można debugować, stosując uzasadnienie deklaratywne .

W czystym Prologu błąd programowy może prowadzić do jednego lub wszystkich następujących zjawisk:

1. predykat nie powiedzie się poprawnie w przypadku, gdy powinien zawieść
2. predykat niepoprawnie zawiedzie w przypadku, gdy powinien się powieść
3. predykat nieoczekiwanie zapętla się, gdy powinien wygenerować tylko skończony zestaw odpowiedzi.

Jako przykład rozważmy, w jaki sposób możemy debugować przypadek (2) na podstawie deklaratywnego rozumowania: Możemy systematycznie usuwać cele klauzul predykatów i sprawdzać, czy zapytanie nadal nie powiedzie się. W kodzie monotonicznym usunięcie celów może co najwyżej uczynić wynikowy program bardziej ogólnym . Dlatego możemy wskazać błędy, sprawdzając, który z celów prowadzi do nieoczekiwanego niepowodzenia.

Przykłady monotonicznych predykatów

Przykładami monotonicznych predykatów są:

• unifikacja za pomocą (=)/2 lub unify_with_occurs_check/2
• dif/2 , wyrażając nierówność terminów
• Ograniczenia CLP (FD), takie jak (#=)/2 i (#>)/2 , przy użyciu monotonicznego trybu wykonywania.

Prolog przewiduje, że same cele monotoniczne są same w sobie monotoniczne.

Predykaty monotoniczne pozwalają na uzasadnienie deklaratywne:

1. Dodanie ograniczenia (tj. Celu) do zapytania może co najwyżej zmniejszyć , nigdy nie rozszerzać, zestaw rozwiązań.
2. Usunięcie celu takich predykatów może co najwyżej rozszerzyć , a nie zmniejszyć, zestaw rozwiązań.

Predykaty niemonotoniczne

Oto przykłady predykatów, które nie są monotoniczne:

• predykaty meta-logiczne, takie jak var/1 , integer/1 itd.
• porównania terminów, takie jak (@<)/2 i (@>=)/2
• predykaty, które używają !/0 , (\+)/1 i innych konstrukcji przełamujących monotoniczność
• predykaty wszystkich rozwiązań, takie jak findall/3 i setof/3 .

Jeśli te predykaty są używane, wówczas dodawanie celów może prowadzić do większej liczby rozwiązań, co jest sprzeczne z ważną deklaratywną właściwością znaną z logiki, że dodanie ograniczeń może co najwyżej zmniejszyć , nigdy nie rozszerzać, zestaw rozwiązań.

W konsekwencji inne właściwości, które polegamy na deklaratywnym debugowaniu i innych wnioskach, również są zepsute. Na przykład predykaty niemonotoniczne łamią podstawowe pojęcie przemienności koniunkcji znane z logiki pierwszego rzędu. Poniższy przykład ilustruje to:

?- var(X), X = a.
X = a.

?- X = a, var(X).
false.

Predykaty wszystkich rozwiązań, takie jak findall/3 również przełamują monotoniczność: dodawanie klauzul może prowadzić do niepowodzenia celów, które wcześniej miały . Jest to również sprzeczne z montonicznością znaną z logiki pierwszego rzędu, gdzie dodawanie faktów może co najwyżej wzrosnąć , nigdy nie zmniejszając zestawu konsekwencji.

Monotoniczne alternatywy dla niemonotonicznych konstruktów

Oto przykłady użycia w swoich programach predykatów monotonicznych zamiast nieczystych, niemonotonicznych konstrukcji:

• dif/2 ma być stosowany zamiast konstruktów niemonotonicznych, takich jak (\=)/2
• ograniczenia arytmetyczne (CLP (FD), CLP (Q) i inne) są przeznaczone do użycia zamiast zmodyfikowanych predykatów arytmetycznych
• !/0 prawie zawsze prowadzi do programów niemonotonicznych i należy tego całkowicie unikać .
• błędy tworzenia wystąpień można zgłaszać w sytuacjach, w których nie można w tej chwili podjąć właściwej decyzji.

Łącząc monotoniczność z wydajnością

Czasami argumentuje się, że ze względu na wydajność musimy zaakceptować stosowanie niemonotonicznych konstrukcji w rzeczywistych programach Prolog.

Nie ma na to dowodów. Ostatnie badania wskazują, że czysty monotoniczny podzbiór Prologu może być nie tylko wystarczający do wyrażenia większości programów w świecie rzeczywistym, ale także akceptowalnie skuteczny w praktyce. Konstrukcją, która została niedawno odkryta i zachęca do tego poglądu, jest if_/3 : Łączy monotoniczność z redukcją punktów wyboru. Zobacz Indeksowanie dif / 2 .

Na przykład kod formularza:

pred(L, Ls) :-
    condition(L),
    then(Ls).
pred(L, Ls) :-
    \+ condition(L),
    else(Ls).

Można zapisać za pomocą if_/3 jako:

pred(L, Ls) :-
    if_(condition(L),
        then(Ls),
        else(Ls)).

i łączy monotoniczność z determinizmem.