104
Appendice E : Concetti base per W
1. Tipi
I tipi possono essere variabili, costanti, funzioni. In Sigma_X questo sistema è stato esteso con tipi oggetto e tipi metodo senza intaccare l’essenza dell’algoritmo.
2. Schemi di tipo
Uno schema di tipo è un tipo in cui occorrono un certo numero di variabili (di tipo). Sebbene le variabili abbiano un certo ordine nello schema dato, questo non è influente ai fini del funzionamento di W.
3. Free Type Variables
Non è altro che l’insieme di tutte le variabili di tipo contenute in un tipo . Queste variabili sono di fatto quantificate essenzialmente e devono essere legate a termini
quando l’algoritmo termina.
4. Sostituzioni
Una sostituzione, molto in breve (da non prendere come definizione esaustiva), è un mapping da variabili di tipo a tipi. Quando una sostituzione è applicata, le variabili di tipo che non sono nel suo dominio devono rimanere invariate. Conseguentemente la
sostituzione vuota si comporta come la funzione identità. Come le sostituzioni
105 5. Ambiente
Un ambiente, in genere denotato con , mappa le variabili libere sui loro corrispondenti schemi di tipo, e fornisce un contesto in cui la type inference può avere luogo.
6. Istanza
Un tipo si dice essere una istanza di uno schema di tipo t se esiste un sostituzione S tale che e S(t) sono sintatticamente uguali.
7. Most general unifier
Dati due tipi e , si indica con mgu( ) il più generico degli unificatori (most general unifier), che altro non è se non una sostituzione.
