Esercizio

Programmazione Funzionale
Davide Mottin - Themis Palpanas
February 26, 2014
1/13
Contatti
I
email : [email protected]
I
sito del corso :
http://disi.unitn.it/~mottin/index.php?pid=7
2/13
Introduzione
Storia
Il lambda-calcolo
Sintassi
Semantica
Regole
Sommario
3/13
Figure: Alan Turing (left) - Alonzo Church(right)
Introduzione
4/13
Tesi di Church-Turing
Se un problema `e intuitivamente calcolabile, allora esister`a una
macchina di Turing (o un dispositivo equivalente, come il
computer) in grado di risolverlo (cio`e di calcolarlo)
Introduzione
5/13
Cos’`e il lambda-calcolo
Il lambda-calcolo `e il pi`
u semplice linguaggio con il quale possiamo
calcolare qualsiasi problema. Ha delle ottime propriet`a
` Turing completo
I E
I
I
I
` il fondamento dei linguaggi funzionali
E
` semplice perch´e possiede un set molto ridotto di istruzioni
E
Tutto `e definibile attraverso funzioni e applicazioni di esse
(lambda-calcolo puro)
Il lambda-calcolo
6/13
Sintassi
Nel lambda calcolo ci sono due operazioni: astrazione e
applicazione. La sintassi `e la seguente
e ::= x | λx.e | e e | c
dove un’esperessione e pu`
o essere
I
x: una variabile
I
λx.e: una funzione che riceve in input un parametro x e
valuta l’espressione e
I
e e: applicazione di due espressioni,
I
c: una costante.
Il lambda-calcolo
7/13
Sintassi
Nel lambda-calcolo ci sono due primitive sintattiche:
I
astrazione di un termine rispetto ad una variabile x: λx.t
”La funzione che, quando applicata ad un valore v , produce t
in cui v rimpiazza x.”
I
applicazione di una funzione ad un argomento: t1 t2
”la funzione t1 applicata all’argomento t2 ”
Il lambda-calcolo
8/13
Applicazione di funzioni nel lambda calcolo
Applicare una funzione significa ridurre un’espressione a un
VALORE
Un valore `e un’espressione non ulteriormente riducibile
Un passo di riduzione: (λx.N)M 7→ N[M/x]
N[M/x] significa sostituire tutte le occorrenze di x in N con M.
e.g. (λx.x 2 ) 2 7→ x 2 [2/x] 7→ 4
L’applicazione `e associativa a sinistra ossia
M N L ≡ (M N) L
Il lambda-calcolo
9/13
Esercizio
Mostrare la riduzione della seguente espressione
(λx.λy .(add x ((λx.(sub x 3)) y ))) 5 6
Il lambda-calcolo
10/13
Esercizio
Mostrare la riduzione della seguente espressione
(λx.λy .(add x ((λx.(sub x 3)) y ))) 5 6
Soluzione
7→ λx.λy .(add x ((λx.(x − 3)) y ))) 5 6
7→ λx.λy .(add x (y − 3)) 5 6
7→ λx.λy .(x + (y − 3)) 5 6
7→ λy .(5 + (y − 3)) 6
7→ (5 + (6 − 3))
7→ (5 + 3)
7→ 8
Il lambda-calcolo
10/13
Altri esercizi
Ridurre ai minimi termini le seguenti espressioni
1. (λx.x(xy ))(λz.zx)
2. (λx.xy )(λz.zx)(λz.zx)
3. (λt.tx)((λz.xz)(xz))
Il lambda-calcolo
11/13
Altri esercizi
Ridurre ai minimi termini le seguenti espressioni
1. (λx.x(xy ))(λz.zx)
Soluzione 1
7→ (λz.zx)((λz.zx)y ) 7→ (λz.zx)(yx) 7→ (yx)x
2. (λx.xy )(λz.zx)(λz.zx)
3. (λt.tx)((λz.xz)(xz))
Il lambda-calcolo
11/13
Altri esercizi
Ridurre ai minimi termini le seguenti espressioni
1. (λx.x(xy ))(λz.zx)
Soluzione 1
7→ (λz.zx)((λz.zx)y ) 7→ (λz.zx)(yx) 7→ (yx)x
2. (λx.xy )(λz.zx)(λz.zx)
Soluzione 2
7→ ((λz.zx)y )(λz.zx) 7→ yx(λz.zx)
3. (λt.tx)((λz.xz)(xz))
Il lambda-calcolo
11/13
Altri esercizi
Ridurre ai minimi termini le seguenti espressioni
1. (λx.x(xy ))(λz.zx)
Soluzione 1
7→ (λz.zx)((λz.zx)y ) 7→ (λz.zx)(yx) 7→ (yx)x
2. (λx.xy )(λz.zx)(λz.zx)
Soluzione 2
7→ ((λz.zx)y )(λz.zx) 7→ yx(λz.zx)
3. (λt.tx)((λz.xz)(xz))
Soluzione 3
7→ (λt.tx)(x(xz)) 7→ x(xz)x
Il lambda-calcolo
11/13
Altri esercizi - 2
Ridurre ai minimi termini le seguenti espressioni (tratte da esami
dell’anno scorso)
1. (λx.yx)((λy .λt.yt)zx)
2. (λx.xzx)((λy .yyx)z)
3. (λx.xy )(λt.tz)((λx.λz.xyz)yx)
Il lambda-calcolo
12/13
Altri esercizi - 2
Ridurre ai minimi termini le seguenti espressioni (tratte da esami
dell’anno scorso)
1. (λx.yx)((λy .λt.yt)zx)
Soluzione 1
7→ (λx.yx)((λt.zt)x) 7→ (λx.yx)(zx) 7→ y (zx)
2. (λx.xzx)((λy .yyx)z)
3. (λx.xy )(λt.tz)((λx.λz.xyz)yx)
Il lambda-calcolo
12/13
Altri esercizi - 2
Ridurre ai minimi termini le seguenti espressioni (tratte da esami
dell’anno scorso)
1. (λx.yx)((λy .λt.yt)zx)
Soluzione 1
7→ (λx.yx)((λt.zt)x) 7→ (λx.yx)(zx) 7→ y (zx)
2. (λx.xzx)((λy .yyx)z)
Soluzione 2
7→ (λx.xzx)(zzx) 7→ (zzx)z(zzx)
3. (λx.xy )(λt.tz)((λx.λz.xyz)yx)
Il lambda-calcolo
12/13
Altri esercizi - 2
Ridurre ai minimi termini le seguenti espressioni (tratte da esami
dell’anno scorso)
1. (λx.yx)((λy .λt.yt)zx)
Soluzione 1
7→ (λx.yx)((λt.zt)x) 7→ (λx.yx)(zx) 7→ y (zx)
2. (λx.xzx)((λy .yyx)z)
Soluzione 2
7→ (λx.xzx)(zzx) 7→ (zzx)z(zzx)
3. (λx.xy )(λt.tz)((λx.λz.xyz)yx)
Soluzione 3
7 (λx.xy )(λt.tz)((λz.yyz)x) 7→ (λx.xy )(λt.tz)(yyx) 7→
→
(λt.tz)y (yyx) 7→ yz(yyx)
Il lambda-calcolo
12/13
Le regole del lambda-calcolo
1. Associativit`a a sinistra : M N L ≡ (M N) L
2. Lo scope dell’astrazione si estende pi`
u a destra possibile:
λx.xyz ≡ λx.(xyz)
3. Rispettare la precedenza delle parentesi, ove esplicitate
4. La precedenza nelle riduzioni va data all’applicazione pi`
ua
sinistra e pi`
u interna: ((λx.x)x)(λx.xy ) 7→ x(λx.xy ), mentre
`
la riduzione ((λx.x)x)(λx.xy ) 7→ (λx.xy )x NON E
CORRETTA
5. Attenzione alla cattura di variabile, se una variabile passa da
libera a vincolata si sta facendo un grave errore : es.
(λy .(λx.yx))x 9 (λx.xx) perch´e la variabile libera y `e
diventata vincolata dopo l’applicazione. La Soluzione `e
rinominare la x vincolata con un nome diverso da y , per
esempio t: (λy .(λt.yt))x, in questo modo non si incorre pi`
u
in cattura di variabili.
Il lambda-calcolo
13/13

Download Report