Przetwarzanie List PF kontra OO

michalkulinski.blogspot.com 5 lat temu

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:

https://blog.cleancoder.com/uncle-bob/2018/12/17/FPvsOO-List-processing.html

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

Wyobraźmy sobie, iż 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, o ile 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żeli 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, iż 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, iż to będzie dodatkowa robota. Wydawało mi się to stratą czasu, iż muszę to rozdzielać i śledzić niezmienione elementy. Jednakże potem doznałem olśnienia.

Wyobraź sobie, iż 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:

https://blog.cleancoder.com/uncle-bob/2018/12/17/FPvsOO-List-processing.html

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

Idź do oryginalnego materiału