LANGAGES FONCTIONNELS
Tels ML Miranda
- Utilisation de fonctions ...
comme moyen principal de former des boucles
donc nécessité de traduction en code efficace
- Variables libres: comme en algol-60 etc.
- Possibilité d'une fonction dont le type du
résultat
est une fonction
- purement fonctionnel: aucun effet de bord
- définition par motif:
f(0,y)=y;f(x,0)=x;f(x,y)=x*y
- définition de structures par leurs fonctions de
construction:
arbreint::=feuille int|
branche(arbreint)(arbreint)
LES REGLES DE TYPE
Typage fort (strict)
Impossible d'appliquer un objet dans un contexte interdit
condition testée par le compilateur
- types de base
- listes [a,b,c] ou (h:t), n-uplets (a,b,c)
- fonctions T1 ® T2 est le type
d'une fonction à
un paramètre de type T1 renvoyant un résultat de type T2
- Complètement récursif: les éléments
des listes, le paramètre
d'une fonction et le résultat d'une fonction peuvent être
des fonctions
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?
- Pourquoi pas les mêmes méthodes que pour un langage
impératif qui permet de définir des fonctions?
- Fonctions renvoyant des fonctions
avec variables libres
- Evaluation paresseuse
- Evaluation partielle
- Peut-on utiliser l'absence d'effets de bord?
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
- représentation d'un programme par un arbre
- Sommets sont: constants, fonctions prédéfinies,
applications (@), fonctions définies par le programme (l), constructeurs
- Réduction est le processus de remplacer un sous-arbre
application par son ``résultat'': pour une fonction
prédéfinie
(par. ex. +), il faut évaluer ses paramètres (des
sous-arbres
évalués récursivement) et appliquer
l'opération; pour une fonction
définie par le programme, les paramètres ne sont pas
forcément évalués
(évaluation paresseuse): remplacer les occurrences des
paramètres dans
le sous arbre (l) par des copies des
paramètres non-évalués
if then else prend aussi des paramètres
non-évalués
- Choix du sommet à réduire? le premier sur le
chemin
le plus à gauche de la racine
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:
- L'arbre devient un graphe
- L'application d'une fonction doit être remplacée
par une copie
de la fonction
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!
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. 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é!!
|
|
(l x. H(x x)) (l x. H(x x)) |
|
|
|
H((l x. H(x x)(l x. H(x x))) |
|
|
|
|
|
(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.