M2 Report

M2 per programmatori C

Il linguaggio C è versatile e utile. Il compilatore M2 è scritto in C e traduce M2 in C. Il C eccelle in due ambiti: i driver software e i programmi di sistema. Tuttavia, il C mostra dei limiti in altri ambiti: i programmi applicativi, la manipolazione di stringhe, le strutture dati dinamiche, il debugging.

Il principio di base di M2 è che i programmi vengono più letti che scritti. Perciò il sorgente deve essere molto chiaro. Per questo le parole chiave di M2 sono scritte in caratteri maiuscoli, in modo da risaltare ed evidenziare la struttura del programma.

Il secondo principio di M2 è che deve esistere un solo modo per scrivere una cosa. Un ciclo FOR deve essere impiegato quando è noto a priori l'intervallo della variabile indice. Gli assegnamenti si fanno solo nelle apposite istruzioni di assegnamento. Le parentesi graffe non esistono: le istruzioni di controllo (IF, WHILE, LOOP, ecc.) usano parole chiave obbligatorie che delimitano le istruzioni controllate; in questo modo il programmatore può concentrarsi sulla logica del suo programma e non perde tempo con la formattazione del sorgente.

I file di inclusione .h corrispondono ai DEFINITION MODULE di M2. In un DEFINITON MODULE si possono dichiarare le costanti, i tipi, le variabili e i prototipi delle funzioni. Tutte le entità dichiarate diventano disponibili ai moduli che importano questo modulo. In questo DEFINIITON MODULE di fantasia, definiamo una interfaccia per accedere al file system. (NOTA: questo non è un modulo reale, ma ha il solo scopo di illustrare le caratteristiche di M2.)

DEFINITION MODULE Files

CONST
    MAX_FILE_NAME = 64
    ROOT_FILE = "C:\"

TYPE
    FILE = FORWARD
    PATH_FILE = ARRAY OF STRING
    ACCESS_MODE = (read, write)

FUNCTION Open(file_name: PATH_FILE, m: ACCESS_MODE): FILE
FUNCTION Write(f: FILE, buffer: STRING)
FUNCTION Read(f: FILE, len: INTEGER): STRING
FUNCTION Close(VAR f: FILE)

END

In questo ipotetico modulo, il nome di un file è rappresentato da una array di stringhe che descrivono il path del file. Il FILE è un tipo FORWARD la cui struttura è dichiarata nell'IMPLEMENTATION MODULE e non è nota ai moduli clienti. Il tipo enumerativo ACCESS_MODE è del tutto simile al tipo enum del C. La funzione Open() ritorna un oggetto di tipo FILE da usare nelle successive funzioni per la lettura e la scrittura dei dati. Un modulo cliente potrebbe essere strutturato così:

MODULE ShowData

IMPORT Files

VAR
    src, dst: FILE
    s: STRING

BEGIN
    src = Open( {"Documenti", "Fotografie", "spiaggia.jpg"}, read )
    dst = Open( {"Archivio", "Foto", "vacanze.jpg" }, write )
    LOOP
        s = Read(f, 4*1024)
        IF s = NIL THEN
            EXIT
        END
        Write(f, s)
    END
    Close(src)
    Close(dst)
END

I nomi dei file sono composti con l'operatore {} che crea un array di stringhe. L'array prodotto è il pathfile che viene passato alla funzione Open(). Il file spiaggia.jpg viene copiato nel file vacanze.jpg. Il ciclo LOOP...END legge blocchi di 4 KB dal file sorgente e li copia nel file destinazione. Quando Read() ritorna NIL la copia è terminata e l'istruzione EXIT termina il ciclo.

Ci sono altri fatti importanti da notare in questo breve programma. Spazi e a-capo vengono ignorati dal compilatore, esattamente come in C. La punteggiatura è ridotta al minimo. Le istruzioni non devono essere terminate da ';'. Il simbolo di '=' è un assegnamento quando usato nella istruzione di assegnamento, ed è un operatore di confronto quando usato in una espressione logica. Non si possono eseguire assegnamenti dentro alle espressioni; pertanto il codice C del tipo

int c;
while( (c = getchar()) != EOF ){
    putchar(c);
}

deve essere tradotto in qualcosa simile a questo:

VAR c: STRING
...
LOOP
    c = Read(f, 1)
    IF c = NIL THEN
        EXIT
    END
    print(c)
END

In M2 non esistono i puntatori, nè è necessario manipolare indirizzi di memoria. Le variabili dinamiche vengono allocate automaticamente quando si assegnano, e vengono rilasciate automaticamente quando non sono più referenziabili. Le stringhe hanno lunghezza arbitraria. Gli array hanno lunghezza arbitraria e si espandono automaticamente. I RECORD, simili alle struct del C, vengono allocati automaticamente. Vediamo le equivalenze tra i tipi nel due linguaggi:

Siccome in M2 le stringhe e gli array sono allocati dinamicamente, le dichiarazioni di stringhe a lunghezza fissa (unsigned char s[80];) e gli array a dimensione fissa (int a[1000];) hanno per equivalenti una stringa (VAR s: STRING) e un array di lunghezza arbitraria (VAR a: ARRAY OF INTEGER).

Questa struttura dati rappresenta i dati di una automobile:

/* MODULE AutoUsate */

typedef struct {
    unsigned char * marca;
    unsigend char * modello;
    int anno_immatricolazione;
    int km_percorsi;
} Automobile;

L'equivalente M2 è:

MODULE AutoUsate

TYPE
    Automobile = RECORD
        marca: STRING
        modello: STRING
        anno_immatricolazione: INTEGER
        km_percorsi: INTEGER
    END

Un rivenditore di automobili usate decide di usare un array per rappresentare le automobili. Inoltre definisce una funzione Inserisci() per inserire un nuovo modello, e una funzione Cerca() per trovare un modello. Cominciamo con la versione in C della funzione di inserimento:

Automobile **automobili = 0;
int automobili_n = 0;


void Inserisci(unsigned char *marca, unsigned char *modello,
    int anno_immatricolazione, int km_percorsi)
{
    Automobile *a;

    a = malloc( sizeof( Automobile ) );
    a->marca = strdup( marca );
    a->modello = strdup( modello );
    a->anno_immatricolazione = anno_immatricolazione;
    a->km_percorsi = km_percorsi;

    if( automobili == 0 )
        automobili = malloc( 1 * sizeof( Automobili * ) );
    else
        automobili = realloc( automobili,
            (automobili_n+1) * sizeof( Automobile ) );
    automobili[ automobili_n++ ] = a;
}


int main()
{
    Inserisci("FIAT", "Duna", 1990, 15000);
}

Lo stesso codice riscritto in M2:

VAR automobili: ARRAY OF Automobile

FUNCTION Inserisci(marca: STRING, modello: STRING,
    anno_immatricolazione: INTEGER, km_percorsi: INTEGER)
VAR a: Automobile
BEGIN
    a[marca] = marca
    a[modello] = modello
    a[anno_immatricolazione] = anno_immatricolazione
    a[km_percorsi] = km_percorsi
    automobili[] = a
END

BEGIN
    Inserisci("FIAT", "Duna", 1990, 1500)
END

Le chiamate di funzione sono del tutto simili in entrambe le versioni: le stringhe vengono passate come puntatori, mentre i numeri interi sono passati come valori. Ma qui terminano le similitudini. Ora vediamo le differenze.

In M2 gli array sono inizialmente non allocati e si espandono in modo da ospitare gli elementi che vengono assegnati. La funzione count(a) ritorna il numero di elementi presenti nell'array. Siccome l'indice degli array parte da zero come in C, questa funzione dà l'indice del prossimo elemento da usare. In alternativa, le parentesi quadre a[] vuote senza indice sono sinonimo der prossimo elemento disponibile a[count(a)].

Il RECORD a è inizialmente non allocato, esattamente come in C. Tuttavia M2 assicura che tutte le variabili non assegnate abbiano un valore iniziale definito. Nel nostro caso inizialmente a=NIL. Il record viene allocato in memoria nel momento in cui si esegue il primo assegnamento al campo marca. M2 provvede ad allocare lo spazio necessario esattamente come abbiamo fatto in C. Notare che il selettore di campo di record e il selettore di elemento di array è la coppia di parentesi quadrate [...].

La differenza più importante tra il C e M2 è il modo in cui vengono trattate le stringhe. In M2 le stringhe sono assimilate a dati di tipo semplice, come i numeri. Nella maggior parte del codice le stringhe vengono "copiate" come puntatori. In effetti nel codice della funzione Inserisci(), M2 non alloca alcuna stringa ma copia solo i puntatori. La conseguenza di questo fatto è che, mentre in C è possibile modificare un carattere di una stringa, in M2 le variabili di tipo stringa non si possono modificare: per cambiare una stringa è necessario copiare nella variabile il puntatore a una nuova stringa. E' per questo motivo che nella implementazione C abbiamo usato strdup().

Vediamo anche il codice della funzione Cerca() che ritorna l'automobile corrispondete alla marca e al modello richiesti. Siccome possono esistere più ricorrenze, la funzione ritorna un array con tutte le ricorrenze trovate. Questa volta riportiamo solo l'implementazione in M2:

FUNCTION Cerca(marca: STRING, modello: STRING): ARRAY OF Automobile
VAR   i: INTEGER   trovate: ARRAY OF Automobile
BEGIN
    FOR i=0 TO count(automobili)-1 DO
        IF automobili[i][marca] = marca
        OR automobili[i][modello] = modello
        THEN
            trovate[] = automobili[i]
        END
    END
    RETURN trovate
END

In questa funzione l'array trovate è inizialmente vuoto; in esso vengono progressivamente inserite le ricorrenze trovate. In realtà ciò che viene copiato nell'array è solo il puntatore al RECORD i-esimo dell'array automobili, e ciò che viene restituito dalla funzione è il puntatore all'array così costruito.

M2 produce automaticamente tutto il codice necessario per gestire la memoria e le strutture dati. In effetti in M2 non esiste un equivalente delle funzioni malloc() e free(). Gli oggetti allocati vengono rilasciati dalla memoria quando non ci sono più variabili, né argomenti di funzione, nè strutture dati che fanno riferimento a quell'oggetto.

Gli array si possono espandere, ma non si possono contrarre. Per rimuovere l'automobile x dal nostro elenco dovremo copiare l'array in un altro array provvisorio omettendo l'elemento da eliminare, quindi dovremo sostituire il vecchio elenco con quello nuovo:

FUNCTION Cancella(x: Automobile)
VAR
    i, j: INTEGER
    a: ARRAY OF Automobile
BEGIN
    FOR i=0 TO count(automobili)-1 DO
        IF automobili[i] <gt; x THEN
            a[] = automobili[i]
        END
    END
    automobili = a
END

Il garbage collector provvederà a cancellare dalla memoria l'elemento x che non ha più riferimenti. Questo codice cancella dall'elenco tutte le FIAT Duna presenti:

VAR a: ARRAY OF Automobile  i: INTEGER
...
a = Cerca("FIAT", "Duna")
FOR i=0 TO count(a)-1 DO
    Cancella(a[i])
END
a = NIL

Quando gli array non sono adeguati per la struttura dati che si deve gestire, in M2 si possono costruire anche liste e alberi. Vediamo per esempio come si rappresenta una lista doppiamente concatenata:

TYPE
    Automobile = RECORD
        marca: STRING
        modello: STRING
        anno_immatricolazione: INTEGER
        km_percorsi: INTEGER
        precedente, seguente: Automobile
    END

VAR automobili: Automobile

Il record ha adesso due nuovi campi che permettono di spostarsi sul record precedente e sul record seguente della lista. La funzione per cancellare un record si modifica come segue:

FUNCTION Cancella(x: Automobile)
VAR a: Automobile
BEGIN
    a = automobili
    WHILE a <gt; NIL DO
        IF a = x THEN
            IF a[precedente] <gt; NIL THEN
                # Collego il precedente al seguente:
                a[precedente][seguente] = a[seguente]
            END
            IF a[seguente] <gt; NIL THEN
                # Collego il seguente al precedente:
                a[seguente][precedente] = a[precedente]
            END
            RETURN
        END
        a = a[seguente]
    END
END

Osserviamo attentamente il sorgente, perché ci sono delle interessanti differenze con il C. Il ciclo WHILE percorre l'elenco delle automobili. Quando viene individuata l'automobile da cancellare, il record prededente viene fatto puntare al seguente, mentre il record seguente viene fatto puntare al precedente. Una volta usciti dalla funzione, il record da cancellare non ha più riferimenti all'interno del programma e lo spazio da esso occupato in memoria viene recuperato. Queste operazioni di cambio indirizzi vengono protette all'interno di due IF che assicurano che l'elemento precedente e seguente esistano. Un controllo di questo tipo è necessario anche in C, per evitare la dereferenziazione di un NULL pointer. In M2 è diverso, ed è interessante studiare cosa accadrebbe se le due istruzioni IF più interne venissero omesse. Se ad esempio il precedente di a non esiste, l'istruzione

a[precedente][seguente] = a[seguente]

creerebbe il record a[precedente] e assegnerebbe il campo [seguente] di questo record, lasciando gli altri con il loro valore default. Questo fatto sorprendente è una conseguenza del meccanismo di allocazione automatica degli oggetti. Ad una attenta analisi, si scopre che questo non avrebbe alcun effetto sulla logica del programma, che sarebbe solo più criptico da capire e meno efficiente.

Operatori. Il C prevede ben 11 livelli di priorità per gli operatori aritmetici, logici e di confronto. Questo permette di risparmiare in alcuni casi le parentesi tonde, ma induce a commettere qualche errore. In M2 invece esistono solo tre priorità: 1) l'operatore di complemento a uno, 2) gli operatori moltiplicativi, 3) gli operatori additivi e di cambio di segno. Ad esempio, in M2 questa espressione

viene calcolata da sinistra verso destra semplicemente come è scritta perché tutti gli operatori che vi compaiono sono di tipo "additivo" e quindi hanno la stessa priorità. In C la stessa espressione viene interpretata in modo meno ovvio:

Per concludere questa panoramica delle differenze tra M2 e C, vediamo come si scrivono nei due linguaggi le istruzioni più comuni:

if( i < 0 && ! b ){
	...
} else if( i > 0 ){
	...
} else {
	...
}

IF (i < 0) AND NOT b THEN
	...
ELSIF i > 0 THEN
	...
ELSE
	...
END

for( i=10; i>0; i-- ){
	...
}

FOR i=10 TO 1 BY -1 DO
	...
END

do {
	...
} while( p != NULL );

REPEAT
	...
UNTIL p = NIL