Przetwarzanie List PF kontra OO

uncle bob label image
Gdy pisałem spacewar przez ostatnie kilka miesięcy, napotkałem na ciekawą różnicę pomiędzy programowaniem funkcyjnym, a programowaniem OO.

Poniższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony:


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.


Wyobraźmy sobie, że mamy dwie listy. Lista statków Klingonów i lista pocisków poruszających się w przestrzeni. Pociskami mogą być promienie fazera, torpedy fotonowe, lub kule żelaza zwane kinetykami. We wszystkich tych przypadkach mają one położenie i prędkość. Tak samo każdy ze statków klingońskich.


Mamy częstotliwość odświeżania liczoną w f klatek na sekundę. W każdej klatce patrzymy na położenie pocisków i porównujemy je z położeniem statków klingońskich. Szukamy trafienia.
Jeżeli znaleźliśmy trafienie, usuwamy pocisk z listy pocisków, dodajemy trafienie do statku Klingonów i dodajemy wybuch do listy wybuchów w świecie gry.
W Javie kod mógłby wyglądać tak:
void updateHits(World world){
  nextShot:
  for (shot : world.shots) {
    for (klingon : world.klingons) {
      if (distance(shot, klingon) <= type.proximity) {
        world.shots.remove(shot);
        world.explosions.add(new Explosion(shot));
        klingon.hits.add(new Hit(shot));
        break nextShot;
      }
    }
  }
}    
Zauważ break z etykietą. Po raz pierwszy w mojej historii pokusiłem się o użycie czegoś takiego.
Pomijając to, kod jest całkiem oczywisty, nieprawdaż? Ale w żaden sposób nie jest funkcyjny, ponieważ zmienia zbiór trafień Klingonów i świat gry.
Program funkcyjny, który ma robić to samo, nie może zmieniać Klingonów i świata gry w żaden sposób. To, co musi robić zamiast tego, to tworzyć całkiem nowy świat, z nowymi Klingonami, nowymi pociskami, wybuchami i trafieniami. Pamiętaj, o tym właśnie jest całe programowanie funkcyjne. Nie możesz zmieniać wartości żadnej istniejącej zmiennej.


Mógłbyś zapytać, w jaki sposób możesz zmienić stan gry, jeżeli nie możesz zmienić stanu żadnej ze zmiennych gry? Odpowiedź jest prosta: Używasz rekurencji ogonowej.
Zasadniczo masz funkcję, która przekształca świat gry w jednym małym kroku. Wynikiem tej funkcji jest całkowicie nowy świat. Wtedy wywołujesz tę funkcję w rekurencyjnej pętli tak, jak tu:
void updateWorld(World world) {
  drawWorld(world);
  updateWorld(transformWorld(world));
}
Jeżeli jesteś programistą Javy, prawdopodobnie zwróciłbyś uwagę na potencjalne przepełnianie się stosu. Ale w językach funkcyjnych (i w innych współczesnych językach innych niż Java) jest cudowny sposób nazywany optymalizacja wywołań ogonowych, która usuwa cały problem, jeśli tylko rekurencyjne wywołanie jest ostatnią operacją w danej funkcji.
A więc jak ktoś miałby napisać funkcję update-hits w języku funkcyjnym takim jak Clojure?


Popatrz na to:
(defn update-hits [target-tag world]
  (let [{:keys [shots explosions]} world
        relevant-shots (filter #(#{:kinetic :torpedo :phaser} (:type %)) shots)
        targets (target-tag world)
        pairs (for [t targets s relevant-shots]
                {:target t
                 :shot s
                 :distance (geo/distance (pos s) (pos t))})
        hits (filter #(>= (shot-proximity (:shot %)) (:distance %)) pairs)
        hit-targets (set (map :target hits))
        hit-shots (set (map :shot hits))
        un-hit-targets (set/difference (set targets) hit-targets)
        un-hit-shots (set/difference (set shots) hit-shots)
        hit-targets (map #(process-hit hits %) hit-targets)
        explosions (concat explosions (map #(explosions/shot->explosion %) hit-shots))]
    (assoc world target-tag (doall (concat un-hit-targets hit-targets))
                 :shots (doall (concat un-hit-shots))
                 :explosions (doall explosions))))
To wygląda trochę inaczej niż funkcja w Javie, prawda? Powinno. Robi o wiele więcej niż funkcja w Javie. A więc prześledźmy ten kod krok po kroku.
  • Na początku dostajemy wszystkie pasujące pociski. Są trzy rodzaje pocisków, które nasz statek może wystrzelić w cele Klingonów i Romulan. Nie zawarłem ich w kodzie Java powyżej, więc to jest po prostu dodatkowy kod.
  • Potem dostajemy nasze cele. W naszym przypadku to jest lista tylko samych Klingonów. Chociaż może to być także lista wszystkich Romulan.
  • Potem dostajemy pary celów i pocisków razem z ich odległością od siebie nawzajem.
  • Potem filtrujemy te pary do tych, których odległości są mniejsze niż graniczne wartości zbliżeniowe broni. To są te pary, które reprezentują trafienia.
  • Potem filtrujemy te pary w listę celów trafionych i pocisków, które trafiły.
  • Potem, i to jest całkiem interesujące, dostajemy listę wszystkich Klingonów, którzy NIE zostali trafieni. Dostajemy także listę wszystkich pocisków, które NIE trafiły. Dlaczego ich potrzebujemy? Czytaj dalej.
  • Następnie tworzymy hit-targets. To uaktualnia każdy trafiony cel jego konkretnym trafieniem.
  • Potem tworzymy listę wszystkich nowych wybuchów dodanych do istniejących wybuchów w świecie gry.
  • Na koniec tworzymy świat gry. Świat jest kopią [1] starego świata, ale z:
    • Klingonami zamienionymi na konkatenację trafionych Klingonów i nietrafionych Klingonów
    • pociskami zamienionymi na te, które nie trafiły
    • wybuchami zamienionymi sumą starych i nowych wybuchów.
Teraz następuje część, którą uważam za interesującą - o tym, że aby stworzyć nową instancję świata, muszę śledzić te elementy świata, które się zmieniły, takie jak Klingonowie, pociski, i wybuchy, i wszystkie te elementy, które się nie zmieniły. Muszę rozdzielić je. Poczynić zmiany. A potem złożyć je z powrotem w całość. Nie mogę po prostu dostać się do świata gry i zrobić zmian.
Na początku myślałem, że to będzie dodatkowa robota. Wydawało mi się to stratą czasu, że muszę to rozdzielać i śledzić niezmienione elementy. Jednakże potem doznałem olśnienia.
Wyobraź sobie, że masz tuzin rowerów w garażu. Ty i Twój kolega będziecie startować w wyścigu, i potrzebujecie wybrać i przygotować dwa rowery. Musicie oddzielić te dwa rowery od reszty, przygotować je, ścigać się na nich i potem umieścić je z powrotem w garażu z resztą rowerów.
Pozwolę Ci się zastanowić nad tym przez jakiś czas.[2]


[1] W rzeczywistości, to nie jest prawdziwa kopia. Większość języków funkcyjnych, włączając w to Clojure, używa bardzo sprytnych sposobów, aby uniknąć całego tego kopiowania poprzez strategiczne współdzielenie elementów, które się nie zmieniają.
[2] Jest to jeden z punktów dyskusji o grze spacewar podczas serii Czysty Kod: Programowanie Funkcyjne na stronie cleancoders.com.


Powyższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony:


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.

2 komentarze:

  1. No dobra, ale kto wygrał?

    OdpowiedzUsuń
  2. Spróbuj sam: http://spacewar.fikesfarm.com/spacewar.html
    Powiem Ci, że nie ma lekko!

    OdpowiedzUsuń