16/4/2008 UNICAM - p. 1/21

Fondamenti dell’informatica

Funzioni ricorsive e linguaggi funzionali

Rosario Culmonerosario.culmone@unicam.it

16/4/2008 UNICAM - p. 2/21

Funzioni ricorsive

Metodo di definizione di algoritmi introdotto negli anni ’30 dal logico tedescoKleene

Si basano su un approccio matematico (funzioni e operatori). A differenza deimodelli di calcolo basate su macchine (Turing o RAM), questo modello dicalcolo si basa sulla definizioni di funzioni base e operatori. Come nel casodella MdT si cerca il numero minimo di funzioni e operatori che permettono didefinire qualsiasi funzione calcolabile.

16/4/2008 UNICAM - p. 3/21

Funzioni ricorsive

Hanno ispirato i linguaggi di programmazione funzionali (LISP, ML, ecc).

Mentre il modello di calcolo basato su macchine ha ispirato i linguaggiimperativi (stato e memoria), le funzioni ricorsive hanno ispirati la classe deilinguaggi funzionali. Entrambe le categorie sono Turing-equivalenti (conqualche differenza) ovvero hanno la stessa espressività

Nel seguito faremo sempre riferimento a funzioni con argomenti sui naturali.Useremo la notazione f (n) per indicare la arietà di una funzione ovvero ilnumero dei suoi argomenti. Se n = 0 la funzione f corrisponde ad unacostante. Una funzione che non richiede argomenti può produrre solo esempre un solo valore.

16/4/2008 UNICAM - p. 4/21

Funzione base

Le funzioni primitive sono:▲ Le funzioni zero: le funzioni O(n)(x1, . . . , xn) = 0. Per n = 0 la funzione O()

corrisponde alla costante 0

▲ Il successore: ovvero la funzione S(x) = x + 1

▲ Le funzioni selettive (o identità): ovvero U(n)i (x1, . . . , xn) = xi (n ≥ i ≥ 1)

16/4/2008 UNICAM - p. 5/21

Operatori

Gli operatori sono:▲ Composizione: date le funzioni g

(n)1 , . . . , g

(n)m e la funzione h(m) definiamo la

funzione f (n) : f(x1, . . . , xn) = h(m)(g(n)1 (x1, . . . , xn), . . . , g

(n)m (x1, . . . , xn)).

La composizione è la forma più semplice per ottenere nuove funzioni. Adesempio f(x) = x + 2 può essere ottenuta ponendo h(x) = S(x) eg1(x) = S(x) ovvero f(x) = S(S(x)) = x + 2

▲ Ricursione primitiva: date le funzioni g(n) e h(n+2) definiamo la funzionef (n+1):

f (n+1)(x1, . . . , xn, 0) = g(n)(x1, . . . , xn)

f (n+1)(x1, . . . , xn, y + 1) = h(n+2)(x1, . . . , xn, y, f (n+1)(x1, . . . , xn, y))

Ad esempio la funzione somma può essere definita per ricursione primitiva apartire dalle funzioni U

(1)1 identità ed S successore:

somma(x, 0) = x

somma(x, y + 1) = S(somma(x, y))

16/4/2008 UNICAM - p. 6/21

La classe più semplice

La classe delle funzioni ricorsive primitive è la più piccola classe di funzioni checontiene le funzioni base ed è chiusa rispetto alle operazioni di composizione ericursione primitiva.

16/4/2008 UNICAM - p. 7/21

Esempi di funzioni ricorsive primitive

Sommaprodotto(x, 0) = 0prodotto(x, y + 1) = somma(x, prodotto(x, y))

Esponenzialeexp(x, 0) = 1exp(x, y + 1) = prodotto(x, exp(x, y))

16/4/2008 UNICAM - p. 8/21

Le funzioni ricorsive primitive non bastano

Le funzioni ricorsive primitive non coprono l’insieme delle funzioni calcolabili: lefunzioni base e la composizione e la ricursione primitiva sono totali e quindicomunque possono definire solo funzioni totali quindi:▲ non contengono le funzioni parziali▲ non permettono di definire meccanismi di ricursione più complessi (ad

esempio ricursione doppia)

16/4/2008 UNICAM - p. 9/21

La funzione di Ackermann

La funzione di Ackermann è un esempio di funzione calcolabile ma nonricorsiva primitiva (ricorsione doppia).Consideriamo le seguenti funzioni ricorsive primitive di due argomenti:

f0(x, y) = x + y

f1(x, y) = xy

per n ≥ 2 fn(x, y) =

{

1 se y = 0

fn−1(x, fn(x, y − 1)) altrimenti

Ad esempio:f2(x, 0) = 1 esponenzialef2(x, y + 1) = f1(x, f2(x, y))

f3(x, y + 1) = xxxx

}

y torre o esponenziale generalizzato

16/4/2008 UNICAM - p. 10/21

Esponenziale generalizzato

La funzione di Ackermann cresce velocissima, ad esempio f(3, 4) = 3333}

4

ovvero f(3, 4) = 3135000000

Se consideriamo come un’unica funzione di tre argomenti:

f(n, x, y) = fn(x, y)

otteniamo una funzione che non è ricorsiva primitiva. Chiamiamo funzione diAckermann la funzione A(n) = f(n, n, n) = fn(n, n). Questa funzione si puòdimostrare che non può essere espressa come funzione primitiva ricorsiva

16/4/2008 UNICAM - p. 11/21

Operazione di minimalizzazione

Data una funzione g(n+1) possiamo definire f (n) come il minimo valore di t chesoddisfa il predicato g(x1, . . . , xn, t) = 0 ovverof (n)(x1, . . . , xn) = µt tale che (g(n+1)(x1, . . . , xn, t) = 0)

Il valore t può non esistere (ovvero non esiste un valore che soddisfa ilpredicato) e quindi la funzione diventa parziale (valore indefinito)

Ad esempioPredecessore(x) = µt(S(t) = x) notare che Predecessore(0) è indefinitoInt(x) = µt((t + 1)(t + 1) > x) ovvero la parte intera della radice quadrata di x⌊√x⌋

In questi ultimi casi non abbiamo considerato l’annullamento del predicato (inun caso l’uguaglianza ad un valore e nell’altro caso il >) per semplicità.

16/4/2008 UNICAM - p. 12/21

Proprietà delle funzioni ricorsive

La classe delle funzioni ricorsive è la più piccola classe di funzioni che contienele funzioni base ed è chiusa rispetto alle operazioni di composizione, ricursioneprimitiva e minimalizzazione.

Che relazione vi è tra le le MdT e le funzioni ricorsive. Ogni funzionecalcolabile secondo Turing può essere formulata come:f(x1, . . . , xn) = U(µt(T (x1, . . . , xn, t) = 0))Ovvero qualsiasi funzione calcolabile secondo Turing può essere espressautilizzando una funzione primitiva ricorsiva U , un predicato T e una sola voltal’operatore di minimizzazione. Vale a dire che una computazione qualsiasi puòessere espressa cercando il verificarsi di una proprietà (l’uguaglianza a 0).Quindi il valore finale può essere calcolato estraendolo (mediante ricursioneprimitiva) dal valore minimale t.

16/4/2008 UNICAM - p. 13/21

Formalismo di Mc Carthy

I linguaggi di programmazione funzionali devono la loro origine a vari filoni e inparicolare:▲ funzioni ricorsive▲ lambda-calcolo. Altro modello di calcolo inventato da Church per dimostrare

che l’aritmetica è indecidibile (tutte le formule non possono esseredimostrate vere)

Anello di congiunzione di tutti questi filoni e i veri e propri linguaggi funzionali èil formalismo di Mc Carthy, collegato al più famoso dei linguaggi funzionaliovvero il LISP

16/4/2008 UNICAM - p. 14/21

Schemi di programmi [1]

Il formalismo di Mc Carthy consente di definire la struttura sintattica deiprogrammi, appunto schemi di programmi.

Le diverse interpretazioni dei simboli utilizzati nel formalismo conducono adiversi possibili linguaggi di programmazione.

Simboli disponibiliV insieme contenente infiniti simboli di variabile x0, x1, . . . , y, z . . .

B insieme contenente infiniti simboli di funzione base b0, b1, . . . , a, b, . . .

F insieme contenente infiniti simboli di funzione variabile F0, F1, . . . , G, H, . . .

Sia le funzione base che le funzioni variabile hanno una loro arietà

16/4/2008 UNICAM - p. 15/21

Schemi di programmi [2]

Si indica con Termine su 〈V, B, F 〉▲ un simbolo di variabile è un termine▲ un simbolo di funzione base con arietà 0 (costante) è un temine▲ se t1, . . . , tn sono termini e la arietà di bi è n allora bi(t1, . . . , tn) è un termine▲ se t1, . . . , tn sono termini e la arietà di Fi è n allora Fi(t1, . . . , tn) è un termineNull’altro è un termine

Se un termine non contiene variabili è chiamato termine chiuso (o di base)Dato 〈V, B, F 〉:T (V, B, F ) denota l’insieme dei terminiT0(V, B, F ) denota l’insieme dei termini chiusi

16/4/2008 UNICAM - p. 16/21

Esempi

Se b0, b1, b2 hanno rispettivamente arietà 0, 2, 1 ed F0 ha arietà 2 allorab1(b0, b0) ∈ T0(V, B, T )F0(F0(b0, b2(b0)), b1(b2(b0), b0)) ∈ T0(V, B, F )F0(F0(x, y), b1(b2(x), b0)) ∈ T (V, B, F )

16/4/2008 UNICAM - p. 17/21

Schemi di programmi [3]

Dichiarazioni di schemi di programmi su 〈V, B, F 〉

Uno schema di programma su 〈V, B, F 〉 è una sequenza di dichiarazioniFi ⇐= ti dove Fi ∈ F e ti ∈ T (V, B, F ) seguita da un termine chiusot0 ∈ T0(V, B, F )

Ad esempio:F (x) ⇐= b2(x, b0(x, F (b1(y)))) F (b1(b0))La prima parte è una dichiarazione di una funzione di una variabile. Bisognatenere presente che si tratta si schemi di programmi ovvero solo unarappresentazione sintattica. L’interpretazione associa una semantica allastruttura sintattica.

16/4/2008 UNICAM - p. 18/21

Il linguaggio SLF

Per passare da schemi di programmi a programmi (cioè per passare dalformalismo di Mc Carthy ad un vero e proprio linguaggio di programmazione)dobbiamo interpretare i simboli di V e B. L’interpretazione di F si otterrà diconseguenza

Consideriamo la seguente interpretazione:▲ i simboli di variabile in V si interpreteranno come variabili intere▲ i simboli di funzione base in B si interpreteranno come le seguenti funzioni

sui naturali:● per ogni numero naturale c, infinite funzioni costanti C

(n)c (x1, . . . , xn) = c

di arietà n ≥ 0 che producono il valore intero costante c; per ogni c,anziché scrivere la funzione C

(0)c utilizzeremo il corrispondente naturale c

● S(x) = x + 1 successore di arietà 1● P (x) = x − 1 predecessore di arietà 1● if − then − else(x, y, z) = se x = 0 allora y, altrimenti z condizionale di

arietà 3

16/4/2008 UNICAM - p. 19/21

Semplice Linguaggio Funzinale

Il linguaggio SLF è un linguaggio di programmazione che si ottieneinterpretando nel modo descritto precedentemente gli schemi di programmi delformalismo di Mc Carthy.

Esempio di programma che calcola il fattoriale di 4FACT (y) ⇐= if − then − else(y, 1, PROD(y, FACT (P (y)))) FACT (4)dove PROD è la funzione prodotto che si assume già definita (è stata definitanello stesso modo). La sintassi è quella di Mc Carthy l’interpretazione quelladefinita precedentemente.

16/4/2008 UNICAM - p. 20/21

Calcolabilità in SLF [1]

Vediamo se le funzioni ricorsive sono calcolabili con questo linguaggio diprogrammazione. Per dimostrare ciò utilizzeremo la struttura induttiva.

Le funzioni base sero e successore sono disponibili come funzioni base nelrepertorio del linguaggio SLF.

Le funzioni selettive si possono calcolare con il programmaU

(n)i (x1, . . . , xn) ⇐= xi

La composizione ovvero F definita per composizione della funzione h con lefunzioni g1, . . . , gm si può definire come segue:F (x1, . . . , xn) ⇐= h(g1(x1, . . . , xn), . . . , gm(x1, . . . , xn))

La ricursione primitiva ovvero F definita per ricursione primitiva a partire dallefunzioni g e h si può definire come segue: F (x1, . . . , xn, y) ⇐=if − then − else(y, g(x1, . . . , xn), h(x1, . . . , xn, P (y), F (x1, . . . , xn, P (y))))

16/4/2008 UNICAM - p. 21/21

Calcolabilità in SLF [2]

La minimalizzazione ovvero F definita per minimalizzazione a partire dallafunzione g e può definire come segue:F (x1, . . . , xn) ⇐= G(x1, . . . , xn, 0)G(x1, . . . , xn, t) ⇐= if − the − else(g(x1, . . . , xn, t), t, G(x1, . . . , xn, S(t)))

Se una funzione è definita per minimalizzazione vuol dire che bisogna calcolareil minimo valore di t che annulla un determinato predicato. Allora a partire da 0si calcolano i predicati sino ad avere l’annullamento del predicato, in questocaso è prodotto g(x1, . . . , xn). Si tratta di una applicazione della ricorsione main questo caso la sentinella t non viene decrementata ma incrementata apartire da 0. In questo modo non è certo che il predicato si annullerà è quindi ilcalcolo procede all’infinito realizzando l’indecidibilità (Turing equivalenza).