Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:prolog:prolog_lab:listy1 [2010/03/17 18:22] ikaf |
pl:prolog:prolog_lab:listy1 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 69: | Linia 69: | ||
| <code prolog> | <code prolog> | ||
| ?- porownaj([a,b,c,d]). | ?- porownaj([a,b,c,d]). | ||
| - | No | + | false |
| ?- porownaj([a,b,c,c]). | ?- porownaj([a,b,c,c]). | ||
| - | Yes | + | true |
| </code> | </code> | ||
| Linia 78: | Linia 78: | ||
| ?- zamien([a,b,c,d],X). | ?- zamien([a,b,c,d],X). | ||
| X=[a,b,d,c] | X=[a,b,d,c] | ||
| - | Yes | + | true |
| </code> | </code> | ||
| Linia 334: | Linia 334: | ||
| ?- odwroc([a,b,c,d],[d,c,b,a]). | ?- odwroc([a,b,c,d],[d,c,b,a]). | ||
| </code> | </code> | ||
| - | ===== -. Dzielenie list ===== | ||
| - | <code prolog> | ||
| - | podziel(L,Idx,L1,L2):- | ||
| - | Idx >= 0, | ||
| - | dlugosc(L,Dlugosc), | ||
| - | Dlugosc1 = Idx, | ||
| - | Dlugosc2 is Dlugosc - Idx, | ||
| - | Dlugosc2 >= 0, | ||
| - | dlugosc(L1,Dlugosc1), | ||
| - | dlugosc(L2,Dlugosc2), | ||
| - | sklej(L1,L2,L),!. | ||
| - | </code> | ||
| - | |||
| - | **Ćwiczenie** | ||
| - | |||
| - | Dopisać predykat ''podziel'' do pliku //listy-1.pl// | ||
| - | |||
| - | Sprawdzić i przemyśleć działanie poniższych: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- podziel([a,b,c,d],4,L1,L2). | ||
| - | ?- podziel([a,b,c,d],0,L1,L2). | ||
| - | ?- podziel([a,b,c,d],3,L1,L2). | ||
| - | </code> | ||
| ===== -. Listy a napisy ===== | ===== -. Listy a napisy ===== | ||
| Linia 376: | Linia 352: | ||
| put(H), wypisz(T). | put(H), wypisz(T). | ||
| wypisz([]). | wypisz([]). | ||
| + | </code> | ||
| + | |||
| + | |||
| + | Inna sytuacja: Przykład wykorzystania wbudowanych predykatów ''name'' i ''append'' do przekształcania napisów. | ||
| + | Predykat ''plural(Noun, Pl)'' - przekształca rzeczownik regularny języka angielskiego z liczby pojedynczej na liczbę mnogą. | ||
| + | <code prolog> | ||
| + | plural(Noun, PL) :- | ||
| + | name(Noun, L), | ||
| + | name(s,T), | ||
| + | append(L,T, NL), | ||
| + | name(PL, NL). | ||
| </code> | </code> | ||
| Linia 394: | Linia 381: | ||
| </code> | </code> | ||
| - | Dopisać predykat ''wypisz'' do pliku //listy-1.pl// | + | Dopisać predykaty ''wypisz'' i ''plural'' do pliku //listy-1.pl// |
| Sprawdzić i przemyśleć działanie poniższych: | Sprawdzić i przemyśleć działanie poniższych: | ||
| Linia 404: | Linia 391: | ||
| </code> | </code> | ||
| + | |||
| + | <code prolog> | ||
| + | ?- plural(day,PL). | ||
| + | </code> | ||
| + | |||
| + | |||
| ===== Dla Zainteresowanych ===== | ===== Dla Zainteresowanych ===== | ||
| + | |||
| + | ==== Minecraft ==== | ||
| + | Zastanówmy się nad próbą implementacji prostej gry typu [[http://pl.wikipedia.org/wiki/Minecraft|Minecraft]]. Kluczowym elementem gry jest silnik wokselowy, który odpowiada za renderowania ogromnego świata przy użyciu prostych klocków zwanych [[http://pl.wikipedia.org/wiki/Woksel|wokselami]]. Zaczniemy od rysowania przykładowego woksela. Proszę uruchomić program {{:pl:prolog:prolog_lab:cuboid.pl|}} (wymagane XPCE) i przeanalizować jego działanie. | ||
| + | |||
| + | <code prolog> | ||
| + | ?- cuboid(2,2,2). | ||
| + | </code> | ||
| + | |||
| + | Następnie proszę zapoznać się z kodem odpowiadającym za animację {{:pl:prolog:prolog_lab:animation.pl|}}: | ||
| + | |||
| + | <code prolog> | ||
| + | ?- sm. | ||
| + | </code> | ||
| + | |||
| + | Zadania: | ||
| + | - Przerobić predykat ''cuboid'' tak, żeby można było sprecyzować jego pozycję w przestrzeni | ||
| + | - Napisać predykat ''cuboids'', który przyjmuje listę współrzędnych i rysuje w nich sześciany o zadanej długości boku | ||
| + | - Przy pomocy predykatu ''cuboids'' należy zamodelować [[http://i.ytimg.com/vi/u1bX8kEy0pg/maxresdefault.jpg?|złożony obiekt ze świata Minecraft]] | ||
| + | - Bazując na kodzie z ''animation.pl'' należy wprawić krowę w ruch sinusoidalny, imitujący [[https://www.youtube.com/watch?v=QH2-TGUlwu4|kota z filmu]] | ||
| + | - [Dla odważnych] dodać do animacji [[https://archive.org/details/nyannyannyan|dźwięk]] podobny do tego z [[https://www.youtube.com/watch?v=QH2-TGUlwu4|filmu]] | ||
| + | |||
| + | Pytania: | ||
| + | - Czy rozsądne jest rysowanie wszystkich klocków? Jak wykryć, które klocki są widoczne z perspektywy gracza? Pomocny może okazać się [[http://et1337.com/2015/02/18/the-poor-mans-voxel-engine/#|link]] | ||
| + | - Czy możliwe jest zrobienie w podobny sposób imitacji poniższego [[http://goo.gl/YroZm|filmu]]? | ||
| + | |||
| ==== Efektywność odwracania list ==== | ==== Efektywność odwracania list ==== | ||
| Linia 427: | Linia 445: | ||
| Rezultat: Znaczna poprawa efektywności. Przykładowo dla 8-elementowej listy predykat wykorzystujący sklej wykonuje 90 kroków, zaś używający akumulatora - 20. --- //[[ikaf@student.agh.edu.pl|Weronika Furmańska]] 2008/10/29 13:33// | Rezultat: Znaczna poprawa efektywności. Przykładowo dla 8-elementowej listy predykat wykorzystujący sklej wykonuje 90 kroków, zaś używający akumulatora - 20. --- //[[ikaf@student.agh.edu.pl|Weronika Furmańska]] 2008/10/29 13:33// | ||
| + | ==== Listy różnicowe ==== | ||
| + | |||
| + | Dużą bolączką operacji na listach w Prologu (jak też w innych językach programowania, które wymuszają przechodzenie po elementach listy od lewej do prawej, np. Haskell) jest nieefektywność operacji działających na końcu listy. Sztandarowym przykładem takiej operacji jest łączenie dwóch list, vel. predykat sklej/3 implementowany na tych laboratoriach — rezolucja musi w nim przejść kolejno po wszystkich elementach pierwszej listy; złożoność czasowa jest zatem liniowa i przy częstym sklejaniu list znacząco spowalnia działanie programu. | ||
| + | |||
| + | Standardowym rozwiązaniem problemu są listy różnicowe (ang. //difference lists//), które reprezentują jedną listę jako **różnicę między dwiema listami**. Różnicę rozumiemy jako odjęcie elementów z drugiej listy od końca pierwszej listy, np. lista <code prolog>[a,b,c].</code> może być reprezentowana równoważnie przez wszystkie poniższe pary list: | ||
| + | <code prolog> | ||
| + | [a,b,c,d,e],[d,e]. | ||
| + | [a,b,c,d,e,f],[d,e,f]. | ||
| + | [a,b,c],[]. | ||
| + | [a,b,c|[d,e,f,g]],[d,e,f,g]. | ||
| + | [a,b,c|[]],[]. | ||
| + | [a,b,c|End],End. | ||
| + | </code> | ||
| + | Szczególnie interesująca jest ostatnia linijka ze względu na swoją ogólność. Każdą listę ''[L]'' można przedstawić jako parę ''[L|End]'',''End''. Kiedy ''End'' jest zmienną bez przypisanej wartości, listę o takiej postaci nazywamy otwartą (ang. //open list//). Z proceduralnego punktu widzenia zmienna ''End'' jest "wskaźnikiem" na koniec listy ''L''; unifikując z ''End'' inną listę, wstawiamy jej elementy na koniec listy ''L''. Poniżej przedstawiony jest predykat ''sklej_roznicowo/3'', który wykonuje tę operację (uwaga: operator '''-''' służy tutaj jedynie grupowaniu argumentów; parę ''[L|End]'', ''End'' zapiszemy jako ''[L|End] - End''). | ||
| + | <code prolog> | ||
| + | sklej_roznicowo(L - End, End, L). | ||
| + | </code> | ||
| + | Poniżej przykład wywołania predykatu: | ||
| + | <code prolog> | ||
| + | ?:- sklej_roznicowo([a,b,c|End]-End,[d,e,f],Wynik). | ||
| + | End = [d, e, f], | ||
| + | Wynik = [a, b, c, d, e, f]. | ||
| + | </code> | ||
| + | |||
| + | Predykat ten różni się od tego implementowanego na zajęciach pod względem złożoności obliczeniowej; ''sklej_roznicowo'' nigdy nie wchodzi w rekurencję, wykonuje jedynie jedną unifikację, ma więc stałą złożoność obliczeniową. | ||
| + | |||
| + | Idąc dalej, jeżeli ustalimy, że argumentami ''sklej_roznicowo'' mogą być jedynie listy różnicowe w postaci par ''L - End'', możemy go przepisać do poniższej, interesującej postaci: | ||
| + | |||
| + | <code prolog> | ||
| + | sklej_roznicowo(L - End, End - End2, L - End2). | ||
| + | </code> | ||
| + | Poniżej przykład wywołania predykatu: | ||
| + | <code prolog> | ||
| + | ?:- sklej_roznicowo([a,b,c|End]-End,[d,e,f|End2]-End2,Wynik). | ||
| + | End = [d, e, f|End2], | ||
| + | Wynik = [a, b, c, d, e, f|End2]-End2. | ||
| + | </code> | ||
| + | |||
| + | Podczas wywołania Prolog unifikuje koniec pierwszej listy z drugą listą, zapamiętując przy tym koniec drugiej listy --- dzięki temu lista wynikowa ''Wynik'' w parze z ''End2'' stanowi kolejną listę różnicową, do której łatwo dołożyć kolejne elementy. | ||
| + | |||
| + | == Do przećwiczenia: == | ||
| + | |||
| + | * przetestować predykat ''sklej_roznicowo/3''; | ||
| + | * spróbować zastąpić predykat ''sklej/3'' predykatem ''sklej_roznicowo/3'' w predykatach zaimplementowanych na zajęciach; | ||
| + | * zastanowić się, jakie przewagi ma ''sklej/3'' nad ''sklej_roznicowo/3''; | ||
| + | * przepisać wybrany predykat z zajęć (poza ''sklej/3'') na wersję korzystającą z list różnicowych. | ||
| + | |||
| + | == Do poczytania: == | ||
| + | |||
| + | * [[http://en.wikipedia.org/wiki/Difference_list|Lista różnicowa na en.wikipeda]]; | ||
| + | * [[http://en.wikibooks.org/wiki/Prolog/Difference_Lists|Lista różnicowa w Prologu na en.wikibooks]]; | ||
| + | * [[http://stackoverflow.com/a/20441480|Pytanie o listy różnicowe na Stackoverflow]]; | ||
| + | * [[http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html|Otwarte i różnicowe listy w ambitnym kursie Prologa]]. | ||
| + | |||
| + | |||
| + | | ||
| + | |||
| + | --- //[[mateusz.slazynski@agh.edu.pl|Mateusz Ślażyński]] 2014/03/17 13:58// | ||
| ===== Komentarze ===== | ===== Komentarze ===== | ||
| Linia 432: | Linia 508: | ||
| --- //[[gjn@agh.edu.pl|Grzegorz J. Nalepa]] 2008/02/20 14:34// | --- //[[gjn@agh.edu.pl|Grzegorz J. Nalepa]] 2008/02/20 14:34// | ||
| - | |||
| - | |||
