Pourquoi les fonctions dans Ocaml / F # ne sont-elles pas récursives par défaut?

Question

Pourquoi les fonctions en F # et Ocaml (et éventuellement d’autres langues) ne sont-elles pas récursives par défaut?

En d'autres termes, pourquoi les concepteurs de langage ont-ils décidé que c'était une bonne idée de vous obliger explicitement à taper rec dans une déclaration telle que:

 let rec foo ... = ...
 

et ne pas donner la fonction récursive par défaut? Pourquoi le besoin d'une construction explicite rec ?

Answer 1

Les français et les Britanniques descendants de l'original ML fait des choix différents et que leurs choix ont été hérités par les décennies à les variantes modernes. Donc, c'est juste de l'héritage, mais elle n'affecte pas les expressions idiomatiques dans ces langues.

Les fonctions ne sont pas récursives par défaut dans le français CAML famille de langues (y compris OCaml). Ce choix fait, il est facile de remplacer la fonction (et variable) à l'aide de définitions let dans ces deux langues, parce que vous pouvez vous référer à la définition précédente à l'intérieur du corps d'une nouvelle définition. F# hérité de cette syntaxe d'OCaml.

Par exemple, en remplaçant la fonction p lors du calcul de l'entropie de Shannon d'une séquence en OCaml:

let shannon fold p =
  let p x = p x *. log(p x) /. log 2.0 in
  let p t x = t +. p x in
  -. fold p 0.0

Notez comment l'argument p à la commande shannon fonction est remplacée par une autre p dans la première ligne du corps, puis un autre p dans la deuxième ligne du corps.

A l'inverse, les Britanniques SML direction générale de la ML de la famille des langues fait un autre choix et SML de l' fun-les fonctions liées sont récursives par défaut. Quand la plupart des définitions de fonction n'ont pas besoin d'accéder à de précédentes liaisons de son nom de fonction, il en résulte la plus simple de code. Cependant, remplacé fonctions sont faits pour utiliser des noms différents (f1, f2 etc.) qui pollue le champ d'application et il est possible de faire appel par erreur à la mauvaise "version" d'une fonction. Et il y a maintenant une différence entre implicitement-récursive fun-tenu des fonctions et de la non-récursive val-les fonctions liées.

Haskell permet d'en déduire les dépendances entre les définitions en les restreignant à être pur. Cela rend le jouet des échantillons look plus simple, mais à un coût exorbitant ailleurs.

Notez que les réponses données par Ganesh et Eddie sont harengs rouges. Ils ont expliqué pourquoi les groupes de fonctions ne peut pas être placé à l'intérieur d'un géant de l' let rec ... and ... , car il affecte lorsque les variables de type get généralisée. Cela n'a rien à voir avec rec étant par défaut en SML mais pas OCaml.

Answer 2

Une raison cruciale pour l'utilisation explicite de rec est de le faire avec Hindley-Milner, l'inférence de type, ce qui sous-tend tous les staticly tapé langages de programmation fonctionnelle (quoique modifié et étendu à diverses façons).

Si vous avez une définition let f x = x, vous vous attendez à avoir le type 'a -> 'a et pour être applicable sur différents 'a types de points différents. Mais aussi, si vous écrivez let g x = (x + 1) + ..., vous attendez x à être traité comme un int dans le reste du corps de l' g.

Le chemin que Hindley-Milner inférence traite avec cette distinction est par le biais d'un explicite généralisation de l'étape. À certains points lors du traitement de votre programme, le type de système s'arrête et dit "ok, les types de ces définitions seront généralisés à ce point, de sorte que lorsque quelqu'un les utilise, gratuit et le type de variables dans leur type sera fraîchement instancié, et donc de ne pas interférer avec les autres utilisations de cette définition."

Il s'avère que l'endroit judicieux de faire cette généralisation est après vérification mutuellement récursives ensemble de fonctions. À une date antérieure, et vous aurez généraliser trop, conduit à des situations où des types fait entrer en collision. Un peu plus tard, et vous aurez généraliser trop peu, en faisant des définitions qui ne peut pas être utilisé avec plusieurs type d'instanciations.

Donc, étant donné que le type de vérificateur doit savoir au sujet de laquelle les ensembles de définitions sont mutuellement récursives, que peut-il faire? Une possibilité est de simplement faire une analyse de dépendance sur toutes les définitions de la portée, et les réorganiser dans le plus petit possible pour les groupes. Haskell en fait cela, mais dans des langues telles que F# (et OCaml et SML), qui ont sans restriction d'effets secondaires, c'est une mauvaise idée, car il pourrait réorganiser les effets secondaires trop. Donc, au lieu de cela, il demande à l'utilisateur de marquer explicitement dont les définitions sont mutuellement récursives, et donc, par extension, d'où la généralisation devrait se produire.

Answer 3

Il y a deux principales raisons à cela est une bonne idée:

Tout d'abord, si vous activez les définitions récursives, alors vous ne pouvez pas se référer à un précédent contraignant d'une valeur du même nom. C'est souvent utile idiome quand vous faites quelque chose comme l'extension d'un module existant.

Deuxièmement, récursive des valeurs, et notamment des ensembles de mutuellement récursives valeurs, il est beaucoup plus difficile de raisonner sur les définitions que procéder dans l'ordre, chaque nouvelle définition de la construction sur le dessus de ce qui a déjà été défini. Il est agréable lors de la lecture d'un tel code pour avoir la garantie que, sauf pour les définitions explicitement marqué comme récursive, de nouvelles définitions ne peut que se référer à des définitions précédentes.

Answer 4

Quelques suppositions:

• let n'est pas seulement utilisé pour lier des fonctions, mais aussi pour les autres valeurs. La plupart des formes de valeurs ne sont pas autorisés à être récursive. Certaines formes de récursive valeurs sont autorisées (par exemple, les fonctions, les paresseux, les expressions, etc.), il a donc besoin d'une syntaxe explicite pour indiquer cela.
• Il pourrait être plus facile d'optimiser les non-fonctions récursives
• La fermeture créé lorsque vous créez une fonction récursive doit inclure une entrée qui pointe vers la fonction elle-même (donc la fonction de manière récursive peut s'appeler lui-même), ce qui rend récursive des fermetures plus compliqué que les non-récursive de fermetures. De sorte qu'il pourrait être agréable d'être en mesure de créer de plus simple, les non-récursive fermetures lorsque vous n'avez pas besoin de récursivité
• Il vous permet de définir une fonction dans les conditions précédemment définies par la fonction ou la valeur du même nom, bien que je pense que c'est une mauvaise pratique
• Plus de sécurité? Permet de s'assurer que vous faites ce que vous avez prévu. par exemple, Si vous n'avez pas l'intention d'être récursive, mais vous avez accidentellement utilisé un nom à l'intérieur de la fonction avec le même nom que la fonction elle-même, il sera plus susceptible de se plaindre (à moins que le nom a été définie avant)
• L' let construction est similaire à l' let construire en Lisp et Scheme, qui sont non-récursive. Il est séparé letrec construire dans le Schéma récursif nous allons

Answer 5

Compte tenu de ceci:

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

Comparer:

let f a = f (g a)

Avec ceci:

let rec f a = f (g a)

L'ancien redéfinit f d'appliquer l'défini précédemment f pour le résultat de l'application d' g de a. Le dernier redéfinit f boucle pour toujours appliquant g de a, ce qui n'est généralement pas ce que vous voulez dans la ML variantes.

Cela dit, c'est un langage de style de concepteur de chose. Juste aller avec elle.