LISP Compiler for DOS (1993–1996)

Ho riaperto una cartella che non toccavo dal 1996. Dentro c'era un compilatore Lisp scritto in Borland C++ fra il 1993 e il 1996, con i suoi eseguibili DOS, i manuali e una manciata di programmi di esempio. Ho passato qualche ora a rimetterlo in ordine e l'ho pubblicato su GitHub, in pubblico dominio.

Vale la pena raccontarlo — non perché sia un buon compilatore, è pieno di scorciatoie — ma perché fa una cosa che nel mondo Lisp si vede raramente: compila davvero. Non interpreta, non genera bytecode, non produce codice C da dare a qualcun altro.

Da dove è venuto

Non era un progetto d'esame. Lo scrissi mentre seguivo il corso di Metodi formali per il trattamento delle informazioni, tenuto dal professor Caporaso, ma il compilatore non faceva parte del programma: era una cosa nata di fianco al corso, per conto suo. Quando il professore se ne accorse si meravigliò, e mi chiese se nel tempo libero scrivessi compilatori. Gli risposi che sì, effettivamente, era proprio quello che facevo.

Il corso però si sente, in quello che ne è uscito. Un compilatore scritto da qualcuno che in quel periodo stava studiando formalismi non parte dalla sintassi comoda: parte dalla notazione dell'articolo originale.

Niente interprete, niente assembler, niente linker

Il compilatore legge un file sorgente e scrive direttamente un eseguibile .COM per DOS. Non c'è un passaggio intermedio: nessun albero sintattico, nessun file assembly, nessun linker. Il parser è a discesa ricorsiva e mentre riconosce la grammatica emette gli opcode 8086, byte per byte, in un buffer che alla fine finisce su disco.

Il risultato è un file eseguibile autonomo, che non ha bisogno di alcuna libreria a runtime e parte istantaneamente. Nel manuale del 1995 avevo scritto una frase che oggi mi fa sorridere:

Non sono ancora riuscito a scrivere un programma LISP che impieghi più di un secondo.

Il generatore di codice è tutto dentro un unico file di meno di 900 righe. Il buffer di uscita è una classe con metodi putByte, putWord, putString; l'eseguibile viene scritto su disco nel distruttore della classe. Non è una scelta che difenderei oggi, ma ha il suo fascino: il programma finisce, l'oggetto esce di scope, il .COM compare.

Non essendoci una fase separata di risoluzione degli indirizzi, tutto quello che va corretto a posteriori viene ritoccato direttamente nel buffer. Il primo byte del .COM è una JMP la cui destinazione resta vuota per tutta la compilazione e viene riempita alla fine, quando finalmente si sa dove comincia il codice di avvio.

Il linguaggio sono le M-espressioni

Questa è la parte che mi sembra più curiosa a distanza di trent'anni. La sintassi non è quella con le parentesi tonde che tutti associano al Lisp. È la notazione che McCarthy usava nell'articolo originale del 1960, le cosiddette M-espressioni — la notazione in cui il Lisp era stato descritto prima ancora che qualcuno si accorgesse che si poteva scrivere direttamente in S-espressioni.

Le parentesi quadre servono per applicare le funzioni e per i condizionali:

ff[x] = [ atom[x] -> x;
          T       -> ff[car[x]]
        ]

subst[x,y,z] = [ atom[z] -> [ eq[z,y] -> x;
                              T       -> z
                            ];
                 T       -> cons[ subst[x,y,car[z]], subst[x,y,cdr[z]] ]
               ]

Le parentesi tonde restano per i dati: (A . B) è la coppia puntata, e (A,B) è zucchero sintattico per (A.(B.NIL)). Le M-espressioni non sono quasi mai state implementate da nessuno — sono rimaste una notazione per la carta. Qui invece si compilano.

Una S-espressione sta in sedici bit

La rappresentazione in memoria è la parte di cui vado ancora fiero, perché è tirata all'osso in un modo che solo un vincolo vero produce.

Una S-espressione è una word, di solito tenuta in BX. Se il bit più alto è a uno è un atomo; altrimenti è un puntatore a una cella. E qui sta il trucco: la cella non occupa due parole consecutive. Il car e il cdr stanno in due segmenti paralleli, indirizzati dallo stesso offset:

DS:[BX]  -->  il car
ES:[BX]  -->  il cdr

Un solo puntatore a 16 bit descrive quindi una coppia intera, e leggere il cdr costa un prefisso di segmento — un singolo byte, 0x26. Il car costa zero.

I segmenti se li ritaglia il programma stesso, in una dozzina di istruzioni all'avvio: prende CS, ci somma 64 KB e ci mette lo stack, somma altri 64 KB per i car, altri 32 KB per i cdr. Il tutto fra una CLI e una STI, perché mentre si sposta SS non è il momento di ricevere un interrupt.

Il codice di un atomo, poi, non è un indice in una tabella: è 0x0103 meno l'offset in cui si trova la sua stringa di stampa dentro il segmento codice. Siccome quell'offset è sempre maggiore di 0x0103, il numero viene negativo, e il bit alto a uno arriva gratis. Stampare un atomo significa fare una sottrazione e saltare lì.

La memoria è già tutta una lista libera

All'avvio il programma compilato non si limita ad azzerare la memoria: la infila tutta in una lista concatenata di celle libere, con un ciclo che percorre l'intero segmento due byte alla volta:

        MOV DI,2
inizio:
        MOV [DI-2],DI          ; il car di ogni cella punta alla successiva
        MOV ES:[DI-2],NIL      ; il cdr di ogni cella è NIL
        ADD DI,2
        CMP DI,8000h
        JNE inizio

Alla fine DI punta alla prima cella libera e ogni cella libera punta alla prossima. Sono 16.384 celle, tutto quello che entra in 32 KB di word.

Non c'è un garbage collector. Non c'è nemmeno una free. La memoria si consuma e basta: quando le celle finiscono, finisce anche il programma. Nel 1995 lo consideravo un dettaglio da sistemare dopo; nelle note di allora c'è scritto che la lista libera serve "più per usi futuri che non per una effettiva utilità attuale". Quegli usi futuri non sono mai arrivati.

La cons in sette istruzioni

Questa è la routine di cui vado più fiero, e sta tutta qui:

POP AX          ; toglie dallo stack l'indirizzo di ritorno
MOV BX,DI       ; BX = prima cella libera
MOV DI,[DI]     ; DI = prossima cella libera, seguendo la lista
POP ES:[BX]     ; il secondo argomento diventa il cdr
POP [BX]        ; il primo argomento diventa il car
JMP AX          ; ritorna

Il punto è la prima istruzione. Gli argomenti sono stati messi sullo stack dal chiamante, ma sopra di loro c'è l'indirizzo di ritorno della CALL, che dà fastidio. Invece di raggiungere gli argomenti scavalcandolo con un indirizzamento relativo a BP, la cons se lo toglie di mezzo infilandolo in AX: così i due argomenti si ritrovano in cima e si estraggono con due POP che scrivono direttamente dentro la cella. Poi si torna al chiamante con una JMP sul registro.

Niente prologo, niente epilogo, niente BP. Allocare una coppia costa sette istruzioni e nessun accesso in memoria oltre a quelli strettamente necessari.

Dove avevo imparato queste cose

Alle scuole superiori i miei genitori mi comprarono, con grandi sforzi, un Olivetti M24. Dentro c'era proprio quell'8086 per cui anni dopo avrei generato codice.

Ne disassemblai il BIOS. È una scuola che nessun manuale sostituisce: quel codice è scritto da qualcuno che doveva far entrare tutto in una ROM, dove ogni istruzione risparmiata era una decisione presa sul serio e ogni scorciatoia aveva un motivo. Non si impara la sintassi delle istruzioni — quella sta sul manuale — si impara il criterio con cui si sceglie fra due modi che funzionano entrambi.

In quegli anni l'assembler era ormai il linguaggio in cui ragionavo. Avevo scritto una libreria grafica più veloce di quella che veniva col Turbo Pascal, che per l'epoca era già molto veloce. E avevo già scritto un compilatore, per il Pascal — ma quello merita un articolo per conto suo.

Quando è arrivato il momento di far produrre codice macchina a un compilatore Lisp, insomma, il terreno era pronto da un pezzo.

Non ringrazierò mai abbastanza i miei genitori per quel computer.

Le primitive, e perché la logica è al contrario

T è rappresentato dal valore 0x0000, e in un condizionale è considerato falso tutto ciò che non è zero. Questa singola scelta si porta dietro tutto il resto.

NIL vale 0x8000 e viene tenuto permanentemente in DX per tutta la durata del programma, cosa che rende le due primitive più usate quasi gratuite:

SUB BX,DX               ; null[x]  -- una istruzione
AND BX,DX / SUB BX,DX   ; atom[x]  -- due istruzioni

E poi c'è la conseguenza che mi diverte di più. Siccome vero è zero, gli operatori logici si compilano scambiati:

or[a,b]   -->   POP AX ; AND BX,AX
and[a,b]  -->   POP AX ; OR  BX,AX

L'or del linguaggio è un AND di macchina, e l'and è un OR. Non è un errore: con vero uguale a zero, l'AND bit a bit dà zero — cioè vero — se almeno uno dei due operandi è zero, che è esattamente la semantica dell'or. E l'OR dà zero solo se sono zero entrambi. Le tabelle di verità tornano da sole, gratis, senza una singola istruzione di confronto.

L'unica primitiva che non se la cava con due istruzioni è not, che ha bisogno di SETZ BL. Ed è per questo che il manuale del 1995 dichiara, in maiuscolo, che serve un 80386 — un requisito che a rileggerlo oggi fa sorridere, perché tutto il resto del codice generato è 8086 puro. Un processore di due generazioni più avanti, richiesto per una singola istruzione, per una singola primitiva.

Il condizionale che ritorna invece di saltare

Il pezzo che ho riletto con più piacere è come vengono compilate le espressioni condizionali.

Il problema è noto: un condizionale a N rami ha N punti di uscita che devono convergere tutti sullo stesso indirizzo, il quale però non è ancora noto quando lo si genera. La soluzione da manuale è emettere N salti con destinazione vuota e ripassare a tapparli.

Qui invece il compilatore fa una cosa diversa. Prima di tutto mette l'indirizzo finale sullo stack, con una PUSH di una costante che verrà riempita alla fine. Poi ogni ramo, quando ha calcolato il suo risultato, esce con una banale RET:

        PUSH label_fine
        calcolo <condizione 1>
        JNZ label2
        calcolo <ramo 1>
        RET                  ; salta a label_fine
label2:
        calcolo <condizione 2>
        JNZ label3
        calcolo <ramo 2>
        RET
        ...
label_fine:

La RET non torna da nessuna chiamata: preleva dallo stack l'indirizzo che ci avevamo messo noi e ci salta. Un'unica word da correggere alla fine invece di N, e ogni uscita costa un byte solo. È un abuso della RET, e funziona benissimo.

C'è un altro dettaglio che oggi chiamerei ottimizzazione e che allora era solo pigrizia ben riposta. Il parser porta con sé un parametro flag passato per riferimento, che dice dove deve finire il risultato dell'espressione appena letta: in BX, sullo stack, o nei flag di stato. Ma serve anche al contrario: se l'espressione era la costante T, la funzione lo comunica indietro al chiamante, che a quel punto cancella il codice appena emesso, perché BX era già a zero. Il compilatore torna indietro di due byte sul buffer e riscrive sopra.

Le funzioni sono valori

Una cosa che non mi aspettavo di ritrovare, aprendo il sorgente, è che le funzioni si possono passare come parametri. E funziona nel modo più diretto possibile: quando il parser incontra una chiamata il cui nome coincide con un parametro formale della funzione corrente, invece di emettere una CALL a un indirizzo emette una chiamata indiretta attraverso lo stack frame:

CALL [BP+offset]

Il valore del parametro è l'offset della funzione, e la si chiama passando da lì. Otto byte di compilatore per avere le funzioni di ordine superiore.

Le funzioni dichiarate FORWARD, cioè usate prima di essere definite, usano lo stesso meccanismo con un livello di indirezione in più: il compilatore riserva una word nel segmento codice, ci genera contro una CALL CS:[offset], e quando finalmente incontra la definizione va a riempire quella word. La tabella dei forward è, letteralmente, una manciata di word in mezzo al codice.

L'interprete dentro il compilato

Fra gli esempi ce n'è uno che è il motivo per cui il progetto esiste: un interprete Lisp scritto in Lisp — l'evaluator metacircolare di McCarthy — compilato da questo compilatore.

Nell'intestazione avevo lasciato una riga:

Nell'interprete originale c'era un errore, che credo di aver corretto.

Non era una nota buttata lì. Nella cartella c'era anche un documento del 1993, quattro pagine, in cui sostengo che l'interprete pubblicato nell'articolo di McCarthy è sbagliato, e provo a dimostrarlo per lemmi: che il risultato di eval non è quotato, che evlis restituisce valutazioni non quotate, e che di conseguenza quando eval incontra una chiamata a funzione l'argomento arriva nella forma sbagliata. Non so se il ragionamento regga — l'ho riletto adesso e mi ci vorrebbe un po' — ma è il documento che dà il senso a tutto il resto. L'ho messo nel repository così com'è.

Nella stessa cartella ci sono anche un derivatore simbolico, che calcola derivate parziali di espressioni con PLUS e TIMES n-ari annidati a piacere e semplifica il risultato, e un decisore di tautologie che restituisce un'assegnazione falsificante quando la formula non è valida. Tutti compilati, tutti con il loro .COM del 1995 accanto.

Il pezzo di storia che non si può più scrivere

Nel manuale, alla domanda "perché un compilatore Lisp?", avevo risposto:

Non conosco l'esistenza di nessun altro compilatore Lisp finora.

Non era arroganza: era il 1995, non c'era un motore di ricerca a cui chiedere, e la risposta a "esiste già?" dipendeva da quali riviste compravi. Esistevano eccome, da vent'anni. Ma da dove stavo io non c'era modo di saperlo, e il compilatore l'ho scritto lo stesso — cosa che, se avessi potuto controllare, forse non avrei fatto.

C'è anche, nel banner del programma, la richiesta di mandare all'autore 20 dollari o 30.000 lire se il programma risultava utile. Era shareware, si faceva così. L'ho tolta prima di pubblicare, perché adesso il codice è in pubblico dominio e le due cose non stavano insieme.

Dov'è

I sorgenti pubblicati sono quelli originali del 1995, recuperati dai backup dell'epoca e convertiti da CP850 a UTF-8 perché gli accenti dei commenti tornassero leggibili. A parte la codifica, il codice è quello di allora.

Il repository è qui:

github.com/gaelazzo/lisp-compiler-dos

Ci sono i sorgenti del compilatore, sei programmi Lisp di esempio, i manuali originali in italiano e in inglese, e i binari DOS del 1995-96, che sotto DOSBox partono ancora. Il README spiega come farli girare.

È tutto in pubblico dominio: copiatelo, modificatelo, vendetelo, fateci quello che volete. Dopo trent'anni in una cartella, mi sembra il minimo.