Types Types

(1)

Types Types

Antonio Cisternino Antonio Cisternino

Giuseppe Attardi

Università di Pisa

(2)

Types Types

 Computer hardware is capable of Computer hardware is capable of

interpreting bits in memory in several interpreting bits in memory in several

different ways different ways

 A type limits the set of operations that A type limits the set of operations that

may be performed on a value belonging to may be performed on a value belonging to

that type that type

 The hardware usually doesn’t enforce the The hardware usually doesn’t enforce the notion of type, though it provides

notion of type, though it provides

operations for numbers and pointers operations for numbers and pointers

 Programming languages tend to associate Programming languages tend to associate types to values to enforce error-checking types to values to enforce error-checking

(3)

Type System Type System



A type system consists of: A type system consists of:

– A mechanism for defining types and

associating them with certain language constructs

– A set of rules for:

• type equivalence: two values are the same

• type compatibility: a value of a given type can be used in a given context

• type inference: type of an expression given the type of its constituents

(4)

Type checking Type checking

 Type checkingType checking is the process of ensuring is the process of ensuring that a program obeys the language’s type that a program obeys the language’s type

compatibility rules compatibility rules

 A language is A language is strongly typedstrongly typed (or (or type safetype safe) if ) if it prohibits, in a way that the language

it prohibits, in a way that the language

implementation can enforce, performing an implementation can enforce, performing an

operation on an object that does not support operation on an object that does not support itit

 A language is A language is statically typedstatically typed if it is if it is strongly strongly typed

typed and type checking can be performed at and type checking can be performed at compile time

compile time

(5)

Programming Languages and type checking Programming Languages and type checking

 AssemblyAssembly

 CC

 PascalPascal

 C++C++

 JavaJava

 LispLisp

 PrologProlog

 MLML

No type checking

Static type checking

Not entirely strongly typed (union, interoperability of pointers and arrays) Static type checking

Not entirely strongly typed (untagged variant records)

Static type checking

Not entirely strongly typed (as C)

Dynamic type checking (virtual methods) Static type checking

Dynamic type checking (virtual methods, upcasting)

Strongly typed

Dynamic type checking Strongly typedDynamic type checking

Strongly typed

Static type checking Strongly typed

(6)

Different views for types Different views for types

 Denotational:Denotational:

– types are set of values (domains) – Application: semantics

 Constructive:Constructive:

– Built-in types

– Composite types (application of type constructors)

 Abstraction-based:Abstraction-based:

– Type is an interface consisting of a set of operations

(7)

Language types Language types

 booleanboolean

 int, long, float, double (signed/unsigned)int, long, float, double (signed/unsigned)

 character (1 byte, 2 bytes)character (1 byte, 2 bytes)

 EnumerationEnumeration

 Subrange (Subrange (nn₁₁....nn₂₂))

 Composite types:Composite types:

– struct – union – arrays – pointers – list

(8)

Type Conversions and Type Conversions and

Casts Casts



Consider the following definition: Consider the following definition:

int add(int i, int j);

int add2(int i, double j);



And the following calls: And the following calls:

add(2, 3); // Exact

add(2, (int)3.0); // Explicit cast

add2(2, 3); // Implicit cast

(9)

Memory Layout Memory Layout



Primitive types on 32 bits Primitive types on 32 bits

architectures require from 1 to 8 architectures require from 1 to 8

bytes bytes



Composite types are represented by Composite types are represented by chaining constituent values together chaining constituent values together



For performance reasons often For performance reasons often

compilers employ padding to align compilers employ padding to align

fields to multiple of 4 bytes fields to multiple of 4 bytes

addresses

(10)

Memory layout example Memory layout example

struct element { struct element { char name[2];char name[2];

int atomic_number;int atomic_number;

double atomic_weight;double atomic_weight;

char metallic;char metallic;

};};

4 bytes/32 bits name

atomic_number atomic_weight metallic

(11)

Optimizing Memory Layout Optimizing Memory Layout

 C requires that fields of struct be placed in C requires that fields of struct be placed in the same order of the declaration

the same order of the declaration

(essential for working with pointers!) (essential for working with pointers!)

 Not all languages behaves like this: for Not all languages behaves like this: for instance ML doesn’t specify any order instance ML doesn’t specify any order

 If the compiler is free of reorganizing If the compiler is free of reorganizing fields holes can be minimized (in the fields holes can be minimized (in the

example by packing

example by packing metallicmetallic with with name name saving 4 bytes)

saving 4 bytes)

(12)

4 bytes/32 bits name

atomic_number atomic_weight metallic

Union Union

 Union types allow sharing the same memory Union types allow sharing the same memory area among different types

area among different types

 The size of the value is the maximum of the The size of the value is the maximum of the constituents

constituents

4 bytes/32 bits

number union u {

struct element e;

int number;

};

(13)

Abstract Data Types Abstract Data Types

 According to the abstraction-based view According to the abstraction-based view of types a type is an interface

of types a type is an interface

 An ADT defines a set of values and the An ADT defines a set of values and the operations allowed on it

operations allowed on it

 In their evolution programming languages In their evolution programming languages have included mechanisms to define ADT have included mechanisms to define ADT

 Definition of an ADT requires the ability of Definition of an ADT requires the ability of incapsulating values and operations

incapsulating values and operations

(14)

Example: a C list Example: a C list

struct node { struct node { int val;int val;

struct list *next;struct list *next;

};};

struct node* next(struct node* l) { return l->next; } struct node* next(struct node* l) { return l->next; } struct node* initNode(struct node* l, int v) {

struct node* initNode(struct node* l, int v) { l->val = v; l->next = NULL; return l;l->val = v; l->next = NULL; return l;

}}

void append(struct node* l, int v) { void append(struct node* l, int v) { struct node p = l;struct node p = l;

while (p->next) p = p->next;while (p->next) p = p->next;

p->next = p->next =

initNode((struct node)malloc(sizeof(struct node)), initNode((struct node)malloc(sizeof(struct node)), v);v);

}}

(15)

ADT, Modules and Classes ADT, Modules and Classes

 C doesn’t provide any mechanism to hide C doesn’t provide any mechanism to hide the structure of data types

the structure of data types

 A program can access the A program can access the nextnext pointer pointer without using the

without using the nextnext function function

 The notion of module has been introduced The notion of module has been introduced to define data types and restrict the

to define data types and restrict the access to their definition

access to their definition

 An evolution of module is the class: An evolution of module is the class:

values and operations are tied together values and operations are tied together

(with the addition of inheritance) (with the addition of inheritance)

(16)

Class type Class type

 Class is a Class is a type constructortype constructor like struct and like struct and array

array

 A class combines other types like structsA class combines other types like structs

 Class definition contains also methods Class definition contains also methods which are the operations allowed on the which are the operations allowed on the datadata

 The The inheritance inheritance relation is introducedrelation is introduced

 Two special operations provide control Two special operations provide control over initialization and finalization of

over initialization and finalization of objects

objects

(17)

The Node Type in Java The Node Type in Java

class Node { class Node { int val;int val;

Node m_next; Node m_next;

Node(int v) { val = v; } Node(int v) { val = v; }

Node next() { return m_next; }Node next() { return m_next; } void append(int v) { void append(int v) {

Node n = this; Node n = this;

while (n.m_next != null) n = n.m_next;while (n.m_next != null) n = n.m_next;

n.m_next = new Node(v); n.m_next = new Node(v);

} } } }

(18)

Inheritance Inheritance



If the class If the class A A inherits from class inherits from class B B ( ( A<:B A<:B ) when an object of class ) when an object of class B B is is

expected an object of class

expected an object of class A A can be can be used instead

used instead



Inheritance expresses the idea of Inheritance expresses the idea of adding features to an existing type adding features to an existing type

(both methods and attributes) (both methods and attributes)



Inheritance can be single or multiple Inheritance can be single or multiple

(19)

Example Example

class A { class A { int i;int i;

int j;int j;

int foo() { return i + j; }int foo() { return i + j; } }}

class B : A { class B : A { int k;int k;

int foo() { return k + super.foo(); }int foo() { return k + super.foo(); } }}

(20)

Questions Questions

 Consider the following:Consider the following:

A a = new A();

A b = new B();

Console.WriteLine(a.foo());

Console.WriteLine(b.foo());

 Which version of Which version of foofoo is invoked in the is invoked in the second print?

second print?

 What is the layout of class What is the layout of class BB??

(21)

Upcasting Upcasting

 Late binding happens because we convert a Late binding happens because we convert a

reference to an object of class B into a reference reference to an object of class B into a reference

of its super-class A

of its super-class A (upcasting(upcasting))::

B b = new B();

A a = b;

 The runtime should not convert the object: only The runtime should not convert the object: only use the part inherited from A

use the part inherited from A

 This is different from the following implicit cast This is different from the following implicit cast where the data is modified in the assignment:

where the data is modified in the assignment:

int i = 10;

long l = i;

(22)

Downcasting Downcasting

 Once we have a reference of the super-Once we have a reference of the super- class we may want to convert it back:

class we may want to convert it back:

A a = new B();

B b = (B)a;

 During During downcastdowncast it is necessary to it is necessary to explicitly indicate which class is the explicitly indicate which class is the

target: a class may be the ancestor of target: a class may be the ancestor of

many sub-classes many sub-classes

 Again this transformation informs the Again this transformation informs the compiler that the referenced object is of compiler that the referenced object is of

type B without changing the object in any type B without changing the object in any wayway

(23)

Upcasting, downcasting Upcasting, downcasting

 We have shown upcasting and downcasting as We have shown upcasting and downcasting as expressed in languages such as C++, C# and expressed in languages such as C++, C# and

Java; though the problem is common to OO Java; though the problem is common to OO

languages languages

 Note that the upcast can be verified at compile Note that the upcast can be verified at compile time whereas the downcast cannot

time whereas the downcast cannot

 Upcasting and downcasting don’t require runtime Upcasting and downcasting don’t require runtime type checking:

type checking:

– in Java casts are checked at runtime

– C++ simply changes the interpretation of an expression at compile time without any attempt to check it at

runtime

(24)

Late Binding Late Binding

 The output of the example depends on the The output of the example depends on the language: the second output may be the language: the second output may be the

result of invoking

result of invoking A::foo()A::foo() or or B::foo()B::foo()

 In Java the behavior would result in the In Java the behavior would result in the invocation of

invocation of B::fooB::foo

 In C++ In C++ A::fooA::foo would be invoked would be invoked

 The mechanism which associates the The mechanism which associates the method

method B::foo()B::foo() to to b.foo()b.foo() is called is called late late binding

binding

(25)

Late Binding Late Binding

 In the example the compiler cannot determine statically In the example the compiler cannot determine statically the exact type of the object referenced by

the exact type of the object referenced by bb because of because of upcasting

upcasting

 To allow the invocation of the method of the exact type To allow the invocation of the method of the exact type rather than the one known at compile time it is

rather than the one known at compile time it is necessary to pay an overhead at runtime

necessary to pay an overhead at runtime

 Programming languages allow the programmer to Programming languages allow the programmer to specify whether to apply late binding in a method specify whether to apply late binding in a method

invocation invocation

 In Java the keyword In Java the keyword final is used to indicate that a final is used to indicate that a

method cannot be overridden in subclasses: thus the method cannot be overridden in subclasses: thus the

JVM may avoid late binding JVM may avoid late binding

 In C++ only methods declared as In C++ only methods declared as virtualvirtual are considered are considered for late binding

for late binding

(26)

Late Binding Late Binding

 With inheritance it is possible to treat objects in a With inheritance it is possible to treat objects in a generic way

generic way

 The benefit is evident: it is possible to write The benefit is evident: it is possible to write

generic operations manipulating objects of types generic operations manipulating objects of types

inheriting from a common ancestor inheriting from a common ancestor

 OOP languages usually support late binding of OOP languages usually support late binding of methods: which method should be invoked is methods: which method should be invoked is

determined at runtime determined at runtime

 This mechanism involves a small runtime This mechanism involves a small runtime

overhead: at runtime the type of an object should overhead: at runtime the type of an object should

be determined in order to invoke its methods be determined in order to invoke its methods

(27)

Example (Java) Example (Java)

class A { class A {

final void foo() {…}final void foo() {…}

void baz() {…}void baz() {…}

void bar() {…}void bar() {…}

}}

class B extends A { class B extends A {

// Suppose it’s possible! // Suppose it’s possible!

final void foo() {…}final void foo() {…}

void bar();void bar();

}}

A a = new A();

B b = new B();

A c = b;

a.foo();

a.foo(); // A::foo()// A::foo() a.baz();

a.baz(); // A::baz()// A::baz() a.bar();

a.bar(); // A::bar()// A::bar() b.foo();

b.foo(); // B::foo()// B::foo() b.bar();

b.bar(); // B::bar()// B::bar() c.foo();

c.foo(); // A::foo()// A::foo() c.bar();

c.bar(); // B::bar()// B::bar()

(28)

Abstract classes Abstract classes

 Sometimes it is necessary to model a set Sometimes it is necessary to model a set S of S of objects which can be partitioned into subsets (

objects which can be partitioned into subsets (AA0₀, … , … AA_n_n) such that their union covers ) such that their union covers S:S:

 x  S  Ai  S, x  Ai

 If we use classes to model each set it is natural thatIf we use classes to model each set it is natural that

  A  S, A<:S

 Each object is an instance of a subclass of Each object is an instance of a subclass of SS and no and no object is an instance of

object is an instance of SS..

 SS is useful because it abstracts the commonalities is useful because it abstracts the commonalities among its subclasses, allowing to express generic among its subclasses, allowing to express generic properties about its objects.

properties about its objects.

(29)

Example Example

 We want to manipulate documents with different We want to manipulate documents with different formats

formats

 The set of documents can be partitioned by type: The set of documents can be partitioned by type:

docdoc, , pdfpdf, , txttxt, and so on, and so on

 For each document type we introduce a class that For each document type we introduce a class that inherits from a class

inherits from a class DocDoc that represents the that represents the document

document

 In the class In the class DocDoc we may store common we may store common

properties to all documents (title, location, …) properties to all documents (title, location, …)

 Each class is responsible for reading the Each class is responsible for reading the document content

document content

 It doesn’t make sense to have an instance of It doesn’t make sense to have an instance of DocDoc though it is useful to scan a list of documents to though it is useful to scan a list of documents to readread

(30)

Abstract methods Abstract methods

 Often when a class is abstract some of its Often when a class is abstract some of its methods could not be defined

methods could not be defined

 Consider the method Consider the method read()read() in the in the previous example

previous example

 In class In class DocDoc there is no reasonable there is no reasonable implementation for it

implementation for it

 We leave it We leave it abstractabstract so that through late so that through late binding the appropriate implementation binding the appropriate implementation

will be called will be called

(31)

Syntax Syntax

 Abstract classes can be declared using the Abstract classes can be declared using the abstract abstract keyword in Java or C#:

keyword in Java or C#:

abstract class Doc { … }

 C++ assumes a class is abstract if it contains an C++ assumes a class is abstract if it contains an abstract method

abstract method

– it is impossible to instantiate an abstract class, since it will lack that method

 A virtual method is abstract in C++ if its definition is A virtual method is abstract in C++ if its definition is empty:

empty:

virtual string Read() = 0;

 In Java and C# abstract methods are annotated with In Java and C# abstract methods are annotated with abstract

abstract and no body is provided: and no body is provided:

abstract String Read();

(32)

Inheritance Inheritance

 Inheritance is a relation among classesInheritance is a relation among classes

 Often systems impose some restriction on Often systems impose some restriction on inheritance relation for convenience

inheritance relation for convenience

 We say that class A is an We say that class A is an interfaceinterface if all its if all its members are abstract; has no fields and members are abstract; has no fields and

may inherit only from one or more may inherit only from one or more

interfaces interfaces

 Inheritance can be:Inheritance can be:

– Single (A <: B  (C. A <: C  C = B))

– Mix-in (S = {B | A <: B}, 1 BS  ¬interface(B)) – Multiple (no restriction)

(33)

Multiple inheritance Multiple inheritance

 Why systems should impose restrictions on inheritance?Why systems should impose restrictions on inheritance?

 Multiple inheritance introduces both conceptual and Multiple inheritance introduces both conceptual and implementation issues

implementation issues

 The crucial problem, in its simplest form, is the following:The crucial problem, in its simplest form, is the following:

– B <: A  C <: A – D <: B  D <: C

 In presence of a common ancestor:In presence of a common ancestor:

– The instance part from A is shared between B and C – The instance part from A is duplicated

 This situation is not infrequent: in C++ This situation is not infrequent: in C++ iosios:>:>istreamistream, ,

iosios:>:>ostreamostream and and iostreamiostream<:<:istreamistream, , iostreamiostream<:<:ostreamostream

 The problem in sharing the ancestor A is that B and C may The problem in sharing the ancestor A is that B and C may change the inherited state in a way that may lead to

change the inherited state in a way that may lead to conflicts

conflicts

(34)

Java and Mix-in Java and Mix-in

inheritance inheritance

 Both single and mix-in inheritance fix the common Both single and mix-in inheritance fix the common ancestor problem

ancestor problem

 Though single inheritance can be somewhat Though single inheritance can be somewhat restrictive

restrictive

 Mix-in inheritance has become popular with Java Mix-in inheritance has become popular with Java and represents an intermediate solution

and represents an intermediate solution

 Classes are partitioned into two sets: interfaces and Classes are partitioned into two sets: interfaces and normal classes

normal classes

 Interfaces constraints elements of the class to be Interfaces constraints elements of the class to be only abstract methods: no instance variables are only abstract methods: no instance variables are allowed

allowed

 A class inherits instance variables only from one of A class inherits instance variables only from one of its ancestors avoiding the diamond problem of

its ancestors avoiding the diamond problem of multiple inheritance

multiple inheritance

(35)

Implementing Single and Implementing Single and

Mix-in inheritance Mix-in inheritance



Consists only in combining the state of Consists only in combining the state of a class and its super-classess

a class and its super-classess

A A

B

A B<:A

A

B C<:B<:A

A

B

D<:C<:B<:A

D

Note that Upcasting and Downcasting comes for free: the pointer at the base of the instance can be seen both as a pointer to an instance of A or B

(36)

Implementing multiple Implementing multiple

inheritance inheritance



With multiple inheritance becomes more With multiple inheritance becomes more complex than reinterpreting a pointer!

complex than reinterpreting a pointer!

A A

B

A B<:A

A C C<:A

A

A (C) A (B) B

C B

D C

D

D<:B, D<:C D<:B, D<:C

(37)

Late binding Late binding

 How to identify which method to invoke?How to identify which method to invoke?

 Solution: use a Solution: use a v-table v-table for each class that has for each class that has polymorphic methods

polymorphic methods

 Each virtual method is assigned a slot in the table Each virtual method is assigned a slot in the table pointing to the method code

pointing to the method code

 Invoking the method involves looking up in the table Invoking the method involves looking up in the table at a specific offset to retrieve the address to use in at a specific offset to retrieve the address to use in the the callcall instruction instruction

 Each instance holds a pointer to the Each instance holds a pointer to the v-tablev-table

 Thus late binding incurs an overhead both in time (2 Thus late binding incurs an overhead both in time (2 indirections) and space (one pointer per object)

indirections) and space (one pointer per object)

 The overhead is small and often worth the benefitsThe overhead is small and often worth the benefits

(38)

Late binding: an example Late binding: an example

(Java) (Java)

void foo() {…} void foo() {…}

void f() {…} void f() {…}

int ai; int ai;

}}

class B extends A { class B extends A { void foo() {…} void foo() {…}

void g() {…} void g() {…}

int bi; int bi;

}}

foo f

foo f g A’s v-table

B’s v-table

ai V-pointer

bi

A a = new A();

a.foo();

a.f();

B b = new B();

b.foo();

b.g();

b.f();

A c = b;

c.foo();

c.f();

a b

c

(39)

Overriding and Overriding and

Overloading Overloading

void foo() {…} void foo() {…}

void f() {…} void f() {…}

}}

class B extends A { class B extends A {

void foo(int i) {…}void foo(int i) {…}

void g() {…} void g() {…}

}}

foo() f

g A’s v-table

B’s v-table

ai V-pointer

bi

A a = new A();

a.foo();

a.f();

B b = new B();

b.foo();

b.g();

b.f();

A c = b;

c.foo(3);

c.f();

a b

c

foo(int)

(40)

JVM invokevirtual JVM invokevirtual

 A call like:A call like:

x.equals("test")

 is translated into:is translated into:

aload_1 ; push local variable 1 (x) onto the operand stack ldc "test" ; push string "test" onto the operand

stack

invokevirtual

java.lang.Object.equals(Ljava.lang.Object;)Z

 where where

java.lang.Object.equals(Ljava.lang.Object;)Z

java.lang.Object.equals(Ljava.lang.Object;)Z is a is a method specification

method specification

 When invokevirtual is executed, the JVM looks at method When invokevirtual is executed, the JVM looks at method specification and determines its # of args

specification and determines its # of args

 From the object reference it retrieves the class, searches From the object reference it retrieves the class, searches the list of methods for one matching the method descriptor.

the list of methods for one matching the method descriptor.

 If not found, searches its superclassIf not found, searches its superclass

(41)

Invokevirtual optimization Invokevirtual optimization

 The Java compiler can arrange every The Java compiler can arrange every subclass method table (mtable) in the subclass method table (mtable) in the

same way as its superclass, ensuring that same way as its superclass, ensuring that

each method is located at the same offset each method is located at the same offset

 The bytecode can be modified after first The bytecode can be modified after first execution, by replacing with:

execution, by replacing with:

invokevirtual_quick mtable-offset

 Even when called on objects of different Even when called on objects of different types, the method offset will be the same types, the method offset will be the same

(42)

Virtual Method in Interface Virtual Method in Interface

 Optimization does not work for interfacesOptimization does not work for interfaces

interface Incrementable { public void interface Incrementable { public void

incr(); } incr(); }

class Counter implements Incrementable class Counter implements Incrementable {{

public void incr(); }public void incr(); }

class Timer implements Incrementable { class Timer implements Incrementable { public void decr();public void decr();

public void inc(); }public void inc(); } Incrementable i;

Incrementable i;

i.incr();

 Compiler cannot guarantee that method incr() is Compiler cannot guarantee that method incr() is at the same offset.

at the same offset.

(43)

Runtime type information Runtime type information

 Execution environments may use the v-table Execution environments may use the v-table pointer as a mean of knowing the exact type pointer as a mean of knowing the exact type

of an object at runtime of an object at runtime

 This is what happens in C++ with RTTI, in .NET This is what happens in C++ with RTTI, in .NET CLR and JVM

CLR and JVM

 Thus the cost of having exact runtime type Thus the cost of having exact runtime type information is allocating the v-pointer to all information is allocating the v-pointer to all

objects objects

 C++ leaves the choice to the programmer: C++ leaves the choice to the programmer:

without RTTI no v-pointer is allocated in without RTTI no v-pointer is allocated in

classes without virtual methods classes without virtual methods

(44)

Overloading Overloading

 Overloading is the mechanism that a Overloading is the mechanism that a

language may provide to bind more than language may provide to bind more than

one object to a name one object to a name

 Consider the following class:Consider the following class:

class A {

void foo() {…}

void foo(int i) {…}

}

 The name The name foofoo is overloaded and it is overloaded and it identifies two methods

identifies two methods

(45)

Method overloading Method overloading

 Overloading is mostly used for methods because the compiler Overloading is mostly used for methods because the compiler may infer which version of the method should be invoked by may infer which version of the method should be invoked by looking at argument types

looking at argument types

 Behind the scenes the compiler generates a name for the Behind the scenes the compiler generates a name for the

method which includes the type of the signature (not the return method which includes the type of the signature (not the return type!)

type!)

 This process is known as name manglingThis process is known as name mangling

 In the previous example the name In the previous example the name foo_v may be associated to foo_v may be associated to the first method and

the first method and foo_ifoo_i to the second to the second

 When the method is invoked the compiler looks at the types of When the method is invoked the compiler looks at the types of the arguments used in the call and chooses the appropriate the arguments used in the call and chooses the appropriate version of the method

version of the method

 Sometimes implicit conversions may be involved and the Sometimes implicit conversions may be involved and the

resolution process may lead to more than one method: in this resolution process may lead to more than one method: in this case the call is considered ambiguous and a compilation error case the call is considered ambiguous and a compilation error is raised

is raised

(46)

Operator overloading Operator overloading

 Syntax for operators such as + and – have Syntax for operators such as + and – have is different from invocation of the function is different from invocation of the function

they represent they represent

 C++ and other languages (i.e. C#) allow C++ and other languages (i.e. C#) allow overloading these operators in the same overloading these operators in the same

way as ordinary functions and methods way as ordinary functions and methods

 Conceptually each invocation of + is Conceptually each invocation of + is

reinterpreted as a function invocation so reinterpreted as a function invocation so the standard overloading process applies the standard overloading process applies

 Example (C++):Example (C++):

c = a + b; // operator=(c, operator+

(a, b))

(47)

Late binding: only on first Late binding: only on first

argument argument

void foo(A a) {…} void foo(A a) {…}

void f() {…} void f() {…}

}}

class B extends A { class B extends A { void foo(B b) {…} void foo(B b) {…}

void g() {…} void g() {…}

}}

foo() f

foo(A) f

g A’s v-table

B’s v-table

ai V-pointer

bi

A a = new A();

a.foo();

a.f();

B b = new B();

b.foo();

b.g();

b.f();

A c = b;

c.foo(c);

c.f();

a b

c

foo(B)