Polymorphism Polymorphism

(1)

Polymorphism Polymorphism

Giuseppe Attardi

Antonio Cisternino

(2)

Generic programming Generic programming

 Code reuse is clearly a good ideaCode reuse is clearly a good idea

 Often an algorithm can be applicable to many Often an algorithm can be applicable to many objects

objects

 Goal is to avoid rewriting as much as possibleGoal is to avoid rewriting as much as possible

 Types introduce great benefits but also may limit Types introduce great benefits but also may limit code reuse:

code reuse:

int sqr(int i, int j) { return i*j; }

double sqr(double i, double j) {return i*j; }

 The notion of The notion of sqrsqr is unique but we must define it is unique but we must define it twice because of types

twice because of types

 Languages offer mechanisms to address this Languages offer mechanisms to address this problem

problem

(3)

Polymorphism Polymorphism

 The ability of associate more than one The ability of associate more than one meaning to a name in a program

meaning to a name in a program

 We have already seen two kinds of We have already seen two kinds of polymorphism:

polymorphism:

– Subtype/inclusion (inheritance) – Overloading

 Polymorphism is the fundamental Polymorphism is the fundamental mechanism for

mechanism for generic programminggeneric programming

 There are other kinds of polymorphismThere are other kinds of polymorphism

(4)

Classification of Polymorphism Classification of Polymorphism

Polymorphism

Universal

Ad hoc

Parametric

Inclusion

Overloading

Coercion

(5)

Universal vs. ad hoc polymorphism Universal vs. ad hoc polymorphism

 With overloading an implementation for With overloading an implementation for each signature is required

each signature is required

 We provide ad hoc solutions for different We provide ad hoc solutions for different objects

objects

 Inheritance instead allows defining Inheritance instead allows defining

algorithms that operate on all classes of algorithms that operate on all classes of

objects that inherit from a given class objects that inherit from a given class

 In this case a single (universal) solution In this case a single (universal) solution applies to different objects

applies to different objects

(6)

Implementing Polymorphism Implementing Polymorphism



Dynamic method dispatch Dynamic method dispatch



C++ adds a v-table to each object C++ adds a v-table to each object

from a class having virtual methods

(7)

Containers Containers

 Example: Java VectorExample: Java Vector

Vector v = new Vector();

v.addElement("Pippo");

v.addElement(new Integer(2));

 Signature of Signature of addElementaddElement::

void addElement(Object x);

 The argument is of type Object because The argument is of type Object because the container may contain any type of the container may contain any type of

object object

(8)

Problem with containers Problem with containers

 Inserting an object in a vector we loose Inserting an object in a vector we loose type information

type information

 In our example we implicitly upcast from In our example we implicitly upcast from String

String to to ObjectObject::

v.addElement("Pippo");

 Extracting the second element with the Extracting the second element with the wrong cast produces a runtime error:

wrong cast produces a runtime error:

Integer i = (Integer)v.elementAt(0);

(9)

Weakest constraint programming Weakest constraint programming

 Where do we assume something about objects that we manipulate?Where do we assume something about objects that we manipulate?

class Vector { Object[] v;

int size;

public Vector() {

v = new Object[15];

size = 0;

}

public addElement(Object e) { if (size == v.length) {

Object[] w = new Object[](2 * size);

w.copy(v, 0, size);

v = w;

}

v[size++] = e;

}}

 We assume only assignment operations and arrays: operation We assume only assignment operations and arrays: operation available on all objects

available on all objects

(10)

Can we sort our vector?

 How to add a method for sorting a vector?How to add a method for sorting a vector?

 We do not have enough information on our objects: We do not have enough information on our objects:

no comparison operation is available no comparison operation is available

 Our vector is too generic!Our vector is too generic!

 Two solutions:Two solutions:

– accept only objects that implement an interface (i.e.

IComparable) that exposes a method to compare objects

public void addElement(IComparable e) {…}

– Pass a functional object: an object which implements an interface for comparing Object instances (i.e. IComparator)

public void Sort(IComparator c) {…}

interface IComparator {

int compare(Object x, Object y); }

(11)

Abstract as much as possible!

 To express generic code with subtype To express generic code with subtype polymorphism we should abstract the polymorphism we should abstract the

essence of the operations required on the essence of the operations required on the

objects we want to manipulate objects we want to manipulate

 Risk is over-abstraction: once defined our Risk is over-abstraction: once defined our vector we can’t easily add a sort method vector we can’t easily add a sort method

 Another issue: inheritance relies on Another issue: inheritance relies on explicit annotation of our types and explicit annotation of our types and

changes are hard to perform changes are hard to perform

(12)

Iterating over a collection Iterating over a collection

 A common programming pattern is to A common programming pattern is to enumerate the elements of a collection enumerate the elements of a collection

 It doesn’t really matter how the collection is It doesn’t really matter how the collection is organized

organized

 We can implement a class per collection type We can implement a class per collection type whose objects enumerates the elements.

whose objects enumerates the elements.

 Example:Example:

Enumeration elements() { return ???; } void printCollection(Enumeration e) {

while (e = hasMoreElements()) { Object o = e.nextElement();

System.out.println(o);

}}

Interface

(13)

Question Question

 Which class implements method Which class implements method elements

elements??

– Class Vector

– Use overloading and singleton

class Enumeration {

static Enumeration getEnumeration(Vector v){

return v.elements();

}

// Other collections’ enumerators }

 Thus we can add enumerators to existing Thus we can add enumerators to existing collections

collections

(14)

Enumerator for Vector Enumerator for Vector

class VectorEnum implements Enumeration { class VectorEnum implements Enumeration { int idx;int idx;

Vector v; Vector v;

bool hasMoreElements() { idx < v.size(); } bool hasMoreElements() { idx < v.size(); } Object nextElement() {Object nextElement() {

return v.elementAt(idx++); return v.elementAt(idx++);

} }

VectorEnum(Vector v) {VectorEnum(Vector v) { idx = 0; idx = 0;

this.v = v; this.v = v; // why it is not copied? // why it is not copied?

}} }}

(15)

Is the enumerator up to date?

 To ensure that the enumerator is consistent To ensure that the enumerator is consistent the vector should be copied into the

the vector should be copied into the enumerator

enumerator

 This isn’t reasonable: memory wasted and we This isn’t reasonable: memory wasted and we iterate on a different vector!

iterate on a different vector!

 There is no way to ensure that the enumerator There is no way to ensure that the enumerator is consistent with the vector

is consistent with the vector

 Possible solution: introduce a “version” of the Possible solution: introduce a “version” of the vector

vector

 Each time the vector is modified the version is Each time the vector is modified the version is incremented

incremented

 Enumerator compares the version of the Enumerator compares the version of the vector with the one at time of creation

vector with the one at time of creation

(16)

Event handling in GUI Event handling in GUI

 Before Java 1.1 OO GUI frameworks were Before Java 1.1 OO GUI frameworks were based on sub-typing

based on sub-typing

 GUI can be easily described using generic GUI can be easily described using generic programming: buttons are a subtype of

programming: buttons are a subtype of control which is a special window

control which is a special window

 Containers of graphical widgets operates Containers of graphical widgets operates on controls, irrespective of their types

on controls, irrespective of their types

 Event dispatching and handling is dealt by Event dispatching and handling is dealt by virtual methods

virtual methods

– hence by default is delegated to the super-type

(17)

Java AWT Event Model Java AWT Event Model

class Component { class Component { int x, y;int x, y;

bool handleEvent(Event e); bool handleEvent(Event e);

}}

class Button extends Component { class Button extends Component { String text; String text;

bool handleEvent(Event e) { } bool handleEvent(Event e) { } … …

}}

class Window extends Component { … } class Window extends Component { … } class Frame extends Window { … }

class Frame extends Window { … }

(18)

Event handling Event handling

class MyButton extends Button { class MyButton extends Button {

boolean handleEvent(Event e) { boolean handleEvent(Event e) {

switch (e.type) { switch (e.type) {

case Event.MOUSE_UP: … case Event.MOUSE_UP: …

return true; // Event return true; // Event handled!

handled!

}}

default:

return super.handleEvent(e);return super.handleEvent(e);

}}}}

(19)

Limits of AWT Event Model Limits of AWT Event Model



Generic programming in this case is Generic programming in this case is quite elegant but inefficient

quite elegant but inefficient



Propagation of events to a number of Propagation of events to a number of handlers, mostly useless

handlers, mostly useless



Proliferation of classes: one for each Proliferation of classes: one for each object with different behavior

object with different behavior

(20)

Alternative Alternative

 Event Delegation modelEvent Delegation model

 Observer Pattern (aka publish/subscribe)Observer Pattern (aka publish/subscribe)

 Observable has set of registered Observable has set of registered observers

observers

 Observable notifies its observers when its Observable notifies its observers when its state changes

state changes

 Handling performed by objects that Handling performed by objects that

provide a Listener interface (aka callback, provide a Listener interface (aka callback,

delegate) delegate)

(21)

Java JDBC Java JDBC



Java DataBase Connectivity is a Java DataBase Connectivity is a

specification from Sun for accessing specification from Sun for accessing

databases in Java databases in Java



Interesting example of generic Interesting example of generic programming

programming



It implements a driver architecture It implements a driver architecture

exploiting the mechanisms of JVM

(22)

Overall architecture Overall architecture

 The The java.sqljava.sql package exposes package exposes only only interfaces

interfaces

 The only class is The only class is DriverManagerDriverManager

 Using the class constructor a driver Using the class constructor a driver register itself with the

register itself with the DriverManagerDriverManager

 The programmer performs the following The programmer performs the following steps:

steps:

– Load the database driver (a Java class) – Create a connection to a database (using

DriverManager)

– Obtain a Statement and execute the query – Enumerate the rows using a ResultSet

(23)

JDBC example JDBC example

Class.forName("…"); // Load the driver Class.forName("…"); // Load the driver

Connection c = Connection c =

DriverManager.getConnection("…");

Statement s = c.createStatement();

ResultSet r = s.executeQuery("select …");

while (r.hasNext()) { while (r.hasNext()) {

// Value of // Value of second column as Stringsecond column as String String s = r.getString(2);String s = r.getString(2);

}}

(24)

Question Question

 Statement is Class or Interface?Statement is Class or Interface?

 Connection, Statement are InterfacesConnection, Statement are Interfaces

 Through the Through the DriverManagerDriverManager the program the program obtains an object of

obtains an object of unknown unknown type which type which implements the

implements the ConnectionConnection interface interface

 The same applies to all the other The same applies to all the other

interfaces: through the connection an interfaces: through the connection an

object implementing

object implementing StatementStatement is is obtained, and so on and so forth obtained, and so on and so forth