Paradigmi - funzionale

Question 1

Booleani di church
FALSE

Answer 1

FALSE = fn x => fn y => y

Question 2

Booleani di church
NOT

Answer 2

NOT = fn x => fn y => yx

Question 3

Booleani di church
- cosa sono
- come sono fatti

Answer 3

I booleani di church sono una rappresentazione dei valori booleani e dei costrutti logici elementari utilizzando solo i lambda termini, ossia :
M ::= x | fn x => M | MN
Quindi in altre parole sono i booleani scritti sotto forma di funzioni.

Question 4

Booleani di church
If

Answer 4

IF = fn z a b => z a b;

Question 5

Booleani di church
And

Answer 5

AND = fn xy => x y false

Question 6

Booleani di church
Or

Answer 6

OR = fn xy => x true y

Question 7

Booleani di church
True

Answer 7

TRUE = fn x => fn y => x

Question 8

Numeri di church
- cosa sono
- come sono fatti

Answer 8

I numeri di Church sono una rappresentazione dei numeri naturali come lambda termini, ossia :
M ::= x | fn x => M | MN
In altre parole sono scritti sotto forma di funzioni.
L’idea è quella di rappresentare il naturale i come i applicazioni di un argomento y a una funziona x:
2 = fn xy => x(xy)
In generale quindi:
n-esimo num di church = fn xy => x^n y

Question 9

Numeri di church - successore

Answer 9

fn zxy => x(zxy)
La funziona successore riceve un numero z e restituisce quel numero che applica x a y una volta in più

Question 10

Numeri di church - somma

Answer 10

fn zwxy => z(wxy)
La funziona somma riceve due numeri di church x e w, e restituisce quel numero che applica w volte x a y, e poi viene viene passato a z che applica altre z volte x a y

alternativa: fn zw => z succ w
applico z volte la funzione successore a partire da w

Question 11

Numeri di church - eval (da num di church a numero normale)

Answer 11

fn z => z succ 0
La funzione eval riceve un numero di church in input e restituisce il risultato della funzione successore applicato x volte a 0

Question 12

Numeri di church - moltiplicazione

Answer 12

fn uvx => u(vx)
u e v sono numeri di churhc. viene restituita la funzione che applica u volte la funziona v all’argomento x
alternativa: fn zw => z (plus w) c0
La funzione times riceve due numeri di church in input e restituisce la funzione che applica x volte plus a

Question 13

Numeri di church - lave

Answer 13

fun lave 0 = (fn x => fn y => y)
| lave n = succ( lave(n-1));
(* n=2
succ(succ(0))
0 = fn x => fn y => y
succ(z) = fn x => fn y => x (z x y)
succ(succ(z)) = fn x => fn y => x (succ(z) x y)
succ(succ(z)) = fn x => fn y => x (fn x => fn y => x (z x y) x y
succ(succ(fn x => fn y => y)) = fn x => fn y => x (fn x => fn y => x (fn x => fn y => y (x y)) x y
succ(succ(fn x => fn y => y)) = fn x => fn y => x (x y)

Question 14

Numeri di church - predecessore

Answer 14

S ≡ fn z ⇒ <succ (P2,1 z), P2,1 zi
pred ≡ fn z ⇒ P2,2 (z S hc0, c0i)

Question 15

Numeri di church - fattoriale

Question 16

Numeri di church - zero
val zero = fn x => fn y => y
Qual è il suo tipo

Answer 16

a -> b -> b

Question 17

Numeri di church - uno
val uno = fn x => fn y => x y;
Qual è il suo tipo

Answer 17

(a -> b) -> a -> b

Question 18

Numeri di church - due
val due = fn x => fn y => x (x y);
Qual è il suo tipo

Answer 18

(‘a -> ‘a) -> ‘a -> ‘a

Question 19

Numeri di church - tre
val tre = fn x => fn y => x ( x (x y ));
Qual è il suo tipo

Answer 19

(a -> a) -> a -> a

Question 20

Costrutti logici - TRUE = fn x => fn y => x
Qual è il suo tipo

Answer 20

a -> b -> a

Question 21

Costrutti logici - FALSE = fn x => fn y => y
Qual è il suo tipo

Answer 21

a -> b -> b

Question 22

Costrutti logici - NOT = fn x => fn y => yx
Qual è il suo tipo

Answer 22

b -> (b -> a) -> a

Question 23

Costrutti logici - IF = fn z => fn a => fn b => z a b;
Qual è il suo tipo

Answer 23

(a -> b -> c) -> a -> b -> c

Question 24

Costrutti logici - AND = fn x => fn y => x y false
Qual è il suo tipo

Answer 24

(a -> (b -> c -> c) -> d) -> a -> d
o anche (‘a -> bool -> ‘b) -> ‘a -> ‘b

Question 25

Costrutti logici - OR = fn x => fn y => x true y
Qual è il suo tipo

Answer 25

( (a -> b -> a) -> c -> d) -> c -> d
o anche (bool -> a -> b) -> a -> b

Question 26

Lambda calcolo

[linguaggio+regole+semantica]

Answer 26

Il lambda calcolo è un sistema formale definito dal matematico Alonzo Church nel 1936, sviluppato per analizzare formalmente le funzioni e il loro calcolo.
Le funzioni sono espresse per mezzo di un linguaggio formale, i lambda termini, che stabilisce quali siano le regole per formare un termine:
M ::= x | fn x => M | MN
Il calcolo delle funzioni è espresso con un sistema di riscrittura, che definisce come i termini possano essere ridotti e semplificati.
Utilizziamo una semantica “call-by-value” basata sugli ambienti, le cui regole sono: [var], [fn] ed [appl].
Il sistema lambda introdotto da Church usa normalmente una semantica call-by-name

Question 27

Lambda calcolo

regole

Answer 27

Var
fn
appl

Question 28

Cosa cambia tra lambda calcolo e fun

Answer 28

Il lambda calcolo fa a meno delle costanti k, della somma M+N, del let.
Fun e lambda calcolo sono tuttavia equivalenti in quanto:
- le costanti le possiamo rappresentare come numeri di church, ossia possiamo rappresentare numeri tramite funzioni
- la somma si può scivere tramite funzioni e applicarla ai numeri di church
- [let] E|- let x => M in N –> v lo scriviamo come E |- (fn x => N) M –> v

Question 29

Quali linguaggi abbiamo studiato

Answer 29

Nell’ambito dei paradigmi funzionali abbiamo studiato exp, fun, lambda calcolo, mentre per il paradigma imperativo abbiamo studiato imp e all.
Exp è il linguaggio minimo per studiare la nozione di variabiledi un linguaggio funzionale, come SML, haskell e LISP.
Fun aggiunge ad exp il ocncetto di funzione, ovvero l’astrazione di un termine rispetto a una variabile.
Questi linguaggi astratti ci consentono di studiare il concetto di scoping statico delle variabili, tipico di lingugagi come SML e haskell, e quello dinamico, che viene implementato in parte da LISP o S.
Ci consentono inoltre di studiare le due tipologia di valutazione eager (usata da SML e LISP) e lazy (usata da haskell e S)
schema
Lambda calcolo è invece un linguaggio funzionale equipotente a fun, ma con una sintassi più ristretta: manca delle costanti, della somma e del let, che riesce a rappresentare però tramite funzioni.
Imp è un linguaggio con if-then-else, while, dichiarazione di variabili e assegnamento di un valore a una variabile già dichiarata. In Imp viene introdotto la nozione di locazione, un’astrazione di un indrizzo di memoria).
All (algol-like-language) arricchisce Imp di procedure ed array.

Question 30

Exp

breve presentazione

Answer 30

Exp è il linguaggio minimo per studiare la nozione di variabile, ossia l’astrazione di un valore, di un linguaggio funzionale, come SML, haskell e LISP.
In exp non si assegna un valore a una variabile, ma è più un concetto di “segnaposto” per un termine (ossia si sostituisce la variabile con un intero termine, invece di assegnarle un valore).

Question 31

Exp

Sintassi

Answer 31

k è una generica costante
x è una generica metavariabile
M è un generico termine di exp
Exp è definito induttivamente nel seguente modo:
k ::= 5 | 40 | . . .
M ::= k | x | M + N | let x = M in N
Il let è un operatore di sintassi astratta con segnatura:
let: var x exp x exp –> exp
intuitivamente rappresenta un pezzo di programmma che assegna localmente alla variabile x il valore risultante dal termine M e un corpo N, che può contenere la variabile x.

Question 32

Semantica operazionale - Exp

la relazione –>

Answer 32

La semantica di exp viene presentata nello stile operazionale, usando la nozione di ambiente.
La semantica operazionale di Exp è una relazione
–> ⊆ Env × Exp × Val.
Un’asserzione di appartenenza (E, M, v) ∈ –> viene chiamata giudizio operazionale e si scrive: E |- M –> v. Questa relazione è definita dal seguente insieme di regole: const, var, plus, let.

Question 33

Exp

Regole - const

Answer 33

E |- k –> k

Question 34

Exp

Regole - var

Answer 34

E|- x –> v
(se E(x) = v)

Question 35

Exp

Regole - plus

Answer 35

plus

Question 36

Exp

Regole - plus

Answer 36

let

Question 37

Quando una variabile si dice libera?

Answer 37

Si dice che una occorrenza di una variabile x è libera in un termine t quando non compare nel corpo N di nessun sottotermine di t della forma let x = M in N.
Ogni occorrenza libera di x in un termine N si dice legata (bound ) alla dichiarazione di x nel termine let x = M in N.
Lo scope di tale dichiarazione è l’insieme delle occorrenze libere di x in N.
Con scope di una variabile si intende la porzione di programma all’interno della quale una variabile può essere riferita.

Question 38

Cos’è lo scope di una variabile?

Answer 38

Con scope di una variabile si intende la porzione di programma all’interno della quale una variabile può essere riferita.
Per esempio, all’interno di un termine let x=M in N, lo scope della dichiarazione di x è l’insieme delle occorrenze libere di x in N.

Question 39

due espressioni si dicono alfa-equivalenti?

Answer 39

Due espressioni si dicono alfa-equivalenti se sono identiche a meno di ridenominazione di variabili legate. Ad esempio: l’espressione let x = 1 in x + 1è alfa-equivalente a let y = 1 in y+1

Question 40

ambiente

Answer 40

Un ambiente è una funzione parziale che associa dei valori a un insieme finito di variabili:
Env = var –fin–> val
L’insieme Val dei “valori”, ovvero l’insieme dei
possibili risultati della valutazione di un termine, coincide con l’insieme delle costanti.
Per esempio, l’ambiente E in cui z vale 3 ed y vale 9 è indicato con {(z,3),(y,9)}.

Question 41

equivalenza operazionale

Answer 41

Definiamo operazionalmente equivalenti due programmi M ed N tali che, per ogni ambiente E e valore v, E |- M –> v se e solo se E |- N –> v. L’equivalenza operazionale, che indichiamo con
M ∼ N, è chiaramente una relazione di equivalenza tra programmi.

Question 42

Valutazione Lazy

Answer 42

La valutazione lazy (pigra) è usata in Haskell e in S.
Questa valutazione consiste nel calcolarsi il risultato di un programma solo se quel risultato effettivamente ci serve, e non quindi “a priori”. Ci sono casi in cui effettivamente si risparmia tempo, come ad esempio:
let x = M in 1
M potrebbe essere un espressione molto complicata e potremmo metterci tanto tempo a risolverla, usando un approccio lazy, si risparmierebbe questo tempo dato che x non viene mai utilizzato.
Questa valutazione ci obbliga a cambiare la nozione di ambiente, che ora associa variabili a espressioni e non a valori.

Question 43

Come cambia l’ambiente (e le regole) con la valutazione lazy

exp

Answer 43

Con la valutazione lazy adattiamo la nozione di ambiente, che ora associa variabili a espressioni e non più a valori.
Env-lazy = Var –fin–> Exp
regole nuove

Question 44

si risparmia sempre tempo di calcolo con lazy?

Answer 44

No non sempre, perchè lazy ci permette sì di calcolarci un’espressione quando e se ce n’è effettivamente bisogno, ma ci obbliga a ricalcolarla a ogni occorrenza della variabile associata all’espressione.
Per esempio, nella seguente espression con lazy N si calcola 3 volte, con eager 1 sola:
let x = N in (x + x + x)

Question 45

Esempio termine diverso con scoping statico o dinamico

Answer 45

let x = 2 in (let y = x in (let x = 3 in y + 1))
lazy statico viene 3
lazy dinamico viene 4

Question 46

Eager e lazy sono equivalenti? (Esempio in cui non lo sono)

Answer 46

No non sono equivalenti, per dare un esempio in cui la valutazione usata cambia il risultato:
let x = 2 in (let y = x in (let x = 3 in y + 1))
Lazy: associamo in Env x a M (che non sappiamo ancora valere 2), poi y a x (importante questo punto, non associamo y al valore di x, ossia 2, ma la generica variabile x), poi associamo x a 3 e eseguiamo il corpo N y+1 nell’ambiente {(x,M),(y,x),(x,M’)} con M–>2 e M’–>3. y è associato a x, andando a cercare nell’ambiente x, troviamo che è associato a M’, che calcolato restituisce il valore 3. y+1 fa quindi 4.
Eager: associamo a x il valore 2, poi alla variabile y il valore di x, ossia 2, poi alla variabile x il valore 3. L’env è {(x,2),(y,2),(x,3)}. il corpo N restituisce il valore 3.
Quindi il risultato cambia quando usiamo variabili non associate a valori costanti, ma associate ad altre variabili, che possono cambiare valore a seconda del punto in cui siamo nel programma (y avrà valore diverso a seconda di quando lo usiamo).

Question 47

Valutazione Eager

Answer 47

La valutazione Eager (avida) è adottata in SML e LISP. Con eager, al momento della dichiarazione di una variabile x:=M, si associa nell’ambiente x al valore risultante dall’espressione M, che viene valutato subito.

Question 48

Scoping di un linguaggio

Answer 48

Lo scoping di un linguaggio è quell’insieme di regole che determinano la visibilità di una variabile all’interno di un programma, che consentono cioè di associare una variabile a ciascun riferimento (ovvero uso della variabile mediante un identificatore).
Può essere statico o dinamico.
In modo intuitivo: col dinamico, quando si entra dentro una funzione che utilizza una variabile omonima a una fuori la funzione, le modifiche fatte alla variabile nascono e muiono in quella funzione.
Uno stesso linguaggio può adottare regole di scoping diverse per entità di tipo diverso. In Java, per esempio, il riferimento ad un campo di un oggetto (ovvero la variabile a cui punta il riferimento) viene risolto staticamente, mentre il riferimento ad un metodo viene risolto dinamicamente.

Question 49

let x = x in x

che risultato produce in sml?

Answer 49

let val x = x in x end;
stdIn:1.14 Error: unbound variable or constructor: x

Question 50

Scoping statico

Answer 50

Nello scoping statico i riferimenti ad una variabile sono risolti in base alla struttura sintattica del programma.
Può essere effettuata dal compilatore, scegliendo il più recente legame attivo elaborato a tempo di compilazione

Question 51

Scoping dinamico

Answer 51

Nello scoping dinamico i riferimenti sono risolti in base allo stato di esecuzione del programma, per esempio: una dichiarazione estende il suo effetto fino a che non si incontra un’altra dichiarazione di variabile con lo stesso nome.

Question 52

Come si modifica l’ambiente con lo scoping statico

exp

Answer 52

L’ambiente con scoping dinamico associa variabili a espressioni M (lazy). Con lo scoping statico associa alla variabile x sia l’espressione M, sia l’ambiente che c’è al momento della dichiarazione di x. Questo rende il valore di M indipendente dal momento in cui si valuta (l’ambiente non cambia, l’abbiamo salvato).
Env-lazy statico = Var –fin–> (Exp × EnvLS).

Question 53

come si modificano le regole di exp con lazy statico

Answer 53

regole

Question 54

Fun

breve presentazione

Answer 54

Il linguaggio Fun estende Exp con la nozione di funzione. Dato un termine t con una variabile libera x è possibile costruire, per astrazione su x, la funzione φ che, dato un valore v per x, restituisce il risultato della valutazione di [v/x]t.
In Fun φ si esprime come fn x ⇒ t; in questo termine la variabile x rappresenta il valore d’ingresso della funzione, e prende il nome di parametro

Question 55

Fun

sintassi

Answer 55

k ::= 5 | 40 | . . .
M ::= k | x | M + N | let x = M in N | fn x ⇒ M | M N
L’operatore di sintassi astratta fn ha segnatura:
fn : Var × Fun → Fun
L’insieme Val dei valori non coincide più con l’insieme delle costanti. è necessario infatti introdurre un nuovo tipo di valore per rappresentare funzioni. Un tale valore, che chiamiamo chiusura, ha la forma (x, M, E), dove x è una variabile, M è un termine ed E è un ambiente, e rappresenta la funzione che mappa un valore v nel risultato della valutazione di M nell’ambiente E {(x, v)}.
Val = {5, 40, . . . } ∪ (Var × Fun × Env)

Question 56

Fun

regole (eager scoping statico)

Answer 56

fn
appl
più le regole ereditate da exp:
const E|- k –> k
var E |- x –> k se E(x,E’)=v
let
plus

Question 57

fun eager dinamico come cambiano le regole

rispetto a statico

Answer 57

appl

Question 58

let x = 7 in ((fn y ⇒ (let x = 3 in y 9)) (fn z ⇒ x))
valutarlo con scoping dinamico e statico

Cosa cambia?

Answer 58

La differenza tra i due si vede nell’applicazione della funzione fn=>x (sostituita a y) all’argomento 9. Quindi y9 torna x. A cosa è associato x? nello scoping dinamico a 3, mentre nello statico ci andiamo a salvare l’ambiente di quando abbiamo dichiarato la funzione (fn=>x), in cui x valeva 7.
quindi statico torna 7, dinamico torna 3.

Question 59

Termine fun che cambia da statico a dinamico

Dare un esempio

Answer 59

let x = 7 in ((fn y ⇒ (let x = 3 in y 9)) (fn z ⇒ x))

Question 60

Termine fun in cui lazy cambia da eager

dare un esempio

Answer 60

(fn x ⇒ x x) (fn x ⇒ x x)

Question 61

sml statico o dinamico? lazy o eager? come provarlo?

Answer 61

Sml è eager,statico.
(* sml è statico )
let val x = 3 in ( let val y = x in (let val x = 5 in y end) end) end;
val it = 3 : int
( ricorsione )
fun bomba x = bomba(x-1);
( sml è eager *)
(fn x => 6) (bomba 5);
uncaught exception Overflow [overflow]

Question 62

C’è differenza tra lazy statico ed eager statico in exp?

Answer 62

No non c’è differenza. La reale differenza tra lazy e eager è una questione di gestione di ambienti:
in lazy si associa a una variabile x un espressione, che si valuterà al momento della valutazione di un termine che contiene x, a differenza di eager che associa a una variabile x un valore, calcolato al momento della dichiarazione di x.
Quindi per rendere lazy equivalente a eager modifichiamo Env: ora associa alla variabile x sia l’espressione M, sia l’ambiente che c’è al momento della dichiarazione di x. Questo rende il valore di M indipendente dal momento in cui si valuta (l’ambiente non cambia, l’abbiamo salvato).
La valutazione Lazy che associa variabili a una coppia espressione-ambiente, si dice che ha scoping statico
Env-lazy statico = Var –fin–> (Exp × EnvLS).

Question 63

C’è differenza tra lazy statico ed eager statico in fun?

esempio?

Answer 63

Cambia nella derivazione della regola [appl]
E |- MN –> v
con lazy statico non ci calcoliamo subito N, ma lo salviamo nell’ambiente, associandolo all’argomento della funzione.