12 października 2020

Podstawy Programowania Funkcyjnego Epizod 3


Czy wszystkie Zasady Się Zmieniają?

Kiedy tylko zaczynamy używać nowego paradygmatu, porównujemy z nim nasze dotychczasowe zasady i nawyki. Pytamy siebie czy te wszystkie zasady i nawyki są poprawne w kontekście tego nowego paradygmatu. Rozważ, dla przykładu: Test Driven Development. Czy nadal jest poprawne w Programowaniu Funkcyjnym? Jeżeli tak, to jak się do tego zabierzesz?

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


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


Aby odpowiedzieć sobie na to pytanie spróbujmy napisać prosty funkcyjny program: Word Wrap (zawijanie tekstu). Wymagania są proste. Mając napis złożony ze słów, oddzielonych pojedynczymi spacjami, i mając daną, pożądaną długość wiersza, wstaw znaki końca linii w odpowiednie miejsca w napisie, aby upewnić się, że żadna linia nie jest dłuższa niż zadana długość. Słowa mogą być ucięte tylko, jeżeli są dłuższe niż zadana długość.
Weźmy tekst Przemowy gettysburskiej jako przykład napisu:
“Four score and seven years ago our fathers brought forth upon this continent a new nation conceived in liberty and dedicated to the proposition that all men are created equal”
I gdy zawiniemy to tak, aby żadna linia nie była dłuższa niż 10 znaków, rezultat będzie taki:
“Four score\nand seven\nyears ago\nour\nfathers\nbrought\nforth upon\nthis\ncontinent\na new\nnation\nconceived\nin liberty\nand\ndedicated\nto the\npropositio\nn that all\nmen are\ncreated\nequal”
Użyjmy świetnego frameworku do testowania o nazwie Midje autorstwa Briana Maricka, i zacznijmy, tworząc pierwszy test.
(facts
  (wrap "" 1) => "")
Co oznacza, że istnieje przypadek, który wywołując (wrap "" 1) zwróci "". Aby to przechodziło definiujemy funkcję wrap i dajemy jej, jak zwykle, najprostszą implementację.
(defn wrap [s n]
  "")
Następny test prowadzi nas znowu w okolice najprostszej implementacji:
(wrap "x" 1) => "x"

(defn wrap [s n]
  s)
Następny test zmusza nas aby rozbić słowa, które są za długie
(wrap "xx" 1) => "x\nx"

(defn wrap [s n]
  (if (<= (length s) n)
    s
    (str (subs s 0 n) "\n" (subs s n))))
Instrukcja if działa w Clojure tak, jak operator warunkowy ?: w C czy w Javie. Zwraca pierwsze wyrażenie, jeżeli wyrażenie logiczne jest prawdziwe; w przeciwnym wypadku zwraca drugie wyrażenie. Funkcja subs prawie samoopisuje się i jest podobna do tej metody subString z Javy. Z kolei funkcja str po prostu łączy wszystkie swoje argumenty w jeden napis.
Następny test zmusza nas do powtarzania tego samego. Użyjemy do tego rekurencji:
(wrap "xxx" 1) => "x\nx\nx"

(defn wrap [s n]
  (if (<= (count s) n)
    s
    (str (subs s 0 n) "\n" (wrap (subs s n) n))))
Następny test sprawdza przypadek, w którym znak tuż po zawinięciu linii jest spacją. Nie chcemy mieć spacji na początku następnej linii, więc pomijamy tę spację.
(wrap "x x" 1) => "x\nx"

(defn wrap [s n]
  (if (<= (count s) n)
    s
    (let [trailing-space (= \space (get s n))
          new-line-start (if trailing-space (inc n) n)
          head (subs s 0 n)
          tail (subs s new-line-start)]
      (str head "\n" (wrap tail n)))))
Polecenie let w Clojure po prostu pozwala stworzyć lokalne symbole, które trzymają wartości użyte w ciele funkcji. To nie są zmienne, ponieważ ich wartość się nie zmienia.
Funkcja get zwraca znak na pozycji n w ciągu znaków. Wyrażenie \space jest stałą w Clojure, oznaczającą spację.
Następny test zmusza nas do szukania w tył ostatniej spacji przed tym, jak będziemy musieli złamać linię. Jeżli nie została znaleziona spacja, to oznacza, że mamy do czynienia z wyrazem dłuższym niż n. W przeciwnym wypadku dzielimy linię na tej spacji. To szukanie wstecz jest robione przy użyciu funkcji .lastIndexOf, którą wołamy bezpośrednio z biblioteki stringów Javy. To właśnie kropka . wskazuje na bezpośrednie odwołanie do Javy.
(wrap "x x" 2) => "x\nx"

(defn wrap [s n]
  (if (<= (count s) n)
    s
    (let [space-before-end (.lastIndexOf s " " n)
          this-line-end (if (neg? space-before-end)
                            n
                            space-before-end)
          trailing-space (= \space (get s this-line-end))
          new-line-start (if trailing-space
                             (inc this-line-end)
                             this-line-end)
          head (subs s 0 this-line-end)
          tail (subs s new-line-start)]
      (str head "\n" (wrap tail n)))))
Zrobiło się to trochę nieładne, więc zrefaktorujmy to troszkę
(defn find-start-and-end [s n]
  (let [space-before-end (.lastIndexOf s " " n)
        line-end (if (neg? space-before-end) n space-before-end)
        trailing-space (= \space (get s line-end))
        line-start (if trailing-space (inc line-end) line-end)]
    [line-start line-end]))

(defn wrap [s n]
  (if (<= (count s) n)
    s
    (let [[start end] (find-start-and-end s n)
          head (subs s 0 end)
          tail (subs s start)]
      (str head "\n" (wrap tail n)))))
Możesz być nieprzekonany, że to wszystkie przypadki testowe. Więc zachęcam Cię do poszukania nowych. Zachęcam Cię do przestudiowania tych sześciu prostych przypadków testowych powoli i dokładnie. Większość ludzi nie pisze ich w ten sposób. Dużo czasu mi zajęło, zanim przekonałem się o wartości dobrze poukładanych, ostrożnie przemyślanych, minimalnych do bólu przypadków testowych.
Pomimo tego, wydaje się, przynajmniej w tym przypadku, że zasady TDD nadają się do wykorzystania tak samo w programowaniu funkcyjnym, jak i innych typach programowania. Zatem, gdy zaczynasz z programowaniem funcyjnym nie wylewaj dziecka z kąpielą. Trzymaj się swojej dyscypliny TDD!
Niektórzy mogliby zarzucić, ten algorytm nie jest funkcyjny; ale zapewniam Cię, że taki jest. Nie ma żadnych skutków ubocznych. Jest reprezentacyjnie przejrzysty. Używa trwałych struktur danych. Jest funkcyjny.
Brakuje mu rzeczywiście jednego przymiotu, który zwykle znajduje się w programach funkcyjnych. Nie jest złożony z zestawu przekształceń.
Rozważ jeszcze raz program do obliczania kwadratów liczb całkowitych.
(take 25 (squares-of (integers))
Czysta elegancja tego kawałka kodu wynika częściowo z faktu, że jest to właśnie seria przekształceń. Pierwsze przekształcenie to funkcja integers. Przekształca nic w leniwą sekwencję liczb całkowitych zaczynających się od 1. Drugie przekształcenie to funkcja squares-of. Przekształca dowolną listę liczb całkowitych w listę ich kwadratów. Ostatnie przekształcenie to funkcja take, która przekształca nieskończoną leniwą sekwencję w sekwencję o dokładnie 25 elementach.
Czy możemy przepisać program do zawijania tekstu do programu, w którym występują tylko serie przekształceń. Jasne. Rozważ to:
(defn wrap [s n]
  (join "\n"
        (make-lines-up-to n
                          (break-long-words n (split s #" ")))))
Bedziemy czytać ten kawałek kodu w sposób, w jaki czytaliśmy program kwadraty liczb całkowitych; od środka w górę. Najpierw musimy rozbić wejściowy napis w sekwencję słów. Potem rozbijamy wszystkie długie słowa dłuższe niż n na dwa lub więcej słów. Następnie dokładamy te słowa do linii które są nie dłuższe niż n. Na koniec łączymy wszystkie linie razem z "\n". Proste, prawda?
No cóż, wygląda na prosty, gdy jest napisany w ten sposób. A tutaj implementacja całego programu:
(defn break-long-words [n words]
  (if (empty? words)
    []
    (let [word (first words)]
      (if (>= n (count word))
        (cons word (break-long-words n (rest words)))
        (cons (subs word 0 n)
              (break-long-words
                 n
                 (cons (subs word n) (rest words))))))))

(defn make-lines-up-to
  ([n words]
    (make-lines-up-to n words [] []))
  ([n words line lines]
    (if (empty? words)
      (conj lines (join " " line))
      (let [new-line (conj line (first words))]
        (if (>= n (count (join " " new-line)))
          (make-lines-up-to n (rest words) new-line lines)
          (make-lines-up-to n
                            words
                            []
                            (conj lines (join " " line))))))))

(defn wrap [s n]
  (join "\n" (make-lines-up-to
                n
                (break-long-words n (split s #" ")))))
Jest na świecie wiele osób, którzy chętnie powiedzą Ci, że nie jestem najlepszym programistą funkcyjnym w okolicy. Zapewne mają rację. Z tego względu ten program może być żałośnie niewystarczający jako demonstracja. Nadal, bardzo trudno jest mi uwierzyć, że moje pierwsze podejście do rozwiązania problemu zawijania tekstu jest gorsze od kodu powyżej. To też nie oznacza, że sekwencje przekształceń są złe. Wręcz przeciwnie, uważam, że są mają w sobie ogromny potencjał i bedziemy rozważać je jeszcze później w szczegółach. Chodzi mi o to, że nie wszystkie programy funkcyjne muszą być sekwencjami przekształceń. Stara zasada "im prościej tym lepiej" nadal aktualna. No i dla algorytmu zawijania tekstu, przynajmniej tak, jak ja to widzę (przyznam niezbyt daleko) rozwiązanie przekształceniowe nie jest najlepsze.
Tak przy okazji, nie używałem TDD do stworzenia tego rozwiązania przekształceniowego, które widzisz powyżej. Pewnie mógłbym, ale zamiast tego użyłem metody, którą preferuje wielu programistów funkcyjnych. Rozważałem to dłuższą chwilę, aż w końcu użyłem ręcznego testowania w konsoli (zwykle nazywa się to REPL, Read Evaluate Print Loop czyli Pętla Wczytaj Wykonaj Wyświetl) aby poskładać wszystko w całość. Cały proces zajął mi przynajmniej trzy razy tyle niż TDD, włączając wiele okropnego debbugowania i komend wyświetlających, co spowodowało mnóstwo rekursywnym pętli nieskończonych, które rozwalały stos i wywalały mi konsolę. Czyniąc długą sprawę krótką, to był ból. Nie polecam tego.
Podsumowując: stare zasady nadal działają. Programowanie funkcyjne może być zmianą - ważną zmianą, ale nie zmienia ono wszystkiego. Programowanie to nadal programowanie. Dyscyplina to nadal dyscyplina. TDD działa w programowaniu funkcyjnym tak dobrze jak w innych stylach programowania. Być może są jakieś zasady, z których musielibyśmy zrezygnować wdrażając programowanie funkcyjne; ale póki co ja żadnej takiej nie znalazłem.

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


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

3 komentarze:

  1. Drobna korekta - Przemowa gettysburska zaczyna sie "Fourscore and seven years....." - score (w znaczeniu liczebnika 20) laczy sie zawsze z liczba

    OdpowiedzUsuń
    Odpowiedzi
    1. Oryginalny tekst Przemowy Gettysburskiej z 1863 roku pisany jest odzielnie: "Four score and seven years ago".

      Usuń
  2. Zgadzam się z poprzednikiem, bo niestety mam to samo... nie bardzo lubię programowanie funkcyjne, ale cóż. Nie można być dobrym we wszystkim :)

    OdpowiedzUsuń

Podstawy Programowania Funkcyjnego Epizod 3

Czy wszystkie Zasady Się Zmieniają? Kiedy tylko zaczynamy używać nowego paradygmatu , porównujemy z nim na...