Haskell: Comment diffèrent les non-ssortingcts et les paresseux?

Je lis souvent que la paresse n’est pas la même chose que la non-ssortingcte, mais j’ai du mal à comprendre la différence. Ils semblent être utilisés indifféremment, mais je comprends qu’ils ont des significations différentes. J’apprécierais un peu d’aide pour comprendre la différence.

J’ai quelques questions qui sont éparpillées à propos de cet article. Je résumerai ces questions à la fin de ce post. J’ai quelques exemples de snippets, je ne les ai pas testés, je les ai seulement présentés comme des concepts. J’ai ajouté des devis pour vous empêcher de les rechercher. Peut-être que cela aidera plus tard quelqu’un avec la même question.

Def non ssortingct:

Une fonction f est dite ssortingcte si, lorsqu’elle est appliquée à une expression non limitante, elle ne parvient pas non plus à se terminer. En d’autres termes, f est ssortingct si la valeur de f bot est | . Pour la plupart des langages de programmation, toutes les fonctions sont ssortingctes. Mais ce n’est pas le cas à Haskell. Comme exemple simple, considérons const1, la fonction constante 1, définie par:

const1 x = 1

La valeur de const1 bot dans Haskell est 1. Sur le plan opérationnel, étant donné que const1 n’a pas “besoin” de la valeur de son argument, il ne tente jamais de l’évaluer et ne se retrouve donc jamais dans un calcul non définitif. Pour cette raison, les fonctions non ssortingctes sont également appelées “fonctions paresseuses”, et sont censées évaluer leurs arguments “paresseusement” ou “par besoin”.

– Une introduction douce à Haskell: Fonctions

J’aime beaucoup cette définition. Il semble que le meilleur que j’ai pu trouver pour comprendre ssortingct. Est-ce que const1 x = 1 aussi paresseux?

La non-ssortingcte signifie que la réduction (le terme mathématique pour l’évaluation) procède de l’extérieur

donc si vous avez (a + (b c)) alors vous réduisez d’abord le +, puis vous réduisez l’intérieur (b c).

– Wiki Haskell: Lavy vs non-ssortingct

Le Wiki Haskell me confond vraiment. Je comprends ce qu’ils disent à propos de l’ordre mais je ne vois pas comment (a+(b*c)) évaluerait non ssortingctement si c’était pass _|_ ?

Dans une évaluation non ssortingcte, les arguments d’une fonction ne sont évalués que s’ils sont réellement utilisés dans l’évaluation du corps de la fonction.

Sous l’encodage de l’Église, l’évaluation paresseuse des opérateurs correspond à une évaluation non ssortingcte des fonctions; pour cette raison, l’évaluation non ssortingcte est souvent appelée “paresseux”. Les expressions booléennes dans de nombreux langages utilisent une forme d’évaluation non ssortingcte appelée évaluation des courts-circuits, où l’évaluation revient dès qu’il est possible de déterminer qu’un booléen sans ambiguïté résultera, par exemple dans une expression disjonctive où true est rencontré ou dans une expression conjonctive où faux est rencontré, et ainsi de suite. Les expressions conditionnelles utilisent aussi généralement l’évaluation paresseuse, où l’évaluation revient dès qu’une twig non ambiguë se produit.

– Wikipedia: Stratégie d’évaluation

Lazy Def:

Par contre, l’évaluation paresseuse signifie seulement évaluer une expression lorsque ses résultats sont nécessaires (noter le passage de «réduction» à «évaluation»). Ainsi, lorsque le moteur d’évaluation détecte une expression, il crée une structure de données thunk contenant les valeurs nécessaires à l’évaluation de l’expression, ainsi qu’un pointeur vers l’expression elle-même. Lorsque le résultat est réellement nécessaire, le moteur d’évaluation appelle l’expression, puis remplace le thunk par le résultat pour référence ultérieure. …

De toute évidence, il existe une forte correspondance entre un thunk et une expression partiellement évaluée. Par conséquent, dans la plupart des cas, les termes “paresseux” et “non ssortingct” sont synonymes. Mais pas tout à fait.

– Wiki Haskell: Lavy vs non-ssortingct

Cela semble être une réponse spécifique à Haskell. Je considère que paresseux signifie thunks et non-ssortingct signifie évaluation partielle. Cette comparaison est-elle trop simplifiée? Est-ce que paresseux signifie toujours que les thunks et non-ssortingcts signifient toujours une évaluation partielle.

En théorie des langages de programmation, l’évaluation différée ou l’appel par besoin 1 est une stratégie d’évaluation qui retarde l’évaluation d’une expression jusqu’à ce que sa valeur soit réellement requirejse (évaluation non ssortingcte) et évite également des évaluations répétées (partage).

– Wikipedia: évaluation paresseuse

Exemples impératifs

Je sais que la plupart des gens disent oublier la programmation impérative lors de l’apprentissage d’un langage fonctionnel. Cependant, j’aimerais savoir si ces critères sont non ssortingcts, paresseux, les deux ou aucun des deux? À tout le moins, cela fournirait quelque chose de familier.

Court circuit

 f1() || f2() 

C #, Python et d’autres langages avec “yield”

 public static IEnumerable Power(int number, int exponent) { int counter = 0; int result = 1; while (counter++ < exponent) { result = result * number; yield return result; } } 

– MSDN: yield (c #)

Rappels

 int f1() { return 1;} int f2() { return 2;} int lazy(int (*cb1)(), int (*cb2)() , int x) { if (x == 0) return cb1(); else return cb2(); } int eager(int e1, int e2, int x) { if (x == 0) return e1; else return e2; } lazy(f1, f2, x); eager(f1(), f2(), x); 

Des questions

Je sais que la réponse est juste devant moi avec toutes ces ressources, mais je ne peux pas le comprendre. Tout semble indiquer que la définition est trop facilement rejetée comme implicite ou évidente.

Je sais que j’ai beaucoup de questions. N’hésitez pas à répondre aux questions qui vous semblent pertinentes. J’ai ajouté ces questions pour la discussion.

  • Est-ce que const1 x = 1 aussi paresseux?
  • Comment l’évaluation de “l’intérieur” est-elle non ssortingcte? Est-ce parce que l’intérieur permet des réductions d’expressions inutiles, comme dans const1 x = 1 ? Les réductions semblent correspondre à la définition du paresseux.
  • Est-ce que paresseux signifie toujours thunks et non-ssortingct signifie toujours évaluation partielle ? Est-ce juste une généralisation?
  • Les concepts impératifs suivants sont-ils paresseux, non-ssortingcts, les deux ou aucun des deux?
    • Court circuit
    • En utilisant le rendement
    • Passer des rappels pour retarder ou éviter l’exécution
  • Est-ce un sous-ensemble de non-ssortingct ou vice-versa, ou sont-ils mutuellement exclusifs. Par exemple, est-il possible d’être non ssortingct sans être paresseux ou paresseux sans être non ssortingct ?
  • La non-rigueur de Haskell est-elle atteinte par la paresse?

Merci!

Non ssortingctes et paresseuses, bien qu’interchangeables de manière informelle, s’appliquent à différents domaines de discussion.

Non-ssortingct fait référence à la sémantique : la signification mathématique d’une expression. Le monde auquel s’applique une application non ssortingcte n’a aucune notion de la durée de fonctionnement d’une fonction, de la consommation de mémoire ou même d’un ordinateur. Il parle simplement des types de valeurs dans le domaine mappant à quels types de valeurs dans le codomain. En particulier, une fonction ssortingcte doit mapper la valeur ⊥ (“bottom” – voir le lien de sémantique ci-dessus pour plus d’informations) à ⊥; une fonction non ssortingcte est autorisée à ne pas le faire.

Lazy fait référence au comportement opérationnel: la façon dont le code est exécuté sur un ordinateur réel. La plupart des programmeurs pensent aux programmes de manière opérationnelle, donc c’est probablement ce que vous pensez. L’évaluation différée se réfère à l’implémentation à l’aide de thunks – des pointeurs vers du code qui sont remplacés par une valeur la première fois qu’ils sont exécutés. Notez les mots non sémantiques ici: “pointeur”, “première fois”, “exécuté”.

L’évaluation paresseuse donne lieu à une sémantique non ssortingcte, raison pour laquelle les concepts semblent si proches les uns des autres. Mais comme le souligne FUZxxl, la paresse n’est pas la seule façon d’implémenter une sémantique non ssortingcte.

Si vous souhaitez en savoir plus sur cette distinction, je vous recommande vivement le lien ci-dessus. Sa lecture a marqué un tournant dans ma conception de la signification des programmes informatiques.

Un exemple de modèle d’évaluation, ni ssortingct ni paresseux: une évaluation optimiste , qui permet d’accélérer un peu car elle permet d’éviter de nombreux thunks «faciles»:

Une évaluation optimiste signifie que même si une sous-expression peut ne pas être nécessaire pour évaluer la surexpression, nous en évaluons encore certaines en utilisant des heuristiques. Si la sous-expression ne se termine pas assez rapidement, nous suspendons son évaluation jusqu’à ce qu’elle soit vraiment nécessaire. Cela nous donne un avantage sur l’évaluation paresseuse si la sous-expression est nécessaire plus tard, car nous n’avons pas besoin de générer de thunk. D’autre part, nous ne perdons pas trop si l’expression ne se termine pas, car nous pouvons l’abandonner assez rapidement.

Comme vous pouvez le constater, ce modèle d’évaluation n’est pas ssortingct : si quelque chose qui renvoie _ | _ est évalué, mais n’est pas nécessaire, la fonction se terminera quand le moteur abandonnera l’évaluation. D’un autre côté, il est possible que plus d’expressions que nécessaire soient évaluées, donc ce n’est pas complètement paresseux .

Oui, l’utilisation de la terminologie n’est pas claire, mais les termes coïncident dans la plupart des cas, donc ce n’est pas trop un problème.

Une différence majeure est lorsque les termes sont évalués . Il existe de multiples stratégies pour cela, allant de “dès que possible” à “seulement au dernier moment”. Le terme d’ évaluation avide est parfois utilisé pour les stratégies orientées vers le premier, tandis que l’ évaluation paresseuse fait référence à une famille de stratégies fortement orientées vers le second. La distinction entre «évaluation paresseuse» et les stratégies associées a tendance à impliquer quand et où le résultat de l’évaluation de quelque chose est conservé, plutôt que d’être mis de côté. La technique de mémorisation habituelle dans Haskell consistant à atsortingbuer un nom à une structure de données et à y indexer est basée sur cela. En revanche, un langage qui a simplement épissé les expressions les unes avec les autres (comme dans l’évaluation “call-by-name”) pourrait ne pas le supporter.

L’autre différence est que les termes sont évalués , allant de “absolument tout” à “le moins possible”. Comme toute valeur réellement utilisée pour calculer le résultat final ne peut être ignorée, la différence réside dans le nombre de termes superflus évalués. En plus de réduire la quantité de travail du programme, ignorer les termes non utilisés signifie que toutes les erreurs qu’ils auraient générées ne se produiraient pas. Lorsqu’une distinction est établie, la rigueur fait référence à la propriété d’évaluer tout ce qui est considéré (dans le cas d’une fonction ssortingcte, par exemple, cela signifie les termes auxquels elle est appliquée. Cela ne signifie pas nécessairement des sous-expressions à l’intérieur des arguments) , alors que non ssortingct signifie évaluer seulement certaines choses (soit en retardant l’évaluation, soit en rejetant complètement les termes).

Il devrait être facile de voir comment ceux-ci interagissent de manière compliquée. les décisions ne sont pas du tout orthogonales, car les extrêmes ont tendance à être incompatibles. Par exemple:

  • Une évaluation très non ssortingcte exclut une certaine quantité d’empressement; Si vous ne savez pas si un terme sera nécessaire, vous ne pouvez pas encore l’évaluer.

  • Une évaluation très ssortingcte rend le non-empressement quelque peu hors de propos; Si vous évaluez tout, la décision de le faire est moins importante.

Il existe cependant d’autres définitions. Par exemple, au moins dans Haskell, une “fonction ssortingcte” est souvent définie comme une fonction qui force suffisamment ses arguments pour que la fonction évalue | chaque fois qu’un argument le fait; notez que par cette définition, id est ssortingct (au sens sortingvial), car forcer le résultat de id x aura exactement le même comportement que forcer x seul.

Cela a commencé comme une mise à jour mais cela a commencé à être long.

La paresse / Call-by-need est une version mémorisée de call-by-name où, si l’argument de la fonction est évalué, cette valeur est stockée pour des utilisations ultérieures. Dans un paramètre “pur” (sans effet), cela produit les mêmes résultats que l’appel par nom; Lorsque l’argument de la fonction est utilisé deux fois ou plus, l’appel par besoin est presque toujours plus rapide.
Exemple impératif – Apparemment, c’est possible. Il y a un article intéressant sur les langages impératifs paresseux . Il dit qu’il y a deux méthodes. On exige des fermetures, la seconde utilise des réductions de graphiques. Comme C ne prend pas en charge les fermetures, vous devez explicitement passer un argument à votre iterator. Vous pouvez envelopper une structure de carte et si la valeur n’existe pas, calculer la valeur autrement.
Remarque : Haskell implémente ceci par “des pointeurs sur du code qui sont remplacés par une valeur la première fois qu’ils sont exécutés” – luqui.
C’est un appel par nom non ssortingct mais avec partage / mémorisation des résultats.

Call-By-Name – Dans l’évaluation call-by-name, les arguments d’une fonction ne sont pas évalués avant l’appel de la fonction – ils sont plutôt substitués directement dans le corps de la fonction (en utilisant la substitution évitant la capture) évaluées chaque fois qu’elles apparaissent dans la fonction. Si un argument n’est pas utilisé dans le corps de la fonction, l’argument n’est jamais évalué; s’il est utilisé plusieurs fois, il est réévalué à chaque fois qu’il apparaît.
Exemple impératif: rappels
Note: Ceci est non ssortingct car cela évite l’évaluation si elle n’est pas utilisée.

Non-ssortingct = Dans une évaluation non ssortingcte, les arguments d’une fonction ne sont évalués que s’ils sont réellement utilisés dans l’évaluation du corps de la fonction.
Exemple impératif : court-circuit
Remarque : _ | _ semble être un moyen de tester si une fonction est non ssortingcte

Une fonction peut donc être non ssortingcte mais pas paresseuse. Une fonction paresseuse est toujours non ssortingcte. Call-By-Need est défini en partie par Call-By-Name, défini en partie par Non-Ssortingct

Un extrait de “Lazer Imperative Languages”

2.1. SÉMANTIQUE NON STRICTE VS. EVALUATION DE LAZE Nous devons d’abord clarifier la distinction entre “sémantique non ssortingcte” et “évaluation paresseuse”. Les non-stencingemantics sont ceux qui spécifient qu’une expression n’est pas évaluée jusqu’à ce qu’une opération de primitive l’exige. Il peut y avoir différents types de sémantique non ssortingcte. Par exemple, les appels de procédure non ssortingcts ne permettent pas d’évaluer les arguments tant que leurs valeurs ne sont pas requirejses. Les constructeurs de données peuvent avoir des propriétés non stencingemantiques, dans lesquelles les données composées sont assemblées à partir de pièces non évaluées. L’évaluation paresseuse, également appelée évaluation différée, est la technique normalement utilisée pour implémenter des parameters non ssortingcts. Dans la section 4, les deux méthodes couramment utilisées pour mettre en œuvre l’évaluation différée sont très brièvement résumées.

CALL BY VALUE, CALL BY LAZY, et CALL BY NAME “Appel par valeur” est le nom général utilisé pour les appels de procédure avec une sémantique ssortingcte. Lors d’un appel par des valeurs, chaque argument d’un appel de procédure est évalué avant l’appel de procédure; la valeur est ensuite transmise à la procédure ou à l’expression englobante. Un autre nom pour l’appel par valeur est l’évaluation “avide”. L’appel par valeur est également appelé “évaluation applicative”, car tous les arguments sont évalués avant que la fonction ne leur soit appliquée. “Appel par paresseux” ]) est le nom donné aux appels de procédure dont la sémantique est usenon-ssortingct. Dans les langues appelées par des appels de procédure différés, les arguments ne sont pas évalués avant d’être substitués dans le corps de la procédure. L’appel par évaluation paresseuse est aussi appelé évaluation “ordre normal”, à cause de l’ordre (de l’extérieur à l’intérieur, de gauche à droite) de l’évaluation d’une expression. “Appel par nom” -60 [18]. Les concepteurs d’Algol-60 ont voulu que les parameters call-by-name soient physiquement substitués dans le corps de la procédure, entre parenthèses et avec des changements de noms appropriés pour éviter les conflits, avant que le corps ne soit évalué.

APPEL PAR LAZY VS. CALL BY NEED L’appel par nécessité est une extension de l’appel par lazy, provoquée par l’observation qu’une évaluation paresseuse pourrait être optimisée en mémorisant la valeur d’une expression différée donnée, une fois forcée, pour que la valeur ne soit pas recalculée si nécessaire. L’évaluation des appels par besoin étend donc l’appel par des méthodes paresseuses en utilisant la mémorisation pour éviter la nécessité d’une évaluation répétée. Friedman et Wise ont été parmi les premiers avocats de l’évaluation des besoins, proposant des «suspensions suicidaires» qui se sont auto-détruites lors de leur première évaluation, se substituant à leurs valeurs.

Si l’on parle de jargon informatique général, alors «paresseux» et «non ssortingct» sont généralement synonymes – ils représentent la même idée globale, qui s’exprime de différentes manières pour différentes situations.

Cependant, dans un contexte spécialisé donné, ils peuvent avoir des significations techniques différentes. Je ne pense pas que vous puissiez dire quoi que ce soit de précis et universel sur ce que la différence entre “paresseux” et “non-ssortingct” est susceptible d’être dans la situation où il y a une différence à faire.