Por que a palavra-chave rec é necessária em F #?

28

No F # é necessário usar a recpalavra - chave. Em Haskell, não há necessidade de dizer explicitamente se uma determinada função é recursiva ou não.

Dado o papel da recursão na programação funcional, o design do F # parece bastante estranho para mim. É uma boa decisão de design de linguagem ou existe apenas por motivos históricos ou devido a uma restrição de implementação?

Simon Bergot
fonte

Respostas:

16

Há uma diferença inerente na semântica de Haskell e F #. No Haskell, uma chamada de função não realiza nenhum cálculo real, mas aloca um objeto de heap conhecido como 'thunk'. Não há problema em um thunk ter um link para si ou para outro thunk. No entanto, em F #, uma chamada de função é uma chamada real, tornando expressões como let x = 1 : 2 : x in xinválidas - pois requer xque seja construída antes de 1 : 2 : xser construída. No entanto, ainda é uma definição mais ou menos razoável para uma lista infinita, alguma maneira de defini-la deve existir. Aqui estão as raízes rec. Se você quiser mais, pesquise e leia a semântica operacional para SML e Haskell - é diferente.

permeakra
fonte
2
AFAIK, Haskell intencionalmente não possui uma semântica operacional.
dan_waterworth
@dan_waterworth é impossível compilar sem semântica operacional definida.
Permeakra #
8
A linguagem Haskell não define uma semântica operacional, mas fornece uma semântica denotacional. Quando você constrói um compilador, uma semântica operacional é definida implicitamente, mas isso não significa que faça parte do padrão da linguagem Haskell.
dan_waterworth
6
@dan_waterworth Na prática, existe apenas uma implementação e padrão da linguagem Haskell: ghc, assim como existe apenas um padrão F #: a implementação da Microsoft. Então, teoricamente, você pode estar certo, mas a prática é uma fera totalmente diferente.
Permeakra
19

Esta pergunta foi respondida no SO e inclui alguns antecedentes históricos fortes sobre o motivo pelo qual "rec" é usado.

Aqui está a citação importante para a posteridade:

As funções não são recursivas por padrão na família de idiomas CAML em francês (incluindo OCaml). Essa opção facilita a substituição de definições de funções (e variáveis) usando let nesses idiomas, porque você pode consultar a definição anterior dentro do corpo de uma nova definição. F # herdou esta sintaxe do OCaml.

Chris Pitman
fonte
12

Uma recursiva letdefine uma semântica significativamente mais complicada do que a normal. Portanto, por uma questão de simplicidade e design de linguagem limpa, há um bom motivo para ter os dois, da mesma forma que ter separado let, let*e letrecno Scheme.

Simples let x = y in zé equivalente a ((fun x -> z) y). Um let recursivo é muito mais complicado e pode envolver o uso de um combinador de ponto fixo.

SK-logic
fonte