Jaka właściwość wad pozwala na wyeliminowanie wad modulo ogona rekurencyjnego?

Znam ideę podstawowej eliminacji rekurencji ogona, w której funkcje, które zwracają bezpośredni wynik wywołania do siebie, można przepisać jako pętle iteracyjne.

foo(...):
    # ...
    return foo(...)

Rozumiem również, że jako szczególny przypadek funkcja może być nadal przepisana, jeśli wywołanie rekurencyjne jest zawinięte w wywołanie do cons.

foo(...):
    # ...
    return (..., foo(...))

Jaka właściwość na consto pozwala? Jakie funkcje poza conszawijaniem rekurencyjnego wywołania ogona bez niszczenia naszej możliwości jego iteracyjnego przepisywania?

GCC (ale nie Clang) jest w stanie zoptymalizować ten przykład „ mnożenia modulo rekurencji ogona ”, ale nie jest jasne, jaki mechanizm pozwala mu to odkryć ani jak dokonuje jego transformacji.

pow(x, n):
    if n == 0: return 1
    else if n == 1: return x
    else: return x * pow(x, n-1)

Chociaż GCC prawdopodobnie stosuje reguły ad-hoc, możesz je uzyskać w następujący sposób. Użyję powdo zilustrowania, ponieważ jesteś footak niejasno zdefiniowany. Można również foonajlepiej rozumieć jako przykład optymalizacji ostatniego wywołania w odniesieniu do zmiennych pojedynczego przypisania, jak ma język Oz i jak omówiono w Pojęciach, technikach i modelach programowania komputerowego . Zaletą stosowania zmiennych pojedynczego przypisania jest to, że pozwala pozostać w deklaratywnym paradygmacie programowania. Zasadniczo możesz mieć każde pole foozwrotów struktury reprezentowane przez zmienne pojedynczego przypisania, które są następnie przekazywane foojako dodatkowe argumenty. foonastępnie staje się rekurencyjnymvoidfunkcja powrotu Nie jest do tego wymagana szczególna spryt.

Wracając pownajpierw do transformacji w styl kontynuacji przejścia . powstaje się:

pow(x, n):
    return pow2(x, n, x => x)

pow2(x, n, k):
    if n == 0: return k(1)
    else if n == 1: return k(x)
    else: return pow2(x, n-1, y => k(x*y))

Wszystkie połączenia są teraz połączeniami ogonowymi. Jednak stos kontrolny został przeniesiony do przechwyconych środowisk w zamknięciach reprezentujących kontynuacje.

Następnie zdefunkcjonalizuj kontynuacje. Ponieważ istnieje tylko jedno wywołanie rekurencyjne, wynikowa struktura danych reprezentująca zdefunkcjonalizowane kontynuacje jest listą. Otrzymujemy:

pow(x, n):
    return pow2(x, n, Nil)

pow2(x, n, k):
    if n == 0: return applyPow(k, 1)
    else if n == 1: return applyPow(k, x)
    else: return pow2(x, n-1, Cons(x, k))

applyPow(k, acc):
    match k with:
        case Nil: return acc
        case Cons(x, k):
            return applyPow(k, x*acc)

Wystarczy applyPow(k, acc)wziąć listę, czyli wolną monoidę, polub ją k=Cons(x, Cons(x, Cons(x, Nil)))i zrób z niej x*(x*(x*acc)). Ale ponieważ *jest asocjacyjny i generalnie tworzy monoid z jednostką 1, możemy ponownie powiązać to z ((x*x)*x)*acc, i, dla uproszczenia, przyczepić się 1do rozpoczęcia produkcji (((1*x)*x)*x)*acc. Kluczową sprawą jest to, że możemy częściowo obliczyć wynik, zanim jeszcze to zrobimy acc. Oznacza to, że zamiast przekazywać kjako listę, która jest w zasadzie jakąś niepełną „składnią”, którą „zinterpretujemy” na końcu, możemy „zinterpretować” ją na bieżąco. Rezultatem jest to, że możemy zastąpić Niljednostką monoidu, 1w tym przypadku, i Consdziałaniem monoidu *, a teraz kreprezentuje „działający produkt”.applyPow(k, acc)staje się właśnie k*acctym, w co możemy ponownie włączyć pow2i uprościć tworzenie:

pow(x, n):
    return pow2(x, n, 1)

pow2(x, n, k):
    if n == 0: return k
    else if n == 1: return k*x
    else: return pow2(x, n-1, k*x)

Oryginalna wersja w stylu rekurencyjnej, przypominającej akumulator pow.

Oczywiście nie mówię, że GCC robi cały ten tok rozumowania w czasie kompilacji. Nie wiem, jakiej logiki używa GCC. Chodzi mi o to, że raz to rozumowałem, stosunkowo łatwo jest rozpoznać wzorzec i natychmiast przetłumaczyć oryginalny kod źródłowy na ostateczną formę. Jednak transformacja CPS i transformacja defunkcjonalizacyjna są całkowicie ogólne i mechaniczne. Stamtąd można zastosować techniki syntezy, wylesiania lub superkompilacji, aby spróbować wyeliminować powtórzone kontynuacje. Transformacje spekulacyjne można odrzucić, jeśli nie można wyeliminować całego przydziału powtórzonych kontynuacji. Podejrzewam jednak, że byłoby to zbyt kosztowne, aby robić to przez cały czas, w ogólnym ujęciu, stąd więcej podejść ad hoc.

Jeśli chcesz być śmieszny, możesz przeczytać artykuł Recycling Continuations, który również wykorzystuje CPS i reprezentacje kontynuacji jako danych, ale robi coś podobnego, ale różniącego się od modulo-konsolidacji ogona-rekurencji. Opisuje, w jaki sposób można tworzyć algorytmy odwracania wskaźnika przez transformację.

Ten wzorzec transformacji i defekcjonalizacji CPS jest dość potężnym narzędziem do zrozumienia i jest stosowany z dobrym skutkiem w serii artykułów, które tu wymieniam .

Będę przez jakiś czas owijać w bawełnę, ale jest sens.

Półgrupy

Odpowiedź brzmi: asocjacyjna właściwość operacji binarnej redukcji .

To dość abstrakcyjne, ale mnożenie jest dobrym przykładem. Jeśli x , y i z są pewnymi liczbami naturalnymi (lub liczbami całkowitymi, liczbami wymiernymi, liczbami rzeczywistymi, liczbami zespolonymi, macierzami N × N lub dowolną liczbą innych elementów), to x × y jest tego samego rodzaju liczby jako zarówno x, jak i y . Zaczęliśmy od dwóch liczb, więc jest to operacja binarna, i otrzymaliśmy jedną, więc zmniejszyliśmy liczbę liczb o jedną, dzięki czemu jest to operacja redukcji. A ( x × y ) × z jest zawsze takie samo jak x × ( y ×z ), która jest własnością asocjacyjną.

(Jeśli już to wszystko wiesz, możesz przejść do następnej sekcji).

Kilka innych rzeczy, które często widzisz w informatyce, które działają w ten sam sposób:

• dodawanie dowolnego z tych liczb zamiast mnożenia
• łączenie ciągów ( "a"+"b"+"c"to "abc", czy rozpocząć "ab"+"c"lub "a"+"bc")
• Łącząc dwie listy razem. [a]++[b]++[c]jest podobnie [a,b,c]albo od tyłu do przodu lub od przodu do tyłu.
• consna głowie i ogonie, jeśli myślisz o głowie jako liście singletonów. To tylko połączenie dwóch list.
• biorąc związek lub przecięcie zbiorów
• Boolean i, Boolean lub
• bitowe &, |i^
• skład funkcji: ( f ∘ g ) ∘ h x = f ∘ ( g ∘ h ) x = f ( g ( h ( x )))
• maksimum i minimum
• dodatek modulo p

Niektóre rzeczy, które nie:

• odejmowanie, ponieważ 1- (1-2) ≠ (1-1) -2
• x ⊕ y = tan ( x + y ), ponieważ tan (π / 4 + π / 4) jest niezdefiniowany
• mnożenie przez liczby ujemne, ponieważ -1 × -1 nie jest liczbą ujemną
• podział liczb całkowitych, który ma wszystkie trzy problemy!
• logiczne nie, ponieważ ma tylko jeden operand, a nie dwa
• int print2(int x, int y) { return printf( "%d %d\n", x, y ); }, jak print2( print2(x,y), z );i print2( x, print2(y,z) );mają różne dane wyjściowe.

Nazwaliśmy go wystarczająco przydatną koncepcją. Zestaw z operacją, która ma te właściwości, jest półgrupą . Tak więc liczby rzeczywiste po pomnożeniu są półgrupą. A twoje pytanie okazuje się jednym ze sposobów, w jaki taka abstrakcja staje się przydatna w prawdziwym świecie. Operacje na półgrupach można zoptymalizować tak, jak pytasz.

Wypróbuj to w domu

O ile mi wiadomo, technika ta została po raz pierwszy opisana w 1974 r. W pracy Daniela Friedmana i Davida Wise'a „Składanie stylizowanych rekurencji w iteracjach” , chociaż przyjęli oni kilka więcej właściwości, niż się okazało, że musieli.

Haskell jest świetnym językiem do zilustrowania tego, ponieważ ma Semigroupklasę w swojej standardowej bibliotece. Nazywa to operacją rodzajową Semigroupoperator <>. Ponieważ listy i łańcuchy są instancjami Semigroup, ich instancje definiują na przykład <>jako operator konkatenacji ++. A przy odpowiednim imporcie [a] <> [b]jest alias [a] ++ [b], który jest [a,b].

Ale co z liczbami? Właśnie widzieliśmy, że typy liczbowe to półgrupy z dodawaniem lub mnożeniem! Który może być <>dla Double? Cóż, jedno z nich! Haskell określa typy Product Double, where (<>) = (*)(to znaczy rzeczywista definicja Haskell), a także Sum Double, where (<>) = (+).

Jedna zmarszczka polega na tym, że wykorzystałeś fakt, że 1 to tożsamość multiplikatywna. Półgrupa z tożsamością nazywana jest monoidem i jest zdefiniowana w pakiecie Haskell Data.Monoid, który wywołuje ogólny element tożsamości klasy mempty. Sum, Producta lista ma każdy element tożsamości (odpowiednio 0, 1 i []), więc są to zarówno wystąpienia, Monoidjak i Semigroup. (Nie mylić z monadą , więc zapomnij, że nawet je wychowałem.)

To wystarczająca ilość informacji, aby przetłumaczyć twój algorytm na funkcję Haskella za pomocą monoidów:

module StylizedRec (pow) where

import Data.Monoid as DM

pow :: Monoid a => a -> Word -> a
{- Applies the monoidal operation of the type of x, whatever that is, by
 - itself n times.  This is already in Haskell as Data.Monoid.mtimes, but
 - let’s write it out as an example.
 -}
pow _ 0 = mempty -- Special case: Return the nullary product.
pow x 1 = x      -- The base case.
pow x n = x <> (pow x (n-1)) -- The recursive case.

Co ważne, zauważ, że jest to półgrupa modulo rekurencji ogona: każdy przypadek jest albo wartością, wywołaniem rekurencyjnym ogona, albo iloczynem półgrupy obu. Ten przykład przydał się również memptyw jednym z przypadków, ale gdybyśmy go nie potrzebowali, moglibyśmy to zrobić przy użyciu bardziej ogólnej klasy Semigroup.

Załadujmy ten program do GHCI i zobaczmy, jak to działa:

*StylizedRec> getProduct $ pow 2 4
16
*StylizedRec> getProduct $ pow 7 2
49

Pamiętasz, jak zadeklarowaliśmy powrodzaj ogólny Monoid, którego typ nazwaliśmy a? Daliśmy GHCI wystarczających informacji, aby wywnioskować, że typ ao to Product Integer, co stanowi instanceo Monoidktórych <>praca jest liczbą całkowitą mnożenia. Tak pow 2 4rozwija się rekurencyjnie 2<>2<>2<>2, który jest 2*2*2*2lub 16. Jak na razie dobrze.

Ale nasza funkcja używa tylko ogólnych operacji monoidów. Wcześniej mówiłem, że istnieje inna instancja Monoidwywołana Sum, której <>operacją jest +. Czy możemy tego spróbować?

*StylizedRec> getSum $ pow 2 4
8
*StylizedRec> getSum $ pow 7 2
14

To samo rozszerzenie daje nam teraz 2+2+2+2zamiast 2*2*2*2. Mnożenie jest dodawaniem, ponieważ potęgowanie polega na mnożeniu!

Podałem jednak jeszcze jeden przykład monoidu Haskella: listy, których operacja polega na konkatenacji.

*StylizedRec> pow [2] 4
[2,2,2,2]
*StylizedRec> pow [7] 2
[7,7]

Pisanie [2]informuje kompilator, że jest to lista, <>na listach jest ++, tak [2]++[2]++[2]++[2]jest [2,2,2,2].

Wreszcie algorytm (dwa, w rzeczywistości)

Przez prostą wymianę xz [x], konwertowanie ogólny algorytm, który używa rekursji modulo półgrupa na taki, który tworzy listę. Która lista Lista elementów, których dotyczy algorytm <>. Ponieważ użyliśmy tylko operacji na półgrupach, które również mają listy, wynikowa lista będzie izomorficzna w stosunku do pierwotnego obliczenia. A ponieważ pierwotna operacja była asocjacyjna, równie dobrze możemy ocenić elementy od tyłu do przodu lub od przodu do tyłu.

Jeśli Twój algorytm kiedykolwiek osiągnie przypadek podstawowy i zakończy działanie, lista nie będzie pusta. Ponieważ sprawa terminalu zwróciła coś, będzie to ostatni element listy, więc będzie miała co najmniej jeden element.

Jak zastosować binarną operację redukcji do każdego elementu listy w kolejności? Zgadza się, fold. Więc można zastąpić [x]przez x, uzyskać listę elementów, aby zmniejszyć przez <>, a następnie albo w prawo lub w lewo-fold-krotnie listy:

*StylizedRec> getProduct $ foldr1 (<>) $ pow [Product 2] 4
16
*StylizedRec> import Data.List
*StylizedRec Data.List> getProduct $ foldl1' (<>) $ pow [Product 2] 4
16

Wersja z foldr1faktycznie istnieje w standardowej bibliotece, zarówno sconcatdla , jak Semigroupi mconcatdla Monoid. Robi leniwy prawy fold na liście. Oznacza to, że rozszerza [Product 2,Product 2,Product 2,Product 2]się 2<>(2<>(2<>(2))).

W tym przypadku nie jest to skuteczne, ponieważ nie możesz nic zrobić z poszczególnymi warunkami, dopóki nie wygenerujesz wszystkich z nich. (W pewnym momencie miałem tutaj dyskusję na temat tego, kiedy stosować prawe fałdy, a kiedy ścisłe lewe fałdy, ale poszło to zbyt daleko.)

Wersja z foldl1'jest ściśle ocenianą lewą zakładką. Oznacza to, że funkcja rekurencyjna ogona ze ścisłym akumulatorem. To (((2)<>2)<>2)<>2oblicza, obliczane natychmiast, a nie później, gdy jest to potrzebne. (Przynajmniej nie ma żadnych opóźnień w owczarni się. Listę zagiętą generowany jest tutaj przez inną funkcję, które mogą zawierać ocenę leniwy) Tak, zagięcia oblicza (4<>2)<>2, a następnie natychmiast oblicza 8<>2, potem 16. Właśnie dlatego potrzebowaliśmy, aby operacja była asocjacyjna: właśnie zmieniliśmy grupowanie nawiasów!

Ściśle lewy pas jest odpowiednikiem tego, co robi GCC. Najbardziej wysunięta w lewo liczba w poprzednim przykładzie to akumulator, w tym przypadku działający produkt. Na każdym kroku jest on mnożony przez następny numer na liście. Innym sposobem wyrażenia tego jest: iterujesz wartości, które chcesz pomnożyć, utrzymując działający produkt w akumulatorze, a przy każdej iteracji mnożymy akumulator przez następną wartość. Oznacza to, że jest to whilepętla w przebraniu.

Czasami może być tak samo wydajny. Kompilator może być w stanie zoptymalizować strukturę danych listy w pamięci. Teoretycznie ma wystarczająco dużo informacji w czasie kompilacji, aby dowiedzieć się, że powinien to zrobić tutaj: [x]jest singletonem, więc [x]<>xsjest taki sam jak cons x xs. Każda iteracja funkcji może być w stanie ponownie użyć tej samej ramki stosu i zaktualizować parametry w miejscu.

W danym przypadku bardziej odpowiednie może być prawe lub ścisłe lewe pasowanie, więc wiedz, który z nich chcesz. Są też rzeczy, które może wykonać tylko prawy fold (np. Generowanie interaktywnego wyjścia bez czekania na wszystkie dane wejściowe i działanie na nieskończonej liście). Tutaj jednak redukujemy sekwencję operacji do prostej wartości, więc chcemy ścisłego zagięcia w lewo.

Tak więc, jak widać, możliwe jest automatyczne optymalizowanie modułu rekurencji ogona dowolnej półgrupy (jednym z przykładów jest dowolny z typowych typów numerycznych pod zwielokrotnieniem) do leniwego prawego fałdu lub ścisłego lewego fałdu w jednej linii Haskell.

Dalsze uogólnianie

Dwa argumenty operacji binarnej nie muszą być tego samego typu, o ile wartość początkowa jest tego samego typu co wynik. (Oczywiście możesz zawsze odwracać argumenty, aby dopasować kolejność składania, którą wykonujesz, w lewo lub w prawo.) Możesz więc wielokrotnie dodawać łaty do pliku, aby uzyskać zaktualizowany plik, lub zaczynając od wartości początkowej 1.0, podziel przez liczby całkowite, aby zgromadzić wynik zmiennoprzecinkowy. Lub dodaj elementy do pustej listy, aby uzyskać listę.

Innym typem uogólnienia jest stosowanie fałd nie do list, ale do innych Foldablestruktur danych. Często niezmienna liniowo połączona lista nie jest strukturą danych, którą chcesz dla danego algorytmu. Jedną kwestią, o której nie wspomniałem powyżej, jest to, że o wiele bardziej wydajne jest dodawanie elementów z przodu listy niż z tyłu, a gdy operacja nie jest przemienna, zastosowanie xpo lewej i prawej stronie operacji nie jest to samo. Musisz więc użyć innej struktury, takiej jak para list lub drzewo binarne, aby przedstawić algorytm, który można zastosować zarówno xpo prawej, <>jak i po lewej stronie.

Należy również pamiętać, że właściwość asocjacyjna umożliwia przegrupowanie operacji na inne użyteczne sposoby, takie jak podział i podbij:

times :: Monoid a => a -> Word -> a
times _ 0 = mempty
times x 1 = x
times x n | even n    = y <> y
          | otherwise = x <> y <> y
  where y = times x (n `quot` 2)

Lub automatyczny paralelizm, w którym każdy wątek redukuje podzakres do wartości, która jest następnie łączona z innymi.