LANGAGES FONCTIONNELS
Tels ML Miranda

LES REGLES DE TYPE
Typage fort (strict)
Impossible d'appliquer un objet dans un contexte interdit
condition testée par le compilateur

EVALUATION PARESSEUSE
Le mode d'évaluation où on n'évalue un paramètre que quand (si) la fonction dépend de sa valeur
et on n'évalue que les parties d'une structure dont dépend la fonction

Exemple:
sommepremiers  (h1:t1) (h2:t2) = h1+h2 peut être évalué sans évaluer t1 et t2

Permet même la manipulation (raisonnable) de structures infinies!
puissances2  i = (i:puissances2 2*i)
sommepremiers (puissances2 4)  (puissances2 16) calcule 20.

Evaluation paresseuse est standard en Miranda et d'autres langages.

LANGAGES FONCTIONNELS: EXECUTION
Compilation ou Interprétation?

Modifier les méthodes ``Traditionnelles''
Variables libres
Les valeurs de variables (paramètres) seront stockées sur le tas. (parce qu'elles peuvent survivre à la fonction qui les contient)
Possibilité d'optimiser dans le cas de variables simples...
La pile ne contient que des pointeurs à ces variables.

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!)

Evaluation paresseuse
La ``valeur'' d'un paramètre (sur le tas) est soit une vraie valeur soit (un pointeur vers) la fermeture d'une fonction sans paramètres qui donnera(it) la vraie valeur.

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.

Evaluation partielle

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.

UNE METHODE SPECIFIQUE:
REDUCTION D'ARBRES

REDUCTION DE GRAPHES
Idée très simple qui rend la réduction efficace:
remplacer un paramètre (identificateur) par un pointeur au paramètre (sous-arbre); ensuite ce sous-arbre va être évalué une fois (au maximum)

Conséquences:

LE PROBLEME DES VARIABLES LIBRES
Dans la fonction l x. x+ (l y. y+x)(2) la fonction imbriquée a la variable libre x

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!

TRADUCTION EN (SUPER)COMBINATEURS
Réduction ?=? méthode raisonnable d'interpréter des programmes fonctionnels?

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!


S f g  x   =  f x (g x)

K  x  y   =  x

I x   =   x

Y  =  (l h. (l x. h(x x)) (l x. h(x x)))

On peut réduire n'importe quelle expression l (y compris celle pour Y) en une combinaison de S, K, I


l x. x    Þ     I

l x. y   Þ     K y      (x   ¹   y)

l x. E1 E2   Þ     S (l x. E1)(l x. E2)

RECURSION!
Comment définir des fonctions récursives par des expressions l non-récursives??

Une fonction récursive (par ex. factoriel) peut être définie comme le point fixe d'une fonction:
Bizarre f   =  l n. if n = 0 then 1 else n*f(n-1)

Donc on peut écrire factoriel = FIXE Bizarre où FIXE a la propriété FIXE  x  =  x(FIXE x).

Y possède cette propriété!!
Y H
=
(l x. H(x x)) (l x. H(x x))

=
H((l x. H(x x)(l x. H(x x)))

=
H(Y H)

(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.)




File translated from TEX by TTH, version 3.05.
On 26 Apr 2005, 12:36.