BasicV2 8kb di potenza inaudita

Quando Chuck Norris installa Windows, è Microsoft che accetta le sue condizioni.

B.A.S.I.C.

Il Beginner’s All-purpose Symbolic Instruction Code che come acronimo intenzionale suona “BASICo” fu inventato nel 1964 da John G. Kemeny e Thomas E. Kurtz al Dartmouth College. Nacque in contrapposizione al Fortran, ed era un linguaggio compilato. Era pensato per effettuare calculi matematici (come il Fortran) e presto supportò anche la manipolazione di stringhe.

L’Altair Basic fu sviluppato dalla Microsoft di Bill Gates e Paul Allen, circa 11 anni dopo (nel 1975) e questo articolo di wikipedia racconta la roccambolesca storia della sue genesi, inclusa la scrittura di una parte fondamentale (il bootloader) durante il viaggio aereo per venderlo all Altair.

Questa prima versione del linguaggio era grande appena 4096 caratteri (4Kb) ma aveva praticamente solo la gestione dei numeri in virgola mobile, e non poteva manipolare le stringhe.

Il Commodore Basic V2 fu sviluppato da Microsoft e venduto per una cifra una-tantum alla Commodore, che esaltata dalla cosa lo installò su più di un computer (dai primi PET fino al C/64), ed è il protagonista di questa storia.

BasicV2

Il BasicV2 è progettato per girare con pochissima memoria, e in appena 9Kb di ROM riesce a stipare 71 comandi, ed è in grado di effettuare calcoli in virgola mobile con una buona precisione per il periodo in cui fu scritto. E’ una version e modificata del Microsoft Basic del 1977 e offre moltissime feature tra cui:

• Gestione di array multidimensionali
• Possibilità di definire nomi di variabili di lunghezza qualsiasi (anche se solo i primi 2 caratteri vengono considerati)
• Sub-rotudini con gosub (ma senza ricorsione)
• Programmazione de-strutturata (GOTO, IF-THEN, FOR-LOOP, READ-DATA)
• Minima capacità di manipolazione delle stringe con gestione automatica delle stringhe in memoria (“Garbage collection”)
• Possibilità di inserire i comandi in modo “abbreviato” per digitarli più velcemente (vengono poi “espansi” dal sistema)
• Editor a tutto schermo, di dimensione configurabile.
• Funzioni trigonometriche fondamentali (SIN,COS,TAN…) logaritmi in base 10 e gestione dei numeri in virgola mobile a singola precisione semi-standard IEEE.

E’ molto probabile che questo articolo finirà per contenere quasi più parole delle istruzione del tokenizer del BasicV2…

Meet 6502 and its code density

Prima di addentrarci nell’architettura di questo interprete, è indispensabile capire il linguaggio macchina per cui era stato scritto, che era quello del chip MOS 6502, una “novità” introdotta a fine anni 70 dalla MOS.

Il chip 6502 è l’equivalente di Python (o Java) dei nostri giorni. E’ un chip ortogonale a 8bit, con una altissima densità di codice. Possiede istruzioni da 1 a 3 byte, può indirizzare fino a 65536 bytes di memoria (64Kb) e dispone di appena 3 registri. E’ a metà strada tra un micro-controllore CISC e un chip RISC. Del CISC condivide un alto numero di modalità di indirizzamento, del chip RISC condivide il fatto che, come vedremo, può avere un numero molto ampio di pseudo-registri.

A fine anni'70 la RAM era una risorsa costosissima (un pò come adesso… :-) grazie all’esplosione dei data center) per cui il BasicV2 è stato progettato per girare in memoria a sola lettura (ROM) ed essere in grado di consumare pochissima RAM. Il Vic20 aveva appena 5Kb di RAM, e il Basic necessitava di meno di 2Kb per offrire tutte le feature di cui sopra.

In 8-9 Kb possono essere stipati in media 4000 istruzioni.

Armi segrete: la zero page

Il 6502 ha un’indirizzamento chiamato ZeroPage Addressing. Neanche a farlo apposta i primi 256 byte della memoria ($00-$FF in esadecimale), sono chiamati ZeroPage: sarà un caso?

No, non lo è.

Lo ZeroPage Addressing è un indirizzamento diretto di memoria (chiamato assoluto) ed è limitato ai primi 256 byte della zero page. Questo indirizzamento consente di usare appena 2 byte per es per memorizzare un valore (1 byte per cosa devi fare+1 byte per la locazione su cui farlo). Solo 21 istruzioni supportano questo indirizzamento. Questi 256 byte possono essere usati come “extra registri”, poiché il chip deve leggere solo 2 byte (contro i 3 che servono per un indirizzamento assoluto) e inoltre può elaborare l’operazione molto più velocemente. Non è un caso che il BasicV2 tenga nella zero page la maggior parte delle sue variabili più importanti, incluso anche una funzione auto-modificante (!) di cui parleremo poi.

Algoritmi

Tokenizer

Per dare un’idea di come tutte queste feature vengano usate tra loro, basti pensare che il BasicV2 non ha un vero e proprio parser nel senso “moderno” del termine. Qualsiasi istruzione venga impartita, viene prima “tokenizzata” e poi interpretata. Il sistema ha due grossi insiemi: i caratteri con un valore inferiori o uguali a 127 e quelli da 128 in su, che si riconoscono perché hanno il bit 7 sempre valorizzato. I byte con il bit 7 impostato sono chiamati token e codificano le parole chiave del Basic. Un codice chiamato chunker legge la riga del codice sottomesso e codifica ogni parola chiave del Basic in un token di 1 byte. In totale ci sono 76 parole chiave, che hanno un codice tra 28/$80 fino a 203/$CB incluso. Quello che non riesce a codificare lo lascia immutato. E’ in grado di capire che se mettette qualcosa tra virgolette si tratta di stringhe da non maciullare. Come risultato, non è possibile avere nessuna variabile o identificatore che abbia al suo interno una parola chiave del Basic. Per es la parola “ERROR” non può essere usata come nome di variabile perché contiene al suo interno la parola chiave OR. Per risparmiare lo spazio della ROM, le parole chiave non hanno un terminatore, ma l’ultima parola ha il bit 7 accesso, così il sistema “sa” dove finisce (siamo a livelli di paranoia, lo so…).

Questo porta diversi vantaggi:

1. Il codice di un listato Basic viene codificato appena viene immesso, e occupa pochissimo spazio in memoria
2. Durante l’esecuzione, il Basic non deve far altro che associare ad ogni token la relativa funzione di gestione (che si occupa anche del parsing della propria sintessi, almeno a grandi linee)

Entità Variabili!

Lo spazio delle variabili si trova in tutta l’area di memoria non occupata dal programma (ne consegue che più il vostro programma è grande, meno variabili potrete allocare…)- Il Basic supporta variabili numeriche, stringhe e interi. Gli interi in realtà sono numeri in virgola mobile arrotondati, e quindi sono lenti quanto quest’ultimi… una occasione mancata per Microsoft, che si rifarà con Windows95.

Garbage Collector

Una delle feature del Basic V2 è la capacità di poter concatenare stringhe a runtime. Per farlo. il Basic alloca queste stringe nello spazio delle variabili, e ne alloca una nuova istanza mano a mano che le operazioni continuano. Quando “finisce” lo spazio, effettua una “garbage collection” per compattare tutte le variabili, sperando che questo porti a liberare un po’ di memoria: riesce spesso, ma ha come effetto collaterale che se elaborate molte variabili il Basic ogni tanto si blocca e va in “coma apparente” perché deve fare questo lavoro.

Si fa presto a dire leggi il codice

La compressione degli identificatori la si trova anche nei nomi delle funzioni… che hanno nomi criptici come CHRGET o CHRGO (vi siete mai chiesto perché il DOS ha nomi di soli 8 caratteri?…. il 6502 deve aver lasciato il segno in Microsoft….).

Esiste una funzione più importante delle altre che si chiama CHRGET. Questa funzione serve a leggere il prossimo token del listato basic, e viene copiata nella zero page intorno a $73 per una ragione cruciale. Per la spiegazione completa del funzionamento di CHRGET vi rimando a questo articolo dell’ottimo C64Wiki, qui vi diamo un cenno della sua complessa eleganza:

 1 0073: E6 7A    INC $7A   ; Increase text pointer, less significant part
 2 0075: D0 02    BNE $0079 ; overflow
 3 0077: E6 7B    INC $7B   ; Text pointer, higher order part
 4 0079: AD 00 08 LDA $0800 ; Read text with self-modified address
 5 007C: C9 3A    CMP #$3A  ; ":"=End of statement, also 1st character after "9"
 6 007E: B0 0A    BCS $008A ; greater than "9", no digit: carry flag=1 or end of instruction at ":"
 7 0080: C9 20    CMP #$20  ; Space...
 8 0082: F0 EF    BEQ $0073 ; read over
 9 0084: 38       SEC       ; Prepare subtraction...
10 0085: E9 30    SBC #$30  ; Digit "0"
11 0087: 38       SEC       ; Invert carry... (digits are >=0)
12 0088: E9 D0    SBC #$D0  ; Subtraction back, less than "0", carry flag=1
13 008A: 60       RTS       ; Zero flag=1 end of instruction, carry flag=1 no digit

Il 6502 ha un grosso tallone di achille: è un chip ortogonale a 8bit, tutti i suoi registri sono a 8bit tranne il puntatore al codice (PC). Il 6502 non ha un modo per indicizzare più di 256 byte di memoria. E’ fisicamente impossibile avere un puntatore a 16 bit che possa indirizzare una falcata maggiore di 256 byte. La CHaRacterGET risolve la cosa con del codice auto-modificante che fa un caricamento immediato della locazione corrente del basic (vedi riga 79). L’istruzione in $79 ha il parametro nei due byte seguenti: $7A e $7B con il byte più significativo in $7B

Prima di leggere la locazione, la funzione modifica fiscamente il parametro della funzione in $79, alterando le locazioni che si trovano in 7A e 7B. La CHRGET si trova nel ciclo più interno del basic perché viene chiamata per il parsing di ogni singola istruzione del Basic, che essendo un linguaggio interpretato deve fare questa operazione in continuazione. La CHRGET deve quindi essere dannatamente veloce, e quindi ogni byte conta: per questa ragione si trova in zero page: le istruzione “INC $7A” e “INC $7B” usano lo ZeroPage Addressing per risultare super performanti.

Il C/128 la allunga di qualche byte per poter indirizzare più memoria e la sposta fuori dalla zero page, ma tanto basta per renderlo più lento del BasicV2.

Riflessioni

Il codice automodificante di CHRGET è molto comune nel 6502, ma anche molto complesso da capire. I chip moderni al 99% proibiscono la possibilità scrivere codice auto-modificante, soprattutto per ragioni di sicurezza informatica ma anche per assicurare una buona stabilità del sistema.

Le ridotte dimensioni del codice del BasicV2, fanno si che in pratica non ci siano raffinati algoritmi a disposizione dell’utente finale: le istruzioni GO TO <linea> sono implementate con una ricerca lineare a partire dall’inizio del programma. E’ per questo che in molti giochi scritti in Basic le routine gosub sono poste in alto: per ridurre al minimo il tempo di ricerca per l’invocazione.

L’unico debug possibile è con i comandi STOP e CONT(INUE). Non c’è una istruzione per indirizzare lo schermo, nulla per gestire gli sprite o charset specializzati. Nulla di nulla.

Espandere! Espandere!

La Commmodore creerà il SuperExpander per espandere il Basic del Vic20 e il SuperExpander64 per il C/64. Infatti una feature il Basic la ha: è possibile espanderlo perché le sue funzionalità principali sono indirizzate tramite “vettori” che vengono tenute in RAM: in questo modo è possibile progettare delle cartucce che “estendano” le funzionalità del Basic. Il SuperExpander64 è fornito su cartuccia, e “mangia” 8kb di RAM, installandosi nella parte alta, $8000 - $9FFF subito prima del Basic in ROM.

A esser maligni, si può ipotizzare che la Commodore non aggiornò mai il BasicV2 del Vic20 e del C/64 per poter poi vendere le cartucce di espansione: potrebbe esserci del vero.