LIK320 / Prolog



Lingwistyka komputerowa 320
Programowanie w Prologu - powtórzenie
Ćwiczenia 3
Kłopoty z rekurencją
rekurencja lewostronna
Mechanizm prologowy napotyka kłopoty z realizacją reguł z rekurencją
lewostronną. Z rekurencją lewostronną mamy do czynienia
wtedy, kiedy ten sam predykat występuje w głowie reguły i w pierwszym podcelu
ciała. Przykład (patrz też zadanie 1): rodzeństwo(piotr, paweł).
rodzeństwo(A, B):- rodzeństwo(B, A).

Podanie celu niezgodnego z bazą, np. rodzeństwo(marek, X), spowoduje
zapętlenie programu.
Przykładowe rozwiązanie:rodzeństwo1(piotr, paweł).
rodzeństwo(A, B):- rodzeństwo1(A, B).
rodzeństwo(A, B):- rodzeństwo1(B, A).

stosowanie akumulatora
Efektywniejszą metodą stosowania rekurencji w programach arytmetycznych jest
użycie konstrukcji z akumulatorem. Odpowiada to zastąpieniu rekurencji iteracją,
np. zamiast następującego programu:silnia(1, 1) :- !.
silnia(N, Wynik) :-
N1 is N - 1,
silnia(N1, Wynik1),
Wynik is N * Wynik1.

można użyć programu:silnia(N, Wynik) :-
silnia_z_akumulatorem_i_licznikiem(N, 1, 1, Wynik).

silnia_z_akumulatorem_i_licznikiem(N, N, Wynik, Wynik) :- !.

silnia_z_akumulatorem_i_licznikiem(N, L, A, Wynik) :-
L1 is L+1,
A1 is A*L1,
silnia_z_akumulatorem_i_licznikiem(N, L1, A1, Wynik).

Drugi argument predykatu silnia_z_akumulatorem_i_licznikiem pełni
funkcję licznika zliczającego liczbę wykonanych pętli (od 1
do N), trzeci argument to akumulator przechowujący
cząstkowy wynik, zaś czwarty argument służy do przekazania wyniku.
Najczęściej możliwe jest, by funkcję licznika pełnił jednocześnie argument
wejściowy - wtedy liczba argumentów zmniejsza się o jeden, np. dla silni:silnia(N, Wynik) :-
silnia_z_akumulatorem(N, 1, Wynik). /* (1) */

silnia_z_akumulatorem(1, A, A) :- !. /* (2) */

silnia_z_akumulatorem(N, A, Wynik) :- /* (3) */
N1 is N - 1,
A1 is A * N,
silnia_z_akumulatorem(N1, A1, Wynik).

Tym razem drugi argument pełni rolę akumulatora, trzeci
argument służy do przekazywania wyniku. Procedura silnia_z_akumulatorem
działa w ten sposób, że dla wywołania silnia_z_akumulatorem(N, A, W)
pod W zostanie podstawiona wartość wyrażenia N! * A. Przy
stosowaniu tej techniki musimy podać:

regułę wprowadzającą akumulator i ustalającą jego początkową wartość
(tutaj klauzula (1)),
regułę kończącą iterację (tutaj: (2))
regułę dokonującą obliczenia kolejnej wartości akumulatora (tutaj: (3)).

Predykaty wejścia-wyjścia

nl - wypisanie znaku końca wiersza,
get0(-Char) - wczytanie znaku z klawiatury, zmienna
Char przyjmuje wartość kodu znaku (w ASCII),
get_single_char(-Char) - wczytanie znaku z klawiatury bez echa i
czekania na naciśnięcie klawisza Enter,
write(+Term) - wypisanie termu prologowego na standardowym
wyjściu,
read(-Term) - wczytanie termu prologowego ze standardowego
wejścia, uwaga: podawany term należy zakończyć kropką, a
następnie nacisnąć klawisz Enter.
Szczegółowe informacje na temat wszystkich predykatów wbudowanych dostępnych
w SWI-Prologu można znaleźć w podręczniku
do tego programu.
Stosowanie alternatywy
W Prologu dopuszczalne jest stosowanie alternatywy w celu uproszczenia zapisu
(jak również poprawienia działania mechanizmu wnioskowania). Do wyrażania
alternatywy służy operator ; (średnik). Następujące zapisy są
równoważne: A :- B.
A :- C.

orazA :- (B; C).

Predykat call
Predykat call służy do wywołania predykatu, który jest argumentem
innego predykatu. Przykład:pokaż_rozwiązanie(Cel) :- call(Cel).

?- pokaż_rozwiązanie(syn(X, henryk)).

Podanie powyższego celu spowoduje wykonanie celu syn(X, henryk).
Predykat repeat
Predykat repeat służy do wymuszenia poszukiwania kolejnych
rozwiązań. Jest to predykat, który zawsze się powodzi i wymusza "zmianę
kierunku" podczas nawracania. Przykład:/* czeka na naciśnięcie klawisza N lub T,
inne klawisze są pomijane */
potwierdzenie(X):-
repeat,
get_single_char(Odp),
((Odp = 78; Odp = 110), X = no;
(Odp = 84; Odp = 116), X = yes).

Przykład zastosowania predykatów call i repeat:sesja :-
repeat,
write('Podaj cel'), nl,
read(Cel), nl,
szukaj_wszystkie_rozw(Cel).

szukaj_wszystkie_rozw(Cel):-
call(Cel),
write('Znalezione rozwiązanie'), nl,
write(Cel), nl,
write('Czy podać następne?'), nl,
get(Odp), nl,
(Odp = 78; Odp = 110).

szukaj_wszystkie_rozw(_) :- write('Brak innych rozwiazan'), nl, fail.

Śledzenie działania mechanizmu wnioskowania
Poszukiwanie rozwiązań można śledzić poprzez podanie celu trace, a
następnie podanie celu, którego osiągnięcie chcemy śledzić. Kolejne kroki
obserwuje się naciskając klawisz Enter. Debugowanie można przerwać poprzez
naciśnięcie n (koniec śledzenia) lub a (przerwanie działania).
Cel notrace unieważnia cel trace. Można śledzić wybrane kroki
poprzez podanie celu spy(predykat). Wówczas program zatrzymuje
się przy napotkaniu podanego predykatu. Naciśnięcie l powoduje skok do
następnej realizacji predykatu.
Modyfikowanie bazy danych w trakcie działania programu
Do bazy danych można dołączyć nowe klauzule podczas wykonywania programu przy
pomocy polecenia asserta(+Klauzula) lub
assertz(+Klauzula). Różnica między nimi polega na tym, że
polecenie asserta umieszcza klauzule przed wszystkimi klauzulami
znajdującymi się już w bazie danych, natomiast assertz - za klauzulami.
Przykłady:asserta(ojciec(bronek, broncio)).
asserta(syn(X, Y):- ojciec(Y,X)).

Predykat retract(+Klauzula) powoduje usunięcie klauzuli z
bazy danych. Predykat abolish(+Predykat, +Arg) powoduje
usunięcie z bazy danych wszystkich klauzul opisujących Predykat o
arności (liczbie argumentów) Arg.
Zadania z ćwiczeń 3
Zadanie 1 Podać przykład opisu relacji przechodniej (np.
dwuargumentowej relacji przodek) z lewostronną rekurencją i bez
niej.
Zadanie 2 Zdefiniować rekurencyjnie predykat potęga(A, B, C),
gdzie C jest wynikiem potęgowania
AB. Zdefiniować ten sam predykat przy użyciu
konstrukcji z akumulatorem (z licznikiem lub bez).
Zadanie 3 Podane przykłady zastosowania instrukcji repeat
wykonać z zasłonięciem i bez zasłonięcia instrukcji repeat.
Zadanie 4 Sprawdzić na wybranej przez siebie bazie, czy zapisy a)
A :- B, C. A:- B, D. b) A:- B, (C; D) są równoważne (tzn., że
przy obu zapisach cel A jest spełniony dla tych samych warunków). Który z
zapisów jest efektywniejszy (tzn. wymaga mniej pracy od mechanizmu
wnioskowania)? Odpowiedź znaleźć, wykorzystując mechanizm śledzenia
wnioskowania.
Zadanie 5 Plik odmiana.pl zawiera
program-bazę danych form fleksyjnych rzeczowników męskożywotnych (rzeczowników
męskich oznaczających zwierzęta, uwaga: program nie zawsze generuje poprawne
formy).

sprawdzić działanie programu, ustawić formę celownika liczby pojedynczej
rzeczownika 'kot' na 'kotu' (zamiast 'kotowi'), ustawić poprawny temat dla
rzeczowników 'lew' i 'paw',
zmodyfikować program, tak aby poprawnie były generowane formy narzędnika
liczby pojedynczej dla 'rak' i innych rzeczowników zakończonych na 'k'
('rakiem' zamiast 'rakem'),
rozszerzyć program o opcje 'a - dodaj wyjątek-formę alternatywną', np. dla
rzeczownika 'osioł' oprócz regularnej formy 'osłowi' celownikiem liczby
pojedynczej może być 'osłu', zmodyfikować procedurę wykonaj(102), tak
aby wypisywała ona wszystkie formy fleksyjne (jeśli jest ich więcej niż
jedna).
Zadanie A Na podstawie pliku baza_dan.pl napisać
swoją bazę danych, np. bazę danych samochodów lub rozbudować bazę danych z
przykładu o dodatkowe operacje.
Zadanie 6 Na podstawie pliku alkohol.pl napisać
podobny program typu "zgadywanka", np. "Twoja ulubiona książka".
Zadanie B (dodatkowe) Podać a) predykat dwuargumentowy obliczający
n-tą liczbę ciągu Fibbonacciego, b) predykat wykonujący to samo zadanie z
licznikiem i akumulatorem.