Come vengono implementati i generici in un moderno compilatore?

How are generics implemented in a modern compiler?

Ti invito a leggere il codice sorgente di un compilatore moderno se desideri sapere come funziona un compilatore moderno. Vorrei iniziare con il progetto Roslyn, che implementa i compilatori C # e Visual Basic.

In particolare attiro la tua attenzione sul codice nel compilatore C # che implementa i simboli di tipo:

link

e potresti anche voler guardare il codice per le regole di convertibilità. C'è molto di ciò che riguarda la manipolazione algebrica dei tipi generici.

link

Ho provato a rendere più facile la lettura di quest'ultimo.

I've thought of a few ways to achieve this, we store the generic function in an AST as Function_Node and then each time we use it we store in the original function node a copy of itself with all of the types T substituted with the types that are being used.

Stai descrivendo modelli , non generici . C # e Visual Basic hanno generici reali nei loro sistemi di tipi.

In breve, funzionano così.

• Iniziamo stabilendo regole per ciò che costituisce formalmente un tipo in fase di compilazione. Ad esempio: int è un tipo, un parametro di tipo T è un tipo, per qualsiasi tipo X , il tipo di matrice X[] è anche un tipo e così via.

• Le regole per i generici implicano la sostituzione. Ad esempio, class C with one type parameter non è un tipo. È un modello per fare tipi. class C with one type parameter called T, under substitution with int for T è un tipo.

• Le regole che descrivono le relazioni tra tipi - la compatibilità al momento dell'assegnazione, come determinare il tipo di un'espressione e così via - sono progettate e implementate nel compilatore.

• Un linguaggio bytecode che supporta tipi generici nel suo sistema di metadati è progettato e implementato.

• In fase di esecuzione il compilatore JIT trasforma il bytecode in codice macchina; è responsabile della costruzione del codice macchina appropriato in base a una specializzazione generica.

Quindi, ad esempio, in C # quando dici

class C<T> { public void X(T t) { Console.WriteLine(t); } }
...
var c = new C<int>(); 
c.X(123);

quindi il compilatore verifica che in C<int> , l'argomento int è una sostituzione valida per T e genera di conseguenza metadati e bytecode. In fase di esecuzione, il jitter rileva che viene creata una C<int> per la prima volta e genera dinamicamente il codice macchina appropriato.

La maggior parte delle implementazioni di generici (o meglio: polimorfismo parametrico) usano la cancellazione di tipo. Questo semplifica enormemente il problema della compilazione del codice generico, ma funziona solo per i tipi di box: poiché ogni argomento è effettivamente un puntatore opaco, abbiamo bisogno di un meccanismo di distribuzione VTable o simile per eseguire operazioni sugli argomenti. In Java:

<T extends Addable> T add(T a, T b) { … }

può essere compilato, controllato dal tipo e chiamato allo stesso modo di

Addable add(Addable a, Addable b) { … }

tranne che i generici forniscono al correttore di tipi molte più informazioni sul sito di chiamata. Questa informazione extra può essere gestita con type variables , specialmente quando vengono inferti tipi generici. Durante il controllo del tipo, ogni tipo generico può essere sostituito con una variabile, chiamiamola $T1 :

$T1 add($T1 a, $T1 b)

La variabile type viene quindi aggiornata con altri fatti man mano che diventano noti, finché non può essere sostituita con un tipo concreto. L'algoritmo di controllo del tipo deve essere scritto in modo tale che possa contenere queste variabili di tipo anche se non sono ancora state risolte in un tipo completo. In Java, di solito, questo può essere fatto facilmente poiché il tipo di argomenti è spesso noto prima che il tipo di chiamata alla funzione debba essere conosciuto. Un'eccezione degna di nota è un'espressione lambda come argomento di funzione, che richiede l'uso di tali variabili di tipo.

Molto più tardi, un ottimizzatore può generare codice specializzato per un determinato insieme di argomenti, questo sarebbe quindi effettivamente un tipo di inlining.

Un VTable per argomenti generici tipizzati può essere evitato se la funzione generica non esegue alcuna operazione sul tipo, ma li passa solo a un'altra funzione. Per esempio. la funzione Haskell call :: (a -> b) -> a -> b; call f x = f x non dovrebbe inserire l'argomento x . Tuttavia, questo richiede una convenzione di chiamata che può passare attraverso i valori senza conoscere la loro dimensione, che in sostanza lo limita comunque ai puntatori.

C ++ è molto diverso dalla maggior parte delle lingue in questo senso. Una classe o una funzione basata su modelli (parlerò solo di funzioni basate su modelli qui) non è richiamabile in sé. Invece, i modelli dovrebbero essere intesi come una meta-funzione in fase di compilazione che restituisce una funzione reale. Ignorando per un momento l'inferenza degli argomenti del modello, l'approccio generale si riduce a questi passaggi:

1. Applica il modello agli argomenti del modello forniti. E.g chiamando template<class T> T add(T a, T b) { … } come add<int>(1, 2) ci darebbe la funzione effettiva int __add__T_int(int a, int b) (o qualunque sia l'approccio di mangling del nome).

2. Se il codice per quella funzione è già stato generato nell'unità di compilazione corrente, continua. Altrimenti, genera il codice come se una funzione int __add__T_int(int a, int b) { … } fosse stata scritta nel codice sorgente. Ciò comporta la sostituzione di tutte le occorrenze dell'argomento modello con i relativi valori. Questa è probabilmente una trasformazione AST → AST. Quindi, esegui il controllo del tipo sull'AST generato.

3. Compila la chiamata come se il codice sorgente fosse stato __add__T_int(1, 2) .

Si noti che i modelli C ++ hanno un'interazione complessa con il meccanismo di risoluzione del sovraccarico, che non voglio descrivere qui. Nota anche che questa generazione di codice rende impossibile avere un metodo basato su modelli che sia anche virtuale - un approccio basato sulla cancellazione del tipo non soffre di questa restrizione sostanziale.

Che cosa significa questo per il tuo compilatore e / o lingua? Devi pensare attentamente al tipo di farmaci generici che vuoi offrire. Digitare la cancellazione in assenza di inferenza di tipo è l'approccio più semplice possibile se si supportano i tipi di box. La specializzazione dei modelli è abbastanza semplice, ma di solito implica il manomissione dei nomi e (per unità di compilazione multiple) una sostanziale duplicazione nell'output, poiché i modelli vengono istanziati nel sito di chiamata, non nel sito di definizione.

L'approccio che hai mostrato è essenzialmente un approccio al modello simile al C ++. Tuttavia, i modelli specializzati / istanziati vengono memorizzati come "versioni" del modello principale. Questo è fuorviante: non sono la stessa cosa concettualmente, e le diverse istanze di una funzione possono avere tipi molto diversi. Ciò complicherà le cose a lungo termine se si consente anche il sovraccarico della funzione. Invece, avresti bisogno di una nozione di un set di overload che contenga tutte le possibili funzioni e modelli che condividono un nome. Tranne che per risolvere il sovraccarico, puoi considerare diversi modelli istanziati completamente separati l'uno dall'altro.