Caml, strict ou pas ?

Bonsoir les zestes,

Je me baladais sur la toile et après une soirée fort fructueuse à découvrir plein de trucs aussi inutiles qu'indispensables, et à commencer à m'introduire au LISP (je frémis d'avance devant le monde qui s'ouvre à moi tellement c'est bô), j'ai décidé de tenter de débrouiller un minimum de théorie des langages fonctionnels de ce que mon peu d'expérience en la matière a pu me fournir comme grain à moudre. J'ai donc suivi quelques liens et atterri sur ce PDF (au passage bien foutu et agréable à lire pour une initiation) sur Caml ; je connais déjà un peu le langage et ses subtilités, mais bon, un peu de rappel n'a jamais fait de mal à personne.

Or, quelle ne fut pas ma stupeur lorsque je suis tombé à la page 14 sur cette phrase anodine :

Soit j'ai mal compris la définition d'un langage strict, soit plusieurs choses se heurtent dans ma tête. En effet, il me semble (non, en fait j'en suis presque certain) que l'évaluation des conditions en Caml, qui ne sont que des expressions puisqu'on est fonctionnel, est justement paresseuse. Ce qui permet de faire des trucs du genre :

1

if n = 0 && trololo then 42 else 42 / n;;

(Oui je sais, c'est bidon, mais j'avais pas d'exemple pertinent en tête. Et la flemme d'en chercher un, aussi.)

Bref. Je comprends intuitivement pourquoi ça marche, là n'est pas le propos, mais du coup j'ai un peu de mal à fixer dans ma tête la définition de ces termes de strict et paresseux… Quelqu'un dans ces eaux troubles pourrait-il éclairer ma lanterne ? Merci d'avance et bon courage pour éclairer une lanterne sous la flotte.

Edit : en fait mon exemple est plus que bidon, il est raté… Mais je sais que l'évaluation des prédicats est paresseuse, si on fait machin && truc et que machin est faux, alors truc ne sera pas testé… Bref, c'est le bordel dans mon cortex informatique. Please help!

Il est vrai que en Caml, le if est paresseux. Au de là du prédicat, 42 et 42 / n sont aussi paresseux - au final, if peut très bien être traduit en lambda-calcul. Maintenant, imagine ce code:

1

let rec f n = if n <= 0 then 0 else f (n - 1) + n

Si nous ne considérions pas le if comme lazy, on devrait évaluer 0 et f (n - 1) + n aussi indépendamment du prédicat - en faite, on considérerais if comme une abstraction pour laquelle il faut évaluer ses arguments. Sauf que ton évaluation va "boucler" car tu vas vouloir évaluer en particulier f (n - 1) et donc réévaluer le corps de la fonction f, donc réévaluer les arguments de if. Tu comprendras que ce n'est pas possible.

En somme, c'est pour cette raison que le if est lazy, notamment pour la récursivité. Maintenant, il y a plusieurs manières de le considérer comme paresseux. La première, c'est considérer if, non plus comme une fonction, mais comme une primitive sur laquelle on applique une compilation spécifique (ce qui est le cas ici en OCaml). Un autre moyen, c'est de wrapper les arguments (typiquement avec ()) pour ensuite les appliquer comme avec cette exemple:

1

let f n = (if n <= 0 then (fun () -> 0) else (fun () -> f (n - 1) + n)) ()

Maintenant, ce point est pour correspondre au vrai monde. Et même si le if est paresseux, on considère tout de même OCaml comme un langage stricte à la différence de Haskell par exemple.

EDIT: Après relecture, c'est pas super clair ce que je dis notamment le fait que tu vas boucler si tu considères par le if comme lazy donc voici un exemple plus parlant:

1
2

let if' i a b = if i then a else b
let f x = if' (x <= 0) 0 (f (x - 1) + x)

Si tu exécutes f, tu auras un stack-overflow puisqu'on va essayer d'évaluer les arguments (notamment la récursion) indépendamment du prédicat. Dans la récursion, il n'y aura donc aucun point d'arrêt (car même si x <= 0, on évaluera quand même (f (x - 1) + x). Voilà !

Salut,

Avec l'évaluation paresseuse, tu n'as pas à te soucier de l'ordre d'évaluation ou des calculs inutiles dans un programme. Par exemple, si une expression n'est pas utile dans le calcul d'un résultat, celle-ci ne sera pas évaluée tandis que dans un contexte strict, ça peut poser problème (programme qui boucle ou qui plante). L'évaluation stricte tient du style de programmation impératif. Evaluation paresseuse sonne plus avec programme récursif.

OCaml est stricte par défaut mais autorise l'évaluation paresseuse lorsque nécessaire. Il y a cependant un module d'évaluation paresseuse (Lazy) qui permettent d'écrire des expressions paresseuses.

Un exemple : la division par 0. Dans ce programme à évaluation stricte, l'appel va sortir une erreur de division par zéro:

1
2
3
4

# let func1 x = 42;;
val func1 : 'a -> int = <fun>
# func1 (10 / 0);;
Exception: division_by_zero.

Et en créant une expression paresseuse :

1
2
3
4

# let lazy_expr = lazy(10 / 0);;
val lazy_expr : int lazy_t = <not evaluated>
# func1 lazy_expr;;
- : int = 42

Je rajouterais un lien pour que tu comprennes que cette caractéristique est hérité par les opérateurs ( || ) et ( && ). Voilà, j'espère que tu y vois plus clair.

Merci beaucoup à vous deux, c'est parfait !

Avec l'évaluation paresseuse, tu n'as pas à te soucier de l'ordre d'évaluation ou des calculs inutiles dans un programme. Par exemple, si une expression n'est pas utile dans le calcul d'un résultat, celle-ci ne sera pas évaluée tandis que dans un contexte strict, ça peut poser problème (programme qui boucle ou qui plante). L'évaluation stricte tient du style de programmation impératif. Evaluation paresseuse sonne plus avec programme récursif.

Attention, ce n'est pas parce que tu choisis d'avoir une stratégie d'évaluation paresseuse que ça t'empêche de définir un ordre d'évaluation . Et réciproquement, tu peux avoir un ordre d'évaluation indéfini dans un langage strict (c'est par exemple le cas en C si je ne m'abuse). En pratique, dans les langages qu'on croise, ceux qui adoptent une stratégie paresseuse (c'est à dire haskell) se trouve(nt) également être fonctionnel prétendument « pur », et une conséquence est que l'ordre d'évaluation ne change rien, puisqu'on ne veut pas parler d'effets de bord (en réalité, c'est évidemment plus compliqué, parce qu'il faut bien choisir l'ordre d'évaluation d'une suite d'expressions qui affichent un truc à l'écran).

De même, le raccourci « strict = impératif, paresseux = fonctionnel » est un peu rapide, plutôt faux, et risque surtout de compliquer la compréhension de choses qui n'ont en réalité pas de rapport. Le fait qu'un langage soit à évaluation stricte signifie uniquement que les arguments d'une fonction sont évalués avant d'être appliqués à la fonction. Ça ne dit absolument rien sur le fait que le programme marche par modifications successives d'un état global ou par transformations d'expressions. C'est pareil dans l'autre sens : on peut parfaitement avoir un langage impératif qui permet de construire des valeurs paresseuses (c'est-à-dire des valeurs qui ne seront pas évaluées lorsqu'elles sont passées en paramètres d'une fonction, mais « plus tard », quand on aura besoin de faire cette évaluation pour obtenir un résultat final - ou quand elles seront passées à une fonction marquée comme stricte).

De même, le raccourci « strict = impératif, paresseux = fonctionnel » est un peu rapide

Oui, je suis d'accord. Je me suis mal exprimé dans mon post. L'évaluation stricte est très utilisé dans les langages impératifs du fait que l'ordre d'exécution des expressions correspond à celui de leurs définitions.

Ce qui n'empêche pas d'avoir des comportements paresseux, en Python le comportement des conditions et prédicats est le même qu'en Caml.