Subtype: A is a subtype of B if every object of type A is also a B,
         i.e., every object of type A has
               (1) all of the data members of B'
               (2) supports all of the operations supported by B,
                   with the operations taking the same argument types
                   and returning the same type
               (3) AND these operations and fields have the 
                  "same meaning" in A and B

It is common to view data field accesses as operations in their
own right. In that case, (1) is subsumed by (2) and (3). 

Inheritance is a language mechanism in OO languages that can
be used to implement subtypes. In particular, the notion of 
interface inheritance corresponds (1), (2) and (3) above, with
the provision that (3) is not checked or enforced by a compiler.
Nevertheless, it is a bad programming practice to violate (3).

Note: In the practice OO-programming, "same meaning" (as in (3)) does not
mean that an operation denotes the same mathematical function in
A and B. Instead, "same" is interpreted as "analagous" or "parallel."
For instance, we may have a "draw" operation that is used to display
objects of type DrawableObject, but the actual figures drawn by
this method will be quite different for different subclasses such
as Circle and Square. 

Based on the above discussion, it follows that the notion of subtyping
and interface inheritance coincide in OO languages. Another way to
phrase this is to say that "interface inheritance captures an
`is-a' relationsship." In otherwords, if A inherits B's interface,
then it must be the case that every A is a B. As mentioned before,
interface inheritance enables reuse of client code: in particular,
code that operates on objects of type B can continue to be used
on objects of type A without amy change. (Recall the "refresh"
function in the graphics editor example.)

A different notion of inheritance supported in OO-languages is
implementation inheritance. If A is implemented using B, then we that
there is an implementation inheritance relationship between A and B. Note,
however, that A need not support any of the operation supported by B. In
otherwords, the use of B in A's implementation is purely based on
convenience, and not because of any similarities among the semantics of A
and B. Specifically, there is no is-a relationship between the two
classes. As such, implementation inheritance does not help in reuse of
client code -- implementation inheritance is thus "irrelevant" from the
point of view of client code. For this reason, private inheritance in C++
corresponds to implementation-only inheritance, while public inheritance
provides both implementation and interface inheritance.

Since implementation-only inheritance is invisible outside a class,
it is not as useful as interface inheritance. In particular, we can
simulate implementation-only inheritance using composition. For instance,
consider the following example:

class B {
  op1(...)
  op2(...)
}

class A: private class B {
  op1(...) /* Some operations supported in B may also be supported by A */
  op3(...) /* New operations supported by A */
}

Now, since the inheritance is invisible to clients of A, they cannot 
access the op1 operation supported by B. They can only access op1
supported by A. More concretely, this means that even if A wishes to
reuse op1's implementation provided by B, it cannot do this implicitly.
Instead, the implementation of op1 in A has to explicitly invoke the
implementation of op1 in B:

A::op1(...) {
    B::op1(...)
}

For this reason, we can simulate implementation inheritance using 
composition as follows:

class A' {
      B b;
      op1(...) {
        b.op1(...)
      }
      op3(...)
}

As such, implementation-only inheritance is not very useful, and has been
eliminated in Java. From a practitioner's view, use of implementation-only
inheritance is unusual. When it occurs, it is often a mistake, and 
composition would have been more appropriate.

Parametric polymorphism Vs Interface Inheritance
-------------------------------------------------

In C++, template classes support parametric polymorphism, while 
public inheritance support interface+implementation inheritance.
Parametric polymorphism is more flexible in many cases. For instance,
consider the design of a list class using template types. We can
do this by:

template class List<class ElemType> {
 private:
   ElemType *first;
   List<ElemType> *next;
 public:
   ElemType *get();
   void insert(ElemType *e);
   ...
}

Now, one can use the List class with any element type:

void f(List<A> alist, List<B> blist) {
     A a = alist.get();
     B b = blist.get();
     ....
}

Note that the variable a's type can be statically determined to 
be A, and appropriate typechecking performed at compile time.
While subtype polymorphism can support the definition of a List
class, this type-checking ability is lost. In more detail: To
use subtype polymorphism, we need to have a common base class 
for A and B, and define a List class that contains objects of 
this type. Specifically, in Java, we do this by making all
objects derive from a base class called Object:

class AltList {
 private:
  Object first; // Note: all object fields really denote pointers
  AltList next; // in java
 public:
  Object get();
  void insert(Object o);
}

void f(AltList alist, AltList blist) {
  A a = (A)alist.get();
  B b = (B)blist.get();
  ...
}

Note that in this case, the operation alist.get() returns an
object of type Object, not A. We therefore need to explicitly cast it into
an object of type A or B as appropriate. Moroever, the type-correctness
of this casting cannot be verified until runtime. This leads to
two problems: (a) type-checking needs to be done at runtime, and
type info maintained at runtime, (b) potential errors, as in the following
code, cannot be caught at compile time

List alist, blist;
A a; A b; // Note b is of type A, not B
alist.insert(a);
blist.insert(b);
f(alist, blist); // f expects second arg to be list of B's, but we are
                 // giving a list of A's.

Overloading, Overriding, and Virtual Functions
-----------------------------------------------

Overloading is the ability to use the same function NAME with 
different arguments to denote DIFFERENT functions. In C++, for
instance, once can define:

void add(int a, int b, int& c);
void add(float a, float b, float& c);

Overriding refers to the fact that an implementation of a method
in a subclass supercedes the implementation of the same method in 
the base class. 

OVERRIDING OF NON-VIRTUAL FUNCTIONS IN C++

For instance:

class B {
   ...
 public:
   void op1(int i) {
     /* B's implementation of op1 */
   }
   ...
}

class A: public class B {
   ...
 public: 
   void op1(int i) {
     /* A's implementation of op1 */
   }
   ...
}

main() {
  B b;
  A a;
  int i = 5;
  b.op1(i); // B's implementation of op1 is used
  a.op1(i); // Although every A is a B, and hence B's implementation of
            // op1 is available to A, A's definition supercedes B's defn,
            // so we are using A's implementation of op1.

  ((B)a).op1(); // Now that a has been cast into a B, B's op1 applies.
  a.B::op1();   // Explicitly calling B's implementation of op1
}

One thing to note in the above example is that the choice of B's or A's
version of op1 to use is based on compile-time type of a variable or
expression. The runtime type is not used. Thus, overriding of method
definitions is based on compile-time type information. This is illustrated
in the following function f,

void f(B x, int i) {
     x.op1(i);
}

which may be invoked as follows:

B b;
A a;
f(b, 1); // f uses B's op1
f(a, 1); // f still uses B's op1, not A's

OVERRIDING IN THE PRESENCE OF VIRTUAL FUNCTION

Use of virtual functions would enable overriding to be based on runtime type
information:

class B {
   ...
 public:
   virtual void op1(int i) {
     /* B's implementation of op1 */
   }
   ...
}

class A: public class B {
   ...
 public: 
   void op1(int i) {// op1 is virtual in base class, so it is virtual here too 
     /* A's implementation of op1 */
   }
   ...
}

main() {
  B b;
  A a;
  int i = 5;
  b.op1(i); // B's implementation of op1 is used
  a.op1(i); // A's implementation of op1 is used.

  ((B)a).op1(); // Although A has been cast into a B, dispatching of
                // virtual function is based on the runtime type info 
                // associated with a. Thus, A's op1 is used. 
                // NOTE difference with nonvirtual case 

  a.B::op1();   // Explicitly calling B's implementation of op1.
                // Disable dynamic dispatching of op1
}

Also, in the second example, things work as expected, based on runtime
type info:

void f(B x, int i) {
     x.op1(i);
}

which may be invoked as follows:

B b;
A a;
f(b, 1); // f uses B's op1
f(a, 1); // f uses A's op1

Note that op1 denotes different funtions in the context of A and B.
Thus, we are overloading the name "op1" with two different meanings.
Reuse of client code, as enabled in OO languages, relies simply
on this fact that the same function name will do the "right thing"
depending on the runtime type.

The right version can be determined using the argument types:
If the object argument is of type A, then we use A's version of
op1, and if it is of type B, then we use B's version of op1.
With nonvirtual functions, the resolution of op1 is done at compile
time, while with virtual functions, resolution is done at runtime.

Implementation Aspects of OO-Languages
---------------------------------------

Allocation of space for data members: The space for data members is 
laid out the same way it is done for structures in C or other languages.
Specifically:
 -- the data members are allocated next to each other
 -- some padding may be required in between fields, if the
    underlying machine architecture requires primitive types to
    be aligned at certain adresses
 -- at runtime, there is no need to look up the name of a field and
    identify the corresponding offset into a structure; instead, we
    can statically translate field names into relative addresses,
    with respect to the beginning of the object.
 -- data members for a derived class immediately follow the data
    members of the base class
 -- multiple inheritance requires more complicated handling, we
    will not discuss it here

Example:

class B {
      int i;
      double d;
      char c;
      float f;
}

Layout of objects of type b:
     ---------------
  0: | int i       | // Assumption: Integer requires 4 bytes
     ---------------
  4: | XXXXXXXXXXX | // pad, assuming double's are to be 
     --------------- // aligned on 8-byte boundaries
  8: | double d    |
     |             | // Assumption: Double requires 8 bytes
     ---------------
 16: | char c|XXXXX| // Assumption: char needs 1 byte, 3 bytes are padded
     ---------------
 20: | float f     | // Assumption: float to be aligned on 4-byte boundaries,
     --------------- // and require 4-bytes of space.

class C {
  int k, l;
  B b;
}

     ---------------
  0: | int k       |
     ---------------
  4: | int l       |
     ---------------
  8: | int i       |
     ---------------
 12: | XXXXXXXXXXX |
     ---------------
 16: | double d    |
     |             |
     ---------------
 24: | char c|XXXXX|
     ---------------
 28: | float f     |
     ---------------

class D: public C {
   double x;
}

     ---------------
  0: | int k       |
     ---------------
  4: | int l       |
     ---------------
  8: | int i       |
     ---------------
 12: | XXXXXXXXXXX |
     ---------------
 16: | double d    |
     |             |
     ---------------
 24: | char c|XXXXX|
     ---------------
 28: | float f     |
     ---------------
 32: | double x    |
     |             |
     ---------------