Definire strutture dati come teorie

Per definire astrazioni di alto livello che consentano di concettualizzare le strtutture dati (collezioni, stringhe, documenti, forme geometriche, ecc) senza ridurle a un agglomerato di componenti (come avviene nella programmazione imperativa), sono necessarie tecniche differenti.

L’ideale sarebbe definire le strutture dati come teorie (in senso matematico), in modo da poter ragionare sulle loro proprietà. Una teoria consiste di:

• uno o più tipi di dati (che sono a loro volta teorie, ovvero una teoria viene definita a partire da altre teorie);
• delle operazioni su tali tipi
• delle proprietà che definiscono le relazioni tra i valori e le operazioni

Un aspetto importante delle teorie matematiche è che, in genere, una teoria non descrive mutazioni, cioè non fornisce meccanismi per modificare caratteristiche degli elementi della teoria. Infatti, le mutazioni possono compromettere la validità delle leggi/proprietà della teoria.

Il vantaggio dell’astrazione basata sulle teorie è la possibilità di ragionare in modo formale sui programmi, così come si fa appunto sulle teorie in ambito matematico, evitando in particolare le difficoltà di ragionamento legate alla semantica operazionale dei linguaggi imperativi (che, essendo basata sui cambiamenti di stato, rende difficile la scrittura delle equivalenze che tipicamente verrebbero usate in matematica per esprimere le proprietà di una teoria).

Esempio: teoria dei polinomi

Esempio: teoria delle stringhe

Programmazione funzionale

Un paradigma che fornisce gli strumenti per definire le strutture dati come teorie è la programmazione funzionale (FP, Functional Programming), che in particolare:

• si concentra sulla definizione di teorie con operatori espressi come funzioni (dove il termine funzione è inteso in senso matematico)
• evita le mutazioni
• individua meccanismi (potenti) di astrazione sulle funzioni e di composizione delle funzioni.

Il termine programmazione funzionale ha due possibili significati:

• In “senso stretto”, significa programmare utilizzando le funzioni come strumento di base, senza variabili mutable, assegnamenti, cicli e altre strutture di controllo imperative.
• In “senso ampio” significa utilizzare le funzioni come strumento centrale nell’attività di programmazione; in particolare, le funzioni possono essere generate durante il processo di computazione, utilizzate e composte. Questo può essere fatto anche in linguaggi non funzionali, ma i linguaggi funzionali forniscono appositi meccanismi per operare in questo modo.

Passando a considerare i linguaggi che implementano le due accezioni di questo paradigma, si ottengono due definizioni di linguaggio di programmazione funzionale (FPL, Functional Programming Language):

• in “senso stretto”, è un linguaggio che non ammette variabili mutable, assegnamenti e strutture di controllo imperative