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 rec
deklaracji takiej jak:
let rec foo ... = ...
i nie daje funkcji domyślnie możliwości rekurencji? Skąd potrzeba jawnej rec
konstrukcji?
Odpowiedzi:
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
let
w 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ę
p
podczas obliczania entropii Shannona sekwencji w OCaml:Zwróć uwagę, jak argument
p
funkcji wyższego rzędushannon
jest zastępowany innym argumentemp
w pierwszej linii treści, a następnie innym argumentemp
w drugiej linii treści.I odwrotnie, brytyjska gałąź języków SML z rodziny ML wybrała inny wybór, a
fun
funkcje 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
,f2
itd.), Które zanieczyszcza zakresu i umożliwia przypadkowo invoke złym „wersja” funkcji. Istnieje teraz rozbieżność między niejawnie rekurencyjnymifun
funkcjami powiązanymi aval
nierekurencyjnymi 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 zrec
byciem domyślnym w SML, ale nie z OCaml.źródło
Jednym z kluczowych powodów, dla których jawne jest użycie,
rec
ma 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 -> 'a
i będzie miała zastosowanie do różnych'a
typów w różnych punktach. Ale równie dobrze, jeśli napiszeszlet g x = (x + 1) + ...
, spodziewasz się, żex
będziesz traktowany jakint
w pozostałej części treścig
.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.
źródło
rec
a 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 tymand
, aby Haskell był trafny.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.
źródło
Kilka domysłów:
let
sł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.let
Konstrukcja jest podobna dolet
konstrukcji w Lispie i systemu; które są nierekurencyjne. Wletrec
Scheme istnieje oddzielna konstrukcja dla rekurencyjnych let'sźródło
let rec xs = 0::ys and ys = 1::xs
.Biorąc to pod uwagę:
Porównać:
Z tym:
Dawne redefiniuje
f
zastosować uprzednio zdefiniowanef
w wyniku nakładaniag
sięa
. Te ostatnie definiuje na nowof
do pętli zawsze stosującg
sięa
, co zazwyczaj nie jest to, co chcesz w wariantach ML.To powiedziawszy, to rzecz w stylu projektanta języka. Olej to.
źródło
W dużej mierze daje to programiście większą kontrolę nad złożonością ich lokalnych zakresów. Spektrum
let
,let*
alet rec
oferta coraz większy poziom zarówno mocy i kosztów.let*
ilet rec
są w istocie zagnieżdżonymi wersjami prostotylet
, 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?
iequal?
)źródło