I tipi di dati astratti e la crisi del software

Nota: Questo fa parte della serie “Composing Software” (ora un libro!) sull’apprendimento della programmazione funzionale e delle tecniche software compositive in JavaScriptES6+ da zero. Restate sintonizzati. Ci sono molte altre cose che verranno!
Acquista il libro | Indice | < Precedente | Successivo >

Da non confondere con:

Tipi di dati algebrici (talvolta abbreviato ADT o AlgDT). I tipi di dati algebrici si riferiscono a tipi complessi nei linguaggi di programmazione (ad esempio, Rust, Haskell, F#) che mostrano alcune proprietà di specifiche strutture algebriche. ad esempio, tipi somma e tipi prodotto.

Strutture algebriche. Le strutture algebriche sono studiate e applicate dall’algebra astratta, che, come le ADT, sono anche comunemente specificate in termini di descrizioni algebriche di assiomi, ma applicabili molto al di fuori del mondo dei computer e del codice. Può esistere una struttura algebrica che è impossibile da modellare completamente nel software. Per contrasto, gli Abstract Data Types servono come specifica e guida per verificare formalmente il software funzionante.

Un Abstract Data Type (ADT) è un concetto astratto definito da assiomi che rappresentano alcuni dati e operazioni su quei dati. Gli ADT non sono definiti in termini di istanze concrete e non specificano i tipi di dati concreti, le strutture o gli algoritmi utilizzati nelle implementazioni. Invece, le ADT definiscono i tipi di dati solo in termini di operazioni, e gli assiomi a cui queste operazioni devono aderire.

Esempi comuni di ADT

• List
• Stack
• Queue
• Set
• Map
• Stream

Le ADT possono rappresentare qualsiasi insieme di operazioni su qualsiasi tipo di dati. In altre parole, la lista esaustiva di tutte le possibili ADT è infinita per la stessa ragione per cui la lista esaustiva di tutte le possibili frasi inglesi è infinita. Le ADT sono il concetto astratto di un insieme di operazioni su dati non specificati, non un insieme specifico di tipi di dati concreti. Un malinteso comune è che gli esempi specifici di ADT insegnati in molti corsi universitari e libri di testo sulla struttura dei dati siano ciò che le ADT sono. Molti di questi testi etichettano le strutture di dati “ADT” e poi saltano l’ADT e descrivono invece le strutture di dati in termini concreti, senza mai esporre lo studente ad una reale rappresentazione astratta del tipo di dati. Ops!

Le ADT possono esprimere molte strutture algebriche utili, inclusi semigruppi, monoidi, funtori, monadi, ecc. La Specifica Fantasyland è un utile catalogo di strutture algebriche descritte dalle ADT per incoraggiare implementazioni interoperabili in JavaScript. I costruttori di librerie possono verificare le loro implementazioni usando gli assiomi forniti.

Perché gli ADT?

I tipi di dati astratti sono utili perché ci forniscono un modo per definire formalmente moduli riutilizzabili in un modo che è matematicamente solido, preciso e non ambiguo. Questo ci permette di condividere un linguaggio comune per fare riferimento ad un ampio vocabolario di utili blocchi di costruzione del software: Idee che sono utili da imparare e portare con noi quando ci spostiamo tra domini, framework e persino linguaggi di programmazione.

Storia degli ADT

Negli anni ’60 e nei primi anni ’70, molti programmatori e ricercatori di informatica erano interessati alla crisi del software. Come disse Edsger Dijkstra nella sua conferenza per il premio Turing:

“La causa principale della crisi del software è che le macchine sono diventate diversi ordini di grandezza più potenti! Per dirla senza mezzi termini: finché non c’erano macchine, la programmazione non era affatto un problema; quando abbiamo avuto qualche computer debole, la programmazione è diventata un problema leggero, e ora abbiamo computer giganteschi, la programmazione è diventata un problema altrettanto gigantesco.”

Il problema cui si riferisce è che il software è molto complicato. Una versione stampata del modulo lunare Apollo e del sistema di guida della NASA è alta come uno schedario. È un sacco di codice. Immaginate di cercare di leggere e capire ogni linea di quello.

Il software moderno è ordini di grandezza più complicato. Facebook era circa 62 milioni di linee di codice nel 2015. Se si stampassero 50 linee per pagina, si riempirebbero 1,24 milioni di pagine. Se impilate quelle pagine, otterrete circa 1.800 pagine per piede, o 688 piedi. Questo è più alto della Millenium Tower di San Francisco, l’edificio residenziale più alto di San Francisco al momento di questa scrittura.

Gestire la complessità del software è una delle sfide principali affrontate da praticamente ogni sviluppatore di software. Negli anni ’60 e ’70 non c’erano i linguaggi, i modelli o gli strumenti che oggi diamo per scontati. Cose come linters, intellisense e persino strumenti di analisi statica non erano ancora stati inventati.

Molti ingegneri del software notavano che l’hardware su cui costruivano le cose funzionava per lo più. Ma il software, il più delle volte, era complesso, intricato e fragile. Il software era comunemente:

• Sopra il budget
• In ritardo
• Buggy
• Requisiti mancanti
• Difficile da mantenere

Se solo si potesse pensare al software in pezzi modulari, non sarebbe necessario comprendere l’intero sistema per capire come far funzionare una parte del sistema. Questo principio di progettazione del software è noto come localizzazione. Per ottenere la localizzazione, avete bisogno di moduli che potete capire in modo isolato dal resto del sistema. Dovreste essere in grado di descrivere un modulo senza ambiguità senza sovraspecificare la sua implementazione. Questo è il problema che le ADT risolvono.

Dagli anni ’60 quasi fino ad oggi, far progredire lo stato della modularità del software era una preoccupazione fondamentale. È stato con questi problemi in mente che persone come Barbara Liskov (la stessa Liskov a cui si fa riferimento nel principio di sostituzione di Liskov dai principi di progettazione OO SOLID), Alan Kay, Bertrand Meyer e altre leggende dell’informatica hanno lavorato sulla descrizione e specificazione di vari strumenti per abilitare il software modulare, tra cui le ADT, la programmazione orientata agli oggetti e la progettazione per contratto, rispettivamente.

Le ADT sono emerse dal lavoro di Liskov e dei suoi studenti sul linguaggio di programmazione CLU tra il 1974 e il 1975. Hanno contribuito significativamente allo stato dell’arte delle specifiche dei moduli software – il linguaggio che usiamo per descrivere le interfacce che permettono ai moduli software di interagire. La conformità dell’interfaccia formalmente dimostrabile ci porta significativamente più vicini alla modularità e all’interoperabilità del software.

Liskov ha ricevuto il premio Turing per il suo lavoro sull’astrazione dei dati, la tolleranza agli errori e il calcolo distribuito nel 2008. Le ADT hanno giocato un ruolo significativo in quel risultato, e oggi, praticamente ogni corso universitario di informatica include le ADT nel curriculum.

La crisi del software non è mai stata completamente risolta, e molti dei problemi descritti sopra dovrebbero essere familiari a qualsiasi sviluppatore professionista, ma imparare ad usare strumenti come oggetti, moduli e ADT aiuta certamente.

Specifiche per le ADT

Diversi criteri possono essere usati per giudicare l’idoneità di una specifica ADT. Io chiamo questi criteri FAMED, ma ho solo inventato il mnemonico. I criteri originali sono stati pubblicati da Liskov e Zilles nel loro famoso documento del 1975, “Specification Techniques for Data Abstractions.”

• Formale. Le specifiche devono essere formali. Il significato di ogni elemento nella specifica deve essere definito in modo abbastanza dettagliato che il pubblico di destinazione dovrebbe avere una ragionevole possibilità di costruire un’implementazione conforme dalla specifica. Deve essere possibile implementare una prova algebrica nel codice per ogni assioma nella specifica.
• Applicabile. Le ADT dovrebbero essere ampiamente applicabili. Un ADT dovrebbe essere generalmente riutilizzabile per molti casi d’uso concreti diversi. Un ADT che descrive una particolare implementazione in un particolare linguaggio in una particolare parte del codice sta probabilmente sovraspecificando le cose. Invece, le ADT sono più adatte a descrivere il comportamento di strutture dati comuni, componenti di libreria, moduli, caratteristiche del linguaggio di programmazione, ecc. Per esempio, un ADT che descrive le operazioni di stack, o un ADT che descrive il comportamento di una promessa.
• Minimo. Le specifiche ADT dovrebbero essere minime. La specifica dovrebbe includere le parti interessanti e ampiamente applicabili del comportamento e niente di più. Ogni comportamento dovrebbe essere descritto con precisione e senza ambiguità, ma con il minor numero possibile di dettagli specifici o concreti. La maggior parte delle specifiche ADT dovrebbe essere dimostrabile usando una manciata di assiomi.
• Estensibile. Le ADT dovrebbero essere estensibili. Un piccolo cambiamento in un requisito dovrebbe portare solo ad un piccolo cambiamento nella specifica.
• Dichiarativo. Le specifiche dichiarative descrivono cosa, non come. Le ADT dovrebbero essere descritte in termini di cosa sono le cose, e di mappature di relazioni tra ingressi e uscite, non i passi per creare strutture di dati o i passi specifici che ogni operazione deve eseguire.

Una buona ADT dovrebbe includere:

• Descrizione leggibile. Le ADT possono essere piuttosto terse se non sono accompagnate da una descrizione leggibile dall’uomo. La descrizione in linguaggio naturale, combinata con le definizioni algebriche, può agire come controllo reciproco per chiarire qualsiasi errore nella specifica o ambiguità nella comprensione della stessa da parte del lettore.
• Definizioni. Definire chiaramente tutti i termini usati nella specifica per evitare qualsiasi ambiguità.
• Firme astratte. Descrivere gli input e gli output previsti senza collegarli a tipi concreti o strutture dati.
• Assiomi. Algebraic definitions of the axiom invariants used to prove that an implementation has satisfied the requirements of the specification.

Stack ADT Example

A stack is a Last In, First Out (LIFO) pile of items which allows users to interact with the stack by pushing a new item to the top of the stack, or popping the most recently pushed item from the top of the stack.

Stacks are commonly used in parsing, sorting, and data collation algorithms.

Definitions

• a: Any type
• b: Any type
• item: Any type
• stack(): an empty stack
• stack(a): a stack of a
• : a pair of item and stack

Abstract Signatures

The stack operation takes any number of items and returns a stack of those items. Typically, the abstract signature for a constructor is defined in terms of itself. Please don’t confuse this with a recursive function.

• stack(...items) => stack(...items)

Stack Operations (operations which return a stack)

• push(item, stack()) => stack(item)
• pop(stack) =>

Axioms

The stack axioms deal primarily with stack and item identity, the sequence of the stack items, and the behavior of pop when the stack is empty.

Identity

Pushing and popping have no side-effects. If you push to a stack and immediately pop from the same stack, the stack should be in the state it was before you pushed.

pop(push(a, stack())) = 

• Given: push a to the stack and immediately pop from the stack
• Should: return a pair of a and stack().

Sequence

Popping from the stack should respect the sequence: Last In, First Out (LIFO).

pop(push(b, push(a, stack())) = 

• Given: push a to the stack, then push b to the stack, then pop from the stack
• Should: return a pair of b and stack(a).

Empty

Popping from an empty stack results in an undefined item value. In concrete terms, this could be defined with a Maybe(item), Nothing, or Either. In JavaScript, it’s customary to use undefined. Popping from an empty stack should not change the stack.

pop(stack()) = 

• Given: pop from an empty stack
• Should: return a pair of undefined and stack().

Concrete Implementations

An abstract data type could have many concrete implementations, in different languages, libraries, frameworks, etc. Here is one implementation of the above stack ADT, using an encapsulated object, and pure functions over that object:

const stack = (...items) => ({
push: item => stack(...items, item),
pop: () => {
// create a item list
const newItems = ; // remove the last item from the list and
// assign it to a variable
const = newItems.splice(-1); // return the pair
return ;
},
// So we can compare stacks in our assert function
toString: () => `stack(${ items.join(',') })`
});const push = (item, stack) => stack.push(item);
const pop = stack => stack.pop();

And another that implements the stack operations in terms of pure functions over JavaScript’s existing Array type:

const stack = (...elements) => ;const push = (a, stack) => stack.concat();const pop = stack => {
const newStack = stack.slice(0);
const item = newStack.pop();
return ;
};

Both versions satisfy the following axiom proofs:

// A simple assert function which will display the results
// of the axiom tests, or throw a descriptive error if an
// implementation fails to satisfy an axiom.
const assert = ({given, should, actual, expected}) => {
const stringify = value => Array.isArray(value) ?
`` :
`${ value }`;
const actualString = stringify(actual);
const expectedString = stringify(expected);
if (actualString === expectedString) {
console.log(`OK:
given: ${ given }
should: ${ should }
actual: ${ actualString }
expected: ${ expectedString }
`);
} else {
throw new Error(`NOT OK:
given ${ given }
should ${ should }
actual: ${ actualString }
expected: ${ expectedString }
`);
}
};// Concrete values to pass to the functions:
const a = 'a';
const b = 'b';// Proofs
assert({
given: 'push `a` to the stack and immediately pop from the stack',
should: 'return a pair of `a` and `stack()`',
actual: pop(push(a, stack())),
expected: 
})assert({
given: 'push `a` to the stack, then push `b` to the stack, then pop from the stack',
should: 'return a pair of `b` and `stack(a)`.',
actual: pop(push(b, push(a, stack()))),
expected: 
});assert({
given: 'pop from an empty stack',
should: 'return a pair of undefined, stack()',
actual: pop(stack()),
expected: 
});

Conclusion

• An Abstract Data Type (ADT) is an abstract concept defined by axioms which represent some data and operations on that data.
• I tipi di dati astratti si concentrano su cosa, non su come (sono formulati in modo dichiarativo, e non specificano algoritmi o strutture di dati).
• Esempi comuni includono liste, pile, insiemi, ecc.
• Le ADT ci forniscono un modo per definire formalmente i moduli riutilizzabili in un modo che è matematicamente valido, preciso e non ambiguo.
• Le ADT sono emerse dal lavoro di Liskov e degli studenti sul linguaggio di programmazione CLU negli anni ’70.
• Le ADT dovrebbero essere FAMED. Formali, ampiamente applicabili, minime, estensibili e dichiarative.
• Le ADT dovrebbero includere una descrizione leggibile dall’uomo, definizioni, firme astratte e assiomi formalmente verificabili.

Suggerimento bonus: se non siete sicuri se incapsulare o meno una funzione, chiedetevi se la includereste in una ADT per il vostro componente. Ricordate, le ADT dovrebbero essere minime, quindi se non è essenziale, manca la coesione con le altre operazioni, o la sua specifica è destinata a cambiare, incapsulatela.

Glossario

• Gli assiomi sono affermazioni matematicamente valide che devono essere vere.
• Matematicamente solido significa che ogni termine è ben definito matematicamente in modo che sia possibile scrivere affermazioni di fatto non ambigue e dimostrabili basate su di essi.

Passi successivi

EricElliottJS.com offre molte ore di video lezioni ed esercizi interattivi su argomenti come questo. Se ti piace questo contenuto, considera la possibilità di iscriverti.