La fermeture qui représente une fonction contient des pointeurs
à ces valeurs sur le tas.
(au lieu d'une liaison statique permettant de reconstruire
un environnement qui n'existe plus!)
La première fois que la valeur est demandée, la fonction est évaluée est son résultat remplace le pointeur vers la fermeture.
Si ce paramètre est passé à une (autre) fonction, c'est le pointeur vers cette location du tas qui est passé; donc la valeur est calculée une fois (au maximum).
Evaluation d'une ``structure paresseuse'' continue jusqu'au moment de connaître le constructeur utilisé et construit un enregistrement avec ce constructeur et autant de fermetures qu'il faut pour évaluer les composants.
Au lieu de traiter un appel tel f x y z comme un appel f x qui construit une fermeture qui est appliquée à y etc., on dit que f est une fonction de 3 paramètres et que si on a f x, c'est une évaluation partielle:
Les seules choses qu'on peut faire avec une évaluation partielle sont de la passer à une autre fonction ou de l'appliquer à un paramètre de plus.
Le résultat de l'évaluation partielle peut être représentée par une fermeture où on a déjà inséré la valeur du premier (¼) paramètre.
Conséquences:
Si on applique cette fonction à un paramètre comme 2*y, la réduction donne 2y+(l y. y+2y)(2)
Ce problème de ``capture de variables'' est très sérieux pour l'implémentation du calcul-l
Avec notre ordre de réduction, ceci peut arriver seulement si y est une variable libre du programme; donc interdit!
Parce que, pour chaque fonction définie par le programme, on doit chercher dans le corps pour trouver les occurrences des paramètres afin de savoir où mettre les pointeurs aux sous-arbres
(Pourquoi pas le faire une fois pour toujours?
l'évaluation partielle peut donner de nouvelles fonctions
avec de nouveaux corps!)
Une solution: traduire tout le programme en fonctions prédéfinies: ensuite il existe un nombre fixe de fonctions à exécuter et pour chacune on peut compiler du code pour faire les manipulations (de pointeurs dans le graphe)
Plusieurs façons de procéder: une méthode n'utilise que 4 combinateurs!
|
|
|
|
On peut réduire n'importe quelle expression l (y compris celle pour Y) en une combinaison de S, K, I
|
|
|
Une fonction récursive (par ex. factoriel) peut
être définie comme le point fixe d'une fonction:
|
Donc on peut écrire factoriel = FIXE Bizarre où FIXE a la propriété FIXE x = x(FIXE x).
Y possède cette propriété!!
|
(En fait on peut prendre Y H = H(Y H) comme définition de Y ou comme la règle de réduction à appliquer aux applications de Y pour donner une implémentation plus rapide.)