# The single representations adts directly support binary operations

Some binary operations can be implemented entirely in terms of the publicly available operations on two abstract values. For example, to implement an equality operation for counters, all we need to do is ask each for its current value (using get) and compare the two numbers that we get back-i.e., the equal operation can just as well live outside the abstraction boundary that protects the concrete representation of counters. We call such operations

weak binary operations.Other binary operations cannot be implemented without concrete, privileged access to the

representations of both abstract values. For example, suppose we are implementing an abstraction representing sets of numbers. After scouring several algorithms textbooks, we choose a concrete representation of sets as labeled trees obeying some particular complex invariant. An efficient implementation of the union operation on two sets will need to view both of them concretely, as trees. However, we donotwant to expose this concrete representation anywhere in the public interface to our set abstraction. So we will need to arrange for union to have privileged access to both of its arguments that is not available to ordinary client code-i.e., the union operation must live inside the abstraction boundary. We call such operationsstrong binary operations.

But there is no satisfactory way to *implement* an object of
this type: all we know about the second argument of the union operation
is that it provides the operations of NatSet, but these do not give us
any way to find out what its elements are so that we can compute the
union.

24.2.5 Exercise [?]

One caveat should be added to this discussion. These comparisons
apply to the simple, "purist" model of objects presented earlier in the
chapter. The classes in mainstream object-oriented languages like C++
and Java *are* designed to allow some forms of strong binary
methods, and are actually best described as a kind of compromise between
the pure objects and pure ADTs that we have seen in this chapter. In
these languages, the type of an object is exactly the name of the class
from which it was instantiated, and this type is considered distinct
from the names of other classes, even if they provide exactly the same
operations (cf. __§19.3__). That is, a given object type in these
languages has a *single* implementation given by the
corresponding class declaration. Moreover, subclasses in these languages
can add instance variables only to those inherited from superclasses.
These constraints mean that every object belonging to type C is
guaranteed to have all the instance variables defined by the (unique)
declaration of class C (and possibly

some more). It now makes sense for a method of such an object to take another C as an argument and concretely access its instance variables, as long as it uses only instance variables defined by C. This permits strong binary operations such as set union to be defined as methods. "Hybrid" object models of this sort have been formalized by

Pierce and Turner (1993)andKatiyar et al. (1994), and elaborated in more detail by Fisher and Mitchell (Fisher andMitchell, 1996,1998;Fisher, 1996b,a).

< Free Open Study > |