Expertiza_Wiki - User contributions [en]

CSC/ECE 517 Fall 2010/ch5 5c gn

2010-11-03T01:38:04Z

Cgoogc:

='''Dynamic Dispatch'''=

This wiki-page serves as a knowledge source for understanding the concept of Dynamic Dispatch in OOLS. Here we will make an effort to address the efficiency considerations about Dynamic Dispatch, advantages of Dynamic Dispatch using parameter types and dynamic binding in CLOS (Common Lisp Object System).<br>

__TOC__

=Introduction=
Dynamic Dispatch is the process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. It is generally used in <b>Object-Oriented Language</b> (OOL) <sup>[http://en.wikipedia.org/wiki/Object-oriented_programming]</sup>. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called as <b>Method Overriding</b> <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup>). When a reference to the super class is used to execute that function, then which version of the function gets executed depends on the type, the reference to which it points to at that time rather than the type of the reference. In literature it also referred to in different names like <b>Runtime Binding</b> or <b>Dynamic Polymorphism</b>. <sup>[http://en.wikipedia.org/wiki/Dynamic_polymorphism]</sup>

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

==Need for Dynamic Dispatch==
Dynamic Dispatch is one of the inherent feature of an Object-Oriented Language <sup>[http://en.wikipedia.org/wiki/Dynamic_polymorphism]</sup>. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

==How Dynamic Dispatch works?==
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment <sup>[http://en.wikipedia.org/wiki/Code_segment]</sup> area of the process image. So a function in C will just map to a memory location in Code Segment of the process image. For example calling a function 'print()', might be converted to something like 'jmp 0xFFDE123' (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal (not shown here) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.

A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementations are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to an equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable (Virtual Method Table <sup>[http://en.wikipedia.org/wiki/Virtual_method_table]</sup>) which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be changed like this by the compiler
Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

<div style="text-align: center;"> Fig.1 - VTable Working </div>

<br>
Virtual Method table or vtable or dispatch table [5] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=Performance Evaluation=
From the above explanation it is evident that Virtual functions <sup>[http://en.wikipedia.org/wiki/Virtual_function] [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm]</sup> are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the Virtual method table [5] and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reasons why not all functions are dynamically binded in C++. In C++, functions which are explicitly marked virtual are dynamically bound whereas remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, hence, all functions are dynamically bound. It is also reasonable to assume that virtual functions might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

We performed a very small experiment to see if Dynamic dispatch is practically slower than static dispatch. We opted to choose C#, since this language provide both static binding and dynamic binding. We measured the time taken to execute 1000000000 dynamically dispatched functions and statically dispatched functions. Below are our observations.

Dynamic Dispatch:
00:00:10.0995777
00:00:10.4315966
00:00:10.4675987

Static Dispatch:
00:00:10.2565866
00:00:10.3255906
00:00:10.1575809

It looks like the performance overhead of dynamic binding is negligible in today's high performing computer. Even if it Dynamic Binding needs few more instruction to perform function call, the overhead in terms of time and memory is not much of a concern, but effective software design is a matter of concern. So we can conclude that Dynamic Binding does not cause serious performance problem in present day Computers.

==Overriding and Overloading==
Overriding <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup> and Overloading <sup>[http://en.wikipedia.org/wiki/Method_overloading]</sup> are two different features of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version of the function to call is deferred till runtime.

Let us see an two examples which provides insight into Overriding and Overloading.

Example - 1: Overloading

public class A{
public boolean equals( A check){ # Equals method of parameter type A
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # Object equals method called
a2.equals(a1); # Object equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # Object equals method called
}
}

Example - 2: Overriding

public class A{
@Override
public boolean equals( Object check){ # Equals method of parameter type Object
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # A equals method called
a2.equals(a1); # A equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # A equals method called
}
}

If you see the comments provided to the side of the method calls, you would note the difference in the equals method called in case of both Overloading and Overriding. The decision which method to use, basically has two phases: First overload resolution, then method dispatch. Overload resolution happens at compile-time, method dispatch at runtime.

==Does Dynamic Dispatching hurts in today's power packed Computers?==

Even though Dynamic Dispatching is done in run-time, and it takes good amount of memory, today's computers are power packed with good amount of memory. Hence efficiency concerns for implementing Dynamic Dispatching in OOL is of little concern.

However, the method to be called cannot be chosen based on the actual arguments passed to the function, rather, the method is called based on the declared type of the parameters.

=Advantages of Dynamic Binding=

Dynamic binding has several advantages. It provides tremendous flexibilities. Also, it allows the software to be malleable when requirements change as the system evolves. Because of dynamic binding, caller objects are not concerned how the invoked objects carry out their methods. All they need to know is that the invoked objects know how to carry out their responsibilities, but they themselves need to know only what the invoked objects can do for them. As a consequence of this, type dependencies (which are the bane of procedural programming) cannot have a ripple effect through the system, when system requirements change. The beauty is that such dependencies remain encapsulated within the objects. The flexibility that developers can derive out of this is enormous. For instance, one can install newer types without having to change or stopping the functioning of existing systems. This is something along the lines of "hot pluggable components" of the hardware cousins.

One other advantage of Dynamic binding based on parameter types is that more than one parameter can be used in the selection of a method. Methods that use dynamic binding in this way are called multi-methods and the concept is called <b>Multiple Dispatch</b> <sup>[http://en.wikipedia.org/wiki/Multiple_dispatch]</sup>.

==Multiple Dispatch==

The Multiple Dispatch is used in Common Lisp Object System (CLOS) <sup>[http://en.wikipedia.org/wiki/Common_Lisp_Object_System]</sup>. Multiple-polymorphism allows specialized functions or methods to be defined to handle various cases:

+(int, int)
+(int, float)
+(int, complex) .. etc

The above functions are specialized to each of the cases required allowing single, highly cohesive and loosely coupled functions to be defined. This is also the true essence of object-oriented polymorphism, which allows objects to define methods for each specific case desired. In addition to better coupling and cohesion, multiple-polymorphism reduces program complexity by avoiding coding logic (switch statements) and because small methods further reduce complexity, as code complexity doesn't grow linearly with lines of code per method, but perhaps exponentially.

=Conclusion=

Hence from the above discussion, we can see that Dynamic Dispatch, though slower when compared to static dispatch is no longer slower due to the new generation of power packed computers. Also, dynamic dispatch can help in preserving the object-oriented concepts in highly complex software products. We have also looked up the differences between method Overloading and Overriding. We also had a sneak-view to Multiple Dispatch where more than one parameter can be used for Dynamic method lookup.

=References=
# [http://en.wikipedia.org/wiki/Object-oriented_programming Object Oriented Programming]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overriding Method Overriding]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Code_segment Code Segment]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_method_table Virtual Method Table]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_function Virtual Functions]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm Virtual Functions in C++]. publib.boulder.ibm.com. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overloading Method Overloading]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Multiple_dispatch Multiple Dispatch]. en.wikipedia.org. Retrieved Oct 31, 2010.

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-11-03T01:35:09Z

Cgoogc: /* Need for Dynamic Dispatch */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-11-03T01:33:57Z

Cgoogc: /* '''Dynamic Dispatch''' */

='''Dynamic Dispatch'''=

This wiki-page serves as a knowledge source for understanding the concept of Dynamic Dispatch in OOLS. Here we will make an effort to address the efficiency considerations about Dynamic Dispatch, advantages of Dynamic Dispatch using parameter types and dynamic binding in CLOS (Common Lisp Object System).<br>

__TOC__

=Introduction=
Dynamic Dispatch is the process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. It is generally used in <b>Object-Oriented Language</b> (OOL) <sup>[http://en.wikipedia.org/wiki/Object-oriented_programming]</sup>. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called as <b>Method Overriding</b> <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup>). When a reference to the super class is used to execute that function, then which version of the function gets executed depends on the type, the reference to which it points to at that time rather than the type of the reference. In literature it also referred to in different names like <b>Runtime Binding</b> or <b>Dynamic Polymorphism</b>. <sup>[http://en.wikipedia.org/wiki/Dynamic_polymorphism]</sup>

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

==Need for Dynamic Dispatch==
Dynamic Dispatch is one of the inherent feature of an Object-Oriented Language [1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

==How Dynamic Dispatch works?==
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment <sup>[http://en.wikipedia.org/wiki/Code_segment]</sup> area of the process image. So a function in C will just map to a memory location in Code Segment of the process image. For example calling a function 'print()', might be converted to something like 'jmp 0xFFDE123' (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal (not shown here) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.

A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementations are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to an equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable (Virtual Method Table <sup>[http://en.wikipedia.org/wiki/Virtual_method_table]</sup>) which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be changed like this by the compiler
Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

<div style="text-align: center;"> Fig.1 - VTable Working </div>

<br>
Virtual Method table or vtable or dispatch table [5] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=Performance Evaluation=
From the above explanation it is evident that Virtual functions <sup>[http://en.wikipedia.org/wiki/Virtual_function] [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm]</sup> are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the Virtual method table [5] and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reasons why not all functions are dynamically binded in C++. In C++, functions which are explicitly marked virtual are dynamically bound whereas remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, hence, all functions are dynamically bound. It is also reasonable to assume that virtual functions might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

We performed a very small experiment to see if Dynamic dispatch is practically slower than static dispatch. We opted to choose C#, since this language provide both static binding and dynamic binding. We measured the time taken to execute 1000000000 dynamically dispatched functions and statically dispatched functions. Below are our observations.

Dynamic Dispatch:
00:00:10.0995777
00:00:10.4315966
00:00:10.4675987

Static Dispatch:
00:00:10.2565866
00:00:10.3255906
00:00:10.1575809

It looks like the performance overhead of dynamic binding is negligible in today's high performing computer. Even if it Dynamic Binding needs few more instruction to perform function call, the overhead in terms of time and memory is not much of a concern, but effective software design is a matter of concern. So we can conclude that Dynamic Binding does not cause serious performance problem in present day Computers.

==Overriding and Overloading==
Overriding <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup> and Overloading <sup>[http://en.wikipedia.org/wiki/Method_overloading]</sup> are two different features of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version of the function to call is deferred till runtime.

Let us see an two examples which provides insight into Overriding and Overloading.

Example - 1: Overloading

public class A{
public boolean equals( A check){ # Equals method of parameter type A
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # Object equals method called
a2.equals(a1); # Object equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # Object equals method called
}
}

Example - 2: Overriding

public class A{
@Override
public boolean equals( Object check){ # Equals method of parameter type Object
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # A equals method called
a2.equals(a1); # A equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # A equals method called
}
}

If you see the comments provided to the side of the method calls, you would note the difference in the equals method called in case of both Overloading and Overriding. The decision which method to use, basically has two phases: First overload resolution, then method dispatch. Overload resolution happens at compile-time, method dispatch at runtime.

==Does Dynamic Dispatching hurts in today's power packed Computers?==

Even though Dynamic Dispatching is done in run-time, and it takes good amount of memory, today's computers are power packed with good amount of memory. Hence efficiency concerns for implementing Dynamic Dispatching in OOL is of little concern.

However, the method to be called cannot be chosen based on the actual arguments passed to the function, rather, the method is called based on the declared type of the parameters.

=Advantages of Dynamic Binding=

Dynamic binding has several advantages. It provides tremendous flexibilities. Also, it allows the software to be malleable when requirements change as the system evolves. Because of dynamic binding, caller objects are not concerned how the invoked objects carry out their methods. All they need to know is that the invoked objects know how to carry out their responsibilities, but they themselves need to know only what the invoked objects can do for them. As a consequence of this, type dependencies (which are the bane of procedural programming) cannot have a ripple effect through the system, when system requirements change. The beauty is that such dependencies remain encapsulated within the objects. The flexibility that developers can derive out of this is enormous. For instance, one can install newer types without having to change or stopping the functioning of existing systems. This is something along the lines of "hot pluggable components" of the hardware cousins.

One other advantage of Dynamic binding based on parameter types is that more than one parameter can be used in the selection of a method. Methods that use dynamic binding in this way are called multi-methods and the concept is called <b>Multiple Dispatch</b> <sup>[http://en.wikipedia.org/wiki/Multiple_dispatch]</sup>.

==Multiple Dispatch==

The Multiple Dispatch is used in Common Lisp Object System (CLOS) <sup>[http://en.wikipedia.org/wiki/Common_Lisp_Object_System]</sup>. Multiple-polymorphism allows specialized functions or methods to be defined to handle various cases:

+(int, int)
+(int, float)
+(int, complex) .. etc

The above functions are specialized to each of the cases required allowing single, highly cohesive and loosely coupled functions to be defined. This is also the true essence of object-oriented polymorphism, which allows objects to define methods for each specific case desired. In addition to better coupling and cohesion, multiple-polymorphism reduces program complexity by avoiding coding logic (switch statements) and because small methods further reduce complexity, as code complexity doesn't grow linearly with lines of code per method, but perhaps exponentially.

=Conclusion=

Hence from the above discussion, we can see that Dynamic Dispatch, though slower when compared to static dispatch is no longer slower due to the new generation of power packed computers. Also, dynamic dispatch can help in preserving the object-oriented concepts in highly complex software products. We have also looked up the differences between method Overloading and Overriding. We also had a sneak-view to Multiple Dispatch where more than one parameter can be used for Dynamic method lookup.

=References=
# [http://en.wikipedia.org/wiki/Object-oriented_programming Object Oriented Programming]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overriding Method Overriding]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Code_segment Code Segment]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_method_table Virtual Method Table]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_function Virtual Functions]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm Virtual Functions in C++]. publib.boulder.ibm.com. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overloading Method Overloading]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Multiple_dispatch Multiple Dispatch]. en.wikipedia.org. Retrieved Oct 31, 2010.

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-11-03T01:33:05Z

Cgoogc: /* Further Reading */

='''Dynamic Dispatch'''=

This wiki-page serves as a knowledge source for understanding the concept of Dynamic Dispatch in Computer Science. Here we will make an effort to address the efficiency considerations about Dynamic Dispatch, advantages of Dynamic Dispatch using parameter types and dynamic binding in CLOS (Common Lisp Object System).<br>

__TOC__

=Introduction=
Dynamic Dispatch is the process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. It is generally used in <b>Object-Oriented Language</b> (OOL) <sup>[http://en.wikipedia.org/wiki/Object-oriented_programming]</sup>. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called as <b>Method Overriding</b> <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup>). When a reference to the super class is used to execute that function, then which version of the function gets executed depends on the type, the reference to which it points to at that time rather than the type of the reference. In literature it also referred to in different names like <b>Runtime Binding</b> or <b>Dynamic Polymorphism</b>. <sup>[http://en.wikipedia.org/wiki/Dynamic_polymorphism]</sup>

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

==Need for Dynamic Dispatch==
Dynamic Dispatch is one of the inherent feature of an Object-Oriented Language [1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

==How Dynamic Dispatch works?==
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment <sup>[http://en.wikipedia.org/wiki/Code_segment]</sup> area of the process image. So a function in C will just map to a memory location in Code Segment of the process image. For example calling a function 'print()', might be converted to something like 'jmp 0xFFDE123' (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal (not shown here) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.

A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementations are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to an equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable (Virtual Method Table <sup>[http://en.wikipedia.org/wiki/Virtual_method_table]</sup>) which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be changed like this by the compiler
Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

<div style="text-align: center;"> Fig.1 - VTable Working </div>

<br>
Virtual Method table or vtable or dispatch table [5] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=Performance Evaluation=
From the above explanation it is evident that Virtual functions <sup>[http://en.wikipedia.org/wiki/Virtual_function] [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm]</sup> are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the Virtual method table [5] and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reasons why not all functions are dynamically binded in C++. In C++, functions which are explicitly marked virtual are dynamically bound whereas remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, hence, all functions are dynamically bound. It is also reasonable to assume that virtual functions might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

We performed a very small experiment to see if Dynamic dispatch is practically slower than static dispatch. We opted to choose C#, since this language provide both static binding and dynamic binding. We measured the time taken to execute 1000000000 dynamically dispatched functions and statically dispatched functions. Below are our observations.

Dynamic Dispatch:
00:00:10.0995777
00:00:10.4315966
00:00:10.4675987

Static Dispatch:
00:00:10.2565866
00:00:10.3255906
00:00:10.1575809

It looks like the performance overhead of dynamic binding is negligible in today's high performing computer. Even if it Dynamic Binding needs few more instruction to perform function call, the overhead in terms of time and memory is not much of a concern, but effective software design is a matter of concern. So we can conclude that Dynamic Binding does not cause serious performance problem in present day Computers.

==Overriding and Overloading==
Overriding <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup> and Overloading <sup>[http://en.wikipedia.org/wiki/Method_overloading]</sup> are two different features of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version of the function to call is deferred till runtime.

Let us see an two examples which provides insight into Overriding and Overloading.

Example - 1: Overloading

public class A{
public boolean equals( A check){ # Equals method of parameter type A
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # Object equals method called
a2.equals(a1); # Object equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # Object equals method called
}
}

Example - 2: Overriding

public class A{
@Override
public boolean equals( Object check){ # Equals method of parameter type Object
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # A equals method called
a2.equals(a1); # A equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # A equals method called
}
}

If you see the comments provided to the side of the method calls, you would note the difference in the equals method called in case of both Overloading and Overriding. The decision which method to use, basically has two phases: First overload resolution, then method dispatch. Overload resolution happens at compile-time, method dispatch at runtime.

==Does Dynamic Dispatching hurts in today's power packed Computers?==

Even though Dynamic Dispatching is done in run-time, and it takes good amount of memory, today's computers are power packed with good amount of memory. Hence efficiency concerns for implementing Dynamic Dispatching in OOL is of little concern.

However, the method to be called cannot be chosen based on the actual arguments passed to the function, rather, the method is called based on the declared type of the parameters.

=Advantages of Dynamic Binding=

Dynamic binding has several advantages. It provides tremendous flexibilities. Also, it allows the software to be malleable when requirements change as the system evolves. Because of dynamic binding, caller objects are not concerned how the invoked objects carry out their methods. All they need to know is that the invoked objects know how to carry out their responsibilities, but they themselves need to know only what the invoked objects can do for them. As a consequence of this, type dependencies (which are the bane of procedural programming) cannot have a ripple effect through the system, when system requirements change. The beauty is that such dependencies remain encapsulated within the objects. The flexibility that developers can derive out of this is enormous. For instance, one can install newer types without having to change or stopping the functioning of existing systems. This is something along the lines of "hot pluggable components" of the hardware cousins.

One other advantage of Dynamic binding based on parameter types is that more than one parameter can be used in the selection of a method. Methods that use dynamic binding in this way are called multi-methods and the concept is called <b>Multiple Dispatch</b> <sup>[http://en.wikipedia.org/wiki/Multiple_dispatch]</sup>.

==Multiple Dispatch==

The Multiple Dispatch is used in Common Lisp Object System (CLOS) <sup>[http://en.wikipedia.org/wiki/Common_Lisp_Object_System]</sup>. Multiple-polymorphism allows specialized functions or methods to be defined to handle various cases:

+(int, int)
+(int, float)
+(int, complex) .. etc

The above functions are specialized to each of the cases required allowing single, highly cohesive and loosely coupled functions to be defined. This is also the true essence of object-oriented polymorphism, which allows objects to define methods for each specific case desired. In addition to better coupling and cohesion, multiple-polymorphism reduces program complexity by avoiding coding logic (switch statements) and because small methods further reduce complexity, as code complexity doesn't grow linearly with lines of code per method, but perhaps exponentially.

=Conclusion=

Hence from the above discussion, we can see that Dynamic Dispatch, though slower when compared to static dispatch is no longer slower due to the new generation of power packed computers. Also, dynamic dispatch can help in preserving the object-oriented concepts in highly complex software products. We have also looked up the differences between method Overloading and Overriding. We also had a sneak-view to Multiple Dispatch where more than one parameter can be used for Dynamic method lookup.

=References=
# [http://en.wikipedia.org/wiki/Object-oriented_programming Object Oriented Programming]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overriding Method Overriding]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Code_segment Code Segment]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_method_table Virtual Method Table]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_function Virtual Functions]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm Virtual Functions in C++]. publib.boulder.ibm.com. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overloading Method Overloading]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Multiple_dispatch Multiple Dispatch]. en.wikipedia.org. Retrieved Oct 31, 2010.

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-11-03T01:32:14Z

Cgoogc: /* Overriding and Overloading */

='''Dynamic Dispatch'''=

This wiki-page serves as a knowledge source for understanding the concept of Dynamic Dispatch in Computer Science. Here we will make an effort to address the efficiency considerations about Dynamic Dispatch, advantages of Dynamic Dispatch using parameter types and dynamic binding in CLOS (Common Lisp Object System).<br>

__TOC__

=Introduction=
Dynamic Dispatch is the process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. It is generally used in <b>Object-Oriented Language</b> (OOL) <sup>[http://en.wikipedia.org/wiki/Object-oriented_programming]</sup>. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called as <b>Method Overriding</b> <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup>). When a reference to the super class is used to execute that function, then which version of the function gets executed depends on the type, the reference to which it points to at that time rather than the type of the reference. In literature it also referred to in different names like <b>Runtime Binding</b> or <b>Dynamic Polymorphism</b>. <sup>[http://en.wikipedia.org/wiki/Dynamic_polymorphism]</sup>

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

==Need for Dynamic Dispatch==
Dynamic Dispatch is one of the inherent feature of an Object-Oriented Language [1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

==How Dynamic Dispatch works?==
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment <sup>[http://en.wikipedia.org/wiki/Code_segment]</sup> area of the process image. So a function in C will just map to a memory location in Code Segment of the process image. For example calling a function 'print()', might be converted to something like 'jmp 0xFFDE123' (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal (not shown here) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.

A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementations are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to an equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable (Virtual Method Table <sup>[http://en.wikipedia.org/wiki/Virtual_method_table]</sup>) which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be changed like this by the compiler
Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

<div style="text-align: center;"> Fig.1 - VTable Working </div>

<br>
Virtual Method table or vtable or dispatch table [5] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=Performance Evaluation=
From the above explanation it is evident that Virtual functions <sup>[http://en.wikipedia.org/wiki/Virtual_function] [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm]</sup> are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the Virtual method table [5] and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reasons why not all functions are dynamically binded in C++. In C++, functions which are explicitly marked virtual are dynamically bound whereas remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, hence, all functions are dynamically bound. It is also reasonable to assume that virtual functions might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

We performed a very small experiment to see if Dynamic dispatch is practically slower than static dispatch. We opted to choose C#, since this language provide both static binding and dynamic binding. We measured the time taken to execute 1000000000 dynamically dispatched functions and statically dispatched functions. Below are our observations.

Dynamic Dispatch:
00:00:10.0995777
00:00:10.4315966
00:00:10.4675987

Static Dispatch:
00:00:10.2565866
00:00:10.3255906
00:00:10.1575809

It looks like the performance overhead of dynamic binding is negligible in today's high performing computer. Even if it Dynamic Binding needs few more instruction to perform function call, the overhead in terms of time and memory is not much of a concern, but effective software design is a matter of concern. So we can conclude that Dynamic Binding does not cause serious performance problem in present day Computers.

==Overriding and Overloading==
Overriding <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup> and Overloading <sup>[http://en.wikipedia.org/wiki/Method_overloading]</sup> are two different features of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version of the function to call is deferred till runtime.

Let us see an two examples which provides insight into Overriding and Overloading.

Example - 1: Overloading

public class A{
public boolean equals( A check){ # Equals method of parameter type A
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # Object equals method called
a2.equals(a1); # Object equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # Object equals method called
}
}

Example - 2: Overriding

public class A{
@Override
public boolean equals( Object check){ # Equals method of parameter type Object
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # A equals method called
a2.equals(a1); # A equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # A equals method called
}
}

If you see the comments provided to the side of the method calls, you would note the difference in the equals method called in case of both Overloading and Overriding. The decision which method to use, basically has two phases: First overload resolution, then method dispatch. Overload resolution happens at compile-time, method dispatch at runtime.

==Does Dynamic Dispatching hurts in today's power packed Computers?==

Even though Dynamic Dispatching is done in run-time, and it takes good amount of memory, today's computers are power packed with good amount of memory. Hence efficiency concerns for implementing Dynamic Dispatching in OOL is of little concern.

However, the method to be called cannot be chosen based on the actual arguments passed to the function, rather, the method is called based on the declared type of the parameters.

=Advantages of Dynamic Binding=

Dynamic binding has several advantages. It provides tremendous flexibilities. Also, it allows the software to be malleable when requirements change as the system evolves. Because of dynamic binding, caller objects are not concerned how the invoked objects carry out their methods. All they need to know is that the invoked objects know how to carry out their responsibilities, but they themselves need to know only what the invoked objects can do for them. As a consequence of this, type dependencies (which are the bane of procedural programming) cannot have a ripple effect through the system, when system requirements change. The beauty is that such dependencies remain encapsulated within the objects. The flexibility that developers can derive out of this is enormous. For instance, one can install newer types without having to change or stopping the functioning of existing systems. This is something along the lines of "hot pluggable components" of the hardware cousins.

One other advantage of Dynamic binding based on parameter types is that more than one parameter can be used in the selection of a method. Methods that use dynamic binding in this way are called multi-methods and the concept is called <b>Multiple Dispatch</b> <sup>[http://en.wikipedia.org/wiki/Multiple_dispatch]</sup>.

==Multiple Dispatch==

The Multiple Dispatch is used in Common Lisp Object System (CLOS) <sup>[http://en.wikipedia.org/wiki/Common_Lisp_Object_System]</sup>. Multiple-polymorphism allows specialized functions or methods to be defined to handle various cases:

+(int, int)
+(int, float)
+(int, complex) .. etc

The above functions are specialized to each of the cases required allowing single, highly cohesive and loosely coupled functions to be defined. This is also the true essence of object-oriented polymorphism, which allows objects to define methods for each specific case desired. In addition to better coupling and cohesion, multiple-polymorphism reduces program complexity by avoiding coding logic (switch statements) and because small methods further reduce complexity, as code complexity doesn't grow linearly with lines of code per method, but perhaps exponentially.

=Conclusion=

Hence from the above discussion, we can see that Dynamic Dispatch, though slower when compared to static dispatch is no longer slower due to the new generation of power packed computers. Also, dynamic dispatch can help in preserving the object-oriented concepts in highly complex software products. We have also looked up the differences between method Overloading and Overriding. We also had a sneak-view to Multiple Dispatch where more than one parameter can be used for Dynamic method lookup.

=Further Reading=

=References=
# [http://en.wikipedia.org/wiki/Object-oriented_programming Object Oriented Programming]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overriding Method Overriding]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Code_segment Code Segment]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_method_table Virtual Method Table]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_function Virtual Functions]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm Virtual Functions in C++]. publib.boulder.ibm.com. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overloading Method Overloading]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Multiple_dispatch Multiple Dispatch]. en.wikipedia.org. Retrieved Oct 31, 2010.

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-11-03T01:31:27Z

Cgoogc: /* Performance Evaluation */

='''Dynamic Dispatch'''=

This wiki-page serves as a knowledge source for understanding the concept of Dynamic Dispatch in Computer Science. Here we will make an effort to address the efficiency considerations about Dynamic Dispatch, advantages of Dynamic Dispatch using parameter types and dynamic binding in CLOS (Common Lisp Object System).<br>

__TOC__

=Introduction=
Dynamic Dispatch is the process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. It is generally used in <b>Object-Oriented Language</b> (OOL) <sup>[http://en.wikipedia.org/wiki/Object-oriented_programming]</sup>. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called as <b>Method Overriding</b> <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup>). When a reference to the super class is used to execute that function, then which version of the function gets executed depends on the type, the reference to which it points to at that time rather than the type of the reference. In literature it also referred to in different names like <b>Runtime Binding</b> or <b>Dynamic Polymorphism</b>. <sup>[http://en.wikipedia.org/wiki/Dynamic_polymorphism]</sup>

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

==Need for Dynamic Dispatch==
Dynamic Dispatch is one of the inherent feature of an Object-Oriented Language [1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

==How Dynamic Dispatch works?==
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment <sup>[http://en.wikipedia.org/wiki/Code_segment]</sup> area of the process image. So a function in C will just map to a memory location in Code Segment of the process image. For example calling a function 'print()', might be converted to something like 'jmp 0xFFDE123' (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal (not shown here) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.

A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementations are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to an equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable (Virtual Method Table <sup>[http://en.wikipedia.org/wiki/Virtual_method_table]</sup>) which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be changed like this by the compiler
Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

<div style="text-align: center;"> Fig.1 - VTable Working </div>

<br>
Virtual Method table or vtable or dispatch table [5] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=Performance Evaluation=
From the above explanation it is evident that Virtual functions <sup>[http://en.wikipedia.org/wiki/Virtual_function] [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm]</sup> are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the Virtual method table [5] and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reasons why not all functions are dynamically binded in C++. In C++, functions which are explicitly marked virtual are dynamically bound whereas remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, hence, all functions are dynamically bound. It is also reasonable to assume that virtual functions might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

We performed a very small experiment to see if Dynamic dispatch is practically slower than static dispatch. We opted to choose C#, since this language provide both static binding and dynamic binding. We measured the time taken to execute 1000000000 dynamically dispatched functions and statically dispatched functions. Below are our observations.

Dynamic Dispatch:
00:00:10.0995777
00:00:10.4315966
00:00:10.4675987

Static Dispatch:
00:00:10.2565866
00:00:10.3255906
00:00:10.1575809

It looks like the performance overhead of dynamic binding is negligible in today's high performing computer. Even if it Dynamic Binding needs few more instruction to perform function call, the overhead in terms of time and memory is not much of a concern, but effective software design is a matter of concern. So we can conclude that Dynamic Binding does not cause serious performance problem in present day Computers.

==Overriding and Overloading==
Overriding [2] and Overloading <sup>[http://en.wikipedia.org/wiki/Method_overloading]</sup> are two different features of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version of the function to call is deferred till runtime.

Let us see an two examples which provides insight into Overriding and Overloading.

Example - 1: Overloading

public class A{
public boolean equals( A check){ # Equals method of parameter type A
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # Object equals method called
a2.equals(a1); # Object equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # Object equals method called
}
}

Example - 2: Overriding

public class A{
@Override
public boolean equals( Object check){ # Equals method of parameter type Object
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # A equals method called
a2.equals(a1); # A equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # A equals method called
}
}

If you see the comments provided to the side of the method calls, you would note the difference in the equals method called in case of both Overloading and Overriding. The decision which method to use, basically has two phases: First overload resolution, then method dispatch. Overload resolution happens at compile-time, method dispatch at runtime.

==Does Dynamic Dispatching hurts in today's power packed Computers?==

Even though Dynamic Dispatching is done in run-time, and it takes good amount of memory, today's computers are power packed with good amount of memory. Hence efficiency concerns for implementing Dynamic Dispatching in OOL is of little concern.

However, the method to be called cannot be chosen based on the actual arguments passed to the function, rather, the method is called based on the declared type of the parameters.

=Advantages of Dynamic Binding=

Dynamic binding has several advantages. It provides tremendous flexibilities. Also, it allows the software to be malleable when requirements change as the system evolves. Because of dynamic binding, caller objects are not concerned how the invoked objects carry out their methods. All they need to know is that the invoked objects know how to carry out their responsibilities, but they themselves need to know only what the invoked objects can do for them. As a consequence of this, type dependencies (which are the bane of procedural programming) cannot have a ripple effect through the system, when system requirements change. The beauty is that such dependencies remain encapsulated within the objects. The flexibility that developers can derive out of this is enormous. For instance, one can install newer types without having to change or stopping the functioning of existing systems. This is something along the lines of "hot pluggable components" of the hardware cousins.

One other advantage of Dynamic binding based on parameter types is that more than one parameter can be used in the selection of a method. Methods that use dynamic binding in this way are called multi-methods and the concept is called <b>Multiple Dispatch</b> <sup>[http://en.wikipedia.org/wiki/Multiple_dispatch]</sup>.

==Multiple Dispatch==

The Multiple Dispatch is used in Common Lisp Object System (CLOS) <sup>[http://en.wikipedia.org/wiki/Common_Lisp_Object_System]</sup>. Multiple-polymorphism allows specialized functions or methods to be defined to handle various cases:

+(int, int)
+(int, float)
+(int, complex) .. etc

The above functions are specialized to each of the cases required allowing single, highly cohesive and loosely coupled functions to be defined. This is also the true essence of object-oriented polymorphism, which allows objects to define methods for each specific case desired. In addition to better coupling and cohesion, multiple-polymorphism reduces program complexity by avoiding coding logic (switch statements) and because small methods further reduce complexity, as code complexity doesn't grow linearly with lines of code per method, but perhaps exponentially.

=Conclusion=

Hence from the above discussion, we can see that Dynamic Dispatch, though slower when compared to static dispatch is no longer slower due to the new generation of power packed computers. Also, dynamic dispatch can help in preserving the object-oriented concepts in highly complex software products. We have also looked up the differences between method Overloading and Overriding. We also had a sneak-view to Multiple Dispatch where more than one parameter can be used for Dynamic method lookup.

=Further Reading=

=References=
# [http://en.wikipedia.org/wiki/Object-oriented_programming Object Oriented Programming]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overriding Method Overriding]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Code_segment Code Segment]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_method_table Virtual Method Table]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_function Virtual Functions]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm Virtual Functions in C++]. publib.boulder.ibm.com. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overloading Method Overloading]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Multiple_dispatch Multiple Dispatch]. en.wikipedia.org. Retrieved Oct 31, 2010.

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-11-03T01:24:54Z

Cgoogc: /* Overriding and Overloading */

='''Dynamic Dispatch'''=

This wiki-page serves as a knowledge source for understanding the concept of Dynamic Dispatch in Computer Science. Here we will make an effort to address the efficiency considerations about Dynamic Dispatch, advantages of Dynamic Dispatch using parameter types and dynamic binding in CLOS (Common Lisp Object System).<br>

__TOC__

=Introduction=
Dynamic Dispatch is the process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. It is generally used in <b>Object-Oriented Language</b> (OOL) <sup>[http://en.wikipedia.org/wiki/Object-oriented_programming]</sup>. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called as <b>Method Overriding</b> <sup>[http://en.wikipedia.org/wiki/Method_overriding]</sup>). When a reference to the super class is used to execute that function, then which version of the function gets executed depends on the type, the reference to which it points to at that time rather than the type of the reference. In literature it also referred to in different names like <b>Runtime Binding</b> or <b>Dynamic Polymorphism</b>. <sup>[http://en.wikipedia.org/wiki/Dynamic_polymorphism]</sup>

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

==Need for Dynamic Dispatch==
Dynamic Dispatch is one of the inherent feature of an Object-Oriented Language [1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

==How Dynamic Dispatch works?==
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment <sup>[http://en.wikipedia.org/wiki/Code_segment]</sup> area of the process image. So a function in C will just map to a memory location in Code Segment of the process image. For example calling a function 'print()', might be converted to something like 'jmp 0xFFDE123' (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal (not shown here) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.

A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementations are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to an equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable (Virtual Method Table <sup>[http://en.wikipedia.org/wiki/Virtual_method_table]</sup>) which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be changed like this by the compiler
Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

<div style="text-align: center;"> Fig.1 - VTable Working </div>

<br>
Virtual Method table or vtable or dispatch table [5] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=Performance Evaluation=
From the above explanation it is evident that Virtual functions <sup>[http://en.wikipedia.org/wiki/Virtual_function] [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm]</sup> are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the Virtual method table [5] and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reasons why not all functions are dynamically binded in C++. In C++, functions which are explicitly marked virtual are dynamically bound whereas remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, hence, all functions are dynamically bound. It is also reasonable to assume that virtual functions might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

--------try to find a performance comparison and discuss about that---------

==Overriding and Overloading==
Overriding [2] and Overloading <sup>[http://en.wikipedia.org/wiki/Method_overloading]</sup> are two different features of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version of the function to call is deferred till runtime.

Let us see an two examples which provides insight into Overriding and Overloading.

Example - 1: Overloading

public class A{
public boolean equals( A check){ # Equals method of parameter type A
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # Object equals method called
a2.equals(a1); # Object equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # Object equals method called
}
}

Example - 2: Overriding

public class A{
@Override
public boolean equals( Object check){ # Equals method of parameter type Object
System.out.println( "A.equals method called");
return true;
}

public static void main(String [] args){ # Main method
Object a1 = new A(); # Instantiate class to get objects
A a2 = new A();
Object o1 = new Object();

a1.equals(a2); # A equals method called
a2.equals(a1); # A equals method called
a2.equals(a2); # A equals method called
a2.equals(o1); # A equals method called
}
}

If you see the comments provided to the side of the method calls, you would note the difference in the equals method called in case of both Overloading and Overriding. The decision which method to use, basically has two phases: First overload resolution, then method dispatch. Overload resolution happens at compile-time, method dispatch at runtime.

==Does Dynamic Dispatching hurts in today's power packed Computers?==

Even though Dynamic Dispatching is done in run-time, and it takes good amount of memory, today's computers are power packed with good amount of memory. Hence efficiency concerns for implementing Dynamic Dispatching in OOL is of little concern.

However, the method to be called cannot be chosen based on the actual arguments passed to the function, rather, the method is called based on the declared type of the parameters.

=Advantages of Dynamic Binding=

Dynamic binding has several advantages. It provides tremendous flexibilities. Also, it allows the software to be malleable when requirements change as the system evolves. Because of dynamic binding, caller objects are not concerned how the invoked objects carry out their methods. All they need to know is that the invoked objects know how to carry out their responsibilities, but they themselves need to know only what the invoked objects can do for them. As a consequence of this, type dependencies (which are the bane of procedural programming) cannot have a ripple effect through the system, when system requirements change. The beauty is that such dependencies remain encapsulated within the objects. The flexibility that developers can derive out of this is enormous. For instance, one can install newer types without having to change or stopping the functioning of existing systems. This is something along the lines of "hot pluggable components" of the hardware cousins.

One other advantage of Dynamic binding based on parameter types is that more than one parameter can be used in the selection of a method. Methods that use dynamic binding in this way are called multi-methods and the concept is called <b>Multiple Dispatch</b> <sup>[http://en.wikipedia.org/wiki/Multiple_dispatch]</sup>.

==Multiple Dispatch==

The Multiple Dispatch is used in Common Lisp Object System (CLOS) <sup>[http://en.wikipedia.org/wiki/Common_Lisp_Object_System]</sup>. Multiple-polymorphism allows specialized functions or methods to be defined to handle various cases:

+(int, int)
+(int, float)
+(int, complex) .. etc

The above functions are specialized to each of the cases required allowing single, highly cohesive and loosely coupled functions to be defined. This is also the true essence of object-oriented polymorphism, which allows objects to define methods for each specific case desired. In addition to better coupling and cohesion, multiple-polymorphism reduces program complexity by avoiding coding logic (switch statements) and because small methods further reduce complexity, as code complexity doesn't grow linearly with lines of code per method, but perhaps exponentially.

=Conclusion=

Hence from the above discussion, we can see that Dynamic Dispatch, though slower when compared to static dispatch is no longer slower due to the new generation of power packed computers. Also, dynamic dispatch can help in preserving the object-oriented concepts in highly complex software products. We have also looked up the differences between method Overloading and Overriding. We also had a sneak-view to Multiple Dispatch where more than one parameter can be used for Dynamic method lookup.

=Further Reading=

=References=
# [http://en.wikipedia.org/wiki/Object-oriented_programming Object Oriented Programming]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overriding Method Overriding]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Code_segment Code Segment]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_method_table Virtual Method Table]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Virtual_function Virtual Functions]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc14cplr139.htm Virtual Functions in C++]. publib.boulder.ibm.com. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Method_overloading Method Overloading]. en.wikipedia.org. Retrieved Oct 31, 2010.
# [http://en.wikipedia.org/wiki/Multiple_dispatch Multiple Dispatch]. en.wikipedia.org. Retrieved Oct 31, 2010.

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T03:31:05Z

Cgoogc: /* Performance Evaluation */

== Dynamic Dispatch ==

=== Introduction ===
The process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. Dynamic Dispatch generally happens in OOL. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called overriding). When a reference to the super class is used to execute that function, then which version of the function gets execute depends on the type, the reference points to at that time, instead of type of the reference. In literature it also given different names like Runtime Binding or [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism ].

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

=== Why we need Dynamic Dispatch ===
Dynamic Dispatch is one of the inherent feature of an Object Oriented Languauge [http://en.wikipedia.org/wiki/Object_oriented_language 1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

=== How Dynamic Dispatch works ===
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment area of the process image. So a function in C will just map to a memory location in Code Segment of the process image.

For example calling a function print(), might be converted to something like jmp 0xFFDE123 (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal(not shown) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.
A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementation are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to a equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be change like this by the compiler

Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

virtual method table or [http://en.wikipedia.org/wiki/Virtual_method_table vtable] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=== Performance Evaluation ===
From the above explanation it is evident that virtual functions are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the virtual method table and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reason why not all functions are dynamic bind in C++. In C++, functions which are explicitly marked virtual are dynamically bound, remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, all functions are dynamically bound. It also reasonable to assume that virtual function might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

--------try to find a performance comparison and discuss about that---------

=== Overriding and Overloading ===
Overriding and Overloading are two different feature of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version to call is deferred till runtime. [http://stackoverflow.com/questions/321864/java-dynamic-binding-and-method-overriding This]provides an interesting discussion about this fact.

=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===
*[http://en.wikipedia.org/wiki/Object_oriented_language 1. Wikipedia - Object Oriented Language]

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T03:30:56Z

Cgoogc: /* Performance Evaluation */

== Dynamic Dispatch ==

=== Introduction ===
The process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. Dynamic Dispatch generally happens in OOL. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called overriding). When a reference to the super class is used to execute that function, then which version of the function gets execute depends on the type, the reference points to at that time, instead of type of the reference. In literature it also given different names like Runtime Binding or [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism ].

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

=== Why we need Dynamic Dispatch ===
Dynamic Dispatch is one of the inherent feature of an Object Oriented Languauge [http://en.wikipedia.org/wiki/Object_oriented_language 1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

=== How Dynamic Dispatch works ===
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment area of the process image. So a function in C will just map to a memory location in Code Segment of the process image.

For example calling a function print(), might be converted to something like jmp 0xFFDE123 (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal(not shown) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.
A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementation are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to a equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be change like this by the compiler

Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

virtual method table or [http://en.wikipedia.org/wiki/Virtual_method_table vtable] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=== Performance Evaluation ===
From the above explanation it is evident that virtual functions are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the virtual method table and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reason why not all functions are dynamic bind in C++. In C++, functions which are explicitly marked virtual are dynamically bound, remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, all functions are dynamically bound. It also reasonable to assume that virtual function might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

try to find a performance comparison and discuss about that---------

=== Overriding and Overloading ===
Overriding and Overloading are two different feature of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version to call is deferred till runtime. [http://stackoverflow.com/questions/321864/java-dynamic-binding-and-method-overriding This]provides an interesting discussion about this fact.

=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===
*[http://en.wikipedia.org/wiki/Object_oriented_language 1. Wikipedia - Object Oriented Language]

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T03:30:32Z

Cgoogc: /* Performance Evaluation */

== Dynamic Dispatch ==

=== Introduction ===
The process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. Dynamic Dispatch generally happens in OOL. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called overriding). When a reference to the super class is used to execute that function, then which version of the function gets execute depends on the type, the reference points to at that time, instead of type of the reference. In literature it also given different names like Runtime Binding or [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism ].

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

=== Why we need Dynamic Dispatch ===
Dynamic Dispatch is one of the inherent feature of an Object Oriented Languauge [http://en.wikipedia.org/wiki/Object_oriented_language 1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

=== How Dynamic Dispatch works ===
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment area of the process image. So a function in C will just map to a memory location in Code Segment of the process image.

For example calling a function print(), might be converted to something like jmp 0xFFDE123 (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal(not shown) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.
A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementation are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to a equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be change like this by the compiler

Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

virtual method table or [http://en.wikipedia.org/wiki/Virtual_method_table vtable] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=== Performance Evaluation ===
From the above explanation it is evident that virtual functions are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the virtual method table and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reason why not all functions are dynamic bind in C++. In C++, functions which are explicitly marked virtual are dynamically bound, remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, all functions are dynamically bound. It also reasonable to assume that virtual function might need 20 to 40 extra instruction sets to execute a function call. Given today's processors speed this might be very insignificant.

****** try to find a performance comparison and discuss about that ******

=== Overriding and Overloading ===
Overriding and Overloading are two different feature of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version to call is deferred till runtime. [http://stackoverflow.com/questions/321864/java-dynamic-binding-and-method-overriding This]provides an interesting discussion about this fact.

=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===
*[http://en.wikipedia.org/wiki/Object_oriented_language 1. Wikipedia - Object Oriented Language]

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T03:28:49Z

Cgoogc: /* How Dynamic Dispatch works */

== Dynamic Dispatch ==

=== Introduction ===
The process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. Dynamic Dispatch generally happens in OOL. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called overriding). When a reference to the super class is used to execute that function, then which version of the function gets execute depends on the type, the reference points to at that time, instead of type of the reference. In literature it also given different names like Runtime Binding or [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism ].

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

=== Why we need Dynamic Dispatch ===
Dynamic Dispatch is one of the inherent feature of an Object Oriented Languauge [http://en.wikipedia.org/wiki/Object_oriented_language 1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

=== How Dynamic Dispatch works ===
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment area of the process image. So a function in C will just map to a memory location in Code Segment of the process image.

For example calling a function print(), might be converted to something like jmp 0xFFDE123 (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal(not shown) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.
A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementation are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to a equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

// C++ function call like
Animal *d = new Dog();
d->talk();

// might be change like this by the compiler

Dog *d = malloc(sizeof(Dog));
d->__id__ = 1;
talk(d);

// talk function can use the __id__ attribute to offset into the vtable to identify which version of function to call.

[[Image:Vtable.png|frame|center]]

virtual method table or [http://en.wikipedia.org/wiki/Virtual_method_table vtable] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=== Performance Evaluation ===
From the above explanation it is evident that virtual functions are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the virtual method table and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reason why not all functions are dynamic bind in C++. In C++, functions which are explicitly marked virtual are dynamically bound, remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, all functions are dynamically bound. The

=== Overriding and Overloading ===
Overriding and Overloading are two different feature of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version to call is deferred till runtime. [http://stackoverflow.com/questions/321864/java-dynamic-binding-and-method-overriding This]provides an interesting discussion about this fact.

=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===
*[http://en.wikipedia.org/wiki/Object_oriented_language 1. Wikipedia - Object Oriented Language]

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T03:25:56Z

Cgoogc: /* Overriding and Overloading */

== Dynamic Dispatch ==

=== Introduction ===
The process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. Dynamic Dispatch generally happens in OOL. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called overriding). When a reference to the super class is used to execute that function, then which version of the function gets execute depends on the type, the reference points to at that time, instead of type of the reference. In literature it also given different names like Runtime Binding or [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism ].

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

=== Why we need Dynamic Dispatch ===
Dynamic Dispatch is one of the inherent feature of an Object Oriented Languauge [http://en.wikipedia.org/wiki/Object_oriented_language 1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

=== How Dynamic Dispatch works ===
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment area of the process image. So a function in C will just map to a memory location in Code Segment of the process image.

For example calling a function print(), might be converted to something like jmp 0xFFDE123 (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal(not shown) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.
A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementation are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to a equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

Cat *c = new Cat();

Cat *c = malloc(sizeof(cat));
c->__id__ = 0;

[[Image:Vtable.png|frame|center]]

virtual method table or [http://en.wikipedia.org/wiki/Virtual_method_table vtable] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=== Performance Evaluation ===
From the above explanation it is evident that virtual functions are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the virtual method table and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reason why not all functions are dynamic bind in C++. In C++, functions which are explicitly marked virtual are dynamically bound, remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, all functions are dynamically bound. The

=== Overriding and Overloading ===
Overriding and Overloading are two different feature of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version to call is deferred till runtime. [http://stackoverflow.com/questions/321864/java-dynamic-binding-and-method-overriding This]provides an interesting discussion about this fact.

=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===
*[http://en.wikipedia.org/wiki/Object_oriented_language 1. Wikipedia - Object Oriented Language]

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T03:25:46Z

Cgoogc: /* Performance Evaluation */

== Dynamic Dispatch ==

=== Introduction ===
The process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. Dynamic Dispatch generally happens in OOL. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called overriding). When a reference to the super class is used to execute that function, then which version of the function gets execute depends on the type, the reference points to at that time, instead of type of the reference. In literature it also given different names like Runtime Binding or [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism ].

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

=== Why we need Dynamic Dispatch ===
Dynamic Dispatch is one of the inherent feature of an Object Oriented Languauge [http://en.wikipedia.org/wiki/Object_oriented_language 1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

=== How Dynamic Dispatch works ===
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment area of the process image. So a function in C will just map to a memory location in Code Segment of the process image.

For example calling a function print(), might be converted to something like jmp 0xFFDE123 (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal(not shown) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.
A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementation are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to a equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

Cat *c = new Cat();

Cat *c = malloc(sizeof(cat));
c->__id__ = 0;

[[Image:Vtable.png|frame|center]]

virtual method table or [http://en.wikipedia.org/wiki/Virtual_method_table vtable] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=== Performance Evaluation ===
From the above explanation it is evident that virtual functions are more complicated that dispatching normal function calls. For example Virtual functions in C++ will need extra memory for each class to store the virtual method table and needs additional CPU cycles to perform vtable lookup, before it can make the actual function call.

This is one of the important reason why not all functions are dynamic bind in C++. In C++, functions which are explicitly marked virtual are dynamically bound, remaining functions are statically bound during the compile time. When we say bound/bind we are actually talking about the mapping between the function name and memory location where it is stored for execution.

In languages like Java, the creators thought dynamic binding being an essential feature of OOL, all functions are dynamically bound. The

=== Overriding and Overloading ===
Overriding and Overloading are two different feature of OOL. In function overloading, which version of function to call is decided by the compiler during the compile time itself, where as when a function is overridden, which version to call is deferred till runtime. [http://stackoverflow.com/questions/321864/java-dynamic-binding-and-method-overriding This] provides an interesting discussion about this fact.

=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===
*[http://en.wikipedia.org/wiki/Object_oriented_language 1. Wikipedia - Object Oriented Language]

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T03:18:22Z

Cgoogc: /* How Dynamic Dispatch works */

== Dynamic Dispatch ==

=== Introduction ===
The process of identifying which version of the function to call based on the runtime type of the reference being used to execute the function. Dynamic Dispatch generally happens in OOL. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called overriding). When a reference to the super class is used to execute that function, then which version of the function gets execute depends on the type, the reference points to at that time, instead of type of the reference. In literature it also given different names like Runtime Binding or [http://en.wikipedia.org/wiki/Dynamic_polymorphism Dynamic Polymorphism ].

To further understand what Dynamic Dispatch is, consider the below example:

class Animal {
public void walk() {
System.out.println("Animal::walk");
}
}

class Dog extends Animal {
public void walk() {
System.out.println("Dog::walk");
}
}

class Cat extends Animal {
public void walk() {
System.out.println("Cat::walk");
}
}

Animal a = new _______();
a.walk();

The compiler cannot decide which version of walk (Animal, Dog or Cat) during compile time. So the decision of which version of the walk function to call will be deferred till the runtime.

=== Why we need Dynamic Dispatch ===
Dynamic Dispatch is one of the inherent feature of an Object Oriented Languauge [http://en.wikipedia.org/wiki/Object_oriented_language 1]. In a reasonably large software based on a procedural language like C, you will come across a bunch of switch or if statement which decides which version of the function to call. Ofcourse Dynamic Dispatch can be simulated in a procedural language like C, but it involves dangerous pointer manipulation, which is usually done well by the Compilers in case of OOL like C++.

For example, consider a toll gate application which charges differently based on the car type like Sedan, SUV, Coupe etc., If we have to do this in a procedural language like C in which each classes of car represented by structure, we might have something like this.

float calculate_charge(void *car, int type)
{
switch(type)
{
case SUV:
return suv_charge(car);
case SEDAN:
return sedan_charge(car);
case COUPE:
return coupe_charge(car);
}

You can see that the code above will quickly becomes messy as we define new type of car. If we have done the same in an OOL language like Java the above statement could be replacement by a simple:

car.charge();

The function charge will be overridden in each of the subclasses (Sedan, Suv, and Coupe). From the above example it is very evident that why we need dynamic dispatch and it is obviously useful.

=== How Dynamic Dispatch works ===
The implementation of Dynamic Dispatch varies significantly based on type language, in fact it changes even from Compiler to Compiler for a same language. We will consider how function are dispatch at runtime in both C and C++. We will try to understand if there is any overhead involved with virtual functions.

In a machine compiled language like C, program logic is compiled into underlying processor instruction set by the compiler. Incase of x86 compiler, C code will be compiled into X86 instruction sets. The function will be compiled and placed in Code Segment area of the process image. So a function in C will just map to a memory location in Code Segment of the process image.

For example calling a function print(), might be converted to something like jmp 0xFFDE123 (jmp is a branching instruction). So a function call is in fact as simple as executing a jump statement (of course you push the arguments into stack before you call jump).

Now lets consider a OOL like C++ which too compiles to hardware instruction set on compilation. Consider the below example of two classes which extend from a common class called Animal(not shown) with one method talk. The below example just demonstrates how dynamic dispatch could be implemented by a compiler.
A word of caution before you proceed; the implementation is hypothetical and far from any practical use. The objective of the example shown below is just to give an idea of how Dynamic Dispatch might be implemented. Practical implementation are lot more complicated, so we have taken this simple example for easy explanation and understanding.

class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

The above C++ program might infact be converted to a equivalent C program by the compiler during pre-compilation. Each newly defined structure gets an __id__ and this id will be used to lookup vtable which maps id to the actual function memory location. One we get the memory location we will execute a jump instruction like we did before.

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

Cat *c = new Cat();

Cat *c = malloc(sizeof(cat));
c->__id__ = 0;

[[Image:Vtable.png|frame|center]]

virtual method table or [http://en.wikipedia.org/wiki/Virtual_method_table vtable] is the key to virtual function working. It is evident from the above that vtable infact makes the function calling little more expensive compared to normal function calls.

=== Performance Evaluation ===
=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===
*[http://en.wikipedia.org/wiki/Object_oriented_language 1. Wikipedia - Object Oriented Language]

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T03:02:06Z

Cgoogc: /* How Dynamic Dispatch works */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:58:55Z

Cgoogc: /* How Dynamic Dispatch works */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:58:42Z

Cgoogc: /* How Dynamic Dispatch works */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:58:25Z

Cgoogc: /* How Dynamic Dispatch works */

File:Vtable.png

2010-10-27T02:57:59Z

Cgoogc: hypothetical vtable structure

hypothetical vtable structure

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:50:20Z

Cgoogc: /* Dynamic Dispatch */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:49:54Z

Cgoogc: /* How Dynamic Dispatch works */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:49:30Z

Cgoogc: /* Why we need Dynamic Dispatch */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:39:54Z

Cgoogc: /* References */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:39:29Z

Cgoogc: /* Why we need Dynamic Dispatch */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:39:13Z

Cgoogc: /* Introduction */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:38:36Z

Cgoogc: /* Introduction */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:37:24Z

Cgoogc: /* Introduction */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:36:57Z

Cgoogc: /* Dynamic Dispath */

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-27T02:09:07Z

Cgoogc: /* Introduction */

== Dynamic Dispath ==

=== Introduction ===
The process of identifying which version of the function with identifier will be executed during the runtime. Dynamic Dispatch generally happens in OOLS. For example, we can have a super class which defines a particular function and then there is a subclass which defines the same function (called overriding). When a reference to the super class is used to execute that function, then which version of the function gets execute depends on the type the reference points to at that time, instead of type of reference. In literature it also given different names like Runtime Binding or [Dynamic Polymorphism http://en.wikipedia.org/wiki/Dynamic_polymorphism].

=== Why we need Dynamic Dispatch ===
=== How Dynamic Dispatch works ===
=== Dynamic Dispatch working in Detail ===
class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

Cat *c = new Cat();

Cat *c = malloc(sizeof(cat));
c->__id__ = 0;

=== Performance Evaluation ===
=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-25T20:47:56Z

Cgoogc: /* Dynamic Dispatch working in Detail */

== Dynamic Dispath ==

=== Introduction ===
=== Why we need Dynamic Dispatch ===
=== How Dynamic Dispatch works ===
=== Dynamic Dispatch working in Detail ===
class Cat
{
public:
void talk()
{
cout << "Meow!!";
}
};

class Dog
{
public:
void talk()
{
cout << "Bark!!";
}
};

struct Cat
{
int __id__; // 0
char name[10];
};

struct Dog
{
int __id__; // 1
char name[10];
};

void cat_talk()
{
printf("meow!");
}

void dog_talk()
{
printf("Bark!!");
}

void talk(void *object)
{
int id = *(int *)object;
vtable[id]();
}

void (*vtable[2]);
vtable[0] = cat_talk;
vtable[1] = dog_talk;

Cat *c = new Cat();

Cat *c = malloc(sizeof(cat));
c->__id__ = 0;

=== Performance Evaluation ===
=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===

CSC/ECE 517 Fall 2010/ch2 5c gn

2010-10-25T20:18:54Z

Cgoogc: Details of dynamic dispatch

== Dynamic Dispath ==

=== Introduction ===
=== Why we need Dynamic Dispatch ===
=== How Dynamic Dispatch works ===
=== Dynamic Dispatch working in Detail ===
=== Performance Evaluation ===
=== Does Dynamic Dispatching hurts in today's power packed Computers? ===
=== Conclusion ===
=== Further Reading ===
=== References ===

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T23:06:12Z

Cgoogc: /* Implementation issues */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance. Now, appliances that control the temperature can be construed as electric appliances with some added functionality (increase/decrease temperature). Here is how they are implemented.

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

Consider a task where two specific temperature control devices has to be modeled. Apart from being temperature control devices, they also implement specific tasks related to their domains, eg heating, cooling.

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* When a class extends two functions which has same function, it will have two version of the function with same name. There is an ambiguity in resolving which function to call. This is called [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]
* The class might have more than one path to the top-most parent class because of multiple Inheritance
* Typecasting will become ambiguous in Multiple Inheritance. Refer to [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance] for an example of this problem.
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.

== Diamond Problem in Detail ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] discusses using Dynamic proxies in greater detail.

= Conclusion =
We discussed briefly about Inheritance, Multiple Inheritance, its advantages and disadvantages. Multiple Inheritance surely offers more flexibility in designing, but languages which don't support Multiple Inheritance has different ways of simulating Multiple Inheritance if required to do so.

<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing software</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it makes the languauge complicated to use and not necessary for most scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T23:05:22Z

Cgoogc: /* Good and bad of Multiple Inheritance */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance. Now, appliances that control the temperature can be construed as electric appliances with some added functionality (increase/decrease temperature). Here is how they are implemented.

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

Consider a task where two specific temperature control devices has to be modeled. Apart from being temperature control devices, they also implement specific tasks related to their domains, eg heating, cooling.

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* When a class extends two functions which has same function, it will have two version of the function with same name. There is an ambiguity in resolving which function to call. This is called [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]
* The class might have more than one path to the top-most parent class because of multiple Inheritance
* Typecasting will become ambiguous in Multiple Inheritance. Refer to [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance] for an example of this problem.
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] discusses using Dynamic proxies in greater detail.

= Conclusion =
We discussed briefly about Inheritance, Multiple Inheritance, its advantages and disadvantages. Multiple Inheritance surely offers more flexibility in designing, but languages which don't support Multiple Inheritance has different ways of simulating Multiple Inheritance if required to do so.

<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing software</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it makes the languauge complicated to use and not necessary for most scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T23:04:48Z

Cgoogc: /* Good and bad of Multiple Inheritance */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance. Now, appliances that control the temperature can be construed as electric appliances with some added functionality (increase/decrease temperature). Here is how they are implemented.

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

Consider a task where two specific temperature control devices has to be modeled. Apart from being temperature control devices, they also implement specific tasks related to their domains, eg heating, cooling.

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* When a class extends two functions which has same function, it will have two version of the function with same. There is an ambiguity in resolving which function to call. This is called [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]
* The class might have more than one path to the top-most parent class because of multiple Inheritance
* Typecasting will become ambiguous in Multiple Inheritance. Refer to [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance] for an example of this problem.
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] discusses using Dynamic proxies in greater detail.

= Conclusion =
We discussed briefly about Inheritance, Multiple Inheritance, its advantages and disadvantages. Multiple Inheritance surely offers more flexibility in designing, but languages which don't support Multiple Inheritance has different ways of simulating Multiple Inheritance if required to do so.

<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing software</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it makes the languauge complicated to use and not necessary for most scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T14:33:20Z

Cgoogc: /* Conclusion */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] discusses using Dynamic proxies in greater detail.

= Conclusion =
We discussed briefly about Inheritance, Multiple Inheritance, its advantages and disadvantages. Multiple Inheritance surely offers more flexibility in designing, but languages which don't support Multiple Inheritance has different ways of simulating Multiple Inheritance if required to do so.

<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing software</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it makes the languauge complicated to use and not necessary for most scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T14:33:13Z

Cgoogc: /* Conclusion */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] discusses using Dynamic proxies in greater detail.

= Conclusion =
We discussed briefly about Inheritance, Multiple Inheritance, its advantages and disadvantages. Multiple Inheritance surely offers more flexibility in designing, but languages which don't support Multiple Inheritance has different ways of simulating Multiple Inheritance if required to do so.

<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing software</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it makes the languauge complicated to use and not necessary for most scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T14:31:49Z

Cgoogc: /* Conclusion */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] discusses using Dynamic proxies in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing software</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it makes the languauge complicated to use and not necessary for most scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T14:30:54Z

Cgoogc: /* Alternates to Multiple Inheritance */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] discusses using Dynamic proxies in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T14:30:48Z

Cgoogc: /* Alternates to Multiple Inheritance */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] talks discusses using Dynamic proxies in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T14:30:20Z

Cgoogc: /* Alternates to Multiple Inheritance */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

* Extended Dynamic Proxies
Dynamic Proxy is a technique in which we can dynamically synthesis a new object from existing objects using reflection. With Dynamic Proxies, we can dynamically make a class implement different interfaces. This is achieved through reflection mechanism. This [http://java.sys-con.com/node/37748 article] talks about using Extended Dynamic Proxies to achieve Multiple Inheritance in Java. But this rather a verbose and a complicated solution. This [http://www.java2s.com/Code/Java/Reflection/Aninvocationhandlerthatcountsthenumberofcallsforallmethodsinthetargetclass.htm article] talks about using Dynamic proxies.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T14:22:58Z

Cgoogc: /* Reference */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]
*[http://java.sun.com/docs/white/langenv/ (4) The Java Language]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T14:20:43Z

Cgoogc: /* What is Inheritance? */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-22T13:41:59Z

Cgoogc: /* Multiple Inheritance - Do we really need this? */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

#For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature #of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class, unlike what we did in C++. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public IAirConditioner {
public void setThresholdTemp(int t);
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-21T20:40:51Z

Cgoogc: /* Multiple Inheritance - Do we really need this? */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

#For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature #of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

== Multiple Inheritance - Do we really need this? ==
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-21T20:40:40Z

Cgoogc: /* Implementation issues */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_517_Fall_2010/ch1_1e_bb#Object_Oriented_Programming Object Oriented Programming] (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

#For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature #of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

== Implementation issues ==
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

= Multiple Inheritance - Do we really need this? =
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-21T20:38:32Z

Cgoogc: /* Further Reading */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of Object Oriented Programming (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

#For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature #of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

= Implementation issues =
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

= Multiple Inheritance - Do we really need this? =
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]
*[http://en.wikipedia.org/wiki/Mixin Mixins]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-21T20:36:00Z

Cgoogc: /* Reference */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of Object Oriented Programming (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

#For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature #of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

= Implementation issues =
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

= Multiple Inheritance - Do we really need this? =
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]
*[http://en.wikipedia.org/wiki/Diamond_problem (3) Diamond Problem with Multiple Inheritance]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-21T20:35:28Z

Cgoogc: /* Implementation issues */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of Object Oriented Programming (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

#For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature #of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

= Implementation issues =
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem(3)]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

= Multiple Inheritance - Do we really need this? =
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-21T20:32:57Z

Cgoogc: /* Reference */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of Object Oriented Programming (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

#For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature #of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

= Implementation issues =
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg|frame|center]]

Now if an object of the HybridCar class calls a method of class Car, an ambiguous situation arises. Assuming the method has been [http://en.wikipedia.org/wiki/Method_overriding overridden] by class MechCar and ElectricCar, then it is not clear which version of the method the object is referring to. This is what is known as the Diamond Problem. This problem is addressed in C++ solves this problem through the use of [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

= Multiple Inheritance - Do we really need this? =
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]
*[http://www.artima.com/weblogs/viewpost.jsp?thread=246341 (2) Mixins considered Harmful]

CSC/ECE 517 Fall 2010/ch1 25 ag

2010-09-21T20:22:10Z

Cgoogc: /* Implementation issues */

= What is Inheritance? =
Inheritance, along with polymorphism and encapsulation, is one of the pillar features of Object Oriented Programming (OOP). Inheritance allows a class to reuse, extend or modify the behavior of another class. The term inheritance generally refers to single inheritance, where a sub-class or a derived class inherits methods and attributes from only one parent class.

#For example, consider a general class of electrical appliances. Switching an appliance on and off can be considered a standard feature #of every appliance.

Example:

class ElectricAppliance
{
public void on() { ... }
public void off() { ... }
}

class TempControlAppliance : public ElectricAppliance
{
public void increaseTemp() { .. }
public void decreaseTemp() { .. }
}

class Heater : public TempControlAppliance
{
public void heat() { .. }
}

class Cooler : public TempControlAppliance
{
public void cool() { .. }
}

If we don't have inheritance, we might have to duplicate all the functions in both Heater and Cooler class. Inheritance is very important to achieve DRY (Don't Repeat Yourself). In the above class hierarchy, TempControlAppliance is super (parent) class for both Cooler and Heater subclass (child).

= What is Multiple Inheritance =
When a class inherits from more than one class i.e., a child class having more than one parent class, is called multiple inheritance. Though this feature offers more flexibility, it seem to overwhelm most of the developer, so some of the object oriented language designer decided not to support Multiple Inheritance. Java and C# are some of the most famous language which don't support multiple inheritance. We need careful design to take proper advantage of Multiple inheritance, otherwise you might end up in spaghetti code, with classes inheritancing from multiple classes.

Example:
Building upon the above example, let us say we have a new device called Air Conditioner which can both heat and cool air. We might have a new class called AirConditioner as follows:

class AirConditioner : public Heater, public Cooler
{
public void setThresholdTemperature(int temp) { ... }
}

= Good and bad of Multiple Inheritance =
Good:
* Multiple Inheritance strongly supports DRY principle, which leads to better software which is extensible, cohesive, less coupled and modular.
* Multiple Inheritance is very common in real world, in which object takes attributes from different objects.
* Multiple Inheritance is more expressive than Single Inheritane, so it gives flexibility in designing software with complex object relationships.

Bad:
* To take complete advantage of Multiple Inheritance needs a thoughtful design. Without a good design, Multiple Inheritance infact might lead to bad code.
* Multiple Inheritance is overwhelming to developers. Requires more experience to properly use Multiple Inheritance.
* Multiple Inheritance is hard to use and make the language complicated. Some example like what happens when you Inherit from multiple classes which has same method?

= Implementation issues =
One of the most common problem with Multiple Inheritance is called the [http://en.wikipedia.org/wiki/Diamond_problem Diamond Problem]. This is encountered when a derived class inherits from multiple parent classes, which in turn inherit from one super class. Let us try to understand this problem using an example.

Consider a task of modelling a car. Now a car can broadly be divided into two subclasses, mechanical cars and electric cars.

class Car
{
public:
void start() { cout << "Start with loud noise";
void steer();
}

class MechCar : public Car
{
}

class ElectricCar : public Car
{
public:
void start() { cout << "start without noise";
}

Now considering modern advancements in vehicle design, a new subclass of hybrid cars have emerged in the market. These cars have traits of both mechanical and electric cars. Here is how this is achieved in C++.

class HybridCar : public MechCar, ElectricCar
{
// This has two copies of start()
}

Here is an illustration of the inheritance hierarchy.

[[Image:Car-hybrid.jpg | frame | center | 50p]]

From the above we can see that there is an ambiguity about which version of start function to use. C++ solves this problem through [http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance].

HybridCar h;
h.ElectricCar::start();

There are also ambiguities during the type casting. For more details about Virtual Inheritance refer [http://en.wikipedia.org/wiki/Virtual_inheritance here]

= Multiple Inheritance - Do we really need this? =
Many languages which don't support multiple inheritance completely, has some ways of emulating multiple inheritance. We will consider Java as an example which does not support Multiple Inheritance completely and see how we can emulate multiple inheritance in Java. It is not completely true to say that Java does not support multiple inheritance, in fact with interfaces we can have multiple inheritance. Since, Interface just defines the behaviour, it does not have any attributes to describe it, Interfaces are not considered as a Class.

Let us consider the previous example of an AirConditioner:

class AirConditioner extends [______________]

We cannot fit both the classes there since a class in Java can extend from a single class. But Java classes can implement multiple interfaces.

public interface IHeater {
void heat();
}

public interface ICooler {
void cool();
}

public Heater extends TempControllerAppliance implements IHeater {
public void heat() { .. }
}

public Cooler extends TempControllerAppliance implements ICooler{
public void cool() { .. }
}

public class AirConditioner extends TempControllerAppliance implements IHeater, ICooler, IAirConditioner {
private ICooler cooler = new Cooler();
private IHeater heater = new Heater();

public void cool() {
cooler.cool();
}

public void heat() {
heater.heat();
}

public void setThreshold(int t) { ... }
}

To implement multiple inheritance in Java, we need to the following:
1. Make every class implement an Interface
2. Classes extends these interfaces to add logic
3. When a class needs to extend from Multiple interfaces, you can implement those interfaces and delegate the call to the actual implementation. This is achieved through Composition.

We can see that it is possible to emulate multiple inheritance through [http://en.wikipedia.org/wiki/Object_composition composition].

Let us take another example and see how we can emulate Multiple inheritance in Java. We are developing a paint application. We have separate tools to draw each primitive shapes.

<table>
<tr>
<td>
class Shape
{
//...
}

class Square : Shape
{
// ..
}

class Circle : Shape
{
//..
}

class Triangle : Shape
{
//..
}
</td>
<td>
class Painter
{
//..
}

class SquarePainter : Painter
{
void draw(Square s) { }
}

class CirclePainter : Painter
{
void draw(Circle c) { }
}

class TrianglePainter : Painter
{
void draw(Triangle t) { }
}
</td>
</tr>
</table>

Now we need a canvas painter, which should have the capability to draw any of the above shape. In C++, this is pretty straight forward, you define a new class which extends all painters.

class CanvasPainter : SquarePainter, CirclePainter, TrianglePainter
{
// ..
}

How can do the same in Java? Ofcourse, we will use composition, but how will you know which version of draw function to call? May be we can write some thing like this:

if (shape instanceof Triangle)
{
trianglePainter.draw((Triangle) shape);
}
else if(shape instanceof Circle)
{
circlePainter.draw((Circle) shape);
}

Unfortunately this is not a scalable solution and for every new tool we add to our paint program, we will have to change this code. This is where design patterns like [http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern Chain of Responsibility] proves helpful.

Implementing the above code in Java using Chain of Responsibility design pattern.

interface IPainter
{
boolean canDraw(Shape s);
void draw(Shape s);
}

All painters will implement the above function:

class TrianglePainter implements IPainter
{
public boolean canDraw(Shape s) { return s instanceof Triangle; }
public void draw(Shape s) { // ... }
}

class CanvasPainter implements IPainter
{
// List<IPainter> = ....
// function to add and remove painters
public void draw(Shape s)
{
for(Paint p : painters)
{
if(p.canDraw(s)) { p.draw(s); return; }
}
}
}

We can see that, chain of responsibility design pattern provides a very neat way to handle multiple inheritance in languages which don't support them completely.

= Alternates to Multiple Inheritance =
* Composition & Interfaces
Compositions provides a neat way of emulating Multiple Inheritance. With Multiple Inheritance, we bring functionality from different classes to the class which extends them. We can achieve the same using Composition in which one class contains instance of other class, there by importing the capability of all those classes. Since a class is allowed to implement Multiple Interfaces, the class behaves as though it extended from Multiple classes.

* Mixins
Some languages provide [http://en.wikipedia.org/wiki/Mixin mixins] as a language feature. Mixins provide another elegant mechanism which mimics Multiple Inheritance. The common problems with Mixin is that it pollutes the class namespace as it imports functions from different modules. This [http://www.artima.com/weblogs/viewpost.jsp?thread=246341 article] talks about the limitations of mixins in greater detail.

= Conclusion =
<table border = "1">
<tr>
<th></th>
<th>Single Inheritance</th>
<th>Multiple Inheritance</th>
</tr>
<tr>
<td>Flexibility</td>
<td>Single Inheritance does have some restriction in terms of modeling real world objects, but mitigate this problem with careful design</td>
<td>Multiple Inheritance provides lots more flexibility for designing</td>
</tr>

<tr>
<td>Easy of Use</td>
<td>Single Inheritance is much simpler to use</td>
<td>Multiple Inheritance sometimes leaves the programmer confused. One of the common problem with Multiple inheritance in Diamond Problem</td>
</tr>

<tr>
<td>Availability</td>
<td>Single Inheritance is supported by all the Object Oriented Programming Languages</td>
<td>Multiple Inheritance is not supported by few of the OOP Languages, because the designer of the language thought it is hard to use and not necessary for common scenarios.</td>
</tr>

<tr>
<td>Efficiency</td>
<td>This actually language specific. But generally it takes less time to figure which version of the function to call in a single inheritance</td>
<td>Virtual Function dispatch in C++ is more time consuming in Multiple Inheritance. For example Multiple Inheritance in C++, needs multiple vtable for dispatching virtual functions. [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1)] discusses about this problem in great detail.</td>
</tr>

</table>

= Further Reading =
*[http://en.wikipedia.org/wiki/Multiple_inheritance Multiple Inheritance]
*[http://en.wikipedia.org/wiki/Virtual_inheritance Virtual Inheritance]
*[http://en.wikipedia.org/wiki/Object_composition Composition]

= Reference =
*[http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf (1) Cost of Virtual Functions C++]