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

104

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?

nsantorello
źródło

Odpowiedzi:

87

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.

JD
źródło
3
Nie sądzę, że są to czerwone śledzie: gdyby nie ograniczenia dotyczące wnioskowania, prawdopodobnie całe programy lub moduły byłyby automatycznie traktowane jako wzajemnie rekurencyjne, tak jak robi to większość innych języków. To spowodowałoby, że konkretna decyzja projektowa dotycząca tego, czy „rec” powinna być wymagana, jest dyskusyjna.
GS - Przeproś Monikę
„... automatycznie traktowane jako wzajemnie rekurencyjne, tak jak robi to większość innych języków”. BASIC, C, C ++, Clojure, Erlang, F #, Factor, Forth, Fortran, Groovy, OCaml, Pascal, Smalltalk i Standard ML nie.
JD
3
C / C ++ wymaga tylko prototypów dla definicji forward, co tak naprawdę nie polega na jawnym oznaczaniu rekursji. Java, C # i Perl z pewnością mają niejawną rekursję. Moglibyśmy wdać się w niekończącą się debatę na temat znaczenia „większości” i znaczenia każdego języka, więc po prostu zadowalajmy się „bardzo wieloma” innymi językami.
GS - Przeproś Monikę
3
„C / C ++ wymaga tylko prototypów dla definicji forward, co tak naprawdę nie polega na jawnym oznaczaniu rekursji”. Tylko w szczególnym przypadku rekursji własnej. W ogólnym przypadku wzajemnej rekursji deklaracje forward są obowiązkowe zarówno w C, jak i C ++.
JD
2
W rzeczywistości deklaracje przekazywania nie są wymagane w C ++ w zakresach klas, tj. Metody statyczne mogą wywoływać się nawzajem bez żadnych deklaracji.
polkovnikov.ph
52

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.

GS - Przeproś Monikę
źródło
3
Eee, nie. Twój pierwszy akapit jest błędny (mówisz o jawnym użyciu „i”, a nie „rec”), a zatem reszta jest nieistotna.
JD
5
Nigdy nie byłem zadowolony z tego wymogu. Dziękuję za wyjaśnienie. Kolejny powód, dla którego Haskell jest lepszy w projektowaniu.
Bent Rasmussen
9
NIE!!!! JAK TO MOGŁO SIĘ STAĆ?! Ta odpowiedź jest po prostu błędna! Przeczytaj odpowiedź Harrop poniżej lub sprawdź Definicję standardowego ML (Milner, Tofte, Harper, MacQueen - 1997) [str. 24]
lambdapower
9
Jak powiedziałem w swojej odpowiedzi, kwestia wnioskowania typu jest jednym z powodów potrzeby rec, a nie jedynym powodem. Odpowiedź Jona jest również bardzo trafną odpowiedzią (poza zwykłym szyderczym komentarzem na temat Haskella); Nie sądzę, żeby ci dwaj byli w opozycji.
GS - Przeproś Monikę
16
„problem wnioskowania o typie jest jednym z powodów potrzeby rec”. Fakt, że OCaml wymaga, reca SML nie wymaga, jest oczywistym kontrprzykładem. Gdyby wnioskowanie o typie było problemem z powodów, które opisujesz, OCaml i SML nie mogłyby wybrać innych rozwiązań, jak to zrobili. Powodem jest oczywiście to, że mówisz o tym and, aby Haskell był trafny.
JD
10

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.

zrr
źródło
4

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
newacct
źródło
„Większość form wartości nie może być rekurencyjna. Niektóre formy wartości rekurencyjnych są dozwolone (np. Funkcje, leniwe wyrażenia itp.), Więc aby to wskazać, potrzebna jest wyraźna składnia”. Tak jest w przypadku F #, ale nie jestem pewien, jak prawdziwe jest to w przypadku OCaml, gdzie możesz to zrobić let rec xs = 0::ys and ys = 1::xs.
JD
4

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.

James Woodyatt
źródło
1

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

Evan Meagher
źródło