Scott D. Anderson
copyright 1998
Back in the days when programming languages were simple, there were only a few relationships that parts of a program could have. Primarily, there was the relationship between the calling function and the called function. In other words, if FOO calls BAR, that establishes a relationship between them. It's easy to see it (since there's a call statement in the code) and it's easy to understand. There are other relationships as well, which we'll discuss in this document.
With object-oriented programming, new relationships come into existence, and so the programs become more complex. Unfortunately, many of these relationships are drawn with arrows between the two related things, and so pictures don't really help. The purpose of this document is to define and describe the different kinds of relationships that occur in a programming language and to try to illustrate them with metaphors rather than pictures.
Each relationship will be named with a single, present-tense verb that relates the two things. Try to use these verbs in your later work in this class, so that we can all start to share a common terminology. Synonyms will also be given, when possible. If these descriptions are confusing or unhelpful, please let me know so that I can improve this document. If the whole document is unhelpful, don't tell me, because I put too much work into it to throw it away.
As mentioned in the introduction, a simple relationship is between a caller and a callee: function FOO calls function BAR.
Diagrams for this kind of relationship are often like an organization chart (using the boss-employee metaphor) or a tree (using the parent-child metaphor), where a boss node in the tree calls all its employees, each of which calls its employees, and so forth. This tree is named the ``call tree'' for a program and reflects the ``hierarchical decomposition'' way of designing programs: MAIN calls some functions, which call other functions, which call other functions until we get to the leaves of the call tree, where the code does some work without calling any other functions.
If more than one boss calls a particular employee, the tree becomes a directed acyclic graph. This is, in fact, an ideal use of functions, because redundancy in the code is eliminated. It may not make sense in real life for someone to have multiple bosses, but it makes perfect sense in programming.
Perhaps a different metaphor will help. Suppose you go to the post office and eventually you get to the head of the line. You ask the clerk to do something for you, and they do. This is analogous to the ``calls'' relationship: you're the caller, and the clerk is the callee, and you called on them to perform a task for you. In principle, you might have been able to do that task yourself, but for reasons of security and division of labor, it makes sense to ask someone else to do it. You can think of this as the ``client-server'' model, in which case the relationship might be termed ``serves,'' but it's usually termed a ``remote procedure call.''
Recursion introduces loops into the call tree, so that some function can become its own employee (direct recursion) or subordinate (indirect recursion). At its most general, the call ``tree'' is a directed graph.
Hierarchical decomposition is now considered old-fashioned, with the new design technique being object-oriented design. Nevertheless, parts of most programs can still be described with call trees, and we will see that the call relationship still exists in OOP.
Why does one function call another? Basically, for the same reason that bosses doesn't do all the work by themselves but hire others to work for them. Each has skills and, when called, exercises those skills. In a program, perhaps the skill is to sort an array. Anytime anyone wants to sort an array, they can call that function. Sure, they could put the code for sorting the array into their own code, avoiding the call, but then there's no division of labor and there's a great deal of redundancy in the code. You have to debug every place the sort code appears, as opposed to debugging just one sort function.
Don't forget the calls relationship. It's common and important.
A carton contains eggs. A classroom contains students. A bus contains passengers. An array or list contains elements. This is a simple relationship, easily understood. It would hardly be worth mentioning, except to acknowledge it and say that it is different from the other relationships that we will mention.
This relationship is not usually drawn with arrows. It's often drawn as either a box or a circle with the contents inside. We will draw other things this way, too, so be careful.
A zoo comprises![[*]](/usr/local/latex2html-97.1/icons.gif/foot_motif.gif){kind=icon}
many animals. The United
States comprises fifty states. An engine comprises many parts. A name
comprises a first, middle, and last name. An address comprises a street,
a city, a state and a zip code. A student record comprises a name, a
social security number, an address, a phone number, and other fields. The
programming language construct that captures this relationship is a
record (Pascal, COBOL, Ada terminology) or a struct (C, C++, Lisp
terminology).
The distinction between ``comprise'' and ``contains'' is perhaps a subtle one. Many people wouldn't make a big deal out of it, but in a programming language class, it makes a difference. The elements of a container are somehow fungible or interchangeable. We might talk about iterating over the elements of a container, removing one (and reducing the size of the container), adding one (and expanding the container), or rearranging (sorting) them. Those operations don't make as much sense for a record.
This relationship is important because it's a building block for objects, which we will get to in a little while.
Sometimes, pointers are inevitable: you can't have a linked list without pointers. Other times, pointers are something of a choice: you can have an array of records or an array of pointers to records. The latter choice allows a single record to occupy the array in more than one place, because more than one element of the array can point to the same record. Therefore, pointers have an advantage because something that's pointed to can be pointed to by many things. Any change to the thing (let's think of it as a record) will be immediately seen by all those pointing to the thing.
Pointers are, of course, always drawn with arrows. Thus, it's easy to confuse with the ``call'' relationship we discussed above. The difference is that pointers are a relationship between data structures (such as the array and the records) and not a relationship between functions.
This difference, however, is not big. The ``points to'' relationship is really the data-structure analog to the ``call'' relationship. You could put the code in every place you need it, or you could put it in one place and have others call it. With the second technique, any change to the code will immediately be felt by every caller, but with the first technique, you'd have to update every place the code appears. This is just the same as the advantage of pointers over direct placement of data.
The encapsulation relationship is an issue of security: an object encapsulates its parts so that no outsider can mess with it.
Consider a juke box. It has buttons and such on the front, and that's the interface with the user. (Remember our ``calls'' relationship? The caller is the user of a function, and the function's arguments and values are its interface with the user, because that's how the user gives information to the function and gets information back.) The juke box protects its innards from users because it doesn't want people pulling random CDs out and putting them on the player. If CDs got put back in the wrong slots, the juke box would play the wrong discs when the user pressed the buttons and the whole thing would be unusable.
For a computer science example, let's consider the classic example of a stack. A stack can be implemented as an array containing the elements of the stack, plus another variable to point to the top of the stack. If we let the user modify those data structures, a user could easily mess everything up. So we want to protect these data structures and force the user to interact with the stack through a defined set of operations. These operations are just what you'd guess: push, pop, top, is-empty, and so forth.
Suppose that we trust the users enough to believe that they will not mess up the stack. They might, however, come to rely on the stack being implemented with an array. The temptation would be enormous to keep an index to an interesting stack element, for example. Later, if we decide to change the implementation from an array to a linked list, the users' code breaks because of that reliance. Therefore, it's important to hide the representation of the stack from the users, for their own good and for our freedom of implementation.
We say that the stack data structure encapsulates some data (the array and the pointer, or the linked list), thereby hiding the implementation from the users. We require users to interact with the data structure by means of these defined operations. Thus, the stack is some data (which is hidden) and some operations on that data: that's all the users know.
Data structures like this are called abstract data types or ADTs. They are abstract because the implementation is hidden. They are datatypes because we can have variables whose type is an ADT. For example, we could declare the variables S1 and S2 to be of type STACK, where STACK is an abstract data type, encapsulating some data. Note that these are two different stacks, and therefore the memory allocated to represent them would have two different arrays or two different linked lists, depending on the implementation.
Two more examples before we move on. First, a Tree Node could easily be an ADT. The operations could be things like leftChild or parent or numChildren and so forth. As users, we suspect that the Tree Node ADT is implemented with a record of some sort, but we don't and can't know. Second, a Tree could be an ADT. Operations on this ADT might be things like height or insertNode or findNode. The implementation of the tree might be done with tree nodes and pointers or might be an array of records (such as a heap) but, again, we don't and can't know. All that's required for something to be an ADT is for it to have a sensible definition as some data and operations on that data.
Abstract Data Types are often drawn as circles, where the inside of the circle encapsulates the (hidden) implementation and users interact only with the surface of the circle, using the defined operations. These interactions are sometimes drawn as arrows, since using an operation (such as push or pop) is equivalent to calling a function. Thus, the call relationship is still with us, now between a user (some other piece of code) and an ADT.
Let's put ourselves on the inside of an ADT for a minute. Indeed, imagine that we are the programmers of the ADT: we have to write some code that will, when the operations are called, do the right thing. We have to write a push operation that somehow modifies the innards of the ADT so that a later pop operation gets the value back--note that we write the pop operation, too. This is called implementing the ADT.
We can distinguish between the interface and the implementation: the semantics of the interface is what the ADT is supposed to do when the operations are performed, the implementation is how that behavior happens.
The Java programming language brings this idea to its zenith by allowing a programmer to define an interface without defining an implementation. The programmer simply says ``anything that implements these operations is a FOO.'' For example, anything that implements push, pop and the rest is a STACK. Alternatively, anything that implements the lessThan operation is a SORTABLE. This means we can write a sort function that can sort any array of objects that are sortable. This is how Java does generic functions.
You might wonder what kinds of things are sortable. Imagine that one stack is less than another if it has fewer elements (ties are broken arbitrarily). We could then sort an array of stacks. On the other hand, one stack could be less than another if its top element is less than the other's top element. We could again sort an array of stacks, but in a different way.
Thus, these data structures could implement several interfaces: the stack interface and the sortable interface. One advantage of interfaces over inheritance in Java is that inheritance is restricted to be single-inheritance, while a class can implement as many interfaces as it wants.
Note that the hidden implementation of an ADT might comprise a bunch of data, such as the array and pointer for our stack. Some of that data might be a container, such as the array. In general, the implementation might exploit all the relationships we've discussed and then some. For example, the implementation of the Tree ADT might comprise some Tree Nodes, each of which is an ADT. The implementation of those Tree Nodes might comprise a list of children and that list might itself be an ADT, where the implementation could be a linked list or an array. Thus, the implementation of ADTs can comprise and contain other ADTs, and this is a different relationship from relationships like ``inherit,'' which is discussed later.
As we saw, a program can have several variables declared to be of some ADT, just as it can have several variables declared to be of some built-in type such as Integer. The data that these variables are bound to are called instances of the datatype or are said to instantiate the type.
The type is just a description of these individuals, but may not exist at run-time. In other words, at run-time, a program might have a variable x whose value is an integer, such as 3, but there is no ``integer'' thing lying around. There are particular integers and particular stacks, but there are no abstractions in the program, taking up storage locations.
Consider the relationship between ``Horse,'' and Black Beauty, Flicka,
Citation and other horses. The latter are individuals that exist in
the real world, they have weight, personalities, and so forth. The
concept of a horse has no physical reality. You can only touch
an instance, not a type. In a program, an instance takes up storage
(it has an address) but a type doesn't.
You can define an ADT that has fifty different variables in its implementation and implements three hundred operations, but if the program doesn't instantiate the ADT, the ADT has no existence at run-time and takes up no space. This is like the concept of the unicorn--a type with no instances. An ADT is a description of some data and some code, but descriptions don't have to exist. This is the view of ADTs that is used by OO languages like C++.
We can, however, take a different view of an ADT: we can consider it
to be a template that stamps out instances or a factory that
manufactures them. If so, we can imagine an ADT that does
exist at run-time. The implementation of the ADT would be some code
that, when called, constructs an instance of that type. This is the
view of ADTs that is used in OO languages like Smalltalk, Java and
CLOS.
Let's take a break from describing relationships (verbs) and discuss some concepts (nouns) for a while.
A class is an ADT: it is a description or definition of some encapsulated data and the possible operations on that data. When you define a class FOO, you are defining an ADT. When you declare x to be of type FOO, you are instantiating that ADT, or, equivalently, making an instance of that class. All the examples of ADTs above could also be examples of classes: stacks, tree nodes, trees, and so forth. Even ``horse'' could be a class: it might have operations to find out how big the horse is, its name, and operations to make it walk, trot, canter or gallop.
A class is usually drawn as a box, listing the operations that can be performed on instances of that class.
An object is an instance of a class. Consequently, an object has run-time existence, encapsulates some data and code, implements some interface, and does things when users ask it to do so. For example, a particular stack (such as S1 or S2) is an object. A particular tree node is an object. Even a particular horse, such as Citation, is an object. You can see that only a particular stack can have a top element (but not the abstraction) and only a particular horse can have a name (but not the concept of horses). Objects differ from other instances of the same class because they have different data values, but they must all implement the same interface, since defining the operations is part of the class definition.
Objects are usually drawn as circles: the interior is the encapsulated data.
A method is an operation on an object. A class defines the set of operations (methods) that can be done to any instance of the class. In the way they work, a method is just like a function: it doesn't store anything, because it's not a data structure, but it can return values and modify the state of the object. For example, the push method stores something in the object, but it, like any other function, runs and finishes. It has no long-term existence, so it is not a store of data.
Methods are often drawn as arrows from the caller to the callee. The callee is necessarily an object of the class that defined the method. The caller can be any other part of the program. The caller may or may not be another instance of the class or, indeed, the same instance of the class. The caller can be any piece of code.
You see that OOP takes the concepts of ADTs and renames them. It is useful to distinguish between objects and classes, but no great innovation was made in renaming operations methods. (I don't know the exact history of the terminology; it may be the case that OOP and ADTs came from different backgrounds and eventually merged.)
In OOP, the programmer's goal is to write the program as a bunch of objects (ADTs), each of which encapsulates part of the data necessary for the program and each of which interacts with the others (using methods) to get the job done.
There is a difference between a class and an ADT: classes have inheritance. That is, the programmer can say that this class is just like this other class except for some differences, and define the new class by referring the existing one and listing just the differences.
The usual relationship is that the ``higher'' or ``parent'' class is more abstract than the ``lower'' or ``child'' class, so that the child is adding information to the parent. For example, the relationship between the concept of a horse and the concept of a quadruped, ruminant or mammal. Each of the latter is more abstract, less specific, than the concept of a horse. Consequently, the Horse class can start with the Mammal class, for example, and add information about diet, size, lifespan, and so forth.
The classes don't have to be natural kinds. Imagine that we have Mazda Protegé as a class. The parent class for that might be Mazda, and the parent class for that might be Car, and the parent class for that might be Vehicle, and so forth.
Because these Class relationships naturally form a hierarchy, they are usually drawn with arrows. Sometimes these arrows go from subclass (lower) to superclass (higher), but usually they go from parent (higher) to child (lower). The usual terminology is parent-child, because that motivates the idea of inheritance. The child inherits everything defined by the parent (all the data and methods), and adds new data and methods. In that way, the child extends the parent, which is the Java terminology. C++ has no special keyword for the inheritance relationship.
This inheritance relationship is different from all the relationships we've discussed so far. It's a new idea and a genuine contribution of OOP, because it can allow programs to reuse existing code by finding an appropriate class and specializing it (another near-synonym) for some new purpose. The effectiveness of this depends a lot on the design of the existing classes.
One test for this relationship is that the relationship is either ISA or AKO: A Horse is a (ISA) Mammal, so that's the right relationship. A Mazda is a kind of (AKO) Car, so that's the right relationship. Note that a Mammals do not contain Horses, and they don't comprise Horses (a Horse is not a component of a Mammal). A Mammal does not call a Horse, or vice versa. A Mammal doesn't point to a Horse. Neither do they encapsulate, implement or instantiate one another. Inheritance is a relationship among types (abstractions), and most of the other relationships are relationships between real entities in a running program.
A real program is going to have all these other relationships too. Some students make the mistake of learning just enough OOP to decide that everything is an inheritance relationship. For example, a student might say that the program as a whole is the parent class, and it has children for the various procedures and aspects of the program. That confuses relationships like ``comprise'' and ``call'' with the inheritance relationship.
A user (a part of a program that is asking another part of the program to do something) can call a function, perform an operation, invoke a method, or send a message. These all mean approximately the same thing. The first is from procedure-oriented programming, where the caller asks the callee to compute some value or perform some task. The second is from ADT-style programming, because ADTs have operations. In OOP, classes (and their instances, which are objects) have methods, and you get an object to do something by invoking the method. Equivalently, you send the object a message .
Why two ways of saying the same thing? They're not quite the same. Because of inheritance and interfaces, a message might mean one thing to one object and another thing to another. More precisely, they might mean the same thing and be implemented differently. At one level of abstraction, asking a stack object to print itself might mean the same thing as asking a tree object to print itself: they both result in the object being printed. However, the details of that meaning are different: (top of the stack first, or bottom first?) (pre-order traversal of the tree, or post-order?). Finally, of course, the implementation is much different.
Therefore, OOP distinguishes between the message (the request to the object to do something) and the method (the implementation of that request). At some point, of course, the connection between these two things has to be made. With polymorphism, that connection is delayed until run-time, otherwise, it might be made at compile-time.
It may seem needlessly picky to talk so much about names for things and relationships between things, but using the right names helps us communicate about what we're doing. If you were talking to some computer scientist and they kept saying ``integer'' when they meant to say ``float,'' you would be confused, then annoyed, and finally wondering if they really understood what they were talking about. Similarly, if they said ``type'' when they meant ``object,'' you would wonder. So, we should use words carefully: when we say ``A calls B'' or ``X inherits Y,'' everyone should understand what is meant.