Week 12.1

🏷️ Replace this section with some keywords that can be used for searching, tagging and the indexing of this page.

Sections

🌱 Links to all Heading1 Blocks in this page.

Runtime Object Allocation

1.0 - Runtime Object Allocation

Objects are allocated dynamically (new) on the heap)
The lifetime of an object may be longer than the lifetime of the method that allocated the object, unlike local (stack-allocated variables)
new allocates a block of memory for the new object
For all objects of class T, each field f is at a fixed offset from the start of every object.
- This is so that we can have efficient access to fields of objects.

1.1 - Subclassing

class S extends T

Subclass S inherits all of the fields and methods of T
The offsets of the inherited fields are the same within S
Additional fields of S follow the inherited fields and have fixed offsets from the start
If a field f is declared in S but f is already a field of T:
- The new field is added
- The old field remains, but its name is masked by the new field
- The old field can be accessed via super.f

1.1.1 - Subclassing Example

public class A {
	int i;
	A() { i = 0; }
	int m(int x) { i = x; return x+1; }
	int getI() { return i; }
}

public class B extends A {
	// inherits field i
	int j;
	B{} ( super(); j = 1; }
	// overrides the definition of A.m in the local scope 
	int m(int x) { return super.m(x) + j; }
	// defines a new method
	int getJ() { return j; }
}

public class C extends B {
	// inherits field i (from A)
  // inherits field j (from B)
	C() { super(); }
	// inherits method getI (from A)
	// inherits method getJ (from B)
	// overrides the definition of B.m in the local scope 
	int m(int x) { return super.m(x) - j }
}

Suppose we instantiate instances of each of these classes, using the following code

A p = new A();
A q = new B(); // Static type A, Dynamic Type B
B r = new C(); // Static type B, Dynamic Type C

Notice that the offsets of i and j are the same for each of the object storages on the heap

Untitled

1.2 - Dynamic Dispatch

class S extends T

Subclass S inherits all of the methods from T
But it may override the methods of T with new implementations.
It can also add new methods
A variable declared to be of some class T has:
- A static (or declared) type of T
- A dynamic type that is either:
  - T
  - Some direct or indirect subtype of T
  - unless it is null
When a (non-static) method is called, it is the dynamic type of the object referenced that determines which method is called.

Suppose we run the following code:

A p = new A(); // Static Type: A         Dynamic Type: A
A q = new B(); // Static Type: A         Dyanmic Type: B
B r = new C(); // Static Type: B         Dynamic Type: C

p.m(2); // calls A.m()
q.m(3); // calls B.m()
r.m(1); // calls C.m()

Observe that it is the dynamic type’s method that is called.

1.2.1 - Dynamic Dispatch Table

Each class has a Dynamic Dispatch Table (DDT)
- It has an entry for every method in the class (including inherited methods)
- The entry gives the address of the code for the method
- The entries are at a fixed offset from the start of the dynamic dispatch table
- The entries for inherited and overridden methods are at the same offsets as in the superclass.
Each object has a reference to the dynamic dispatch table for its dynamic type
- At runtime, the DDT referenced by the object is used t o determine which method is used / called.

Untitled

Observe that the DDT for each class has entries for:
- Each variable
- Each method
Each of these entries point to the code to be executed when the method is called.
Observe here that there isn’t an entry in the DDT for each of the class constructors - this can be worked out statically and thus a DDT entry is not required,
Object A inherits from Object, which also has meaps of methods (which have been ommitted here for space)
- They would point to the code for object’s defined methods
The class B overrides A’s implementation of the method m - this is reflected in the DDT which points B.m to the new code implementation
However, B.getI is inherited from B.getI

1.3 - This, or Self

The keyword this represents the reference to the object on which a method was called
It is passed as an additional implicit parameter to the method

class T {
	...
	void m(int n) {      // Really calling void m(T this, int n)
		...
	}
	...
}

So when we perform a call, we’re really doing:

// Normal call
T p = new T();
...
p.m(x+1);         // Really calling T.m(p, x+1);

1.4 - Super

class S extends T

super(…) within the construct for S refers to the construct for T
super.m(…) calls within S refer to method T.m
super references are resolved statically (at compile time) as we know what the superclass is.

1.4.1 - Superclass Example

public class A {
	int i;
	A() { i = 0; }
	int m(int x) { i = x; return x+1; }
	int getI() { return i; }
}

public class B extends A {
	// inherits field i
	int j;
	B{} ( super(); j = 1; } // Invoke A's constructor
	// overrides the definition of A.m in the local scope 
	int m(int x) { return super.m(x) + j; } //  call A.m
	// defines a new method
	int getJ() { return j; }
}

public class C extends B {
	// inherits field i (from A)
  // inherits field j (from B)
	C() { super(); } // Invoke B's constructor
	// inherits method getI (from A)
	// inherits method getJ (from B)
	// overrides the definition of B.m in the local scope 
	int m(int x) { return super.m(x) - j }
}g

1.5 - Instance Of

x instanceof T

Checks if the dynamic type of $x$ is an instance of T or some direct or indirect subtype of T
Follows the parent link of DDT of type of $x$ until type T is found (true) or end reached (false)

A p = new A();
A q = new B();
B r = new C();

Variable X	x instanceof A	x instanceof B	x instanceof C
p	true	false	false
q	true	true	false
r	true	true	true
null	false	false	false

A p = new A(); // Static type A, Dynamic type A

x instanceof A as p is of type A
x instanceof B as p is not of type B
x instanceof C as p is not of type C

A q = new B(); // Static type A, Dynamic type B

x instanceof A as p is of type B (which is a subtype of A)
x instanceof B as p is of type B
x instanceof C as p is not of type C

B r = new C(); // Static type B, Dynamic type C

x instanceof A as p is of type C (which is a sub-subtype of A)
x instanceof B as p is of type C (which is a subtype of A )
x instanceof C as p is not of type C

In code, you will often see:
```
x ≠ null && x instanceof B
```
The check $\color{lightblue}x != \text{null}$ is actually redundant as null instanceof C is always false.
Generally avoid null, e.g. for empty lists, maps.
For example, in the compiler, we use an ErrorNode for this purpose.

We use the DDT to determine whether a dynamic type is a subtype by following the parent links backward.
For example, to evaluate r instanceof A, where r has a dynamic type of $C$ , we follow the dynamic parent link from C → B → A.
q instanceof C evaluates to false, as by traversing the parent links, we can’t get to C.

Untitled

1.6 - Static Fields and Methods

Static fields and methods are resolved statically, at compile time
- There is one instance of a static field for the whole class
- That instance is shared by all objects o that class
- Static methods are not called on an object, and hence
  - They do not have an object reference as an implicit this parameter
  - They cannot refer to this
  - They cannot directly call a non-static method of the class (because they need an implicit this parameter for this)

1.7 - Interfaces

Allow multiple inheritance
- A class can implement multiple interfaces, but can only extend a single class
More complex runtime mechanism
Each class that implements an interface:
- Effectively provides a DDT for the interface
- There is a dynamic lookup of the DDT for the interface, based on the:
  - Dynamic type of the object on which the method is called
  - The interface that the method belongs to
- Dynamic loading of classes also adds additional constraints