Tipi di dato astratti

In questa pagina 5

Definizione

Un tipo di dato astratto (ADT, abstract data type) è un insieme di valori più un insieme di operazioni su di essi, descritto solo da che cosa fanno le operazioni, non da come sono realizzate.

Interfaccia: nomi, parametri, risultati e comportamento atteso (con precondizioni) delle operazioni.
Implementazione: rappresentazione concreta dei dati (array, struct, lista collegata...) e codice delle operazioni.
Incapsulamento: chi usa l'ADT accede ai dati solo tramite le operazioni. Si può cambiare l'implementazione senza toccare il codice che la usa.

Esempi di ADT classici: pila e coda (Pila e coda), lista (Liste concatenate), mappa e insieme (Dizionari e insiemi in Python). Anche list, str e dict di Python sono ADT: se ne usano le operazioni senza vedere l'implementazione in C dell'interprete.

ADT in Python: le classi

Una classe definisce un nuovo tipo; i suoi oggetti (istanze) hanno attributi (dati) e metodi (funzioni che ricevono l'oggetto come primo parametro, per convenzione self).

python

from math import gcd

class Frazione:
    """Numero razionale num/den, sempre ridotto e con den > 0."""

    def __init__(self, num, den=1):          # costruttore: inizializza l'oggetto
        if den == 0:
            raise ValueError("denominatore nullo")
        if den < 0:
            num, den = -num, -den
        g = gcd(num, den)
        self._num = num // g                 # "_" = attributo interno, da non usare fuori
        self._den = den // g

    def numeratore(self):
        return self._num

    def denominatore(self):
        return self._den

    def __add__(self, altra):                # definisce l'operatore +
        return Frazione(self._num * altra._den + altra._num * self._den,
                        self._den * altra._den)

    def __eq__(self, altra):                 # definisce ==
        return self._num == altra._num and self._den == altra._den

    def __str__(self):                       # usato da print e str()
        return f"{self._num}/{self._den}"


a = Frazione(1, 2)
b = Frazione(1, 3)
print(a + b)                 # 5/6
print(Frazione(2, 4) == a)   # True

Frazione(1, 2) crea l'oggetto e chiama __init__ con self = il nuovo oggetto.
a.numeratore() equivale a Frazione.numeratore(a).
I metodi "speciali" con doppio trattino basso (__add__, __eq__, __str__, __len__, __lt__, ...) collegano l'ADT agli operatori e alle funzioni predefinite.
Python non impedisce l'accesso agli attributi: il prefisso _ è una convenzione di incapsulamento.
L'invariante della classe (qui: frazione ridotta, den > 0) è stabilito dal costruttore e mantenuto da ogni operazione; per questo i dati non vanno modificati dall'esterno.

ADT in C: header e tipo opaco

In C l'interfaccia sta nel file .h, l'implementazione nel .c (vedi Funzioni in C). Dichiarando nel .h solo il nome della struct (tipo opaco) chi usa l'ADT non può accedere ai campi: l'incapsulamento è garantito dal compilatore.

frazione.hc

#ifndef FRAZIONE_H
#define FRAZIONE_H

typedef struct frazione *Frazione;       /* tipo opaco: i campi non sono visibili */

Frazione fraz_crea(int num, int den);    /* NULL se den == 0 o memoria esaurita */
Frazione fraz_somma(Frazione a, Frazione b);
int fraz_num(Frazione f);
int fraz_den(Frazione f);
void fraz_distruggi(Frazione f);

#endif

frazione.cc

#include <stdlib.h>
#include "frazione.h"

struct frazione {
    int num, den;
};

static int mcd(int a, int b) {           /* static: funzione visibile solo in questo file */
    if (a < 0) a = -a;
    while (b != 0) { int t = a % b; a = b; b = t; }
    return a;
}

Frazione fraz_crea(int num, int den) {
    if (den == 0) return NULL;
    Frazione f = malloc(sizeof *f);
    if (f == NULL) return NULL;
    if (den < 0) { num = -num; den = -den; }
    int g = mcd(num, den);
    f->num = num / g;
    f->den = den / g;
    return f;
}

Frazione fraz_somma(Frazione a, Frazione b) {
    return fraz_crea(a->num * b->den + b->num * a->den, a->den * b->den);
}

int fraz_num(Frazione f) { return f->num; }
int fraz_den(Frazione f) { return f->den; }
void fraz_distruggi(Frazione f) { free(f); }

main.cc

#include <stdio.h>
#include "frazione.h"

int main(void) {
    Frazione a = fraz_crea(1, 2), b = fraz_crea(1, 3);
    Frazione s = fraz_somma(a, b);
    printf("%d/%d\n", fraz_num(s), fraz_den(s));    /* 5/6 */
    /* s->num qui darebbe errore di compilazione: struct incompleta */
    fraz_distruggi(a); fraz_distruggi(b); fraz_distruggi(s);
    return 0;
}

Differenze rispetto a Python: in C servono funzioni esplicite di creazione e distruzione (la memoria è manuale, vedi Gestione della memoria in C) e non si possono ridefinire gli operatori.

Progettare un ADT

Elencare le operazioni necessarie al codice che userà il tipo, con precondizioni e risultato.
Scegliere una rappresentazione e scrivere l'invariante.
Valutare il costo di ogni operazione con quella rappresentazione (Complessità computazionale): spesso rappresentazioni diverse favoriscono operazioni diverse (es. coda su array o su lista collegata).
Scrivere test che usano solo l'interfaccia (Debugging e testing): restano validi anche cambiando implementazione.

Errori tipici

Accedere direttamente alla rappresentazione dall'esterno, rompendo l'invariante.
In Python, dimenticare self come primo parametro dei metodi o davanti agli attributi (num invece di self._num).
In C, non fornire (o non chiamare) la funzione di distruzione: memory leak.