Comparison of objects

*** 
*** Please if you read French, translate the corresponding page using the French version as a model.
*** If you decide to translate this page, start to add here a *** note in order to avoid multiple
*** translators.
*** Please, check also our Author guidelines first !
*** Thanks in advance.
*** Colnet 11:59, 6 Sep 2005 (CEST)
***
*** Well, I've made a small start, but others are welcome (as far as I'm concerned) to contribute.
*** I'm having fun translating it, but this could take some days!
*** Peter Gummer 6 Sep 2005
***
*** I've done the next section.  I will flag up here before starting on another one.
*** Oliver Elphick, 7 Sep 2005
***
*** Thank you all for the great work. Colnet 09:41, 7 Sep 2005 (CEST)
***
*** Still not finished, but getting close!
*** Peter Gummer 12 Sep 2005
*** 
*** Embarking on the last bits 
*** Oliver Elphick 7 Nov 2005

Comparing two objects

How to compare two objects is a problem that has to be mastered fairly quickly, for it's a very common problem posed in many applications, if not almost all applications.

In Eiffel, as in most object-oriented languages, there are several ways to compare two objects, be it to compare their respective addresses or be it to compare the information contained in each of the two objects. In other words, using Eiffel terminology, one must choose whether to use the predefined = operator or the redefinable is_equal routine.

Because the Eiffel language aims, as far as possible, to prevent careless mistakes, it isn't possible to compare any type of expression with any other type of expression. The validity of a comparison will be detailed below.

Finally, just to be complete, this part will also discuss the possibility of carrying out a third sort of comparison, deep equality, a comparison uniquely reserved for a very rare family of applications.

Comparison using the operators = or /=

Let there be two variables point_a and point_b both of type POINT. Let us suppose that these two variables have been initialised with something other than Void. The following code fragment shows a possible usage of the predefined = comparison operator:

if point_a = point_b then
   io.put_string("We have a single, unique POINT !")
else
   io.put_string("We have two POINTs at different memory locations.")
end

Comparison using the = operator is the most basic building block for comparison. In the case of a reference type, it corresponds simply to the direct comparison of the two addresses. What the two addresses point to is not considered. If our two variables point_a and point_b actually designate a single, unique POINT in memory, then the test above evaluates to true. Once there are two distinct POINTs in memory, then the test is false even if the two POINTs seem exactly identical, in the debugger for example, or when printed.

Note that we also have the /= operator, which corresponds to the negation of the = operator. The /= operator is also predefined and is simply a shortcut to avoid having to use not for negation. So to test whether a reference variable refers to an object, the usage is:

if point /= Void then
   io.put_string("The variable point refers to a POINT!")
else
   io.put_string("The variable point does not refer to any object.")
end

When comparing variables of an expanded type, the effect of the = and /= operators is simply to compare the values in question. For two variables of type INTEGER, that boils down to comparing the two numbers:

if integer_a = integer_b then
   io.put_string("integer_a is the same value as integer_b!")
else
   io.put_string("The two values are different.")
end

The essential details about the = and /= predefined operators have now been clearly explained above, at least, so we hope. If you are reading this to find out about comparison methods, go straight to the section on is_equal. Otherwise, continue to the next section for additional information about these two predefined operators.

The = and /= operators with expanded types

The = and /= operators, apart from being predefined, are non-redefinable operators. The effect of = and /= is completely fixed, within the compiler.

When comparing two expressions of a reference type with the = or /= operators, as has already been mentioned above, only the two addresses are compared. Let's see what happens when the two compared expressions are of an expanded type.

Comparing two expanded expressions using = simply comes down to comparing, at the lowest level, bit by bit, the two areas of memory corresponding to the two objects. Of course, the expanded type used on the left of the = operator must be compatible with the expanded type used on the right. Indeed, apart from some rare exceptions that we'll detail later, a comparison is accepted only when the two expanded types are exactly the same. It's obviously possible to compare two expressions of type CHARACTER with each other; and, for example, to compare two expressions of type INTEGER with each other. In order to avoid any careless mistakes, however, directly comparing a CHARACTER with an INTEGER is forbidden. Note that in the latter case, it's up to the program's designer to make a call to the appropriate conversion routine. There are multiple possibilities, be it to convert the INTEGER expression into a CHARACTER, or be it, inversely, to convert the CHARACTER expression into an INTEGER. In both cases the possible conversion routines are themselves numerous. Several routines exist, for example, to convert from CHARACTER to INTEGER. Here are two such examples, among many others:

if my_character.to_integer = my_integer then
   io.put_string("Conversion with possible sign extension.")
end

and again:

if my_character.decimal_value = my_integer then
    io.put_string("Conversion using the value of the corresponding number.")
end

Thus, it seems that it's absolutely not possible to automate the choice of conversion that ought to be applied before the comparison. It depends completely on the context of the comparison, on the problem being dealt with, and this choice must be made manually by the program's designer. The strict rule, consisting of allowing the comparison of two expanded objects only when they have exactly the same type, is indeed the simplest and safest. Thus, if the compiler rejects your comparison expression, read the error message carefully and choose the most appropriate conversion with care. Having said this, two exceptions to this very strict rule remain, probably for historical reasons.

The two exceptions concern two special cases that leave no doubt thanks to the fact that the expanded objects concerned are very elementary. The first exception to the strict rule of the identity of two expanded types concerns the case of two objects taken from the set {INTEGER_8, INTEGER_16, INTEGER_32, INTEGER, INTEGER_64}. Comparison using = is true if and only if the two values correspond to exactly the same integer value. In fact, without any loss of information, it is always possible to represent in 16 bits any number that is represented in 8 bits; and so on and so forth. This exception to the hard and fast rule therefore lets us write simply and without risk:

if my_integer_8 = my_integer_16 then ...

knowing that it's as if we had written:

if my_integer_8.to_integer_16 = my_integer_16 then ...

The second and last exception is similar to the preceding one and concerns the following set of expanded types: {REAL_32, REAL_64, REAL, REAL_80, REAL_128, REAL_EXTENDED}. Like the integers, for the set of floating point numbers in question, it is always possible to convert a given floating point number to a bigger number of bits without any loss of information. Thus, a comparison expression using = or /= can mix two types taken from the REAL_* family.

Note, finally, that it is forbidden to compare directly any object from the REAL_* family with any object from the INTEGER_* family. If you find yourself having to make such a comparison, which isn't illogical, it's up to you to decide which conversion routine is appropriate to your needs. The Eiffel language has no rule that could decide this for you.

The redefinable is_equal routine

The redefinable is_equal routine provides a less elementary comparison than using the predefined = operator. Consider once again our example of comparing two variables of type POINT, but this time let's use is_equal. Like the above case, let's suppose for the moment that the two variables point_a and point_b are initialised with something other than Void:

if point_a.is_equal(point_b) then
   io.put_string("Either they are both the same POINT or else they are 2 identical POINTs.")
else
   io.put_string("They are two different POINTs.")
end

In a given class, if the is_equal routine hasn't been redefined by the user, the behaviour of is_equal consists of comparing all attributes of the two objects with each other. That means, for the POINT example, successively comparing the two x attributes and then the two y attributes. In other words, it's as if we'd written:

if (point_a.x = point_b.x) and (point_a.y = point_b.y) then
   io.put_string("Either they are both the same POINT or else they are 2 identical POINTs.")
else
   io.put_string("They are two different POINTs.")
end

Note how the comparison between attributes does not use is_equal, but the elementary fixed = operator. The following diagram presents a picture of the possible memory contents during comparison of point_a and point_b. Note that in the following case, these two POINTs situated in two memory locations are identical and, consequently, comparison using is_equal will return True:

In the example above, the two objects that are being compared are both instances of the POINT class: very simple objects. As the diagram shows, a POINT is composed of two expanded attributes, or, more exactly, the attributes x and y of type REAL, a primitive expanded type (i.e. without an intermediate pointer). In this case the default definition of the is_equal function fits perfectly.

Before describing is_equal any further, let's be clear that is_equal can be used when the type of the two compared objects is expanded. For example, with INTEGERs, the result of a comparison using the predefined = operator has exactly the same effect as using the is_equal routine. Note however that using is_equal is quite unusual when the two operands are expanded, especially if it's a basic expanded type like INTEGER, CHARACTER, REAL or BOOLEAN. In general, by convention and especially for the sake of simplicity, = and /= are preferred for primitive expanded types.

As soon as the objects are more complex, with for example some attributes that themselves point towards other objects, it's necessary to pay attention to the predefined behaviour of the is_equal function. Consider for example the case of comparing two TRIANGLEs, as in the following figure:

Both objects of class TRIANGLE in the figure above are identical but if one procedes to compare them using the predefined is_equal routine the result will be False! In fact, let's emphasise that triangle_a and triangle_b designate, even if they are similar, two distinct objects in memory. Indeed, if the is_equal function has not been redefined in the TRIANGLE class, the comparison of triangle_a and triangle_b using is_equal, in other words the expression:

triangle_a.is_equal(triangle_b)

is equivalent to the expression:

(triangle_a.p1 = triangle_b.p1) and (triangle_a.p2 = triangle_b.p2) and (triangle_a.p3 = triangle_b.p3)

The expression above corresponds to the predefined behaviour of is_equal. In order to obtain a more useful comparison function, it's up to the designer of the TRIANGLE class to think of how to alter the predefined definition by redefining TRIANGLE's is_equal function like this:

is_equal (other: TRIANGLE): BOOLEAN is
   do
      Result := p1.is_equal(other.p1) and p2.is_equal(other.p2) and p3.is_equal(other.p3)
   end

Note that it's very hard to imagine how a good function for comparison could be defined automatically. In particular, it's not always enough to call is_equal again on the attributes, as in the TRIANGLE case, rather than using =. (To convince youself of this, see the STRING and ARRAY classes as examples.) Thus, without knowing how to automate this task with a language rule or by adding a strong dose of intelligence to the compiler, the job belongs solely to the designer of the class. The conscientious designer of a class must take care of the good behaviour of the is_equal function for objects of that class. The default behaviour described above has been chosen for its simplicity, because it suits often enough as a good comparison function and also because it is implemented easily in low level machine instructions that are very fast (comparison instructions for two memory blocks).

Validité des comparaisons

Ne cherchez pas la définition des opérateurs de comparaison = et /= dans le code source Eiffel des classes car ces deux opérateurs sont prédéfinis et leur définition est volontairement figée à l'intérieur même du compilateur. Un des buts du langage Eiffel consistant à limiter les erreurs d'inattention, il ne serait pas raisonnable d'autoriser n'importe quelle comparaison (i.e. d'autoriser tous les mélanges comme par exemple la comparaison d'un CAMION avec une FLEUR pour prendre un cas extrême). Les types statiques des deux expressions que l'on compare doivent respecter certaines contraintes. Bien entendu, et c'est le cas le plus commun, quand les deux expressions sont de même type statique, la comparaison est évidemment autorisée. Il est toujours possible de comparer deux expressions ayant le même type statique à l'aide des opérateurs de comparaison = et /=.

Dès que les deux expressions ne sont pas de même type statique, il faut respecter la règle générale suivante. Une comparaison de la forme :

x = y

ou encore :

x /= y

est valide s'il est possible de faire une affectation dans le sens x vers y ou bien, s'il est possible de faire une affectation dans le sens y vers x. Plus exactement, car x et y ne sont pas forcément des variables, soit le type statique de x est acceptable pour une affectation vers le type statique de y soit le type statique de y est acceptable pour une affectation vers le type statique de x.

La règle de validité précédente contribue à vérifier que le concepteur du programme effectue bien une comparaison raisonable. Par l'expérience, nous avons constaté que cette règle guidée par le bon sens est cruciale pour la détection en amont d'erreurs qui sont souvent des erreurs d'inattention.

Dans quelques cas rares et souvent obscures cette règle peut être jugée trop contraignante. Si d'aventure vous vous trouvez face à une situation ou le compilateur rejette votre comparaison mais que vous pensez vraiment qu'il est souhaitable de comparer malgré tout les deux expressions vous pourrez facilement arrivez à vos fins en utilisant deux variables locales dont le type statique est plus général (utilisez éventuellement pour cela le type ANY).

Pour terminer sur cette règle générale de vérification des comparaisons avec les opérateurs = et /=, notons que la règle qui vient d'être énoncée englobe aussi le cas évoqué précédemment qui concerne la comparaison des expressions de type INTEGER_* ou REAL_*. En effet, il est par exemple possible d'affecter une expression de type INTEGER_16 dans une variable de type INTEGER_32. La comparaison entre une expression de type INTEGER_16 avec une expression de type INTEGER_32 est donc valide.

Comparaison avec is_deep_equal, la méthode figée

Seulement pour être exhaustif dans cette partie consacrée à la comparaison d'objets, signalons enfin que la classe ANY offre une possibilité de comparaison en profondeur de deux objets : la fonction is_deep_equal. Les attributs des deux objets à comparer sont eux mêmes comparés deux à deux avec la fonction is_deep_equal et ainsi de suite récursivement. Cette fonction compare récursivement que les deux objets sont structurellement identiques. Notons qu'une circularité dans le graphe des objets est parfois possible comme par exemple dans le cas de la comparaison de deux listes chaînées structurellement circulaires. Pour être considérés identiques au sens is_deep_equal, le graphe des deux objets à comparer doit être superposable.

La définition de la fonction is_deep_equal est figée (frozen) dans la classe ANY. La fonction is_deep_equal doit être utilisée avec précautions car elle dépend totalement de l'implantation des objets qu'elle compare. En fait, abstraction oblige, il est toujours préférable de ne pas utiliser la fonction is_deep_equal.