Pourquoi le mot-clé rec est-il nécessaire en F #?

28

En F # il faut utiliser le recmot - clé. Dans Haskell, il n'est pas nécessaire de dire explicitement si une fonction donnée est récursive ou non.

Étant donné le rôle de la récursivité dans la programmation fonctionnelle, la conception F # me semble plutôt étrange. Est-ce une bonne décision de conception de langage ou existe-t-il uniquement pour des raisons historiques ou en raison d'une contrainte de mise en œuvre?

Simon Bergot
la source

Réponses:

16

Il existe une différence inhérente à la sémantique Haskell et F #. Dans Haskell, un appel de fonction n'effectue aucun calcul réel, mais alloue un objet tas appelé «thunk». Il est parfaitement normal qu'un thunk ait un lien avec lui-même ou un autre thunk. Cependant, en F #, un appel de fonction est un appel réel, rendant les expressions comme let x = 1 : 2 : x in xinvalides - car il doit xêtre construit avant d' 1 : 2 : xêtre construit. Cependant, il s'agit toujours d'une définition plus ou moins raisonnable pour une liste infinie, un moyen de la définir devrait exister. Ici se trouve les racines de rec. Si vous en voulez plus, recherchez et lisez la sémantique opérationnelle pour SML et Haskell - c'est différent.

permeakra
la source
2
AFAIK, Haskell n'a délibérément pas de sémantique opérationnelle.
dan_waterworth
@dan_waterworth il est impossible de compiler sans sémantique opérationnelle définie.
permeakra
8
Le langage Haskell ne définit pas une sémantique opérationnelle, mais fournit plutôt une sémantique dénotationnelle. Lorsque vous construisez un compilateur, une sémantique opérationnelle est implicitement définie, mais cela ne signifie pas qu'elle fait partie de la norme de langage Haskell.
dan_waterworth
6
@dan_waterworth Dans la pratique, il n'y a qu'une seule implémentation et norme du langage Haskell: ghc, ainsi qu'une seule norme F #: l'implémentation de Microsoft. Donc, théoriquement, vous avez peut-être raison, mais la pratique est une bête entièrement différente.
permeakra
19

Cette question a été répondue sur SO , et elle comprend un certain historique fort pour expliquer pourquoi "rec" est utilisé.

Voici la citation importante pour la postérité:

Les fonctions ne sont pas récursives par défaut dans la famille de langues CAML française (dont OCaml). Ce choix permet de remplacer facilement les définitions de fonction (et de variable) en utilisant let dans ces langages car vous pouvez vous référer à la définition précédente dans le corps d'une nouvelle définition. F # a hérité de cette syntaxe d'OCaml.

Chris Pitman
la source
12

Une récursive letdéfinit une sémantique beaucoup plus compliquée qu'une sémantique normale. Par conséquent, dans un souci de simplicité et de conception de langage clair, il y a une bonne raison d'avoir les deux, tout comme avoir séparé let, let*et letrecdans Scheme.

Simple let x = y in zest équivalent à ((fun x -> z) y). Un let récursif est beaucoup plus compliqué et peut impliquer l'utilisation d'un combinateur à point fixe.

SK-logic
la source