Before You Begin

Today is Friday Quiz Day! Close your computer and get ready for your TA to hand it out for your completion before you start on today’s assignment.

Once the quiz is over, go ahead and pull today’s lab from the master branch of the skeleton remote repository, and import it into an IntelliJ project.

Learning Goals

The first focus of this lab will be to introduce you to object oriented programming, a programming paradigm that focuses on objects, which are containers of data, and how these objects interact with one another. Objects are instances of different classes. Java is an object oriented language, so it is necessary to understand how objects work in order to make full use of the language.

Related to objects and classes is the concept of inheritance, a mechanism that allows a class to be defined that differs only slightly from an existing class. Inheritance provides numerous benefits. In particular, programmers can take advantage of already written correct code and avoid reinventing the wheel.

A related concept is polymorphism, meaning many forms. In Java, this refers to how an object can have different forms or types. The procedure for untangling an instance of polymorphism can be somewhat complicated, so there are numerous exercises that provide you with practice.

We will introduce the difference between the static and dynamic types of an object, which is related to polymorphism in Java. Static vs dynamic type can be a tricky subject, so there are also many practice exercises in this lab.

Lastly, we will wrap up loose ends from yesterday’s lab, particularly concerning scope, which determines where a variable can be accessed. When programming, you will need to think about scope in order to organize your code and ensure its correctness. You’ll also use the IntelliJ debugger to look for issues in code.

Inheritance

Review of Inheritance from CS 61A

You learned in CS 61A that a programmer can set up one class to inherit characteristics (methods and instance variables) from another. This is typically done to reuse most of an already-defined class that needs an extra method, or that requires a method to behave slightly differently.

The Subclass and the Superclass

We say that the subclass (the inheriting class) extends the superclass (its parent).

If you look in your skeleton files, we have provided you with a Fish.java implementation and a Salmon.java implementation. Since Salmon extends Fish, Salmon is the subclass and Fish is the superclass.

extends signifies an “is-a” relationship. A Salmon is a Fish. Notice however that the reverse of this is not necessarily true; not all Fish are Salmon. (Just like how all squares are rectangles, but not all rectangles are squares.)

Constructors

Worksheet: 1.1 Fish and Salmon [Optional]

Let’s take a look at how constructors are inherited. Question 1.1 will have you open up Fish.java and Salmon.java and leave-in or comment-out different combinations of constructors to see what is allowed and what isn’t. To test these combinations, you can run javac Fish.java Salmon.java in the terminal to compile the code. If there is no output, then the constructor combination is allowed, and the classes compiled successfully. Otherwise, read the error message to see why the combination is not allowed.

If you would like, complete this exercise on your worksheet. It is optional and will not be graded.

Overview

Your exploration should expose the following rules of Java constructor inheritance:

• Constructors are generally not inherited from the superclass.
• In any class, if there are no constructors, Java will automatically provide a no-argument constructor. But, if at least one constructor is explicitly provided, then Java will not automatically provide this no-argument constructor.
• When defining a constructor for a subclass, the very first line should be a call to a super constructor. If you do not explicitly provide this line, then Java will automatically insert a call to the no-argument super constructor. However, if there does not exist a no-argument constructor in a superclass, then compilation will fail nonetheless. This is because when constructing a subclass object, you must always construct its superclass first.

That was a flurry of intricacies! Make sure you understand every caveat listed above and that your understanding of these rules align with the results of your experiment!

Static and Dynamic Type

Before we continue with talking about how fields and methods are inherited, we need to understand static and dynamic types first.

Introduction to Polymorphism

The word polymorphism comes from the Greek words for “many” (poly) and “forms” (morphe). In the context of object-oriented programming, it means that a given object can be regarded either as an instance of its own class, as an instance of its superclass, as an instance of its superclass’s superclass, and so on up the hierarchy. In particular, where a given reference type is requested for a method argument or needed for a return type, we can supply instead an instance of any subclass of that reference type. That’s because inheritance establishes an “is-a” relationship: for example, a Salmon is a Fish with some extra properties. As an example, imagine you have the following method:

public static void makeDinner(Fish f) {
    f.fry();
}

...
Fish f = new Fish();
Salmon s = new Salmon();
makeDinner(f); // This works!
makeDinner(s); // This works too!

We can call makeDinner and pass in either a Fish object or a Salmon object (again, since a Salmon is a Fish). And it turns out, if we pass in a Salmon object, the code will use the fry method that you defined in Salmon!

Ok that’s pretty cool, but what about something like this? Do you think the following will compile?

public static void makeSecondDinner(Salmon f) {
    f.fry();
}
...
Fish fs = new Salmon(); //Line A
makeSecondDinner(fs);   //Line B

Worksheet: 1.2 Fish and Salmon

Choose a combination of constructors that compiles and comment the rest out. In the main() method of Main.java, add lines A and B of the snippet above.

Complete this exercise on your worksheet.

Defining Static and Dynamic Type

The Java compiler and runtime system have to resolve two questions that arise when polymorphism is used. At compile time, the compiler, which wants to catch typing inconsistencies and other possibilities for error, asks can a method with a given name can be invoked on a given object. Once the compiler has answered “yes” to that question, the runtime system needs to find which of the possible versions of that method is the right one to invoke.

To explore exactly how this works, we introduce some new terminology: static type and dynamic type.

So far in the class, most of the variable instantiations you’ve seen have been in a form like

Fish f = new Fish();
Salmon s = new Salmon();

where the class name, like Fish, appears twice, once on the left of the assignment operator (=) and once on the right of the assignment operator. But we just learned that because of polymorphism, we are allowed to do something like:

Fish f2 = new Salmon();

This means a variable can have two different types associated with it. The one on the left of the equals sign, Fish, is referred to as the static type of the variable (note that this is not to be confused with the static keyword in a method signature–these are two separate things!). It is the type that the reference is declared as. The one on the right of the equals sign, Salmon, is referred to as the dynamic type of the variable. It is the type of the object that is constructed.

The static type of a variable is allowed to be the same as the dynamic type, or the superclass of the dynamic type (or the superclass’s superclass, and so on). However, the static type cannot be a subclass of the dynamic type (as you saw earlier). The static type can also be an interface that the dynamic type implements, a design that we will learn in a later lab.

Thus, this is not allowed:

Salmon s2 = new Fish(); // compiler error

You can think of the left-hand side static type as a label on a box, which tells of what the box contains. And you can think of the right-hand side dynamic type as the actual identity of the item inside of the box. Below, we have two boxes, one labeled with a static type of Fish and one with a static type of Salmon. We also have an instance of a Fish and an instance of a Shark shown here. And the four different assignment statements above can be represented by different combinations of putting our Fish and Salmon instances into our labeled boxes.

For Fish f = new Fish(); and Salmon s = new Salmon();, our analogy agrees with what Java allows; yes, it makes sense to allow a Fish inside of a box labeled Fish. And yes, it makes sense to allow a Salmon inside of a box labeled Salmon.

For Fish f2 = new Salmon();, we claimed that Java allows it, and this makes sense; we can have a Salmon instance inside of a box labeled as Fish–we wouldn’t be surprised if we opened a box labeled Fish and found a Salmon inside, since after all, a Salmon is a Fish!

For Salmon s2 = new Fish();, we claimed that Java does not allow it, and this makes sense; if we opened a box labeled Salmon and found any Fish inside of it, such as a shark, we would be surprised. (I would be furious! Imagine if I had found a Shark instead of the Salmon I had been promised!?)

If you think about Box and Pointer Diagrams, our analogy fits in as well. We’ve learned to draw a variable box for the static type, and for the dynamic type we draw an instance and draw an arrow from our static type variable box to our instance; we have a labeled box that holds an instance.

Recap

Perhaps at this point you would like to refine your answer for worksheet question 1.2 (b), now that we have introduced static and dynamic typing!

Methods

Great! We’ve learned about how constructors are treated in Java’s inheritance rules, and then we took a break and learned about static and dynamic types. Let’s now talk about how methods are treated by Java’s inheritance rules.

• Methods are inherited from the superclass to the subclass.
• You can override a method that is inherited by redefining it in the subclass with the exact same signature and return type as that of the superclass.
• You’ll sometimes see overriden functions with an @Override annotation above the function. This is not required for the overriding behavior to occur, but what it does is that it signifies to Java that you are intending to provide an overriding function definition, and so in that case if you accidentally did not provide a matching function signature and your overriding effort fails, Java’s compiler will stop you and let you know about it.
• You can overload a method of the same class by providing multiple methods in a class with the same name with unique number of parameters or parameter types.

What the Compiler Does

Recall that the compiler executes when you enter javac Filename.java in your terminal. To determine the legality of a method call such as

f.swim(10);

the compiler examines the static type of f. If the static type of f contains a swim method that takes one integer as the argument (or one of its superclasses does), then the statement is legal, and the code compiles and is allowed to run. If not, a compiler error results. The red underlines in IntelliJ indicate compiler errors.

Worksheet: 1.3 Fish and Salmon

Complete this exercise on your worksheet. Your lab TA will go over this exercise with your section.

What Happens at Run Time

Once there are no compiler errors, your code can be executed by a runtime system, such as when you enter java FileName in the terminal or when you click the Run button in IntelliJ. Following the example above, after the compiler is satisfied that a swim method with matching arguments is available for an object’s static type, the runtime system will select the most specialized swim method with matching arguments to call based on the dynamic type. For an object with dynamic type Fish, it uses the Fish’s swim method. For an object with dynamic type Salmon, it uses the Salmon’s swim method.

Worksheet: 1.4 Fish and Salmon

Complete this exercise on your worksheet.

Once you have made your guesses on paper, check your answers for 1.3 and 1.4 by adding these lines to the main method of Main.java.

Your lab TA will go over this exercise with your section.

Caveats

Two caveats:

• If you’re trying to call a static method, only the static type is used. This behavior is similar to field lookup, which we will discuss below.

• The method used at runtime must be a direct override of the method found at static time. It cannot be an overload. This means the method signature must match exactly (both the name of the method and argument list length and types must match).

Exercise: Extending the Point Class

We can extend classes that we haven’t written ourselves – such as those in the Java API – provided they aren’t declared as final. Here’s an example of extending the Point class from the java.awt library.

Some classes provide “setter” methods. Setter methods allow you to change the values of instance variables, even if they are private, because the method is public. A useful debugging aid is to override a setter method to produce informative output every time the object’s state changes.

The setter method for the Point class is named move; the call

p.move(27, 13);

changes the x coordinate to 27 and the y coordinate to 13 in the Point referenced by p. Given below is the framework for a TracedPoint class intended to intercept calls to move and print information about the pre- and post-change state of the Point along with doing the move. You are to complete and test the framework after reading a note about super in the next subsection.

import java.awt.*;
public class TracedPoint extends Point {

    public TracedPoint(int x, int y) {
        super(x, y);
    }

    public static void main (String[] args) {
        TracedPoint p1 = new TracedPoint(5, 6);
        p1.move(3, 4); // prints: "point moved from (5,6) to (3,4)"
        p1.move(9, 10); // prints: "point moved from (3,4) to (9,10)"

        TracedPoint p2 = new TracedPoint (25, 30);
        p2.move(45, 50); // prints: "point moved from (25,30) to (45,50)"

        System.out.println("p1 is " + p1);
        System.out.println("p2 is " + p2);
    }
}

Another way to use super

The super keyword has another use besides for constructors. It also allows you to call superclass methods that the subclass has overriden. Use it similarly to how you would use the this keyword.

this.method(); // calls the method in the current class
super.method(); // calls the method in the parent class

Now implement TracedPoint and take advantage of the superclass’s methods and variables as much as possible rather than reinventing the wheel. To look at exact the method signature of the java Point class, search “java 11 Point class” in a search engine like Google.

Casting

Ok…but this a’int really fair though is it? In the previous exercise, bob had a dynamic type of Salmon, but because it had a static type of Fish, Java refused to compile the line bob.swim(5);. That’s really too bad, because you and I know that bob really should be able to swim and swim(int speed) because he is a Salmon, but Java didn’t even care to open the box because the box label only guaranteed bob to be at least a Fish, and not all Fish can swim(int speed). Poor bob.

Luckily, Java provides us a way out. We communicate this information to the compiler by a type cast, putting a class name in parentheses immediately preceding a reference or reference expression. A type cast temporarily changes the static type of a variable. It is us saying: Hey Java compiler, sweetheart, trust me on this one. If you compile this code for me, then I’ll promise, promise you that it’ll work!!

Let’s see how this works. Say we have the following instances to work with:

Fish redFish = new Fish();
Fish blueFish = new Salmon();

We saw in the previous exercise that something like this won’t compile, because the static type does not have a swim with an int method.

blueFish.swim(5); // compiler error

We can throw a cast on this line to solve this: Hey Java compiler, sweetheart, trust me on this one. If you compile this code for me, then I’ll promise, promise you that it’ll work!!

((Salmon) blueFish).swim(5); // swimming at 5 mph

Nice! How about this? Hey Java compiler, sweetheart, trust me on this one. If you compile this code for me, then I’ll promise, promise you that it’ll work!!

((Salmon) redFish).swim(5); // run-time error

This code snippet will compile, but at runtime, Java will hit you with a ClassCastException. Uh-oh…what happened? Well you used a cast, and so you promised Java that the contents of the redFish box will be a Salmon. The compiler saw that Salmon has a swim with an int method, and so it went ahead and compiled your code for you because of your cast. But then at runtime, when Java actually went to look at the dynamic type of redFish it saw that it was a…Fish! Unfortunately, Fish cannot swim(int speed), and so at that point, Java realizes that you lied to it; you casted redFish to be a Salmon but it really wasn’t a Salmon. And because of that, Java is mad at you and makes your program crumble to the ground at runtime.

Also note that casts don’t always allow code to compile. You can’t cast anything to anything, it has to be in the same hierarchy or it won’t compile. Assuming that a Cats is not a Fish, the following cast fails at compile time:

((Cat) redFish).meow(); // compiler error

Worksheet: 2. Identify Static Types

Complete this exercise on your worksheet.

Scope

When we reference a variable in any way during the execution of a method - for example, to increment by saying something like counter = counter + 1, the Java run time environment must do variable look-up. This is when scoping comes into play. Java adheres to a tiered look-up system, and checks for the existence of variables in this order:

1. Local scope. This is the current method body and we’ll discuss this in a bit more detail below.
2. Current instance scope, the fields directly available in the type of the object pointed to by this. Typically (but not always, because of polymorphism!), this is also the class the method currently being executed is defined in.
3. Any classes that the current class inherits from. How this works has been talked about extensively above.

Consider the following code snippet, which can also be found as Swap.java without the comments:

public class Swap {
    int counter = 0;            // instance variable
    int counter2 = 0;           // instance variable
    static int counter3 = 0;    // static, is a class variable

    /* swap(...) iterates through the array from the start_index and
       swaps elements forward if they are in descending order with respect
       to the next element, and then prints out the number of swaps. */
    public int swap(int[] arr, int start_index) {   // beginning of method block
        while (start_index < arr.length - 1) {          // beginning of while block
            int counter = 0;                        // local variable, available inside while loop
            if (arr[start_index] > arr[start_index+1]) {
                int temporary = arr[start_index];   // available inside if statement
                arr[start_index] = arr[start_index+1];
                arr[start_index+1] = temporary;
                counter = counter + 1;              // references local variable counter
                counter2 = counter2 + 2;            // references instance variable
                counter3 = counter3 + 1;            // references class variable
            }
            start_index = start_index + 1;          // references local variable start_index
        }                                           // end of while block
        System.out.println("Swapped " + counter + " times.");
        return counter;
    }                                               // end of method block

    public static void main(String[] args) {
        Swap s = new Swap();
        int[] arr = {3, 2, 6, 1, 4};
        s.swap(arr, 0);     // expect to swap 3 times, (3, 2), (6, 1) and (6, 4)
                            // -> arr is {2, 3, 1, 4, 6}
        s.swap(arr, 0);     // expect to swap 1 time -> arr is {2, 1, 3, 4, 6}
    }
}

Let’s first talk about local scope. A pair of matching curly braces with statements inside, except for the curly braces around the class definition, defines a block. Examples of this are method definitions, while statements, for loops, if statements, and so on.

Variables declared inside a block are local variables. These exist until the end of the block. This means that variables declared inside a method goes out of scope after the method finishes execution, inside of an if statement are not accessible after the if statement, and inside of a loop go out of scope after an iteration of the loop. Finally, note that method arguments behave like local variables declared at the beginning of the method’s execution. This can be seen in the example in the line start_index = start_index + 1.

Variables declared just inside the class are fields or instance variables, and are used when look-up for a local variable fails. For example, when we say counter = counter + 1, we find counter as a local variable and do not look up the instance variable counter. However, when we say counter2 = counter2 + 2, we don’t find a local variable counter2 and use the instance variable counter2.

When we define a local variable that has the same name as a field, like counter, counter now refers to the local variable and the only way to access the field is through this.counter.

Take a moment to read through the code snippet above, and think about what is going on and going wrong. If you’re not immediately sure, that’s good! We’ll walk through using the IntelliJ Debugger, which is an important and vital tool you’ll be using throughout this class.

Exercise: Use the debugger to find the fix

You can set a breakpoint by clicking to the left of the line of code, as shown by the red dot here:

Then, when you run the program in Debug mode (right click the file Swap in the left pane and hit “Debug Swap.main()”, click the green bug on the top right corner of your screen and select Swap), program execution will run up to but not including the point where a breakpoint is specified, execution will stop and drop you into the debugger.

Notice how in “Variables”, you can inspect the active variables and open them up. In the code display section, the values of variables will be shown. And circled in white are the control buttons. You can hover over them and see what they are labeled:

• Step into - if there’s a function call on the current line, step into that function’s execution. If there is none, behaves the same as step over.
• Step over - execute everything on the current line and move on to the next one.
• Force Step Into - You shouldn’t need this.
• Step out of - If you’re in a function call, finish the function call and go to the calling method.

Here we want to “Step Into” the swap call, as we want to see how our scope is modified when Swap executes. Inside Swap, try “Step Over” and watching the course of execution. Watch the values of variables change and inspect which variables are available from the current context. Before clicking “Step Over”, try to predict how the variables should change, and check if the variables change accordingly after you click.

Finally, one useful thing to notice is the stack trace:

Clicking on either method in the call trace will move the current view to that method’s current context (that is, either line 11 of swap or line 23 of main in this example).

You’ll want to use the debugger instead of print-statement debugging for most bugs, especially in your larger projects. Learning to use it will save you valuable time in tracking down bugs.

Fix up Swap.java so that it behaves correctly and outputs the correct number of swaps.

Sidenote: The CS61BL IntelliJ Plugin

Additionally, the CS61BL plugin for IntelliJ that we had you install allows you to use the Java Visualizer in IntelliJ. This can also be a tool for you to use to debug programs. Note that while this will be helpful for smaller programs, for larger projects, it might not be possible for you to visualize everything.

To use the built-in visualizer, debug your code, setting breakpoints as necessary. When your code stops, you can click the Java Visualizer icon:

The Java Visualizer will appear, displaying the stack of the currently paused program:

Fields

In terms of inheritance, at compile time we check the static type for the existence of the field. Fields can be inherited, so it is also acceptable for the field to exist in a superclass of the static type. At runtime, we also use the static type to get the value. A situation in which a subclass has the same field name as its superclass is called field hiding. We won’t test you on situations with it since field hiding is bad practice!

Worksheet: 3. Playing with Puppers

Complete this exercise on your worksheet.

Conclusion

Summary

Today we talked about object-oriented programming (OOP), inheritance, polymorphism, static and dynamic types, and scope.

Deliverables

A quick recap of things you need to do to complete this lab:

• Implement TracedPoint.java which extends from the java.awt library.

• Fix Swap.java so that it correctly prints the number of swaps.

• Fill out the week 1 reflection to get the secret word and put it in magic_word.txt