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

Jednym z kluczowych powodów dla jawnego użycia rec jest wnioskowanie typu Hindley-Milner, które leży u podstaw wszystkich statycznie wpisywanych języków programowania funkcyjnego (choć zmienianych i rozszerzanych na różne sposoby).

Jeśli masz definicję let f x = x, spodziewasz się, że będzie ona miała typ 'a -> 'a i będzie miała zastosowanie do różnych typów 'a w różnych punktach. Ale równie dobrze, jeśli napiszesz let g x = (x + 1) + ..., spodziewasz się, że x będzie traktowana jako int w pozostałej części ciała g.

Sposób, w jaki Wnioskowanie hindleya-Milnera dotyczy tego rozróżnienia poprzez jawne uogólnienie . W pewnych momentach podczas przetwarzania programu, System typów zatrzymuje się i mówi: "ok, typy tych definicji zostaną uogólnione w tym momencie, tak że gdy ktoś ich użyje, dowolne zmienne typu w ich typie zostaną świeżo utworzone, a tym samym nie będą kolidować z żadnymi innymi zastosowaniami tej definicji."

Okazuje się, że sensowne miejsce na to uogólnienie polega na sprawdzeniu wzajemnie rekurencyjnego zbioru funkcji. Trochę wcześniej, a zbyt wiele uogólniasz, co prowadzi do sytuacji, w których typy mogą się zderzyć. Później zbyt mało uogólniasz, tworząc definicje, których nie można używać w przypadku wielu instancji typu.

Więc, biorąc pod uwagę, że kontroler typu musi wiedzieć, które zbiory definicji są wzajemnie rekurencyjne, co może zrobić? Jedną z możliwości jest po prostu przeprowadzenie analizy zależności od wszystkich definicji w zakresie, i uporządkować je na najmniejsze możliwe grupy. Haskell faktycznie to robi, ale w językach takich jak F# (i OCaml i SML), które mają nieograniczone skutki uboczne, jest to zły pomysł, ponieważ może zmienić kolejność skutków ubocznych zbyt. Zamiast tego prosi użytkownika o jednoznaczne zaznaczenie, które definicje są wzajemnie rekurencyjne, a więc przez rozszerzenie, gdzie powinno nastąpić uogólnienie.

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

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

Po drugie, wartości rekurencyjne, a zwłaszcza zbiory wzajemnie rekurencyjnych wartości, są znacznie trudniejsze do rozumowania o to są definicje, które postępują w kolejności, każda nowa definicja opiera się na tym, co już zostało zdefiniowany. Dobrze jest, gdy czyta się taki kod, mieć gwarancję, że z wyjątkiem definicji wyraźnie oznaczonych jako rekurencyjne, nowe definicje mogą odnosić się tylko do poprzednich definicji.

Kilka domysłów:

• let jest używany nie tylko do wiązania funkcji, ale także innych regularnych wartości. Większość form wartości nie może być rekurencyjna. Dopuszczalne są pewne formy wartości rekurencyjnych (np. funkcje, wyrażenia leniwe itp.), więc do wskazania tego potrzebna jest jednoznaczna składnia.
• może być łatwiej zoptymalizować funkcje nie rekurencyjne
• zamknięcie utworzone podczas tworzenia funkcji rekurencyjnej musi zawierać wpis, który wskazuje na samą funkcję (więc funkcja może wywoływać się rekurencyjnie), co sprawia, że zamknięcia rekurencyjne są bardziej skomplikowane niż zamknięcia nie rekurencyjne. Więc może być miło, aby móc tworzyć prostsze nie rekurencyjne zamknięcia, gdy nie potrzebujesz rekurencji
• pozwala zdefiniować funkcję pod względem wcześniej zdefiniowanej funkcji lub wartości o tej samej nazwie; chociaż myślę, że jest to zła praktyka
Dodatkowe bezpieczeństwo? Upewnia się, że robisz to, co zamierzałeś. np. jeśli nie masz zamiaru być rekurencyjny, ale przypadkowo użyłeś nazwy wewnątrz funkcji o tej samej nazwie co sama funkcja, najprawdopodobniej będzie ona narzekać (chyba że nazwa została zdefiniowana wcześniej)
• let construct jest podobny do let construct w Lispie i Scheme; które nie są rekurencyjne. Istnieje oddzielna letrec KONSTRUKCJA w schemacie dla rekurencyjnego let ' s

Biorąc pod uwagę to:

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

Porównaj:

let f a = f (g a)

Z tym:

let rec f a = f (g a)

Poprzedni redefiniuje f, Aby zastosować wcześniej zdefiniowane f do wyniku zastosowania g do a. Ten ostatni redefiniuje f do pętli forever stosując g do a, co zwykle nie jest tym, czego chcesz w wariantach ML.

To powiedziawszy, to styl projektanta języka. Po prostu to zrób.

Duża część tego polega na tym, że daje programistom większą kontrolę nad złożonością ich lokalnych zakresów. Spektrum let, let* i let rec oferują coraz większy poziom zarówno mocy, jak i kosztów. let* i {[2] } są w istocie zagnieżdżonymi wersjami prostych let, więc używanie obu z nich jest droższe. Ta klasyfikacja pozwala na mikrozarządzanie optymalizacją programu, ponieważ możesz wybrać poziom let, którego potrzebujesz do danego zadania. Jeśli nie potrzebujesz rekurencji lub możliwości zapoznaj się z poprzednimi wiązaniami, a następnie możesz wrócić do prostego letu, aby zaoszczędzić trochę wydajności.

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