Dlaczego funkcje w Ocaml / F # nie są domyślnie cykliczne?

Dlaczego jest tak, że funkcje w F # i Ocaml (i prawdopodobnie w innych językach) nie są domyślnie rekurencyjne?

Innymi słowy, dlaczego projektanci języka zdecydowali, że dobrym pomysłem jest jawne nakazanie wpisania recdeklaracji takiej jak:

let rec foo ... = ...

i nie daje funkcji domyślnie możliwości rekurencji? Skąd potrzeba jawnej reckonstrukcji?

Francuscy i brytyjscy potomkowie oryginalnego ML dokonali różnych wyborów, a ich wybory zostały odziedziczone przez dziesięciolecia do nowoczesnych wariantów. Więc to tylko dziedzictwo, ale ma wpływ na idiomy w tych językach.

Funkcje nie są domyślnie rekurencyjne we francuskiej rodzinie języków CAML (w tym OCaml). Ten wybór ułatwia zastąpienie definicji funkcji (i zmiennych) używanych letw tych językach, ponieważ można odwołać się do poprzedniej definicji w treści nowej definicji. F # odziedziczył tę składnię z OCaml.

Na przykład, zastępując funkcję ppodczas obliczania entropii Shannona sekwencji w OCaml:

let shannon fold p =
  let p x = p x *. log(p x) /. log 2.0 in
  let p t x = t +. p x in
  -. fold p 0.0

Zwróć uwagę, jak argument pfunkcji wyższego rzędu shannonjest zastępowany innym argumentem pw pierwszej linii treści, a następnie innym argumentem pw drugiej linii treści.

I odwrotnie, brytyjska gałąź języków SML z rodziny ML wybrała inny wybór, a funfunkcje powiązane z SML są domyślnie rekurencyjne. Gdy większość definicji funkcji nie potrzebuje dostępu do poprzednich powiązań ich nazwy funkcji, skutkuje to prostszym kodem. Jednak zastąpiona funkcje wykonywane są w użyciu różnych nazw ( f1, f2itd.), Które zanieczyszcza zakresu i umożliwia przypadkowo invoke złym „wersja” funkcji. Istnieje teraz rozbieżność między niejawnie rekurencyjnymi funfunkcjami powiązanymi a valnierekurencyjnymi funkcjami powiązanymi.

Haskell umożliwia wnioskowanie o zależnościach między definicjami poprzez ograniczenie ich do czystości. To sprawia, że ​​próbki zabawek wyglądają na prostsze, ale gdzie indziej wiąże się to z poważnymi kosztami.

Zwróć uwagę, że odpowiedzi udzielone przez Ganesh i Eddie to czerwone śledzie. Wyjaśnili, dlaczego grup funkcji nie można umieścić wewnątrz olbrzyma, let rec ... and ...ponieważ wpływa to na uogólnienie zmiennych typu. Nie ma to nic wspólnego z recbyciem domyślnym w SML, ale nie z OCaml.

Jednym z kluczowych powodów, dla których jawne jest użycie, recma związek z wnioskiem typu Hindleya-Milnera, który leży u podstaw wszystkich funkcjonalnych języków programowania ze statycznym typowaniem (aczkolwiek zmienionych i rozszerzonych na różne sposoby).

Jeśli masz definicję let f x = x, spodziewasz się, że będzie miała typ 'a -> 'ai będzie miała zastosowanie do różnych 'atypów w różnych punktach. Ale równie dobrze, jeśli napiszesz let g x = (x + 1) + ..., spodziewasz się, że xbędziesz traktowany jak intw pozostałej części treści g.

Sposób, w jaki wnioskowanie Hindleya-Milnera radzi sobie z tym rozróżnieniem, prowadzi przez wyraźny krok uogólnienia . W pewnych momentach podczas przetwarzania twojego programu, system typów zatrzymuje się i mówi "ok, typy tych definicji zostaną uogólnione w tym miejscu, tak że gdy ktoś ich użyje, wszelkie wolne zmienne typu w ich typie będą świeżo utworzone, a zatem nie będzie kolidować z innymi zastosowaniami tej definicji. ”

Okazuje się, że sensownym miejscem do zrobienia tego uogólnienia jest sprawdzenie wzajemnie rekurencyjnego zestawu funkcji. Jakikolwiek wcześniejszy, a będziesz uogólniać zbyt wiele, co prowadzi do sytuacji, w których typy mogą faktycznie kolidować. Później za mało uogólniasz, tworząc definicje, których nie można używać z wystąpieniami wielu typów.

A zatem, biorąc pod uwagę, że narzędzie do sprawdzania typów musi wiedzieć, które zestawy definicji są wzajemnie rekurencyjne, co może zrobić? Jedną z możliwości jest po prostu przeprowadzenie analizy zależności na wszystkich definicjach w zakresie i uporządkowanie ich w jak najmniejszych grupach. Haskell faktycznie to robi, ale w językach takich jak F # (oraz OCaml i SML), które mają nieograniczone skutki uboczne, jest to zły pomysł, ponieważ może również zmienić kolejność efektów ubocznych. Zamiast tego prosi użytkownika o wyraźne zaznaczenie, które definicje są wzajemnie rekurencyjne, a zatem, przez rozszerzenie, gdzie powinno nastąpić uogólnienie.

Są dwa kluczowe powody, dla których jest to dobry pomysł:

Po pierwsze, jeśli włączysz definicje rekurencyjne, nie możesz odwołać się do poprzedniego powiązania wartości o tej samej nazwie. Jest to często przydatny idiom, gdy robisz coś takiego, jak rozszerzenie istniejącego modułu.

Po drugie, wartości rekurencyjne, a zwłaszcza zbiory wartości wzajemnie rekurencyjnych, są znacznie trudniejsze do rozważenia, w związku z czym definicje przebiegają w kolejności, a każda nowa definicja opiera się na tym, co zostało już zdefiniowane. Podczas czytania takiego kodu dobrze jest mieć gwarancję, że poza definicjami wyraźnie oznaczonymi jako rekurencyjne, nowe definicje mogą odnosić się tylko do poprzednich definicji.

Kilka domysłów:

• letsłuży nie tylko do wiązania funkcji, ale także innych zwykłych wartości. Większość form wartości nie może być rekurencyjna. Dozwolone są pewne formy wartości rekurencyjnych (np. Funkcje, wyrażenia leniwe itp.), Więc do wskazania tego potrzeba wyraźnej składni.
• Może być łatwiej zoptymalizować funkcje nierekurencyjne
• Zamknięcie utworzone podczas tworzenia funkcji rekurencyjnej musi zawierać wpis, który wskazuje na samą funkcję (aby funkcja mogła rekurencyjnie wywołać samą siebie), co sprawia, że ​​zamknięcia rekurencyjne są bardziej skomplikowane niż zamknięcia nierekurencyjne. Więc fajnie byłoby móc tworzyć prostsze nierekurencyjne domknięcia, gdy rekurencja nie jest potrzebna
• Pozwala zdefiniować funkcję w kategoriach wcześniej zdefiniowanej funkcji lub wartości o tej samej nazwie; chociaż myślę, że to zła praktyka
• Dodatkowe bezpieczeństwo? Upewnia się, że robisz to, co zamierzałeś. np. jeśli nie zamierzasz, aby była rekurencyjna, ale przypadkowo użyłeś nazwy wewnątrz funkcji o takiej samej nazwie jak sama funkcja, najprawdopodobniej będzie narzekać (chyba że nazwa została wcześniej zdefiniowana)
• letKonstrukcja jest podobna do letkonstrukcji w Lispie i systemu; które są nierekurencyjne. W letrecScheme istnieje oddzielna konstrukcja dla rekurencyjnych let's

Biorąc to pod uwagę:

let f x = ... and g y = ...;;

Porównać:

let f a = f (g a)

Z tym:

let rec f a = f (g a)

Dawne redefiniuje fzastosować uprzednio zdefiniowane fw wyniku nakładania gsię a. Te ostatnie definiuje na nowo fdo pętli zawsze stosując gsię a, co zazwyczaj nie jest to, co chcesz w wariantach ML.

To powiedziawszy, to rzecz w stylu projektanta języka. Olej to.

W dużej mierze daje to programiście większą kontrolę nad złożonością ich lokalnych zakresów. Spektrum let, let*a let recoferta coraz większy poziom zarówno mocy i kosztów. let*i let recsą w istocie zagnieżdżonymi wersjami prostoty let, więc użycie którejkolwiek z nich jest droższe. Ta ocena pozwala na mikrozarządzanie optymalizacją programu, ponieważ możesz wybrać poziom, którego potrzebujesz do wykonania zadania. Jeśli nie potrzebujesz rekursji lub możliwości odwoływania się do poprzednich powiązań, możesz wrócić do prostego let, aby zaoszczędzić trochę wydajności.

Jest podobny do stopniowanych predykatów równości w schemacie. (tj eq?, eqv?i equal?)