Ćwiczenia laboratoryjne:
Programowanie deklaratywne
Katedra Sztucznej Inteligencji
Instytut Informatyki
Wydział Nauk Ścisłych
Akademia Podlaska
Ćwiczenie laboratoryjne Nr 1-2
WPROWADZENIE DO PROGRAMOWANIA
W ŚRODOWISKU SWI PROLOG
Autor: dr inż. Jerzy Tchórzewski, jtchorzewski@interia.pl
Cel ćwiczenia
Poznanie podstaw języka PROLOG jako języka programowania logicznego oraz środowiska SWI Prolog jako środowiska programowania w logice:
Nazwa PRPLOG: PROgrammation en LOGique,
PROgramming in LOGic),
PROgramowanie LOGiczne
Historia języka: język programowania oparty na logice matematycznej oraz metalogice. Naukę logiki wprowadzili starożytni Grecy, którzy przeprowadzali dedukcję, czyli na podstawie prawdziwych stwierdzeń (przesłanek) wyprowadzali prawdziwe wnioski (konkluzje). Były więc fakty i reguły wyprowadzania nowych faktów. Reguły powinny być niezmienne. Powszechnie znaną regułą był sylogizm. Na podstawie reguły sylogizmu zakładając prawdziwość przesłanek można stwierdzić, że wniosek jest prawdziwy.
Przykład reguły sylogizmu: Przesłanka wszyscy ludzie są śmiertelni
Przesłanka X jest człowiekiem
Wniosek A zatem X jest śmiertelny
Na tej bazie rozwinęła się logika informatyczna, która znalazła liczne zastosowania w informatyce, od rozwoju systemów logicznych aż po programowanie w języku logiki. Przełom nastąpił wraz z rozwojem rachunku predykatów i w następstwie opracowania zagadnienia rezolucji przez Robinsona. Podstawy języka PROLOG opracował Kowalski na Uniwersytecie w Edynburgu. Następnie implementacji dokonali: Colmerauer na Uniwersytecie Aix-Marseille w 1972 roku oraz Warren na Uniwersytecie w Edynburgu w 1977 roku.
Współcześnie dostępnych jest szereg implementacji języka Prolog, jak na przykład: Jana Wielemaker-a SWI-Prolog, dostępny na stronie http://www.swi-prolog.org oraz Daniela Diaz-a GNU-Prolog, dostępny na stronie http://gnu-prolog.inria.fr. Na ćwiczeniach laboratoryjnych programowanie w języku Prolog będzie prowadzone w środowisku SWI PROLOG, którego podstawowym interfejsem jest powłoka. Uruchamianie powłoki w systemie Windows następuje w sposób klasyczny za pomocą ikony, menu, itp.
Podstawy Prologu
Język Prolog jest konwersacyjnym językiem opisowym i deklaratywnym. Programowanie w Prologu polega na opisywaniu znanych faktów i relacji dotyczących rozwiązywanego problemu, a algorytm sprowadzony jest do zapisu reguł wyprowadzania konkluzji na bazie prawdziwych przesłanek. Instrukcje sterujące ograniczone są do minimum. Programowanie w Prologu składa się z:
deklarowania faktów dotyczących obiektów i związków między nimi,
definiowania reguł dotyczących obiektów i związków między nimi,
zadawania pytań o obiekty i związki między nimi.
Elementy składniowe programu:
atomy: stałe znakowe,
niewiadome/szukane (tzw. zmienne logiczne),
termy: symbole funkcyjne przyjmujące argumenty.
Program składa się z:
szeregu klauzul (ang. clause), wyróżniamy: fakty (klauzule proste) i reguły (klauzule złożone),
oraz celu (ang. goal).
Uruchamianie programu polega na załadowaniu pliku z kodem w Prologu przy pomocy predykatu consult/1 (skrót [nazwa].), którą należy powtarzać po każdej modyfikacji kodu.
Programowanie w Prologu wymaga poznania:
metod strukturalizowania informacji, pojęcia termy,
rekurencji i unifikacji - mechanizmów dopasowywania wzorców.
rezolucji - metody wnioskowani logicznego,
strategii sterowania wnioskowaniem,
a więc zasad tworzenia systemów ekspertowych (doradczych).
Styl programowania w Prologu
Uwagi początkowe:
U1. Każda ,,linia kodu'' w Prologu musi się kończyć kropką.
U2. Prolog oczekuje wprowadzenia faktów i reguł.
U3. Po wprowadzeniu faktów i reguł (bazy wiedzy) Prolog będzie działał jak Maszyna Wnioskująca (MW) i może być systemem doradczym (ekspertowym) - odpowiadać na zadawane pytania.
U4. Należy sprawdzić działanie systemu pomocy predykatu help., a następnie przeczytać opis do predykatu consult/1. Następnie należy opuścić powłokę przez halt i ponownie ją uruchomić.
Ćwiczenie laboratoryjne 1.
Pierwszy program w Prologu pod tytułem ród. Na początku należy w edytorze Worda (lub innym) stworzyć trzypoziomowy schemat genologiczny swego rodu, wychodząc od pradziadków ojca i matki, a kończąc na ostatnich potomkach rodu. Następnie należy napisać w Prologu program do obsługi bazy wiedzy o rodzie wykorzystując następujący przykład:
Klasyczny przykład programu w Prologu o nazwie Rodzina
rodzic(kasia,robert).
rodzic(tomek,robert).
rodzic(tomek,eliza).
kobieta(kasia).
kobieta(eliza).
mezczyzna(tomek).
mezczyzna(robert).
Po napisaniu przy pomocy wybranego edytora tekstów własnego programu w Prologu należy go zapisać w pliku fam2.pl i wczytać w powłoce SWI:
?- [fam2].
Program po zintegrowaniu z zawartą już wiedzą istniejącej pierwotnie bazy wiedzy dostępnej z powłoki jest gotowy służyć wiedzą o naszej rodzinie jak nasz doradca (ekspert, system ekspertowej)wiedzy. Systemowi można zadawać pytania (cele, goal) do zrealizowania. Można to sprawdzić:
Kto jest kobietą?
?- kobieta(X).
Kto jest mężczyzną?
?- mezczyzna(X).
Czy tomek jest mężczyzną?
?- mezczyzna(tomek).
Czy reksio jest mężczyzną?
?- mezczyzna(reksio).
Czy kasia jest rodzicem robert?
?- rodzic(kasia,robert).
Czyim rodzicem jest kasia?
?- rodzic(kasia,X).
Czy zamiast X można wpisać inny symbol? Jaki?
Kto jest rodzicem robert?
?- rodzic(Y,robert).
Czy zamiast Y można wpisać inny symbol?
Kontynuacja ćwiczenia laboratoryjnego 1.
Należy rozbudować swój program o inne gałęzie rodów związanych ze swoim rodem (ciotki, wujka, swej żony, dziewczyny, itp.)w analogicznej (co do liczby osób i zależności) formie, kierując się wzorcem:
rodzic(kasia,robert).
rodzic(tomek,robert).
rodzic(tomek,eliza).
rodzic(robert,anna).
rodzic(robert,magda).
rodzic(magda,jan).
kobieta(kasia).
kobieta(eliza).
kobieta(magda).
kobieta(anna).
mezczyzna(tomek).
mezczyzna(robert).
mezczyzna(jan).
Czy kolejność wpisywania linii ma znaczenie?
UWAGA: aby dopisane fakty były dostępne dla Prologu, należy go ponownie wczytać!
Jeżeli koniunkcję celów oznaczamy przecinkiem, to jak zapytać kto jest matką, a kto ojcem roberta?
Należy ponadto spróbować dopisać do programu takie linijki:
famme(kasia).
homme(krzys).
parent(kasia,krzys).
Czy nazwa użytych symboli wpływa na działanie programu?
Jakie są ograniczenia na używane symbole?
Proszę dopisać też poniższe reguły i sprawdzić ich działanie.
matka(X,Y) :-
rodzic(X,Y),
kobieta(X).
ojciec(X,Y) :-
rodzic(X,Y),
mezczyzna(X).
Proszę zdefiniować reguły opisujące: brata, siostrę, dziadka i babcię.
Proszę dokładnie sprawdzić ich działanie.
Jaki pojawia się problem przy bracie/siostrze?
Uwaga na operator:\=
Proszę się zastanowić nad własnymi regułami opisującymi relacje w rodzinie (może są nietypowe?).
Rekurencja jest jednym z podstawowych mechanizmów programowania w Prologu. Proszę się przyjrzeć regułom opisującej przodka:
przodek(X,Y) :-
rodzic(X,Y).
przodek(X,Z) :-
rodzic(X,Y),
przodek(Y,Z).
Te dwie klauzule, w tym przypadku reguły, opisują dokładnie jeden predykat: przodek/2.
Jak zdefiniować potomka, krewnego?
Sprawdzić działanie systemu pomocy.
Sprawdzić działanie systemu pracy z linią poleceń (GNU Readline): historia, dopełnianie, skrótu klawiaturowe.
Należy następnie przejrzeć tryb pracy w GNU Emacs i edytorze PCE Emacs (uruchomić SWI Prolog przez xpce).
Sprawdzić działanie predykatu listing/0.
Sprawdzić działanie predykatu listing/1:
?- listing(rodzic).
W sytuacjach kiedy nie interesują nas wartości pewnych szukanych w predykacie, można też użyć tzw. szukanych anonimowych. Na przykład: ,,czy Robert ma rodziców?''
?- rodzic(_,robert).
Poprawny styl kodowania bardzo wpływa na przejrzystość programów w Prologu. Program w Prologu jest specyficzną reprezentacją wiedzy, powinien więc być zrozumiały dla osoby znającej jedynie notację (realcyjną) użytą w Prologu. Nie jest wymagana znajomość,,algorytmu'' czy ,,modelu'' (np. obiektowego) w celu zrozumienia programu, gdyż program jest bazą wiedzy, a Prolog jest maszyna wnioskującą.
Na zakończenie:
?- write('Hello world'), nl.
Literatura:
Ben-Ari M.: Logika matematyczna w informatyce. Klasyka informatyki. WNT. Warszawa 2005
Clocsin W.F., Mellish C.S.: Prolog. Programowanie w logice. Helion. Gliwice 2003
Hunter G.: Metalogika: wstęp do metateorii standardowej logiki pierwszego rzędu. PWN. Warszawa 1982
Murawski R., Świdrydowicz K.: Wstęp do teorii mnogości. WN UAM. Poznań 2005
Stanosz B.: Wprowadzenie do logiki formalnej. PWN. Warszawa 1999
Roy P.V., Haridi S.: Programowanie. Koncepcje, techniki i modele. Helion. Warszawa 2005
Tchórzewski J.: Programowanie deklaratywne. Cz. 1. Wykłady z programowania deklaratywnegoi. Cz. 2. Ćwiczenia laboratoryjne w SWI Prolog. Wyd. WPH. Siedlce (postać elektroniczna). Cz. 1 dostępna dla studentów kierunku informatyka w postaci prezentacji w Power Point. Ostatnia aktualizacja: wrzesień 2010. Cz. 2 dostępna w postaci instrukcji ćwiczeń laboratoryjnych w wersji z września 2010. Dla dyplomantów dostępne są obszerne fragmenty skryptu w wersji elektronicznej z 2008 (w trakcie końcowego przygotowania do druku, ostatnia aktualizacja: wrzesień 2010)
Wójcicki R.: Wykłady z logiki z elementami teorii wiedzy. WN Scholar. Warszawa 2003
UWAGA:
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub części w jakiejkolwiek postaci zabronione. Materiały przeznaczone są w chwili obecnej jedynie dla studentów kierunku informatyka na Wydziale Nauk Ścisłych Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach za zgodą autora.
Siedlce, wrzesień 2010
Rachunek predykatów jest rozszerzeniem rachunku zdań o symbole predykatowi interpretowane jako relacje w określonej dziedzinie. Predykat składa się z nagłówka i argumentów, na przykład: ojciec(tomasz, agata), gdzie ojciec to nagłówek a tomasz i agata to argumenty. Predykat może zostać użyty do wyrażenia pewnych faktów o świecie, które są znane programowi. W tym przypadku programista musi nadać im znaczenie. Jedną z interpretacji zdania ojciec(tomasz, agata) jest "tomasz to ojciec agaty". Jednak równie dobrze mogłoby to znaczyć "ojcem tomasza jest agata". Prolog nie ma pojęcia, co oznaczają te stwierdzenia. Wszystko co robi to manipulacja symbolami w oparciu o reguły. Dlatego można wybrać dowolny sposób zapisu tego, że "tomasz to ojciec agaty", pod warunkiem konsekwentnego przestrzegania kolejności argumentów w całym programie (Wykłady z Programowania deklaratywnego) [7].
Programowanie deklaratywne
Lab_1-2. Wprowadzenie do programowania w środowisku SWI Prolog
Autor: dr inż. Jerzy Tchórzewski
-----------------------------------------------------------------------------------------------------------
1