Inferenza di tipo globale nel compilatore Schema Stalin

Question

Sto esaminando il compilatore Scheme Stalin. È grande e complesso. Inoltre, se ho capito bene, l'autore stava pianificando di scrivere una serie di articoli che descrivono in dettaglio gli aspetti dell'implementazione, ma non sono mai riusciti a farlo.

L'aspetto di Stalin che mi interessa è l'inferenza di tipo globale: dedurre i tipi di cose in base al loro utilizzo in altri punti del programma. Stalin lo fa davvero? Se sì, come, e dove nella sua base di codice? Usa una variante/estensione di un algoritmo Hindley-Milner?

Answer 1

Dal README:

Stalin fa analisi di tipo statico globale utilizzando un sistema di tipo morbido che supporta i tipi di unione ricorsivi. Stalin può determinare un tipo monomorfico stretto o addirittura per ogni espressione del codice sorgente in programmi Schema arbitrario senza dichiarazioni di tipo. Ciò consente a Stalin di ridurre, oppure spesso eliminare, il controllo e l'invio dei tipi di runtime. Stalin anche esegue la selezione della rappresentazione di basso livello in base all'espressione. Ciò consente l'utilizzo di rappresentazioni dei dati della macchina base unboxed per tutti i tipi monomorfici con conseguente codice numerico numerico ad alte prestazioni.

Da un 1997 talk by Siskind:

Stalin esegue l'inferenza di tipo utilizzando l'analisi a base di set (SBA aka 0CFA). Questa analisi è aumentata per supportare la suddivisione della procedura polyvariant . I risultati di SBA vengono utilizzati per ridurre il tipo di esecuzione di controllo e dispacciamento. I risultati di SBA vengono anche utilizzati per eseguire la selezione di rappresentazione a basso livello in base all'espressione. Questo ha due vantaggi. Innanzitutto, i tag di tipo possono essere eliminati per i monotipi, consentendo l'utilizzo di rappresentazioni della macchina di base per i dati primari . In secondo luogo, la boxe può essere eliminata, alleggerendo i costi di indiretta, allocazione e recupero associati al boxing . L'eliminazione della boxe richiede che l'organizzazione di runtime consenta a variabili, parametri, slot di struttura e slot vettoriali di avere larghezza diverse a seconda del tipo di dati che sono in attesa di . Inoltre, le strutture definite dall'utente possono essere disattivate solo se le strutture sono immutabili. SBA viene esteso per determinare i dati di larghezza e mutabilità in fase di compilazione.

l'algoritmo attuale inferenza di tipo sembra essere attuate per lo più nel file di origine source/stalin3b.sc.

Sembra che SBA/0CFA sia un algoritmo completamente separato da Hindley-Milner. Tuttavia, Hindley-Milner può anche essere utilizzato per implementare la digitazione soft.

Ecco un più bello description of the 0CFA algorithm.

documenti rilevanti sono il controllo del flusso di 1.991 tesi di dottorato Olin Shivers' Analisi di ordine superiore Lingue o bisbetica Lambda e Flanagan & carta 1.995 Set-Based Analysis di Felleisen per schema completo e il suo uso in Soft- Digitando.