Polimorfismo

Introduzione

Monoforfo

Quando non posso utilizzare un tipo come parametro. Ossia non possiamo definire una funzione generica.

Polimorfismo

Polimorfismo, come dice il nome, significa avere tante forme, in questo caso tanti tipi. Ma avere tanti tipi non è una cosa ambigua? Questa cosa si risolve solitamente a compile time (facendo checks di sottotipo, oppure dispatch della funzione corretta).

A program part is polymorphic if it can be used for objects of several classes

Tipologie di Polimorfismo (3)

• ad-hoc polymorphism questo è anche chiamato overloading in cui vado a definire un nuova funzione (con lo stesso nome) che accetti il nuovo tipo di dato.
• subtype polymorphism
• parametric polymorphism

Ad-hoc (3)

Questo è molto simile al tipo somma, solamente fatto da un punto di vista funzionale (i domini devono essere separati).

In C sono molto conosciute questa tipologia di polimorfismo. Però ci sono anche forme comuni, come l’operatori aritmetici.

L’invocazione è anche chiamato dispatch , quando abbiamo risolto l’overloading, ossia abbiamo fatto il dispatch dell’invocazione, allora l’overloading scompare e viene eseguita una specifica funzione. Questa funzione può essere fatta in modo statico oppure dinamico.

Riassumendo:

• Definisco stesso nome che prendono tipi diversi
• Avviene un dispatch statico o dinamico
• Una volta avvenuto il dispatch, la funzione eseguita è univocamente identificata.

Statico o dinamico nel dispatch

Dispatch è il processo che va a decidere la funzione overloadata da chiamare, questo processo si può classificare come dinamico se avviene durante il runtime (come solitamente è per le interfacce) oppure statico quando avviene e a tempo di compilazione (come solitamente avviene per le funzioni overloaddate).

Di sottotipo

Possiamo andare a dire che un tipo S è sottotipo di un tipo T, indicato con $S <: T$, quando S può essere utilizzato in qualunque occasione al posto di T. Questo è anche chiamato come principio di sostituzione di Liskov, vedi Classi OOP

SetTheory per sottotipi

• Slide polimorfismo di sottotipo

  

Questo concetto l’abbiamo anche accennato in Algebra dei tipi quando abbiamo parlato di coercizione.

praticamente quando abbiamo un tipo più specifico $S$ che andiamo ad indicare con $S <: T$, allora quando ho S e devo utilizzare T, lo posso fare, questo perché S contiene tutte le caratteristiche di T.

Solitamente questa è una relazione di preordine ossia riflessiva e transitiva, spesso anche antisimmetrica, quindi è spesso un ordine parziale.

Si può dire che esiste un rapporto di specificazione (parola da utilizzare nell’orale per bella figura lel) perché S è più specifico di T, in questo senso possiamo utilizzare S in ogni posto in cui c’è T.

Tipologie di sottotipaggio (2)

Per questa parte possiamo andare a definire un concetto di sottotipaggio per profondità o per larghezza.

Per larghezza: basta che il sottotipo abbia molti più campi! in questo senso Dog < Animal, perché anche dog posso utilizzarlo come un animal, dato che ha tutte le cose di animal. (l’unica differenza col duck typing è il fatto che T qui è esplicito, mentre nel duck typing non mi importa del tipo, solamente dello stesso utilizzo).

• Differenza fra duck e width subtyping per chatGPT

  Width subtyping is a form of subtype polymorphism where a type is considered a subtype of another type if it has at least the same properties and methods as the supertype. This means that a subtype can have more properties and methods than the supertype, but it must at least have all of the ones that are defined in the supertype. This is called “width” because it is based on the width of the type’s interface.

  Duck typing, on the other hand, is a more dynamic approach to type checking where the type of an object is determined by its behavior at runtime rather than its static type. In other words, if it walks like a duck and quacks like a duck, then it must be a duck. This means that two objects with different types can still be treated as if they have the same type if they share the same behavior.

  In summary, width subtyping is based on the interface of a type and allows for subtype polymorphism, while duck typing is based on the behavior of an object at runtime and allows for more dynamic type checking.

Per profondità: Quando un campo ha un tipo che sia un sottotipo di un altro. Questo è visto molte meno volte, però si può fare. Questa ha però delle particolarità, è importante introdurre il concetto di covariante per tipi quando le parti del record mantengono la stessa direzione di sottotipaggio. Quando abbiamo due tipi che sono covarianti, possiamo utilizzarli solo per le letture. In scrittura però potremmo avere dei campi non inizializzati, quindi non va molto bene. (nell’esempio avremmo un animale in output in scrittura, mentre gli abbiamo dato un dog e ci aspettavamo un dog in output). (queste nozioni di covarianza comunque sono sempre in funzione del contesto).

In pratica vado a rimpiazzare i campi del record con dei sottotipi, questo è buono per cose immutabili, for example, you can assign 1.5 to the ‘x’ field of a real point (a record with two real fields), but you can’t do the same to the ‘x’ field of an integer point (which, however, is a deep subtype of the real point type) because 1.5 is not an integer.

Covariante e Controvariante e consumo (!!)

Abbiamo trattato più recentemente di queste regole in Typing and Subtyping. È stato spiegato meglio.

• Slide covariante, controvariante e consumi e produzione

  

• Esempio strano

  

Questa nozione si basa sull’inversione fra produzione e consumazione.

Avevamo detto che abbiamo una relazione di sottotipo, perché DogHouse < AnimalHouse quindi sono covarianti rispetto a Dog < Animal House. Ma nella fase di consumo, questo si inverte, quindi si può dire che siano controvarianti.

In breve:

1. Consumo (input) → Controvariante
2. Produzione (output) → Covariante

Il motivo per cui succede è che Dog fn utilizza i campi di Dog, che sono più estesi, posso sostituire a questo consumo anche animal, che utilizza i campi di animal, quindi sono anche presenti in Dog, ecco che il rapporto si inverte

Possiamo fare un parallelo fra le funzioni di consumo e quelle di produzione.

Sussunzione

Con sussunzione andiamo a parlare di quando possiamo fare l’inferenza di sottotipaggio ossia se è vero o meno che un tipo è sottotipo di un altro (e quindi possibile utilizzare S al posto di T in qualunque luogo).

Possiamo fare la sussunzione in modo estensionale o intensionale quindi o:

1. Caratterizzando tutti gli elementi del sottotipo
2. Parlare di predicati e domini.

Teoria dei Tipi#Tipo estensionali o intensionali abbiamo parlato di estensionale o intensionale.

• Esempi di sussunzione

  

Polimorfismo parametrico

Il problema che il polimorfismo parametrico risolve rispetto a quello di sottotipo è il fatto che per ritrovare l’informazione iniziale, c’è bisogno di castin. Con il polimorfismo parametrico non avremo più bisogno di questo.

Tipi parametrici

Quando abbiamo delle operazioni anche se non conosciamo esattamente cosa c’è sotto, però riguardo la struttura so bene cosa vanno a fare. (un esempio riguardo a questo è il sort).

Questa parametrizzazione ci permette di definire delle cose per tutti i tipi che possiedono quella funzione (ricorda i tratti di rust), ed è per questo che possiamo dire che sia un tipo universale. Questa cosa che vale per tutti ci permette di poter provare dei teoremi a gratis.

Upper Bounds

We can infer which methods are available by setting the upper bounds (methods that are present) with respect to a generic type.

For example, if a class extends from

interface Comparable<T> {int compareTo( T o );}

Then we know that at least the method compareTo is implemented within this function. If not we cannot assume anything for the model.

Subtyping with Generics

• Generic types aresubtypes of theirdeclared supertypes
• Type variables aresubtypes of their upperbounds

But different instantiations are unrelated directly. They cannot neither be covariant parameter types, neither contravariant. Make sure you know some examples where this is valid.

• Covariance is unsafe when a generic type argument is used for variables that are written by clients- Mutable fields- Method arguments
• Contravariance isunsafe when a generictype argument is usedfor variables that areread by clients- Fields- Method results

The standard solution in Java is non-variancy, which means the types are neither covariant or contravariant, they just are not compatible with each other. Sometimes this is over restrictive though. Covariant generics would need lots of runtime checks for every field update and argument passing, which is a lot.

Covariance and Contravariance Annotations

We can make generics support covariance or contravariance if that generic only uses the type parameter in covariant or contravariant settings. Scalla allows for these kinds of settings:

class Random[ +T ] { // +T indicates covariance
  def next: T = { ... }
}

// ----------------------------------------------------
// Subtyping Check: Covariance allows Random[String] to be treated as Random[AnyRef]
// (i.e., Random[String] <: Random[AnyRef])
val r: Random[ AnyRef ] = new Random<a href="/notes"> String </a> // Good. Covariance allows this assignment because String <: AnyRef.

// Usage Check: 'a' will be inferred as AnyRef because 'r's static type is Random[AnyRef]
val a = r.next // Good. 'r.next' returns a T, which resolves to AnyRef here.
// ----------------------------------------------------

class Random[ +T ] { // +T indicates covariance
  def next: T = { ... }
  // Error! A covariant type parameter [+T] cannot appear in a contravariant position,
  // such as a method argument position (input).
  def initialize( i: T ) = { ... } // Scalac: Error. Covariant type T appears in contravariant position. Doesn't even compile.
}

We can do a similar thing for contravariant generics.

Using Parametric Polimorphism

Adding Type Parameters

class Person { ... }
class Student extends Person { ... }
class PersonComp implements Comparator<Person> {int compare( Person fst, Person snd ) { ... }}
interface Comparator<T> {int compare( T fst, T snd );}
class TreeSet<F, E extends F> {TreeSet( Comparator<F> c ) { ... }... }
TreeSet<Person, Student> s =new TreeSet<Person, Student>( new PersonComp() );

We could not use personcomp without defining the F, because student does not implement that comparator, even if students are persons. The above is too low level to be useful.

The main drawbacks are:

• The client needs to understand exactly what needs to go there. We need to understand how to use those.
• Type instantiation: after a type has been instantiated we cannot change it anymore, so it has some bad dynamicism.

Allowing different comparisons

class PersonComp<T extends Person> implements Comparator<T> {int compare( T fst, T snd ) { ... }}
TreeSet<Student> s =new TreeSet<Student>( new PersonComp<Student>() );

We can also define it in the above manner, and instantiate the correct comparisor. But:

1. The client still needs to understand how personComp works
2. We need to have foresight to understand the cases we need to run that simple little thing.

Using Existential Types

We now have a

• “There exists a type argument T such that c has typeCollection T", and this is instantiated automatically by the type system.

You can use it like this:

static void printAll( Collection<?> c ) {for ( Object e : c ) { System.out.println( e ); }}
Collection<String> c = new ArrayList<String>( );
...
printAll( c );

After that we can bound the wildcard types correctly when needed.

static void printFormatted(Collection<? extends Format> c) {
    for (Format e : c) {
        String s = e.format(80);
        System.out.println(s);
    }
}

We basically can set up sub or super typing relations between the bounds using the existential quantifier in java!

The existence of this flexible type system allows now to define the tree comparator as:

class TreeSet<E> {TreeSet( Comparator<? super E> c ) { ... }... }

Which is really nice and concise.

Type Erasure

For backwards compatibility all this generics system (which was introduced in Java 5) all the type generics annotation is erased at the bytecode level.

Yet this is not the same for C#, which has this information!

C++ Landscape

Templating in C++

There are two main differences compared to Java code:

• Here we do not check return types
• And we do not check availability of methods, until they are instantiated.

Concepts

template<class T>
concept Comparable = requires( T a, T b ) {
    { a.compareTo( b ) } -> std::same_as<bool>;
};

template<class T>
requires Comparable<T>
class Queue {
    T elem;
    Queue<T>* next;
    // ... other members and methods
};

We can check if bounds are satisfied in this manner, statically.

Template Metaprogramming

template<int n>
class Fact {
public:
    static const int val = Fact<n-1>::val * n;
};

template<>
class Fact<0> {
public:
    static const int val = 1;
};

The compiler generates the instantiations and effectively computes the values!

Comparisons with Parametric Polimorphism

Ibridazione con polimorfismo di sottotipo

A volte non vogliamo che la nostra funzione vada per tutti, senza quindi conoscere come è fatto sotto, vorremmo avere certe funzioni (quindi un sottotipo del tipo generale), per esempio nei tratti di rust possiamo dire che questa nostra funzione vada per tutte in cui è definita una certa funzione/interfaccia/tratto, in questo senso andiamo ad utilizzare un sottotipo

Array c’erano già all’inizio, lo puoi utilizzare covariante in entrambe le direzioni, mentre altrimenti non ti permetterebbe di utilizzare in entrambe le direzioni (vuole che tu sia prima sicuro se vuoi utilizzarlo come consumer o producer. un buon modo per ricordarsi è PECS producer deve estender, mentre consumer deve fare super.

Abbiamo sempre che è safe, nel senso che ritorna sempre un tipo senza bloccarsi (e posso sapere a tempo di compilazione cosa vada a ritornare).

Esempi di utilizzo di polimorfismo parametrico e di sottotipo

Tipi maybe e result

Questi sono alcuni tipi ispirati alle monadi, solamente capire in che formato sono:

• Maybe: Some qualcosa> + None
• Result: come le promises di js, possiamo esprimere i risultati di errore e nel caso sia andato tutto bene.