Quali sono le sfide legate alla digitazione nella scrittura di un compilatore per un linguaggio tipizzato dinamicamente?

Hai semplificato eccessivamente la frase di Guido nel formulare la tua domanda. Il problema non è scrivere un compilatore per un linguaggio tipizzato in modo dinamico. Il problema è scrivere uno che (criterio 1) è sempre corretto, (criterio 2) mantiene la digitazione dinamica, e (criterio 3) è notevolmente più veloce per una quantità significativa di codice.

È facile implementare il 90% (criterio 1 non riuscito) di Python ed essere costantemente veloce con esso. Allo stesso modo, è facile creare una variante Python più veloce con tipizzazione statica (criterio 2 non riuscito). Anche implementare il 100% è facile (nella misura in cui implementa un linguaggio complesso che sia facile), ma finora ogni modo semplice per implementarlo risulta relativamente lento (criterio 3 in mancanza).

L'implementazione di un interprete più JIT è corretta, implementa l'intera lingua ed è più veloce perché alcuni codici risultano fattibili, anche se molto più difficili (cfr PyPy) e solo così se automatizzi il creazione del compilatore JIT (Psyco ne ha fatto a meno, ma era molto limitato sul codice che potrebbe accelerare). Notate che questo è esplicitamente fuori dall'ambito, visto che stiamo parlando di compilatori statici (anche in anticipo). Ne parlo solo per spiegare perché il suo approccio non funziona per i compilatori statici (o almeno non esiste un controesempio esistente): prima deve interpretare e osservare il programma, quindi generare codice per una specifica iterazione di un ciclo (o un altro codice lineare percorso), quindi ottimizzare l'inferno di quello basato su ipotesi valide solo per quella specifica iterazione (o almeno, non per tutte le iterazioni possibili). L'aspettativa è che molte esecuzioni successive di quel codice corrisponderanno anche alle aspettative e quindi trarranno vantaggio dalle ottimizzazioni. Alcuni controlli (relativamente economici) vengono aggiunti per assicurare la correttezza. Per fare tutto questo, hai bisogno di un'idea su cosa specializzare e di una implementazione lenta ma generale a cui ricorrere. I compilatori AOT non hanno né. Non possono specializzare affatto in base a codice che non possono vedere (ad esempio codice caricato dinamicamente), e specializzarsi incautamente significa generare più codice, che ha un numero di problemi (utilizzo di icache, dimensione binaria, compilare tempo, rami aggiuntivi).

L'implementazione di un compilatore AOT che correttamente implementa la intera lingua è anche relativamente semplice: genera codice che richiama nel runtime per fare ciò che l'interprete dovrebbe fare quando viene alimentato con questo codice. Nuitka (principalmente) fa questo. Tuttavia, questo non offre molti vantaggi in termini di prestazioni (criterio 3 non soddisfacente), poiché devi ancora svolgere il lavoro inutile quanto un interprete, salvo per inviare il bytecode al blocco del codice C che esegue ciò che hai compilato. Ma si tratta solo di un costo piuttosto piccolo, abbastanza significativo da meritare l'ottimizzazione in un interprete esistente, ma non abbastanza significativo da giustificare una nuova implementazione con i propri problemi.

Cosa sarebbe necessario per soddisfare tutti e tre i criteri? Non ne abbiamo idea. Ci sono alcuni schemi di analisi statica che possono estrarre alcune informazioni su tipi concreti, controllo del flusso, ecc. Da programmi Python. Quelli che producono dati accurati oltre lo scopo di un singolo blocco di base sono estremamente lenti e hanno bisogno di vedere l'intero programma, o almeno la maggior parte di esso. Tuttavia, non puoi fare molto con quelle informazioni, a parte forse ottimizzare alcune operazioni sui tipi predefiniti.

Perché? Per dirla senza mezzi termini, un compilatore rimuove la possibilità di eseguire il codice Python caricato in fase di runtime (criterio 1 non riuscito), o non fornisce alcuna ipotesi che possa essere invalidata da alcun codice Python. Sfortunatamente, questo include praticamente tutto ciò che è utile per ottimizzare i programmi: le funzioni globali possono essere rimbalzate, le classi possono essere mutate o sostituite interamente, i moduli possono essere modificati arbitrariamente, l'importazione può essere dirottata in diversi modi, ecc. Una singola stringa passata a eval , exec , __import__ , o numerose altre funzioni, possono fare qualsiasi di queste cose. In effetti, ciò significa che non è possibile applicare grandi ottimizzazioni, con un piccolo vantaggio in termini di prestazioni (criteri 3 non soddisfacenti). Torna al paragrafo precedente.

Il problema più difficile è capire che tipo ha tutto in un dato momento.

In un linguaggio statico come C o Java, una volta che hai visto la dichiarazione del tipo, sai cos'è quell'oggetto e cosa può fare. Se una variabile è dichiarata int , è un numero intero. Ad esempio, non è un riferimento a una funzione richiamabile.

In Python, può essere. Questo è orribile Python, ma legale:

i = 2
x = 3 + i

def prn(s):
    print(s)

i = prn
i(x)

Ora, questo esempio è piuttosto stupido, ma illustra l'idea generale.

Più realisticamente, potresti sostituire una funzione built-in con una funzione definita dall'utente che fa qualcosa di leggermente diverso (come una versione che registra i suoi argomenti quando la chiami).

PyPy usa la compilazione Just-In-Time dopo aver visto cosa fa realmente il codice, e questo fa sì che PyPy acceleri molto. PyPy può guardare un loop e verificare che ogni volta che viene eseguito il ciclo, la variabile foo sia sempre un numero intero; quindi PyPy può ottimizzare il codice che cerca il tipo di foo su ogni passaggio del ciclo e spesso può anche sbarazzarsi dell'oggetto Python che rappresenta un intero e foo può semplicemente diventare un numero seduto in un registrati sulla CPU. Ecco come PyPy può essere più veloce di CPython; CPython ricerca il tipo il più velocemente possibile, ma nemmeno la ricerca è ancora più veloce.

Non conosco i dettagli, ma ricordo che c'era un progetto chiamato Unladen Swallow che stava cercando di applicare la tecnologia del compilatore statico per accelerare Python (usando LLVM). Puoi cercare su Google Unladen Swallow e vedere se riesci a trovare una discussione sul motivo per cui non ha funzionato come speravano.

Come dice l'altra risposta, il problema chiave è capire le informazioni sul tipo. Nella misura in cui puoi farlo staticamente, puoi generare direttamente un buon codice.

Ma anche se non è possibile farlo staticamente, è comunque possibile generare codice ragionevole, solo in fase di esecuzione, quando si ricevono informazioni di tipo effettivo . Questa informazione risulta essere spesso stabile o avere al massimo alcuni valori diversi per una particolare entità in un particolare punto di codice. Il linguaggio di programmazione SELF ha aperto la strada a molte delle idee di raccolta di tipo runtime aggressivo e generazione di codice runtime. Le sue idee sono ampiamente utilizzate nei moderni compilatori basati su JIT come Java e C #.