Mental Model of Type Conformance/Subtype Polymorphism

Question

I'm finding that my CS2 students really struggle with the notions of type conformance and subtype polymorphism in Java. Say we have the following:

public abstract class Vehicle {
    // attributes + constructor
    public void ride() { ... }
    public String toString() { ... }
}

public class Bicycle extends Vehicle {
    // attributes + constructor
    // notice this is an override from Vehicle
    public void ride() { ... }
    public String honkHorn() { ... }
}

They then consider the following problems, with my commentary on common mistake(s) following each problem:

Bicycle b = new Bicycle();
Vehicle v = b;

Students look at this and think b cannot be stored in v, either due to the type difference, or maybe because Bicycle has a constructor with a different number of parameters than the Vehicle constructor, so of course b can't 'fit' inside v.

Bicycle b = new Bicycle();
Vehicle v = b;
v.ride();

Students commonly think that the ride method in Vehicle will be called. I understand why this mistake is made, but those who get this correct still struggle then with this next problem:

Bicycle b = new Bicycle();
Vehicle v = b;
v.honkHorn();

Students now think this is also syntactically valid. Because subtype polymorphism ensures that the method call will use the object's implementation, rather than the variable's, they think that Java will somehow recognize that v is storing an object of type Bicycle, and thus honkHorn is available to be called. It never occurs to them that Vehicle doesn't even have this method, so of course it won't work.

Anyway, they have had two quizzes and now an exam involving these concepts (despite seeing them in class contextualized in other learning material all semester, and theoretically a little at the end of last semester), and a significant number of students are still struggling with this. Any suggestions on how to convey all these concepts? My approach is usually to convey very clear models of how things look in memory, but that doesn't seem sufficient here. Do I just need lots of examples/practice problems? Other suggestions?

Answer 1

The problem is that you don't really have subtype polymorphism here. While the language permits it, it is poor practice to change the interface (set of public methods) as you move down the hierarchy. I'm not speaking of the formal interface but only of the messages that an object is allowed to handle. Your class Vehicle doesn't have honkHorn, but a subclass does.

The problem with this is that if I have an object, I need to know its specific type to know what methods it supports. Some Vehicles support honkHorn, but others don't so I need to test.

This is, at best, ad-hoc polymorphism.

If you want true subtype polymorphism define a class as an interface or abstract class as you have done here, but all subclasses should exhibit exactly the same interface.

Then, if you define a variable to have the interface (abstract class) type, then it can refer to any object of any subclass and it can field any message defined at the top level. You never need to ask instanceof and you never need to cast.

It is, of course, harder to build a system keeping such a pure rule, but it can be done and it saves you a ton of grief later.

One of the reasons we want to build OO software is to let the system figure things out without explicit testing. If you change "interfaces" within hierarchies you are just back to ad-hoc decision making. You are defeating the notion of IS-A that the OO paradigm was built for.

In your example you can't really say that a Bicycle IS-A Vehicle. You can say that it is a Vehicle, but something more, and we have to determine what by ad-hoc means in many instances. Sometimes by declaring variables to have a specific type (rather than a general type) and sometimes by testing.

In terms of "contracts", if you change the contract as you come down the hierarchy, it wasn't really a contract.

Sadly, too many books don't understand this and define meaningless, and difficult to work with, "hierarchies".

One way to avoid this issue, is to define Vehicle as an interface and then define Bicycle as another interface that extends Vehicle. Now your intent is clear. Classes implementing an interface have only the public methods defined in their interface and nothing more. Now you have interfaces of concepts which is what they are really intended to model, and classes of objects that conform to specific concepts. This may be the mental model you seek, actually.

---

I discussed Polymorphism at some length here: https://cseducators.stackexchange.com/a/4050/1293

---

Let me add some things here to point to a better way. One of the lessons is that subclassing is generally overused. Some books present it as the "really big thing". Instead, programming by composition is much more valuable. When you create a class give it parts that are instances of some other, simpler, class.

For the immediate problem here. Give Vehicle a method makeSound. Give each subclass of it an instance field that refers to some kind of object that might make a typical sound. For a bicycle object it might be a Horn object. Then when any vehicle is sent the makeSound message it delegates the making of the sound to the object that is part of its composition. Delegation is the big idea here. Now you don't need to change the protocol in different classes. Just change the implementation, but giving different "parts" to different vehicles.

At least one very commonly used book has something like the following hierarchy. First a Point class. A point has some coordinates. Then, for the first (ugh) example of subclassing is a Circle class. This is "easy" to write, since if you subclass Point all you need to add is a radius value. But to a mathematician, is every circle a specialization of point? It is backwards, of course. Taking it farther, a Cylinder can subclass Circle just by adding a height value. This makes it very easy to type in, but very foolish, both mathematically and from a program design standpoint. If you create a Cylinder, what sort of variable should you use to refer to it. If you don't use a Cylinder variable, then within the next few lines you are very likely to have to cast the variable, or, if you have put such things into a List then you are going to have to type case them (or equivalent) when you look at them again. Don't do that. But what can you do better. Use delegation.

When you build your Circle class, don't make it an extension of Point. Instead, give it an instance variable of type Point. A Circle is a different kind of thing. It isn't a point, but it HAS-A point as a field.

Likewise the Cylinder HAS-A Circle for its base. Much cleaner. The cylinder delegates some of its actions to its base when it receives a message. Likewise the base (a Circle) delegates some messages to its location (a Point).

Now you have a defensible design, but it might not have used subclassing at all. You get reuse (via delegation) and don't confuse the nature of things and require ad-hoc decision making throughout a long program.

Answer 2

So as not to confuse issues, let me give more detailed advice here on why the students are going wrong and about their mental model. I'll try to keep this distinct from the problems of what I consider a poor example of subclassing.

The first lesson that you need to give them is the distinction between a message and a method. A method is the implementation some actions or information request. A message is the invocation of those actions. Methods are defined in classes. Messages are sent to objects generally via a variable of some kind. Be clear about the terminology. Don't say function (except static methods). Don't say "call a method". Say "send a message". Just as you would IRL. Language is important. If you want students to have a good mental model, use appropriate language. If you use the language of C, they will think like C programmers, but OO isn't like that.

The second lesson is that objects receive messages and every message is interpreted by the object that receives it in terms of its own most specific class. It doesn't matter which variable refers to it, or the declared type of the variable (so long as it is legal). The interpretation of the message is specific to the object.

The third lesson is that the "system" knows different things at compile time and at run time. At compile time it only knows the declared types of things, not the actual types. At run time the system "knows" the actual type of an object being referred to (more accurately, an object knows its own type). But objects are only created at run time. At compile time, all we have is the text of the program.

The fourth lesson is that variables don't "hold" values. Variables reference values. You can actually take this view even for int values without loss. The implementation is immaterial to a valid mental model. An int variable refers to an int. It can later refer to a different int. "Holding" has no place here. This makes the reference model of objects much easier to grok.

The fifth lesson is that objects get a type only when they are created. The same is true for all values, actually. Moreover, no value ever changes its type. Its type is immutable as long as it is in existence.

Putting lessons 4 and 5 together, a variable can refer to different objects at different times (when legal in the type system). But no value changes its type, nor does the variable change its (declared) type.

The reason for declaring variables to have a type and to give values a type at creation is to avoid a large set of programmer errors as you create the program so they don't have to be caught (or missed) at run time. Other languages (Python, Ruby) don't give a declared type to variables, so there are a larger number of potential errors that can escape if testing isn't rigorous.

I think these rules are sufficient to dispel the variable mismatch issues in the question asked here, but can extend if comments make it necessary.

---

On the question of language and especially the notion of a "message" vs a "call".

In languages like C one "calls" a function. And in languages like Java, one sends a "message" to an object requesting a service. The actual mechanism for this is quite different.

In C, one can examine the text of the program and determine precisely what will happen when a function is called. The "dispatch" of the function is direct - a sort of direct goTo. Note the words "determinable from the text of the program."

In Java you cannot in principle know precisely which method will be dispatched when you send a message as this depends on the specific type of the object that receives the message, not on the text of the message (the text of the program). Of course if the program uses no polymorphism at all, so that the specific type to which every variable refers is known then than won't be true, but in general if object A and B both implement interface I, then x.mumble(3) can be different depending on whether, at that run time instant, x refers to an A or to a B. Therefore you can't "call" methods (other than static methods) of A or B, you can only send a message to the object referred to that you would like service "mumble".

If you ignore this, then polymorphism will be much harder to understand. Since the mechanism is different, different language is called for and appropriate.

To respond directly to the comment that generated this addendum, no, you don't "send a message to a knife to cut". YOU cut with the knife. The knife isn't an actor here. You are and only you. But if you had a household of service robots you would send messages to them since they are actors that "know" how to carry out their own actions. "Daneel, cut the bread." is a message. The robot knows how to cut, but Charlee might cut differently (say with a laser). Here you use messages.

Ultimately you want to be able to think in a language. If you use misleading terminology (leading you to think that you have more "control" than you really do), then you will just confuse yourself.

For a specific example. Suppose you have a Set (with A, B, and I) taken from above. Now you iterate over the set and send "mumble(t)" to each element. Different things happen and the text of the program doesn't tell you what will happen other than that it is some implementation of a method defined in I - not the explicit method. The objects are in control. The receiver of a message, not the sender, is in control. Request a service - send a message. Dispatch is indirect via the object, not direct from the code invoking the service.

Answer 3

This is only a partial answer, and it is aiming at doing something very practical in your classroom right away.

I rather liked the old GridWorld case study from AP Computer Science for this, as there were various sorts of Actors, all of whom had their own act() method. (This is also the approach used in GreenFoot.)

It allowed you to create an ArrayList<Actor> and add many different Actors. Rocks, Flowers, Critters, etc, and then loop through your list and just run act().

You can quickly imitate, in a very silly way, something similar using an ArrayList. The code is ridiculous, but in terms of exploring the simple nuts-and-bolts of upcasting, downcasting, type, and polymorphism, it's actually a great example.

The fact that it works at all already gives students an immediate sense of what is happening. I'd present them with the code, and ask them to predict what it will do. Then run it a few times, and begin to ask them questions like, "Why does this work at all?" And "Could I call .length() on the items in silliness? Why or why not?" And "Given the code you're seeing here, could you imagine a legitimate reason to group different sorts of Objects together?" And "Why do the Objects all print different things to the screen, even though silliness only thinks that they are Objects, not Strings or arrays or whatever?"

ArrayList<Object> silliness = new  ArrayList<Object>();
for (int i = 0; i < 10; i++)
    silliness.add(nextObject());
for (Object mystery : silliness)
    System.out.println(mystery);

// . .. . . . elsewhere...

public Object nextObject(){
    Random rand = new Random();
    int randomNum = rand.nextInt(4);
    if(randomNum == 0)
        return new int[10];
    else if(randomNum == 1)
        return new String("Silly String!");
    else if(randomNum == 2)
        return new ArrayList<Integer>();
    else
        return new Integer(31415);
}

This code, as ridiculous as it is, gives a nice, simple touch-point in your discussions with students throughout the unit that can help them make sense of the polymorphic behaviors.

Answer 4

This discussion of the design of the code is a worthwhile one to have. However, regardless of ones opinion, one is likely to encounter code which follows this pattern. Therefore, it is important to understand what is happening.

The line Vehicle v = b; is giving an alternate name to the same object. Additionally, it is saying "v, you are a bicycle, but I am going to treat you as an ordinary vehicle. I will ignore anything special about you." As a result, any method of Vehicle that Bicycle overrides will be honored. However, I will not call any of your special methods. The compiler enforces this by generating the error.

This is exactly what happens when you declare the type of a variable to be an interface. You are promising only to invoke the methods defined by that interface.

Answer 5

I'm not so surprised that people struggle with something like Bicycle b = new Bicycle(); Vehicle v = b;. It is not a very practical example, and it doesn't really dictate what behavior you would expect. What about using more realistic and practical example(s)?

You can use some examples from this question. My answer there describes implementation of arithmetic expressions. This was one of the examples used in my Object Programming course, and I think it's an excellent one (I list its advantages in the answer). Of course Java implementation would look differently and would use actual inheritance.

I think that basics of inheritance and methods dispatch are actually very simple and intuitive (if you have a Bicycle, why would you expect to not behave like a bicycle?), but not very easy to describe in words, or on abstract examples. My general idea is that you should first build the expectations for a mechanism that behaves in particular way, and then present inheritance as fulfillment of this expectation. In other words, you first build the mental model, and only then give it a name. Otherwise you risk that people will first create wrong mental model that will be hard to fix.

One approach would be to actually implement these arithmetic expressions using one class with enum type tag and switch statements or ifs. It is easily demonstrable, that this approach is pretty inflexible (and rather ugly), and that it would be useful to give it a structure in which method implementations are grouped by behavior. I believe at this point explaining interfaces/inheritance should be easier, as you have a tangible problem which they solve.

Disclaimer: I don't have any measurable experience in using this approach, but I think I have seen it working (while studying myself).

Answer 6

There is yet another flaw indicated in the code as presented, but it is of a different kind, so I've separated this out into a separate answer. One of the principles of good OO design is called "Tell, don't Ask".

What this means is that whenever possible, we should tell an object to do something to advance our computation rather than asking it for the information we need in order to advance that computation elsewhere. Generally, void methods are of the tell variety, and others are of the ask kind. In the sample code, the drive method tells a Vehicle to do something. This is fine. What it does is determined by its own class and by arguments in the method (here none).

But the honkHorn method doesn't tell a Bicycle to honk its horn. It asks for a piece of information (a String) that might be used elsewhere in the program to indicate the sound of a program. The Bicycle, itself, does no honking.

If you do this sort of thing a lot - gather information from objects and act on that information - what it means is that the actual behavior of the program is distributed around the program, where it can be harder to maintain than if it is localized within the objects.

Not every program can avoid such accessor methods altogether (nor should that be a goal for most programs), but, when you consider adding an accessor to a class, try to decide if the locus of the action shouldn't better be within the object itself, rather than somewhere, maybe not yet determined, else in the program. Tell the objects to do your bidding. Don't just treat them as convenient data stores with the logic elsewhere.

Answer 7

I notice you expressed your concerns without once using the word 'pointer' (or even 'reference'). This may be a problem. You also talk about v = b meaning "b is stored in v", but that's not really what this means. It means the pointer "v" gets overwritten by the pointer "b", which is a pointer to the object "b." (b-dot). The object doesn't "fit inside" its pointer. I'm nitpicking here because although Java calls its implicit smart pointers 'references', they are pointers and this concept is essential to grasp in understanding their behavior.

Primarily, students need to learn that any non-primitive Java variable, which is a pointer, is a completely different entity from the object it points to. These two things are separate: they're created in separate places in code, they mean very different things when you use them, and they can have different types.

I usually illustrate this by drawing the pointer as a triangle, labeling it with its type above and its variable name (if it isn't anonymous) below. The object I draw as a circle with its type above and its object name (variable-dot) below, and I illustrate the abstract value of the object in the circle.

For example, if I have an Set<Integer> pointer called foo, the type of foo is pointer to Set<Integer> (though I'd generally just say that aloud and label it Set<Integer>) and the name of foo is foo. The type of the object might be HashSet<Integer>, and its name would be "foo." as in "foo-dot". This is because when you use the dot operator in Java, it automatically gives you the object. Any time you omit the dot you're talking about the pointer, and anytime you use . you're talking about the object. So "foo." is the literal name of that object (or one literal name, if it has aliases).

Object types must be class types, but the pointer type can be any supertype of the object type because (for example) a HashSet<Integer> is a kind of Set<Integer>. Thus, it's still type-safe for a pointer of that type to point to an object of that type: HashSet<Integer> must contain all of the methods described in Set<Integer>, so any method we can call on the pointer will have a corresponding body in the object (provided the pointer is not pointing to null).