First, let's look at what "object-oriented" actually means.
The very first object-oriented programming language was Simula (1960). As the name implies, it was designed for simulations. If you want to be able to simulate objects in a way that they are indistinguishable from the real thing, one important requirement is that you can only observe the externally visible behavior. If you were able to observe its internal behavior, or its internal representation, you would be able to distinguish between the simulation and the simulatee, which is what we want to avoid.
Hence, data abstraction and encapsulation are fundamental to OO. And not any kind of data abstraction, we are talking specifically about procedural or behavioral abstraction. This is different from the kind of abstraction Abstract Data Types use. (See for example On Understanding Data Abstraction, Revisited by William R. Cook for a simple explanation)
The person who coined the term "Object-Oriented" is Alan Kay, the designer of Smalltalk (among many other things). He has defined OO like this:
OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.
He later on clarified that "The big idea is 'messaging'", and regrets having called it "object-oriented" instead of "message-oriented", because the term "object-oriented" puts the focus on the unimportant thing (objects) and distracts from what is really important (messaging):
Just a gentle reminder that I took some pains at the last OOPSLA to try to remind everyone that Smalltalk is not only NOT its syntax or the class library, it is not even about classes. I'm sorry that I long ago coined the term "objects" for this topic because it gets many people to focus on the lesser idea.
The big idea is "messaging" -- that is what the kernal of Smalltalk/Squeak is all about (and it's something that was never quite completed in our Xerox PARC phase). The Japanese have a small word -- ma -- for "that which is in between" -- perhaps the nearest English equivalent is "interstitial". The key in making great and growable systems is much more to design how its modules communicate rather than what their internal properties and behaviors should be. Think of the internet -- to live, it (a) has to allow many different kinds of ideas and realizations that are beyond any single standard and (b) to allow varying degrees of safe interoperability between these ideas.
Messaging is fundamental to OO, both as metaphor and as a mechanism.
If you send someone a message, you don't know what they do with it. The only thing you can observe, is their response. You don't know whether they processed the message themselves (i.e. if the object has a method), if they forwarded the message to someone else (delegation / proxying), if they even understood it. That's what encapsulation is all about, that's what OO is all about. You cannot even distinguish a proxy from the real thing, as long as it responds how you expect it to.
Alan Kay designed Smalltalk right around the time that modern networking also was invented. He worked at Xerox PARC, where the Ethernet was invented, and he knew some of the people who were just in the process of inventing what would later become the ARPANet and then the Internet. He envisioned objects as tiny little computers in their own right, with their own memory (instance variables), private code (methods), and the only way to speak to them is by sending them a message (just like you can't read another computer's memory on the Internet or execute its code, but you can send it a message):
In computer terms, Smalltalk is a recursion on the notion of computer itself. Instead of dividing "computer stuff" into things each less strong than the whole—like data structures, procedures, and functions which are the usual paraphernalia of programming languages—each Smalltalk object is a recursion on the entire possibilities of the computer. Thus its semantics are a bit like having thousands and thousands of computers all hooked together by a very fast network. Questions of concrete representation can thus be postponed almost indefinitely because we are mainly concerned that the computers behave appropriately, and are interested in particular strategies only if the results are off or come back too slowly.
—The Early History Of Smalltalk, Alan Kay
The above-mentioned William Cook has surveyed many programming languages that people agree are object-oriented, and many programming language that people agree are not object-oriented and has worked on distilling what, precisely, it is that languages that are commonly called "object-oriented" have in common and what distinguishes them from languages that are commonly agreed to be not object-oriented. And he has distilled his findings into a Proposal for Simplified, Modern Definitions of "Object" and "Object Oriented":
Dynamic dispatch of operations is the essential characteristic of objects. It means that the operation to be invoked is a dynamic property of the object itself. Operations cannot be identified statically, and there is no way in general to exactly what operation will executed in response to a given request, except by running it. This is exactly the same as with first-class functions, which are always dynamically dispatched.
Note that the last sentence is very interesting. In fact, William Cook has somewhat jokingly argued that λ-calculus is the first object-oriented programming language, because λ-calculus' only abstraction mechanism is functions, and therefore all abstraction is always functional/behavioral.
You asked about integers, sets, and quad trees, but let's start with something even more simple first: booleans.
You are probably familiar with what an Abstract Data Type based encoding of booleans looks like: it's basically just one bit, and some functions (or operators) that look at the value of the bit. But, as we discussed above, this is not possible for objects: you cannot inspect the internal representation, so you cannot know what value the bit has.
Let's take a small excursion back to the λ-calculus, and specifically to the Church Encoding of booleans. The Church Encoding encodes booleans as functions (obviously, since functions are the only thing that exists in the λ-calculus), specifically as a pair of functions, defined something like this:
[Note: all code examples will be in ECMAScript, with which I am much more familiar than C++, but nothing in them is ECMAScript-specific except some bits of syntax. All concepts are general OO concepts that apply to all OO languages. Even the examples that use classes might just as well be expressed using traits or mixins or prototype delegation.]
function t(a, b) { return a; }
function f(a, b) { return b; }
So, essentially, we have two functions with two parameters, and the first one evaluates its first argument and ignores the second, and the second one evaluates its second argument and ignores the first.
In other words, this is a conditional!
But wait: here we have a "thing" (true or false) which is at the same time a value but also behavior. What does that remind us of? Isn't that just an object?
Indeed, the object-oriented encoding of booleans is very similar to the Church Encoding, it looks a little like this:
const t = {
or(other) { return t; },
and(other) { return other; },
ifThenElse(a, b) {return a(); },
};
const f = {
or(other) { return other; },
and(other) { return f; },
ifThenElse(a, b) {return b(); },
};
t.not = f;
f.not = t;
f.not.or(f).ifThenElse(() => console.log("is true"), () => console.log("is false"));
// is true
This is not a hypothetical scenario, this is actually how booleans are implemented in Smalltalk, Self, Newspeak, Pico, Fancy, and many other programming languages. It is, however, not how booleans are implemented in, for example, C++, Java, or C#. In those programming languages, booleans are Abstract Data Types, not objects at all.
You mentioned sets: the On Understanding Data Abstraction paper I mentioned above actually uses sets as the running example to show how an object-oriented set would look like and how it differs from an ADT.
The main question is: if objects are behaviorally abstract, then what is the behavior of a set object, exactly? Let's take a look over to mathematics. In mathematics, there are generally two ways in which sets are defined. One way is to just list all the members, e.g. { 1, 2, 3 }. However, listing all the members is "somewhat inconvenient" for example for the set of all even integers: you'll need a lot of time writing down all even integers!
So, the other way in which sets can be defined in mathematics is through what is called the indicator function. I.e. you can define the set of all even integers as "member(2n) = true, member(2n+1) = false".
Now, here is where it gets interesting: in an ADT-based set data type, the set would probably have a contains function. But, as we have seen, in some sense, a set also is its contains function. And that is how you can represent a set in an object-oriented way with behavioral abstraction: you identify the set with its indicator function. (In Scala, for example, Set[T] is literally a subclass of Function1[T, Boolean].)
An OO set would look something like this:
const Empty = {
contains(_) { return false; },
union(other) { return other; },
intersect(_) { return Empty; },
}
class Set {
union(other) { return new Union(this, other); }
intersect(other) { return new Intersection(this, other); }
}
class Union extends Set {
#a; #b;
constructor(a, b) {
super(); this.#a = a; this.#b = b;
}
contains(other) { return this.#a.contains(other) || this.#b.contains(other); }
}
class Intersection extends Set {
#a; #b;
constructor(a, b) {
super(); this.#a = a; this.#b = b;
}
contains(other) { return this.#a.contains(other) && this.#b.contains(other); }
}
class SingletonSet extends Set {
#el;
constructor(el) {
super(); this.#el = el;
}
contains(other) { return other === this.#el; }
}
const EvenIntegers = new Set();
EvenIntegers.contains = n => n%2 === 0;
const MultiplesOfThree = new Set();
MultiplesOfThree.contains = n => n%3 === 0;
const EvenMultiplesOfThree = EvenIntegers.intersect(MultiplesOfThree);
Note that, depending on the language and the library, this may or may not be how sets are actually implemented in your particular case. In fact, it is quite likely that this is not how sets are implemented in your particular case. It is much more likely that any set you will ever encounter will be implemented as an Abstract Data Type, not as an object. But, you asked specifically how one could implement things like sets as an object with behavior, and this is one way to do it.
You also asked about integers. I encourage you to try it out yourself. Maybe start with something slightly simpler: natural numbers. Here's a hint: you could represent a natural number n as an iterator that applies that a given function n times. If you then have some simple operations such as successor and predecessor, and you have a singleton number ZERO, then you can build your natural numbers fully on top of that, only using behavior, without ever needing to fiddle around with another number's internal representation.
In closing, I would like to point out something very important, because you asked about what is the "correct" way: Objects and Abstract Data Types are complementary, and in some sense duals of each other. But neither is better or worse than the other: they have different tradeoffs.
In particular, Objects by definition do not support what William Cook calls "complex operations", by which he means operations that need to inspect the internal representation of more than one object at the same time. Remember, objects can only observe each other by sending messages and observing the response. This means that one object can never inspect another object's internal representation, even if both objects are instances of the same type / class.
This is different with ADTs: an instance of an ADT can inspect the internal representation of another instance of that same ADT.
A simple example of a complex operation that is trivial with ADTs but impossible with Objects is concatenating two doubly-linked lists in O(1) time. This requires you to have access to the prev pointer of the head of the second list and the next pointer of the tail of the first list at the same time, which is allowed for ADTs but impossible for Objects.
[Note: the astute reader might have noticed that instances of the same class in Java or C# can inspect each other's internal representation. That is true, and that indeed means that instances of classes in Java are not objects. Only instances of interfaces are objects.]
So, neither of the two options is more correct than the other. And there is nothing wrong with, e.g. C++ integers or Java class instances being ADTs and not objects.
