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

Pourquoi est-ce que les fonctions en F # et Ocaml (et éventuellement d’autres langages) ne sont 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 faire taper rec dans une déclaration comme:

 let rec foo ... = ... 

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

Les descendants français et britanniques du ML original ont fait des choix différents et leurs choix ont été hérités au fil des décennies des variantes modernes. Donc, ce n’est qu’un inheritance, mais cela affecte les idiomes dans ces langues.

Les fonctions ne sont pas récursives par défaut dans la famille de langues française CAML (y compris OCaml). Ce choix facilite le remplacement des définitions de fonctions (et de variables) par 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.

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

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

Notez que l’argument p de la fonction shannon ordre supérieur est remplacé par un autre p dans la première ligne du corps, puis un autre p dans la deuxième ligne du corps.

À l’inverse, la twig britannique de SML de la famille de langages ML a pris l’autre choix et les fonctions fun SML sont récursives par défaut. Lorsque la plupart des définitions de fonctions n’ont pas besoin d’accéder aux liaisons précédentes de leur nom de fonction, le code est plus simple. Cependant, les fonctions remplacées sont faites pour utiliser des noms différents ( f1 , f2 etc.) qui polluent la scope et permettent d’invoquer accidentellement la mauvaise “version” d’une fonction. Et il existe maintenant une divergence entre les fonctions fun implicitement récursives et les fonctions non récursives.

Haskell permet de déduire les dépendances entre définitions en les restreignant à la pure. Cela rend les échantillons de jouets plus simples mais coûte très cher ailleurs.

Notez que les réponses données par Ganesh et Eddie sont des herrings rouges. Ils ont expliqué pourquoi les groupes de fonctions ne peuvent pas être placés dans un let rec ... and ... un géant let rec ... and ... parce que cela affecte quand les variables de type sont généralisées. Cela n’a rien à voir avec rec par défaut dans SML mais pas avec OCaml.

Une des raisons essentielles de l’utilisation explicite de rec est liée à l’inférence de type Hindley-Milner, qui sous-tend tous les langages de programmation fonctionnels statiquement typés (bien que modifiés et étendus de diverses manières).

Si vous avez une définition, let fx = x , vous vous attendez à ce qu’elle ait le type 'a -> 'a et à être applicable sur différents types à différents points. Mais de même, si vous écrivez let gx = (x + 1) + ... , vous vous attendez à ce que x soit traité comme un int dans le rest du corps de g .

La manière dont infère Hindley-Milner traite de cette distinction passe par une étape de généralisation explicite. A certains moments du traitement de votre programme, le système de type s’arrête et dit “ok, les types de ces définitions seront généralisés à ce stade, de sorte que lorsque quelqu’un les utilise, toutes les variables de type libres de leur type seront instanciées, et donc n’interfèrera avec aucune autre utilisation de cette définition. ”

Il s’avère que le bon endroit pour faire cette généralisation est de vérifier un ensemble de fonctions mutuellement récursives. Plus tôt, et vous en généraliserez trop, conduisant à des situations où les types pourraient entrer en collision. Plus tard, et vous généraliserez trop peu, en faisant des définitions qui ne peuvent pas être utilisées avec plusieurs instanciations de types.

Donc, étant donné que le vérificateur de type doit savoir quels ensembles de définitions sont mutuellement récursifs, que peut-il faire? Une possibilité est de faire simplement une parsing de dépendance sur toutes les définitions d’une étendue et de les réorganiser en groupes les plus petits possibles. Haskell fait cela, mais dans des langages comme F # (et OCaml et SML) qui ont des effets secondaires illimités, c’est une mauvaise idée car cela pourrait aussi réorganiser les effets secondaires. Donc, à la place, il demande à l’utilisateur de marquer explicitement les définitions qui sont mutuellement récursives, et donc par extension où la généralisation doit avoir lieu.

Il y a deux raisons principales pour lesquelles c’est une bonne idée:

Tout d’abord, si vous activez les définitions récursives, vous ne pouvez pas vous référer à une liaison précédente d’une valeur du même nom. Ceci est souvent un idiome utile lorsque vous faites quelque chose comme l’extension d’un module existant.

Deuxièmement, les valeurs récursives, et en particulier les ensembles de valeurs mutuellement récursives, sont beaucoup plus difficiles à raisonner que les définitions qui suivent, chaque nouvelle définition s’appuyant sur ce qui a déjà été défini. Lors de la lecture d’un tel code, il est intéressant d’avoir la garantie que, à l’exception des définitions explicitement marquées comme récursives, les nouvelles définitions ne peuvent se référer qu’aux définitions précédentes.

Quelques suppositions:

  • let n’est pas seulement utilisé pour lier des fonctions, mais aussi d’autres valeurs régulières. La plupart des formes de valeurs ne peuvent être récursives. Certaines formes de valeurs récursives sont autorisées (par exemple, fonctions, expressions paresseuses, etc.), il faut donc une syntaxe explicite pour l’indiquer.
  • Il pourrait être plus facile d’optimiser les fonctions non récursives
  • La fermeture créée lors de la création d’une fonction récursive doit inclure une entrée qui pointe vers la fonction elle-même (la fonction peut donc s’appeler de manière récursive), ce qui rend les fermetures récursives plus compliquées que les fermetures non récursives. Il peut donc être intéressant de pouvoir créer des fermetures non récursives plus simples lorsque vous n’avez pas besoin de récursivité
  • Il vous permet de définir une fonction en fonction d’une fonction ou d’une valeur préalablement définie du même nom. bien que je pense que c’est une mauvaise pratique
  • Sécurité supplémentaire? Assurez-vous que vous faites ce que vous vouliez. Par exemple, si vous ne souhaitez pas que ce soit récursif mais que vous ayez accidentellement utilisé un nom dans la fonction avec le même nom que la fonction elle-même, elle se plaindra probablement (sauf si le nom a déjà été défini)
  • La construction let est similaire à la construction let dans Lisp et Scheme; qui sont non récursifs. Il y a une construction letrec séparée dans Scheme pour récursive

Compte tenu de ceci:

 let fx = ... and gy = ...;; 

Comparer:

 let fa = f (ga) 

Avec ça:

 let rec fa = f (ga) 

Le premier redéfinit f pour appliquer le f précédemment défini au résultat de l’application de g à a . Ce dernier redéfinit f pour boucler toujours l’application de g à a , ce qui n’est généralement pas ce que vous voulez dans les variantes ML.

Cela dit, c’est un style de styliste. Va juste avec ça.

Une grande partie de cela est que cela donne au programmeur plus de contrôle sur la complexité de leurs étendues locales. Le spectre de let , let* et let rec offre un niveau croissant de puissance et de coût. let* et let rec sont par essence des versions nestedes du simple let , donc utiliser l’une ou l’autre est plus coûteux. Cette gradation vous permet de microgérer l’optimisation de votre programme, car vous pouvez choisir le niveau dont vous avez besoin pour la tâche à accomplir. Si vous n’avez pas besoin de la récursivité ou de la possibilité de vous référer aux liaisons précédentes, vous pouvez utiliser une méthode simple pour économiser un peu de performance.

C’est similaire aux prédicats d’égalité gradués dans Scheme. (ie eq? eqv? et equal? )