Procedure e processi

Una procedura definisce uno "schema" di evoluzione locale di un processo computazionale. La procedura specifica in ogni fase del processo, come il processo stesso viene eseguito a partire dalla fase precedente. È interessante studiare il comportamento globale di un processo la cui evoluzione locale è stata specificata da una procedura. In generale, andare a studiare questo comportamento è molto complicato, ma in alcuni casi semplici si possono identificare degli schemi ricorrenti (in inglese pattern).

Proviamo ora a studiare la "forma" che prendono alcuni processi generati da procedure molto semplici. Studieremo anche velocemente la velocità con cui questi processi consumano le due risorse di calcolo fondamentali:

IL TEMPO
LA MEMORIA

Come nelle lezioni precedenti, le procedure che consideriamo sono molto semplici. Il loro ruolo è lo stesso ricoperto dai test patterns in fotografia: uno schema prototipale ipersemplificato, piuttosto che un caso d'uso reale.

Ricorsione lineare e iterazione lineare

Si consideri la funzione fattoriale definita come segue: si definisce il fattoriale di un numero naturale $n$, indicato con $n!$, il prodotto dei numeri naturali uguali o minori a $n$, ovvero:

$$n! = \prod_{k=1}^n k = 1 \cdot 2 \cdot 3 \cdot \cdot \cdot (n-2) \cdot (n-1) \cdot n$$

Esistono molti modi di calcolare il fattoriale di un numero naturale. Un modo è di osservare che $n!$ è uguale ad $n$ volte $(n-1)!$ per qualsiasi intero $n$:

$$ n! = n \cdot [(n-1)\cdot(n-2)\cdots 3 \cdot 2 \cdot 1] = n \cdot (n-1)!$$

In questo modo possiamo calcolare $n!$ calcolando prima $(n-1)!$ e moltiplicando poi il risultato per $n$. Se aggiungiamo la definizione che $1!$ è uguale a 1, possiamo definire la procedura seguente:



In [1]:

    
def Fattoriale(n):
    if n == 1:
        return 1
    else:
        return n * Fattoriale(n-1)



In [2]:

    
Fattoriale(5)









    Out[2]:





120

Se usiamo il substitution model per valutare la procedure per $5!$, otteniamo lo schema seguente:

Fattoriale(5)
5 * Fattoriale(4)
5 * (4 * Fattoriale(3))
5 * (4 * (3 * Fattoriale(2)))
5 * (4 * (3 * (2 * Fattoriale(1))))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2)) 
5 * (4 * 6) 
5 * 24
120

Ora, questa procedura è corretta, in quanto produce il risultato richiesto (si può dimostrare formalmente la correttezza, ma non è lo scopo di questa capitolo).

Possiamo tuttavia calcolare il fattoriale di un numero usando un approccio diverso. Potremmo descrivere una regola per calcolare il fattoriale di un numero naturale $n$ specificando che prima moltiplichiamo 1 per 2, poi moltiplichiamo il risultato per 3, poi il risultato per 4, e cosi via, sino a raggiungere il valore di $n$.

Più formalmente, manteniamo una variabile per il prodotto corrente (chiamata in gergo un accumulator), insieme a una variabile che "tiene il conto" da 1 a $n$ (un counter). Possiamo descrivere il processo di calcolo dicendo che l'accumulator e il counter aggiornano il loro stato "contemporaneamente" ad ogni fase del processo di calcolo:

accumulator <- counter * accumulator
counter <- counter + 1

Chiaramente, sia l'accumulator che il counter sono inizializzati a 1.

Data questa regola per calcolare $n!$, possiamo scrivere le due procedure seguenti:



In [3]:

    
def FactorialIter(accumulator, counter, n):
    if counter > n:
        return accumulator
    else:
        return FactorialIter(counter*accumulator, counter+1, n)
    
def FactorialI(n):
    return FactorialIter(1, 1, n)



In [4]:

    
FactorialI(5)









    Out[4]:





120

Come prima, se usiamo il substitution model possiamo visualizzare il processo di calcolare $5!$ usando la procedura FactorialI, come segue:

FactorialI(5)
FactorialIter(1, 1, 5)
FactorialIter(1, 2, 5)
FactorialIter(2, 3, 5)
FactorialIter(6, 4, 5)
FactorialIter(24, 5, 5)
FactorialIter(120, 6, 5)
120

Si provi a confrontare questo schema di calcolo rispetto al precedente.

A prima vista non sembrano troppo diversi: entrambi calcolano $5!$. Entrambe le procedure richiedono un numero di passi proporzionale al numero $n$. Entrambe le procedure eseguono la stessa sequenza di prodotti, ottenendo gli stessi prodotti parziali. Tuttavia, visualizzando l'evoluzione del processo di calcolo, otteniamo chiaramente una "forma" diversa per i due processi.

Si consideri il primo processo. Procedendo con il modello sostitutivo, otteniamo prima una sequenza di espansioni, seguita da una sequenza di contrazioni. Le espansioni si ottengono mentre il processo costruisce una sequenza di operazioni deferred (in questo caso la sequenza di moltiplicazioni). Le contrazioni avvengono quando le operazioni deferred sono effettivamente calcolate.

Questo tipo di processo, caratterizzato da una sequenza di operazioni deffered, viene chiamato PROCESSO RICORSIVO.

Questo processo richiede che l'interprete tenga memoria delle operazioni che deve eseguire dopo, durante la sequenza di contrazioni. Nel caso del calcolo di $n!$, la lunghezza della sequenza di operazioni deferred, e quindi la quantità di informazioni da mantenere in memoria, è lineare nell'input $n$. Si parla quindi di PROCESSO RICORSIVO LINEARE.

Al contrario, il secondo processo, quello della procedura FactorialI(n) non si espande e non si contrae. Ad ogni passo, gli unici valori di cui dobbiamo tener traccia sono le tre variabili accumulator, counter, e n. Questo viene chiamato un PROCESSO ITERATIVO. In generale, un processo iterativo può essere descritto da un numero finito di variabili di stato, insieme con una regola che descrive come le variabili di stato dovrebbero essere aggiornate quando il processo passo da uno stato all'altro, e dovrebbe avere un test d'arresto (i.e., un predicato condizionale if) che specifica sotto quali condizioni il processo dovrebbe terminare. Nel calcolare $n!$, il numero di passo richiesto cresce linearmente con $n$. Tale processo viene chiamato un PROCESSO ITERATIVO LINEARE (in inglese vengono chiamate funzioni tail-recursive).

IMPORTANTE

Nel confrontare i due tipi di processi, si deve fare attenzione a non confondere il concetto di processo ricorsivo con quello di procedura ricorsiva.

Quando descriviamo una procedura come ricorsiva, ci stiamo riferendo al fatto di definire una funzione che richiama se stessa.

Tuttavia, quando descriviamo un processo che segue uno schema linearmente ricorsivo, stiamo parlando di come il processo evolve, non della sintassi che viene usata per scrivere la procedura. Può creare confusione il dire che una procedura ricorsiva, come ad esempio FactorialI(n), genera un processo iterativo. In ogni caso il processo è iterativo: il suo stato è descritto completamente dalle sue tre variabili di stato, e l'interprete deve tener traccia solo di quelle tre variabili per poter eseguire il processo.

Il motivo principale che genera questa confusione, è che l'implementazione attuale di molti di linguaggi di programmazione comuni (C, Java, e lo stesso Python) sono implementati in modo tale che l'esecuzione di ogni chiamata ricorsiva consuma una quantità di memoria che cresce linearmente con il numero di chiamate ricorsive alla stessa procedura, anche se il processo stesso è iterativo. L'implementazione di altri linguaggi di programmazione (per esempio, il LISP e Haskell) è in grado di distinguere i processi ricorsivi e i processi iterativi, che risultano in grado di ottimizzare il processo di calcolo usando una quantità di memoria che dipende solo dal numero di variabili di stato.

Ricorsione ad albero

Un altro schema ricorrente di calcolo è la ricorsione ad albero. Si consideri per esempio la successione dei numeri di Fibonacci, in cui ogni numero è la somma dei due numeri precedenti:

$$0, 1, 1, 2, 3, 5, 8, 13, 21, ...$$

In generale, l'ennessimo numero di Fibonacci può essere definito dalla regola seguente:

$$Fib(n) = \left\{ \begin{array}{ll} 0 & \mbox{if } n = 0 \\ 1 & \mbox{if } n = 1 \\ Fib(n-1) + Fib(n-2) & \mbox{altrimenti} \end{array} \right.$$

ESERCIZIO 4.1: Tradurre questa definizione in una procedura ricorsiva per calcolare l'ennesimo numero di Fibonacci.



In [5]:

    
# COMPLETARE
def Fib(n):
    if n <= 1:
        return n
    else:
        return Fib(n-1) + Fib(n-2)



In [6]:

    
print(Fib(6))

Si consideri lo schema di calcolo di tale funzione (FARE ALLA LAVAGNA). Si noti che il processo stesso evolve come un albero: ad ogni nodo il processo di ramifica in due sottoprocessi, tranne che ai nodi foglia. Questo è dovuto al fatto che la procedura chiama se stessa due volte per ogni invocazione.

Questa procedura per calcolare i numeri di Fibonacci è un ottimo esempio di struttura ad albero, ma è un pessimo modo di calcolare i numeri di Fibonacci. Per rendersi conto di quanto sia inefficiente, si consideri che questo processo usa un numero di passi che cresce esponenzialmente con l'input. Tuttavia, lo spazio richiesto cresce solo linearmente con l'input, in quanto dobbiamo tener traccia dei nodi al di sotto del nodo corrente a qualsiasi momento del processo. In generale, il numero di passi richiesto da un processo ricorsivo ad albero sarà proporzionale al numero di nodi dell'albero, mentre lo spazio richiesto sarà proporzionale alla profondità massima dell'albero.

Il calcolo dei numeri di Fibonacci può essere formulato anche come un processo iterativo. L'idea è di usare una coppia di numeri $a$ e $b$, inizializzati con $Fib(1)=1$ e $Fib(0)=0$, e di applicare ripetutamente le trasformazioni simultanee:

a <- a + b
b <- a

Non dovrebbe essere complicato realizzare che dopo aver applicato queste trasformazioni $n$ volte, $a$ e $b$ avranno i valori $Fib(n+1)$ e $Fib(n)$.

ESERCIZIO 4.2: Scrivere una procedura che calcoli i numeri di Fibonacci usando un processo iterativo.



In [7]:

    
# DA COMPLETARE