CSci 581: Obj.-Oriented Design & Programming
Spring Semester 1999
Lecture Notes

Implications of Inheritance (Budd's UOOPJ, Ch. 11)

This is a set of "slides" to accompany chapter 11 of Timothy Budd's textbook Understanding Object-Oriented Programming with Java (Addison-Wesley, 1998).

Idealization of is-a Relationship

• A TextWindow is-a Window

• Because TextWindow subclasses Window, all behavior of Window present in instances of TextWindow

• Therefore, variable declared as Window should be able to hold value of type TextWindow

Unfortunately, practical programming language implementation issues complicate this idealized picture.

Impact of Inheritance on Other Language Features

Support for inheritance and the principle of substitutability impacts most aspects of a programming language:

• Polymorphic variables needed

  Polymorphic variable:

  variable that is declared as one type but actually holds a value of a subtype

• Polymorphic variables better if objects allocated on heap rather than stack -- storage requirements vary among subtypes

• Heap allocation makes reference (pointer) semantics more natural than copy semantics for assignment and parameter passing -- copy address of object rather than value

• Heap allocation also makes reference semantics natural for object identity testing -- compare addresses -- separate operator for object value equality

• Heap allocation requires storage management -- reference semantics makes manual allocation difficult -- garbage collection encouraged

Polymorphic Variables

class Shape
{   public Shape (int ix, int iy) { x = ix; y = iy; }
    public String describe() { return "unknown shape"; }

    protected int x;
    protected int y;
}

class Square extends Shape
{   public Square(int ix, int iy, int is) { super(ix, iy); side = is; }
    public describe() { return "square with side " + side;}

    protected int side;
}

class Circle extends Shape
{   public Circle(int ix, int iy, int ir) { super(ix, iy); radius = is; }
    public describe() { return "circle with radius " + radius;}

    protected int radius;
}

class ShapeTest
{   public static void main(String[] args)
    {   Shape form = new Circle(10, 10, 5);
	System.out.println("form is " + form.describe(); 
    }
}

Output of ShapeTest: form is circle with radius 5

Polymorphic Variables (from Solitaire)

public class CardPile { ... }

class SuitPile extends CardPile { ... }

class DeckPile extends CardPile { ... }

class DiscardPile extends CardPile { ... }

class TablePile extends CardPile { ...}

public class Solitaire 
{   ...
    static public CardPile allPiles [ ];
    ...
    public void init () 
    {       // first allocate the arrays
        allPiles = new CardPile[13];
	...
        allPiles[0] = deckPile = new DeckPile(335, 30);
        allPiles[1] = discardPile = new DiscardPile(268, 30);
        for (int i = 0; i < 4; i++)
            allPiles[2+i] = suitPile[i] =
                new SuitPile(15 + (Card.width+10) * i, 30);
        for (int i = 0; i < 7; i++)
            allPiles[6+i] = tableau[i] =
                new TablePile(15 + (Card.width+5) * i, Card.height + 35, i+1); 
    }

    private class SolitaireFrame extends Frame 
    {   ...
        public void paint(Graphics g) 
        {   for (int i = 0; i < 13; i++) 
                allPiles[i].display(g);
        }
    }

Memory Allocation -- Stack and Heap Based

Generally, programming languages use two different techniques for allocation of memory:

Stack-based allocation:

memory allocated on the runtime stack

• Memory allocation/release tied to procedure entry/exit

• Space requirement determined at compile time based on static types

• Advantage: efficient -- all local variables allocated/deallocated as a block (activation record)

• Disadvantage: polymorphic variable size not known at compile time -- objects stored may vary during execution

Heap-based allocation:

memory allocated in free memory area

• Memory allocation/release not tied to procedure entry/exit

• Space requirement determined at run-time based using dynamic considerations -- size known when allocated

• Allocated objects accessed by indirection through a pointer (reference in Java)

• Advantage: supports polymorphic variables -- values can be pointers to object on heap

• Disadvantage: considered less efficient than stack-based

Memory Allocation in Java and C++

Java

• All object variables hold pointers to heap-allocated objects -- fixed size on stack, differing sizes on heap

  Variable of type Shape holds address of object on heap

• Polymorphic variables thus easy to implement

  Assignment of Square instance to Shape variable means new address stored

• Primitive type variables hold values, copy on assignment, not polymorphic

C++

• Variables stored on the stack -- enough space allocated to hold instance of actual declared type

  Variable of type Shape holds actual object

• "Ordinary" variables are not polymorphic

  Assignment of Square instance to Shape variable means object copied with extra field sliced off -- no longer Circle

• Pointer variables hold addresses of objects -- thus support polymorphism

  Assignment of Square pointer to Shape pointer variable means new address stored

• Objects may be allocated on heap (or on stack or statically)

  Care must be taken with pointers to deallocated objects on stack (or in heap memory)

Copy versus Reference Semantics

Copy semantics:

Assignment copies the entire value of right side to the left side variable.

The two values are independent; changes to one do not affect the other

Examples: Java assignments to primitive variables, C++ assignments to non-pointer variables

Reference (pointer) semantics:

Assignment changes the left side variable to refer to the right side value.

There are now two references to the exact same value; if the value is changed, it can be observed using either reference

Example: Java assignments to object variables, C++ assignments to pointer variables.

Java Reference Semantics Example

public class Box 
{   public Box() { value = 0; }
    public void setValue(int v) { value = v; }
    public int getValue() { return value; }

    private int value;
}

public class BoxTest
{   static public void main(Sring[] args)
    {   Box x = new Box();
	x.setValue(7);   // sets value of x

	Box y = x;       // assign y the same value as y
	y.setValue(11);  // change value of y

	System.out.println("contents of x " + x.getValue());
	System.out.println("contents of y " + y.getValue());
    }
}

• After y = x, both x and y in BoxTest refer to the same object

• Call y.setValue(11) thus changes object referred to by both x and y

• Message getValue() thus returns same value (11) for both x and y

Creating Copies in Java

• If need copy, explicitly create it

  Box y = new Box(x.getValue());
  

• If commonly need copy, provide a specific copy-creating method

  public class Box
  {   ...
      public Box copy()
      {   Box b = new Box();
          b.setValue(getValue());
          return b;
      } // return (new Box()).setValue(getValue())
      ...
  }
  

  and use method when needed

  Box y = x.copy();    
  

• Copy constructors are sometimes useful

  public class Box
  {   ...
      public Box(Box x) { value = x.getValue()); }
      ...
  }
  

• Base class Object has protected method clone() that creates a bitwise copy of the receiver

• Interface Cloneable denotes objects that can be cloned -- not methods in interface, just tag

  Cloneable objects needed by some API methods

Example: Java Clones

Make Box a Cloneable object

• Implement interface Cloneable

• Override method clone() (which returns type Object)

• Make clone() public

  public class Box implements Cloneable
  {   public Box() { value = 0; }
      public void setValue(int v) { value = v; }
      public int getValue() { return value; }
      public Object clone() 
      {   return (new Box()).setValue(getValue()); }
  
      private int value;
  }
  
  public class BoxTest
  {   static public void main(Sring[] args)
      {   Box x = new Box();
  	x.setValue(7);   // sets value of x
  
  	Box y = (Box) x.clone();  // assign copy of x to y
  	y.setValue(11);           // change value of y
  
  	System.out.println("contents of x " + x.getValue());
  	System.out.println("contents of y " + y.getValue());
      }
  }
  

• Values 7 and 11, respectively, would be printed by BoxTest

Shallow versus Deep Copying

Suppose that the values being held by the Box objects are themselves objects of type Shape

• Box's clone would not copy the Shape object; the clones would both refer to the same Shape object (instead of ints)

  It creates a shallow copy

• If the internal Shape object were also copied, then it would be a deep copy.

  Box's method clone() could call Shape's clone() operation

• Decide whether shallow or deep copy is needed for application

Parameter Passing as Assignment

• Parameter-passing is assignment from argument to parameter

• Java primitive values are passed by value from argument to parameter -- copy semantics

  Modification of parameter just local, no effect on argument

• Java object variables are passed by reference from argument to parameter -- reference semantics

  Note: Value of reference is copied from argument to parameter

  Modification of parameter's internal state is change to argument

  public class BoxTest
  {   static public void main(Sring[] args)
      {   Box x = new Box();
  	x.setValue(7);   // sets value of x
  
          sneaky(x);
  	System.out.println("contents of x " + x.getValue());
      }
  
      static void sneaky(Box y)
      {   y.setValue(11); }
  }
  

  Value 11 would be printed by BoxTest

Equality Testing -- Primitive Types

How do we test whether two values of the same primitive type are equal?

Test whether their values are identical -- i.e., same bits

Java: x == y

What about equality of values of different primitive types?

In general, will not pass type checker unless well-accepted conversion between

Java: numeric types converted and compared, but otherwise mismatched types means inequality

Equality Testing -- Object Identity

Some languages will compare the values; others, compare pointers (references)

Java uses pointer semantics -- i.e., tests object identity

Java == tests object identity

Integer x = new Integer(7);
Integer y = new Integer(3 + 4);
if (x == y)
    System.out.println("equivalent")
else
    System.out.println("not equivalent")

Output is "not equivalent"

Objects x and y physically distinct -- but same value internally

Java type checker disallows comparison of unrelated object types with ==

But can compare if one an ancestor of other

Circle x = new Circle(10, 10, 5);
Shape  y = new Square(10, 10, 5);
Shape  z = new Circle(10, 10, 5);

Above x == y and x == z pass type checking, but neither returns true

null is of type Object; can be compared for equality with any object

Equality Testing -- Object Value Equality

Java Object class has equals(Object) methods to do bitwise comparisons, often redefined

if (x.equals(y))
    System.out.println("equivalent")
else
    System.out.println("not equivalent")

Output is "equivalent"

Can override equals() to get more appropriate definition

class Circle extends Shape
{   ...
    public boolean equals(Object arg)
    {   return arg instanceof Circle &&
               radius == ((Circle)arg).radius); 
    }  // more compact above than textbook example
}

Above c.equals(d) iff c and d are both Circles with same radius regardless of location

Should override equals() if object contains other objects

But be careful with asymmetric equality comparisons

Suppose override equals() in Shape

class Shape
{   ...
    public boolean equals(Object arg)
    {   if (arg instanceof Shape)
        {   Shape s = (Shape)arg;
            return x == s.x && y = s.y ;
        }
        else
            return false;
    }
}

But not in subclass Square

Now consider

Square s = new Square(10,10,5);
Circle c = new Circle(10,10,5);
if (s.equals(c))  // true, uses Shape method
    System.out.println("square equal to circle");
if (c.equals(s)) // false, uses Circle method
    System.out.println("circle equal to square");

Changing Method Arguments

For equality testing, it might useful to change types of method arguments

class Shape 
{   ...
    public boolean equals (Shape s) { return false; }
}

class Circle extends Shape 
{   ...
    public boolean equals (Circle c) { ... }
}

class Square extends Shape 
{   ...
    public boolean equals (Square sq) { ... }
}

Covariance and Contravariance

• An argument or return value made more specialized is covariant

  Type replaced by descendant of original type

• An argument made more general is contravariant

• Both can destroy is-a relation, have tricky semantics

• Most languages forbid both

  Java and C++ forbid

  Eiffel supports covariance

Storage Deallocation

Polymorphic variables lead naturally to heap-based allocation

Heap-based allocation requires a storage deallocation mechanism

Two approaches were discussed previously

Explicit deallocation by programmer

-- programmer must return unneeded memory to system

Examples: C++ delete, Pascal dispose

Advantage: efficiency

Disadvantages:

• attempted use of memory not yet allocated or already freed
• multiple freeing of memory
• freeing of memory that is still needed
• memory leak -- allocated memory is never released

Implicit deallocation by runtime system

-- system detects when data unneeded, automatically recovers memory

-- garbage collection

Examples: Java, Smalltalk, Perl

Advantage: safety and convenience

Disadvantage: relative inefficiency / loss of programmer control

UP to CSCI 581 Lecture Notes root document?