Comparison of objects

*** Translation completed 7 Nov 2005
*** Will a French speaker please review to ensure that the
*** sense has been properly conveyed.

Comparing two objects

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

In Eiffel, as in most object-oriented languages, there are several ways to compare two objects, whether by comparing their respective addresses or by comparing 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 is not possible to compare just any type of expression with any other type of expression. The validity of a comparison will be explained in detail below.

Finally, just for completeness, this part will also discuss the possibility of carrying out a third sort of comparison, deep equality, a comparison reserved only 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

The = operator is the fundamental 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 in the compiler's internals.

When comparing two expressions of a reference type with the = or /= operators, as has already been mentioned above, only the two addresses are compared. Now let us 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 which we will go into later, a comparison is accepted only when the two expanded types are exactly the same. It is 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. In the latter case, it is up to the program's designer to make a call to the appropriate conversion routine. There are multiple possibilities, perhaps to convert the INTEGER expression into a CHARACTER, or, contrariwise, to convert the CHARACTER expression into an INTEGER. In both cases there are many possible conversion routines. 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 completely impossible to automate the choice of conversion that should be applied before the comparison. It depends entirely 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, to allow 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. That being said, 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, requiring two expanded types to be identical, 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 is 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 is not illogical, it is 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 more sophisticated comparison than using the predefined = operator. Consider once again our example of comparing two variables of type POINT, but this time let us use is_equal. As in the case above, let us 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 has not been redefined by the user, the behaviour of is_equal is to compare 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 is as if we had 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

See how the comparison between attributes does not use is_equal, but the basic 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 precisely, 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 us make it 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 is 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 is 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 diagram:

Both objects of class TRIANGLE in the diagram above are identical but if one proceeds to compare them using the predefined is_equal routine the result will be False! In fact, let us 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 is 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

It is very hard to imagine how a good function for comparison could be defined automatically. In particular, it is 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, since we do not know 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 class designer must ensure that the is_equal function behaves properly for objects of that class. The default behaviour described above has been chosen for its simplicity, because it is is for the most part suitable 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).

Comparison validity

Do not look for the definition of the = and /= comparison operators in the Eiffel classes' source code, because these two operators are predefined and their definition is deliberately fixed in the compiler's internals. Since one of the goals of the Eiffel language is to limit the possibility of careless errors, it would not be reasonable to allow just any comparison (that is, to allow all mixtures, like comparing a LORRY with a FLOWER, to take an extreme example). The static types of two expressions to be compared must conform to certain constraints. Of course -- and this is the usual case -- when the two expressions are of the same static type, the comparison is obviously allowed. It is always possible to compare two expressions with the same static type using the comparison operators = and /=.

As soon as the two expressioms are not of the same static type, they have to conform to the following general rule. A comparison of the form:

x = y

or again:

x /= y

is valid if it is possible to assign x to y or vice versa. More precisely, seeing that x and y are not necessarily variables, either the static type of x is acceptable for an assignment to the static type of y or else the static type of y is acceptable for an assignment to the static type of x.

The foregoing validity rule helps to check whether the program designer is writing a reasonable comparison. From experience, we have established that this rule, guided by common sense, is crucial for detecting upstream(?) errors, which are often careless mistakes.

In a few uncommon and often obscure cases, this rule can perhaps be found to be too restrictive. If you should find yourself in the situation where the compiler is rejecting your comparison but nevertheless you genuinely think that comparing the two expressions is desirable, you can achieve your ends by using two local variables with a more general static type (ultimately, you can use type ANY).

To conclude this section on the general verification rule for comparisons with the = and /= operators, let us remember that the rule just declared above also includes the previously mentioned case concerning the comparison of two expressions of type INTEGER_* or of type REAL_*. For example, it is possible to assign an expression of type INTEGER_16 to a variable of type INTEGER_32. A comparison between an expression of type INTEGER_16 and one of type INTEGER_32 is therefore valid.

Comparison using is_deep_equal, the fixed method

Just for the sake of completeness in this section on comparing objects, let us finally be aware that the ANY class offers the possibility of a deep comparison of two objects: the is_deep_equal function. The attributes of the two obects to be compared are themselves compared with the is_deep_equal function and so on recursively. This function recursively checks that the two objects are structurally identical. Note that it is sometimes possible to have an endless loop in the object graph(?), for example when comparing two linked lists with a circular structure. In order to be considered identical by is_deep_equal, it must be possible to superimpose the graph of the two objects.

The definition of the is_deep_equal function is fixed in the ANY class. The is_deep_equal function must be used with care because it depends entirely on the implementation of the objects which it is comparing. In fact, as a general rule, it is always preferable to avoid using the is_deep_equal function.