Notional Machine

Table of contents

1. Machine abstraction
2. Inheritance
3. Compile-time
4. Casting

Machine abstraction

We’ve now seen two types of abstraction: data abstraction (e.g. lists, sets, maps) and functional abstraction (e.g. domain, range, behavior). These abstractions specify a contract between the client of the abstraction and the implementer of the abstraction. For example, a client that calls a method can only expect it to work if they pass in valid arguments (preconditions) and if the implementer has written the correct code to produce the expected outputs (postconditions).

In this lesson, we’ll explore an even more fundamental abstraction that underlies all of the programming in the past, present, and foreseeable future.

Machine abstraction

A model of a computer system that specifies how the computer system works in terms of input, possible operations, and output.

Machine abstractions are all around us. All of the computer and smart-things in our daily lives are machine abstractions. Machine abstraction is the reason behind how the Java programs that we write can run on a laptop, in a datacenter, or on a chip embedded in a toy. The web browser that you’re using to read this document on the internet is also a machine abstraction. The browser takes as input a program specifying the web page layout and interactive components. It then reads the program, builds the layout, and adds interactivity.

The details behind how all of this works is complicated to say the least. The web browser is a machine abstraction for the internet. The web browser is a program, and the programming language is a machine abstraction. The program is running on an operating system, which is also a machine abstraction. The operating system is sending instructions to the processor hardware, a machine abstraction. The principle of machine abstraction allows all of these components to change independently: we can update our web app independent of the web browser independent of the programming language independent of the operating system independent of the processor hardware.

Each of these layers could be a lifetime of study on its own. The concept of a notional machine distills the complexity of a machine abstraction down to only the parts that are relevant to us as learners. The question for this lesson is, “What parts of the Java’s machine abstraction are relevant to us as programmers?”

Inheritance

We’ve often declared our data structures using the following syntax, prefering to use the interface type wherever possible. Interface inheritance defines the rules for checking that ArrayList implements all of the behavior required by the List interface.

List<Integer> numbers = new ArrayList<Integer>();

In contrast, Java also allows for implementation inheritance where classes can be derived from other classes, inheriting fields and methods from those other classes. Every class has only one direct superclass that can be explicitly declared with the extends keyword. In the absence of any explicit superclass, every class is implicitly a subclass of Object. This is why classes defined without equals or toString can still call those methods because their implementations are inherited from Object.equals and Object.toString.

But inheritance can get hairy! Sometimes, it’s not clear why inheritance doesn’t compile or doesn’t give the expected output. Consider the following classes. Which method does each statement actually call?

public class Main {
    public static void main(String[] args) {
        Term term = new FancyTerm();
        FancyTerm fancy = new FancyTerm();

        term.compareTo(term);
        term.compareTo(fancy);
        fancy.compareTo(term);
        fancy.compareTo(fancy);
    }
}

class Term implements Comparable<Term> {

    // Implement Comparable<Term>
    public int compareTo(Term other) {
        System.out.println("Term.compareTo(Term)");
        return 0;
    }
}

class FancyTerm extends Term {

    // Override inherited compareTo(Term)
    public int compareTo(Term other) {
        System.out.println("FancyTerm.compareTo(Term)");
        return 0;
    }

    // Specialized compareTo(FancyTerm)
    public int compareTo(FancyTerm other) {
        System.out.println("FancyTerm.compareTo(FancyTerm)");
        return 0;
    }
}

Compile-time

Before running a Java program, it needs to be compiled using javac, the Java compiler. The Java compiler catches mistakes (like using values of the wrong type) or typos (like calling a method that isn’t actually defined).

Java compiler

A program that translates source code to “bytecode” that can be executed by the Java runtime.

The goal of the Java compiler is to ensure that every statement can (at least in theory) run.

List<Integer> list = new ArrayList<Integer>();
list.containsKey(5); // List cannot call containsKey, so compiler error

Let’s study this closely. Consider the following inheritance hierarchy representing real-world music players.

• Object
  • MusicPlayer
    • MP3Player
      • iPod
        • iPhone
      • Zune
    • TapeDeck
    • CDPlayer

As with interface types, the left-hand side type (promised type) does not need to be the same as the right-hand side type (actual type). We can declare a MusicPlayer as the promised type with its value as a reference to the actual type iPhone, for example.

MusicPlayer p = new iPhone();

The compiler checks this line against the inheritance hierarchy.

Is iPhone a MusicPlayer?

Looking at the inheritance hierarchy above, iPhone is indeed a MusicPlayer so we can p.play() music.

However, we cannot call p.phoneCall() even though the actual type is iPhone. By declaring the promised type as MusicPlayer, the compiler can only guarantee access to the methods and fields of MusicPlayer and its superclasses.

We can write some code that randomly picks between an iPhone and a CDPlayer as the actual type. As a result, there’s no way for the compiler to know the actual type of p until running the code.

MusicPlayer p;
if (new Random().nextBoolean()) {
    p = new iPhone();
} else {
    p = new CDPlayer();
}
p.play();
p.phoneCall(); // MusicPlayer cannot call phoneCall

The compiler keeps track of the details of which methods are available to which types in a virtual method table. The compiler refers to this table to make sure that every method can be called at runtime. In order to build the virtual method table, the compiler associates each class with all of its method signatures.

Method signature

The unique identifier for the method given by the name of the method and its parameter types. Two methods cannot share the same signature in the same class.

Overriding

A subclass defines a method with the same exact signature as a method in its superclass.

Overloading

A class defines multiple methods with the same name but different parameter types.

For example, List.add is overloaded: one method appends to the end while another adds at an index.

The reason why it’s called a virtual method table (as opposed to just “method table”) is because the actual method that’s called is determined at runtime. In the List example, we know that List is an interface: it doesn’t actually define any implementation for each of the two add methods. Instead, the List interface requires implementations such as ArrayList and LinkedList to override each of the two add methods.

Casting

The compiler doesn’t always have complete information about the actual type of a variable. As we saw, it’s impossible to know whether the actual type of p is iPhone or CDPlayer until the program is actually executed.

MusicPlayer p;
if (new Random().nextBoolean()) {
    p = new iPhone();
} else {
    p = new CDPlayer();
}
p.play();
p.phoneCall(); // MusicPlayer cannot call phoneCall

In the circumstances when this restriction might be too harsh, the programmer can use a cast to temporarily change the promised type of an expression. This is typically used to change the promised type from a more general type like MusicPlayer to a more specific type like iPhone.

MusicPlayer p;
if (new Random().nextBoolean()) {
    p = new iPhone();
} else {
    p = new CDPlayer();
}
p.play();
((iPhone) p).phoneCall(); // iPhone can call phoneCall

The compiler performs a consistency check to confirm that the cast is possible. At runtime, Java performs another consistency check to confirm that the actual type is truly compatible with the casted promise type.

Compile-time casting check

Is it possible for the value of a variable p with promised type MusicPlayer to have actual type iPhone (or a subtype of iPhone)?

Runtime casting check

Check to make sure that the actual type works with the promised type. Otherwise, throw a ClassCastException.

The runtime check is necessary since it’s possible that the actual type of p is actually CDPlayer, in which case CDPlayer cannot call phoneCall(). The code will compile since it’s possible that p has an actual type of iPhone based on the relationship between MusicPlayer and iPhone, but it will throw a ClassCastException at runtime if it turns out that p is actually a CDPlayer.

Note

Casting does not change the actual type of an object. It only changes the promised type of the expression! It’s not possible to change the actual type of an object using casting.

In summary, the process for determining the result of executing a program with an inheritance hierarchy is complicated.

Compile-time

The compiler only considers the promised type of an expression.

1. Determine the promised type of the expression. Perform the compile-time casting check.
2. Determine the compile-time method signature. Look in the promised type before searching its superclasses. If there are multiple methods in the class that could work with the promised parameter types, choose the method that most closely matches the promised types.

Runtime

1. Validate any casting. Perform the runtime casting check.
2. Dynamic method dispatch. Look for the most specific method that exactly matches the compile-time method signature. Look in the actual type before searching its superclasses. At least one implemented method is guaranteed to exist since we found a valid compile-time method signature earlier.¹