Regole generali per scrivere un compilatore X su Z in Y

q1. pypy is the interpreter, a RPython program which can interpret Python code, there is no output language, so we can't consider it as a compiler, right?

PyPy è simile a CPython, entrambi hanno un interprete + compilatore. CPython ha un compilatore scritto in C che compila Python in Python VM bytecode quindi esegue il bytecode in un interprete scritto in C. PyPy ha un compilatore scritto in RPython che compila Python in Python VM bytecode, quindi lo esegue in PyPy Interpreter scritto in RPython.

q2. Can compiler py2rpy exist, transforming all Python programs to RPython? In which language it's written is irrelevant. If yes, we get another compiler py2c. What's the difference between pypy and py2rpy in nature? Is py2rpy much harder to write than pypy?

Esiste un compilatore py2rpy? Teoricamente sì. Completezza di Turing ti garantisce così.

Un metodo per costruire py2rpy consiste semplicemente nel includere il codice sorgente di un interprete Python scritto in RPython nel codice sorgente generato. Un esempio del compilatore py2rpy, scritto in Bash:

// suppose that /pypy/source/ contains the source code for pypy (i.e. Python -> Nothing RPython)
cp /pypy/source/ /tmp/py2rpy/pypy/

// suppose $inputfile contains an arbitrary Python source code
cp $inputfile /tmp/py2rpy/prog.py

// generate the main.rpy
echo "import pypy; pypy.execfile('prog.py')" > /tmp/py2rpy/main.rpy

cp /tmp/py2rpy/ $outputdir

ora ogni volta che devi tradurre un codice Python in codice RPython, chiami questo script, che produce - nel $ outputdir - un% in% di RPython, il codice sorgente di Python Interpreter di RPython e un prog di blob binario. py. E poi puoi eseguire lo script RPython generato chiamando main.rpy .

(nota: dato che non ho familiarità con il progetto rpython, la sintassi per chiamare l'interprete rpython, la capacità di importare pypy e fare pypy.execfile, e l'estensione .rpy è puramente inventata, ma penso che tu possa ottenere il punto)

q3. Is there some general rules or theory available about this?

Sì, qualsiasi lingua di Turing Complete può teoricamente essere tradotta in qualsiasi lingua di Turing Complete. Alcune lingue possono essere molto più difficili da tradurre rispetto ad altre lingue, ma se la domanda è "è possibile?", La risposta è "sì"

q4. ...

Non ci sono domande qui.

Per rispondere solo a q2, c'è un libro compilatore di William McKeeman in cui la teoria dei compilatori per il linguaggio X scritto nel linguaggio Y che produce il linguaggio di uscita Z viene esplorata tramite un sistema di diagrammi a T. Pubblicato negli anni '70, titolo da non consegnare, scusa.

q1. Generalmente, un interprete non è un compilatore. La differenza fondamentale tra un compilatore e un interprete è che un interprete si avvia sempre, con il codice sorgente nella lingua di partenza, ogni volta. Se il tuo pypy era invece pyAST, o pyP-code, e poi avevi un interprete AST o P-code, allora potevi chiamare pyAST un compilatore. Questo è il modo in cui ha funzionato il vecchio compilatore PASCAL di UCSD (e anche molti altri): sono stati compilati con un codice P, che è stato interpretato durante l'esecuzione del programma. (Anche .NET fornisce qualcosa di simile a questo, quando la compattezza del codice oggetto generato è molto più importante della velocità.)

q2. Sì, naturalmente. Vedi UCSD PASCAL (e molti altri).

q3. Scava tra i testi classici in informatica. Leggi su Concurrent PASCAL, di Per Brinch-Hansen (se la memoria mi serve). Molto è stato scritto sui compilatori e sulla generazione di codice. Generare uno pseudocodice indipendente dalla macchina è di solito molto più semplice rispetto alla generazione del codice macchina: lo pseudocodice di solito è privo di stranezze che le macchine reali invariabilmente contengono.

q4. Se vuoi che il tuo oggetto generato funzioni più velocemente, rendi il compilatore più intelligente, per fare una migliore ottimizzazione. Se il tuo oggetto è interpretato, consideri di spingere le operazioni più complesse in pseudoinstruzioni primitive (CISC vs. RISC è l'analogia), quindi fai del tuo meglio per ottimizzare il frack dal tuo interprete.

Se vuoi che il tuo compilatore funzioni più velocemente, devi guardare TUTTO quello che fa, incluso ripensare il tuo codice sorgente. Dopo aver caricato il compilatore stesso, la parte più lunga della compilazione è SEMPRE che legge il codice sorgente nel compilatore. (Si consideri il C ++ per esempio .Tutte le altre cose sono relativamente uguali, un compilatore che deve abbattere 9.000 (o forse 50.000) righe di # include file per compilare un semplice programma "Hello, World" non sarà mai veloce come uno basta leggere quattro o cinque righe.)

Non ricordo dove l'ho letto, ma il compilatore originale di Oberon all'ETH di Zurigo aveva un meccanismo di tavolo simbolico molto sofisticato, abbastanza elegante. Il benchmark di Wirth per le prestazioni del compilatore era il tempo necessario per compilare il compilatore. Una mattina, entrò, tirò fuori lo splendido tavolo simbolico a più alberi con collegamenti multipli e lo sostituì con un semplice array lineare e ricerche lineari e lineari. Gli studenti laureati nel suo gruppo erano SHOCKED. Dopo il cambiamento, il compilatore era più veloce, perché i moduli che stava compilando erano sempre abbastanza piccoli che l'elegante mostro imponeva un overhead totale maggiore rispetto all'array lineare e alla ricerca lineare.

Le tue domande come riportate mi portano a credere che ciò di cui hai veramente bisogno / bisogno sia una spiegazione di cosa sia un compilatore, di cosa sia un interprete e le differenze tra i due.

Un compilatore mappa un programma scritto nel linguaggio X in un programma funzionalmente equivalente scritto nel linguaggio Y. Come esempio, un compilatore da Pascal a C potrebbe essere compilato

function Square(i: Integer)
begin
    Square := i * i
end

a

int Square(int i)
{
    return i * i;
}

La maggior parte dei compilatori compilano "verso il basso", quindi compilano linguaggi di programmazione di livello superiore in linguaggi di livello inferiore, l'ultimo linguaggio di livello inferiore essendo il codice macchina.

La maggior parte dei compilatori compilano direttamente il codice macchina, ma alcuni (in particolare i linguaggi Java e .NET) vengono compilati in "bytecode" ( codice bytecode Java e CIL ). Pensa al codice byte come codice macchina per un ipotetico computer. Questo bytecode viene quindi interpretato o JITted quando viene eseguito (ne parleremo più avanti).

Un interprete esegue un programma scritto in una lingua Z. Un interprete legge un programma bit per bit, eseguendolo mentre procede. Ad esempio:

int i = 0;
while (i < 1)
{
    i++
}
return i;

Immagina l'interprete che guarda la riga del programma per la linea, esamina la linea, esegue ciò che fa, guarda la riga successiva e così via.

Il miglior esempio di un interprete è la CPU del tuo computer. Interpreta il codice macchina e lo esegue. Il modo in cui la CPU funziona è specificato da come è stato costruito fisicamente. Come funziona un programma interprete è specificato da come appare il suo codice. La CPU quindi interpreta ed esegue il programma interprete, che a sua volta interpreta ed esegue il suo input. Puoi collegare gli interpreti in questo modo.

Un JITter è un compilatore Just-In-Time. Un JITter è un compilatore. L'unica differenza è il tempo in cui viene eseguita: la maggior parte dei programmi viene scritta, compilata, spedita agli utenti e quindi eseguita, ma il bytecode e il CIL Java vengono prima inviati ai propri utenti, quindi poco prima che vengano eseguiti vengono compilati sulla macchina codice dei loro utenti.

C # - > (compile) - > CIL - > spedito al cliente - > (compila poco prima dell'esecuzione) - > codice macchina - > (Esecuzione)

L'ultima cosa che vorresti sapere è Completezza Turing ( link ) . Un linguaggio di programmazione è Turing Completo se può calcolare tutto ciò che una macchina di Turing 'può, cioè è almeno come' potente 'come una macchina di Turing. La tesi di Church-Turing afferma che una macchina di Turing è potente almeno quanto qualsiasi altra macchina che possiamo mai costruito. Ne consegue che ogni lingua completa di Turing è altrettanto potente della macchina di Turing, e quindi tutte le lingue complete di Turing sono ugualmente potenti.

In altre parole, finché il tuo linguaggio di programmazione è completo di Turing (quasi tutti lo sono), non importa quale lingua scegli, poiché tutti possono calcolare le stesse cose. Ciò significa anche che non è molto rilevante quale linguaggio di programmazione scegli per scrivere il tuo compilatore o il tuo interprete. Ultimo ma non meno importante, significa che puoi sempre scrivere un compilatore dalla lingua da X a Y se X e Y sono entrambi completi di Turing.

Nota che essere Turing completo non dice nulla sul fatto che la tua lingua sia efficiente, né su tutti i dettagli di implementazione della tua CPU e altro hardware, o sulla qualità del compilatore che usi per la lingua. Inoltre, il tuo sistema operativo potrebbe decidere che il tuo programma non ha i diritti per aprire un file, ma ciò non impedisce la tua capacità di calcolare qualsiasi cosa - non ho deliberatamente definito il calcolo, poiché ciò richiederebbe un altro muro di testo.