Non Pensare da Informatico!

Pensare da Informatico (PdI) è un libro generoso e benintenzionato, e il suo autore merita un posto tra i santi evangelisti di Python. È anche purtroppo un libro tragicamente pieno di inesattezze, spiegazioni didatticamente male impostate, esempi poco ispirati. Il bonus/malus di essere gratis e tradotto in Italiano ne ha facilitato la diffusione e ha prodotto negli anni una quantità di storture nella testa di centinaia di studenti. Inauguro qui una serie di note in cui analizzo in modo non sistematico i problemi del libro. Non certo per "fare le pulci" con cattiveria, ma per mettere in guardia i suoi lettori: PdI è un libro facile e scorrevole, ma nasconde le sue insidie.

Proprio oggi un post su Python.it ha attirato la mia attenzione sul breve paragrafo 11.6 (versione 2.2.23) dedicato alla memoizzazione nel classico caso di Fibonacci ricorsivo. E va detto prima di tutto che questo è un buon paragrafo: l'idea di parlare di memoizzazione nel capitolo sui dizionari è buona, usare Fibonacci per introdurre la memoizzazione va benone, la spiegazione è chiara, c'è una figura che aiuta a capire il problema. Davvero, per la media dei paragrafi di PdI, questo è un buon paragrafo.

Solo che poi il codice è questo (ops):

# PdI, esempio dal paragrafo 11.6
memo = {0:0, 1:1}

def fibonacci(n):
    if n in memo:
        return memo[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    memo[n] = res
    return res

Notate nulla di strano? Io niente, a una prima scorsa. Ma appena l'occhio si posa per più di pochi secondi su questo esempio, suona un campanello d'allarme. Dove si ferma questa funzione? Che cosa le impedisce di annidarsi in ricorsioni infinite, man mano che le chiamate a fibonacci(n-1) e n-2 diventano numeri negativi? In effetti, la prima volta che PdI fa l'esempio di Fibonacci ricorsivo, qualche capitolo prima, la funzione ha la classica forma a cui siamo abituati:

# PdI, esempio dal paragrafo 6.7
def fibonacci(n):
    if n == 0: 
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Nella versione con memoizzazione, dove sono finiti i test di arresto per n==0 e n==1? Semplice: l'idea dell'autore è che non sono più necessari perché una attenta e conveniente inizializzazione della cache memo = {0:0, 1:1} si occupa di gestire la cosa. Ma lo sentite il campanello di allarme? Adesso abbiamo una funzione che opera correttamente solo in presenza di uno stato esterno indipendente, correttamente configurato a parte. Notate che questo stato esterno dovrebbe essere "solo" una cache messa lì per ottimizzare la performance della funzione: in teoria potrebbe non esserci. Per sua natura una cache è volatile: altri processi potrebbero decidere di svuotarla, o il contenuto potrebbe andar perso in una serializzazione tra due sessioni. Insomma, già è un anti-pattern bello e buono che una funzione possa non funzionare correttamente in base alla configurazione di uno stato esterno; ma che poi questo stato esterno sia proprio una cache, uno degli oggetti per definizione più aleatori, è proprio un pugno nell'occhio.

E sì, certo, lo so: questo codice funziona; nessuno si sogna di serializzare, svuotare o manipolare questa cache. E poi il focus del paragrafo è sulla memoizzazione, c'è davvero bisogno di essere così precisi sul resto?
Ma vedete, questo è proprio un fastidioso modus operandi onnipresente in PdI: mentre spiega una cosa, e magari anche ben(ino), introduce sottili storture e cattive abitudini che magari non c'entrano nel merito ma intanto restano lì, nella testa di chi legge. Nel caso in oggetto, costava davvero tanta fatica scrivere invece questo?

# PdI, esempio dal paragrafo 11.6 - meglio, questa volta
memo = {}

def fibonacci(n):
    if n in memo:
        return memo[n]
    if n < 2: # per brevità uniamo i due test
        res = n
    else:
        res = fibonacci(n-1) + fibonacci(n-2)
    memo[n] = res
    return res

Questa versione non è poi così diversa: la prima volta che n==0 o n==1, il valore finisce comunque nella cache e da quel punto in poi è la cache a gestire anche i casi-limite (if n in memo:...). La differenza è puramente... pedagogica. Intanto la cache non ha più bisogno di essere configurata proprio nel modo giusto. E poi adesso la funzione "basta a se stessa": funziona già di suo. La memoizzazione è una feature in più, ma non pregiudica il corretto funzionamento della funzione. La cache può fare quello che vuole, ma la nostra funzione restituisce sempre il valore corretto, magari solo più lentamente: come appunto dovrebbe essere.

Certo adesso non siamo in grado di apprezzare fino in fondo quanto sia migliore questo modo di impostare il problema. L'attività di memoizzazione è "incastrata" dentro la funzione e non possiamo farci molto. L'ideale sarebbe spostare la gestione della cache in una funzione esterna indipendente dalla nostra fibonacci, e poi applicare questa funzione di memoizzazione alla fibonacci, magari con un elegante decoratore. A questo punto sarebbe ovvia l'utilità di non far dipendere il funzionamento di fibonacci dalla sua cache: la memoizzazione è una feature esterna che può essere applicata oppure no, senza cambiare una riga del codice interno di fibonacci:

def memoizza(funzione):
    # siccome "memoizza" può servire in teoria per diverse funzioni, 
    # non possiamo più usare una cache globale, beninteso!
    memo = {} 
    def controlla(x):
        if x not in memo:
            memo[x] = funzione(x)
        return memo[x]
    return controlla

@memoizza
def fibonacci(n):
    if n < 2: # per brevità uniamo i due test
        return n
    else:
        return fibonacci(n-2) + fibonacci(n-1)

D'accordo, nessuno dice che bisogna arrivare a questo: il lettore di PdI a quel punto non ha ancora queste competenze, e quindi va benissimo anche scrivere fibonacci con la memoizzazione incorporata. A patto di scriverla bene però!, in modo da conservare l'idea giusta di fondo: che la memoizzazione è uno strumento aggiunto per aumentare la performance, ma non deve cambiare in nessun modo il funzionamento interno di fibonacci.


Bonus: forse avete anche storto il naso per il modo di usare la cache memo come variabile globale, a livello del modulo. Niente paura: il paragrafo successivo (11.7) discute proprio questo aspetto... O forse, ripensadoci: p-a-u-r-a! Dopo un paragrafo tutto sommato buono, l'11.7 è invece un paragrafo terribile. Intanto, che ci sta a fare un discorso sulle variabili globali nel capitolo sui dizionari? Ma insomma, qui ci vorrebbe un articolo a parte. Per il momento, un aspetto interessante che purtroppo PdI non menziona è questo: aver scelto di usare come cache un oggetto mutabile globale ha un effetto collaterale positivo, che la cache non viene mai invalidata. Quindi la cache non aiuta solo nelle chiamate ricorsive durante l'esecuzione della funzione, ma anche nelle chiamate tra una funzione e l'altra. Ovvero, se chiamate fibonacci(100) con cache, questo è più veloce della stessa chiamata senza cache. Ma non solo: la seconda volta che chiamate fibonacci(100), il risultato sarà istantaneo perché la cache non si è svuotata nel frattempo. Ecco un caso in cui avere uno stato globale mutabile ha un lato positivo.