Poczytaj mi Clojure, cz. 11: Pętle i rekurencja

Niektóre funkcje i problemy mogą być czytelnie wyrażone w postaci rekurencyjnej lub zapętlonej. W Clojure istnieją konstrukcje, które pozwalają implementować algorytmy w taki właśnie sposób.

Pętle i rekurencja

Algorytmy, w których występuje konieczność przeliczania pewnego wyrażenia lub zestawu wyrażeń więcej niż raz, mogą być w Clojure zaprogramowane z użyciem dwóch mechanizmów: pętli lub rekurencji.

W paradygmacie funkcyjnym unika się typowych zapętleń, chociaż niektóre problemy można łatwiej wyrażać i wydajniej rozwiązywać stosując podejście strukturalne, z którego pętle się wywodzą. Clojure daje więc wolną rękę programiście i obsługuje niektóre z ich rodzajów. Z kolei rekurencja pozwala w czytelny sposób definiować funkcje i inne formuły, których działanie wymaga powtórzonego wykonania większości operacji wchodzących w skład ich ciał. Można więc powiedzieć, że pętle i rekurencja służą do wyrażania rozwiązań problemów, które przedstawione w inny sposób byłyby mniej spójne i na przykład zawierały powtórzone czy nazbyt zagnieżdżone fragmenty kodu.

Uwaga: Stosowanie pętli i rekurencji w celu przetwarzania wieloelementowych kolekcji jest często nadużywane. Zawsze warto zbadać, czy dany problem może być rozwiązany z wykorzystaniem dostępu sekwencyjnego i funkcyjnych mechanizmów przekształcania (kaskadowego filtrowania, odwzorowywania i redukowania zbiorów danych).

Pętle

Pętla (ang. loop) to konstrukcja, która pozwala na wielokrotne powtarzanie obliczania wartości tego samego wyrażenia lub zestawu wyrażeń, często z wielokrotnym emitowaniem efektów ubocznych. Przeliczanie wiąże się oczywiście z uruchamianiem związanych z wyrażeniami podprogramów. Z funkcyjnego punktu widzenia pętle można uznać za ograniczoną formę rekurencji, a dokładniej tzw. rekurencji ogonowej.

W wielu językach programowania (opartych o paradygmat imperatywny i strukturalny) wewnątrz pętli może pojawić się też konstrukcja sterująca, która pozwala wykonać skok do pierwszej instrukcji lub całkowicie przerwać wykonywanie. W językach funkcyjnych i akcentujących paradygmat funkcyjny możemy mieć kłopot ze znalezieniem odpowiedników tego typu form, ponieważ pętle są tam również specyficznymi wyrażeniami, tzn. dokonują wielokrotnego przeliczania podanych formuł, ale nie umożliwiają niskopoziomowego sterowania wykonywaniem się podprogramu. W Lispach (a więc i w Clojure) korzysta się więc zamiast tego z wyrażeń warunkowych, które pozwalają osiągać te same efekty sterowania wykonywaniem, zachowując przy tym elegancję i jednoznaczność struktury kodu źródłowego.

Pewnym wyjątkiem od powyższego jest w Clojure formuła recur, która zostanie omówiona później. Pozwala ona wykonać skok do ustanowionego wcześniej miejsca początkowego pętli z opcjonalną zmianą powiązań leksykalnych dla podanych symboli.

Wyróżniamy następujące rodzaje pętli:

Pętle warunkowe

Pętla warunkowa (ang. condition-controlled loop) to taka pętla, dla której podany jest warunek zakończenia przetwarzania. Warunek ten jest sprawdzany po każdorazowym przeliczeniu wartości wyrażeń umieszczonych w ciele pętli lub przed wykonaniem wartościowania.

Pętla warunkowa, while

Makro while służy do tworzenia pętli warunkowych. Przyjmuje ono jeden obowiązkowy argument, którym powinno być wyrażenie warunkowe. Każdy następny argument będzie potraktowany jako wyrażenie wchodzące w skład ciała pętli i będzie przeliczane dopóty, dopóki podany warunek jest spełniony. Za spełnienie warunku uznaje się sytuację, w której podane wyrażenie zwraca wartość różną od nil i różną od false. Testowanie warunku odbywa się przed wartościowaniem wyrażeń.

Makro zwraca wartość nil.

Warto zauważyć, że pętla na bazie while będzie badała warunek, który związany jest ze zmiennymi dynamicznymi, zmiennymi lokalnymi, efektem ubocznym funkcji obsługującej wejście/wyjście, albo z wartościami powiązanymi z globalnym stanem kontrolowanym z użyciem jednego z typów referencyjnych. Dzieje się tak, ponieważ w konstrukcji tej nie mamy do czynienia z obsługą lokalnych powiązań, które wyrażałyby wartość jakiegoś obsługiwanego przez mechanizm pętli licznika bądź innej formy wyrażającej stan. Wartość używana do sprawdzania warunku musi więc pochodzić z zewnątrz.

Użycie:

  • (while warunek & wyrażenie…).
Przykład użycia makra while
1
2
3
4
5
6
7
8
9
10
(with-local-vars [a 1 b 1]
  (while (< @a 8)
    (println @a)
    (var-set a (+ @a @b))
    (var-set b (inc @b))))
; >> 1
; >> 2
; >> 4
; >> 7
; => nil

Pętle kolekcyjne

Pętla kolekcyjna (ang. collection-controlled loop), zwana też pętlą typu foreach (ang. foreach loop), pozwala na wykonywanie pewnych wyrażeń dla każdego elementu podanej kolekcji lub innej wieloelementowej struktury.

W Clojure następcze przetwarzanie struktur w tym stylu można zrealizować korzystając z sekwencyjnego interfejsu dostępu i obsługujących sekwencje funkcji oraz makr, do których należą między innymi: doseq, doall, dorun, cyclemap.

Jeżeli mamy do czynienia ze strukturą danych, która pozwala na dostęp sekwencyjny i istnieje możliwość kaskadowego przetwarzania elementów, aby uzyskać rezultaty, to jest to zalecany sposób.

Pętle ogólne

Pętla ogólna (ang. generic loop), zwana też ogólnym dostępem następczym (ang. general iteration) pozwala uzyskiwać dostęp do kolejnych elementów wielu sekwencyjnych struktur danych jednocześnie, a umożliwia to zestaw wielu liczników powiązanych z ich pozycjami i warunków zakończenia przetwarzania. Przykładem takiej pętli jest znana z języka C instrukcja for.

Pętla ogólna, for

W Clojure pętlę ogólną możemy utworzyć z wykorzystaniem makra for i podanych zestawów danych wyposażonych w sekwencyjne interfejsy dostępu. Jej głównym zadaniem jest operowanie na elementach struktur powiązanych leksykalnie z symbolami w wektorze powiązaniowym, który trzeba podać jako pierwszy argument. Mogą w nim znaleźć się również tzw. modyfikatory o etykietach wyrażonych słowami kluczowymi: :when (wywołujący when), :let (wywołujący let) lub :while (wywołujący while).

Umieszczenie modyfikatora w wektorze powiązaniowym sprawi, że będzie wywołana formuła specjalna lub makro o odpowiadającej mu nazwie, a znajdujące się po nim wartości zostaną przekazane jako argumenty.

Rezultatem wywołania for jest wartość wyrażenia podanego jako jego drugi argument. W wyrażeniu tym można korzystać z symboli powiązanych z wartościami w wektorze powiązaniowym. Dla każdej iteracji powiązania symboli będą aktualizowane w taki sposób, że będą one odnosiły się do kolejnych elementów sekwencji. W przypadku więcej niż jednej pary powiązaniowej makro for dokona zagnieżdżonej iteracji dla każdego elementu z każdym, poczynając od elementów pierwszego powiązania.

Użycie:

  • (for wektor-powiązaniowy wyrażenie).
Przykłady użycia makra for
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
;; mnożenie przez 2
(for [element1 '(1 2 3)] (* element1 2))
; => (2 4 6)

;; wykorzystanie modyfikatorów
(for [element1 '(1 2 3)
      :let   [razy-dwa (* element1 2)]
      :while (< razy-dwa 5)]
  razy-dwa)
; => (2 4)

;; tworzenie sekwencji wektorów z kombinacjami
;; (zagnieżdżone iteracje)
(for [liczba '(1 2 3)
      litera '(:a :b)]
  [litera liczba])
; => ([:a 1] [:b 1] [:a 2] [:b 2] [:a 3] [:b 3])

Zobacz także:

Pętle licznikowe

Pętla licznikowa (ang. count-controlled loop), zwana też pętlą iteracyjną to pętla, która po każdym przebiegu dokonuje modyfikacji podanego licznika lub liczników. Pętla kończy pracę, gdy spełniony zostanie warunek zakończenia związany z bieżącą wartością licznika (np. gdy będzie on równy zeru lub innej podanej wartości). W pętli tego typu warunek zakończenia i początkowa wartość licznika muszą być znane zanim rozpocznie się jej praca.

W wyrażeniach umieszczonych w pętli można korzystać z wartości licznika na przykład do wskazywania elementu uporządkowanej kolekcji o podanym numerze indeksu.

W Clojure nie istnieje konstrukcja specyficzna dla pętli licznikowych, jednak można użyć na przykład makra for z sekwencją reprezentującą zakres liczbowy czy makra while.

Przykłady implementacji pętli licznikowej z użyciem for
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
;; z licznikiem i warunkiem określonym wartością końcową
(for [n (range 4)] (println n))
; >> 0
; >> 1
; >> 2
; >> 3
; => (nil nil nil nil)

;; z licznikiem i warunkiem wyrażonym wprost
(for [n (range 4 10)
      :while (<= n 8)]
  (println n))
; >> 4
; >> 5
; >> 6
; >> 7
; >> 8
; => (nil nil nil nil nil)

Zauważmy, że w powyższych przykładach makro for poza efektami ubocznymi zwróciło sekwencje zawierające wartości będące wartościami kolejnych wywołań podanych wyrażeń (w naszym przypadku nil). Jeżeli jest to wysoce niepożądane, możemy:

  • użyć funkcji dorun, która sprawi, że wartość zwracana przez makro for będzie zignorowana i zastąpiona wartością nil;
  • skorzystać z innych konstrukcji, na przykład: doseq, loop czy while (wraz z with-local-vars).
Przykłady implementacji pętli licznikowej z użyciem dorun, doseq, loop i while
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
(dorun (for [n (range 4)] (println n)))
; >> 0
; >> 1
; >> 2
; >> 3
; => nil

(doseq [n (range 1 4)]
  (println n))
; >> 1
; >> 2
; >> 3
; => nil

(loop [n 3]
  (when (<= n 5)
    (println n)
    (recur (inc n))))
; >> 3
; >> 4
; >> 5
; => nil

(with-local-vars [n 5]
  (while (< @n 8)
    (println @n)
    (var-set n (inc @n))))
; >> 5
; >> 6
; >> 7
; => nil

Pętle powtórzeniowe

Pętla powtórzeniowa, zwana też pętlą typu times (ang. times loop), jest pętlą o określonej liczbie powtórzeń, lecz bez deklarowania wartości początkowej licznika i warunku zakończenia. Podczas użycia należy podać po prostu liczbę iteracji.

Pętla powtórzeniowa, dotimes

Makro dotimes pozwala utworzyć pętlę o określonej liczbie powtórzeń. Przyjmuje ono jeden obowiązkowy argument, którym powinien być uproszczony (nie zawierający konstrukcji dekompozycyjnych) wektor powiązaniowy złożony z dokładnie jednej pary powiązaniowej: symbolu i liczby powtórzeń. Kolejne argumenty to wyrażenia stanowiące ciało pętli, w którym można korzystać z powiązanego wcześniej symbolu – dla każdego przebiegu powiązana z nim wartość będzie zmieniała się od 0 do wartości o jeden mniejszej, niż podana liczba powtórzeń.

Wartością zwracaną przez makro dotimes jest nil.

Użycie:

  • (dotimes wektor-powiązaniowy & wyrażenie…).
Przykład użycia makra dotimes
1
2
3
4
5
(dotimes [n 4] (println n))
; >> 0 
; >> 1
; >> 2
; >> 3

Pętle nieskończone

Pętla nieskończona (ang. infinite loop) to taka pętla, której liczba przebiegów nie jest określona, a więc potencjalnie może się ona wykonywać w nieskończoność.

W Clojure nie istnieje konstrukcja typowa dla pętli nieskończonej, lecz można ją utworzyć, bazując na dostępnych formułach specjalnych: looprecur lub while.

Przykład implementacji pętli nieskończonej
1
2
3
4
5
6
7
8
;; użycie loop i recur
(loop []
  (println "w pętli")
  (recur))

;; użycie while
(while true
  (println "w pętli"))

Innym rozwiązaniem może być skorzystanie z funkcji obsługujących sekwencje:

  • cycle, która generuje leniwą i potencjalnie nieskończoną sekwencję złożoną z cyklicznie powtarzanych elementów pochodzących z podanej kolekcji;
  • repeat, która generuje leniwą i potencjalnie nieskończoną sekwencję złożoną z elementów o podanej wartości;
  • repeatedly, która generuje leniwą i potencjalnie nieskończoną sekwencję dla rezultatów stanowiących kolejne wywołania przekazanej funkcji.

Rekurencja

Rekurencja (ang. recurrence), zwana też rekursją (ang. recursion) to taki schemat postępowania w rozwiązywaniu problemu, w którym jeden z etapów polega na użyciu właśnie tego schematu.

Realizować następczo jest rzeczą ludzką, rekursywnie: boską.  
 
— L. Peter Deutsch

Obiekty uruchomieniowe, które działają w sposób rekurencyjny muszą mieć dwie podstawowe właściwości:

  1. Powinny obsługiwać przynajmniej jeden przypadek bazowy (ang. base case), w którym rezultat generowany jest bez odwoływania się obiektu do samego siebie i przynajmniej jeden przypadek rekursywny (ang. recursive case), gdzie następuje odwołanie się obiektu do samego siebie.

  2. Powinny zawierać przynajmniej jeden warunek zakończenia rekurencji, który prowadzi do skrócenia (redukcji) rezultatów, dążąc do przypadku bazowego.

Przypadek bazowy nazywa się czasem przypadkiem prostym, a warunek zakończenia rekurencji warunkiem zatrzymania.

Tworząc implementacje rekurencyjnych algorytmów, należy odpowiedzieć na następujące pytania:

  • Jakie są warunki przypadku bazowego?
  • Jakie są warunki przypadku rekursywnego?
  • Jaki jest sposób redukcji problemu, który przypadki rekursywne sprowadzi do przypadków bazowych?

Może również zdarzyć się tak, że dany problem nie jest problemem funkcyjnym i próba rozwiązania go rekurencyjnie będzie nieoptymalna pod względem czasowej i/lub pamięciowej złożoności obliczeniowej. W takich przypadkach lepiej skorzystać z pętli czy nawet konstrukcji w stylu imperatywnym (np. z wykorzystaniem lokalnych obiektów typu Var).

Istnieje kilka rodzajów rekurencji, które różnią się sposobem wywoływania podprogramu własnego i mechanizmem przekazywania wartości. W Clojure możemy obsługiwać następujące:

Higieniczny programista – przykład

Aby zrozumieć rekurencję,
musisz najpierw zrozumieć rekurencję.
 
 
— D. Hunter

Spróbujmy zastanowić się nad hipotetycznym przypadkiem programisty, który dba o higienę. W tym celu każdego ranka udaje się pod prysznic, gdzie korzysta z szamponu, aby umyć włosy. Jakie instrukcje należałoby umieścić na etykiecie specyfiku, aby proces przebiegał pomyślnie?

Mogłoby to wyglądać w ten sposób:

  1. Otworzyć butelkę.
  2. Nanieść niewielką ilość na włosy.
  3. Zamknąć butelkę.
  4. Spłukać.
  5. Czynność powtórzyć.

W krążącym w Sieci dowcipie o informatyku, który w ten sposób myje włosy, znajdujemy naszego bohatera martwego z wycieńczenia, ponieważ brakuje warunku zakończenia rekurencji i dochodzi do nieskończonego zapętlenia procesu. Rzeczywistość nie byłaby jednak tak tragiczna, ponieważ podobnie jak w pamięci komputera, tu również mamy do czynienia ze skończonymi zasobami. Po prostu wystąpiłaby sytuacja wyjątkowa, gdy po kilkunastu czy kilkudziesięciu powtórzeniach skończyłby się szampon.

Jak więc mogłaby wyglądać rekursywna instrukcja, którą zrozumiałby nasz higieniczny koder? Spróbujmy:

  1. Otworzyć butelkę.
  2. Nanieść niewielką ilość na włosy.
  3. Zamknąć butelkę.
  4. Spłukać.
  5. Jeżeli włosy są brudne: czynność powtórzyć.

W ostatnim punkcie mamy do czynienia z warunkiem zakończenia rekurencji wyrażonym negatywnie. Tym sposobem zadbaliśmy o drogocenny czas obliczeniowy naszego hipotetycznego czyścioszka!

Warto zauważyć, że zadania z punktów o numerach 2 i 4 mogą być w naszym przykładzie przypadkami bazowymi (właściwymi czynnościami wiodącymi do rozwiązania problemu), natomiast punkt nr 5 to przypadek rekursywny (prowadzący do powtórzenia wszystkich czynności).

Rekurencja nazwana i nienazwana

Czasem możemy spotkać się z nazwami rekurencja nazwana (ang. named recursion) i rekurencja nienazwana (ang. unnamed recursion), zwana też rekurencją anonimową (ang. anonymous recursion). Pierwszy termin oznacza, że rekursywne wywołanie obiektu odbywa się z wykorzystaniem nadanej mu wcześniej nazwy, a drugi, że nie korzysta się z powiązania z identyfikatorem, lecz odwołuje do podprogramu własnego w inny sposób, np. z użyciem specjalnych konstrukcji lub przez przekazywanie obiektu funkcyjnego do funkcji wyższego rzędu.

W Clojure za rekurencję nazwaną można uznać wszelkie rekurencyjne wywołania funkcji z użyciem powiązanej z nią wcześniej symbolicznej nazwy. Z kolei za rekurencję nienazwaną:

Warto zauważyć, że za rekurencję anonimową uznamy nawet wywołania funkcji nazwanej, jeżeli sposób rekursywnego odwoływania się do niej nie korzysta z nazwy, lecz np. z konstrukcji recur. Podobnie w przypadku rekurencji nazwanej: możemy uznać, że nawet wywołania funkcji anonimowej, jeżeli korzystają z jej symbolicznego identyfikatora (podanego na początku definicji, tuż po symbolu fn), są formą rekurencji nazwanej.

Rekurencja nieogonowa

Rekurencja nieogonowa (ang. non-tail recursion), zwana czasem rekurencją zwykłą (ang. plain recursion) lub po prostu rekurencją, polega na wywoływaniu podprogramu realizującego pewne zadanie przez samego siebie. W Clojure rekurencyjnych wywołań możemy dokonywać z wnętrza funkcji.

Dzięki zastosowaniu rekurencji zwykłej jesteśmy w stanie w przejrzysty i funkcyjny sposób wyrażać sposoby rozwiązywania wielu problemów. Należy jednak być ostrożnym, ponieważ w Clojure nie mamy do czynienia z automatyczną optymalizacją rekurencji, co może prowadzić do przepełnienia stosu wywołań (ang. call stack). Wynika to ze sposobu, w jaki odbywa się wywoływanie funkcji. Programy komputerowe korzystają ze stosu, aby umieszczać na nim informacje o aktualnie realizowanych podprogramach (np. wywołanych funkcjach). Powodem korzystania z takiej struktury jest konieczność powrotu z podprogramu i przekazania sterowania do instrukcji następującej po instrukcji jego wywołania.

Stos wywołań złożony jest z tzw. ramek (ang. stack frames). Każde odwołanie się do kodu funkcji sprawia, że na stosie pojawia się nowa ramka. Jeżeli funkcja wywołuje samą siebie (własny podprogram) wielokrotnie, to na stosie umieszczanych jest odpowiednio dużo ramek. Każda z nich będzie zajmowała określony obszar pamięci, której rozmiar jest ograniczony. Jeżeli wywołań będzie zbyt wiele, przestrzeni pamięciowej nie wystarczy i wykonywanie się programu zostanie awaryjnie przerwane.

Powyższe oznacza, że w praktyce powinniśmy stosować rekurencję nieogonową tam, gdzie nie będziemy mieli do czynienia ze zbyt wieloma rekurencyjnymi wywołaniami. Jeżeli dany algorytm na to nie pozwala, należy zastosować inne, omówione niżej rodzaje rekurencji lub skorzystać z pętli.

Rekurencyjne wywoływanie funkcji

Oczywistym przykładem rekurencji nieogonowej jest wywołanie funkcji w jej ciele. Może być to funkcja anonimowa lub nazwana. Wywołanie rekurencyjne w zapisie nie różni się od zwyczajnego wywołania funkcji: posługujmy się listowym S-wyrażeniem, którego pierwszym elementem jest symbol powiązany z podprogramem funkcji.

Spróbujmy zdefiniować funkcję o symbolicznej nazwie !, która będzie rekurencyjnie realizowała algorytm silni:

Przykład funkcji rekurencyjnej
1
2
3
4
5
6
7
8
9
10
11
(defn ! [n]
  (if (zero? n)           ; warunek zakończenia rekurencji
    1                     ; przypadek bazowy
    (*' (! (dec n)) n)))  ; przypadek rekursywny
                          ;  · wynik wywołania dla n-1 mnożony przez n
(! 1)   ; => 1
(! 5)   ; => 120
(! 21)  ; => 51090942171709440000N

(! 7000)
; >> #<StackOverflowError java.lang.StackOverflowError>

Zauważmy, że w linii nr 4 zamiast ze standardowego operatora mnożenia, korzystamy z operatora obsługującego potencjalnie duże liczby: *'. Dzięki niemu unikamy pojawiania się w linii nr 9 błędu związanego z przepełnieniem zakresu.

W ostatniej linii przykładu doszło do awaryjnego przerwania pracy i zgłoszenia wyjątku StackOverflowError komunikującego przepełnienie stosu. Przyczyną była zbyt duża liczba odłożonych na stos ramek. Wywołując funkcję, przekazaliśmy jej jako argument liczbę 7000, która w naszym przypadku oznacza dążenie do siedmiu tysięcy zagnieżdżonych wywołań. Receptą na to jest skorzystanie na przykład z rekurencji ogonowej.

Operator paradoksalny Y (Y-combinator)

Operator punktu stałego (ang. fixed-point combinator) to taka funkcja wyższego rzędu, która dla podanej funkcji zwraca jej punkt stały (miejsce, w którym zwracana wartość jest tożsama z przekazanym argumentem).

Popularnym operatorem punktu stałego jest pochodzący z rachunku lambda operator paradoksalny Y (ang. Y-combinator). Jego nazwa pochodzi od tzw. paradoksu Curry’ego, czyli paradoksu, w którym zdanie logiczne definiuje własną prawdziwość, np.: Jeśli to zdanie jest prawdziwe, Lisp jest najmocniejszym językiem programowania.

Ponieważ operator Y daje się wyrazić w rachunku lambda, więc – jak nietrudno się domyślić – możemy zaimplementować go w Lispach, a więc i w Clojure. Do czego można go użyć? Okazuje się, że dzięki niemu możliwe jest wyrażanie rekurencyjnych funkcji, które nie będą wprost odwoływały się do samych siebie (np. z użyciem symbolicznych nazw). Oznacza to, że z użyciem operatora Y możemy wyrazić prostą rekurencję anonimową przez przekazywanie bieżącej funkcji jako argumentu.

Implementacja silni z użyciem operatora paradoksalnego Y
1
2
3
4
5
6
7
8
9
10
11
12
13
;; operator Y
(defn Y [f]
  (#(% %)
   #(f (fn [& args] (apply (% %) args)))))

;; silnia 
(defn ! [f] #(if (zero? %) 1 (*' % (f (dec %)))))

;; wywołania
((Y !) 0)   ; => 1
((Y !) 1)   ; => 1
((Y !) 2)   ; => 2
((Y !) 12)  ; => 479001600

Zauważmy, że ta implementacja operatora punktu stałego Y nie jest zoptymalizowana i przy głębszych poziomach rekurencji dochodzić będzie do przepełnienia stosu.

Rekurencja ogonowa

Rekurencja ogonowa (ang. tail recursion) – zwana też rekurencją prawostronną (ang. right recursion), wywołaniem ogonowym (ang. tail call) lub rekurencją końcową – jest rodzajem rekurencji, w którym najpierw przeprowadzane są wszelkie możliwe obliczenia, a dopiero potem następuje wywołanie rekursywne. Istotne jest to, aby wywołanie to było ostatnim przeliczanym wyrażeniem ciała funkcji lub funkcyjnej konstrukcji.

Dzięki powyższemu kompilatory są w stanie przeprowadzać tzw. optymalizację wywołania ogonowego (ang. tail-call optimization, skr. TCO) i nie tworzyć nowych ramek odkładanych na stosie, bo każde kolejne wywołanie funkcji zastępuje wywołanie poprzedniej (korzysta z jej ramki). Jest to możliwe, ponieważ wywołanie to jest ostatnim wyrażeniem i po jego wartościowaniu nie ma już potrzeby wracać do konkretnego miejsca w podprogramie, a więc i pamiętać miejsca tego powrotu na stosie.

W Clojure nie mamy do czynienia z automatycznym wykrywaniem wywołań ogonowych, ani tym bardziej z automatycznym przekształcaniem kodu źródłowego w taki sposób, aby wywołania nieogonowe transformować do bardziej iteracyjnej postaci. Rekurencję ogonową należy więc wyrazić samodzielnie i wprost, z użyciem konstrukcji recur.

Ogonowa rekurencja anonimowa, recur

Formuła specjalna recur pozwala tworzyć ogonowe wywołania podprogramów, które nie powodują odkładania ramek na stos. Jej działanie polega na przeniesieniu wykonywania podprogramu do określonego wcześniej punktu początkowego, który powinien być zdefiniowany w obejmującym wywołanie recur kontekście leksykalnym.

Formuła recur przyjmuje zero lub więcej wyrażeń inicjujących, których wartości zostaną przekazane do konstrukcji stanowiącej wspomniany punkt początkowy. W przypadku funkcji będą to jej argumenty, a w przypadku formuły specjalnej loop wyrażenia inicjujące. W ten sposób zaktualizowane zostaną powiązania obejmującej formuły – ich symbole (reprezentujące parametry funkcji lub leksykalne powiązania konstrukcji loop) będą odnosiły się do nowych wartości.

W przypadku funkcji wieloczłonowych punktem początkowym będzie bieżące ciało (przypisane do danej argumentowości), a nie cała funkcja.

Użycie:

  • (recur & wyrażenie-inicjujące…).

Następujące konstrukcje mogą być zastosowane jako punkty początkowe recur:

  • funkcje anonimowe – formuły fnletfn,
  • funkcje nazwane – makro defn,
  • formuła specjalna loop.
Przykłady użycia formuły specjalnej recur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
;; funkcje anonimowe
((fn !                               ; wywołanie i definicja funkcji anonimowej
   ([n] (! n 1))                     ; pierwsze ciało: wywołanie drugiego
   ([n acc]                          ; drugie ciało:
    (if (zero? n)                    ;  · warunek zakończenia rekurencji
      acc                            ;    · przypadek bazowy
      (recur (dec n) (*' acc n)))))  ;    · przypadek rekursywny
 12)                                 ; argument wywołania funkcji
; => 479001600

;; funkcje nazwane
(defn !                              ; definicja funkcji
  ([n] (! n 1))                      ; pierwsze ciało: wywołanie drugiego
  ([n acc]                           ; drugie ciało:
    (if (zero? n)                    ;  · warunek zakończenia rekurencji
      acc                            ;    · przypadek bazowy
      (recur (dec n) (*' acc n)))))  ;    · przypadek rekursywny
                                     ; 
(! 12)                               ; wywołanie funkcji nazwanej
; => 479001600

;; formuła specjalna loop
(loop [n 12 acc 1]                   ; wywołanie formuły specjalnej loop
  (if (zero? n)                      ;  · warunek zakończenia rekurencji
    acc                              ;    · przypadek bazowy
    (recur (dec n) (*' acc n))))     ;    · przypadek rekursywny
; => 479001600

Punkt początkowy rekurencji ogonowej, loop

Makro loop pozwala na ustalenie punktu początkowego rekurencji ogonowej z możliwością tworzenia powiązań leksykalnych. Powiązania te mogą być następnie aktualizowane przez wywoływanie recur. Dzięki loop możliwe jest budowanie anonimowych, rekurencyjnie wykonywanych podprogramów, które oszczędzają przestrzeń stosu.

Użycie:

  • (loop wektor-powiązaniowy & wyrażenie…).

Pierwszym przekazywanym argumentem powinien być wektor powiązaniowy, w którym dokonać możemy początkowego przypisania wartości do symbolicznych nazw (z możliwą dekompozycją). Kolejne, opcjonalne argumenty to wyrażenia stanowiące ciało konstrukcji. Będą one wartościowane za każdym jej wywołaniem, a w ich zasięgu leksykalnym można używać symboli powiązanych z wartościami w podanym wcześniej wektorze.

Ostatnimi wyrażeniami w ciele konstrukcji loop (pod względem poziomu zagłębienia w drzewie składniowym) mogą być wspomniane wcześniej wywołania recur. Ich obecność sprawi, że przetwarzanie wszystkich wyrażeń wewnątrz loop zacznie się od początku. Jako argumenty przekazywane do recur należy podać nowe wartości symboli obecnych w podanym jako pierwszy argument wektorze powiązaniowym. Umieszczać należy tylko wartości (odpowiedniki wyrażeń inicjujących lub argumentów pozycyjnych), a nie całe pary powiązaniowe.

Wartością zwracaną przez loop jest wartość ostatnio obliczonego wyrażenia lub wartość nil, jeśli żadne wyrażenie nie zostało obliczone w ostatnim przebiegu.

Przykład użycia loop i recur
1
2
3
4
5
(loop [n 12 acc 1]                ; wywołanie formuły specjalnej loop
  (if (zero? n)                   ;  · warunek zakończenia rekurencji
    acc                           ;    · przypadek bazowy
    (recur (dec n) (*' acc n))))  ;    · przypadek rekursywny
; => 479001600

Powyższy przykład z loop jest po prostu bardziej wydajnym odpowiednikiem następującego:

Przykład użycia fn do określenia punktu startowego dla recur
1
2
3
4
5
6
((fn [n acc]                      ; definicja i wywołanie funkcji anonimowej
  (if (zero? n)                   ;  · warunek zakończenia rekurencji
    acc                           ;    · przypadek bazowy
    (recur (dec n) (*' acc n))))  ;    · przypadek rekursywny
 12 1)                            ; argumenty wywołania funkcji
; => 479001600

Który z kolei możemy zapisać w postaci nieogonowej:

Przykład odpowiednika nieogonowego z wykorzystaniem fn
1
2
3
4
5
6
((fn ! [n acc]                    ; definicja i wywołanie funkcji anonimowej
  (if (zero? n)                   ;  · warunek zakończenia rekurencji
    acc                           ;    · przypadek bazowy
    (! (dec n) (*' acc n))))      ;    · przypadek rekursywny
 12 1)                            ; argumenty wywołania funkcji
; => 479001600

Rekurencja zagnieżdżona

Rekurencja zagnieżdżona (ang. nested recursion) to specyficzny rodzaj rekurencji, w którym dochodzi do odwołania się obiektu do samego siebie przez przekazanie jego dodatkowej instancji w argumencie wywołania.

Dobrym przykładem rekurencji zagnieżdżonej jest funkcja Ackermanna, która jest funkcją rekurencyjną, ale nie pierwotnie rekurencyjną:

Rekurencja zagnieżdżona na przykładzie funkcji Ackermanna
1
2
3
4
5
6
7
8
9
10
11
12
13
(defn acker [m n]                 ; definicja funkcji
  (cond                           ; warunki zakończenia rekurencji    
    (zero? m) (inc n)             ; przypadek bazowy
    (zero? n) (acker (dec m) 1)   ; przypadek rekursywny (rekurencja pierwotna)
    :else     (acker              ; przypadek rekursywny (rekurencja zagnieżdżona)
               (dec m)
               (acker m (dec n)))))

(acker 0  0)  ; => 1
(acker 1  0)  ; => 2
(acker 1  1)  ; => 3
(acker 2  2)  ; => 7
(acker 3 10)  ; >> #<StackOverflowError java.lang.StackOverflowError>

Z uwagi na bardzo szybki przyrost liczby wywołań użycie funkcji z powyższego przykładu szybko kończy się przepełnieniem stosu. Receptą na to może być przekształcenie algorytmu w taki sposób, aby korzystał z rekurencji ogonowej:

Przykład implementacji funkcji Ackermanna w wariancie ogonowym
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(defn acker [x y]                      ; definicja funkcji
  (loop [m x                           ; parametr m
         n y                           ; parametr n
         stos ()]                      ; lista akumulująca rezultaty
    (cond                              ; warunki zakończenia rekurencji
      (zero? m) (if (empty? stos)
                  (inc n)              ; przypadek bazowy
                  (recur (peek stos)   ; przypadek rekursywny
                         (inc n)
                         (pop stos)))
      (zero? n) (recur (dec m)         ; przypadek rekursywny
                       1
                       stos)
      :else     (recur m               ; przypadek rekursywny
                       (dec n)
                       (conj stos (dec m))))))

(acker 0  0)  ; => 1
(acker 1  0)  ; => 2
(acker 1  1)  ; => 3
(acker 2  2)  ; => 7
(acker 3 10)  ; => 8189

Zastosowaliśmy tu dodatkowy, trzeci argument, którego zadaniem jest przekazywanie rezultatów wywołań, które odzwierciedlają zmiany jednego z parametrów (m). Technika ta pozwala utworzyć własny wariant stosu dla pewnych danych, który może zajmować większy obszar pamięciowy, aby akumulować rezultaty pośrednie. W tym konkretnym przypadku własny stos pozwala składować efekty pracy dodatkowego wywołania, które w wersji nieogonowej jest zagnieżdżone.

Rekurencja pośrednia i wzajemna

Rekurencja pośrednia (ang. indirect recursion) to taki rodzaj rekurencji, w którym nie dochodzi do bezpośredniego odwołania się obiektu do samego siebie, lecz do odwołania do innego obiektu, który następnie korzysta z bieżącego.

Popularnym wariantem rekurencji pośredniej jest tzw. rekurencja wzajemna (ang. mutual recursion), gdzie kilka różnych obiektów naprzemiennie odwołuje się do siebie, aby realizować pewien algorytm.

Rekurencja wzajemna wywołań

Przykładem wzajemnej rekurencji mogą być naprzemienne wywołania dwóch lub większej liczby funkcji, np. w implementacji predykatów testujących parzystość i nieparzystość:

Przykład rekurencji pośredniej z wywołaniami funkcji
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(declare parzysta?)          ; deklaracja funkcji definiowanej później

(defn nieparzysta? [x]
  (and                       ; warunek zakończenia rekurencji
   (not= 0 x)                ; przypadek bazowy (gdy x równe 0)
   (parzysta? (dec x))))     ; przypadek rekursywny

(defn parzysta? [x]
  (or                        ; warunek zakończenia rekurencji
   (zero? x)                 ; przypadek bazowy (gdy x równe 0)
   (nieparzysta? (dec x))))  ; przypadek rekursywny

(nieparzysta? 0)  ; => false
(nieparzysta? 1)  ; => true
(nieparzysta? 2)  ; => false
(parzysta?    0)  ; => true
(parzysta?    1)  ; => false
(parzysta?    2)  ; => true

(nieparzysta? 2000000N)
; >> #<StackOverflowError java.lang.StackOverflowError>

W powyższym przykładzie funkcja nieparzysta? w przypadku rekursywnym dokonuje wywołania funkcji parzysta? dla podanego argumentu pomniejszonego o 1. Z kolei funkcja parzysta? robi to samo, wywołując funkcję parzysta?. W efekcie będziemy mieli do czynienia z szeregiem wartości, z których każda jest o 1 mniejsza od pozostałych.

Tak będzie wyglądał stos wywołań dla (parzysta? 4):

1
2
3
4
5
6
(parzysta? 4)
  (nieparzysta? 3)
    (parzysta? 2)
      (nieparzysta? 1)
        (parzysta? 0)
          true

A tak dla (nieparzysta? 4):

1
2
3
4
5
6
(nieparzysta? 4)
  (parzysta? 3)
    (nieparzysta? 2)
      (parzysta? 1)
        (nieparzysta? 0)
          false

Warto jednak zauważyć, że mamy tu do czynienia z rekurencją, która prowadzić może do wyczerpania miejsca pamięci stosu.

Optymalizacja rekurencji wzajemnej, trampoline

Funkcja trampoline jest pomocna w optymalizowaniu algorytmów, które bazują na rekurencji wzajemnej, ponieważ pomaga uniknąć zużycia całej dostępnej pamięci stosu. Warunkiem koniecznym jest jednak zdefiniowanie rekurencyjnie wywoływanych funkcji w taki sposób, aby zwracanymi przez nie wartościami były obiekty typu funkcyjnego, a dopiero one mogą zawierać rekurencyjne wywołania właściwych funkcji. Dzięki temu trampoline jest w stanie dokonywać redukcji rezultatów, korzystając z wewnętrznego akumulatora zamiast ze stosu.

Użycie:

  • (trampoline funkcja & argumenty).

Funkcja jako pierwszy, obowiązkowy argument przyjmuje funkcję, która zamiast rekurencyjnie wywoływać inną funkcję powinna zwracać obiekt funkcyjny dokonujący tej operacji. Kolejne, opcjonalne argumenty przekazywane do trampoline zostaną przekazane do podanej jej funkcji.

Jeżeli przekazana funkcja zwróci obiekt inny niż funkcję, zostanie to potraktowane jako przypadek bazowy i zwrócona będzie wartość, a wywoływanie kolejnych odwołujących się do siebie wzajemnie funkcji zakończy się.

Przykład rekurencji pośredniej, wzajemnej z użyciem funkcji trampoline
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defn fn-parzysta? [n]
  (or
   (zero? n)
   #(fn-nieparzysta? (dec n))))

(defn fn-nieparzysta? [n]
  (and
   (not= 0 n)
   #(fn-parzysta? (dec n))))

(defn parzysta?    [n] (trampoline fn-parzysta?    n))
(defn nieparzysta? [n] (trampoline fn-nieparzysta? n))

(nieparzysta? 2000000N)
; => false

Stos wywołań dla (nieparzysta? 3) przedstawia się tu następująco:

1
2
3
4
5
6
7
(nieparzysta? 3)
  (trampoline fn-nieparzysta? 3)
    (fn-nieparzysta? 3)
    (fn-parzysta? 2)
    (fn-nieparzysta? 1)
    (fn-parzysta? 0)
      true

Dzięki zastosowaniu funkcji trampoline uniknęliśmy odkładania na stos ramek zawierających adresy powrotne funkcji. Było to możliwe, ponieważ funkcja ta wywołuje każdy zwrócony obiekt funkcyjny, działając jak reduktor. Warunkiem jest oczywiście to, aby przypadki rekursywne były obsługiwane przez zwracanie obiektów funkcyjnych, a nie bezpośrednie wywoływanie funkcji.

Ostatni przykład możemy uprościć, korzystając z konstrukcji letfn, aby nie tworzyć publicznie dostępnych funkcji:

Przykład rekurencji pośredniej, wzajemnej (wersja z letfn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defn parzysta? [n]
  (letfn [(parzyste [x]
            (or
             (zero? x)
             #(nieparzyste (dec x))))
          (nieparzyste [x]
            (and
             (not= 0 x)
             #(parzyste (dec x))))]
    (trampoline parzyste n)))

(defn nieparzysta? [n] (not (parzysta? n)))

(nieparzysta? 2000000N)
; => false

Spójrzmy jeszcze na użycie trampoline w odniesieniu do implementacji silni:

Implementacja silni z użyciem trampoline
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(defn ! [n]
  (letfn
      [(następna-liczba [koniec nr poprzednia]           ; generuje kolejną wartość
         (let [następna (*' n poprzednia)]
           (if (= koniec nr)                             ; warunek zakończenia
             następna                                    ;   · przypadek bazowy
             #(następny-nr koniec nr następna))))        ;   · przypadek rekurencyjny

       (następny-nr [koniec p-nr bieżąca]                ; generuje kolejny element
         #(następna-liczba koniec (inc p-nr) bieżąca))]

    (trampoline następna-liczba (if (zero? n) 1 n) 1 1)))

(! 1)     ; => 1
(! 2)     ; => 2
(! 21)    ; => 51090942171709440000N
(! 7000)  ; => 884200795…000N

Leniwe sekwencje

Leniwe sekwencje mogą być przykładem praktycznego wykorzystania rekurencji pośredniej, gdy funkcja generująca odwołuje się do samej siebie przez wywołanie odpowiednich funkcji pośredniczących.

Warto zaznaczyć, że często będziemy mieć tu do czynienia z zewnętrznym warunkiem zakończenia rekurencji (w formie funkcji wyższego rzędu, np. pobierającej tylko podany zakres elementów).

Przykład rekurencyjnej funkcji generującej leniwą sekwencję
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(defn !
  ([n v]
   (let [nowa-n (inc n)
         nowa-v (*' n v)]
     (cons v (lazy-seq (! nowa-n nowa-v)))))
  ([n]
   (let [jeden (if (zero? n) 1 (/ n n))]
     (nth (! jeden jeden) n))))

(def s-silni (! 1 1))

(time (do (nth s-silni 1)     nil))  ; >> "Elapsed time: 0.082552 msecs"
(time (do (nth s-silni 20000) nil))  ; >> "Elapsed time: 1825.722463 msecs"
(time (do (nth s-silni 20000) nil))  ; >> "Elapsed time: 5.520258 msecs"
(time (do (nth s-silni 20001) nil))  ; >> "Elapsed time: 6.744783 msecs"
(time (do (nth s-silni 19999) nil))  ; >> "Elapsed time: 5.420101 msecs"

(! 1)     ; => 1
(! 2)     ; => 2
(! 21)    ; => 51090942171709440000N
(! 7000)  ; => 884200795…000N

W powyższym przykładzie mamy do czynienia z funkcją wieloczłonową o symbolicznej nazwie !, która w pierwszym wariancie przyjmuje dwa argumenty (nv), a w drugim jeden argument (n). Pierwszy wariant zwraca leniwą sekwencję kolejnych rozwinięć silni i jest funkcją rekurencyjną, natomiast drugi służy do pobierania konkretnego elementu tej sekwencji, czyli obliczania wartości silni dla podanego argumentu.

Argumenty nv wariantu rekurencyjnego są początkowo równe 1. Jest to przypadek bazowy. Następnie przeprowadzane są obliczenia, które generują dwie nowe wartości na bazie tych argumentów. W pierwszym wywołaniu rezultatami będą liczby 2 i 1. Druga z wartości (1) zostanie wpisana do pierwszego slotu obiektu typu Cons, której slot drugi będzie odnosił się do leniwej sekwencji, której funkcją generującą będzie rekurencyjne wywołanie ! z argumentami 21. Przy kolejnym rekurencyjnym wywołaniu będzie to 32, a przy następnym 46. Komórki cons dla pierwszych 4 elementów będą więc miały następujące zawartości:

[1 *]
    \
    [1 *]
        \
         [2 *]
             \
             [6 *]

W przykładzie możemy też zauważyć, że rekurencyjne wywołanie funkcji jest zawarte w ciele makra lazy-seq. Działa ono w ten sposób, że dla podanych wyrażeń zwraca obiekt typu LazySeq, który sprawi, że ich wartości zostaną obliczone tylko przy pierwszym odwołaniu do zwracanego obiektu, a rezultaty zostaną wewnętrznie spamiętane. Każde kolejne odwołanie do wynikowej sekwencji będzie już korzystało z wcześniej obliczonych wartości.

Spamiętywanie

Rekurencja ogonowa i zwracanie obiektów funkcyjnych w przypadkach rekursywnych nie są jedynymi sposobami optymalizacji rekurencyjnych algorytmów. Jeżeli danych nie jest zbyt wiele, możemy posłużyć się tzw. spamiętywaniem (ang. memoization). Proces ten polega na zapisywaniu wartości zwracanych przez funkcje, aby przy kolejnych ich wywołaniach korzystać z już obliczonych rezultatów. Bazą, w której przechowywane są wyniki, jest zazwyczaj asocjacyjna struktura danych (np. mapa), której kluczami są przyjmowane argumenty, chociaż możliwe jest też tworzenie bardziej (lub mniej) skomplikowanych buforów.

W Clojure możemy spamiętywanie zaimplementować samodzielnie, albo skorzystać z funkcji memoize:

Przykład spamiętywania wywołań silni z użyciem funkcji memoize
1
2
3
4
5
6
7
8
9
(defn !
  ([n] (! n 1))
  ([n acc] (if (zero? n) acc (recur (dec n) (*' acc n)))))

(def ! (memoize !))

(time (do (! 8000) nil))  ; >> "Elapsed time: 257.792908 msecs"
(time (do (! 8000) nil))  ; >> "Elapsed time: 0.0836 msecs"     (zapamiętany rezultat)
(time (do (! 7999) nil))  ; >> "Elapsed time: 294.067773 msecs"

Zauważmy, że w powyższym przykładzie nie mamy do czynienia z wykorzystaniem rezultatów pośrednich rekurencyjnych wywołań. Mimo że w siódmej linii przykładu obliczyliśmy rozwinięcia ciągu rezultatów funkcji silnia dla wartości 8000, to w linii ostatniej (dla 7999) obliczenia przeprowadzane są ponownie. Zapamiętany został tylko konkretny wynik.

Aby było inaczej, możemy zdefiniować własną funkcję buforującą, np. tak, jak to pokazano w sekcji poświęconej Atomom, albo wyrazić algorytm w postaci leniwej sekwencji.

Ten materiał jest częścią większej całości, którą można zobaczyć odwiedzając poniższy odnośnik:

Komentarze