Czy języki funkcjonalne są lepsze w rekurencji?


41

TL; DR: Czy języki funkcjonalne lepiej radzą sobie z rekurencją niż języki niefunkcjonalne?

Obecnie czytam Code Complete 2. W pewnym momencie książki autor ostrzega nas przed rekurencją. Mówi, że należy tego unikać, gdy jest to możliwe, a funkcje wykorzystujące rekurencję są na ogół mniej skuteczne niż rozwiązanie wykorzystujące pętle. Na przykład autor napisał funkcję Java, używając rekurencji do obliczenia silni liczby w ten sposób (może nie być dokładnie taka sama, ponieważ w tej chwili nie mam ze sobą książki):

public int factorial(int x) {
    if (x <= 0)
        return 1;
    else
        return x * factorial(x - 1);
}

Jest to przedstawiane jako złe rozwiązanie. Jednak w językach funkcjonalnych używanie rekurencji jest często preferowanym sposobem działania. Na przykład tutaj jest funkcja silni w Haskell przy użyciu rekurencji:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

I jest powszechnie akceptowane jako dobre rozwiązanie. Jak widziałem, Haskell bardzo często korzysta z rekurencji i nigdzie nie widziałem, żeby się jej skrzywiła.

Więc moje pytanie w zasadzie brzmi:

  • Czy języki funkcjonalne lepiej radzą sobie z rekurencją niż języki niefunkcjonalne?

EDYCJA: Mam świadomość, że przykłady, których użyłem, nie są najlepsze do zilustrowania mojego pytania. Chciałem tylko zauważyć, że Haskell (i ogólnie języki funkcjonalne) znacznie częściej korzysta z rekurencji niż języki niefunkcjonalne.


10
Przykład: wiele języków funkcjonalnych często wykorzystuje optymalizację wywołania ogona, podczas gdy robi to bardzo niewiele języków proceduralnych. Oznacza to, że rekurencja wywołania ogona jest znacznie tańsza w tych językach funkcjonalnych.
Joachim Sauer

7
W rzeczywistości podana przez ciebie definicja Haskella jest dość zła. factorial n = product [1..n]jest bardziej zwięzły, wydajniejszy i nie przepełnia stosu dla dużych n(a jeśli potrzebujesz zapamiętywania, wymagane są zupełnie inne opcje). productjest zdefiniowany w kategoriach niektórych fold, które zdefiniowane rekurencyjnie, ale z najwyższą ostrożnością. Rekurencja jest akceptowalnym rozwiązaniem przez większość czasu, ale nadal łatwo jest zrobić to źle / nieoptymalnie.

1
@ JoachimSauer - Przy odrobinie ozdoby Twój komentarz byłby wartościową odpowiedzią.
Mark Booth

Twoja edycja wskazuje, że nie złapałeś mojego dryfu. Podana definicja jest doskonałym przykładem rekurencji, która jest zła nawet w językach funkcjonalnych . Moja alternatywa jest również rekurencyjna (chociaż jest w funkcji biblioteki) i bardzo wydajna, tylko sposób, w jaki się powtarza, robi różnicę. Haskell jest również dziwnym przypadkiem, ponieważ lenistwo łamie zwykłe zasady (przypadek: funkcje mogą przepełniać stos, będąc rekurencyjnym ogonem i być bardzo wydajnym bez rekurencji ogona).

@delnan: Dzięki za wyjaśnienie! Zmienię edycję;)
marco-fiset

Odpowiedzi:


36

Tak, robią to, ale nie tylko dlatego, że mogą , ale dlatego, że muszą .

Kluczową koncepcją jest tutaj czystość : czysta funkcja jest funkcją bez skutków ubocznych i bez stanu. Funkcjonalne języki programowania ogólnie obejmują czystość z wielu powodów, takich jak rozumowanie kodu i unikanie nieoczywistych zależności. Niektóre języki, zwłaszcza Haskell, posuwają się nawet tak daleko, że dopuszczają tylko czysty kod; wszelkie skutki uboczne, które może mieć program (takie jak wykonywanie operacji we / wy), są przenoszone do nieczystego środowiska wykonawczego, utrzymując czysty język.

Brak efektów ubocznych oznacza, że ​​nie możesz mieć liczników pętli (ponieważ licznik pętli stanowiłby stan zmienny, a modyfikacja takiego stanu byłaby efektem ubocznym), więc najbardziej iteracyjną, jaką może uzyskać czysty język funkcjonalny, jest iteracja po liście ( ta operacja jest zwykle nazywana foreachlub map). Jednak rekurencja jest naturalnym dopasowaniem z czystym programowaniem funkcjonalnym - żaden stan nie jest potrzebny do rekurencji, z wyjątkiem argumentów funkcji (tylko do odczytu) i wartości zwracanej (tylko do zapisu).

Jednak brak efektów ubocznych oznacza również, że rekurencja może być zaimplementowana wydajniej, a kompilator może ją zoptymalizować bardziej agresywnie. Nie badałem dogłębnie żadnego takiego kompilatora, ale o ile wiem, kompilatory większości funkcjonalnych języków programowania wykonują optymalizację wywołania ogonowego, a niektóre mogą nawet kompilować pewne rodzaje konstrukcji rekurencyjnych w pętlach za kulisami.


2
Dla przypomnienia, eliminacja ogonów nie zależy od czystości.
szalik

2
@scarfridge: Oczywiście, że nie. Jeśli jednak podana jest czystość, kompilatorowi łatwiej jest zmienić kolejność kodu, aby umożliwić wywołania ogona.
tdammers

GCC wykonuje znacznie lepszą pracę w zakresie TCO niż GHC, ponieważ nie można zrobić TCO w całym tworzeniu thunk.
dan_waterworth

18

Porównujesz rekurencję z iteracją. Bez eliminacji wywołania ogonowego iteracja jest rzeczywiście bardziej wydajna, ponieważ nie ma dodatkowego wywołania funkcji. Również iteracja może trwać wiecznie, podczas gdy możliwe jest, że zabraknie miejsca na stosie z powodu zbyt wielu wywołań funkcji.

Jednak iteracja wymaga zmiany licznika. Oznacza to, że musi istnieć zmienna zmienna , która jest zabroniona w czysto funkcjonalnym otoczeniu. Tak więc języki funkcjonalne są specjalnie zaprojektowane do działania bez potrzeby iteracji, stąd usprawnione wywołania funkcji.

Ale żadna z tych odpowiedzi nie wyjaśnia, dlaczego przykładowy kod jest tak elegancki. Twój przykład pokazuje inną właściwość, którą jest dopasowanie wzorca . Dlatego próbka Haskell nie ma wyraźnych warunków warunkowych. Innymi słowy, to nie usprawniona rekurencja sprawia, że ​​kod jest mały; to dopasowanie wzoru.


Wiem już, o co chodzi w dopasowywaniu wzorców i myślę, że jest to niesamowita funkcja w Haskell, za którą tęsknię w językach, których używam!
marco-fiset

@marcof Chodzi mi o to, że cała rozmowa na temat rekurencji vs iteracji nie odnosi się do elegancji twojej próbki kodu. Naprawdę chodzi o dopasowanie wzorca do warunków. Być może powinienem był to zrobić w mojej odpowiedzi.
chrisaycock

Tak, też to zrozumiałem: P
marco-fiset

@chrisaycock: Czy byłoby możliwe postrzeganie iteracji jako rekurencji ogona, w której wszystkie zmienne użyte w treści pętli są argumentami i zwracają wartości wywołań rekurencyjnych?
Giorgio

@Giorgio: Tak, spraw, aby funkcja wzięła i zwróciła krotkę tego samego typu.
Ericson2314,

5

Technicznie nie, ale praktycznie tak.

Rekurencja jest o wiele bardziej powszechna, gdy funkcjonalnie podchodzisz do problemu. Jako takie, języki zaprojektowane z myślą o funkcjonalnym podejściu często zawierają funkcje, które sprawiają, że rekursja jest łatwiejsza / lepsza / mniej problematyczna. Z czubka mojej głowy są trzy typowe:

  1. Optymalizacja ogona. Jak podkreślają inne plakaty, języki funkcjonalne często wymagają TCO.

  2. Leniwa ocena. Haskell (i kilka innych języków) jest leniwie oceniany. Opóźnia to faktyczną „pracę” metody, dopóki nie będzie wymagana. Prowadzi to do powstania bardziej rekurencyjnych struktur danych, a przez to rekurencyjnych metod ich pracy.

  3. Niezmienność. Większość rzeczy, z którymi pracujesz w funkcjonalnych językach programowania, jest niezmienna. Ułatwia to rekurencję, ponieważ nie musisz martwić się stanem obiektów w czasie. Na przykład nie możesz zmienić wartości pod spodem. Ponadto wiele języków zostało zaprojektowanych do wykrywania czystych funkcji . Ponieważ czyste funkcje nie mają skutków ubocznych, kompilator ma dużo większą swobodę w ustalaniu kolejności uruchamiania funkcji i innych optymalizacji.

Żadna z tych rzeczy nie jest tak naprawdę specyficzna dla języków funkcjonalnych w porównaniu do innych, więc nie są po prostu lepsze, ponieważ są funkcjonalne. Ale ponieważ są funkcjonalne, podejmowane decyzje projektowe będą zmierzać w kierunku tych funkcji, ponieważ są one bardziej użyteczne (a ich wady mniej problematyczne) podczas programowania funkcjonalnego.


1
Re: 1. Wczesne powroty nie mają nic wspólnego z ogonami. Możesz wrócić wcześnie z ogonem, a „późny” powrót ma także ogon, i możesz mieć jedno proste wyrażenie z rekurencyjnym wezwaniem nie w pozycji ogona (por. Definicja czynnikowa OP).

@delnan: Dzięki; jest wcześnie i minęło sporo czasu, odkąd to studiowałem.
Telastyn

1

Haskell i inne języki funkcjonalne zwykle używają leniwej oceny. Ta funkcja umożliwia pisanie niekończących się funkcji rekurencyjnych.

Jeśli napiszesz funkcję rekurencyjną bez zdefiniowania podstawowego przypadku, w którym kończy się rekurencja, skończysz z nieskończonymi wywołaniami tej funkcji i przepełnieniem stosu.

Haskell obsługuje również optymalizacje rekurencyjnych wywołań funkcji. W Javie każde wywołanie funkcji nakładałoby się na siebie i powodowało obciążenie.

Tak więc, funkcjonalne języki radzą sobie z rekurencją lepiej niż inne.


5
Haskell jest jednym z niewielu nie-ścisłych języków - cała rodzina ML (poza niektórymi spinoffami badawczymi, które dodają lenistwo), wszystkie popularne Lisps, Erlang itp. Są surowe. Również drugi akapit wydaje się - jak słusznie stwierdza w akapicie pierwszym, lenistwo nie pozwala nieskończonej rekurencji (preludium Haskell ma niezmiernie użyteczne forever a = a >> forever ana przykład).

@deinan: O ile mi wiadomo, SML / NJ oferuje również leniwe oceny, ale jest to dodatek do SML. Chciałem też wymienić dwa z kilku leniwych języków funkcjonalnych: Miranda i Clean.
Giorgio

1

Jedynym powodem technicznym, jaki znam, jest to, że niektóre języki funkcjonalne (i niektóre języki imperatywne, jeśli pamiętam) mają tak zwaną optymalizację wywołania ogonowego, która pozwala metodzie rekurencyjnej nie zwiększać wielkości stosu przy każdym wywołaniu rekurencyjnym (tj. Wywołanie rekurencyjne mniej więcej zastępuje bieżące wywołanie na stosie).

Zauważ, że ta optymalizacja nie działa na żadnym wywołaniu rekurencyjnym, tylko na metodach rekurencyjnych typu tail-call (tj. Metodach, które nie utrzymują stanu w momencie wywołania rekurencyjnego)


1
(1) Taka optymalizacja ma zastosowanie tylko w bardzo szczególnych przypadkach - przykładem OP nie są one, a wiele innych prostych funkcji wymaga szczególnej uwagi, aby stać się rekurencyjnym. (2) Optymalizacja rzeczywistego wywołania ogonowego nie tylko optymalizuje funkcje rekurencyjne, ale usuwa narzut miejsca z każdego wywołania, po którym następuje natychmiast powrót.

@delnan: (1) Tak, bardzo prawdziwe. W „oryginalnym szkicu” tej odpowiedzi wspomniałem, że :( (2) Tak, ale w kontekście pytania pomyślałem, że byłoby to obce wspomnienie.
Steven Evers

Tak, (2) to po prostu użyteczny dodatek (choć niezbędny do stylu kontynuacji), odpowiedzi nie trzeba wspominać.

1

Będziesz chciał spojrzeć na Garbage Collection jest szybki, ale stos jest szybszy , artykuł o używaniu tego, co programiści C pomyśleliby za „stosie” ramek stosu w skompilowanym C. Wierzę, że autor majstrował przy Gcc, aby to zrobić . To nie jest jednoznaczna odpowiedź, ale może pomóc ci zrozumieć niektóre problemy z rekurencją.

Język programowania Alef , który pojawiał się wraz z Planem 9 z Bell Labs, miał instrukcję „stać” (patrz sekcja 6.6.4 tego dokumentu ). Jest to rodzaj wyraźnej optymalizacji rekurencji wywołania ogona. „Ale zużywa stos wywołań!” argument przeciwko rekurencji mógłby potencjalnie zostać zniesiony.


0

TL; DR: Tak, wykonują
Rekurencja jest kluczowym narzędziem w programowaniu funkcjonalnym, dlatego wiele pracy włożono w optymalizację tych wywołań. Na przykład R5RS wymaga (w specyfikacji!), Aby wszystkie implementacje obsługiwały niezwiązane wywołania rekurencji ogona, bez programisty martwiącego się o przepełnienie stosu. Dla porównania domyślnie kompilator C nie wykona nawet oczywistej optymalizacji wywołania ogonowego (spróbuj rekurencyjnego odwrotności połączonej listy), a po niektórych wywołaniach program się zakończy (kompilator zoptymalizuje jednak, jeśli użyjesz - O2).

Oczywiście w okropnie napisanych programach, takich jak słynny fibprzykład, który ma charakter wykładniczy, kompilator nie ma prawie żadnych opcji wykonania swojej „magii”. Należy więc uważać, aby nie utrudniać kompilacji w zakresie optymalizacji.

EDYCJA: Przez przykład fib mam na myśli następujące:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)

0

Języki funkcjonalne są lepsze w dwóch bardzo specyficznych rodzajach rekurencji: rekurencji ogona i rekurencji nieskończonej. Są tak samo złe, jak inne języki podczas innych rodzajów rekurencji, takich jak twój factorialprzykład.

Nie oznacza to, że nie ma algorytmów, które działałyby dobrze z regularną rekurencją w obu paradygmatach. Na przykład wszystko, co i tak wymaga struktury danych podobnej do stosu, jak przeszukiwanie drzewa z głębokością pierwszą, jest najłatwiejsze do wdrożenia z rekurencją.

Rekurencja pojawia się częściej w programowaniu funkcjonalnym, ale jest również zbyt często wykorzystywana, szczególnie przez początkujących lub w samouczkach dla początkujących, być może dlatego, że większość początkujących programistów funkcjonalnych używała rekurencji wcześniej w programowaniu imperatywnym. Istnieją inne funkcjonalne konstrukcje programowania, takie jak interpretacje list, funkcje wyższego rzędu i inne operacje na kolekcjach, które zwykle są znacznie lepiej dostosowane koncepcyjnie, pod względem stylu, zwięzłości, wydajności i zdolności do optymalizacji.

Na przykład sugestia Delnana factorial n = product [1..n]jest nie tylko bardziej zwięzła i łatwiejsza do odczytania, ale jest również wysoce równoległa. To samo dotyczy używania a foldlub reducejeśli twój język nie ma productjuż wbudowanego. Rekurencja jest rozwiązaniem ostatecznym dla tego problemu. Głównym powodem, dla którego widzisz, że jest rozwiązany rekurencyjnie w samouczkach, jest odskocznia przed osiągnięciem lepszych rozwiązań, a nie przykład najlepszej praktyki.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.