Czy Haskell ma ogonową rekurencyjną optymalizację?

Odkryłem dzisiaj polecenie „time” w Uniksie i pomyślałem, że użyję go do sprawdzenia różnicy w czasie wykonywania między ogonowymi funkcjami rekurencyjnymi a normalnymi rekurencyjnymi funkcjami w Haskellu.

Napisałem następujące funkcje:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

Są one ważne, pamiętając, że były przeznaczone wyłącznie do użytku w tym projekcie, więc nie zawracałem sobie głowy sprawdzaniem zer ani liczb ujemnych.

Jednak po napisaniu głównej metody dla każdego z nich, skompilowaniu ich i uruchomieniu za pomocą polecenia „time”, obie miały podobne środowiska wykonawcze z normalną funkcją rekurencyjną, która wykraczała poza rekurencyjną ogonową. Jest to sprzeczne z tym, co słyszałem w odniesieniu do optymalizacji rekurencyjnej ogona w seplenie. Jaki jest tego powód?

Haskell używa leniwej oceny do implementacji rekurencji, więc traktuje wszystko jako obietnicę dostarczenia wartości w razie potrzeby (nazywa się to thunk). Thunks są zmniejszane tylko o tyle, o ile jest to konieczne do kontynuowania, nie więcej. Przypomina to sposób matematycznego upraszczania wyrażenia, więc warto pomyśleć o tym w ten sposób. Fakt, że kolejność oceny nie jest określona w Twoim kodzie, umożliwia kompilatorowi wykonanie wielu sprytniejszych optymalizacji niż tylko eliminacja wywołań końcowych, do których jesteś przyzwyczajony. Skompiluj z, -O2jeśli chcesz optymalizacji!

Zobaczmy, jak oceniamy facSlow 5jako studium przypadku:

facSlow 5
5 * facSlow 4            -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3)       -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2))  -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

Tak więc, tak jak się martwiłeś, mamy nagromadzenie liczb przed wykonaniem jakichkolwiek obliczeń, ale w przeciwieństwie do ciebie, martwisz się, że nie ma stosu facSlowwywołań funkcji czekających na zakończenie - każda redukcja jest stosowana i znika, pozostawiając ramkę stosu w swoim wake (to znaczy, ponieważ (*)jest ścisłe, a więc uruchamia ocenę drugiego argumentu).

Funkcje rekurencyjne Haskella nie są oceniane w bardzo rekurencyjny sposób! Jedynym stosem wywołań wiszących w pobliżu są same mnożenia. Jeśli (*)jest postrzegany jako ścisły konstruktor danych, jest to tak zwane rekursję chronioną (chociaż zwykle określa się ją jako taką w przypadku nieograniczonych konstruktorów danych, gdzie to, co po nim pozostaje, to konstruktory danych - gdy są wymuszane przez dalszy dostęp).

Spójrzmy teraz na rekurencyjny ogon fac 5:

fac 5
fac' 5 1
fac' 4 {5*1}       -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}}    -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}        -- the thunk "{...}" 
(2*{3*{4*{5*1}}})        -- is retraced 
(2*(3*{4*{5*1}}))        -- to create
(2*(3*(4*{5*1})))        -- the computation
(2*(3*(4*(5*1))))        -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120

Możesz więc zobaczyć, jak sama rekurencja ogona nie zaoszczędziła ci czasu ani miejsca. Nie tylko wymaga więcej kroków niż ogólnie facSlow 5, ale także tworzy zagnieżdżoną pozycję (pokazaną tutaj jako {...}) - wymagającą dodatkowej przestrzeni - która opisuje przyszłe obliczenia, zagnieżdżone mnożenia do wykonania.

Ten thunk następnie rozplatany przechodzenia go do dołu, ponowne obliczenie na stosie. Istnieje również niebezpieczeństwo spowodowania przepełnienia stosu przy bardzo długich obliczeniach dla obu wersji.

Jeśli chcemy to ręcznie zoptymalizować, wszystko, co musimy zrobić, to uściślić to. Do $!zdefiniowania można użyć ścisłego operatora aplikacji

facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
    facS' 1 y = y
    facS' x y = facS' (x-1) $! (x*y) 

To zmusza facS'do ścisłości w drugim argumencie. (Jest już ścisły w pierwszym argumencie, ponieważ należy go ocenić, aby zdecydować, którą definicję facS'zastosować.)

Czasami surowość może ogromnie pomóc, czasami jest to duży błąd, ponieważ lenistwo jest bardziej wydajne. Oto dobry pomysł:

facSlim 5
facS' 5 1
facS' 4 5 
facS' 3 20
facS' 2 60
facS' 1 120
120

Myślę, że to właśnie chciałeś osiągnąć.

Podsumowanie

• Jeśli chcesz zoptymalizować swój kod, pierwszym krokiem jest skompilowanie z -O2
• Rekurencja ogonowa jest dobra tylko wtedy, gdy nie ma nagromadzenia myśli, a dodanie ścisłości zwykle pomaga temu zapobiec, jeśli i gdzie jest to stosowne. Dzieje się tak, gdy tworzysz wynik, który jest potrzebny później na raz.
• Czasami rekurencja ogonowa jest złym planem, a rekursja strzeżona jest lepszym rozwiązaniem, tj. Gdy tworzony wynik będzie potrzebny kawałek po kawałku, w częściach. Zobacz to pytanie o foldr, a foldlna przykład i przetestować je przed sobą.

Wypróbuj te dwa:

length $ foldl1 (++) $ replicate 1000 
    "The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000 
    "The number of reductions performed is more important than tail recursion!!!"

foldl1jest rekurencyjny ogon, podczas gdy foldr1wykonuje rekursję chronioną, dzięki czemu pierwsza pozycja jest natychmiast przedstawiana do dalszego przetwarzania / dostępu. _{(Pierwszy „nawiasy” od razu po lewej stronie (...((s+s)+s)+...)+s, wymuszając pełną listę danych wejściowych do końca i budując dużą część przyszłych obliczeń znacznie wcześniej niż potrzebne są pełne wyniki; drugi nawias stopniowo w prawo s+(s+(...+(s+s)...)), zużywając dane wejściowe lista kawałek po kawałku, więc całość może działać w stałej przestrzeni, z optymalizacjami).}

Może być konieczne dostosowanie liczby zer w zależności od używanego sprzętu.

Należy wspomnieć, że facfunkcja nie jest dobrym kandydatem do chronionej rekursji. Najlepszą metodą jest rekurencja ogona. Z powodu lenistwa nie uzyskujesz efektu całkowitego kosztu posiadania w swojej fac'funkcji, ponieważ argumenty akumulatorów wciąż budują duże uderzenia, które po oszacowaniu będą wymagały dużego stacka. Aby temu zapobiec i uzyskać pożądany efekt całkowitego kosztu posiadania, należy uściślić te argumenty akumulacyjne.

{-# LANGUAGE BangPatterns #-}

fac :: (Integral a) => a -> a
fac x = fac' x 1 where
  fac' 1  y = y
  fac' x !y = fac' (x-1) (x*y)

Jeśli kompilujesz przy użyciu -O2(lub tylko -O) GHC, prawdopodobnie zrobi to samodzielnie w fazie analizy ścisłości .

Powinieneś sprawdzić artykuł wiki o rekurencji ogonów w Haskell . W szczególności, ze względu na ocenę wyrażenia, żądany rodzaj rekursji jest rekursją chronioną . Jeśli opracujesz szczegóły tego, co dzieje się pod maską (w abstrakcyjnej maszynie dla Haskella), otrzymasz to samo, co w przypadku rekurencji ogonowej w językach ścisłych. Oprócz tego masz jednolitą składnię dla leniwych funkcji (rekurencja ogonowa wiąże cię ze ścisłą oceną, podczas gdy rekursja chroniona działa bardziej naturalnie).

(A jeśli chodzi o naukę Haskella, reszta tych stron wiki też jest niesamowita!)

Jeśli dobrze pamiętam, GHC automatycznie optymalizuje zwykłe funkcje rekurencyjne do zoptymalizowanych funkcji ogonowo-rekurencyjnych.