Czy języki funkcjonalne są lepsze w rekurencji?

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.

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.

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.

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.

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.

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)

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.

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)))
 )
)

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.