# How can mainstream OO languages support strong binary operations by classes?

Section 24.2 in Types and Programming Languages by Pierce compares ADT and existential objects,in terms of how well they support strong 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 eﬃcient implementation of the union operation on two sets will need to view both of them concretely, as trees. However, we do not want 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 operations strong binary operations.

and says strong binary operations can't be expressed as methods of existential objects:

Strong binary operations, on the other hand, cannot be expressed as methods of objects in our model. We can express their types just as we did for weak binary methods above:

NatSet = {∃X, {state:X, methods: {empty:X, singleton:Nat→X,
member:X→Nat→Bool,
union:X→NatSet→X}}}


. 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 ﬁnd out what its elements are so that we can compute the union.

but then says that mainstream OO languages provide support for strong binary operations by classes (instances of which are supposedly existential objects):

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 deﬁned 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 deﬁned by C. This permits strong binary operations such as set union to be deﬁned as methods.

When a method in a class has an argument which is another object of the same class, how can the method "concretely access the instance variables" of the other object?

Does the book assume that the class makes the instance variables only privately accessible, and doesn't provide public accessible methods to access the instance variables? (I guess yes, because it seems to me that the third quote has the same situation as the second quote where it be impossible for union method on existential objects.)

Thanks.

• Do you have experience with C++/Java? – Yuval Filmus Sep 4 '19 at 21:24
• Methods can access private instance variables. – Yuval Filmus Sep 4 '19 at 21:24
• It just can. The rules of the language allow it. – Yuval Filmus Sep 4 '19 at 21:33
• Perhaps you should study a mainstream OO language such as C++ or Java. – Yuval Filmus Sep 4 '19 at 21:34
• Monographs like TAPL are not written like poetry or like legal texts. They are trying to convey a general message, but don't pay attention to each and every word in each and every sentence. – Yuval Filmus Sep 5 '19 at 11:47

I will attempt an answer, though, the discussion in comments with @yuval-filmus seems to be going in the right way.

Let's recap: The book discusses ADTs against objects in their strictest sense.

ADTs are entirely public about their unique representation. Belonging in the ADT means satisfying said representation, and so binary methods can rightfully assume that both operands have that exact representation.

Objects are entirely opaque about their non-unique representation. Belonging in the object type means satisfying its interface, with no guarantees as to how this is achieved internally, and so binary methods may only assume that the two objects can respond to the same set of messages, but are quite possibly implemented entirely differently.

Even if the interface has a getter getFoo, that is no guarantee that the object has a foo field that you could poke at directly. Maybe some mock object is faking it with a method that returns a constant Foo. All you know as a client is that it supports a getFoo call.

Where the class-based object approach differs from the pure object approach is that the knowledge of the type of an object (the class it belongs to) gives you some guarantees about the structure of the object, and so, allows you to partially break the abstraction barrier. Because all objects of a class must have been built with, at least, a call to the constructor of that class, you can guarantee the presence of some fields (initialized during that constructor), and so the language lets you access those directly, foregoing the mandatory message-passing of the pure object style.

This is a strength and a weakness:

• because you have access to the concrete representation, you might be able to implement operations more efficiently,

• but because you ask for a member of the class, a "mock" implementation is no longer a valid object for this operation: if you want to allow such an object, you must define an interface, and you are effectively back to a pure-object approach.

As in my other answer to one of your question, this paper is extremely relevant:

http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf "On Understanding Data Abstraction, Revisited", by William R. Cook

Of particular interest are section 3.3 on autognosis, which hints at why binary methods in the ADT style are strong, whereas in the object style are weak, and section 5 which explains a bit the difference between what is considered a pure object approach and the more general objects available in Java. (You can program in the pure object style in Java, but you have to follow a given discipline about not breaking certain abstraction boundaries, which relates to the discussion you've had in the comments)

I hope this makes sense, I'm sorry you had trouble with my other answer, this is a hard topic to get your head around, but once you have fixed your misunderstandings you will see it is not that complex!

• Thanks. I am slowly understanding your replies. Meanwhile, thanks again if you could also consider cs.stackexchange.com/questions/113618/… – Tim Sep 10 '19 at 20:57
• Thanks. "Because all objects of a class must have been built with, at least, a call to the constructor of that class, you can guarantee the presence of some fields (initialized during that constructor), and so the language lets you access those directly, foregoing the mandatory message-passing of the pure object style." In such case, when a strong operator takes another object in the same class as an argument, and wants to access the private fields of the object, does the operator not need a public method? Could you give some example in Java? – Tim Sep 12 '19 at 9:16
• paste.awesom.eu/eloz&ln In this code, a method of some class Doggo receives as argument another object of the same class Doggo, and is allowed to access the private field booped. This is against the pure object approach ideology, where one should instead use the getter/setter methods. But it is considered "fair", because the object is from the very same class, so the type system allows you to see the actual implementation, possibly allowing you to do more than just through the public interface. – Ptival Sep 12 '19 at 16:35