Paradygmaty programowania/Wykład 13: Programowanie w logice w Prologu I

Dwa kolejne wykłady poświęcone będą programowaniu w logice, a praktycznie — językowi Prolog, który jest jedynym liczącym się reprezentantem tego paradygmatu. Zajmiemy się rezolucją, czyli metodą dowodzenia twierdzeń, która jest podstawą działania interpretera Prologu oraz charakterystycznymi dla Prologu mechanizmami, jak np. uzgadnianie (unifikacja) i ukonkretnianie zmiennych. Spodziewamy się, że Czytelnik zapoznał się już z przeglądowym wykładem na temat programowania w logice i że zna podstawy rachunku predykatów.

Wstęp

John McCarthy (1927-)
Zobacz biografię

Tak jak prezentacja języka Haskell była sposobem na zapoznanie się z programowaniem funkcyjnym, tak omówienie Prologu niechaj będzie metodą zaznajomienia się z programowaniem w logice.

Motywacja do powstania programowania w logice była po części podobna jak w przypadku programowania funkcyjnego: wykorzystanie logiki, a zatem formalizmu "starego jak świat", dobrze poznanego i ugruntowanego, przy jednoczesnym uniezależnieniu się od architektury von Neumanna. Spodziewano się ponadto, że ten sposób programowania będzie szczególnie odpowiedni do zastosowań typu sztucznej inteligencji. W latach 80-tych XX wieku wieszczono prawdziwą rewolucję; wydawało się, że np. komunikowanie się z komputerem w języku naturalnym jest w zasięgu ręki. Narzędziem tej rewolucji miał być Prolog...

Dzisiaj wiemy, że rewolucji nie było, a do swobodnego komunikowania się z komputerami w językach naturalnych wciąż jest nam daleko. Tym niemniej Prolog zdobył ważne miejsce nie tylko w historii informatyki, ale również w pewnych specyficznych dziedzinach związanych ze sztuczną inteligencją (choć i to określenie straciło sporo ze swojego dawnego blasku...). Co więcej, przyjrzenie się Prologowi pozwala lepiej zrozumieć np. związki programowania z logiką, a to zapewne przyda się każdemu programiście, nawet jeśli nigdy Prologu używał nie będzie.

Każdy, kto chciałby spróbować programowania w Prologu osobiście, może pobrać jedną z publicznie dostępnych wersji tego języka. Najbardziej chyba rozpowszechnioną jest SWI-Prolog, rozwijany cały czas pod patronatem Uniwersytetu w Amsterdamie. Wszelkie informacje i odnośniki można znaleźć na stronie [www.swi-prolog.org www.swi-prolog.org].

Przykłady, które będziemy podawali, będą zapisane w składni SWI-Prologu, która odpowiada standardom ISO i kontynuuje tradycję historycznego już DEC-Prologu opracowanego w Edynburgu w drugiej połowie lat 70-tych XX wieku. Nieco inna była składnia Prologu z Marsylii z pierwszej połowy lat 70-tych oraz różnych implementacji na małe komputery z lat 80-tych (np. micro-Prolog przypominał pod tym względem Lisp).

Od czego zacząć opisywanie Prologu?

Ci, którzy na programowanie w logice patrzą przede wszystkim jako na metodę automatycznego dowodzenia twierdzeń, zaczęliby zapewne od podstaw logicznych — rachunku predykatów na samym wstępie, a następnie rezolucji. Ponieważ jednak nasze podejście jest bardziej "programistyczne", a o rachunku predykatów w paru słowach mówiliśmy już w wykładzie przeglądowym, teraz zaczniemy od prologowych struktur danych i ich intuicyjnego rozumienia.

Jak wygląda program?

Przypomnijmy jeden z przykładów programu prologowego:

 lubi(jan, tatry).
 lubi(jan, beskidy).
 lubi(jerzy, beskidy).
 lubi(jerzy, bieszczady).
 lubi(józef, sudety).
 lubi(justyna, gświętokrzyskie).
 bratniadusza(X, Y) :- lubi(X, S), lubi(Y, S), X \= Y.

Ten program jest zupełnie „samowystarczalny” — nie potrzebujemy nigdzie dodatkowo deklarować, co to jest „lubi” bądź „bratniadusza”. Wszystko, co potrzeba do wykorzystania tego programu, już tu jest. Samo uruchomienie polega na wpisaniu celu; oto kilka przykładów, wraz z wynikami. Znaki „?-” są wypisywane przez interpreter:

 ?- lubi(jan, beskidy).
 Yes
 
 ?- lubi(jan, sudety).
 No
 
 ?- lubi(jan, X).
 X = tatry;
 X = beskidy;
 No
 
 ?- lubi(X, beskidy)
 X  = jan;
 X = jerzy;
 No
 
 ?- lubi(X, Y).
 X = jan, Y = tatry;
 X = jan, Y = beskidy;
 X = jerzy, Y = beskidy;
 X = jerzy, Y = bieszczady;
 X = józef, Y = sudety;
 X = justyna, Y = gświętokrzyskie;
 No
 
 ?- lubi(filip, tatry).
 No
 
 ?- lubi(filip, X).
 No

Cel może być albo „konkretny”, albo może zawierać zmienne. W pierwszym przypadku interpreter odpowiada po prostu „tak” lub „nie”, w zależności od tego, czy udało mu się znaleźć potwierdzenie wpisanego celu. W drugim przypadku interpreter znajduje wszystkie możliwości spełnienia wpisanej relacji (po czym odpowiada „nie” — co oznacza, że nie ma już więcej rozwiązań). Zauważmy, że odpowiedź przecząca oznacza, że interpreter nic nie wie na żądany temat — a nie że potrafi udowodnić fałszywość wpisanego celu. Innymi słowy, Prolog działa przy założeniu, że mamy „zamknięty świat”, o którym wiemy wszystko; to, czego nie wiemy, nie istnieje...

Uwaga techniczna: możemy pytać o byty, o których wcześniej nie wspomnieliśmy ani słowem. Tak jest np. w pytaniu lubi(filip, tatry). Wbrew pozorom, nie zawsze uzyskamy wtedy odpowiedź „nie”. Możemy otrzymać odpowiedź twierdzącą, jeśli wynika to z mniej szczegółowych stwierdzeń programu. Do tej kwestii będziemy wracali parokrotnie.

Druga uwaga techniczna: nazwy zmiennych we wpisanym celu nie mają nic wspólnego z ewentualnymi nazwami zmiennych w programie.

Powyższe przykłady celów i odpowiedzi pokazują, że można zapytać o dowolny fragment relacji, a interpreter spróbuje dopasować (ściślej mówimy uzgodnić lub zunifikować; dopasowanie to właściwie techniczny sposób dokonania uzgodnienia) wartości zmiennych tak, by uzyskać stwierdzenia zgodne z posiadanym stanem wiedzy (czyli stwierdzeniami w programie). Wszystkie te przykłady były jednak ograniczone do pytań, które dało się rozstrzygnąć przez pojedyncze dopasowanie celu do stwierdzeń w programie. Prolog jest oczywiście znacznie bardziej zręczny i potrafi udowodnić stwierdzenia, które wymagają uzgodnień w wielu etapach. Przykładowo:

 ?- bratniadusza(jan, jerzy).
 Yes
 
 ?- bratniadusza(jan, józef).
 No
 
 ?- bratniadusza(jan, X).
 X = jerzy;
 No
 
 ?- bratniadusza(X, Y).
 X = jan, Y = jerzy;
 X = jerzy, Y = jan;
 No

Sposób, w jaki interpreter Prologu poszukuje odpowiedzi na tak postawione pytania, był przedstawiony w wykładzie przeglądowym. Do szczegółów tego procesu będziemy oczywiście wracali, teraz natomiast zastanówmy się, jaka jest rola stwierdzeń w programie, które zawierają zmienne. Otóż możemy je traktować tak, jak gdyby stał przed nimi kwantyfikator uniwersalny wiążący wszystkie owe zmienne. Dzięki temu stwierdzenie:

 bratniadusza(X, Y) :- lubi(X, S), lubi(Y, S), X \= Y.

staje się regułą, na podstawie której interpreter może wnioskować o „byciu bratnią duszą”.

Jak rozumieć klauzule?

Tym samym dochodzimy do kwestii interpretacji stwierdzeń w programie prologowym.

Przypomnijmy, że klauzula złożona z pojedynczej struktury prologowej to stwierdzenie, które przyjmujemy za fakt, np. lubi(jan, tatry). Zwróćmy uwagę, że występujące w tej klauzuli atomy — lubi, jan i tatry — nie mają tu żadnego innego znaczenia niż powiązanie ich w taką właśnie klauzulę, która następnie może być wykorzystana przy poszukiwaniu odpowiedzi przez interpreter. Innymi słowy, atomy oznaczają po prostu siebie i dopóki nie użyjemy ich w jakimś konkretnym kontekście (np. w operacji arytmetycznej), nie wymagamy od nich żadnych własności. Oczywiście intuicyjne rozumienie takiej klauzuli-faktu to stwierdzenie, że „Jan lubi Tatry”, czyli że podane w nawiasach obiekty spełniają relację podaną na początku. A zatem funktor (lubi) spełnia rolę nazwy relacji, zaś atomy-parametry (jan, tatry) — rolę elementów tę relację spełniających. Zamiast atomów mogą pojawiać się stałe liczbowe lub napisowe oraz całe struktury (o czym będzie za chwilę).

Drugi typ klauzul to klauzule postaci $B:-A_{1},A_{2},\ldots ,A_{m}$, takie jak podana chwilę wcześniej reguła „bycia bratnią duszą”. Klauzule tego rodzaju prawie zawsze zawierają zmienne. Ich czysto logiczne znaczenie to implikacja, w której zmienne są związane kwantyfikatorem uniwersalnym, czyli w tym przykładzie:

 $\forall X,Y,S:[{\text{lubi}}(X,S)\wedge {\text{lubi}}(Y,S)\wedge X\neq Y\Rightarrow {\text{bratniadusza}}(X,Y)]$.

W praktyce klauzulę taką rozumiemy jako definicję nowej relacji — nie poprzez wyliczenie obiektów ją spełniających, lecz poprzez określenie reguły wiążącej ją z innymi relacjami. W trakcie poszukiwania odpowiedzi interpreter może wykorzystać taką klauzulę, uzgadniając odpowiednio zmienne.

W jakiej roli występują struktury?

Przypomnijmy najpierw kilka definicji:

• Struktura to twór postaci funktor(listaParametrów), gdzie parametry są atomami, zmiennymi lub innymi strukturami, rozdzielonymi przecinkami.
• Term to stała, zmienna lub struktura.
• Stała może być atomem (składnia — jak typowy identyfikator zaczynający się od małej litery lub napis ujęty w apostrofy) lub liczbą. System typów Prologu jest niezbyt rozbudowany i zazwyczaj obejmuje liczby całkowite, zmiennopozycyjne oraz napisy, przy czym napisy w podwójnych cudzysłowach utożsamiane są z listą kodów znaków, zaś napisy w apostrofach — z atomami.
• Nazwy zmiennych zaczynają się od dużej litery.

Struktury mogą występować zarówno w roli danych, jak i w roli zbliżonej do funkcji w klasycznych językach programowania. W rozważanym dotychczas przykładzie struktury z funktorem lubi uznalibyśmy zapewne za dane, natomiast strukturę z funktorem bratniadusza — za coś w rodzaju funkcji. Podział ten jest jednak sztuczny i bierze się po prostu z naszych przyzwyczajeń. Prolog traktuje wszystkie struktury tak samo, wykorzystując je w uzgodnieniach. Zauważmy, że do naszego programu moglibyśmy dodać klauzulę:

 lubi(_, pieniny).

Można ją interpretować jako stwierdzenie, że wszyscy lubią Pieniny. W tej sytuacji funktor lubi przestaje oznaczać tylko dane... Zauważmy, że taka klauzula pozwala interpreterowi odpowiedzieć twierdząco np. na poniższe pytania:

 lubi(X, pieniny).
 lubi(filip, pieniny).
 lubi(filip, _).

Również pytając

 lubi(filip, X).

dostaniemy sensowną odpowiedź: X = pieniny.

Uwaga techniczna — jeśli jakaś zmienna występuje w klauzuli tylko raz, to należy ją zapisać jako zmienną anonimową, czyli znak podkreślenia. Taka sytuacja oznacza, że wartość tej zmiennej nie będzie potrzebna w żadnym innym miejscu. W szczególności dwa wystąpienia znaku podkreślenia oznaczają dwie zupełnie nie związane ze sobą zmienne anonimowe. Tak więc np. klauzula zna(X, X) oznacza „każdy zna samego siebie”, natomiast zna(_, _) — „każdy zna każdego”. Zmienna anonimowa użyta we wpisanym celu oznacza, że nie chcemy znać wartości, jakie interpreter nada tej zmiennej, próbując osiągnąć cel.

Powróćmy do kwestii reprezentowania danych przez struktury prologowe. Przykład struktur z funktorem lubi kojarzy nam się być może nie tyle z reprezentacją „obiektów pierwotnych” bazy danych (czyli, powiedzmy, rekordów w tabeli w relacyjnej bazie danych), co raczej z reprezentacją zależności między takimi obiektami. Popatrzmy więc na taki przykład:

 pracownik(imię(jan), nazwisko(kowalski), adres(ulica(długa), nr(2), miasto (kraków)),
           telefon(’0123456789’)).
 
 pracownik(imię(jerzy), nazwisko(nowak), adres(ulica(krótka), nr(123), miasto(kraków)),
           telefon(’0987654321’)).

Użyliśmy tu zagnieżdżonych struktur do reprezentacji danych pracowników. W potocznym rozumieniu owi pracownicy są „obiektami pierwotnymi”. Zauważmy jednak, że w Prologu sposób reprezentowania jest w obydwu przypadkach w istocie taki sam.

Reprezentacja taka jak powyżej daje nam możliwości podobne do rekordów przy znacznie większej elastyczności. Przyjrzyjmy się ponownie pracownikom:

• Funktor pracownik użyty jest w roli podobnej do nazwy typu.
• Funktory imię, nazwisko itp. spełniają rolę analogiczną do pól rekordu.
• Atomy i liczby zachowują się jak wartości pól.

Mamy tu obiekty (pracowników) opisane w sposób samoistny — bez odwoływania się do zewnętrznych definicji typów. Mechanizm ten, chociaż nie pozwala np. na statyczne sprawdzenie zgodności typu, ma cechy przyzwoitego typowania. Otóż wszelkie wykorzystanie takich obiektów musi następować przez uzgodnienie, a żeby ono się powiodło, konieczna jest pełna zgodność struktur (nazwy, arności i podstruktury). Dodajmy, że atomy można traktować jako funktory zeroargumentowe.

Zmienne i ich ukonkretnianie

Zmienne w Prologu są zupełnie odmienne od zmiennych w językach imperatywnych i tylko trochę podobne do zmiennych w językach funkcyjnych. Owo podobieństwo polega na tym, że zmienna prologowa nie może dowolnie zmieniać wartości tak, jak się to dzieje przy podstawieniach — tych zresztą w ogóle w Prologu nie ma. W Prologu nadawanie wartości zmiennym następuje w wyniku uzgodnień; będziemy o nich mówili obszerniej w drugiej części wykładu.

Ukonkretnianie zmiennych

Zmienna w programie prologowym reprezentuje zupełnie nieokreślony byt, bez typu. W trakcie obliczeń, w rezultacie uzgodnień następuje ukonkretnianie zmiennej, czyli bliższe określenie bytu reprezentowanego przez zmienną. Ów byt będziemy nazywali konkretyzacją zmiennej.

Ukonkretnienie może być całkowite — zmienna utożsamia się wówczas z termem niezawierającym zmiennych i nie podlega dalszemu ukonkretnianiu. W tym momencie można ją postrzegać jak zainstancjonowaną zmienną w programie funkcyjnym. Ukonkretnienie może jednak być tylko częściowe — zmienna reprezentuje wtedy term, który wciąż zawiera inne zmienne, i może być ukonkretniana dalej.

Ciekawym przypadkiem jest ukonkretnienie, które następuje przy uzgadnianiu dwóch dotychczas nieukonkretnionych zmiennych. Nie pojawia się wtedy żaden bardziej szczegółowy opis struktury reprezentowanej przez zmienną, gdyż obydwie zmienne na razie reprezentują byty nieokreślone. Dwie zmienne zostają natomiast utożsamione, czyli odtąd każde wystąpienie i ukonkretnienie jednej z nich odnosi się tak samo do drugiej.

Ukonkretnienie zmiennej nie może zostać zmienione na inne, może natomiast zostać anulowane w wyniku nawrotu. Generalnie odnosi się to do ostatniego etapu ukonkretnienia — zmienna wraca do poprzedniej konkretyzacji, a nie do stanu całkowicie nie ukonkretnionego. Tu ponownie odsyłamy Czytelnika do drugiej części wykładu.

Przykłady ukonkretniania

Rozważmy teraz parę przykładów ukonkretnienia.

Przykład pierwszy: mamy dotychczasowy program „górski” i wpisujemy cel bratniadusza(jan, X). W pierwszym etapie następuje dopasowanie owego celu do definicji bratniadusza(X, Y), co skutkuje dwoma uzgodnieniami:

• Atom jan zostaje dopasowany do zmiennej X z definicji. W rezultacie zmienna X zostaje ukonkretniona do wartości jan.
• Zmienna X z celu zostaje uzgodniona ze zmienną Y z definicji. W rezultacie powstaje jedna zmienna.
• Oczywiście zmienna X, której konkretyzacją jest atom jan, nie ma nic wspólnego z tą drugą.

Przykład drugi: mamy w programie opisanych wcześniej pracowników i wpisujemy cel pracownik(X, Y, Z, telefon(’0123456789’)). Cel pasuje do definicji jednego, konkretnego pracownika, a zatem mamy trzy uzgodnienia z następującymi skutkami:

• Zmienna X zostaje ukonkretniona do imię(jan).
• Zmienna Y zostaje ukonkretniona do nazwisko(kowalski).
• Zmienna Z zostaje ukonkretniona do adres(ulica(długa), nr(2), miasto(kraków)).

Zauważmy, że wartościami zmiennych stają się tu całe struktury, a nie pojedyncze atomy. Druga obserwacja to to, że interpretera Prologu można użyć wprost jako mechanizmu wyszukiwania w bazie danych — podajemy znane elementy (tu: telefon), a interpreter znajduje wszystkie pasujące „rekordy”.

Przykład trzeci: ponownie mamy bazę pracowników; wpisujemy cel pracownik(imię(X), nazwisko(Y), adres(A1, A2, A3), telefon(Z)). Tym razem cel pasuje do obydwu pracowników, więc mamy jeden zestaw ukonkretnień, nawrót (a więc anulowanie ukonkretnień) i drugi zestaw. Konkretyzacje zmiennych X, Y, A1, A2, A3 i Z w poszczególnych zestawach to oczywiście dane dwóch pracowników:

• X = jan, Y = kowalski, A1 = ulica(długa), A2 = nr(2), A3 = miasto(kraków), Z = ’0123456789’.
• X = jerzy, Y = nowak, A1 = ulica(krótka), A2 = nr(123), A3 = miasto(kraków), Z = ’0987654321’.

W przypadku zmiennych X, Y i Z dotarliśmy tu już do atomów, natomiast w przypadku A1, A2 i A3 otrzymujemy struktury, gdyż na tym poziomie zagnieżdżenia odbyło się uzgodnienie.

Dwa ostatnie przykłady pokazują, że uzgodnienia mogą być na różnych poziomach zagnieżdżenia. Pozwala to zadawać pytania o różnym stopniu szczegółowości. Trzeba natomiast pamiętać, że zawsze należy przestrzegać arności funktora. A zatem niepoprawne, właśnie ze względu na niewłaściwą arność, są cele:

• pracownik(imię(X), nazwisko(Y), adres(A), telefon(Z)).
• pracownik(imię(X), nazwisko(Y), adres(A1, A2), telefon(Z)).