C311 script13.txt -- 4/22/97

---

		  OBJECT-ORIENTED PROGRAMMING: Part III

---

CASTING: to convert the type of an expression from its computed type to
another type to which it is related by the subtype relation.

  In the absense of interfaces in Java, this means moving up or down the
  class inheritance tree.

  Java syntax: "(C)exp" is the value of exp with type C, where C is a
  subtype or supertype of the type of exp.

  Casting has no effect on dynamic method dispatch.

+++

WIDENING (a.k.a. CASTING UP or SAFE CASTING): move to a supertype 

  Towards the tree's root

  No runtime action in Java (some action may be required in C due to 
  multiple inheritance)

  Java supports automatic widening of method arguments. (E.g. follows)

  Some languages provide automatic widening wherever it will help make
  types match: this is called SUBSUMPTION.   

    Java does not support subsumption.  E.g. the following is ill-typed
    in Java, but would be well-typed with subsumption.

      true ? "a string" : System.out

+++

NARROWING (a.k.a. CASTING DOWN or UNSAFE CASTING): move to a subtype 

  Away from the tree's root

  Narrowing is never automatic.  

  Strong typing (Java, not C++) requires a runtime check to insure that
  the cast value really has the type it is being cast to.

  In Java, a run-time exception is raised if widening fails.  Widening to a type
  that is not a subtype is a compile-time error.

  Class checks can be done at run time to be sure narrowing won't fail.

    syntax of Java type check expression: EXP instanceof CLASS

---

Java casting example:

    public class CastEG {
      public static void main(String[] args) {
	A a = new B(); // automatic widening
	a = (A)(new B()); // explicit widening
	if (a instanceof B) {
	  B b = (B)a; // narrowing
	}
	else {
	  System.out.println("Narrowing error!"); // this can't happen
	}
	try {
	  B b = (B)(new A()); // this narrowing raises an exception
	  System.out.println(b.m()); // not executed
	  // but the last statement is necessary to raise the exception
	} 
	catch (Exception e) { 
	  System.out.println(e); // prints java.lang.ClassCastException: A
	}
	System.out.println(a.m()); // prints 2
        // (String)(new A()); // this is a compiler-time error
      }
    }
    class A {
      int m() { return 1; }
    }
    class B extends A {
      int m() { return 2; }
      Object m() { return "s"; } // object return type widening
    }

---

Arrays carry their original type at run-time.

When an array element is assigned, a run-time check is made to see that the
element assigned has a type that is subsumed by (is assignable to) the type
stored in the array.

  This is necessary to avoid the classic error in combining subtyping with 
  data element assignment.

For example: 

    try {
      String [] sa = {"one"};
      Object [] oa = sa;
      oa[0] = (Object) System.out; 
      System.out.println(sa[0].indexOf('e')); // would blow up
    }
    catch (Exception e) { 
      System.out.println(e); // prints java.lang.ArrayStoreException
    }

---

All Java types are of two kinds

  PRIMITIVE TYPES in Java: boolean, byte, char, double, float, int, long, short

  REFERENCE TYPES: the types of objects and arrays (but not necessarily
  array elements)

NULL constant in Java

  Used to initialize array elements and instance variables of reference type
  that do not have initializers.

  Null is not a type, but all reference types are effectively unions with null.

    null may be assigned to any reference type

    In general (unless the compiler can prove otherwise) method calls
    must include a check that the object is not null.	
    
---

POLYMORPHISM in OOP

  A polymorphic method (or function) may be passed arguments of more than
  one type.

  Several kinds of polymorphism are used in OOP:

    dynamic typing (e.g. in Smalltalk, CLOS, Scheme)

    SUBTYPING via implementation inheritance and interfaces

      This form of polymorphism is the most important for a statically-typed
      OOP language.

    GENERIC PROCEDURES (e.g. in CLOS) 

    METHOD OVERLOADING (e.g. in Java, C++): multiple methods in a class
    with the same name, with selection based on argument types

---

SUBTYPING

  If A extends B, then A is a subtype of B, written A <= B.

  The subtype relation is TRANSITIVE: A <= B and B <= C implies A <= C.

  If A implements INTERFACE B, A is also a subtype of B.

  Subtyping is more general than inheritance

    Necessary for databases where structure outlives implementation.

---

Java class declaration syntax: after class name and possible extends clause,
there may be a clause of the form "implements InterfaceName,+" (one or more
InterfaceNames separated by comas), indicating interface "inheritance".

  "Multiple inheritance" of interfaces is not a problem.

+++

In C++, fully abstract classes (having only abstract methods) may be used
as interfaces.

---

Java (slightly simplified) INTERFACE DECLARATION syntax

  similar to class declaration except

    keyword 'interface' instead of 'class'
    
    may not implement any class, but may extend multiple interfaces

    body contains

      no static initializers (code mixed in with declarations, which is
        used to initialize class variables)

      only variables with constants as initializer expressions
      and which have only the implicit modifiers static and final 

      methods declarations with abstract body (just a semicolon)          
      and which have only the implicit modifiers public and abstract

---

Java example using interfaces:

    public class InterfaceEG {
      public static void main(String[] args) {
	print(new One()); // prints 1
	print(new Two()); // prints 2
      }
      static void print(Num n) {
	System.out.println(n.value());
      }
    }
    interface Num {
      int value();
    }
    interface NextNum extends Num {
      int next();
    }
    class One implements Num {
      public int value() { return 1; }
    }
    class Two implements NextNum {
      public int value() { return 2; }
      public int next() { return 3; }
    }

---

Example from java.lang:

  public interface Runnable {
    abstract public void run ();
  }
  public class Thread implements Runnable {...}

---

A class may have a number of types: it's own type, the type of the
class that it extends, and any of its types, and the type of each interface
that it implements, and all the types that they have.

Thus to check if A is a subtype of B, the compiler must search for B in a tree
rooted at A with links pointing from classes to their parents and implemented
interfaces, and from interfaces to their implemented interfaces.

Two classes or interfaces with different names, but otherwise identical,
are still distinct. 

  Java type equality is BY-NAME, rather than STRUCTURAL.

If interface A extends interface B, all the methods in B are considered
to be in A.

The methods in a class are those defined in the class and those that are in
its parent (less those that are overridden).

If a class implements an interface, every method in the interface must be
in the class.  (The class may have additional methods.)

---

The JVM (Java Virtual Machine) represents objects as pointers to "handles"
consisting of a reference to a method table (also containing a reference to
the object's class) and a sequence of instance variable values.  This is
typical of statically typed languages with dynamic method dispatch.  

The JVM instruction invokevirtual invokes a method based on an offset into
the method table that is computed at compile time.  This is the usual form
of method call when the object type is a class.  (Other JVM instructions
are used in special circumstances such as invoking static methods, calls
using super, and calls to initializers.)

If the object type is an interface, the instruction invokeinterface is
used.  This instruction performs a search of the method table at run time.
The JVM leaves open the possibility (not apparently used by present
implementations) that a cache associating an object's class with a method
address might be associated with the point of these method calls.  This
technique, which is extensively used to implement latently typed O-O
language implementations, would in most cases greatly reduce the need for a
time consuming search of the method table.

---

Java does not use subtyping when determining whether a class implements
declaration is valid (though it would seem that it could).  E.g.

    interface I {
      Object m(String s);
    }

    class C implements I {         // not valid
      public String m(Object o) {  // must be 'Object m(String s)'
	return "string";           // and '(Obect) "string"'
      }  
    }

---

Java exceptions are either unchecked or checked.

  UNCHECKED exceptions extend the class Error or RuntimeException and
  include the standard exceptions such as divide by zero.

  CHECKED exceptions extend the class Exception.  

A method declaration my include after the parameter list a clause of the
form "throws ExceptionName,+", where each ExceptionName is the name of a
subclass of Exception.

  If control may leave a method via a checked exception, e, the method
  declaration must include a throws clause that names an exception e1 that
  subsumes e (that is, e must be a subclass of e1).

---

The SIGNATURE of a method consists of the name of the method and the number
and types of the method's formal parameters, but not the return type or
"throws" clause (to be discussed).

In Java, overridden methods must have the same signature.

  Their return types must be the same also (or both void).

  An overriding method's throws clause must be subsumed by the throws
  clause of the overridden method.

    That is, if E is in the throws clause of a declaration that overrides
    a declaration with throws clause E1,...,En, then E <= Ei for some i.

---

In Java, overloaded methods must have distinct signatures.

  Excluding the return type from overloading resolution greatly simplifies
  type checking.

  In an overloaded method access method, the method with the "most specific"
  signature match to the parameter types is chosen.

    First select the set of methods (of the given name) with parameters that
    subsume (can be assigned) the argument types.

    If any method, m, in the set has parameter types that all subsume the
    corresponding paramter types of another method in the set, then remove
    m from the set.

    Repeat the last step as often as possible.  It is a type error unless
    there is exactly one method left, which is the method to invoke.

---

Overloading example:

    class A {}
    class A1 extends A {}
    class B {}
    class B1 extends B {}

    public class OverloadingEG {
      public static void main(String[] args) {
	Object obj = new Object();
	A a = new A();
	A1 a1 = new A1();
	B b = new B();
	B1 b1 = new B1();
	m(obj, b);  // prints 1
	m(a1, obj); // prints 2
	m(a1, b1);  // prints 3
	// m(a, b); // type error if uncommented: ambiguous overloading
      }
      static void m(Object obj, B b) { System.out.println(1); }
      static void m(A a, Object obj) { System.out.println(2); }
      static void m(A1 a, B b) { System.out.println(3); }
    }

---

PARAMETERIZED CLASSES

Most statically typed O-O languages, such as Ada95, Eiffel, and C++,
provide support for parameterizing classes with a type variable.
(Templates are used for this purpose in C++.)  The initial Java language
design has been widely criticized for not providing such support.  This is
one of a very small number of features that is likely to be added to the
Java specification shortly.

When a class is parameterized, the class name becomes a TYPE OPERATOR: a
function from types to types, which is only used at compile time.
(Ordinary functions, by contrast, map elements of types to elements of
types.)  Java already provides one built-in type operator: the array
constructor.

The following example is from a proposal for such an extension of Java in
the Pizza language design by Odersky and Wadler referenced in Script 12.
Whatever is officially added to Java will likely be very similar.

---

The class Pair is paramterized by a type named elem.  This allows pairs
with differing element types to be created easily.

    class Pair<elem> {
      elem x; elem y;
      Pair(elem x, elem y) {this.x = x; this.y = y;}
      void swap() {elem t = x; x = y; y = t;}
    }
    // test code follows
      Pair<String> p = new Pair("world!", "Hello,");
      p.swap();
      System.out.println(p.x + p.y); // prints "Hello, world!"

      Pair<int> q = new Pair(22, 64);
      q.swap();
      System.out.println(q.x - q.y); // prints 42

---

With a HETEROGENIOUS TRANSLATION this translates into the following Java
program.  (This illustrates one way of obtaining this functionality
directly in Java.)  C++ templates are used similarly.

    class Pair_String {
      String x; String y;
      Pair_String(String x, String y) {this.x = x; this.y = y;}
      void swap() {String t = x; x = y; y = t;}
    }
    class Pair_int {
      int x; int y;
      Pair_int(int x, int y) {this.x = x; this.y = y;}
      void swap() {int t = x; x = y; y = t;}
    }
    // test code follows
      Pair_String p = new Pair_String("world!", "Hello,");
      p.swap();
      System.out.println(p.x + p.y);

      Pair_int q = new Pair_int(22, 64);
      q.swap();
      System.out.println(q.x - q.y);

---

Alternatively, a HOMOGENENOUS TRANSLATION may be used.  (This illustrates
the other way of obtaining this functionality directly in Java.)

    class Pair {
      Object x; Object y;
      Pair(Object x, Object y) {this.x = x; this.y = y;}
      void swap() {Object t = x; x = y; y = t;}
    }
    // test code follows
      Pair p = new Pair("world!", "Hello,"); 
	// implicit widening of strings to Object
      p.swap();
      System.out.println((String)p.x + (String)p.y); 
	// narrowing of Objects to Strings

      Pair q = new Pair(new Integer(22), new Integer(64)); 
	// Integer containers are widened to Object
      q.swap();
      System.out.println(((Integer)(q.x)).intValue() - 
			 ((Integer)(q.y)).intValue());
	// The intValue method gets the value from an Integer container.

---

BOUNDED PARAMETERIC POLYMORPHISM

Sometimes it is important to limit the type parameter of a parameterized
class to subtypes of a given type.  This is an important use for
interfaces. 

    interface Ord<elem> {
      boolean less(elem o);
    }
    class Pair<elem implements Ord<elem>> {
      elem x; elem y;
      Pair(elem x, elem y) {this.x = x; this.y = y;}
      elem min() {if (x.less(y)) return x; else return y; }
    }
    class OrdInt implements Ord<OrdInt> {
      // this class can't extend Integer, since that class is final
      int i;
      OrdInt(int i) { this.i = i; }
      int intValue() { return i; }
      public boolean less(OrdInt o) { return i < o.intValue(); }
    }
    // test code follows
      Pair<OrdInt> p = new Pair(new OrdInt(22), new OrdInt(64));
      System.out.println(p.min().intValue()); // prints 22

---

The heterogenenous translation is:

    interface Ord_OrdInt {
      boolean less(OrdInt o);
    }
    class Pair_OrdInt {
      OrdInt x; OrdInt y;
      Pair_OrdInt(OrdInt x, OrdInt y) {this.x = x; this.y = y;}
      OrdInt min() {if (x.less(y)) return x; else return y; }
    }
    class OrdInt implements Ord_OrdInt {
      // this class can't extend Integer, since that class is final
      int i;
      OrdInt(int i) { this.i = i; }
      int intValue() { return i; }
      public boolean less(OrdInt o) { return i < o.intValue(); }
    }
    // test code follows
      Pair_OrdInt p = new Pair_OrdInt(new OrdInt(22), new OrdInt(64));
      System.out.println(p.min().intValue()); // prints 22

Exercise: what is the homogeneous translation of this program?

---

END

---