Multiple Inheritance
Seminario curato da
Emanuele Debenedetti
Paolo Gasti
Angela Locoro
Perché usare l’ereditarietà multipla
• Consideriamo di voler simulare una rete di computer:
Switch
Librerie di
sistema
Classe
NetworkDevice
Classe
Displayed
Classe
Terminal
Terminals
•L’ereditarietà multipla permette di combinare
concetti indipendenti
•Permette di modellare molti problemi in
maniera più elegante
•I vantaggi risultano ancora più evidenti se si
aumenta il numero di classi di base
Svantaggi di questo approccio

Non è sempre banale comprendere il
comportamento di costruttori e distruttori

Realizzare di una implementazione efficiente è più
complessa rispetto al caso dell’ereditarietà singola

Oggi si tende a enfatizzare la differenza tra
sottotipazione e derivazione dell’implementazione

Spesso si incontra il problema del diamante
Il problema del diamante

Se una classe eredita operazioni con
lo stesso nome da più di un genitore
avviene un conflitto

Ci sono due strategie d’uso comune
per gestire questa situazione:
 gestire direttamente il grafo di
ereditarietà
 trasformarlo in una catena lineare e
gestirlo come ereditarietà singola
Z
Y1
Y2
X
Soluzione Graph – Oriented

La semantica di tali linguaggi modella
direttamente il grafo di ereditarietà

Se un’operazione è definita solo dalla
classe z, è ereditata da y1 e da x
senza errori

Si deve prevedere il caso di
ridefinizione dei metodi doppi da
parte di y2
Z
Y1
Y2
X
Soluzione Lineare
Z


Y2

La gerarchia di derivazione viene
linearizzata
Si elimina l’invocazione multipla di
metodi della soluzione precedente
Svantaggi

Y1

X

Lo sviluppatore non è al corrente della
gerarchia di sottotipazione implicita
La selezione del metodo da utilizzare è a
discrezione del compilatore
Problemi nel collegamento con il genitore
effettivo
La soluzione del C++

Per ogni classe specificata come non virtuale l’oggetto
della classe derivata conterrà un subobject di quel tipo
L
L
A
B
C
class L {....}
class A: public L {....}
class B: public L {....}
class C: public A, public B {....}
Per un metodo f
definito in L
occorrerà definire
esplicitamente a quale
dei due subobject L si
vuol fare riferimento:
es. void C::f()
{A::next = B::next}
si riferisce ad
entrambi
La soluzione del C++

Una classe può avere derivazioni virtuali e
non virtuali
B
X
B
Y
Z
AA
class B {....}
class X: virtual public B {....}
class Y: virtual public B {....}
class Z: public B {....}
class AA: public X, public Y, public Z {....}
Ogni oggetto di classe
AA avrà un’occorrenza
del subobject B per ogni
occorrenza virtuale di B
ed un subobject di B per
ogni singola occorrenza
di B non virtuale
nell’esempio due
occorrenze di B: il B di Z
e il B virtuale condiviso
da X ed Y
Implementazione di un oggetto





Un istanza di un oggetto è rappresentata in modo
simile a un record
Si implementa mediante un’area di memoria contigua
Contiene informazioni sulle variabili disposte in
ordine di dichiarazione
Non necessita di informazioni sui suoi metodi non
virtuali
Contiene un puntatore alla virtual method table
(VMT)
Implementazione dell’ereditarietà singola

Consideriamo gli oggetti istanziati dalle seguenti classi:
class thing
{
int age;
}
class animal : thing
{
string food;
}
class leggedAnimal : animal
{
int noOfLegs;
}
Implementazione dell’ereditarietà multipla

Utilizzando lo schema precedente, i campi degli oggetti verranno disposti in
memoria nel seguente modo:
class animal : thing
{
string food;
}
class leggedThing : thing
{
int noOfLegs;
}
class leggedAnimal : animal, leggedThing
{
}
•Utilizzando slot con indirizzo fisso vengono lasciati gap, sprecando spazio
•Non è possibile decidere a priori quanto spazio lasciare perché per ogni classe
esistono infinite classi derivate
Implementazione dell’ereditarietà multipla

Nello schema implementativo tradizionale leggedAnimal sarà:
(thing *) pLeggedAnimal, pLeggedAnimal
thing
(animal *) pLeggedAnimal
animal
leggedThing
VMT *
Variabili di classe statiche
Virtual Method Table
this
Codice dei metodi
Implementazione classica e il casting


Il casting esplicito costringe a sommare o
sottrarre un delta al puntatore alla classe
Nasce il problema del puntatore a NULL
(thing *) pLeggedAnimal, pLeggedAnimal
thing
(animal *) pLeggedThing
animal
pAnimal = pLeggedAnimal + Delta(thing, animal)
pLeggedAnimal = pAnimal – Delta(thing, animal)
leggedThing
pLeggedAnimal = (pAnimal==0) ? 0 : (pAnimal – Delta(thing, animal))
Implementazione mediante Address Map

È posizionata all’inizio di ogni oggetto

Contiene i riferimenti ai suoi campi sotto forma di
stringa – puntatore

L’aggiunta di nuovi campi è molto semplice

Si può ridurre la dimensione degli indici sostituendoli
con codici di hash
Implementazione mediante Address Map

Per una maggiore efficienza spaziale si può utilizzare una sola copia
dell’address map per ogni tipo di oggetto

Resta ancora il limite della ricerca basata su hashing
Si può allora introdurre un dizionario che metta in relazione una
stringa e un indice intero, ma si rendono più complicati il
decentramento e la compilazione separata

Implementazione mediante Address Map


Ogni oggetto può essere visto da più punti di vista
Mediante più address map è semplice realizzare
un’implementazione efficiente
Twin Object

I twin object sono un modo di esprimere la
multiple inheritance usando la single inheritance

I twin object possono essere usati per
implementare la multiple inheritance in linguaggi
che non la supportano, ad esempio in Java

Quindi la multiple inheritance non aumenta
l’espressività del linguaggio, ma rende la
notazione più compatta e da
un’implementazione più efficiente
Schemi

Multiple Inheritance
P2
P1

Twin objects
P2
P1
C
C


C1
T1
T2
C2
C1 e C2 sono chiamati twins (gemelli) esprimendo il fatto che
sono sempre generati assieme
T1 e T2 sono dei puntatori usati per riferirsi da un twins
all’altro
Twin

Se la nostra classe C ereditasse da n classi base, ci
sarebbero n twins
P1
P2
C1
P3
C3
C2
Variabili e metodi aggiuntivi

Se dobbiamo inserire nella nostra classe variabili o
metodi aggiuntivi (non definiti nelle classi basi)


o creiamo una classe aggiuntiva C in cui li inseriamo
o li mettiamo in uno dei due twin (ad es. in C1, che chiamiamo C)
P2
P1
C
T1
T2
C2
Ereditare da una classe twin
P2
P1
C
G
T1
T2
C2
ERRATO!!
G eredita solo da C, ed è
incompatibile con C2
P2
P1
C
T1
G1
T1
T2
T2
C2
G2
Name clashes ed antenato comune

I twin object non soffrono del problema del namely
clashes


infatti se le classi base hanno campi o metodi con lo stesso
nome, essi saranno ereditati da classi diverse (C1 erediterà
i metodi di P1 e C2 i metodi di P2), quindi non si avrà un
name clash
Un discorso analogo vale quando le classi base
hanno un antenato in comune (non si ha il problema
del diamante)
Efficienza

i twin comunicano tramite composizione, quindi
perdono tempo nel passaggio di messaggi
(meno efficiente della single inheritance)

comunque la multiple inheritance è molto meno
efficiente che la single inheritance

 il costo dei twin object non è il problema
maggiore
Ottimizzare i twin objects

L’implementazione vista precedentemente
può essere ottimizzata:



Raggruppando i twins in un blocco
Mantenendo l’ordine di allocazione per avere un
offset noto a tempo di compilazione.
Memorizzando i metodi in blocchi contigui di
memoria
C1
C
C2
Eliminazione transitività virtuale e devirtualizzazione

Semplificano le gerarchie delle classi
TRANSITIVITÀ
DEVIRTUALIZZAZIONE
ESEMPIO
x
y
z
Y è duplicata:
non può essere
devirtualizzata
Y2 non è duplicata:
è derivalizzabile
la devirtualizzazione
implicherebbe due
sott’oggetti x in z, il che
viola la semantica della
virtual inheritance
Originale
Senza
transitività
Devirtualizzata
Inlining virtual bases

Invece di memorizzare un puntatore ad una virtual base
subobject, questo subobject può essere memorizzato in
un offset fisso nel memory layout della classe derivata
Ridotto il tempo di accesso di
d ad a
Eliminato il VBPTR da b ad a
ed il VPTR separato di a
Come applicare le ottimizzazioni viste

L’eliminazione della transitività deve sempre
essere applicata per prima (abilita la
devirtualizzazione ed elimina i candidati inferiori
all’inlining)

La devirtualizzazione può ridurre drasticamente
il numero di campi generati dal compilatore
Il Bidirectional Object Layout
 Schema per il layout di oggetti che produce oggetti
più piccoli e più rapida invocazione di metodi,
ottimizzando in modo automatico particolari usi della
multiple inheritance
 tipo di gerarchia comune: strato di astrazione che
separa interfaccia ed implementazione
dove Ci sono classi, Ti tipi astratti
le frecce denotano le relazioni:
- è sottotipo di (nell’es. T2 sottotipo di T1)
- implementa (nell’es. C1 implementa T1
- eredita da (nell’es. C2 eredita da C1)
Bidirectional layout di un oggetto
object
Dispatch vectors (d.v.)
Dispatch
header
Separazione tra campi ed
informazioni di dispatch
(d.h.)
fields
Class dispatch vector
Dispatch header: array di puntatori a vari dispatch vectors dei metodi
Class vector: è l’ultimo dei dispatch vectors. Contiene tutti i metodi
dell’oggetto
Fields: variabili di istanza di un oggetto.
Bidirectional layout di un oggetto
Compatibilità tra layout di
una classe e della sua
superclasse

In generale un layout (oggetto, dispatch header, dispatch
vector) è compatibile a quello della corrispondente
superclasse se quest’ultimo è incorporato nel layout della
sottoclasse
Un esempio di implementazione

Le classi CA e CB implementano
rispettivamente i tipi A e B

i layout dei due oggetti mostrano i rispettivi
dispatch headers e i dispatch vectors

Un solo dispatch vector, quello della classe

Indici degli n metodi in un d.v. 0...n-1

indici dei dispatch vector di una classe
-m...n-1
Il layout di un type header
Regola e notazioni per un
semplice type header
layout



INEFFICIENTE
un type header è compatibile col dispatch header di ciascuno dei suoi
supertipi
per ogni Ti i metodi inclusi nel dispatch vector sono quelli per cui non c’è
un puntatore nella parte relativa ai suoi supertipi T1....Ti-1
Il tipo T1 è chiamato il supertipo primario I tipi T2...Tn sono supertipi
secondari
Regole di merging per i type header
Regola 1: Se T ha un supertipo S il cui
header è della stessa dimensione ed
è presente in L sostituisco T ad S se
m (dispatch vector di T senza metodi
di S) non è in conflitto con S
Regola 2: metto S alla fine di T
Nessun conflitto con la parte w di T.

T e suoi supertipi (sottotipi di S)
devono essere su una catena di
supertipo primario

Le diramazioni nella struttura dei
supertipi di T, sono incluse nella parte
w di T
La funzione di merge applicando le 2 regole
Regola M1: un solo type header
Regola M2: come le 2 regole
precedenti, se non ci sono
diramazioni lungo il path da Tn ad S
se ci sono S dev’essere supertipo
primario di Tn
Regola M3: Se nessuna delle due si
può applicare si aggiunge Tn
all’inizio del merge precedente
Regole di merging per i class header
La classe C non eredita da una superclasse


I metodi di C privati sono aggiunti prima all’ultimo
dispatch vector di T. I metodi di C hanno indici
negativi
T ha una gerarchia di tipi singola quindi il class
header di C avrà una sola entry per oggetto
La classe C: implementa T ed eredita da Cs
 L’header di Cs deve esporre un header per S
compatibile con T
 L’header di C è formato estendendo il dispatch vector
di classe di Cs all’indietro ed inglobando l’header di S
 Entrambe le operazioni possono interessare lo
stesso dispatch vector se non compatibili con
l’estensione di S
Regole di merging per i class header
Classe C che implementa T ed eredita da Cs

L’header di C è formato concatenando
l’header di T e Cs, senza merging
Possibili varianti
 C non implementa T
la parte del layout relativa è empty

T è supertipo di Cs
viene aggiunta solo la parte dei metodi di C al
dispatch vector della classe Cs
Confronto fra layout
Concludendo

Oggi disponiamo di metodi efficienti per
implementare l’ereditarietà multipla

Nonostante ciò i linguaggi di programmazione
moderni la implementano solo a livello di interfacce

Questa scelta è dovuta ad una complessità
intrinseca della semantica della ereditarietà multipla

Del resto in alcuni casi l’utilizzo dell’ereditarietà
multipla permette una modellazione più elegante