A.A. 2002-03

Linguaggi di Programmazione I: Paradigmi

primo “esonero”

data di assegnazione: 27 marzo 2003 data di consegna: 4 aprile 2003

Numeri di Church^{1}

Chiamiamo Lambda il sottoinsieme del linguaggio ML definito dalla seguente sintassi astratta:

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

dove M ed N indicano generici termini del linguaggio. Conveniamo di indicare con M^{n}N il termine M(M(… (M N) …)), in cui M è ripetuto n volte. In particolare M^{0}N è N. Sia ϕ : N → Lambda la funzione di codifica dei numeri naturali nel linguaggio Lambda così definita:

ϕ(n) = fn x ⇒ (fn y ⇒ x^{n}y).

Infine, sia ⊕ : Lambda × Lambda → Lambda la seguente operazione binaria su Lambda:

M ⊕ N = fn x ⇒ (fn y ⇒ ((M x) ((N x) y))).

Scrivere in ML una funzione F tale che

– F (ϕ(n)) = n, ed inoltre

– F (ϕ(m) ⊕ ϕ(n)) = m + n.

Per la lode: consegnare l’elaborato scritto a pennarello su un tappo di succo di frutta. Buon lavoro!

1 Si consiglia la lettura del capitolo 5 delle dispense.