Option Compilation
TD mardi 26 avril
Compilation de langages fonctionnels en combinateurs
Après une la réduction qui correspond à la
définition
S f g x = (f x)(g x), quelles sont
les possibilités pour le
sommet du graphe où il faudra effectuer la prochaine
réduction
(par rapport à la racine du sous-arbre représentant le
(f x)(g x)?
Traduire les expressions de combinateurs en expressions-l traditionnelles.
(KS)(KSS)
KI
KSKSS
S(S(KI)(KK))(S(KK)(SII))
Traduire les expressions en combinateurs.
lf. lx.
f (f x)
lf. ( lx.
f(x x))( lx. f(x x))
la. lb.
lc. (c a)(b a)
Le combinateur paradoxal Y
Y = (l h. (l x. h(x x)) (l x. h(x x)))
Vérifiez que (si H est d'un type tel que Y H
existe)
Y H = H(Y H)
Quel doit être le type de H?
En utilisant Y H = H(Y H) comme
règle de réduction pour
une
application de Y dans une réduction de graphes, calculez la
valeur
de
Y F 3
où F =lg. ln.
cond
(le n 1) 1 (add (g (sub n 1)) (g(sub n 2)))
et cond x y z est stricte dans son premier argument et
cond vrai y z = y et
cond faux y z = z.
Quelle est la valeur de Y F n pour un entier
positif n?
File translated from
TEX
by
TTH,
version 3.05.
On 26 Apr 2005, 12:49.