EmbeddedMATLAB_2_C

Abstract

In alcuni contesti di sviluppo, solitamente l’idea risolutiva di un problema ingegneristico viene prima testata in Matlab successivamente una volta raggiunta una certa stabilità viene tradotta in C per poter essere calibrata in maniera definitiva su un’architettura “convenzionale” o su un DSP, microcontrollore, GPU, etc.

L’obiettivo del progetto EmbeddedMATLAB_2_C è quindi quello di creare un traduttore da Embedded Matlab a C, leggermente in controtendenza con quelli già esistenti, ovvero un traduttore che conservi la semantica del programma sorgente e che produca un codice oggetto corretto e facilmente modificabile. Al contrario i traduttori distribuiti dalla MathWorks sono in grado di generare codice oggetto non modificabile a meno di ricompilazione.

Introduzione

EmbeddedMATLAB_2_C (em2c) è un prodotto software che permette la traduzione di un programma scritto in linguaggio Matlab (con i vincoli di EmbeddedMatlab) in codice C. L’idea di questo progetto nasce dalla voglia di fornire alla comunità scientifica uno strumento che permetta di ridurre il gap tra l’idea e l’implementazione. Oggi giorno chi è portato a risolvere determinati problemi di calcolo, e.g. realizzazione di processi e simulazioni, ricerca strumenti flessibili ed immediati come Matlab, sfruttando la facilità di sviluppo e debug del software che questo linguaggio interpretato mette a disposizione. Questo però rende abbastanza oneroso il lavoro di traduzione quando si intende trasportare il proprio lavoro su un sistema embedded o microcontrollori che vengono prevalentemente programmati in linguaggio C. La Mathworks fornisce compilatori che permettano di tradurre un codice scritto in Matlab con uno scritto in linguaggio C come mcc o emlx; tuttavia questi due compilatori possiedono alcuni svantaggi: uno di questi è che una eventuale modifica da fare sul prodotto compilato obbliga il ritorno a Matlab e alla ricompilazione; con em2c le modifiche, necessarie in fase di calibrazione dell’applicazione, possono essere effettuate direttamente nel codice C generato. In molti ambienti ingegneristici differenti da quello informatico apportare le modifiche in Matlab risulterebbe più semplice (data la familiarità del linguaggio) ma richiederebbe più tempo di sviluppo. L’idea di effettuare le modifiche sul codice generato è sostenuta dal fatto che il linguaggio C diventa sempre più noto anche tra i non esperti del settore.

Punti di Forza

Un punto di forza di em2c è sicuramente la possibilità di modificare il codice compilato perché conservando la semantica delle istruzioni è possibile manipolarle. Un ulteriore punto di forza del nostro compilatore è la sua struttura modulare che si basa su un modulo che costituisce il front end (la fase di analisi) ed uno che costituisce il back end (sintesi); il primo analizza il file sorgente e crea una struttura intermedia, detta Abstract Syntax Tree (AST), che servirà come input per il secondo modulo. La suddivisone del compilatore in queste componenti risulta essere vantaggiosa perché consente di sostituire il back end per tradurre il codice sorgente in altri linguaggi target come Java o C++. In letteratura esistono diverse rappresentazioni intermedie ma l’adozione dell’AST è data dalla volontà di tradurre codice source-to-source, ed inoltre la struttura ad albero consente di rendere esplicito il flusso di istruzioni del codice sorgente e di utilizzare questa informazione nella fase di traduzione. Un inconveniente di questa scelta è la necessità di dover memorizzare la rappresentazione intermedia. Per ovviare a questo problema, si è progettata una struttura sintetica ad hoc che permetta di ottenere un occupazione di memoria pari ad 1/3 della struttura originale.

Un altro punto di forza del nostro progetto è la struttura mat all’interno del codice target che descrive le matrici. Tale struttura è composta da due interi che indicano la dimensione della matrice a cui punta il doppio puntatore anch’esso presente nella struttura. Questa struttura è stata scelta perché in Matlab ogni variabile viene memorizzata come una matrice ed ognuna di esse conserva delle informazioni associate come le dimensioni, tipo, etc.. Il linguaggio C invece distingue i dati semplici dai dati strutturati. Per cui, se in Matlab un dato scalare è memorizzato in una matrice di dimensioni 1×1 in ogni caso, in C questa scelta è priva di senso per quanto detto testé. Sicché, si è optato per l’implementazione della struttura mat solo per dati matriciali. Questa peculiarità è realizzata in fase di traduzione attraverso l’utilizzo di una funzione che scansiona il sottoalbero alla ricerca di matrici; se queste vengono individuate ad esempio a destra di un’assegnazione, un flag abilita uno stato del traduttore che si predispone a generare istruzione contenenti gli operatori che utilizzano la struttura mat.

Per realizzare una corrispondenza semantica tra i comandi Matlab e i comandi tradotti, il file generato si serve di una libreria statica (Matlab.h), da noi creata che contiene l’implementazione di alcuni metodi di base. Basti pensare che in Matlab un prodotto matriciale è composto da una sola riga di codice, mentre in C questo andrebbe fatto sviluppando l’intero algoritmo. Utilizzando la Matlab.h il codice tradotto utilizza una chiamata a funzione (e quindi una sola riga di codice) per espletare la medesima operazione.

Considerando che i dispositivi target su cui far eseguire i codici tradotti da em2c possano avere a disposizione poche risorse, come la memoria dinamica, è necessario generare un codice target che tenga conto di questa esigenza. Così nella medesima libreria Matlab.h; sono state inserite delle funzioni che garantiscono un uso accorto della memoria dinamica: la copia tra due strutture già allocate non avviene scambiando i puntatori ma facendo una copia valore-per-valore, sfruttando quindi l’allocazione fatta precedentemente; le strutture temporanee usate per memorizzare valori parziali vengono liberate non appena non sono più necessarie.

Durante la progettazione si è pensato di introdurre il concetto di correttezza semantica anche nell’albero sintattico. Senza questo piccolo accorgimento all’aumentare della complessità dell’operazione scritta nel programma sorgente, si otterrebbero alberi molto profondi; prima di procedere con la generazione del codice si dovrebbe rivisitare tutto l’albero per verificarne la correttezza semantica per poi tradurlo. Propagando il concetto di correttezza semantica all’interno dell’albero sintattico, dalle foglie sino alla radice, si può velocemente determinare se il contenuto dell’albero è semanticamente corretto, effettuando così una specie di potatura. Nel caso in cui la presenza di un errore viola la correttezza semantica del codice (e quindi dell’albero sintattico), la costruzione dell’ast viene interrotta risparmiando quindi occupazione di memoria ma il compilatore continua la ricerca degli errori.

Punti di Debolezza

Un punto di debolezza è che in questa versione di em2c non sono state implementate alcune funzionalità come il ciclo for, il selettore “:” e le funzioni: tali costrutti sono comunque riconosciuti dall’analizzatore lessicale e sono state inserite ugualmente nell’analizzatore sintattico. Tuttavia sono state implementati tutti i costrutti necessari (sequenza, selezione e iterazione) per soddisfare il teorema di Böhm-Jacopini.

La scelta di un compilatore a due passate ha il difetto di essere onerosa in termini di occupazione di memoria a causa della memorizzazione delle rappresentazioni intermedie; in em2c l’adozione della forma sintetica dell’ast mitiga questo problema.

Sviluppi Futuri

Essendo il progetto molto ambizioso e tutt’ora ad un livello nascente, ci sarebbero molti sviluppi futuri applicabili. Uno tra tanti è lo sviluppo delle regole semantiche e delle strutture dati dell’AST relative alle funzioni e al costrutto for. Si potrebbe ampliare la grammatica per inserire altri costrutti, come la selezione di interi vettori di matrici attraverso i due punti (:). Si potrebbe sviluppare il back end che traduca l’AST in linguaggio C++ che grazie al polimorfismo ed alla ridefinizione degli operatori aritmetici, faciliterebbe le operazioni tra strutture dati.

Infine, la scelta dell’AST come rappresentazione intermedia conduce ad un altro sviluppo cruciale: l’ottimizzazione della rappresentazione intermedia. Come detto precedentemente, l’AST conserva il flusso di istruzione del programma, per cui a partire da questa struttura si può rappresentare il DAG (Directed Acyclic Graph) relativo al workflow ed individuare più facilmente le dipendenze tra istruzioni, blocchi di codice ricorrenti, blocchi inutilizzati, etc., all’interno del codice sorgente.

Conclusioni

L’obiettivo che ci ha spinto alla realizzazione di em2c è quello di dimostrare che una strada realmente complessa può essere comunque affrontata con curiosità e desiderio di apprendere. Progettare un compilatore è una delle sfide più impegnative per un ingegnere informatico ma è anche un’esperienza estremamente formativa. Le difficolta incontrate ci hanno permesso di riconoscere e nel tempo anche risalire alle cause degli innumerevoli core dump incontrati.

Infine considerando che le restrizioni di EmbeddedMatlab da noi considerate non lo rendono molto diverso da Matlab, em2c potrebbe essere la base per un traduttore da Matlab a C++ con supporto per la programmazione orientata agli oggetti: chimera (non più irrealizzabile!) del nostro progetto iniziale.

Crediti

Questo progetto è stato svolto dal sottoscritto e dal collega Marco Colaprico, come tema d’anno per l’esame di Compilatori e Interpreti.

Download

Adobe fileRelazione Compilatori.pdf