Quelle est la différence entre non strict et paresseux ?

Question

Je lis souvent que paresseux n'est pas la même chose que non stricte mais je trouve difficile de comprendre la différence. Ils semblent pour être utilisés de manière interchangeable mais je comprends qu'ils ont des significations différentes. J'apprécierais que l'on m'aide à comprendre la différence.

J'ai quelques questions qui sont éparpillées dans ce post. Je résumerai ces questions à la fin de ce billet. 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 citations pour vous éviter de les chercher. Peut-être que cela aidera quelqu'un qui se posera la même question plus tard.

Défense non stricte :

Une fonction f est dite stricte si, lorsqu'elle est appliquée à une expression non terminante non terminale, elle ne se termine pas non plus. En d'autres termes, f est stricte si la valeur de f bot est | . Pour la plupart des langages de programmation, toutes les fonctions sont strictes. Mais ce n'est pas le cas en Haskell. Un exemple simple exemple simple, considérons const1, la fonction constante 1, définie par :

const1 x = 1

La valeur de const1 bot en Haskell est 1. D'un point de vue opérationnel, puisque const1 n'a pas "besoin" de la valeur de son argument, il ne tente jamais de de l'évaluer, et donc n'est jamais pris dans un calcul non terminant. nonterminant. Pour cette raison, les fonctions non strictes sont également appelées "fonctions paresseuses". "fonctions paresseuses", et on dit qu'elles évaluent leurs arguments "paresseusement", ou "par besoin".

- Une introduction douce à Haskell : Fonctions

J'aime beaucoup cette définition. Elle semble être la meilleure que j'ai pu trouver pour comprendre le terme "strict". Est-ce que const1 x = 1 paresseux aussi ?

La non-striction signifie que la réduction (le terme mathématique pour évaluation) se fait de l'extérieur vers l'intérieur,

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

- Haskell Wiki : Lazy vs non-strict

Le Haskell Wiki m'embrouille vraiment. Je comprends ce qu'ils disent à propos de l'ordre mais je ne vois pas comment (a+(b*c)) serait évalué de manière non stricte s'il s'agissait d'un pass _|_ ?

En évaluation non stricte, les arguments d'une fonction ne sont pas évalués sauf s'ils sont effectivement utilisés dans l'évaluation du corps de la fonction.

Sous le codage de Church, l'évaluation paresseuse des opérateurs correspond à l'évaluation non stricte l'évaluation non stricte des fonctions ; pour cette raison, l'évaluation non stricte est souvent qualifiée de "paresseuse". Les expressions booléennes de nombreux langages utilisent une forme d'évaluation non stricte appelée évaluation en court-circuit, dans laquelle l'évaluation revient dès qu'il est possible de déterminer qu'un booléen non ambigu en résultera. booléen non ambigu - par exemple, dans une expression disjonctive où true est rencontré, ou dans une expression conjonctive où false 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 branche non ambiguë non ambiguë.

- Wikipedia : Stratégie d'évaluation

Défense paresseuse :

L'évaluation paresseuse, en revanche, consiste à n'évaluer une expression que lorsque ses résultats sont nécessaires. expression que lorsque ses résultats sont nécessaires (notez le passage de la "réduction" à "évaluation"). Ainsi, lorsque le moteur d'évaluation voit une expression une expression, il construit une structure de données thunk contenant les valeurs nécessaires à l'évaluation de l'expression, ainsi qu'une structure de données thunk. nécessaires à l'évaluation de l'expression, plus un pointeur vers l'expression elle-même. l'expression elle-même. Lorsque le résultat est réellement nécessaire, le moteur d'évaluation appelle l'expression et remplace ensuite le thunk avec le résultat résultat pour référence future. ...

De toute évidence, il y a 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-strict" sont des synonymes. Mais pas tout à fait.

- Haskell Wiki : Lazy vs non-strict

Cela semble être une réponse spécifique à Haskell. Je suppose que paresseux signifie des bruits sourds et non stricte signifie une évaluation partielle. Cette comparaison n'est-elle pas trop simplifiée ? Est-ce que paresseux signifie toujours des bruits sourds et non stricte signifie toujours une évaluation partielle.

Dans la théorie des langages de programmation, l'évaluation paresseuse ou le call-by-need 1 est une stratégie d'évaluation qui retarde l'évaluation d'une expression jusqu'à ce que sa valeur soit réellement requise (évaluation non stricte) et également d'éviter les évaluations répétées (partage).

- Wikipédia : Évaluation paresseuse

Exemples d'impératifs

Je sais que la plupart des gens disent d'oublier la programmation impérative lorsqu'on apprend un langage fonctionnel. Cependant, j'aimerais savoir si ceux-ci sont qualifiés de non impératifs, de paresseux, des deux ou d'aucun des deux ? Cela permettrait au moins d'avoir quelque chose de familier.

Court-circuitage

f1() || f2()

C#, Python et autres langages avec "yield" (rendement)

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

- MSDN : rendement (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);

Questions

Je sais que la réponse est juste devant moi avec toutes ces ressources, mais je n'arrive pas à la saisir. Tout semble indiquer que la définition est trop facilement rejetée comme étant 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 const1 x = 1 aussi paresseux ?
• Comment l'évaluation de "l'intérieur" peut-elle être non stricte ? Est-ce parce que "inward" permet de réduire les expressions inutiles, comme en const1 x = 1 ? Les réductions semblent correspondre à la définition de la paresse.
• Fait paresseux signifie toujours thunks et non stricte signifie toujours évaluation partielle ? S'agit-il d'une simple généralisation ?
• Les concepts impératifs suivants sont-ils paresseux, non stricts, les deux ou aucun ?
  • Court-circuitage
  • Utilisation du rendement
  • Passage de Callbacks pour retarder ou éviter l'exécution
• Est paresseux un sous-ensemble de non stricte ou vice versa, ou sont-ils mutuellement exclusifs. Par exemple, est-il possible d'être non stricte sans être paresseux ou paresseux sans être non stricte ?
• Le manque de rigueur de Haskell est-il dû à la paresse ?

Merci beaucoup !

Answer 1

Non-strict et paresseux, bien qu'interchangeables de manière informelle, s'appliquent à des domaines de discussion différents.

Non-strict se réfère à sémantique : la signification mathématique d'une expression. Le monde auquel s'applique non-strict n'a aucun concept du temps d'exécution d'une fonction, de la consommation de mémoire, ou même d'un ordinateur. Il parle simplement de quels types de valeurs dans le domaine correspondent à quels types de valeurs dans le codomaine. En particulier, une strict doit faire correspondre la valeur ⊥ ("bottom" -- voir le lien sémantique ci-dessus pour en savoir plus) à ⊥ ; une fonction non stricte est autorisée à ne pas le faire.

Paresseux 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, c'est donc probablement ce à quoi vous pensez. L'évaluation paresseuse fait référence à l'implémentation utilisant des thunks -- des pointeurs vers du code qui sont remplacés par une valeur la première fois qu'ils sont exécutés. Remarquez les mots non sémantiques ici : "pointeur", "première fois", "exécuté".

L'évaluation paresseuse donne lieu à une sémantique non stricte, ce qui explique pourquoi les concepts semblent si proches. Mais comme le souligne FUZxxl, la paresse n'est pas le seul moyen de mettre en œuvre une sémantique non stricte.

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

Answer 2

Un exemple de modèle d'évaluation, qui n'est ni strict ni paresseux : évaluation optimiste ce qui donne un certain gain de vitesse car cela permet d'éviter un grand nombre de thunks "faciles" :

L'évaluation optimiste signifie que même si une sous-expression peut ne pas être nécessaire pour évaluer la super-expression, nous en évaluons quand même une partie en utilisant certaines 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 un thunk. D'autre part, nous ne perdons pas trop si l'expression ne se termine pas, car nous pouvons l'interrompre assez rapidement.

Comme vous pouvez le constater, ce modèle d'évaluation est non strict : Si quelque chose qui donne _|_ est évalué, mais n'est pas nécessaire, la fonction se terminera quand même, car le moteur abandonne l'évaluation. D'un autre côté, il est possible que plus d'expressions que nécessaire soient évaluées, alors c'est la fonction pas complètement paresseux .

Answer 3

Oui, la terminologie utilisée n'est pas toujours claire, mais les termes coïncident dans la plupart des cas, ce qui ne pose pas trop de 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 évaluation enthousiaste est parfois utilisé pour des stratégies qui penchent vers la première, alors que évaluation paresseuse fait proprement référence à une famille de stratégies penchant fortement vers la seconde. La distinction entre "l'évaluation paresseuse" et les stratégies connexes tend à impliquer quand et où le résultat de l'évaluation de quelque chose est conservé, par opposition à être mis de côté. La technique de mémorisation bien connue en Haskell, qui consiste à attribuer un nom à une structure de données et à l'indexer, est basée sur ce principe. En revanche, un langage qui se contente d'épisser les expressions les unes dans les autres (comme dans l'évaluation "call-by-name") pourrait ne pas supporter cela.

L'autre différence est quels termes sont évalués allant de "absolument tout" à "le moins possible". Comme toute valeur effectivement utilisée pour calculer le résultat final ne peut être ignorée, la différence ici réside dans le nombre de termes superflus évalués. En plus de réduire la quantité de travail que le programme doit effectuer, le fait d'ignorer les termes inutilisés signifie que les erreurs qu'ils auraient générées ne se produiront pas. Lorsqu'une distinction est établie, rigueur fait référence à la propriété d'évaluer tout ce qui est considéré (dans le cas d'une fonction stricte, par exemple, cela signifie les termes auxquels elle est appliquée. Il s'agit de n'a pas signifie nécessairement des sous-expressions à l'intérieur des arguments), alors que non stricte signifie que l'on n'évalue que certaines choses (soit en retardant l'évaluation, soit en éliminant complètement les termes).

Il devrait être facile de voir comment ces éléments 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 peu stricte exclut un certain degré d'impatience ; si vous ne savez pas si un terme sera nécessaire, vous ne pouvez pas encore l'évaluer.

• Une évaluation très stricte rend le manque d'empressement quelque peu non pertinent ; si vous évaluez tout, la décision de quand pour le faire est moins importante.

Il existe cependant des définitions alternatives. Par exemple, au moins en Haskell, une "fonction stricte" est souvent définie comme une fonction qui force suffisamment ses arguments pour que la fonction soit évaluée à _|_ ("bottom") chaque fois qu'un argument le fait ; notez que par cette définition, id est strict (dans un sens trivial), car forcer le résultat de id x aura exactement le même comportement que le forçage x seul.

Answer 4

C'était au départ une mise à jour, mais ça a commencé à devenir long.

Paresse / Appel par le besoin 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 cadre "pur" (sans effet), cela produit les mêmes résultats que call-by-name ; lorsque l'argument de la fonction est utilisé deux fois ou plus, call-by-need est presque toujours plus rapide.
Exemple d'impératif - Apparemment, c'est possible. Il y a un article intéressant sur Langages impératifs paresseux . Il est indiqué qu'il existe deux méthodes. L'une nécessite des fermetures, la seconde utilise des réductions de graphes. Comme le C ne supporte pas les fermetures, vous devrez explicitement passer un argument à votre itérateur. Vous pourriez envelopper une structure map et, si la valeur n'existe pas, la calculer, sinon renvoyer la valeur.
Note : Haskell implémente cela par "des pointeurs vers du code qui sont remplacés par une valeur la première fois qu'ils sont exécutés" - luqui.
Il s'agit d'un appel par nom non strict mais avec partage/mémorisation des résultats.

Appel par nom - Dans l'évaluation call-by-name, les arguments d'une fonction ne sont pas évalués avant que la fonction ne soit appelée - ils sont plutôt substitués directement dans le corps de la fonction (en utilisant la substitution évitant la capture) et ensuite laissés pour être évalués chaque fois qu'ils apparaissent dans la fonction. Si un argument n'est pas utilisé dans le corps de la fonction, il 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 : Il s'agit d'une mesure non stricte, car elle évite l'évaluation si elle n'est pas utilisée.

Non-Strict \= Dans une évaluation non stricte, les arguments d'une fonction ne sont pas évalués, sauf s'ils sont effectivement utilisés dans l'évaluation du corps de la fonction.
Exemple d'impératif : court-circuitage
Note : _|_ semble être un moyen de tester si une fonction est non stricte

Une fonction peut donc être non stricte mais pas paresseuse. Une fonction qui est paresseuse est toujours non stricte. Appel à la rescousse est partiellement défini par Appel par nom qui est en partie définie par Non-Strict

Un extrait de "Langages impératifs paresseux"

2.1. SÉMANTIQUE NON STRICTE VS. LAZY EVALUATION Nous devons tout d'abord clarifier la distinction entre "sémantique non stricte" et "évaluation paresseuse". La sémantique non stricte est celle qui spécifie qu'une expression n'est pas évaluée jusqu'à ce qu'elle soit nécessaire à une opération primitive. évaluée que lorsqu'elle est requise par une opération primitive. Il peut exister différents types de sémantique non stricte. Par exemple, la sémantique non stricte non strictes n'évaluent pas les arguments jusqu'à ce que leurs valeurs soient requises. nécessaires. Les constructeurs de données peuvent avoir une sémantique non stricte, dans laquelle les données composées sont assemblées à partir de morceaux non évalués L'évaluation paresseuse, également appelée évaluation différée, est la technique normalement utilisée pour pour implémenter la sémantique non stricte. Dans la section 4, les deux méthodes couramment utilisées pour implémenter l'évaluation paresseuse sont très brièvement résumées.

APPEL PAR VALEUR, APPEL PAR LAZY, ET APPEL PAR NOM "Appel par valeur" est le nom général utilisé pour les appels de procédure avec une sémantique stricte. nom général utilisé pour les appels de procédure avec une sémantique stricte. Dans les langues par valeur, chaque argument d'un appel de procédure est évalué avant l'appel de procédure. avant que l'appel de procédure ne soit effectué ; la valeur est ensuite transmise à la procédure ou à l'expression qui l'entoure. procédure ou à l'expression qui l'entoure. Un autre nom pour l'appel par valeur est l'évaluation "empressée". "L'appel par la valeur est également connu sous le nom d'évaluation par "ordre applicatif". L'appel par valeur est également connu sous le nom d'évaluation par ordre applicatif, car tous les arguments sont évalués avant que la fonction ne leur soit appliquée. Call by lazy" (selon la terminologie de William Clinger dans [8]). William Clinger dans [8]) est le nom donné aux appels de procédure qui utilisent une sémantique non stricte. Dans les langages avec des appels de procédure call by lazy, les arguments ne sont pas évalués avant d'être substitués dans le corps de la procédure. corps de la procédure. L'évaluation paresseuse est également connue sous le nom d'évaluation "normale". normal", en raison de l'ordre d'évaluation (de l'extérieur vers l'intérieur, de gauche à droite). de gauche à droite) de l'évaluation d'une expression. est une implémentation particulière de l'appel paresseux, utilisée dans Algol-60 [18]. Le site concepteurs d'Algol-60 voulaient que les paramètres d'appel par nom soient physiquement substitués dans le corps de la procédure, entourés de parenthèses parenthèses et avec des changements de nom appropriés pour éviter les conflits, avant que le corps ne soit évalué.

APPEL PAR PARESSEUX VS. APPEL PAR BESOIN L'appel par besoin est une extension de l'appel paresseux, motivée par l'observation qu'une évaluation paresseuse pourrait être optimisée en se souvenant de la valeur d'un paramètre donné. pourrait être optimisée en se souvenant de la valeur d'une expression retardée donnée. expression retardée donnée, une fois forcée, de sorte que la valeur n'a pas besoin d'être recalculée si elle est nécessaire. recalculée si elle est à nouveau nécessaire. L'appel par évaluation paresseuse, donc, étend l'appel par des méthodes paresseuses en utilisant la mémorisation pour éviter le besoin d'une évaluation répétée. Friedman et Wise étaient parmi les premiers défenseurs de l'appel par évaluation des besoins, proposant des "suspensions suicidaires" qui s'autodétruisent. qui s'autodétruisaient lors de leur première évaluation, en se remplaçant par leurs valeurs.

Answer 5

De la manière dont je le comprends, "non strict" signifie essayer de réduire la charge de travail en l'achèvement en une quantité de travail moindre.

Alors que l'"évaluation paresseuse" et les méthodes similaires tentent de réduire la charge de travail globale en éviter l'achèvement complet (espérons-le pour toujours).

à partir de vos exemples...

f1() || f2()

...le court-circuitage de cette expression n'aurait pas pour résultat de déclencher un "travail futur", et il n'y a pas de facteur spéculatif/amorti dans le raisonnement, ni de dette de complexité informatique accumulée.

Alors que dans l'exemple du C#, la "paresse" permet de conserver un appel de fonction dans la vue globale, mais en échange, elle s'accompagne des difficultés susmentionnées (au moins du point d'appel jusqu'à l'achèvement complet éventuel... dans ce code, il s'agit d'un chemin de distance négligeable, mais imaginez que ces fonctions doivent supporter des verrous à forte tension).

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);