Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

Both sides previous revision Poprzednia wersja
Nowa wersja
Poprzednia wersja
pl:prolog:prolog_lab:listy1 [2009/02/24 14:56]
holownia
pl:prolog:prolog_lab:listy1 [2019/06/27 15:50] (aktualna)
Linia 58: Linia 58:
 </​code>​ </​code>​
  
-Wybieranie ​wybranego ​elementu:+Wybieranie elementu:
  
-  ​trzeci([A,​B,​C|Reszta],​C).+<code prolog>​ 
 +trzeci([A,​B,​C|Reszta],​C). 
 +</​code>​
  
 Zdefiniować predykat porównujący 2 wybrane elementy listy, np. 3. i 4. Zdefiniować predykat porównujący 2 wybrane elementy listy, np. 3. i 4.
  
-Zdefiniować predykat zamieniający 2 wybrane elementy listynp3. i 4.+Przykład użycia: 
 +<code prolog>​ 
 +?- porownaj([a,b,c,d]). 
 +false 
 +?- porownaj([a,​b,​c,​c]). 
 +true 
 +</​code>​
  
 +Zdefiniować predykat zamieniający 2 wybrane elementy listy, np. 3. i 4.
 +<code prolog>
 +?- zamien([a,​b,​c,​d],​X).
 +X=[a,b,d,c]
 +true
 +</​code>​
  
 ===== -. Przynależność do listy ===== ===== -. Przynależność do listy =====
Linia 114: Linia 128:
 ===== -. Rekurencyjna analiza list ===== ===== -. Rekurencyjna analiza list =====
  
-(źródło: [[http://www.coli.uni-saarland.de/~kris/​learn-prolog-now/​html/​node35.html#​sec.l4.rdal|LearnPrologNow]])+(źródło: [[http://cs.union.edu/~striegnk/​learn-prolog-now/​html/​node35.html#​sec.l4.rdal|LearnPrologNow]])
  
 <code prolog> <code prolog>
Linia 139: Linia 153:
 </​code>​ </​code>​
  
-Uwaga: ten predykat robi "coś ciekawego"​ na listach zaczynających się od ''​a''​ i ''​b''​!+Uwaga: ten predykat robi "coś ciekawego" ​tylko na listach zaczynających się od ''​a''​ i ''​b''​!
  
  
Linia 230: Linia 244:
 ?- usun(1,​X,​[a,​b,​c,​d]). ?- usun(1,​X,​[a,​b,​c,​d]).
 </​code>​ </​code>​
 +
 +Proszę znajdywać wszystkie rozwiązania (;).
  
 Uwaga: dopisać i przetestować predykat: Uwaga: dopisać i przetestować predykat:
Linia 336: 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 354: 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 364: 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 ====
-  * Predykat podany w sekcji [[#​odwracanie_list|odwracanie list]], tzw. naiwny, używa predykatu sklej, co powoduje jego nieefektywność. Innym rozwiązaniem jest użycie tzw. akumulatora,​ w którym przechowujemy budowaną na bieżąco listę. Opis procedury: http://www.coli.uni-saarland.de/~kris/​learn-prolog-now/​html/​node51.html#​subsec.l6.reverse.acc+  * Predykat podany w sekcji [[#​odwracanie_list|odwracanie list]], tzw. naiwny, używa predykatu sklej, co powoduje jego nieefektywność. Innym rozwiązaniem jest użycie tzw. akumulatora,​ w którym przechowujemy budowaną na bieżąco listę. Opis procedury: ​[[http://cs.union.edu/~striegnk/​learn-prolog-now/​html/​node51.html#​subsec.l6.reverse.acc|tutaj]]
 W kolejnych krokach predykat ten buduje listę Accumulator:​ W kolejnych krokach predykat ten buduje listę Accumulator:​
     List: [a,​b,​c,​d] ​ Accumulator:​ []     List: [a,​b,​c,​d] ​ Accumulator:​ []
Linia 387: 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 =====
 +
 Z braku lepszego miejsca tutaj studenci wpisują komentarze natury ogólnej do tego lab. 8-) Z braku lepszego miejsca tutaj studenci wpisują komentarze natury ogólnej do tego lab. 8-)
  
  --- //​[[gjn@agh.edu.pl|Grzegorz J. Nalepa]] 2008/02/20 14:34//  --- //​[[gjn@agh.edu.pl|Grzegorz J. Nalepa]] 2008/02/20 14:34//
- 
pl/prolog/prolog_lab/listy1.1235483796.txt.gz · ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0