Dlaczego słowo kluczowe rec jest potrzebne w F #?

28

W języku F # konieczne jest użycie recsłowa kluczowego. W Haskell nie ma potrzeby jawnego określania, czy dana funkcja jest rekurencyjna, czy nie.

Biorąc pod uwagę rolę rekurencji w programowaniu funkcjonalnym, projekt F # wydaje mi się dość dziwny. Czy jest to dobra decyzja dotycząca projektu języka, czy istnieje tylko z powodów historycznych lub z powodu ograniczenia implementacyjnego?

Simon Bergot
źródło

Odpowiedzi:

16

Istnieje nieodłączna różnica w semantyce Haskella i F #. W Haskell wywołanie funkcji nie wykonuje żadnych rzeczywistych obliczeń, ale przydziela obiekt sterty zwany „gromadą”. Jest całkowicie w porządku, aby thunk miał link do siebie lub innej thunk. Jednak w języku F # wywołanie funkcji jest faktycznym wywołaniem, które powoduje, że wyrażenia są let x = 1 : 2 : x in xniepoprawne - ponieważ wymaga xto zbudowania przed 1 : 2 : xzbudowaniem. Jednak wciąż jest to mniej lub bardziej rozsądna definicja nieskończonej listy, jakiś sposób jej zdefiniowania powinien istnieć. Tu leżą korzenie rec. Jeśli chcesz więcej, wyszukaj i przeczytaj semantykę operacyjną dla SML i Haskell - jest inaczej.

permeakra
źródło
2
AFAIK, Haskell celowo nie ma semantyki operacyjnej.
dan_waterworth
@dan_waterworth kompilacja nie jest możliwa bez zdefiniowanej semantyki operacyjnej.
permeakra
8
Język Haskell nie definiuje semantyki operacyjnej, ale zamiast tego zapewnia semantykę denotacyjną. Podczas konstruowania kompilatora semantyka operacyjna jest domyślnie zdefiniowana, ale nie oznacza to, że jest ona częścią standardu językowego Haskell.
dan_waterworth
6
@dan_waterworth W praktyce istnieje tylko jedna implementacja i standard języka Haskell: ghc, a także tylko jeden standard F #: implementacja Microsoft. Więc teoretycznie możesz mieć rację, ale praktyka to zupełnie inna bestia.
permeakra
19

Odpowiedź na to pytanie została udzielona na SO i zawiera pewne silne historyczne podłoże, dla którego używane jest „rec”.

Oto ważny cytat dla potomności:

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) przy użyciu let w tych językach, ponieważ można odwoływać się do poprzedniej definicji w treści nowej definicji. F # odziedziczył tę składnię po OCaml.

Chris Pitman
źródło
12

Rekurencja letdefiniuje znacznie bardziej skomplikowaną semantykę niż normalna. Dlatego, ze względu na prostotę i przejrzysty wygląd języka, istnieje dobry powód, aby mieć oba, tak samo jak oddzielne let, let*i letrecna schemacie.

Prosty let x = y in zjest równoważny ((fun x -> z) y). Rekurencyjne let jest znacznie bardziej skomplikowane i może wymagać użycia kombinatora punktów stałych.

Logika SK
źródło