Comparaison trilatérale

En informatique, une comparaison trilatérale prend deux valeurs A et B appartenant à un type avec une relation d'ordre total et détermine si A < B, A = B ou A > B en une seule opération, conformément à la mathématique de la loi de trichotomie.

Calcul au niveau machine

De nombreux processeurs ont des jeux d'instructions qui supportent cette opération sur les types primitifs. Certaines machines ont des nombres entiers signés basés sur un complément à un (voir représentation des entiers négatifs), qui permettent de différencier un zéro positif et un zéro négatif. Cela ne viole pas la trichotomie tant qu'un ordre total consistant est adopté: les choix -0 = +0 et -0 < +0 sont tous deux valides. Les types à virgule flottante, cependant, ont une exception à la trichotomie: il y a une valeur spéciale "NaN" (Not a Number) telle que x < NaN, x > NaN, et x = NaN sont tous faux pour toutes les valeurs à virgule flottante x (y compris NaN lui-même).

Les langages de haut niveau

En C, les fonctions strcmp et memcmp effectuent une comparaison trilatérale entre les chaînes de caractères et les buffers mémoires, respectivement. Ils renvoient un nombre négatif quand le premier argument est plus petit que le second (d'un point de vue lexicographique), zéro lorsque les arguments sont égaux, et un nombre positif sinon. Cette convention de retourner le "signe de la différence" est arbitrairement étendue à des fonctions de comparaison par la fonction standard de tri qsort, qui prend une fonction de comparaison comme argument et l'utilise pour trier les éléments. C++20 ajoute le "spaceship operator" (littéralement l'opérateur vaisseau spatial) <=>, qui renvoie le signe de la différence et peut également renvoyer différents types (convertibles en entiers signés) en fonction du caractère strict ou non de la comparaison.

En Perl (pour les comparaisons numériques seulement,  cmp est utilisé pour les comparaisons lexicales de chaînes de caractères), PHP (depuis la version 7), Ruby, et Apache Groovy, le "spaceship operator" <=> renvoie les valeurs -1, 0 ou 1 selon que A < B, A = B ou A > B, respectivement. En Python 2.x (supprimé en 3.x), OCaml et Kotlin, les fonctions cmp, compare et compareTo calculent la même chose, respectivement. Dans la bibliothèque standard Haskell, la fonction de comparaison trilatérale compare est définie pour tous les types de la classe Ord; elle renvoie le type Ordering, dont les valeurs sont LT (moins que, pour Lesser Than), EQ (égal, pour EQual) et GT (plus que, pour Greater Than)[1]. De nombreux langages orientés objet ont une méthode de comparaison trilatérale, qui effectue une comparaison trilatérale entre l'objet et un autre objet donné. Par exemple, en Java, toute classe qui implémente l'interface Comparable a une méthode compareTo qui renvoie un entier négatif, zéro ou un nombre entier positif, ou lève une NullPointerException (si l'un ou les deux objets sont null). De même, dans le .NET Framework, toute classe qui implémente l'interface IComparable a une méthode CompareTo équivalente.

Depuis Java version 1.5, la même chose peut être calculée en utilisant la méthode statique Math.signum si la différence peut être connue sans problèmes de calcul tels que le dépassement d'entier mentionnés ci-dessous. De nombreux langages informatiques permettent la définition de fonctions pour qu'un compare(A,B) puisse être conçu de manière appropriée, mais la question est de savoir si sa définition interne reposera sur une syntaxe trilatérale ou sur des tests répétés.

Lors de la mise en œuvre d'une comparaison trilatérale lorsqu'un opérateur ou une méthode de comparaison trilatérale n'est pas déjà disponible, il est fréquent de combiner deux comparaisons, telles que A = B et A < B ou A < B et A > B. En principe, un compilateur peut en déduire que ces deux expressions pourraient être remplacées par une seule comparaison suivie par de multiples tests sur le résultat, mais la mention de cette optimisation ne semble pas exister dans les différents textes sur le sujet.

Dans certains cas, la comparaison trilatérale peut être simulée par la soustraction de A et B et en examinant le signe du résultat, en exploitant des instructions spéciales pour étudier le signe d'un nombre. Cependant, cela nécessite que le type de A et B dispose d'une différence bien définie. Les entiers signés à largeur fixe peuvent générer un overflow, les nombres à virgules flottantes peuvent être NaN avec un signe indéfini, et les chaînes de caractères n'ont aucune fonction de différence correspondant à leur ordre total. Au niveau machine, un overflow sera traqué et pourra être utilisé pour déterminer l'ordre après une soustraction, mais cette information n'est généralement pas disponible dans des langages de plus haut niveau.

Même si elle est aujourd'hui dépréciée, la déclaration arithmétique IF du Fortran fournissait une instruction conditionnelle trilatérale qui permettait de sauter à 3 labels selon le signe du résultat :La fonction strcmp en C (et langages apparentés) est une comparaison lexicographique trilatérale de chaînes de caractères. Cependant, ces langages manquent d'un opérateur générique de comparaison trilatérale.

Types de données composites

Les comparaisons trilatérales ont la particularité d'être faciles à composer et de construire des comparaisons lexicographiques de types non-primitifs, à la différence des comparaisons bilatérales.

Voici un exemple de composition en Perl. Notez que cmp, en Perl, est pour les chaînes de caractères, alors que => est pour les nombres. Les équivalents bilatéraux ont tendance à être moins compact, mais pas nécessairement moins lisible. L'exemple ci-dessus tire avantage de l'évaluation "Court-circuit" de l'opérateur || , et du fait que 0 est considérée comme faux en Perl. En conséquence, si la première comparaison donne "égal" (donc évaluée à 0), il va "traverser" la deuxième comparaison, et ainsi de suite, jusqu'à ce qu'il en trouve une qui est non-nul, ou jusqu'à ce qu'il atteigne la fin.

Dans certaines langues, y compris Python, Ruby, Haskell, etc., la comparaison des listes est faite de manière lexicographique, ce qui signifie qu'il est possible de construire une chaîne de comparaisons, comme dans l'exemple ci-dessus en mettant les valeurs dans des listes dans l'ordre voulu; par exemple, en Ruby:

Proposition pour le C++

Le 5 février 2017, Herb Sutter a proposé l'ajout d'un troisième opérateur de comparaison, appelé le "spaceship operator", à la norme C++ avec la syntaxe <=> , dans un article intitulé "Consistent Comparison"[2].

Il a été fusionné dans le projet C++20 en novembre 2017.

Trivia

L'opérateur de comparaison pour les nombres est orthographié <=> en Perl, Ruby, Apache Groovy, PHP et Eclipse Ceylon, et est appelé le spaceship operator[3] parce qu'il a rappelé à Randal L. Schwartz un vaisseau spatial dans un jeu HP BASIC de Star Trek[4]. un autre codeur a suggéré qu'il était nommé ainsi parce qu'il semblait similaire au TIE fighter de Dark Vador dans la saga Star Wars[5].

Voir aussi

• strcmp

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Three-way comparison » (voir la liste des auteurs).

1. Data.Ord
2. Consistent Comparison
3. « Math::Complex », sur Perl Programming Documentation (consulté le 26 septembre 2014)
4. « Spaceship history (was Re: [dart-misc] DEP meeting notes) »
5. « Super Spaceship Operator », 8 décembre 2000 (consulté le 6 août 2014)