Made in Heaven

Da un po' di tempo mi interesso a come funzionano, internamente, i compilatori. Oggi pomeriggio ho deciso di provare a crearne uno, e per rendere le cose semplici ho deciso di creare un compilatore Brainf*ck.

Follow up:

Innanzi tutto, è bene specificare la sintassi e la semantica del linguaggio che andremo a compilare. Un sorgente Brainf*ck (d'ora in avanti, BF) altro non è che una sequenza dei seguenti simboli: < > + - [ ] . ,. Il linguaggio non prevede nessuna struttura dati, l'unico modo di memorizzare valori è scriverli in un unico array di 30000 celle dalle dimensioni di un byte ciascuna. All'avvio del programma si presume di avere tutto l'array inizializzato a zero e di aver selezionato la prima cella. I comandi hanno i seguenti significati:

• < seleziona la cella che precede quella attualmente attiva nell'array;
• > seleziona la cella che segue quella attualmente attiva nell'array;
• + incrementa di uno il valore della cella attiva;
• - decrementa di uno il valore della cella attiva;
• [ se la cella attiva contiene il valore zero, salta alla parentesi chiusa corrispondente, altrimenti non fa nulla;
• ] se la cella attiva non contiene il valore zero, salta alla parentesi aperta corrispondente, altrimenti non fa nulla;
• . stampa a video il valore della cella corrente, interpretato secondo il codice ASCII;
• , scrive nella cella corrente il valore letto da tastiera, interpretato secondo il codice ASCII.

Qualsiasi carattere diverso dagli otto sopra elencati sarà considerato un commento e quindi ignorato.

Nel file allegato trovate due implementazioni di questo linguaggio: nella prima il linguaggio viene interpretato direttamente, nella seconda viene generato il bytecode per una macchina virtuale (ovviamente anch'essa disponibile).
Iniziamo con l'analizzare il codice dell'interprete, contenuto in simple.c:

C:

Questa implementazione si limita a eseguire passo passo i comandi incontrati nel file sorgente. Questa tecnica non presenta particolari problemi fino a quando non dobbiamo usare gli operatori [ ], i quali costringono l'interprete a ricercare la parentesi corrispondente con conseguente perdita di efficienza.

Viceversa, esaminiamo il lavoro svolto dal compilatore nella funzione bc_compiler in bytecode.c:

C:

Il compilatore si limita a generare il bytecode corrispondente nel caso in cui il comando non sia relativo a un ciclo. Viceversa, quando incontra le parentesi aperte genera un bytecode JNZ (Jump if Not Zero) seguito da un byte nullo segnaposto, e inserisce la locazione attuale in uno stack. Quando invece viene incontrata una parentesi chiusa viene generato un bytecode JZ (Jump if Zero), seguito dall'offset a cui saltare ricavato come differenza tra la posizione attuale e l'ultima registrata nello stack. Contestualmente viene anche rimpiazzato il byte nullo segnaposto del JNZ corrispondente con l'offset "contrario".
Si noti come si sarebbe potuto ottenere lo stesso effetto inserendo un salto non condizionato alla fine del ciclo; in questo modo tuttavia si salta un'operazione nel caso in cui il byte nella cella attiva sia pari a zero.

A questo punto possiamo esaminare la macchina virtuale, contenuta nella funzione bc_execute in bytecode.c:

C:

Come si può notare l'esecuzione delle istruzioni [ ] è estremamente più semplice e rapida in questo caso, limitandosi la macchina virtuale a modificare il valore contenuto nel Program Counter.

Osservando i tre listati qui sopra notiamo come la compilazione di un programma in bytecode sia vantaggiosa nel caso in cui le istruzioni del nostro linguaggio non abbiano una corrispondenza 1:1 con gli opcode del linguaggio macchina di destinazione. Questo nel caso di BF si limita a due sole istruzioni, ma basta prendere un qualsiasi linguaggio più complesso di questo per accorgerci di come le istruzioni "facili" siano in netta minoranza rispetto a quelle "difficili". Oltre a questo, nel caso in cui il linguaggio di programmazione di partenza sia strutturato, la compilazione iniziale evita di dover ogni volta ricostruire l'albero sintattico astratto, e di dover poi "saltare tra i rami" di tale albero continuamente durante l'esecuzione del programma.
Questi aspetti, così come un compilatore per un linguaggio leggermente più complesso, saranno trattati in un prossimo articolo.
Nel frattempo, potreste provare ad aggiungere qualche opcode alla macchina virtuale (modificando bytecode.c e bytecode.h) e a modificare il linguaggio affinché sfrutti tali novità.

UPDATE 18/01/2009
Una semplice ottimizzazione possibile consiste nel "raggruppare" sequenze dei comandi + - < >. Per fare questo occorre aggiungere quattro opcode al nostro bytecode: ADD, SUB, BWD, FWD. Ciascun comando avrà come parametro un intero positivo che andrà a specificare il valore da sommare o sottrarre per i primi due casi, oppure le celle da scorrere indietro o avanti negli ultimi due casi. L'implementazione in bc_execute sarà semplicemente:

C:

Allo stesso modo occorrerà modificare bc_compiler per generare i nuovi opcode nel caso in cui vi siano delle sequenze di comandi identici nel file sorgente. Ogni istruzione "ripetibile" nel file sorgente sarà trattata da una regola di questo tipo:

C:

Andando a compilare il file di esempio hellow.bf con la versione nuova, e confrontando il bytecode risultante con quello generato dalla versione vecchia, possiamo notare come le dimensioni siano passate da 114 byte a soli 60 byte. Inoltre ridurre la dimensione del bytecode da interpretare porta un discreto guadagno prestazionale, dato che nella nostra implementazione una delle azioni più costose dal punto di vista della complessità è proprio la fase di dispatch.
Trovate la versione aggiornata dei sorgenti nel file bfc2.zip allegato.