J'apprends le C ++ en lisant les "Principes et pratiques d'utilisation du C ++" de Stroustrup.

Dans la section sur les pré- et post-conditions, il y a l'exemple de fonction suivant:

int area(int length, int width)
// calculate area of a rectangle;
// pre-conditions: length and width are positive
// post-condition: returns a positive value that is the area
{
    if (length<=0 || width <=0) 
        error("area() pre-condition");

    int a = length*width;

    if (a<=0) 
        error("area() post-condition");

    return a;
}

Ce qui m'a dérouté, c'est la tâche concernant ce code:

Trouvez une paire de valeurs pour que la condition préalable de cette version de area soit maintenue, mais pas la post-condition.

Existe-t-il de telles valeurs possibles pour les entiers que les pré-conditions sont correctes mais pas les post-conditions?

19
Pavel_K 31 déc. 2015 à 14:01

9 réponses

Meilleure réponse

Existe-t-il de telles valeurs possibles pour les entiers que les pré-conditions sont correctes mais pas les post-conditions?

Oui, il existe un certain nombre de valeurs d'entrée qui peuvent entraîner l'échec de la condition de publication. Si par exemple

int a = length*width;

Dépasse la plage positive int (std::numeric_limits<int>::max()) et l'implémentation du compilateur donne une valeur négative pour ce cas.


Comme d'autres l'ont noté dans leurs réponses, la situation dans laquelle length*width sort des limites de ]0-std::numeric_limits<int>::max()[ est en fait un comportement indéfini, et la post-condition devient simplement inutile, car toute valeur doit être attendue pour {{X2 }}.

Le point clé pour résoudre ce problème est donné dans @Deduplicator answer, la condition préalable doit être améliorée.


En guise de lance aux raisonnements de Bjarne Stroustrup pour donner cet exemple:

Je suppose qu'il voulait souligner qu'un tel comportement indéfini pourrait conduire à des valeurs négatives inattendues dans la post-condition et des résultats surprenants pour une hypothèse naïve vérifiée avec la pré-condition.

33
Community 23 mai 2017 à 12:24

Non, il n'y a aucune valeur qui, dans les limites du comportement défini du C ++ standard, violera la post-condition. Cependant, il existe des valeurs qui peuvent encore faire en sorte que la fonction se comporte de manière incorrecte, à savoir des valeurs si grandes que leur produit ne rentre pas dans un entier. Essayez de passer 200'000 et 15'000.

En raison de la façon dont la plupart des compilateurs implémentent C ++, vous pouvez voir la post-condition violée, mais ce que vous observez réellement est un comportement indéfini en raison d'un dépassement d'entier.

27
Sebastian Redl 1 janv. 2016 à 17:16

La réponse est que son contrôle préalable est incomplet. Même si c'est trop restrictif.
Il n'a pas inclus de vérification que le produit peut être représenté au lieu de donner lieu à UB:

int area(int length, int width) {
    // calculate area of a rectangle
    assert(length >= 0 && width >= 0 && (!width
        || std::numeric_limits<int>::max() / width >= length));
    int a = length * width;
    assert(a >= 0); // Not strictly neccessary - the math is easy enough
    return a;
}
12
Deduplicator 1 janv. 2016 à 17:41

Ce qui me vient à l'esprit, c'est un débordement signé. Il s’agit d’un comportement non défini, mais peut donner une valeur négative.
Essayez std::numeric_limits<int>::max() et 2.

5
cadaniluk 31 déc. 2015 à 11:04

Oui si supposons que vous utilisez un ordinateur 16 bits donc int = 2B Valeur maximale +32767 donc dans la suite

{
    length = 500, width = 100;
    if (length<=0 || width <=0) error("area() pre-condition");
    int a = length*width;   // a = 500 * 100 = 50000
    if (a<=0) error("area() post-condition");
    return a;
}

Maintenant la valeur finale sera a = -17233 car elle entre dans la valeur -ve. donc la deuxième condition devient fausse.

Tout dépend de la portée.

4
Kamaldeep singh Bhatia 31 déc. 2015 à 12:06

INT_MAX ne remplira pas la post-condition lorsqu'il est utilisé à la fois pour la longueur et la largeur pour tous les compilateurs conformes.

On pourrait être tenté de dire que, puisque la norme garantit que INT_MAX & gt; = 32767, alors INT_MAX*INT_MAX sera toujours supérieur à INT_MAX et donc non représentable dans un int qui est défini comme pouvant contenir une valeur maximale de INT_MAX.
C'est un bon argument et c'est en fait ce qui arrive le plus souvent, vous obtiendrez un débordement avec la plupart des compilateurs.

Mais pour couvrir toutes les bases, nous devons être conscients que le C ++ la norme déclare:

3.4.3
1 comportement non défini
comportement, lors de l'utilisation d'une construction de programme non portable ou erronée ou de données erronées, pour lequel la présente Norme internationale n'impose aucune exigence

2 REMARQUE Les comportements indéfinis possibles vont de l'ignorance totale de la situation avec des résultats imprévisibles, au comportement pendant la traduction ou l'exécution du programme d'une manière documentée caractéristique de l'environnement (avec ou sans émission d'un message de diagnostic), à l'arrêt d'une traduction ou d'une exécution (avec l'émission d'un message de diagnostic).

3 EXEMPLE Un exemple de comportement indéfini est le comportement en cas de dépassement d'entier.

C'est donc un peu plus sérieux que de ne pas avoir la bonne valeur pour la zone. Lorsque INT_MAX est utilisé à la fois pour la longueur et la largeur (ou pour toute autre combinaison avec un résultat qui n'est pas représentable), il n'y a aucune garantie de ce que le programme compilé fera. Tout peut arriver; des probables comme les débordements ou plantages aux improbables comme les formats de disque.

3
Anonymous Coward 31 déc. 2015 à 17:10

La multiplication des valeurs qui dépassent la représentation binaire du type valeur n'est pas définie car le nombre de bits débordés peut être supérieur à 1. Ainsi, vous pourriez vous retrouver avec un bit de signe positif ou négatif et le nombre de bits perdus est variable.

Exemple 1: INT_MAX * 2: le résultat est correct mais puisque le bit haut représente le bit de signe il n'est pas corrigé représenté pour son type.

Exemple 2: INT_MAX * 4: 1 bit est perdu en cas de débordement et le bit de signe est incorrect comme dans l'exemple précédent.

Exemple 3: (INT_MAX + 1) * 2 = 0: en raison d'un débordement de tous les bits définis mais le signe est correct.

J'utilise une représentation binaire 8 bits pour faciliter la lecture, pour montrer pourquoi cela se produit.

0111 1111              // Max positive signed value
+1
1000 0000              // Sign bit set but binary value is correct
*2
0000 0000              // Upper bit is lost due to overflow

Dans ce cas, il y a à la fois débordement progressif, aucune information perdue mais la représentation est incorrecte. Et hard overflow où le bit n'est plus présent dans le résultat.

La différence entre les débordements est la façon dont le débordement peut être détecté. En règle générale, les débordements importants sont détectés par le matériel et nécessitent très peu de travail pour le logiciel. Cependant, les débordements logiciels peuvent obliger le logiciel à tester explicitement la condition de débordement car le matériel ne reconnaît généralement pas un bit de signe dans les opérations mathématiques entières.

La façon dont la bibliothèque d'exécution gère le débordement dépend de la bibliothèque. La plupart l'ignoreront car il est plus rapide de le faire, tandis que d'autres peuvent générer une erreur. Un comportement non défini ne signifie pas qu'il pourrait formater votre disque. Le résultat d'une opération mathématique ne modifie en aucune façon le flux de code, sauf si la logique du code l'exige. Il peut ignorer le débordement ou essayer de le gérer d'une manière ou d'une autre. La norme ne dicte pas la méthode à utiliser si le code ou le matériel tente de gérer le problème.

En gros trois, il y a trois choses possibles qui peuvent arriver.
1. Le débordement est ignoré et la valeur renvoyée est invalide.
2. Le débordement est ignoré par la bibliothèque d'exécution, mais le matériel renvoie une erreur qui est également ignorée, entraînant une défaillance matérielle du code en cours d'exécution. Dans cette situation, il appartient entièrement au système d'exploitation de déterminer ce qui se passe ensuite. Faire des folies et détruire des données serait une mauvaise décision de conception.
3. Le débordement est géré par la bibliothèque d'exécution qui doit déterminer la meilleure façon de procéder. En règle générale, cela signifie donner au code une chance d'attraper l'erreur et de la gérer, ou en fermant le code aussi gracieusement que possible.

3
Mykola 31 déc. 2015 à 23:32

Depuis C ++ 11, il existe une valeur booléenne que vous pouvez tester:

std::numeric_limits<int>::is_modulo

Si cette valeur est true, alors l'arithmétique signée se comporte de manière enveloppante et il n'y a pas de comportement indéfini dans le code d'origine. Une valeur négative pourrait en effet être produite et donc le test dans le code d'origine est significatif.

Pour plus d'informations sur is_modulo cliquez ici

3
Community 23 mai 2017 à 12:00

Donc, fondamentalement, les valeurs positives lors de la multiplication ... aboutissent à des valeurs positives mais celles-ci peuvent ne pas correspondre au type de résultat .

Votre condition préalable n'est pas complète et votre postcondition est également invalide. Non seulement vous pouvez obtenir des valeurs négatives mais aussi des valeurs positives qui sont juste plus petites que la valeur d'entrée, tout ce dont vous avez besoin est des valeurs suffisamment grandes comme entrée pour que le bouclage dépasse zéro, c'est-à-dire un long-wrap-around .

Vous pouvez utiliser ceci:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

Pour se prémunir contre les débordements, mais vous voudrez alors utiliser des vérifications supplémentaires pour les FAUX-positifs.

Sinon, si les performances ne posent pas vraiment problème, vous pouvez utiliser la bibliothèque MPZ. Si les performances sont un problème et que vous souhaitez écrire un assembly pour un processeur doté d'un indicateur de dépassement de capacité, vous pouvez le faire. Il est possible que votre compilateur puisse également effectuer les vérifications pour vous, par exemple G ++ a fno-strict-overflow ou peut-être casté en unsigned int après la vérification des conditions préalables.

Dans tous les cas, la plupart de ces solutions ne résolvent pas réellement votre problème: les résultats seront foo , c'est-à-dire que vous pourriez obtenir une zone plus petite que le résultat réel.

Donc, votre seul choix sûr est de n'autoriser que les multiplications sûres comme indiqué ici, en faisant cela vous manquez quelque chose, mais pas tant que ça.

0
Community 23 mai 2017 à 12:00