Programmazione funzionale in spazio logaritmico: una libreria di funzione aritmetiche

In questa Tesi forniamo una libreria di funzioni aritmetiche che operano in spazio logaritmico rispetto all'input. Partiamo con un'analisi dei campi in cui è necessario o conveniente porre dei limiti, in termini di spazio utilizzato, alla computazione di un determinato software. Vista la larga diffusione del Web, si ha a che fare con collezioni di dati enormi e che magari risiedono su server remoti: c'è quindi la necessità di scrivere programmi che operino su questi dati, pur non potendo questi dati entrare tutti insieme nella memoria di lavoro del programma stesso. In seguito studiamo le nozioni teoriche di Complessità, in particolare quelle legate allo spazio di calcolo, utilizzando un modello alternativo di Macchina di Turing: la Offline Turing Machine. Presentiamo quindi un nuovo “modello” di programmazione: la computazione bidirezionale, che riteniamo essere un buon modo di strutturare la computazione limitata in spazio. Forniamo poi una “guida al programmatore” per un linguaggio di recente introduzione, IntML, che permettere la realizzazione di programmi logspace mantenendo però il tradizionale stile di programmazione funzionale. Infine, per mostrare come IntML permetta concretamente di scrivere programmi limitati in spazio, realizziamo una libreria di funzioni aritmetiche che operano in spazio logaritmico. In particolare, mostriamo funzioni per calcolare divisione intera e resto sui naturali, e funzioni per confrontare, sommare e moltiplicare numeri espressi come parole binarie.