Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00059 006633 13243029 na godz. na dobę w sumie
Siedem języków w siedem tygodni. Praktyczny przewodnik nauki języków programowania - książka
Siedem języków w siedem tygodni. Praktyczny przewodnik nauki języków programowania - książka
Autor: Liczba stron: 368
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-3379-1 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> c - programowanie
Porównaj ceny (książka, ebook, audiobook).

Siedmiotygodniowa podróż po czterech odmiennych paradygmatach programowania, siedmiu różnych stylach składni i czterech dekadach rozwoju języków!

Jeśli myślisz, że to kolejna książka z serii 'Jak schudnąć 50 kilogramów w trzy dni' albo 'Jak zostać obrzydliwie bogatym w dwa tygodnie', na szczęście się mylisz! Oto podręcznik, który w siedem tygodni przedstawi Ci najważniejsze modele programowania na przykładzie siedmiu przydatnych języków. Zaproponowana tu innowacyjna forma nauki pozwoli Ci poznawać je dzień po dniu. Zaczniesz od krótkiego omówienia składni i możliwości każdego języka, by na końcu wypróbować go w akcji. I choć po lekturze tej książki nie staniesz się ekspertem, opanujesz to, co w każdym z przedstawionych tu języków jest kluczowe. Będziesz mógł tworzyć czytelniejszy, lepszy kod z mniejszą ilością powtórzeń. Zdobędziesz także niezwykle cenną umiejętność - zaczniesz sprawnie wykorzystywać pojęcia z jednego języka w celu znalezienia kreatywnych rozwiązań w innym!

W książce tej opisano jeden język programowania logicznego, dwa z pełną obsługą pojęć obiektowych, cztery o charakterze funkcyjnym i jeden prototypowy - wszystko po to, by zapewnić Ci możliwie najbardziej wszechstronne przygotowanie programistyczne. Lepiej przyswoisz sobie także techniki obsługi współbieżności, będące kręgosłupem następnej generacji aplikacji internetowych, oraz poznasz sposoby wykorzystywania filozofii 'Let it crash' Erlanga do budowy systemów odpornych na awarie.

Jakie praktyczne języki poznasz dzięki tej książce?

  1. Ruby - język obiektowy, a przy tym łatwy w użytkowaniu i czytelny
  2. Io - prototypowy język, wyposażony w unikatowy mechanizm dystrybucji komunikatów
  3. Prolog - język oferujący łatwe rozwiązania, które w Javie lub C byłyby bardzo kłopotliwe
  4. Scala - jeden z języków nowej generacji, przeznaczony na maszynę wirtualną Javy
  5. Erlang - język funkcyjny, z mechanizmami obsługi współbieżności, na którym działa już kilka słynnych baz danych w stylu cloud
  6. Clojure - język, w którym wykorzystano strategię wersjonowania baz danych w celu zarządzania współbieżnością
  7. Haskell - język o charakterze czysto funkcyjnym

Jeden z tych języków może już wkrótce stać się Twoim ulubionym narzędziem!


Bruce Tate - prowadzi w Austin, w stanie Teksas, firmę RapidRed, która zajmuje się tworzeniem aplikacji w Ruby. Jest autorem ponad dziesięciu podręczników informatycznych, wydawanych na całym świecie. Należą do nich From Java to Ruby, Deploying Rails Applications, Beyond Java oraz zdobywczyni prestiżowej nagrody Jolt - książka Better, Faster, Lighter Java.

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

Siedem języków w siedem tygodni. Praktyczny przewodnik nauki języków programowania Autor: Bruce A. Tate Tłumaczenie: Radosław Meryk ISBN: 978-83-246-3379-1 Tytuł oryginału: Seven Languages in Seven Weeks: A Pragmatic Guide to Learning Programming Languages Format: 168×237, stron: 368 Siedmiotygodniowa podróż po czterech odmiennych paradygmatach programowania, siedmiu różnych stylach składni i czterech dekadach rozwoju języków! • Poznaj najważniejsze modele programowania i techniki obsługi współbieżności • Opanuj tajniki systemu prototypów i dynamicznych typów • Zostań wszechstronnym programistą, gotowym zmierzyć się z każdym projektem! Jeśli myślisz, że to kolejna książka z serii „Jak schudnąć 50 kilogramów w trzy dni” albo „Jak zostać obrzydliwie bogatym w dwa tygodnie”, na szczęście się mylisz! Oto podręcznik, który w siedem tygodni przedstawi Ci najważniejsze modele programowania na przykładzie siedmiu przydatnych języków. Zaproponowana tu innowacyjna forma nauki pozwoli Ci poznawać je dzień po dniu. Zaczniesz od krótkiego omówienia składni i możliwości każdego języka, by na końcu wypróbować go w akcji. I choć po lekturze tej książki nie staniesz się ekspertem, opanujesz to, co w każdym z przedstawionych tu języków jest kluczowe. Będziesz mógł tworzyć czytelniejszy, lepszy kod z mniejszą ilością powtórzeń. Zdobędziesz także niezwykle cenną umiejętność – zaczniesz sprawnie wykorzystywać pojęcia z jednego języka w celu znalezienia kreatywnych rozwiązań w innym! W książce tej opisano jeden język programowania logicznego, dwa z pełną obsługą pojęć obiektowych, cztery o charakterze funkcyjnym i jeden prototypowy – wszystko po to, by zapewnić Ci możliwie najbardziej wszechstronne przygotowanie programistyczne. Lepiej przyswoisz sobie także techniki obsługi współbieżności, będące kręgosłupem następnej generacji aplikacji internetowych, oraz poznasz sposoby wykorzystywania filozofii „Let it crash” Erlanga do budowy systemów odpornych na awarie. Jakie praktyczne języki poznasz dzięki tej książce? • Ruby – język obiektowy, a przy tym łatwy w użytkowaniu i czytelny • Io – prototypowy język, wyposażony w unikatowy mechanizm dystrybucji komunikatów • Prolog – język oferujący łatwe rozwiązania, które w Javie lub C byłyby bardzo kłopotliwe • Scala – jeden z języków nowej generacji, przeznaczony na maszynę wirtualną Javy • Erlang – język funkcyjny, z mechanizmami obsługi współbieżności, na którym działa już kilka słynnych baz danych w stylu cloud • Clojure – język, w którym wykorzystano strategię wersjonowania baz danych w celu zarządzania współbieżnością • Haskell – język o charakterze czysto funkcyjnym Jeden z tych języków może już wkrótce stać się Twoim ulubionym narzędziem! Idź do • Spis treści • Przykładowy rozdział • Skorowidz Katalog książek • Katalog online • Zamów drukowany katalog Twój koszyk • Dodaj do koszyka Cennik i informacje • Zamów informacje o nowościach • Zamów cennik Czytelnia • Fragmenty książek online Kontakt Helion SA ul. Kościuszki 1c 44-100 Gliwice tel. 32 230 98 63 e-mail: helion@helion.pl © Helion 1991–2011 Spis treĂci Dedykacja ............................................................................................................ 7 PodziÚkowania .................................................................................................... 9 Sïowo wstÚpne .................................................................................................. 13 Rozdziaï 1. Wprowadzenie ............................................................................... 17 1.1. Metoda w szaleñstwie ............................................................................................... 17 1.2. JÚzyki ....................................................................................................................... 19 1.3. Kup tÚ ksiÈĝkÚ .......................................................................................................... 22 1.4. Nie kupuj tej ksiÈĝki ................................................................................................. 23 1.5. Ostateczny wniosek ................................................................................................... 26 Rozdziaï 2. Ruby ................................................................................................ 27 2.1. Krótki rys historyczny ............................................................................................... 28 2.2. Dzieñ 1. Gdzie jest niania? ....................................................................................... 30 2.3. Dzieñ 2. SfrunÈÊ z nieba .......................................................................................... 38 2.4. Dzieñ 3. Powaĝna zmiana ........................................................................................ 52 2.5. Ruby. Podsumowanie ............................................................................................... 60 Rozdziaï 3. Io ..................................................................................................... 65 3.1. Przedstawiamy jÚzyk Io ............................................................................................. 65 3.2. Dzieñ 1. Urywamy siÚ ze szkoïy. Wagarujemy ........................................................... 66 3.3. Dzieñ 2. Król kieïbasy .............................................................................................. 80 3.4. Dzieñ 3. Festyn oraz inne dziwne miejsca .................................................................. 89 3.5. Io. Podsumowanie .................................................................................................... 99 Rozdziaï 4. Prolog ............................................................................................ 103 4.1. O Prologu ............................................................................................................. 104 4.2. Dzieñ 1. ¥wietny kierowca ...................................................................................... 105 6  Siedem jÚzyków w siedem tygodni 4.3. Dzieñ 2. PiÚtnaĂcie minut do Wapnera .................................................................... 119 4.4. Dzieñ 3. PodbiÊ Vegas ........................................................................................... 131 4.5. Prolog. Podsumowanie ........................................................................................... 143 Rozdziaï 5. Scala .............................................................................................. 147 5.1. O jÚzyku Scala ....................................................................................................... 148 5.2. Dzieñ 1. Zamek na wzgórzu ................................................................................... 152 5.3. Dzieñ 2. Przycinanie ĝywopïotu i inne sztuczki ......................................................... 168 5.4. Dzieñ 3. CiÚcie puchu ............................................................................................ 183 5.5. Scala. Podsumowanie ............................................................................................. 193 Rozdziaï 6. Erlang ........................................................................................... 199 6.1. Przedstawiamy Erlanga .......................................................................................... 200 6.2. Dzieñ 1. Z wyglÈdu czïowiek .................................................................................. 204 6.3. Dzieñ 2. Zmiana form ............................................................................................ 215 6.4. Dzieñ 3. Czerwone piguïki ...................................................................................... 228 6.5. Erlang. Podsumowanie ........................................................................................... 241 Rozdziaï 7. Clojure .......................................................................................... 245 7.1. Przedstawiamy jÚzyk Clojure ................................................................................... 246 7.2. Dzieñ 1. Szkolenie Luke’a ...................................................................................... 248 7.3. Dzieñ 2. Yoda i Moc .............................................................................................. 267 7.4. Dzieñ 3. Oko zïa .................................................................................................... 282 7.5. Clojure. Podsumowanie .......................................................................................... 291 Rozdziaï 8. Haskell .......................................................................................... 297 8.1. Przedstawiamy Haskella ......................................................................................... 297 8.2. Dzieñ 1. WartoĂci logiczne ..................................................................................... 299 8.3. Dzieñ 2. Wielka siïa Spocka ................................................................................... 315 8.4. Dzieñ 3. ’ÈcznoĂÊ umysïów .................................................................................... 326 8.5. Haskell. Podsumowanie .......................................................................................... 342 Rozdziaï 9. Podsumowanie ............................................................................ 347 9.1. Modele programowania .......................................................................................... 348 9.2. WspóïbieĝnoĂÊ ....................................................................................................... 351 9.3. Konstrukcje programowania .................................................................................... 354 9.4. Znajdě swój gïos .................................................................................................... 356 Dodatek A. Bibliografia .................................................................................. 357 Skorowidz ........................................................................................................ 359 Rozdziaï 4. Prolog Sally Dibbs, Dibbs Sally. 461-0192. Raymond A ch, ten Prolog. Czasami spektakularnie bïyskotliwy, innym razem tak sa- mo frustrujÈcy. ZdumiewajÈce odpowiedzi uzyskujemy tylko wtedy, kiedy wiemy, jak naleĝy zadawaÊ pytania. Porównaïbym go do postaci z Rain Mana1. PamiÚtam, jak jeden z gïównych bohaterów, Raymond, niewiele myĂlÈc, wyrecytowaï numer telefonu Sally Dibbs po przeczytaniu dzieñ wczeĂniej ksiÈĝki telefonicznej. Zarówno w przypadku Raymonda, jak i Prologu czÚsto zadajÚ sobie dwa pytania: „SkÈd on to wiedziaï” i „Jak on mógï tego nie wiedzieÊ?”. Jest kopal- niÈ wiedzy, jeĂli tylko uda nam siÚ wïaĂciwie sformuïowaÊ pytanie. Prolog znaczÈco róĝni siÚ od innych jÚzyków, z którymi dotychczas mieliĂmy do czy- nienia. Zarówno Io, jak i Ruby zaliczajÈ siÚ do jÚzyków imperatywnych. W jÚzy- kach imperatywnych formuïujemy „przepisy”. Dokïadniej mówiÈc, instruujemy kom- puter, w jaki sposób naleĝy wykonaÊ zadanie. JÚzyki imperatywne wyĝszego poziomu dajÈ programistom nieco wiÚcej swobody. PozwalajÈ na poïÈczenie wielu dïuĝszych kroków w jeden. Ogólnie rzecz biorÈc, programowanie sprowadza siÚ jednak do zde- finiowania listy skïadników i opisania krok po kroku procesu wypiekania ciasta. 1 Rain Man. DVD. Reĝyseria Barry Levinson. 1988; Los Angeles, CA: MGM, 2000. 104  Siedem jÚzyków w siedem tygodni Zanim podjÈïem próbÚ napisania tego rozdziaïu, poĂwiÚciïem kilka tygodni na eks- perymentowanie z Prologiem. W tym czasie skorzystaïem z kilku samouczków. Stu- diowaïem miÚdzy innymi przykïady z samouczka J.R. Fishera2. W poznaniu termi- nologii i struktury programu pomógï mi teĝ samouczek A. Aaby’ego3. Wykonaïem równieĝ wiele samodzielnych Êwiczeñ. Prolog jest jÚzykiem deklaratywnym. Programista podaje fakty i reguïy wnioskowa- nia, a Prolog znajduje rozwiÈzanie. To tak, jakbyĂmy poszli do dobrego cukiernika. Opisujemy mu ciastka, które nam smakujÈ, a on sam, na podstawie przekazanych reguï, dobiera skïadniki i piecze ciasto. ProgramujÈc w Prologu, nie trzeba znaÊ od- powiedzi na pytanie jak. Za wyciÈganie wniosków odpowiedzialny jest komputer. Wystarczy trochÚ poszperaÊ w internecie, aby znaleěÊ przykïady rozwiÈzania sudo- ku za pomocÈ programu skïadajÈcego siÚ z mniej niĝ dwudziestu linijek kodu. SÈ teĝ programy do ukïadania kostki Rubika, czy teĝ rozwiÈzywania popularnych ïami- gïówek, takich jak Wieĝa Hanoi (zaledwie kilkanaĂcie linijek). Prolog byï jednym z pierwszych jÚzyków programowania logicznego, które odniosïy sukces. Programi- sta formuïuje logiczne twierdzenia, a Prolog ocenia, czy sÈ one prawdziwe. W po- dawanych twierdzeniach mogÈ byÊ luki. Prolog stara siÚ wypeïniÊ luki w taki sposób, by niekompletne fakty tworzyïy prawdziwe stwierdzenia. 4.1. O Prologu Prolog jest jÚzykiem programowania logicznego opracowanym w 1972 roku przez Alaina Colmerauera i Phillippe’a Roussela. JÚzyk ten zyskaï popularnoĂÊ w prze- twarzaniu jÚzyka naturalnego. Obecnie ten szacowny jÚzyk dostarcza podstaw pro- gramowania dla szerokiej gamy problemów — poczÈwszy od planowania zadañ, a skoñczywszy na systemach ekspertowych. Ten bazujÈcy na reguïach jÚzyk moĝna wykorzystaÊ do wyraĝania logiki i zadawania pytañ. Tak jak SQL, Prolog przetwa- rza bazy danych, choÊ w przypadku Prologu dane skïadajÈ siÚ z reguï i zwiÈzków logicznych. Tak jak SQL, Prolog moĝna podzieliÊ na dwie czÚĂci: jednej do opisy- wania danych i drugiej do zadawania pytañ o dane. W Prologu dane majÈ postaÊ logicznych reguï. Oto podstawowe bloki budulcowe Prologu: 2 http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html 3 http://www.lix.polytechnique.fr/~liberti/public/computing/prog/prolog/prolog-tutorial.html Rozdziaï 4. • Prolog  105  Fakty. Fakt jest podstawowym twierdzeniem dotyczÈcym rzeczywistoĂci (Piggy to Ăwinia, Ăwinie lubiÈ bïoto).  Reguïy. Reguïa definiuje wniosek dotyczÈcy faktów w okreĂlonej rzeczy- wistoĂci (zwierzÚ lubi bïoto, jeĂli jest ĂwiniÈ).  Zapytanie. Zapytanie jest pytaniem dotyczÈcym wybranej rzeczywistoĂci (czy Piggy lubi bïoto?). Fakty i reguïy sÈ zapisywane w bazie wiedzy. Kompilator Prologu kompiluje ba- zÚ wiedzy, przeksztaïcajÈc jÈ na postaÊ pozwalajÈcÈ na wydajne formuïowanie za- pytañ. StudiujÈc przykïady zamieszczone w tym rozdziale, bÚdziemy wykorzystywali Prolog do przedstawienia bazy wiedzy. NastÚpnie spróbujemy bezpoĂrednio wy- dobyÊ dane i skorzystaÊ z Prologu do powiÈzania ze sobÈ reguï w taki sposób, aby zdobyÊ informacje, których nie znamy. DoĂÊ wprowadzenia. Zabierzmy siÚ do pracy. 4.2. Dzieñ 1. ¥wietny kierowca W Rain Manie Raymond powiedziaï swojemu bratu, ĝe jest Ăwietnym kierowcÈ, po- niewaĝ potrafi sprawnie prowadziÊ samochód po parkingu z prÚdkoĂciÈ 10 kilome- trów na godzinÚ. Raymond uĝywaï wszystkich gïównych podzespoïów samochodu — kierownicy, hamulców, pedaïu gazu — ale uĝywaï ich w ograniczony sposób. Taki jest nasz dzisiejszy cel. Uĝyjemy Prologu do sformuïowania pewnych faktów, zdefiniowania reguï oraz wykonania pewnych podstawowych zapytañ. Prolog, tak jak Io, jest jÚzykiem o niezwykle prostej skïadni. Bardzo szybko moĝna siÚ nauczyÊ podstawowych reguï. Prawdziwa zabawa zaczyna siÚ w chwili, kiedy pojÚcia uïoĝÈ siÚ w warstwy, tworzÈc interesujÈcÈ kompozycjÚ. JeĂli to jest dla czytelnika pierwsze spotkanie z Prologiem, to gwarantujÚ, ĝe albo zmieni sposób swojego myĂlenia, al- bo bÚdzie skazany na niepowodzenie. Szersze rozwiniÚcie tematu pozostawimy na dalszy dzieñ. Najpierw podstawa. Trzeba przygotowaÊ dziaïajÈcÈ instalacjÚ. Dla potrzeb niniej- szej ksiÈĝki uĝywam GNU Prolog w wersji 1.3.1. Naleĝy zachowaÊ ostroĝnoĂÊ. Dialekty Prologu róĝniÈ siÚ pomiÚdzy sobÈ. BÚdÚ siÚ staraï, aby stÈpaÊ po „wspól- nym gruncie”, ale czytelnicy, którzy wybiorÈ innÈ wersjÚ Prologu, bÚdÈ musieli od- robiÊ zadanie domowe. DziÚki temu zrozumiejÈ róĝnice wystÚpujÈce w wybranej 106  Siedem jÚzyków w siedem tygodni przez siebie odmianie jÚzyka. Poniĝej zamieĂciïem opis sposobu korzystania z jÚzy- ka — niezaleĝnie od wybranej wersji. Proste fakty W niektórych jÚzykach uĝywanie wielkich i maïych liter jest wyïÈcznie w gestii pro- gramisty, ale w Prologu wielkoĂÊ liter ma znaczenie. JeĂli sïowo rozpoczyna siÚ ma- ïÈ literÈ, to jest to atom — ustalona wartoĂÊ, tak jak symbol w Ruby. JeĂli nato- miast rozpoczyna siÚ wielkÈ literÈ lub symbolem podkreĂlenia, to jest to zmienna. Zmienne mogÈ siÚ zmieniaÊ, atomy nie. Spróbujmy stworzyÊ prostÈ bazÚ wiedzy zawierajÈcÈ kilka faktów. Wpisz poniĝszy kod w edytorze: Pobierz: prolog/przyjaciele.pl lubi(wallace, ser). lubi(gromit, ser). lubi(wendolene, owce). przyjaciel(X, Y) :- +(X = Y), lubi(X, Z), lubi(Y, Z). Powyĝszy plik to baza wiedzy zawierajÈca fakty i reguïy. Pierwsze trzy instrukcje to fakty, natomiast ostatnia instrukcja jest reguïÈ. Fakty sÈ bezpoĂrednimi obserwacja- mi rzeczywistoĂci. Reguïy sÈ logicznymi wnioskami dotyczÈcymi rzeczywistoĂci. Na razie zwróÊmy uwagÚ na pierwsze trzy wiersze. Wszystkie one opisujÈ fakty. wallace, gromit i wendolene4 sÈ atomami. Fakty moĝna zinterpretowaÊ nastÚpujÈco: wallace lubi ser, gromit lubi ser, a wendolene lubi owce. Spróbujmy wykorzystaÊ fakty w praktyce. Uruchamiamy interpreter Prologu. Czytelnicy uĝywajÈcy wersji GNU Prolog po- winni w tym celu wpisaÊ polecenie gprolog. NastÚpnie w celu zaïadowania pliku na- leĝy wpisaÊ nastÚpujÈce polecenie: | ?- [ przyjaciele.pl ]. compiling C:/Seven Languages/przyklady/przyjaciele.pl for byte code... C:/Seven Languages/przyklady/przyjaciele.pl compiled, 5 lines read - 976 bytes written, 15 ms (16 ms) yes | ?- JeĂli Prolog nie oczekuje na poĂrednie wyniki, to udzieli odpowiedzi yes (tak) lub no (nie). W naszym przypadku zaïadowanie pliku zakoñczyïo siÚ pomyĂlnie, dlate- 4 Wallace, Gromit i Wendolene to postacie z brytyjskiego filmu animowanego Wallace i Gromit: Golenie owiec, 1995 — przyp. tïum. Rozdziaï 4. • Prolog  107 go Prolog odpowiedziaï yes. Moĝemy zaczÈÊ zadawaÊ pytania. Najprostsze sÈ py- tania o potwierdzenie bÈdě zaprzeczenie okreĂlonych faktów. Spróbujmy zadaÊ kil- ka tego rodzaju pytañ: | ?- lubi(wallace, owce). no | ?- lubi(gromit, ser). yes Powyĝsze pytania sÈ doĂÊ intuicyjne. Czy wallace lubi owce? Nie. Czy gromit lubi ser? Tak. Nie jest to zbyt ciekawe. Prolog jedynie powtarza jak papuga fakty z ba- zy wiedzy. Nieco ciekawiej robi siÚ w przypadku, gdy spróbujemy zbudowaÊ jakÈĂ logikÚ. Przyjrzyjmy siÚ mechanizmowi wnioskowania. Proste wnioski i zmienne Wypróbujmy reguïÚ przyjaciel: | ?- przyjaciel(wallace, wallace). no Jak widaÊ, Prolog analizuje wpisane reguïy i odpowiada na pytania twierdzÈco bÈdě przeczÈco. Wnioskowanie to coĂ wiÚcej niĝ widaÊ na pierwszy rzut oka. Ponownie przyjrzyjmy siÚ regule przyjaciel: Aby X mógï byÊ przyjacielem Y, nie moĝe byÊ taki sam jak Y. Przyjrzyjmy siÚ pierw- szej czÚĂci wystÚpujÈcej z prawej strony symbolu :-. Jest to tzw. cel czÚĂciowy (ang. subgoal). + jest operatorem negacji logicznej. Zatem instrukcja +(X = Y) oznacza X nie równa siÚ Y. Wypróbujmy kilka innych zapytañ: | ?- przyjaciel(gromit, wallace). yes | ?- przyjaciel(wallace, gromit). yes X jest przyjacielem Y, jeĂli moĝna udowodniÊ, ĝe X lubi jakieĂ Z, a Y lubi to samo Z. Za- równo wallace, jak i gromit lubiÈ ser, dlatego odpowiedě na to pytanie jest twierdzÈca. Spróbujmy zagïÚbiÊ siÚ w kod. W zapytaniach X nie jest równe Y, co udowadnia pierwszy cel czÚĂciowy. W zapytaniu bÚdÈ uĝyte pierwszy i trzeci cel czÚĂciowy: 108  Siedem jÚzyków w siedem tygodni lubi(X, Z) i lubi(Y, Z). gromit i wallace lubiÈ ser, zatem udowodniliĂmy drugi i trze- ci cel czÚĂciowy. Wypróbujmy inne zapytanie: | ?- przyjaciel(wendolene, gromit). no W tym przypadku interpreter Prologu musiaï wypróbowaÊ kilka moĝliwych warto- Ăci X, Y i Z:  wendolene, gromit i ser;  wendolene, gromit i owce. ¿adna kombinacja nie speïniaïa obu celów — tzn. aby wendolene lubiïa Z i jedno- czeĂnie by gromit takĝe lubiï Z. Nie istnieje takie Z, dlatego maszyna wnioskowania udzieliïa odpowiedzi „nie” — to nie sÈ przyjaciele. Spróbujmy sformalizowaÊ terminologiÚ. Poniĝsza instrukcja: przyjaciel(X, Y) :- +(X = Y), lubi(X, Z), lubi(Y, Z). jest reguïÈ Prologu z trzema zmiennymi: X, Y i Z. ReguïÚ tÚ opisujemy przyjaciel/2 — jest to skrócona forma reguïy przyjaciel z dwoma parametrami. Reguïa ta za- wiera trzy cele czÚĂciowe oddzielone od siebie przecinkami. Aby reguïa byïa praw- dziwa, wszystkie cele czÚĂciowe muszÈ byÊ prawdziwe. A zatem nasza reguïa ozna- cza, ĝe X jest przyjacielem Y, jeĂli X i Y nie sÈ sobie równe, a jednoczeĂnie zarówno X, jak i Y lubiÈ to samo Z. Wypeïnianie luk WykorzystaliĂmy Prolog do uzyskania odpowiedzi „tak” lub „nie” na postawione pytania. Zastosowania Prologu nie ograniczajÈ siÚ jednak wyïÈcznie do tego. W tym punkcie wykorzystamy maszynÚ wnioskowania do znalezienia wszystkich moĝliwych odpowiedzi na pytanie. Aby to zrobiÊ, okreĂlimy w zapytaniu zmiennÈ. Przeanalizujmy nastÚpujÈcÈ bazÚ wiedzy: Pobierz: prolog/zywnosc.pl zywnosc_typ(velveeta, ser). zywnosc_typ(ritz, krakers). zywnosc_typ(konserwa, miÚso). zywnosc_typ(kieïbasa, miÚso). zywnosc_typ(jolt, napój). zywnosc_typ(twinkie, deser). Rozdziaï 4. • Prolog smak(sïodki, deser). smak(pikantny, miÚso). smak(pikantny, ser). smak(sïodki, napój).  109 zywnosc_smak(X, Y) :- zywnosc_typ(X, Z), smak(Y, Z). W bazie wiedzy mamy kilka faktów. Niektóre z nich, na przykïad zywnosc_typ(velveeta, ser), oznaczajÈ, ĝe ĝywnoĂÊ jest okreĂlonego typu. Inne, na przykïad smak(sïodki, deser), oznaczajÈ, ĝe ĝywnoĂÊ okreĂlonego typu ma charakterystyczny smak. Na ko- niec mamy reguïÚ o nazwie zywnosc_smak, która umoĝliwia wywnioskowanie smaku ĝywnoĂci okreĂlonego typu. ¿ywnoĂÊ X ma zywnosc_smak Y, jeĂli ĝywnoĂÊ posiada zywnosc_typ Z oraz to Z ma charaterystyczny smak. Spróbujmy skompilowaÊ ten skrypt: | ?- [ code/prolog/zywnosc.pl ]. compiling C:/Seven Languages/przyklady/zywnosc.pl for byte code... C:/Seven Languages/przyklady/zywnosc.pl compiled, 13 lines read - 1567 bytes written, 15 ms yes Moĝemy teraz zadaÊ kilka pytañ. | ?- zywnosc_typ(Co, miÚso). Co = konserwa ? ; Co = kieïbasa ? ; no ZwróÊmy uwagÚ na interesujÈcy aspekt. DaliĂmy Prologowi zadanie: „Znajdě pew- nÈ wartoĂÊ zmiennej Co, która speïnia zapytanie zywnosc_typ(Co, miÚso)”. Prolog zna- lazï jednÈ takÈ wartoĂÊ: konserwa. Kiedy wpisaliĂmy polecenie ; poprosiliĂmy, aby Prolog znalazï innÈ wartoĂÊ zmiennej. W odpowiedzi uzyskaliĂmy wartoĂÊ kieïbasa. WartoĂci te ïatwo byïo znaleěÊ, poniewaĝ zapytania bazowaïy na prostych faktach. NastÚpnie zadaliĂmy pytanie o kolejnÈ wartoĂÊ, a Prolog odpowiedziaï no. Takie zachowanie jest trochÚ niespójne. Gdyby Prolog potrafiï wykryÊ, ĝe nie ma wiÚcej alternatywnych wartoĂci, zobaczylibyĂmy odpowiedě yes. JeĂli Prolog nie moĝe na- tychmiast stwierdziÊ, czy istnieje wiÚcej alternatywnych rozwiÈzañ, bez dodatkowych obliczeñ, zwraca no i oczekuje na kolejne polecenie. WïasnoĂÊ ta istnieje wyïÈcznie dla wygody uĝytkownika. JeĂli Prolog potrafi udzieliÊ odpowiedzi wczeĂniej, to jej udzieli. Spróbujmy zadaÊ kilka dodatkowych pytañ: | ?- zywnosc_smak(kieïbasa, sïodki). no | ?- smak(sïodki, Co). 110  Co = deser ? ; Co = napój Siedem jÚzyków w siedem tygodni yes Nie, kieïbasa nie jest sïodka. Jakiego typu ĝywnoĂÊ jest sïodka? Deser i napój. Wszyst- ko to sÈ fakty. Pozwólmy jednak, aby Prolog sam wyciÈgnÈï wnioski: | ?- zywnosc_smak(Co, pikantny). Co = velveeta ? ; Co = konserwa ? ; Co = kieïbasa ? ; no ZapamiÚtajmy, zywnosc_smak(X, Y) to reguïa, a nie fakt. PoprosiliĂmy interpreter Prologu o znalezienie wszystkich wartoĂci speïniajÈcych zapytanie „Jakie typy ĝyw- noĂci majÈ pikantny smak?”. Aby znaleěÊ rozwiÈzanie, Prolog musiaï powiÈzaÊ ze sobÈ proste fakty dotyczÈce ĝywnoĂci — jej typów i smaków. Silnik wnioskowania musiaï przeanalizowaÊ wszystkie moĝliwe kombinacje wartoĂci, dla których wszyst- kie cele czÚĂciowe zostaïy osiÈgniÚte. Kolorowanie map Spróbujmy wykorzystaÊ tÚ samÈ koncepcjÚ do kolorowania map. Przeanalizujmy poniĝszy przykïad, aby uzyskaÊ bardziej spektakularny poglÈd na Prolog. Zamie- rzamy pokolorowaÊ mapÚ poïudniowowschodniego rejonu Stanów Zjednoczonych. Na rysunku 4.1 zamieszczono mapÚ stanów, które bÚdziemy kolorowaÊ. Zakïada- my, ĝe dwa stany pokolorowane na taki sam kolor nie mogÈ siÚ ze sobÈ stykaÊ. Zakodujemy kilka prostych faktów. Pobierz: prolog/mapa.pl róĝne(czerwony, zielony). róĝne(czerwony, niebieski). róĝne(zielony, czerwony). róĝne(zielony, niebieski). róĝne(niebieski, czerwony). róĝne(niebieski, zielony). pokoloruj(Alabama, Missisipi, Georgia, Tennessee, Floryda) :- róĝne(Missisipi, Tennessee), róĝne(Missisipi, Alabama), róĝne(Alabama, Tennessee), róĝne(Alabama, Missisipi), róĝne(Alabama, Georgia), róĝne(Alabama, Floryda), róĝne(Georgia, Floryda), róĝne(Georgia, Tennessee). Rozdziaï 4. • Prolog  111 Rysunek 4.1. Mapa wybranych poïudniowowschodnich stanów USA Mamy trzy kolory. Przekazujemy Prologowi informacjÚ o zbiorach róĝnych kolorów do wykorzystania w kolorowaniu mapy. Jest równieĝ reguïa. W regule pokoloruj in- formujemy Prolog o tym, które stany ze sobÈ sÈsiadujÈ. To wszystko. Wypróbujmy poniĝszy kod: | ?- pokoloruj(Alabama, Missisipi, Georgia, Tennessee, Floryda). Alabama = niebieski Floryda = zielony Georgia = czerwony Missisipi = czerwony Tennessee = zielony ? Z pewnoĂciÈ istnieje sposób pokolorowania tych piÚciu stanów za pomocÈ trzech kolorów. Aby uzyskaÊ inne moĝliwe kombinacje, wystarczy wpisaÊ a. WykonaliĂmy zadanie zaledwie za pomocÈ kilkunastu linijek kodu. Logika jest Ămiesznie prosta — nawet dziecko zorientowaïoby siÚ, o co w niej chodzi. W pewnym momencie trze- ba jednak zadaÊ sobie pytanie… 112  Siedem jÚzyków w siedem tygodni Gdzie jest program? W powyĝszym kodzie nigdzie nie ma implementacji algorytmu! Spróbujcie rozwiÈ- zaÊ taki sam problem w dowolnym jÚzyku proceduralnym. Czy to rozwiÈzanie by- ïoby zrozumiaïe? PomyĂlcie, co trzeba by byïo zrobiÊ, aby rozwiÈzaÊ podobnie zïo- ĝony problem logiczny w takich jÚzykach jak Ruby lub Io. Oto jeden z moĝliwych sposobów postÚpowania: 1. sformuïowanie logiki rozwiÈzania problemu, 2. wyraĝenie logiki w programie, 3. znalezienie wszystkich moĝliwych danych wejĂciowych, 4. sprawdzenie dziaïania programów dla tych danych. Pisanie takiego programu mogïoby zajÈÊ sporo czasu. W Prologu logikÚ wyraĝa siÚ w postaci faktów i wniosków. NastÚpnie moĝna zadawaÊ pytania. Programista pi- szÈcy programy w tym jÚzyku nie jest odpowiedzialny za tworzenie receptur krok po kroku. Prolog nie sïuĝy do zapisywania algorytmów w celu rozwiÈzywania pro- blemów logicznych. Prolog sïuĝy do opisywania Ăwiata i prezentowania problemów logicznych, które komputer próbuje rozwiÈzywaÊ. Pozwólmy komputerom wykonywaÊ swojÈ pracÚ. Unifikacja. CzÚĂÊ 1. W tym momencie nadszedï czas, aby trochÚ siÚ cofnÈÊ i zaprezentowaÊ wiÚcej teo- rii. Spróbujmy rzuciÊ nieco wiÚcej Ăwiatïa na unifikacjÚ. W niektórych jÚzykach sto- sujemy podstawienia zmiennych. Na przykïad w Javie lub w Ruby x = 10 oznacza: podstaw 10 do zmiennej x. Unifikacja dwóch struktur to dÈĝenie do tego, aby obie staïy siÚ identyczne. Przeanalizujmy nastÚpujÈcÈ bazÚ wiedzy: Pobierz: prolog/zwierzeta.pl kot(lew). kot(tygrys). dorota(X, Y, Z) :- X = lew, Y = tygrys, Z = nieděwiedě. dwa_koty(X, Y) :- kot(X), kot(Y). W tym przykïadzie symbol = oznacza „zunifikuj” — tzn. spowoduj, aby obie strony byïy identyczne. W bazie wiedzy sÈ zapisane dwa fakty: lwy i tygrysy sÈ kotami. Ma- my takĝe dwie proste reguïy: W regule dorota/3 argumenty X, Y i Z to odpowiednio Rozdziaï 4. • Prolog  113 lew, tygrys i nieděwiedě. W regule dwa_koty/2 argument X to kot i Y to kot. PowyĝszÈ bazÚ wiedzy moĝemy wykorzystaÊ do dokïadniejszego wyjaĂnienia unifikacji. Najpierw spróbujmy zastosowaÊ pierwszÈ reguïÚ. Skompilujemy, a nastÚpnie wyko- namy proste zapytanie bez parametrów. | ?- dorota(lew, tygrys, nieděwiedě). yes PamiÚtajmy: unifikacja oznacza „znajdě wartoĂci, dla których dwie strony sÈ sobie równe”. Po prawej stronie Prolog wiÈĝe argumenty X, Y i Z z wartoĂciami lew, tygrys i nieděwiedě. WartoĂci te pasujÈ do odpowiadajÈcych im wartoĂci po lewej stronie. Oznacza to, ĝe unifikacja przebiegïa pomyĂlnie. Prolog odpowiada yes. Powyĝszy przypadek jest dosyÊ prosty, moĝna go jednak trochÚ skomplikowaÊ. Unifikacja moĝe dziaïaÊ po obu stronach implikacji. Spróbujmy wykonaÊ nastÚpujÈcy kod: | ?- dorota(Jeden, Dwa, Trzy). Dwa = tygrys Jeden = lew Trzy = nieděwiedě yes W tym przykïadzie wystÚpuje dodatkowa warstwa poĂrednia. W funkcji celu Pro- log unifikuje argumenty X, Y i Z do wartoĂci lew, tygrys i nieděwiedě. Po lewej stro- nie Prolog wiÈĝe argumenty X, Y i Z ze zmiennymi Jeden, Dwa i Trzy, a nastÚpnie wy- Ăwietla wyniki. Przejděmy teraz do ostatniej reguïy: dwa_koty/2. Reguïa ta mówi, ĝe dwa_koty(X, Y) jest prawdÈ, jeĂli moĝna udowodniÊ, ĝe zarówno X, jak i Y to koty. Wypróbujmy po- niĝszy kod: | ?- dwa_koty(Jeden, Dwa). Jeden = lew Dwa = lew ? Prolog wyĂwietliï pierwsze rozwiÈzanie: lew i lew to dwa koty. Przenalizujmy spo- sób dojĂcia do tej konkluzji: 1. SformuïowaliĂmy zapytanie: dwa_koty(Jeden, Dwa). Prolog powiÈzaï zmien- nÈ Jeden z X oraz Dwa z Y. W celu rozwiÈzania problemu Prolog musi obli- czyÊ funkcje celu. 2. Pierwszy cel to kot(X). 114  Siedem jÚzyków w siedem tygodni 3. FunkcjÚ tÚ speïniajÈ dwa fakty: kot(lew) i kot(tygrys). Prolog podejmuje próbÚ sprawdzenia pierwszego faktu. Podstawia do argumentu X wartoĂÊ lew i przechodzi do nastÚpnej funkcji celu. 4. Teraz Prolog wiÈĝe zmiennÈ Y z kot(Y). RozwiÈzanie tej funkcji celu Pro- log znajduje w taki sam sposób jak w pierwszym przypadku — wybiera wartoĂÊ lew. 5. Obie funkcje celu sÈ speïnione, zatem reguïa jest prawdziwa. Prolog wy- Ăwietliï wartoĂci Jeden i Dwa, dla których reguïa jest speïniona, i odpowie- dziaï yes. Mamy zatem pierwsze rozwiÈzanie, dla którego reguïy sÈ prawdziwe. Czasami jedno rozwiÈzanie nam wystarcza. Czasem potrzebujemy wiÚcej niĝ jednego. Moĝemy te- raz przeglÈdaÊ po kolei inne rozwiÈzania, wpisujÈc symbol ;. Moĝemy teĝ zaĝÈdaÊ wyĂwietlenia wszystkich pozostaïych rozwiÈzañ. W tym celu wystarczy wcisnÈÊ a. Dwa = lew ? a Jeden = lew Dwa = tygrys Jeden = tygrys Dwa = lew Jeden = tygrys Dwa = tygrys (1 ms) yes ZwróÊmy uwagÚ, ĝe Prolog przeanalizowaï listÚ wszystkich kombinacji argumen- tów X i Y, uwzglÚdniajÈc dostÚpne informacje w funkcjach celu oraz odpowiednich faktach. Jak przekonamy siÚ póěniej, unifikacja pozwala równieĝ na przeprowadza- nie zïoĝonego dopasowywania na podstawie struktury danych. Tyle wystarczy na pierwszy dzieñ. Nieco bardziej zïoĝonymi przykïadami zajmiemy siÚ drugiego dnia. Prolog w praktyce ZetkniÚcie siÚ z „programem” zaprezentowanym w ten sposób moĝe byÊ doĂÊ oso- bliwym przeĝyciem. W Prologu czÚsto nie tworzymy precyzyjnych receptur krok po kroku, a jedynie przepis na placek, który trzeba wyjÈÊ z pieca, kiedy juĝ bÚdzie go- towy. Kiedy uczyïem siÚ Prologu, bardzo pomógï mi wywiad z osobÈ, która korzy- staïa z tego jÚzyka w praktyce. Rozmawiaïem z Brianem Tarboksem — naukow- Rozdziaï 4. • Prolog  115 cem, który skorzystaï z Prologu do opracowania harmonogramów pracy personelu laboratorium z delfinami w projekcie badawczym. Wywiad z Brianem Tarboksem — naukowcem badajÈcym delfiny Bruce: Czy moĝe nam pan opowiedzieÊ o swoich doĂwiadczeniach z nauki Prologu? Brian: Prologu zaczÈïem siÚ uczyÊ pod koniec lat osiemdziesiÈtych podczas studiów na Uniwersytecie Hawajskim w Manoa. Pracowaïem w Kewalo Basin Marine Mam- mal Laboratory. Prowadziïem badania moĝliwoĂci poznawczych delfinów butelkono- sych. WiÚkszoĂÊ dyskusji w laboratorium dotyczyïa róĝnych teorii na temat sposobów myĂlenia delfinów. PracowaliĂmy gïównie z delfinem o imieniu Akeakamai — zdrob- niale nazywaliĂmy go Ake. Wiele rozmów zaczynaïo siÚ mniej wiÚcej tak: „Wydaje mi siÚ, ĝe Ake postrzega tÚ sytuacjÚ w taki to a taki sposób…”. Postanowiïem, ĝe w mojej pracy skupiÚ siÚ na stworzeniu modelu pasujÈcego do na- szego postrzegania sposobu widzenia Ăwiata przez Ake’a. Miaïem zamiar zaprezen- towaÊ co najmniej podzbiór tego, nad czym prowadziliĂmy badania. Gdyby ten mo- del potrafiï przewidzieÊ rzeczywiste zachowania Ake’a, zyskalibyĂmy potwierdzenie naszych teorii dotyczÈcych sposobu jego rozumowania. Prolog jest cudownym jÚzykiem, ale dopóki nie przyzwyczaimy siÚ do niego, otrzymy- wane wyniki mogÈ wydawaÊ siÚ nam doĂÊ dziwne. PamiÚtam jedno z moich pierw- szych doĂwiadczeñ z Prologiem. Napisaïem coĂ w stylu x = x + 1. Prolog odpo- wiedziaï „no”. JÚzyki zazwyczaj nie mówiÈ „nie”. Czasami moĝna uzyskaÊ bïÚdne wyniki, innym razem program nie chce siÚ skompilowaÊ, ale nigdy nie spotkaïem siÚ z jÚzykiem, który by do mnie mówiï „nie”. Zwróciïem siÚ wiÚc do pomocy technicz- nej i powiedziaïem, ĝe uzyskaïem odmowÚ wykonania polecenia, gdy chciaïem zmieniÊ wartoĂÊ zmiennej. Zapytali mnie: „A czemu miaïaby sïuĝyÊ zmiana wartoĂci zmien- nej?”. PomyĂlaïem, co u licha? Jaki jÚzyk nie pozwala ci zmieniaÊ wartoĂci zmien- nych? Po pewnym czasie poznawania Prologu staje siÚ jasne, ĝe zmienne albo majÈ jakÈĂ konkretnÈ wartoĂÊ, albo sÈ niezwiÈzane, ale wtedy jeszcze tego nie wiedziaïem. Bruce: W jaki sposób wykorzystaï pan Prolog? Brian: Stworzyïem dwa gïówne systemy: symulator delfina i program do tworzenia harmonogramów pracy laboratorium. Laboratorium prowadziïo cztery doĂwiadczenia dziennie z kaĝdym z czterech delfinów. Musicie wiedzieÊ, ĝe delfiny doĂwiadczalne to 116  Siedem jÚzyków w siedem tygodni niezwykle ograniczony zasób. Kaĝdy delfin pracowaï na potrzeby innego doĂwiad- czenia, a kaĝde doĂwiadczenie wymagaïo innego personelu. Pewne role, na przykïad trenera delfinów, mogïo odgrywaÊ zaledwie kilka osób. Inne role, na przykïad rejestra- torów danych, mogïy byÊ odgrywane przez szersze grono osób, ale pomimo to musiaïy to byÊ osoby odpowiednio przeszkolone. WiÚkszoĂÊ doĂwiadczeñ wymagaïa perso- nelu zïoĝonego z szeĂciu do dwunastu osób. MieliĂmy do dyspozycji licealistów, stu- dentów i ochotników ze spoïecznoĂci Earthwatch. Kaĝda osoba miaïa wïasny plan pracy oraz indywidualny zakres umiejÚtnoĂci. Opracowanie takiego harmonogramu pracy laboratorium, który zapewniaïby realizacjÚ wszystkich zadañ, byïo peïnoetato- wym zadaniem dla jednej osoby. Z tego powodu postanowiïem napisaÊ w Prologu program do tworzenia harmonogra- mu. Okazaïo siÚ, ĝe ten problem idealnie pasowaï do moĝliwoĂci Prologu. Najpierw zdefiniowaïem zbiór faktów opisujÈcych umiejÚtnoĂci wszystkich czïonków personelu, plan pracy kaĝdego z nich oraz wymagania kaĝdego doĂwiadczenia. Po wykonaniu tych zadañ pozostaïo jedynie powiedzieÊ Prologowi: „zrób to”. Dla kaĝdego zadania wymienionego w doĂwiadczeniu Prolog znalazï dostÚpnÈ osobÚ z odpowiednimi umie- jÚtnoĂciami i przypisaï jÈ do zadania. NastÚpnie kontynuowaï pracÚ tak dïugo, aĝ speï- niï wszystkie potrzeby doĂwiadczenia lub doszedï do wniosku, ĝe ich speïnienie jest niemoĝliwe. JeĂli nie mógï znaleěÊ prawidïowego rozwiÈzania, zaczynaï cofaÊ po- przednie powiÈzania i podejmowaï kolejnÈ próbÚ z innÈ kombinacjÈ. Na koniec albo rozwiÈzanie zostaïo znalezione, albo moĝna byïo wyciÈgnÈÊ wniosek, ĝe ogranicze- nia dla danego doĂwiadczenia sÈ zbyt ostre. Bruce: Czy moĝe pan przytoczyÊ jakieĂ interesujÈce przykïady faktów, reguï lub aser- cji powiÈzanych z delfinami, które miaïyby sens dla naszych czytelników? Brian: PamiÚtam, ĝe byïa jedna bardzo spektakularna sytuacja, kiedy symulowany delfin pomógï nam zrozumieÊ rzeczywiste zachowanie Ake’a. Ake odpowiadaï na jÚzyk gestów zawierajÈcy takie „zdania” jak „skok przez”, czy „prawa piïka ogon dotknij”. DawaliĂmy mu instrukcje, a on reagowaï. Jednym z celów moich badañ byïa próba nauczenia Ake’a nowych sïów, na przykïad „nie”. W tym kontekĂcie zdanie „dotknij nie piïka” oznaczaïo polecenie dotkniÚcia czegokolwiek poza piïkÈ. Dla Ake’a byï to trudny problem do rozwiÈzania. Przez pe- wien czas trening przynosiï dobre rezultaty. Jednak w pewnym momencie Ake zaczÈï chowaÊ siÚ pod wodÈ zawsze, kiedy usïyszaï pewnÈ instrukcjÚ. Nie byliĂmy w stanie Rozdziaï 4. • Prolog  117 tego zrozumieÊ, byïo to bardzo frustrujÈce. Nie moĝesz przecieĝ spytaÊ delfina, dlacze- go coĂ zrobiï. Z tego wzglÚdu zdefiniowaliĂmy zadanie symulatorowi delfina i uzyska- liĂmy interesujÈce wyniki. Chociaĝ delfiny sÈ bardzo inteligentne, zazwyczaj starajÈ siÚ znaleěÊ najprostsze rozwiÈzanie problemu. TÚ samÈ heurystykÚ zastosowaliĂmy w odniesieniu do symulatora. Okazaïo siÚ, ĝe jÚzyk gestów Ake’a zawieraï „sïowo” opisujÈce jedno z okien w zbiorniku. WiÚkszoĂÊ trenerów zapomniaïa o tym sïowie, poniewaĝ korzystano z niego rzadko. Symulator delfina odkryï reguïÚ, zgodnie z którÈ „okno” byïo poprawnÈ odpowiedziÈ na polecenie „nie piïka”. Byïo równieĝ popraw- nÈ odpowiedziÈ na polecenia „nie skok”, „nie rura” i „nie ringo”. ZabezpieczyliĂmy siÚ przed stosowaniem tego schematu dla innych obiektów, zmieniajÈc zbiór obiektów w zbiorniku przy kaĝdej próbie, ale — co oczywiste — nie mogliĂmy usunÈÊ okna. Okazaïo siÚ, ĝe kiedy Ake pïynÈï na dno zbiornika, ustawiaï siÚ obok okna, choÊ ja tego nie mogïem zobaczyÊ. Bruce: Co w Prologu podoba siÚ panu najbardziej? Brian: Model programowania deklaratywnego jest bardzo interesujÈcy. Ogólnie rzecz biorÈc, jeĂli potrafisz opisaÊ problem, to potrafisz go równieĝ rozwiÈzaÊ. W przypad- ku wiÚkszoĂci jÚzyków zdarzaïo mi siÚ w pewnych sytuacjach dyskutowaÊ z kompu- terem. Mówiïem: „Przecieĝ wiesz, co mam na myĂli. Po prostu to zrób!”. Symbolem tego zachowania mogÈ byÊ bïÚdy zgïaszane przez kompilatory jÚzyków C lub C++ w rodzaju „oczekiwano Ărednika”. JeĂli „oczekiwano Ărednika”, to dlaczego go nie wstawiono, by sprawdziÊ, czy to rozwiÈzuje problem? W Prologu moja rola w rozwiÈzaniu problemu planowania sprowadzaïa siÚ do stwier- dzenia „Chciaïbym, aby dzieñ wyglÈdaï w taki oto sposób, zatem zrób to tak”. W od- powiedzi komputer znajdowaï rozwiÈzanie. Bruce: Co sprawiïo panu najwiÚkszy kïopot? Brian: Prolog jest rozwiÈzaniem typu „wszystko albo nic” dla wiÚkszoĂci problemów — przynajmniej tych, z którymi miaïem do czynienia. W przypadku problemu pla- nowania pracy laboratorium zdarzaïo siÚ, ĝe program „myĂlaï” przez 30 minut, po czym albo wyĂwietlaï doskonaïe rozwiÈzanie planu dnia, albo po prostu wyĂwietlaï odpowiedě „no”. W tym przypadku oznaczaïo to zbyt ostre ograniczenia dla danego dnia, takie, które nie pozwalaïy na znalezienie peïnego rozwiÈzania. Prolog nie ofe- ruje niestety rozwiÈzañ czÚĂciowych ani nie informuje o tym, w którym miejscu ogra- niczenia sÈ zbyt ostre. 118  Siedem jÚzyków w siedem tygodni To, co zostaïo zaprezentowane powyĝej, to niezwykle interesujÈca koncepcja. Nie trzeba opisywaÊ sposobu rozwiÈzania problemu. Trzeba jedynie opisaÊ problem. JÚzykiem opisu problemu jest logika — wyïÈcznie logika. Naleĝy okreĂliÊ fakty i re- guïy wnioskowania, a Prolog zajmie siÚ resztÈ. Programy w Prologu sÈ na wyĝszym poziomie abstrakcji w porównaniu do programów w innych jÚzykach. Harmonogra- my i schematy zachowañ to Ăwietne przykïady problemów nadajÈcych siÚ do rozwiÈ- zania za pomocÈ Prologu. Czego nauczyliĂmy siÚ pierwszego dnia? DziĂ nauczyliĂmy siÚ podstawowych bloków budulcowych jÚzyka Prolog. Zamiast kodowania kroków, które prowadziïyby Prolog do znalezienia rozwiÈzania, kodo- waliĂmy wiedzÚ, wykorzystujÈc czystÈ logikÚ. Prolog wykonaï ciÚĝkÈ pracÚ zinter- pretowania tej wiedzy w celu znalezienia rozwiÈzania problemów. LogikÚ naleĝy umieĂciÊ w bazie wiedzy. NastÚpnie wystarczy formuïowaÊ zapytania do tej bazy. Po stworzeniu kilku baz wiedzy skompilowaliĂmy je, a nastÚpnie zadawaliĂmy pytania. Zapytania majÈ dwie formy. Po pierwsze, zapytanie pozwala na okreĂlenie faktów. Prolog poinformuje nas o tym, czy te fakty sÈ prawdziwe, czy faïszywe. NastÚpnie naleĝy utworzyÊ zapytanie zawierajÈce jednÈ lub wiÚcej zmiennych. Prolog obliczy wszystkie moĝliwoĂci wartoĂci zmiennych powodujÈce prawdziwoĂÊ podanych faktów. DowiedzieliĂmy siÚ, ĝe Prolog przetwarza reguïy poprzez analizowanie po kolei klau- zul wybranej reguïy. Dla kaĝdej klauzuli Prolog stara siÚ speïniÊ kaĝdy z celów, pró- bujÈc dobraÊ moĝliwe kombinacje zmiennych. W ten sposób dziaïajÈ wszystkie pro- gramy w Prologu. W kolejnych punktach przeprowadzimy bardziej zïoĝone wnioskowanie. Dowiemy siÚ równieĝ, w jaki sposób wykonywaÊ dziaïania arytmetyczne oraz wykorzystywaÊ bardziej zïoĝone struktury danych, na przykïad listy. Zapoznamy siÚ równieĝ ze stra- tegiami iterowania po listach. Dzieñ 1. Praca do samodzielnego wykonania Poszukaj:  darmowych samouczków Prologu,  forum wsparcia technicznego (dostÚpnych jest kilka),  podrÚcznika online dla uĝywanej wersji Prologu. Rozdziaï 4. • Prolog Wykonaj nastÚpujÈce Êwiczenia:  119  Stwórz prostÈ bazÚ wiedzy. Powinna ona reprezentowaÊ ulubione ksiÈĝki i autorów.  Znajdě w bazie wiedzy wszystkie ksiÈĝki napisane przez jednego autora.  Stwórz bazÚ wiedzy reprezentujÈcÈ muzyków i instrumenty.  Zaprezentuj muzyków oraz gatunek tworzonej przez nich muzyki.  Znajdě wszystkich muzyków, którzy grajÈ na gitarze. 4.3. Dzieñ 2. PiÚtnaĂcie minut do Wapnera ZrzÚdliwy sÚdzia Wapner z programu The People’s Court jest obsesjÈ gïównej po- staci z Rain Mana. Tak jak wiÚkszoĂÊ osób autystycznych Raymond ma obsesjÚ na punkcie znanych postaci. Studiujemy ten enigmatyczny jÚzyk i powoli wszystko za- czyna ukïadaÊ siÚ w caïoĂÊ. ByÊ moĝe jesteĂ jednym ze szczÚĂliwców, którzy rozu- miejÈ wszystko od poczÈtku, ale jeĂli tak nie jest, poproszÚ o cierpliwoĂÊ. Dzisiaj jest rzeczywiĂcie „piÚtnaĂcie minut do Wapnera”. Spokojnie! Potrzeba nam kilku dodatkowych narzÚdzi w przyborniku. Nauczymy siÚ uĝywaÊ rekurencji, operacji arytmetycznych i list. Kontynuujmy naukÚ! Rekurencja Ruby i Io to imperatywne jÚzyki programowania. WymagajÈ zdefiniowania kaĝdego kroku algorytmu. Prolog jest pierwszym jÚzykiem deklaratywnym, którym siÚ zajmu- jemy. Podczas przetwarzania kolekcji elementów, na przykïad list lub drzew, czÚsto korzystamy z rekurencji zamiast iteracji. Zajmiemy siÚ rekurencjÈ i wykorzystamy jÈ do rozwiÈzania pewnych problemów wymagajÈcych prostego wnioskowania. Na- stÚpnie zastosujemy tÚ samÈ technikÚ w odniesieniu do list oraz do wykonywania dziaïañ arytmetycznych. Przyjrzyjmy siÚ bazie danych zamieszczonej poniĝej. Prezentuje ona rozbudowane drzewo rodziny Waltonów — postaci z serialu Waltonowie z roku 1963 oraz ko- lejnych serii. W bazie zdefiniowano relacjÚ ojciec, która sïuĝy do wnioskowania zwiÈzków pomiÚdzy potomkami i przodkami. Poniewaĝ przodek moĝe byÊ ojcem, dziadkiem lub pradziadkiem, powstaje koniecznoĂÊ zagnieĝdĝania reguï bÈdě itera- cji. Poniewaĝ mamy do czynienia z jÚzykiem deklaracyjnym, trzeba zastosowaÊ za- gnieĝdĝanie. Jedna z klauzul w klauzuli przodek bÚdzie wykorzystywaïa klauzulÚ 120  Siedem jÚzyków w siedem tygodni przodek. W tym przypadku przodek(Z, Y) to rekurencyjny cel czÚĂciowy. TreĂÊ bazy wiedzy zamieszczono poniĝej: Pobierz: prolog/rodzina.pl ojciec(zeb, john_boy_sr). ojciec(john_boy_sr, john_boy_jr). przodek(X, Y) :- ojciec(X, Y). przodek(X, Y) :- ojciec(X, Z), przodek(Z, Y). ojciec to zasadniczy zbiór faktów pozwalajÈcych na obliczenie celu czÚĂciowego w sposób rekurencyjny. Reguïa przodek/2 zawiera dwie klauzule. Kiedy reguïa skïa- da siÚ z kilku klauzul, to tylko jedna klauzula musi byÊ prawdziwa, aby caïa reguïa byïa prawdziwa. Potraktujmy przecinki pomiÚdzy celami czÚĂciowymi jako warun- ki and, natomiast kropki pomiÚdzy klauzulami jako warunki or. Pierwsza klauzula mówi „X jest przodkiem Y, jeĂli X jest ojcem Y”. Ta relacja jest oczywista. ReguïÚ tÚ moĝemy wypróbowaÊ w nastÚpujÈcy sposób: | ?- przodek(john_boy_sr, john_boy_jr). true ? no Prolog odpowiedziaï true (prawda): John Boy senior jest przodkiem Johna Boya juniora. Pierwsza klauzula bazuje na prostym fakcie. Druga klauzula jest bardziej zïoĝona: przodek(X, Y) :- ojciec(X, Z), ojciec(Z, Y). Ta klauzula mówi, ĝe X jest przodkiem Y, jeĂli moĝna udowodniÊ, ĝe X jest ojcem Z i jednoczeĂnie ten sam Z jest przodkiem Y. Doskonale! Spróbujmy skorzystaÊ z drugiej klauzuli: | ?- przodek(zeb, john_boy_jr). true ? Tak, zeb jest przodkiem Johna Boya juniora. Moĝna oczywiĂcie spróbowaÊ wyko- rzystaÊ zmienne w zapytaniach. Robi siÚ to w nastÚpujÈcy sposób: | ?- przodek(zeb, Kto). Kto = john_boy_sr ? a Kto = john_boy_jr no Rozdziaï 4. • Prolog  121 Widzimy równieĝ, ĝe zeb jest przodkiem Johna Boya juniora i Johna Boya seniora. Predykat przodek dziaïa takĝe w przeciwnÈ stronÚ: | ?- przodek(Kto, john_boy_jr). Kto = john_boy_sr ? a Kto = zeb (1 ms) no Doskonale! Moĝemy skorzystaÊ z tej reguïy w naszej bazie wiedzy w dwóch celach: by znaleěÊ przodków oraz by znaleěÊ potomków. Krótkie ostrzeĝenie. W przypadku uĝywania rekurencyjnych celów czÚĂciowych trze- ba zachowaÊ ostroĝnoĂÊ. Kaĝdy rekurencyjny cel czÚĂciowy wykorzystuje miejsce na stosie, które w koñcu siÚ wyczerpie. JÚzyki deklaratywne czÚsto rozwiÈzujÈ ten pro- blem za pomocÈ techniki optymalizacji znanej jako rekurencja ogonowa (ang. tail recursion). JeĂli da siÚ umieĂciÊ rekurencyjny cel czÚĂciowy na koñcu reguïy re- kurencyjnej, to Prolog zoptymalizuje wywoïanie — wyeliminuje odwoïanie do stosu i wykorzysta staïÈ z pamiÚci. Nasze wywoïanie jest rekurencjÈ ogonowÈ, poniewaĝ rekurencyjny cel czÚĂciowy przodek(Z, Y) jest ostatnim celem w regule rekurencyjnej. Kiedy w programie w Prologu nastÈpi bïÈd krytyczny spowodowany wyczerpaniem siÚ miejsca na stosie, bÚdzie to znak, ĝe naleĝy poszukaÊ sposobu optymalizacji z wy- korzystaniem rekurencji ogonowej. Po omówieniu tego ostatniego „narzÚdzia w przyborniku” moĝemy przyjrzeÊ siÚ li- stom i krotkom. Listy i krotki Listy i krotki sÈ bardzo waĝnÈ czÚĂciÈ Prologu. ListÚ moĝna okreĂliÊ jako [1, 2, 3], natomiast krotkÚ jako (1, 2, 3). Listy sÈ kontenerami o zmiennym rozmiarze, nato- miast krotki sÈ kontenerami o staïym rozmiarze. MoĝliwoĂci zarówno list, jak i kro- tek stajÈ siÚ bardziej wyraěne, jeĂli pomyĂlimy o nich w kategoriach unifikacji. Unifikacja. CzÚĂÊ 2. Jak pamiÚtamy, kiedy Prolog unifikuje zmienne, próbuje przyrównaÊ do siebie lewÈ i prawÈ stronÚ porównania. Dwie krotki sÈ ze sobÈ zgodne, jeĂli majÈ tÚ samÈ liczbÚ elementów oraz wszystkie one sÈ zunifikowane. Przeanalizujmy kilka przykïadów: 122  Siedem jÚzyków w siedem tygodni | ?- (1, 2, 3) = (1, 2, 3). yes | ?- (1, 2, 3) = (1, 2, 3, 4). no | ?- (1, 2, 3) = (3, 2, 1). no Dwie krotki sÈ zunifikowane, jeĂli wszystkie ich elementy sÈ zunifikowane. Krotki w pierwszym porównaniu pasowaïy do siebie dokïadnie. W drugim nie miaïy tej samej liczby elementów, a w trzecim nie miaïy tych samych elementów w tej samej kolejnoĂci. Spróbujmy wprowadziÊ kilka zmiennych: | ?- (A, B, C) = (1, 2, 3). A = 1 B = 2 C = 3 yes | ?- (1, 2, 3) = (A, B, C). A = 1 B = 2 C = 3 yes | ?- (A, 2, C) = (1, B, 3). A = 1 B = 2 C = 3 yes WïaĂciwie nie ma znaczenia, po której stronie sÈ zmienne. SÈ zunifikowane, jeĂli Prolog moĝe je do siebie dopasowaÊ. Teraz przyjrzyjmy siÚ listom. Jest z nimi po- dobnie jak z krotkami. | ?- [1, 2, 3] = [1, 2, 3]. yes | ?- [1, 2, 3] = [X, Y, Z]. X = 1 Y = 2 Z = 3 yes | ?- [2, 2, 3] = [X, X, Z]. Rozdziaï 4. • Prolog X = 2 Z = 3 yes | ?- [1, 2, 3] = [X, X, Z].  123 no | ?- [] = []. InteresujÈce sÈ dwa ostatnie przykïady. [X, X, Z] i [2, 2, 3] sÈ zunifikowane, po- niewaĝ Prolog moĝe je dopasowaÊ, jeĂli podstawi X = 2. [1, 2, 3] = [X, X, Z] nie sÈ zunifikowane, poniewaĝ wykorzystano X zarówno na pierwszej, jak i na drugiej pozycji, a 1 nie równa siÚ 2. Listy majÈ wïasnoĂÊ, której krotki nie majÈ. Listy moĝna zapisaÊ w postaci [Gïowa|Ogon]. W przypadku unifikacji listy zapisanej za pomocÈ ta- kiej konstrukcji Gïowa zostanie powiÈzana z pierwszym elementem listy, a Ogon z caïÈ resztÈ, w nastÚpujÈcy sposób: | ?- [a, b, c] = [Gïowa|Ogon]. Gïowa = a Ogon = [b,c] yes Wyraĝenie [Gïowa|Ogon] nie zunifikuje siÚ z pustÈ listÈ. Jednoelementowa lista daje siÚ jednak prawidïowo dopasowaÊ: | ?- [] = [Gïowa|Ogon]. no | ?- [a] = [Gïowa|Ogon]. Gïowa = a Ogon = [] yes Oto kilka bardziej zïoĝonych kombinacji: | ?- [a, b, c] = [a|Ogon]. Ogon = [b,c] (1 ms) yes Prolog dopasowaï wartoĂÊ a i zunifikowaï resztÚ listy z listÈ Ogon. Uzyskany w ten sposób ogon takĝe moĝna rozdzieliÊ na gïowÚ i ogon: | ?- [a, b, c] = [a|[Gïowa|Ogon]]. Gïowa = b Siedem jÚzyków w siedem tygodni 124  Ogon = [c] yes Spróbujmy pobraÊ trzeci element: | ?- [a, b, c, d, e] = [_, _|[Gïowa|_]]. Gïowa = c yes Znak podkreĂlenia (_) jest symbolem wieloznacznym, który unifikuje siÚ z dowolnÈ wartoĂciÈ. Ogólnie rzecz biorÈc, oznacza on „nie interesuje mnie, co znajdzie siÚ na tej pozycji”. PoinstruowaliĂmy Prolog, aby pominÈï pierwsze dwa elementy, a resztÚ podzieliï na gïowÚ i ogon. Z czïonem Gïowa bÚdzie powiÈzany trzeci element, a koñ- cowy symbol _ oznacza ogon, zatem pozostaïa czÚĂÊ listy zostanie zignorowana. To powinno wystarczyÊ na poczÈtek. Unifikacja jest potÚĝnym narzÚdziem, a uĝy- wanie jej w poïÈczeniu z listami i krotkami jeszcze zwiÚksza te moĝliwoĂci. W tym momencie czytelnicy powinni znaÊ zasadnicze struktury danych w Prologu, a takĝe sposoby dziaïania unifikacji. JesteĂmy teraz gotowi, aby poïÈczyÊ te elemen- ty z reguïami i asercjami w celu wykonywania dziaïañ matematycznych na wyraĝe- niach logicznych. Arytmetyka list W ramach naszego kolejnego przykïadu postanowiïem zaprezentowaÊ sposób wyko- rzystywania rekurencji i arytmetyki w celu wykonywania dziaïañ na listach. Poniĝ- sze przykïady sïuĝÈ do zliczania elementów oraz obliczania podsumowañ i Ărednich. CaïÈ ciÚĝkÈ pracÚ wykonuje piÚÊ reguï. Pobierz: prolog/arytmetyka_list.pl policz(0, []). policz(LiczbaElementów, [Gïowa|Ogon]) :- policz(LiczbaElementówOgona, Ogon), :- LiczbaElementów is LiczbaElementówOgona + 1. suma(0, []). suma(Suma’Ècznie, [Gïowa|Ogon]) :- suma(Suma, Ogon), Suma’Ècznie is Gïowa + Suma. Ărednia(¥rednia, Lista) :- suma(Suma, Lista), policz(LiczbaElementów, Lista), ¥rednia is :- Suma/LiczbaElementów. Najprostszym przykïadem jest predykat policz. Moĝna go wykorzystaÊ w nastÚpu- jÈcy sposób: Rozdziaï 4. • Prolog | ?- policz(Co, [1]). Co = 1 ? ;  125 no Reguïy sÈ trywialnie proste. Liczba elementów pustej listy wynosi 0. Liczba elemen- tów niepustej listy jest równa liczbie elementów ogona plus jeden. Przeanalizujmy krok po kroku, jak to dziaïa.  WprowadziliĂmy zapytanie policz(Co, [1]), które nie moĝe zostaÊ zunifi- kowane z pierwszÈ reguïÈ, poniewaĝ lista nie jest pusta. W zwiÈzku z tym przechodzimy do sprawdzenia celów drugiej reguïy: policz(LiczbaElementów, [Gïowa|Ogon]). NastÚpuje unifikacja, powiÈzanie zmiennej Co ze zmiennÈ LiczbaElementów, zmiennej Gïowa z wartoĂciÈ 1 i zmiennej Ogon z wartoĂciÈ [].  Po unifikacji pierwszym celem jest policz(LiczbaElementówOgona, []). Stara- my siÚ udowodniÊ cel czÚĂciowy. Tym razem unifikujemy z pierwszÈ regu- ïÈ. WiÈĝemy zmiennÈ LiczbaElementówOgona z wartoĂciÈ 0. Pierwsza reguïa jest teraz speïniona. Moĝemy zatem przejĂÊ do kolejnego celu.  Teraz wyznaczamy wartoĂÊ wyraĝenia LiczbaElementów is LiczbaElementów- Ogona + 1. Moĝemy zunifikowaÊ zmienne. ZmiennÈ LiczbaElementówOgona wiÈĝemy z wartoĂciÈ 0, a zatem zmienna LiczbaElementów ma wartoĂÊ 0 + 1, czyli 1. To wszystko. Nie definiowaliĂmy procesu rekurencyjnego. DefiniowaliĂmy tylko reguïy logiczne. NastÚpny przykïad dotyczy sumowania elementów listy. Oto kod tych reguï: suma(0, []). suma(Suma’Ècznie, [Gïowa|Ogon]) :- suma(Suma, Ogon), Suma’Ècznie is Gïowa + Suma. Powyĝszy kod dziaïa identycznie jak reguïa liczenia elementów. Takĝe zawiera dwie klauzule — przypadek bazowy i przypadek rekurencyjny. Sposób uĝycia tej reguïy jest podobny: | ?- suma(Co, [1, 2, 3]). Co = 6 ? ; no JeĂli spojrzymy na to z punktu widzenia jÚzyka imperatywnego, dojdziemy do wniosku, ĝe reguïa suma dziaïa dokïadnie tak, jak naleĝaïoby oczekiwaÊ w jÚzyku rekurencyjnym. 126  Siedem jÚzyków w siedem tygodni WartoĂÊ reguïy suma pustej listy wynosi zero. W pozostaïych przypadkach suma jest równa wartoĂci Gïowa plus suma z Ogon. Moĝna to jednak zinterpretowaÊ inaczej. Nie powiedzieliĂmy Prologowi, w jaki spo- sób oblicza siÚ sumy. OpisaliĂmy jedynie sumy w postaci reguï i celów. Speïnienie pewnych celów wymaga od maszyny wnioskujÈcej speïnienia pewnych celów czÚĂcio- wych. Interpretacja deklaratywna jest nastÚpujÈca: „Suma pustej listy wynosi zero, natomiast suma wszystkich elementów na liĂcie ma wartoĂÊ Suma’Ècznie, jeĂli moĝna udowodniÊ, ĝe suma ogona i gïowy wynosi Suma’Ècznie”. ZastÈpiliĂmy rekurencjÚ pojÚciem dowodzenia celów i celów czÚĂciowych. Dziaïanie reguïy policz moĝna wy- jaĂniÊ podobnie: liczba elementów pustej listy wynosi zero. Liczba elementów nie- pustej listy wynosi jeden (liczba elementów gïowy) plus liczba elementów ogona. Tak jak zwykle w przypadku logiki, reguïy mogÈ bazowaÊ na innych reguïach. Na przykïad moĝemy uĝyÊ reguïy suma razem z reguïÈ policz w celu obliczenia Ăredniej: Ărednia(¥rednia, Lista) :- suma(Suma, Lista), policz(Policz, Lista), ¥rednia is Suma/Policz. A zatem Ărednia argumentu Lista wynosi ¥rednia, jeĂli moĝna udowodniÊ, ĝe:  suma tego argumentu Lista wynosi Suma.  WartoĂÊ policz tego argumentu Lista wynosi Policz.  ¥rednia wynosi Suma/Policz. Powyĝszy kod dziaïa zgodnie z oczekiwaniami: | ?- Ărednia(Co, [1, 2, 3]). Co = 2.0 ? ; no Wykorzystywanie reguï w dwóch kierunkach W tym momencie czytelnik powinien mieÊ doĂÊ wyraěny obraz dziaïania rekurencji. W tym punkcie trochÚ „pozmieniam biegi” i omówiÚ reguïÚ append. Reguïa append (Lista1, Lista2, Lista3) jest prawdziwa, jeĂli lista Lista3 jest sumÈ list Lista1 + Lista2. To interesujÈca reguïa, którÈ moĝna wykorzystywaÊ na róĝne sposoby. Ta niepozorna reguïa daje wiele moĝliwoĂci. Moĝna jÈ wykorzystywaÊ na wiele róĝ- nych sposobów. Jako wykrywacz kïamstwa: | ?- append([olej], [woda], [olej, woda]). yes Rozdziaï 4. • Prolog  127 | ?- append([olej], [woda], [olej, smar]). no Jako narzÚdzie do tworzenia list. | ?- append([piwo], [szampan], Co). Co = [piwo,szampan] yes Do odejmowania list: | ?- append([przybranie_deseru], Kto, [przybranie_deseru, pasta_do_podïogi]). Kto = [pasta_do_podïogi] yes Do obliczania moĝliwych permutacji: | ?- append(Jeden, Dwa, [jabïka, pomarañcze, banany]). Dwa = [jabïka, pomarañcze, banany] ? a Jeden = [] ? a Dwa = [pomarañcze, banany] Jeden = [jabïka] Dwa = [banany] Jeden = [jabïka, pomarañcze] Dwa = [] Jeden = [jabïka, pomarañcze, banany] (15 ms) no Jak widaÊ, jedna reguïa daje nam cztery. Na pierwszy rzut oka wydaje siÚ, ĝe utwo- rzenie takiej reguïy wymaga duĝej iloĂci kodu. Spróbujmy siÚ dowiedzieÊ ile. Posta- ramy siÚ napisaÊ samodzielnie reguïÚ Prologu append, ale nazwiemy jÈ po swojemu — doïÈcz. Zadanie wykonamy w kilku krokach: 1. Napiszemy reguïÚ o nazwie doïÈcz(Lista1, Lista2, Lista3) umoĝliwiajÈcÈ doïÈczenie pustej listy do listy Lista1. 2. Dodamy reguïÚ, która doïÈcza jeden element z listy Lista1 do listy Lista2. 3. Dodamy reguïÚ, która doïÈcza drugi i trzeci element z listy Lista1 do listy Lista2. 4. Spróbujemy wprowadziÊ uogólnienia. 128  Siedem jÚzyków w siedem tygodni A wiÚc do dzieïa. Pierwsza czynnoĂÊ polega na doïÈczeniu pustej listy do listy Lista2. Napisanie reguïy, która jest potrzebna do osiÈgniÚcia tego celu, nie jest trudne. Pobierz: prolog/dolacz_krok1.pl doïÈcz([], Lista, Lista). ¿adnych problemów. Reguïa doïÈcz jest prawdziwa, jeĂli pierwszy parametr jest listÈ, a nastÚpne dwa parametry sÈ takie same. To dziaïa. | ?- doïÈcz([], [heniek], Co). Co = [heniek] yes Przejděmy do nastÚpnego kroku. Dodamy reguïÚ, która doïÈcza pierwszy element z listy Lista1 na poczÈtek listy Lista2. Pobierz: prolog/dolacz_krok2.pl doïÈcz([], Lista, Lista). doïÈcz([Gïowa|[]], Lista, [Gïowa|Lista]). Aby napisaÊ reguïÚ doïÈcz(Lista1, Lista2, Lista3), rozbijemy listÚ Lista1 na gïowÚ i ogon, przy czym ogon bÚdzie pustÈ listÈ. Trzeci element rozbijemy na gïowÚ i ogon, wykorzystujÈc gïowÚ listy Lista1 oraz listÚ Lista2 jako ogon. PamiÚtajmy o skompi- lowaniu bazy wiedzy. Dziaïa bez zarzutu: | ?- doïÈcz([malfoy], [potter], Co). Co = [malfoy,potter] yes Moĝemy teraz zdefiniowaÊ kolejnych kilka reguï opisujÈcych ïÈczenie list o dïugo- Ăciach 2 i 3 elementów. DziaïajÈ one w taki sam sposób: Pobierz: prolog/dolacz_krok3.pl doïÈcz([], Lista, Lista). doïÈcz([Gïowa|[]], Lista, [Gïowa|Lista]). doïÈcz([Gïowa1|[Gïowa2]|[]]], Lista, [Gïowa1| Gïowa2|Lista]). doïÈcz([Gïowa1|[Gïowa2]|[Gïowa3|[]]]], Lista, [Gïowa1, Gïowa2, Gïowa3|Lista]). | ?- doïÈcz([malfoy, granger], [potter], Co). Cot = [malfoy,granger,potter] yes Rozdziaï 4. • Prolog  129 Mamy tu przypadek bazowy oraz strategiÚ, zgodnie z którÈ kaĝdy cel czÚĂciowy zmniejsza liczbÚ elementów na pierwszej liĂcie i rozszerza trzeciÈ listÚ. Druga lista pozostaje staïa. Mamy teraz wystarczajÈco duĝo informacji, by spróbowaÊ uogólniÊ wyniki. Poniĝej reguïa doïÈcz zdefiniowana z wykorzystaniem reguï zagnieĝdĝonych: Pobierz: prolog/dolacz.pl doïÈcz([], Lista, Lista). doïÈcz([Gïowa|Ogon1], Lista, [Gïowa|Ogon2]) :- doïÈcz(Ogon1, Lista, Ogon2). ObjaĂnienie tego niewielkiego fragmentu kodu jest niezwykle proste. Pierwsza klau- zula mówi, ĝe w wyniku doïÈczenia pustej listy do argumentu Lista otrzymujemy tÚ samÈ wartoĂÊ argumentu Lista. Druga klauzula mówi, ĝe doïÈczenie listy Lista1 do listy Lista2 daje w wyniku listÚ Lista3 w przypadku, gdy gïowy list Lista1 i Lista3 sÈ takie same oraz moĝna udowodniÊ, ĝe w wyniku scalenia listy Lista1 z listÈ Lista2 otrzymamy ogon listy Lista3. Prostota i elegancja tego rozwiÈzania sÈ testamentem moĝliwoĂci Prologu. Zobaczmy, co siÚ dzieje w zapytaniu doïÈcz([1,2],[3], Co). Dla kaĝdego kroku prze- analizujemy unifikacje. PamiÚtajmy o tym, ĝe zagnieědziliĂmy reguïy, zatem przy kaĝdej próbie udowodnienia celu czÚĂciowego mamy innÈ kopiÚ zmiennych. Najwaĝ- niejsze miejsca oznaczyïem literami. DziÚki temu moĝna z ïatwoĂciÈ ĂledziÊ przykïad. W kaĝdym przebiegu pokaĝÚ, co siÚ bÚdzie dziaïo w czasie, kiedy Prolog podejmie próbÚ udowodnienia kolejnego celu czÚĂciowego.  Rozpoczynamy od nastÚpujÈcej reguïy: doïÈcz([1,2], [3], Co)  Pierwsza reguïa nie jest speïniona, poniewaĝ [1, 2] nie jest pustÈ listÈ. Uni- fikujemy jÈ w nastÚpujÈcy sposób: doïÈcz([1|[2]], [3], [1|Ogon2-A]) :- doïÈcz([2], [3], [Ogon2-A]) Unifikacja wszystkich czïonów poza drugim przebiegïa pomyĂlnie. Przejdě- my teraz do celów. Unifikujemy prawÈ stronÚ.  Spróbujemy zunifikowaÊ reguïÚ doïÈcz([2], [3], [Ogon2-A]). W efekcie otrzymujemy: doïÈcz([2|[ ]], [3], [2|Ogon2-B]) :- doïÈcz([ ], [3], Ogon2-B) ZwróÊmy uwagÚ, ĝe Ogon2-B jest ogonem listy Ogon2-A. Nie jest to ta sama lista co poczÈtkowa lista Ogon2. Teraz jednak musimy ponownie zunifiko- waÊ prawÈ stronÚ. doïÈcz([ ], [3], Ogon2-C) :- doïÈcz([ ], [3], [3]) . 130  Siedem jÚzyków w siedem tygodni  Wiemy zatem, ĝe Tail2-C ma wartoĂÊ [3]. Moĝemy teraz pójĂÊ w górÚ ïañ- cucha. Przyjrzyjmy siÚ trzeciemu parametrowi, który na kaĝdym kroku do- ïÈcza listÚ Ogon2. Ogon2-C ma wartoĂÊ [3], co oznacza, ĝe [2|Ogon2-2] to li- sta [2, 3] i na koniec [1|Ogon2] to lista [1, 2, 3]. Zmienna Co ma wartoĂÊ [1, 2, 3]. Prolog wykonaï tu mnóstwo pracy. RadzÚ analizowaÊ tÚ listÚ tak dïugo, aĝ wszyst- ko stanie siÚ zrozumiaïe. Unifikowanie zagnieĝdĝonych celów czÚĂciowych to pod- stawowa umiejÚtnoĂÊ — niezbÚdna do rozwiÈzywania zaawansowanych problemów w niniejszej ksiÈĝce. PrzestudiowaliĂmy wïaĂnie jednÈ z najwaĝniejszych funkcji Prologu. PoĂwiÚÊmy tro- chÚ czasu na analizÚ rozwiÈzañ w taki sposób, aby staïy siÚ zrozumiaïe. Czego nauczyliĂmy siÚ drugiego dnia? W tym punkcie zajÚliĂmy siÚ podstawowymi blokami budulcowymi wykorzystywa- nymi w Prologu do organizowania danych: listami i krotkami. StudiowaliĂmy takĝe zagnieĝdĝanie reguï pozwalajÈce na przedstawienie problemów, które w innych jÚ- zykach rozwiÈzuje siÚ za pomocÈ instrukcji iteracyjnych. PrzyjrzeliĂmy siÚ dokïad- niej unifikacji oraz sposobowi dziaïania Prologu podczas porównywania obu stron operatorów :- lub =. PrzekonaliĂmy siÚ, ĝe piszÈc reguïy, opisujemy zasady logiczne, a nie algorytmy. To Prolog wypracowuje rozwiÈzanie. PokazaliĂmy równieĝ, w jaki sposób wykorzystuje siÚ dziaïania arytmetyczne. Dowie- dzieliĂmy siÚ, jak wykorzystuje siÚ podstawowe dziaïania arytmetyczne i zagnieĝdĝo- ne cele czÚĂciowe do obliczania podsumowañ i Ărednich. Na koniec pokazaliĂmy, w jaki sposób wykorzystuje siÚ listy. ZaprezentowaliĂmy, jak dopasowaÊ jednÈ bÈdě kilka zmiennych z listÈ, ale co waĝniejsze, pokazaliĂmy, w jaki sposób moĝna dopasowaÊ ze zmiennymi gïowÚ listy wraz z jej pozostaïymi elementami, uĝywajÈc wzorca [Gïowa|Ogon]. WykorzystaliĂmy tÚ technikÚ do rekuren- cyjnego iterowania po listach. Poznane bloki budulcowe bÚdÈ nam sïuĝyÊ jako baza do rozwiÈzywania zïoĝonych problemów, z którymi spotkamy siÚ trzeciego dnia. Dzieñ 2. Praca do samodzielnego wykonania Poszukaj:  Implementacji algorytmów do wyznaczania ciÈgu Fibonacciego i oblicza- nia silni. W jaki sposób one dziaïajÈ? Rozdziaï 4. • Prolog  131  SpoïecznoĂci uĝytkowników Prologu. Do rozwiÈzywania jakich problemów czïonkowie tej spoïecznoĂci uĝywajÈ Prologu? Czytelnicy poszukujÈcy bardziej zaawansowanych zadañ mogÈ przeanalizowaÊ na- stÚpujÈce problemy:  ImplementacjÚ Wieĝy Hanoi. W jaki sposób dziaïa algorytm rozwiÈzania tego zadania?  Jakie problemy mogÈ wystÚpowaÊ podczas posïugiwania siÚ wyraĝeniami zanegowanymi? Dlaczego naleĝy zachowaÊ ostroĝnoĂÊ, posïugujÈc siÚ taki- mi wyraĝeniami w Prologu? Wykonaj nastÚpujÈce zadania:  Odwracanie elementów listy.  Wyszukiwanie najmniejszego elementu na liĂcie.  Sortowanie elementów listy. 4.4. Dzieñ 3. PodbiÊ Vegas Czytelnicy powinni teraz lepiej rozumieÊ powody, dla których porównaïem Prolog do Rain Mana, autystycznego geniusza. ChoÊ czasami trudno to zrozumieÊ, wspa- niale jest myĂleÊ o programowaniu w taki sposób. Jednym z moich ul
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Siedem języków w siedem tygodni. Praktyczny przewodnik nauki języków programowania
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: