Parametric Parametric Polymorphism Polymorphism

(1)

Parametric Parametric

Polymorphism Polymorphism

Antonio Cisternino Antonio Cisternino

Giuseppe Attardi Giuseppe Attardi Università di Pisa Università di Pisa

(2)

Parametric Polymorphism Parametric Polymorphism

 C++ templates implement a form of C++ templates implement a form of parametric polymorphism

parametric polymorphism

 PP is implemented in many flavors and many PP is implemented in many flavors and many languages: Eiffel, Mercury, Haskell, ADA, ML, languages: Eiffel, Mercury, Haskell, ADA, ML,

C++, … C++, …

 Improve the expressivity of a languageImprove the expressivity of a language

 May improve the performance of programsMay improve the performance of programs

 It is a form of It is a form of UniversalUniversal polymorphism polymorphism

(3)

C++ templates and macros C++ templates and macros

 Macros are dealt by the preprocessorMacros are dealt by the preprocessor

 C++ templates are implemented on the syntax treeC++ templates are implemented on the syntax tree

 The instantiation strategy is lazyThe instantiation strategy is lazy

 The following class compiles unless the method The following class compiles unless the method foofoo is used:

is used:

template <class T>class Foo { T x;

int foo() { return x + 2; } };

Foo<char*> f;

f.x = “”;

f.foo();

(4)

A more semantic approach A more semantic approach

 Parametric polymorphism has been Parametric polymorphism has been introduced also in Java and C#

introduced also in Java and C#

 Java Generics and Generic C# for .NET

 In both cases the compiler is able to check In both cases the compiler is able to check parametric classes just looking at their

parametric classes just looking at their definition

definition

 Parametric types are more than macros on Parametric types are more than macros on ASTAST

 Syntax for generics is similarSyntax for generics is similar

(5)

Generics in a Nutshell Generics in a Nutshell

 Type parameterization for classes, interfaces, and Type parameterization for classes, interfaces, and methods e.g.

methods e.g.

class Set<T> { ... } // parameterized class class Dict<K,D> { ... } // two-parameter class

interface IComparable<T> { ... } // parameterized interface

struct Pair<A,B> { ... } // parameterized struct (“value class”) T[] Slice<T>(T[] arr, int start, int count) // generic method

 Very few restrictions on usage:Very few restrictions on usage:

• Type instantiations can be primitive (only C#) or class e.g.

Set<int> Dict<string,List<float>> Pair<DateTime, MyClass>

• Generic methods of all kinds (static, instance, virtual)

• Inheritance through instantiated types e.g.

class Set<T> : IEnumerable<T>

class FastIntSet : Set<int> Virtual methods

only in GC#!

In GJ is

<T> T[] Slice(…)

(6)

C#

JG C++

More on generic methods More on generic methods

 Generic methods are similar to template methods in C++Generic methods are similar to template methods in C++

 As in C++ JG tries to infer the type parameters from the As in C++ JG tries to infer the type parameters from the method invocation

method invocation

 C# requires specifying the type argumentsC# requires specifying the type arguments

 Example:Example:

template <class T> T sqr(T x) { return x*x; } std::cout << sqr(2.0) << std::endl;

class F { <T> static void sort(T[] a) {…} } String[] s; F.sort(s);

class F { static void sort<T>(T[] a) {…} } string[] s; F.sort<string>(s);

(7)

Generic Stack Generic Stack

class Stack<T> { class Stack<T> {

private T[] items; private T[] items;

private int nitems; private int nitems;

Stack<T>() { nitems = 0; items = new T[] (50); } Stack<T>() { nitems = 0; items = new T[] (50); } T Pop() { T Pop() {

if (nitems == 0) throw Empty();if (nitems == 0) throw Empty();

return items[--nitems]; return items[--nitems];

} }

bool IsEmpty() { return (nitems == 0); } bool IsEmpty() { return (nitems == 0); } void Push(T item){ void Push(T item){

if (items.Length == nitems) { if (items.Length == nitems) {

T[] temp = items; T[] temp = items;

items = new T[nitems*2]; items = new T[nitems*2];

Array.Copy(temp, items, nitems); }Array.Copy(temp, items, nitems); } items[nitems++] = item;

items[nitems++] = item;

}} }}

How does the compiler

check the definition?

(8)

The semantic problem The semantic problem

 The C++ compiler cannot make assumptions The C++ compiler cannot make assumptions about type parameters

about type parameters

 The only way to type-check a C++ class is to The only way to type-check a C++ class is to wait for argument specification (instantiation):

wait for argument specification (instantiation):

only then it is possible to check operations only then it is possible to check operations

used (i.e.

used (i.e. compcomp method in sorting) method in sorting)

 From the standpoint of the C++ compiler From the standpoint of the C++ compiler

semantic module all types are not parametric semantic module all types are not parametric

(9)

Checking class definition Checking class definition

 To be able to type-check a parametric class To be able to type-check a parametric class just looking at its definition the notion of

just looking at its definition the notion of bound

bound is introduced is introduced

 Like method arguments have a type, type Like method arguments have a type, type arguments are bound to other types

arguments are bound to other types

 The compiler will allow to use values of such The compiler will allow to use values of such types as if upcasted to the bound type

types as if upcasted to the bound type

 Example: Example: class Vector<T: Sortable>class Vector<T: Sortable>

 Elements of the vector should implement (or Elements of the vector should implement (or inherit from)

inherit from) SortableSortable

(10)

Example Example

interface Sortable<T> { interface Sortable<T> { int compareTo(T a);int compareTo(T a);

}}

class Vector<T: Sortable<T>> { class Vector<T: Sortable<T>> { T[] v;T[] v;

int sz;int sz;

Vector() { sz = 0; v = new T[15]; }Vector() { sz = 0; v = new T[15]; } void addElement(T e) {…}void addElement(T e) {…}

void sort() {void sort() { …

…

if (v[i].compareTo(v[j]) > 0)if (v[i].compareTo(v[j]) > 0) …

… }} }}

Compiler can type- check this because v

contains values that implement Sortable<T>

Not possible in Java, because Sortable is an interface and type T is lost.

(11)

Pros and Cons Pros and Cons

 A parameterized type is checked also if no A parameterized type is checked also if no instantiation is present

instantiation is present

 Assumptions on type parameters are always explicit Assumptions on type parameters are always explicit (if no bound is specified

(if no bound is specified Object is assumed)Object is assumed)

 Is it possible to make assumptions beyond bound? Is it possible to make assumptions beyond bound?

 Yes, you can always cheat by upcasting to Yes, you can always cheat by upcasting to Object Object and then do whatever you want:

and then do whatever you want:

class Foo<T : Button> { void foo(T b) {

String s = (String)(Object)b;

}}

 Still the assumption made by the programmer is Still the assumption made by the programmer is explicit

explicit

(12)

Implementation Implementation

 Different implementations of parametric Different implementations of parametric polymorphism:

polymorphism:

 C++ only collects definition at class definition;

code is produced at first instantiation

 Java deals with generic types at compile time: the JVM is not aware of parametric types

 C# exploits support by the CLR (Common Language Runtime) of parametric types

• the CIL (Common Intermediate Language) has special instructions for dealing with type parameters

(13)

Java Generics strategy Java Generics strategy

 The Java compiler verifies that generic types The Java compiler verifies that generic types are used correctly

are used correctly

 Type parameters are dropped and the bound Type parameters are dropped and the bound is used instead; downcasts are inserted in is used instead; downcasts are inserted in

the right places the right places

 Generated code is a normal class file Generated code is a normal class file unaware of parametric polymorphism unaware of parametric polymorphism

(14)

Example Example

class Vector<T> { class Vector<T> { T[] v; int sz; T[] v; int sz;

Vector() { Vector() {

v = new T[15]; v = new T[15];

sz = 0; sz = 0;

} }

<U implements Comparer<T>> <U implements Comparer<T>>

void sort(U c) { void sort(U c) { …

…

c.compare(v[i], v[j]); c.compare(v[i], v[j]);

… … } } }}

……

Vector<Button> v;

v.addElement(new Button());

Button b = v.elementAt(0);

class Vector { class Vector {

Object Object[] v; int sz;[] v; int sz;

Vector() { Vector() {

v = new v = new ObjectObject[15];[15];

sz = 0; sz = 0;

} }

void sort(Comparer c) { void sort(Comparer c) { …

…

c.compare(v[i], v[j]); c.compare(v[i], v[j]);

… … } } }}

……

Vector v;

v.addElement(new Button());

Button b = Button b = (Button)

(Button)b.elementAt(0);b.elementAt(0);

(15)

Wildcard Wildcard

class Pair<X,Y> { class Pair<X,Y> {

X first;

Y second;

}}

public String pairString(Pair<?, ?> p) { public String pairString(Pair<?, ?> p) {

return p.first + “, “ + p.second;

}}

(16)

Expressivity vs. efficiency Expressivity vs. efficiency

 JG does not improve execution speed; though it JG does not improve execution speed; though it helps to express genericity better than

helps to express genericity better than inheritance

inheritance

 Major limitation in JG expressivity: exact type Major limitation in JG expressivity: exact type information is lost at runtime

information is lost at runtime

 All instantiations of a generic type collapse to All instantiations of a generic type collapse to the same class

the same class

 Consequences are: no virtual generic methods Consequences are: no virtual generic methods and pathological situations

and pathological situations

 Benefit: old Java < 5 classes could be seen as Benefit: old Java < 5 classes could be seen as generic types! Reuse of the existing codebase generic types! Reuse of the existing codebase

(17)

Generics and Java Generics and Java

Java Generics

Wadler Generic CLR

Kennedy, Syme

Parameterized types 

+ bounds 

+ bounds

Polymorphic methods  

Type checking at point of definition  

Non-reference instantiations  

Exact run-time types  

Polymorphic virtual methods  

Type parameter variance  

System Feature

(18)

Compilation Strategies Compilation Strategies

 Java compiler compiles to Java bytecode:Java compiler compiles to Java bytecode:

 Java bytecode is loaded and compiled at run time by the JIT + HotSpot

 C# (and other CLR) compilers generate CIL C# (and other CLR) compilers generate CIL code which is compiled to binary at load time code which is compiled to binary at load time

(19)

Problem with Java Generics Problem with Java Generics

Stack<String> s = new Stack<String>();

s.push("Hello");

Stack<Object> o = s;

Stack<Button> b = (Stack<Button>)o;

// Class cast exception // Class cast exception

Button mb = b.pop();

Cast authorized:

both Stack<String> and Stack<Button> map to class Stack

(20)

Type Erasure Type Erasure

ArrayList<Integer> li = new ArrayList<Integer>();

ArrayList<Float> lf = new ArrayList<Float>();

if (li.getClass() == lf.getClass()) { // evaluates to true

System.out.println("Equal");

}

(21)

Generic C#

 The CLR supports parametric typesThe CLR supports parametric types

 In IL placeholders are used to indicate type In IL placeholders are used to indicate type arguments (!0, !1, …)

arguments (!0, !1, …)

 When the program needs an instantiation of a When the program needs an instantiation of a generic type the

generic type the loaderloader generates the appropriate generates the appropriate typetype

 The JIT can share implementation of reference The JIT can share implementation of reference instantiations (

instantiations (Stack<String> has essentially the Stack<String> has essentially the same code of

same code of Stack<Object>Stack<Object>))

(22)

Generic C# compiler Generic C# compiler

 Template-like syntax with notation for Template-like syntax with notation for bounds

bounds

 NO type-inference on generic methods: the NO type-inference on generic methods: the type must be specified in the call

type must be specified in the call

 The compiler relies on GCLR to generate the The compiler relies on GCLR to generate the codecode

 Exact runtime types are granted by the CLR Exact runtime types are granted by the CLR so virtual generic methods are allowed

so virtual generic methods are allowed

 All type constructors can be parameterized: All type constructors can be parameterized:

struct, classes, interfaces and delegates.

(23)

Example Example

using System;

namespace n { namespace n {

public class Foo<T> { public class Foo<T> { T[] v; T[] v;

Foo() { v = new T[15]; } Foo() { v = new T[15]; } public static public static

void Main(string[] args) {void Main(string[] args) {

Foo<string> f = Foo<string> f =

new Foo<string>();new Foo<string>();

f.v[0] = "Hello";f.v[0] = "Hello";

string h = f.v[0];string h = f.v[0];

Console.Write(h);Console.Write(h);

} } } } }}

.field private !0[] v .field private !0[] v

.method private hidebysig .method private hidebysig

specialname specialname rtspecialname

rtspecialname

instance void .ctor() cil instance void .ctor() cil

managed { managed { .maxstack 2.maxstack 2 ldarg.0 ldarg.0

call instance void call instance void

[mscorlib]System.Object::.ct [mscorlib]System.Object::.ct or()or()

ldarg.0 ldarg.0

ldc.i4.s 15 ldc.i4.s 15 newarr !0 newarr !0

stfld !0[] class n.Foo<! stfld !0[] class n.Foo<!

0>::v 0>::v ret ret

} // end of method Foo::.ctor } // end of method Foo::.ctor

(24)

Performance of CLR Generics Performance of CLR Generics

 Despite instantiation being performed at load Despite instantiation being performed at load time, the overhead is minimal

time, the overhead is minimal

 Code sharing reduces instantiations, Code sharing reduces instantiations, improving execution speed

improving execution speed

 A technique based on dictionaries is A technique based on dictionaries is employed to keep track of previous employed to keep track of previous

instantiated types instantiated types

(25)

Expressive power of Expressive power of

Generics Generics

 System System F F is a typed is a typed -calculus with -calculus with polymorphic types

polymorphic types

 While Turing-equivalence is a trivial property While Turing-equivalence is a trivial property of programming languages, for a type-system of programming languages, for a type-system

being equivalent to System

being equivalent to System FF it is not it is not

 Polymorphic languages such as ML and Polymorphic languages such as ML and Haskell cannot fully express System

Haskell cannot fully express System F F (both (both languages have been extended to fill the gap) languages have been extended to fill the gap)

 System System FF can be transposed into C# can be transposed into C#

http://www.cs.kun.nl/~erikpoll/ftfjp/2002/Ken http://www.cs.kun.nl/~erikpoll/ftfjp/2002/Ken

nedySyme.pdf nedySyme.pdf

(26)

Liskov Substitution Principle Liskov Substitution Principle

 Sub-Typing/Sub-Classing defines the class Sub-Typing/Sub-Classing defines the class relation “

relation “BB is a sub-type of is a sub-type of A”, marked A”, marked B <: B <: AA..

 According to the substitution principle,According to the substitution principle, if if BB <: <: A, then an instance of A, then an instance of BB can be can be

substituted for an instance of substituted for an instance of AA..

 Therefore, it is legal to assign an instance Therefore, it is legal to assign an instance bb of of BB to to aa variable of type variable of type AA

A a = b;

(27)

Inheritance as Subtyping Inheritance as Subtyping

 Simple assumption:Simple assumption:

 If class B derives from class A then:

B <: A

(28)

Generics and Subtyping Generics and Subtyping

 Do the rules for sub-types and assignment work for Do the rules for sub-types and assignment work for generics?

generics?

If B <: A, then G<B> <: G<A>?

List<String> ls = new List<String>();

List<Object> lo = ls;

// Since String <: Object, so far so good.

lo.add(new Object());

String s = (String)ls.get(0); // Error!

The rule B <: A  G<B> <: G<A> defies the principle of substitution!

Counter example

(29)

Other example Other example

class B extends A { … } class B extends A { … } class G<E> {

class G<E> { public E e;public E e;

}}

G<B> gb = new G<B>();

G<A> ga = gb;

ga.e = new A();

B b = gb.e; //

B b = gb.e; // Error!Error!

Given

Given B <: A B <: A, and , and assuming

assuming G<B> <: G<A>G<B> <: G<A>, , then:

then:

G<A> ga = gb;

would be legal.

In Java, type is erased.

(30)

Bounded Wildcard Bounded Wildcard

A wildcard does not allow doing much A wildcard does not allow doing much

To provide operations with wildcard types, one To provide operations with wildcard types, one

can specify

can specify boundsbounds:: Upper Bound

Upper Bound The ancestor of unknown:The ancestor of unknown:

G<? extends X>

G<? extends X> JavaJava G<T> where T : X

G<T> where T : X C#C#

Lower Bound

Lower Bound The descendant of The descendant of unknown:

unknown:

G<? super Y>

G<? super Y> JavaJava G<T> where Y : T

G<T> where Y : T C#C#

(31)

Bounded Wildcards Bounded Wildcards

Subtyping Rules Subtyping Rules

For any B such that B <: A:

 G<B> <: G<? extends A>G<B> <: G<? extends A>

 G<A> <: G<? super B>G<A> <: G<? super B>

(32)

Bounded Wildcards - Bounded Wildcards -

Example Example

G<A> ga = new G<A>();

G<B> gb = new G<B>();

G<? extends A> gea = gb;

// Can read from // Can read from A a = gea.e;

A a = gea.e;

G<? super B> gsb = ga;

// Can write to // Can write to gsb.e = new B();

gsb.e = new B();

G<B> <: G<? extends A>

hence legal hence legal

G<A> <: G<? super B>

hence legal hence legal

(33)

Wildcard subtyping in Java Wildcard subtyping in Java

By Vilhelm.s - CC BY-SA 3.0

(34)

Generics and Polymorphism Generics and Polymorphism

class Shape { void draw() {…} } class Shape { void draw() {…} }

class Circle extends Shape { void draw() {…} } class Circle extends Shape { void draw() {…} }

class Rectangle extends Shape { void draw() {…} } class Rectangle extends Shape { void draw() {…} }

public void drawAll(Collection<Shape> shapes) { public void drawAll(Collection<Shape> shapes) { for (Shape s: shapes)for (Shape s: shapes)

s.draw();s.draw();

}}

 Does not work. Why?Does not work. Why?

 Cannot be used on Cannot be used on Collection<Circle>Collection<Circle>

(35)

Bounded Polymorphism Bounded Polymorphism

 Bind the wildcard: replace the type Bind the wildcard: replace the type

Collection<Shape>

Collection<Shape> with Collection<? extends Shape> with Collection<? extends Shape>::

public void drawAll(Collection<? extends Shape> shapes) {

for (Shape s: shapes) s.draw();

}

 Now Now drawAll()_drawAll() will accept lists of any subclass will accept lists of any subclass of of Shape_Shape

 The The ?_? Stands for an unknown subtype of Stands for an unknown subtype of Shape_Shape

 The type The type Shape _Shape is the is the upper boundupper bound of the of the wildcard

wildcard

(36)

Bounded Wildcard Bounded Wildcard

 There is a problem when using wildcards:There is a problem when using wildcards:

public void addCircle(Collection<?

extends Shape> shapes) { shapes.add(new Circle());

}

 What will happen? Why?What will happen? Why?

(37)

Covariance, Contravariance, Covariance, Contravariance,

Invariance Invariance

Given types A and B such that B <: A, a type Given types A and B such that B <: A, a type

constructor G is said:

 Covariant: if G<B> <: G<A>Covariant: if G<B> <: G<A>

 Contravariant: if G<A> <: G<B>Contravariant: if G<A> <: G<B>

 Invariant: if neither covariant nor Invariant: if neither covariant nor contravariant

contravariant

(38)

C# Variance Declaration C# Variance Declaration

interface IEnumerator<

interface IEnumerator<outout T> { T> { T Current { get; } T Current { get; }

bool MoveNext(); bool MoveNext();

} }

public delegate void Action<in T>(T obj);

Action<Shape> b = (shape) => { shape.draw(); };

Action<Circle> d = b; // Action<Shape> <: Action<Circle>

d(new Circle());

Action<Object> o = b; // illegal

A covariant type parameter can be used as the return type of a A covariant type parameter can be used as the return type of a delegate

delegate

A contravariant type parameters can be used as parameter typesA contravariant type parameters can be used as parameter types

a function argument is contravariant

The type of a result is covariant

(39)

Substitutability Principle Substitutability Principle

 If S is a subtype of T, then objects of type T may be replaced with objects of type S

without altering any of the desirable

properties of that program (e.g. correctness).

(40)

Liskov Substitution Principle Liskov Substitution Principle

Let Let ((xx)) be a true property of objects be a true property of objects xx of type T of type T. . Then

Then ((y)y) should be true for objects should be true for objects yy of type of type SS where

where SS is a subtype of is a subtype of TT..

Behavioral subtyping is a stronger notion than nominal or structural subtyping

(41)

Nominal Subtyping (Duck Nominal Subtyping (Duck

Typing) Typing)

 If objects of class A can handle all of the

messages that objects of class B can handle (that is, if they define all the same methods), then A is a subtype of B regardless of

inheritance.

If it walks like a duck and swims like a duck and quacks like a duck, I call it a duck.

(42)

Structural Subtyping Structural Subtyping

 In structural typing, an element is considered to be compatible with another if, for each

feature within the second element's type,

there is a corresponding and identical feature in the first element's type.

 Subtype polymorphism is structural subtyping

 Inheritance is not subtyping in structurally- typed OO languages:

 if a class defines a methods that takes arguments or returns values of its own type

(43)

Liskov Signature Liskov Signature

Requirements Requirements

 Matching function or method types involves Matching function or method types involves deciding on subtyping on method signatures deciding on subtyping on method signatures

 Methods argument types must obey Methods argument types must obey contravariance

contravariance

 Return types must obey covarianceReturn types must obey covariance

(44)

Examples Examples

 AssumingAssuming

 Cat <: Animal

 Enumerable<T> is covariant on T

 Action<T> is contravariant on T

 Enumerable<Cat> is a subtype of Enumerable<Cat> is a subtype of

Enumerable<Animal>. The subtyping is Enumerable<Animal>. The subtyping is

preserved.

 Action<Animal> is a subtype of Action<Cat>. Action<Animal> is a subtype of Action<Cat>.

The subtyping is reversed.

 Neither List<Cat> nor List<Animal> is a subtype Neither List<Cat> nor List<Animal> is a subtype of the other, because List<T> is invariant on T.

of the other, because List<T> is invariant on T.

(45)

A Typical Violation A Typical Violation

 Class Square derived from class Rectangle, if Class Square derived from class Rectangle, if for example methods from class Rectangle

for example methods from class Rectangle are allowed to change width/height

are allowed to change width/height independently

independently

(46)

Contravariance of Arguments Contravariance of Arguments

Types Types

public class SuperType {

public virtual string AgeString(short age) { return age.ToString();

} }

public class LSPLegalSubType : SuperType { public override string AgeString(int age) {

// This is legal due to the Contravariance requirement // widening the argument type is allowed

return age.ToString();

} }

public class LSPIllegalSubType : SuperType { public override string AgeString(byte age) {

// illegal due to the Contravariance requirement return base.AgeString((short)age);

} }

(47)

Covariance of return Type Covariance of return Type

public class SuperType {

public virtual int DaysSinceLastLogin(User user) { return int.MaxValue;

} }

public class LSPLegalSubType : SuperType {

public override short DaysSinceLastLogin(User user) {

return short.MaxValue; // Legal because it will always fit into a n int

} }

public class LSPIllegalSubType : SuperType {

public override long DaysSinceLastLogin(User user) { return long.MaxValue;

// Illegal because it will not surely fit into an int }

}

(48)

To wildcard or not to To wildcard or not to

wildcard?

 That is the question:That is the question:

interface Collection<E> {

public <T> boolean containsAll(Collection<T> c);

public <T extends E> boolean addAll(Collection<T> c);

}

interface Collection<E> {

public boolean containsAll(Collection<?> c);

public boolean addAll(Collection<? extends E> c);

}

(49)

Lower Bound Example Lower Bound Example

interface sink<T> { interface sink<T> { flush(T t);flush(T t);

}}

public <T> T public <T> T

flushAll(Collection<T>

col, Sink<T> sink) col, Sink<T> sink) {{

T last;T last;

for (T t: col) {for (T t: col) { last = t;last = t;

sink.flush(t);sink.flush(t);

}}

return last;return last;

}}

(50)

Lower Bound Example (2) Lower Bound Example (2)

Sink<Object> s;

Collection<String> cs;

String str = flushAll(cs, s); //

String str = flushAll(cs, s); // Error!Error!

(51)

Lower Bound Example (3) Lower Bound Example (3)

public <T> T flushAll(Collection<T> col, public <T> T flushAll(Collection<T> col,

Sink<T> sink) { … } Sink<T> sink) { … }

……

String str = flushAll(cs, s); // Error!Error!

TT is now solvable as is now solvable as ObjectObject, but it is not the , but it is not the correct type: it should be

correct type: it should be String_String

(52)

Lower Bound Example (4) Lower Bound Example (4)

public <T> T flushAll(Collection<T> col, Sink<?

Super T> sink) { … } Super T> sink) { … }

……

String str = flushAll(cs, s); // OK!OK!

(53)

Combining generics and Combining generics and

inheritance inheritance

 The inheritance relation must be extended The inheritance relation must be extended with a new subtyping rule:

with a new subtyping rule:

 Can now cast up and down to Can now cast up and down to ObjectObject safely safely

 Note: types must be substituted because the Note: types must be substituted because the super-class can be parametric

super-class can be parametric

Given

class C<T₁,...,T_n> extends B

we have

C<t₁,...,t_n> <: B[t₁/T₁, ..., t_n/T_n]

(54)

Manipulating types Manipulating types

 Grouping values into types has helped us Grouping values into types has helped us to build better compilers

to build better compilers

 Could we do the same with types?Could we do the same with types?

 Types can be grouped by means of Types can be grouped by means of

inheritance which represents the union of inheritance which represents the union of

type sets type sets

 Parametric types combined with Parametric types combined with inheritance allow expressing

inheritance allow expressing function on function on types

types::

class Stack<T:Object> : Container

Function name Function arguments Result type

(55)

Example: generic containers Example: generic containers

class Row<T : Control> : Control class Row<T : Control> : Control { /* row of graphic controls *> } { /* row of graphic controls *> } class Column<T : Control> : Control class Column<T : Control> : Control { /* column of graphic controls */ } { /* column of graphic controls */ }

class Table<T : Control> : Row<Column<T>>

{ /* Table of graphic controls */ } { /* Table of graphic controls */ }

……

// It generates the keypad of a calculator // It generates the keypad of a calculator Table<Button> t = new Table<Button>(3, 3);

Table<Button> t = new Table<Button>(3, 3);

for (int i = 0; i < 3; i++) for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) for (int j = 0; j < 3; j++)

t[i, j].Text = (i * 3 + j + 1).ToString();t[i, j].Text = (i * 3 + j + 1).ToString();