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

Pourquoi les fonctions en F # et Ocaml (et éventuellement dans d'autres langages) 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 faire explicitement taper recune déclaration comme:

let rec foo ... = ...

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

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 aux variantes modernes. Ce n'est donc qu'un héritage, mais cela affecte les idiomes dans ces langues.

Les fonctions ne sont pas récursives par défaut dans la famille de langages français CAML (y compris OCaml). Ce choix facilite le remplacement des définitions de fonction (et de variable) utilisées letdans 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, remplacer la fonction plors 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 pde la shannonfonction d' ordre supérieur est remplacé par un autre pdans la première ligne du corps, puis un autre pdans la deuxième ligne du corps.

À l'inverse, la branche britannique SML de la famille de langages ML a pris l'autre choix et les funfonctions liées à SML sont récursives par défaut. Lorsque la plupart des définitions de fonction n'ont pas besoin d'accéder aux liaisons précédentes de leur nom de fonction, cela se traduit par un code plus simple. Cependant, les fonctions remplacées sont amenées à utiliser des noms différents ( f1, f2etc.) qui polluent la portée et permettent d'invoquer accidentellement la mauvaise «version» d'une fonction. Et il y a maintenant un écart entre les funfonctions liées implicitement récursives et les fonctions liées non récursives val.

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

Notez que les réponses données par Ganesh et Eddie sont des harengs rouges. Ils ont expliqué pourquoi les groupes de fonctions ne peuvent pas être placés à l'intérieur d'un géant let rec ... and ...car cela affecte le moment où les variables de type sont généralisées. Cela n'a rien à voir avec le fait d' recêtre par défaut dans SML mais pas avec OCaml.

Une raison cruciale de l'utilisation explicite de recest liée à l'inférence de type Hindley-Milner, qui sous-tend tous les langages de programmation fonctionnelle typés statiquement (bien que modifiés et étendus de diverses manières).

Si vous avez une définition let f x = x, vous vous attendez à ce qu'elle ait un type 'a -> 'aet qu'elle soit applicable sur différents 'atypes à différents points. Mais également, si vous écrivez let g x = (x + 1) + ..., vous vous attendez xà être traité comme un intdans le reste du corps de g.

La manière dont l'inférence Hindley-Milner traite cette distinction passe par une étape de généralisation explicite . À certains moments lors du traitement de votre programme, le système de types 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 libre dans leur type seront fraîchement 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 après avoir vérifié un ensemble de fonctions mutuellement récursives. Tout plus tôt, et vous généraliserez trop, conduisant à des situations où les types pourraient réellement entrer en collision. Plus tard, et vous généraliserez trop peu, créant des définitions qui ne peuvent pas être utilisées avec plusieurs instanciations de types.

Donc, étant donné que le vérificateur de type a besoin de savoir quels ensembles de définitions sont mutuellement récursifs, que peut-il faire? Une possibilité consiste simplement à effectuer une analyse de dépendance sur toutes les définitions d'une étendue et à les réorganiser dans les plus petits groupes possibles. Haskell le fait en fait, 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 également réorganiser les effets secondaires. Donc, à la place, il demande à l'utilisateur de marquer explicitement quelles définitions 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:

Premièrement, si vous activez les définitions récursives, vous ne pouvez pas faire référence à une liaison précédente d'une valeur du même nom. C'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 procèdent dans l'ordre, chaque nouvelle définition s'appuyant sur ce qui a déjà été défini. Il est agréable, lors de la lecture d'un tel code, 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:

• letn'est pas seulement utilisé pour lier des fonctions, mais également d'autres valeurs régulières. La plupart des formes de valeurs ne sont pas autorisées à être récursives. Certaines formes de valeurs récursives sont autorisées (par exemple les fonctions, les expressions paresseuses, etc.), il faut donc une syntaxe explicite pour l'indiquer.
• Il peut être plus facile d'optimiser les fonctions non récursives
• La fermeture créée lorsque vous créez une fonction récursive doit inclure une entrée qui pointe vers la fonction elle-même (afin que la fonction puisse s'appeler elle-même 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 termes d'une fonction préalablement définie ou d'une valeur du même nom; même si je pense que c'est une mauvaise pratique
• Sécurité supplémentaire? S'assure que vous faites ce que vous vouliez. Par exemple, si vous ne souhaitez pas que ce soit récursif mais que vous avez accidentellement utilisé un nom dans la fonction avec le même nom que la fonction elle-même, il se plaindra probablement (à moins que le nom n'ait été défini auparavant)
• La letconstruction est similaire à la letconstruction en Lisp et Scheme; qui sont non récursifs. Il existe une letrecconstruction distincte dans Scheme pour les récursifs Let's

Compte tenu de ceci:

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

Comparer:

let f a = f (g a)

Avec ça:

let rec f a = f (g a)

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

Cela dit, c'est une chose de style concepteur de langage. Allez-y simplement.

Une grande partie de cela est que cela donne au programmeur plus de contrôle sur la complexité de leurs portées locales. Le spectre de let, let*et let recoffre un niveau croissant de puissance et de coût. let*et let recsont essentiellement des versions imbriquées du simplelet , donc utiliser l'un ou l'autre est plus coûteux. Cette notation vous permet de microgérer l'optimisation de votre programme car vous pouvez choisir le niveau de disponibilité dont vous avez besoin pour la tâche à accomplir. Si vous n'avez pas besoin de récursivité ou de la possibilité de faire référence à des liaisons précédentes, vous pouvez vous rabattre sur un simple let pour économiser un peu de performances.

C'est similaire aux prédicats d'égalité graduée dans Scheme. (c'est eq?-à- dire eqv?et equal?)