A.A. 2001-02

Linguaggi di Programmazione I: Paradigmi

1^{o} “esonero”

data di assegnazione: 24 ottobre 2001 data di consegna: 26 ottobre 2001 - ore 14:00

Lambda

Considerare il seguente linguaggio Lambda:

M ::= x | fn x ⇒ M | M N

Lambda è un sottolinguaggio (assai potente^{1}) del linguaggio Fun visto a lezione. Indicando rispettivamente con ⇝_{ES} e ⇝_{LS} la semantica eager (scoping statico) e la semantica lazy (scoping statico) di Lambda, dimostrare che ⇝_{ES} è equivalente a ⇝_{LS}, oppure dimostrare il contrario fornendo un controesempio.

Suggerimenti. Notate che in Lambda si può scrivere un termine come:

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

Provate a valutarlo!

Buon lavoro!

1 Lambda è Turing-completo. Mancano i booleani? Ok, ma si possono codificare, per esempio stipulando che il termine fn x ⇒ (fn y ⇒ x) corrisponda a true, mentre fn x ⇒ (fn y ⇒ y) corrisponda a false. Per la lode: quale termine fn x ⇒ (fn y ⇒ (fn z ⇒ M)) corrisponde a if x then y else z?