SE/LS/L4
From WikiZMSI
Spis treści |
Operator odcinania
Odcinanie oznaczane jest znakiem:
!
Jest operatorem do kontrolowania nawracania w Prologu. Dzięki jego umiejętnemu wykorzystaniu można zwiększyć efektywność kodu poprzez zmniejszenie liczby sprawdzanych warunków.
Zadania prezentujące zastosowania operatora !:
1. Napisać predykat funkcja/2, który nie zawiedzie, gdy pierwszy argument X i drugi argument Y przyjmą wartości opisane warunkami:
- Jeżeli X <3, to Y = 0.
- Jeżeli X ≥ 3 i X < 6, to Y = 2.
- Jeżeli X ≥ 6, to Y = 4.
Zadać zapytanie:
funkcja(1,Y),Y > 2.
Jaki jest schemat odpowiedzi? Kiedy nastąpią nawroty? Wykorzystać polecenie trace, by prześledzić redo czyli nawroty.
2. W pliku Funkcja.pro znajduje się wersja programu rozwiązująca zadanie 1 z wykorzystaniem operatora !. Zadać to samo zapytanie jak w punkcie 1 i sprawdzić jaka jest różnica w udzielanej odpowiedzi. Wykorzystać polecenie trace.
3. Aby zwiększyć optymalność kodu można zapisać źródło w postaci następujących reguł:
- Jeżeli X<3, to Y = 0.
- W przeciwnym przypadku, jeżeli X < 6, to Y = 2.
- W przeciwnym przypadku Y = 4.
Co doprowadza do źródła postaci: Funkcja_o.pro
4. Usunąć znaki odcięcia w kodzie w punktu 3 i zaobserwować jak w nowej wersji zachowywałby się predykat funkcja.
5. Dany jest program. Wykonać dla programu zadania:
5.1. Narysować drzewo zależności pomiędzy predykatami. W korzeniu:
top( X, Y)
a w liściach fakty.
5.2. Jaka będzie odpowiedź na pytanie
top( X, Y).
Ważne są wszystkie odpowiedzi i ich kolejność.
5.3. Używając trace zaznaczyć punkty nawrotów (redo) w drzewie. Ile jest nawrotów?
5.4. Zamienić
true(1)
na
!
Powtórzyć zadania z punktów 5.2. i 5.3. Jaki fragment drzewa został odcięty z przeszukiwania?
5.5. Zamienić
true(2)
na
!
Powtórzyć zadania z punktów 5.2. i 5.3. Jaki fragment drzewa został odcięty z przeszukiwania?
6. Napisać predykat max/3, który nie zawodzi, gdy trzeci argument jest większą z podanych w argumentach pierwszym i drugim liczb. Zastosować odcięcie. Co zmienia zastosowanie odcięcia?
7. Zdefiniować predykat element/2 sprawdzający, czy zadany element jest na liście. Stosując odcięcie powinniśmy zapewnić, że jak tylko rozwiązanie jest znalezione, to dalsze przeszukiwanie jest zbyteczne. Kiedy widać różnicę w działaniu wbudowanego predykatu member i zdefiniowanego w niniejszym zadaniu?
8. Zdefiniować predykat dodaj/3 dodający element na początku podanej listy. Predykat nie zawodzi, gdy 3 argument to lista zawierająca wynik połączenia. Dodanie powinno nastąpić tylko wówczas, gdy elementu nie ma jeszcze na liście, w przeciwnym wypadku jako wynik wyświetlamy listę zadaną. Stosując odcięcie powinno się zapewnić, że jak tylko sprawdzone zostanie, że element jest na liście, to dalsze przeszukiwanie jest zbyteczne. Porównać zachowanie predykatu dodaj/3 z operatorem i bez operatora odcięcia.
9. Wpisać polecenie w trybie zapytań
help(->).
W pliku Elseif.pro pokazane jest zastosowanie operatora ->.
Stosowanie negacji w Prologu
Negacja znana z rachunku zdań czy rachunku predykatów w Prologu nie występuje. Istnieje jednak operator
\+
który zdaje się działać podobnie. Działanie tego operatora jest oparte na wykorzystaniu operatora odcinania i wbudowanego predykatu fail/0.
Zadania prezentujące zastosowania operatora \+:
1. Przykład wykorzystania złączenia !,fail działającego podobnie do negacji. Predykat opisujący zdanie: Ala lubi wszystkie zwierzęta oprócz węży: dany jest w pliku Ala.pro. Zadać zapytania:
lubi(ala,waz). lubi(ala,kot).
2. Stosując !,fail jako negację zdefiniować predykat rozne/2, który nie zawodzi, gdy dwa elementy są różne.
3. Definicja operatora \+ dana jest w pliku Not.pro. Przeanalizować jego działanie. Wpisać polecenie w trybie zapytań
help(not).
Sugeruje się jednak stosowanie operatora \+.
4. Zmienić predykat z zadania 1 i 2 stosując operator \+ zamiast !,fail. Czy jest różnica w działaniu?
Problemy z zastosowaniem odcinania
Stosowanie operatorów ! i \+ ma plusy i minusy. Zaletą jest zwiększenie efektywności programu i możliwość stosowania reguł zależnych: jeżeli... w przeciwnym przypadku...
Zastosowanie operatora odcięcia zmienia logicznie (deklaratywnie) zdanie. np.:
p :- a, b. p :- c.
jest równoważne zdaniu:
p ⇔ (a &b) ∨ c.
Natomiast:
p :- a, !, b. p :- c.
co jest równoważne zapisowi:
p ⇔ (a &b) ∨ (~a & c).
Należy pamiętać, że negacje działają poprawnie tylko dla zunifikowanych zmiennych.
Przykład problemu wynikającego ze stosowania operatora \+ należy prześledzić wykorzystując plik z danymi: Rest.pro. Do pliku należy zadać zapytania:
wysoki_standard(X), polecana(X). polecana(X), wysoki_standard(X).
Jakie są odpowiedzi i dlaczego?
Zadanie domowe
Do przeczytania: W.F. Clocksin i C.S. Mellish. "Prolog. Programowanie." - Rozdział 4.
