PROFILING SANS EXÉCUTION

Mémoire de fin d’études
Master d’Informatique

Etudiant : BUI Nguyen-Minh
Sous la direction de :
Professeur Danny DUBÉ
Département d’informatique, Université LAVAL

Institute de la Francophonie pour l’Informatique
Novembre 2006


Remerciements
Je voudrais remercier professeur Danny Dubé au Département d’Informatique et de Génie Logiciel à l’Université Laval pour tout ce qu’il a fait
pour moi pendant mon stage, même je n’étais pas très autonome. Je tiens
également à remercier tous les professeurs à l’IFI. Merci à mes parents et mes
amis.

1


Résumé
Dans cette mémoire, nous voudrions présenter une autre façon pour faire le
profiling. Les méthodes courantes, en général, elles ajoutent quelques morceaux de code sources et exécutent le programme pour calculer le profil d’un
programme. Par contre, notre méthode, elle n’exécute pas le programme mais
essaye de construire un système qui modèle l’exécution du programme puis
calcule le profil basé sur le résultat obtenu quand on résout le système. Cette
méthode se compose de deux phases. La première phase vise à calcul le résultat abstrait en utilisant un système de contrainte. Dans la deuxième phase,
utilisant le résultat de la première phase, on construit et résout un système

d’équation pour obtenir un résultat plus détaillé. Pourtant, la méthode de
profiling sans exécution reste de nombreux de problèmes sur le processus
de la modélisation le programme, la solution le système, la convergence du
système et l’évaluation. Nous abordons aussi quelques idées générales sur le
langage fonctionnel et le langage de programmation Scheme.


Table des matières
1 Introduction
1.1 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Types de profiling . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Sujet de stage . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
1
2

2 Langage fonctionnel
2.1 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Particularité des langages fonctionnels . . . . . . . . . .
2.2.1 Absence des effets de bord . . . . . . . . . . . . .
2.2.2 Transparence référentielle . . . . . . . . . . . . .
2.2.3 Peu de structures de contrôle . . . . . . . . . . .
2.2.4 Fonctions comme objets de première classe . . . .
2.2.5 Gestion de la mémoire de façon automatiquement
2.3 Lambda calcul . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Idées générales . . . . . . . . . . . . . . . . . . .
2.3.2 La syntaxe du lambda calcul . . . . . . . . . . . .
2.3.3 Alpha réduction . . . . . . . . . . . . . . . . . . .

2.3.4 Beta réduction . . . . . . . . . . . . . . . . . . .
2.4 Schème . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3
3
3
4
5
6
6
6
6
7
8
8
8

.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.


3 Pré-traitement
9
3.1 Langage à analyser . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Analyse de jetons . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 L’algorithme en bref . . . . . . . . . . . . . . . . . . . . . . . 11
4 Analyse abstraite
4.1 Valeurs abstraites . . . . .
4.2 Idée générale . . . . . . .
4.3 Génération des contraintes
4.4 Commentaires . . . . . . .
4.5 Un exemple . . . . . . . .

.
.
.
.
.

.
.
.
.
.
i

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

13
13
14
14
17
17


5 Analyse statique
5.1 Idée générale . . . . . . . . . . . . . . .
5.1.1 Définitions . . . . . . . . . . . . .
5.2 Système d’équation . . . . . . . . . . . .
5.2.1 Règles pour calculer Πl : . . . . .
5.2.2 Règles pour calculer Πx : . . . . .
5.2.3 Règles pour calculer χl et Kl (l ) :
5.3 Vérifier les équations . . . . . . . . . . .
5.4 Résoudre le système d’équations . . . . .

5.5 Un exemple . . . . . . . . . . . . . . . .
6 Conclusion

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.

19
19
19
20
20
22
22
24
29
31
34

ii


Chapitre 1
Introduction
1.1

Profiling

Les outils pour analyser les programmes (profiling) jouent un rôle très important dans la compréhension des comportements des programmes. En effet,
les constructeurs de matériel informatique ont en besoin pour évaluer comment les programmes marcheront dans la nouvelle architecture. Ils sont aussi
indispensables pour les programmeurs dans l’analyse de leurs codes sources
et dans l’identification des morceaux importants. D’autre part, le profiling
est considéré, par les compilateurs, un outil de mesurer les algorithmes d’optimisation.


1.2

Types de profiling

En général, il y a deux types de profiling : Analyse statique de programmes
et analyse dynamique de programmes.
L’analyse statique de programmes est une famille de techniques permettant de dériver des résultats sur l’exécution de programmes sans exécuter ces
derniers.
Elle se distingue ainsi de l’analyse dynamique ou test, qui revient à essayer
le programme sur différentes entrées jugées représentatives, afin de vérifier
s’il produit les résultats attendus sur ces entrées.
L’analyse dynamique de programmes est une famille de techniques d’analyse d’exécution qui mesure le comportement d’un programme, en particulier
la fréquence et la durée des appels de fonction, quand il fonctionne. La sortie
est une suite des événements enregistrés (une trace) ou d’un résumé statistique des événements observés (un profil )

1


Actuellement, il existe un bon nombre de logiciels qui permettent de faire
l’analyse dynamique de programmes, par exemple : grof, ATOM ...
Les profileurs emploient une grande variété de techniques pour rassembler
des données, y compris des interruptions, l’instrumentation de code, des hooks
de système d’exploitation, et des compteurs d’exécution.
L’instrumentation de code, au temps de la compilation, il insère le code
dans le programme à analyser. Alors le code inséré produit des données d’analyse. Le logiciel ATOM utilise cette technique.

1.3

Sujet de stage


Notre stage a le profiling sans exécution comme le sujet principal. Cette
méthode de profiling consiste à essayer d’estimer le résultat d’un programme
et de mesurer ses comportements sans exécuter le programme.

2


Chapitre 2
Langage fonctionnel
2.1

Concepts

Il y a trois types de langage de programmation : Programmation impérative, programmation fonctionnelle et programmation logistique.
La programmation logique est une forme de programmation dont l’essence
est de définir des règles de logique mathématique au lieu de fournir une
succession d’instructions que l’ordinateur exécuterait. Le premier langage de
programmation logique est Prolog.
La programmation impérative est le style de programmation le plus utilisé, dans lequel les instructions qui modifient les données sont exécutées
simplement les unes après les autres, avec quelques structures de contrôle
permettant de créer des boucles ou des alternatives.
Le troisième type de langage de programmation est le style de programmation dans lequel on ne programme qu’en écrivant des fonctions qui appellent
d’autres fonctions. Ce paradigme de programmation fournie une abstraction
très puissante et très bien connue en mathématiques : la fonction.

2.2
2.2.1

Particularité des langages fonctionnels
Absence des effets de bord


Dans la programmation fonctionnelle, on s’affranchit de façon radicale
des effets de bord en interdisant toute opération d’assignation.
La programmation fonctionnelle souligne l’application des fonctions, contrairement à la programmation impérative qui met l’accent sur les changements
d’état et l’exécution des commandes séquentielles.
C’est pour cette raison qu’on peut éviter les effets de bord en utilisant ce
3


type de langage. En effet, pour décrire un programme, au lieu d’une machine
d’états, le paradigme fonctionnel utilise un emboîtement de fonctions considéré comme des boîtes noires qui sont imbriquées les unes dans les autres.
L’effet de bord est un effet dans lequel une fonction modifie un état autre
que sa valeur de retour. Par exemple une fonction change la valeur d’une
variable globale, donc quand on exécute cette fonction on peut obtenir deux
résultats différents.
int x = 0 ;
int getx()
{
x++ ;
return x ;
}
Cela rende souvent le comportement des programmes plus difficile à comprendre.

2.2.2

Transparence référentielle

Une autre propriété liée à la programmation fonctionnelle, c’est la transparence référentielle. Une expression est transparente de manière référentielle
si elle peut être remplacée dans le code source de programme sans changer
le résultat final du programme. En d’autres termes, cela résulte en un programme avec les même effets et sorties pour les mêmes entrées.

Un grand avantage d’écrire du code avec un style référentiellement transparent est que l’analyse de code statique est plus facile et que des transformations d’amélioration de code sont automatiquement possibles. Par exemple,
en programmation en C, il y a une pénalité de performance pour l’inclusion
d’une fonction dans une boucle, même si l’appel de fonction pourrait être déplacé à l’extérieur de la boucle sans changer les résultats du programme. Le
programmeur pourrait être forcé à faire ce déplacement, peut-être au dépend
de la lisibilité du code. Mais, si le compilateur est capable de déterminer si
l’appel de la fonction est référentiellement transparent, il peut alors effectuer
automatiquement cette transformation.
int square(int x)
{
return (x*x) ;
}

4


Donc, ce morceau de code :
int foo(int n)
{
for (int i = 0 ; i printf(square (5)) ;
}
peut être remplacé par
int foo(int n)
{
int y = square (5) ;
for (int i = 0 ; i printf(y) ;
}

2.2.3

Peu de structures de contrôle

Contrairement aux langages impératifs, dans les langages fonctionnels, les
structures de contrôle sont utilisées de façon moins fréquente que les fonctions
récursives.
Par exemple la fonction pour calculer une somme en C :
sum = 0 ;
for (i :=1 ; isum += i ;
est récrite en Scheme :
(let loop ((i 0))
(if (= i n)
0
(+ i
(loop (+ i 1)))))

5


2.2.4

Fonctions comme objets de première classe

Les langages fonctionnels traitent les fonctions en tant qu’objets de première classe. Spécifiquement, ceci signifie que des fonctions peuvent être
créées pendant l’exécution d’un programme, être stockées en structures de
données, passer comme arguments à d’autres fonctions, et retourner comme
valeurs d’autres fonctions. Par exemple :
Création des fonctions à la volée :
(set ! f (lambda (x) (+ x 1)))

Passage en argument, retour comme résultat :
(f c (lambda (x) (g (+ x 1))))
Stockage dans les structures de données et extraction des structures de données :
(define lst (list 1 (lambda (x) ( + x 1))))
(set ! f (list-ref lst 1))

2.2.5

Gestion de la mémoire de façon automatiquement

Dans les langages fonctionnels, on utilise la gestion automatiquement de
la mémoire, donc, ces langages sont généralement plus sécuritaires mais ils
prennent plus de mémoire par rapport aux langages impératifs comme C.

2.3
2.3.1

Lambda calcul
Idées générales

Le lambda calcul a été inventé par le logicien américain Alonzo Church
dans les années 1930. Le lambda calcul joue un rôle très important dans les
langages fonctionnels parce que la fonction est le centrale dans les langages
fonctionnels.
Dans le calcul de lambda, chaque expression représente une fonction avec
un argument simple. Une fonction est anonyme définie par une expression de
lambda qui exprime l’application de la fonction sur son argument.
Par exemple, ajouter-deux la fonction f tels que f (x) = x + 2 serait
exprimé en calcul de lambda comme λx.x + 2 (ou d’une manière équivalente
comme λy.y +2, le nom de l’argument formel est peu important) et le nombre

f (3) serait écrit en tant que (λx.x + 2)3

6


L’application de fonction est associative à gauche : f xy = (f x)y.
Considérer la fonction qui prend une fonction comme argument et s’applique
avec la valeur de 3 : λf.f 3. Cette dernière fonction pourrait être appliquée à
notre plutôt ajoutent-deux la fonction comme suit : (λf.f 3)(λx.x + 2).
Donc les trois expressions (λf.f 3), (λx.x + 2) et (λx.x + 2)3 et 3 + 2 sont
équivalentes.
Une fonction de deux variables est exprimée en calcul de lambda en fonction d’un argument qui renvoie une fonction d’un argument. Par exemple, la
fonction f (x, y) = x − y serait écrite comme λy.λx.x − y ou λyx.x − y
Les trois expressions (λyx.x−y) 7 2 et (λy.7−y)2 et 7−2 sont équivalentes.
C’est cette équivalence des expressions de lambda qui en général ne peuvent
pas être décidées par un algorithme.
Les expressions de lambda ne peuvent pas toutes être réduites à une valeur
définie comme celle ci-dessus ; considérer par exemple (λx.xx)(λx.xx).
Tandis que le calcul de lambda lui-même ne contient pas des symboles
pour les nombres entiers ou l’addition, ceux-ci peuvent être définis comme
abréviations dans le calcul.

2.3.2

La syntaxe du lambda calcul

Les trois constructions principales du lambda calcul sont
– La variable, par exemple : x, y, z...
– L’application : si u et v sont deux programmes, on peut considérer
u comme une fonction et v comme un argument possible, et former

l’application uv.
– l’abstraction : si u est un programme dépendant (ou non) de la variable
x, alors on peut former un nouveau programme λx.u, qui représente la
fonction qui prend la variable x et retourne u.
D’une autre manière, on peut définir lambdaŰcalcul en utilisant la définition formelle grammaire hors-contexte BNF
< expr >::=< identif ier >
< expr >::= (λ < identif ier > . < expr >)
< expr >::= (< expr >< expr >)
En lambda calcul, l’évaluation se fait à l’aide de réductions. Les deux
réductions dont nous aurons besoin sont l’alpha - réduction qui est l’équivalent du renommage de variable et la bêta - réduction, qui est l’équivalent
de l’appel de fonction.

7


2.3.3

Alpha réduction

On peut constater que les deux expressions : λx.x+1 et λy.y +1 dénotent
la même fonction : que l’argument s’appelle x ou y, c’est toujours la fonction
qui ajoute 1 à son argument. On va donc vouloir confondre les deux termes.
L’égalité entre deux termes dont seuls les noms des variables d’entrée diffèrent
s’exprime alors par la règle suivante, dite d’alpha renommage :
λx.u =α λy.u[x → y]

2.3.4

Beta réduction

Sémantiquement, la règle importante est la beta-réduction qui exprime
que si on applique la fonction qui à x associe u à l’argument v, on obtient la
même chose que si on calcule directement u avec x remplacé par v.
(λxu)v =β u[x → v]
Par exemple, (λxx + 1)4 = 4 + 1.

2.4

Scheme

Scheme est un langage de programmation dérivé du langage fonctionnel
Lisp, créé dans les années 1970 au MIT par Gerald Jay Sussman et Guy
L. Steele. Le but des créateurs du langage était d’épurer le langage Lisp
en conservant les aspects essentiels, la flexibilité et la puissance expressive.
Scheme a donc une syntaxe extrêmement simple, avec un nombre très limité
de mots-clé.

8


Chapitre 3
Pré-traitement
3.1

Langage à analyser

Les langages courants sont trop compliqués pour faire le profiling parce
qu’ils contiennent trop de structures et de types de données (pas nécessaire
pour le but de tester le profiling). De plus, la structure de programme est
aussi compliquée. Donc, on définit un autre langage de programmation qui

est simple mais complet. Il est semblable au langage Scheme.
Syntaxe des expressions :
e ::=
|
|
|
|
|
|
|
|
|

#f constante faux
x référence
(λx.e) lambda-expression
(ee) appel de fonction
(if e e e) conditionnelle
(µx. e) point fixe
(cons e e) création de paire
(car e) extraction du CAR
(cdr e) extraction du CDR
(pair? e) test de parité

Syntaxe des valeurs :
e ::= #f constante faux
| (λx.e) fonction
9

|

(cons e e) paire

Contexte des alpha-réductions :
C α ::=
|
|
|
|
|
|
|
|
|
|
|
|

(λx.C α )
(C α e)
(e C α )
(if C α e e)
(if e C α e)
(if e e C α )
(µx. C α )
(cons C α e)
(cons e C α )
(car C α )
(cdr C α )

(pair? C α )
[.]

Règles des alpha-réductions :
C α [λx.e] →α C α [λy.(e[x → y])]
C α [µx.e] →α C α [µy.(e[x → y])]
Contexte des beta-réductions :
C β ::=
|
|
|
|
|
|
|
|

(C β e)
(v C β )
(if C β e e)
(cons C β e)
(cons v C β )
(car C β )
(cdr C β )
(pair? C β )
[.]

Règles des beta-réductions (règles d’évaluation) :
C β [(λx.e) v] →β C β [e[x → y]]
10

C β [if#f e2 e3 ]
C β [if(λx.e1 )e2 e3 ]
C β [if(consv1 v2 )e2 e3 ]
C β [µx.e]
C β [car (cons v1 v2 )]
C β [cdr (cons v1 v2 )]
C β [pair? #f ]
C β [pair? (λx.e)]
C β [pair? (cons v1 v2 )]

3.2

→β
→β
→β
→β
→β
→β
→β
→β
→β

C β [e3 ]
C β [e2 ]
C β [e2 ]
C β [e[x → (µx.e)]]
C β [v1 ]
C β [v2 ]

C β [#f ]
C β [#f ]
C β [#f ]

Analyse de jetons

Pour les langages impératifs comme C, notre entrée - le programme à analyser est considéré comme une suite de caractère, donc tout d’abord il faut
faire l’analyse de jetons pour découper et regrouper les caractères constituant un programme en jetons. Mais, en utilisant Scheme avec le langage à
analyser au dessus, on peut omettre cette phase. Scheme analyse automatiquement l’entrée et retourne le code source de programme à analyser comme
une expression des symboles.Par exemple,l’expression : (cons #f #f ) est
automatiquement ‘interprétée’ comme une liste de trois symboles, (mais pas
une paire).

3.3

L’algorithme en bref

Cette méthode est divisée en deux phases. La première phase vise à calculer le résultat abstrait en utilisant un système de contrainte. Basant sur le
résultat de la première phase, on construit et résout, dans la phase suivante,
un système d’équation pour obtenir un résultat plus exact.
Par exemple, avec une expression simple :
E = (if (#f ) (#f ) (cons (#f ) (#f )))
Après la première phase, on obtient les valeurs possibles de E sont #f ou
une paire (#f, #f ).
Après la deuxième phase on obtient les valeurs possibles de E sont : #f
avec la probabilité de 0% et une paire (#f, #f ) avec la probabilité de 100%.
Normalement, le résultat de notre méthode est une liste de valeurs, chaque
11

valeur est liée à une probabilité, mais, en réalité, chaque expression retourne
seulement une valeur en exécutant.

12


Chapitre 4
Analyse abstraite
Dans ce chapitre, on va présenter une analyse abstraite sur le code source
d’un programme. Le résultat de cette phase est nécessaire pour faire le profiling dans la deuxième phase.Cette analyse a pour but d’estimer toutes les
valeurs possibles que chaque expression dans le programme puisse créer sans
compter la probabilité de chaque valeur.
Pour faciliter l’analyse abstraite, toutes les expressions dans le programme
sont étiquetées (avec des étiquettes différentes). Par exemple :
(cons1 (#f2 ) (#f3 ))

4.1

Valeurs abstraites

On définit les valeurs abstraites suivantes :
– #f : valeur de faux
– Pi : une paire à la position d’un (sous)-expression ayant l’étiquette i)
– λi : une fonction à la position d’un (sous)-expression ayant l’étiquette i)
– ERROR : une erreur
– ⊥ : valeur infinie, quand l’expression ne retourne pas
Avec les définitions au dessous, on peut dire que la valeur de E = (cons1 (#f2 ) (#f3 ))
est P1 et la valeur de l’appel de fonction E = (call1 (#f2 ) (#f3 )) est
ERROR.

13


On dénote αi l’ensemble des valeurs que l’expression ayant l’étiquette i
peut retourner.

4.2

Idée générale

L’idée générale de cet algorithme est qu’on essaie de calculer la valeur retournée d’un expression en combinant les valeurs des sous-expressions (après
vérifier les relations entres les sous-expressions).
Par exemple, pour l’expression
E = (if1 e2 e3 e4 )
on a α1 = α3 α4 .
Mais on constate que cette estimation est un peu faible parce qu’on ne compte
pas les valeurs de e2 . Une autre estimation plus exacte est comme suivante :
α2 ⊆ {#f } ⇒ α1 ⊆ α4
(α2 \{#f } =

) ⇒ α1 ⊆ α3

(notons que dans Scheme, et dans notre langage, tout est vrai sauf la valeur
de faux #f )
Il nous reste un autre problème à résoudre : comment peut-t-on éliminer
les codes mortes (c’est à dire les morceaux de code qui ne sont jamais exécutés) pour qu’on ne doive pas calculer ses valeurs, et ses valeurs n’affectent
pas d’autres estimations ?
On dénote δi la valeur booléenne vraie/faux, qui indique si l’expression
ayant l’étiquette i est exécutée.
Au début, seulement δ1 est vraie, tous les autres δ sont associés à une fausse

valeur. Pas à pas, en vérifiant la structure de programme, on ‘allume’ les
autres δ jusqu’à il n’y pas de nouveau changement d’état de δ.
Par exemple :
si el = (consl e1 e2 ) alors δl ⇒ δ1 et δl ⇒ δ1

4.3

Génération des contraintes

Ensuite, on présente le système des contraintes qui sont construits à partir
du code source de programme.

14


– Si el = #fl alors
δl ⇒ αl ⊆ {#f }
– Si el = xl alors
δl ⇒ αl ⊆ αx
– Si el = (λl x. el1 ) alors :
δl ⇒ αl ⊆ {λl }
(αx =

) ⇒ δl1

– Si el = (l el1 el2 ) alors :
δl ⇒ δl1
δl ⇒ δl2
pour tout λl3 ∈ αl1 tel que el3 = (λl3 x. el4 ) alors
αx ⊆ αl2

αl ⊆ αl4
αl1 ⊆ {Pi } ⇒ αl ⊆ ERROR
αl1 ⊆ {#f } ⇒ αl ⊆ ERROR
αl1 ⊆ {ERROR} ⇒ αl ⊆ ERROR
αl2 ⊆ {ERROR} ⇒ αl ⊆ ERROR

– Si el = (ifl el1 el2 el3 ) alors :
δl ⇒ δl1
(αl1 \{#} = ) ⇒ δl2
(#f ∈ αl1 ) ⇒ δl3
αl ⊆ αl2 ∪ αl3
(ERROR ∈ αl1 ) ⇒ αl ⊆ ERROR
– Si el = (µl x. el1 ) alors :
δ1
αl
αx
(ERROR ∈ αl1 )

15

⇒
⊆
⊆
⇒

δl1
αl1
αl1
αl ⊆ ERROR

– Si el = (consl el1 el2 ) alors :
δ1
δ1
δ1
αl1 ⊆ {ERROR}
αl2 ⊆ {ERROR}

⇒
⇒
⇒
⇒
⇒

δl1
δl2
αl ⊇ {Pl }
αl ⊆ ERROR
αl ⊆ ERROR

– Si el = (carl el1 ) alors :
δ1 ⇒ δl1
pour tout Pl2 ∈ αl1 tel que el2 = (consl2 el3 el4 ) alors
αl ⊆ αl3
αl1 ⊆ {λi } ⇒ αl ⊆ ERROR
αl1 ⊆ {#f } ⇒ αl ⊆ ERROR
αl1 ⊆ {ERROR} ⇒ αl ⊆ ERROR
– Si el = (cdrl el1 ) alors :
δ1 ⇒ δl1
pour tout Pl2 ∈ αl1 tel que el2 = (consl2 el3 el4 ) alors

αl ⊆ αl4
αl1 ⊆ {λi } ⇒ αl ⊆ ERROR
αl1 ⊆ {#f } ⇒ αl ⊆ ERROR
αl1 ⊆ {ERROR} ⇒ αl ⊆ ERROR
– Si el = (pair?l el1 ) alors :
δ1 ⇒ δl1
soit π = {Pl2 ∈ αl1 }
αl ⊆ π
si αl1 \π = alors αl ⊆ {#f }
αl1 ⊆ {ERROR} ⇒ αl ⊆ ERROR
Contrainte additionnelle sur le programme :
E = e1 et δ1 = vrai
16


4.4

Commentaires

L’analyse reste conservatrice mais elle est relativement précise. Tous les
trois types d’objets sont pris en compte mais seulement les donnes pertinentes
circulent et seulement les expressions qui doivent être évaluées sont calculées.

4.5

Un exemple

Prenons un exemple de cette analyse. Supposons qu’on doit analyser le
programme suivant :
(1 (λ2 f

(if3 #f4
(5 f6 #f7 )
(8 f9 (cons10 #f11 #f12 )))
(λ13 x (car14 x15 ))))
Tout d’abord, on met δ1 = #t, et tous les autres δ = #f . On a un système
de contrainte :
δ1 ⇒ δ2
δ1 ⇒ δ13
pour tout λl3 ∈ α2 tel que el3 = (λl3 x. el4 ) alors
αf ⊆ α13
αl ⊆ αl4
δ2 ⇒ α2 ⊆ {λ2 }
(αf = ) ⇒ δ3
...
À partir de δ1 et les valeurs natives des expressions, on fait l’itération et la
substitution jusqu’au moment où il n’y pas de changement de δ. Le résultat
final est donc comme suivant :
α1
α2
αf
α3
α4
α5

=
=
=
=
=
=

#f , δ1 = #t
λ2 , δ2 = #t
{λ13 }
{#f }, δ3 = #t
{#f }, δ4 = #t
, δ5 = #f
17


α6
α7
α8
α9
α10
α11
α12
α13
αx
α14
α15

=
=
=
=
=
=
=
=

=
=
=

, δ6 = #f
, δ7 = #f
{#f }, δ8 = #t
{λ13 }, δ9 = #t
{P10 }, δ10 = #t
{#f }, δ11 = #t
{#f }, δ12 = #t
{λ13 }, δ13 = #t
{P10 }
{#f }, δ14 = #t
{P10 }, δ15 = #t

18


Chapitre 5
Analyse statique
L’algorithme mentionné dans le chapitre précédent ne donne qu’une analyse ‘abstraite’. Dans ce chapitre, nous voudrions présenter donc une autre
méthode permettant de nous apporter un résultat plus détaillé. Dans cette
méthode, on estime non seulement le résultat de chaque expression mais aussi
la fréquence que chacune (sous-)expression est exécutée dans l’exécution du
programme.

5.1

Idée générale

5.1.1

Définitions

Pour faciliter l’illustration de notre méthode, nous donnons quelques définitions suivantes :
– Πl (v) : On dénote Πl (v) la probabilité de el lorsqu’évalué vaut v, v
est un élément de l’ensemble de valeurs possibles - les valeurs qu’on a
obtenu après la phase 1.
– χl : On dénote χl la probabilité que el soit la prochaine expression à
évaluer.
Donc, le but de notre projet est de calculer les Πl (v) et χl .
– On définit les ensembles suivants :
Val = {#f, ERROR, ⊥} ∪ {λi |i ∈ Label} ∪ {Pi |i ∈ Label} - l’ensemble de tous les valeurs possibles
Val+ = {#f } ∪ {λi |i ∈ Label} ∪ {Pi |i ∈ Label} ∪ {µi |i ∈ Label}

19


OK = {#f } ∪ {λi |i ∈ Label} ∪ {Pi |i ∈ Label}
TRUE = {λi |i ∈ Label} ∪ {Pi |i ∈ Label}
On définit :
– Kl (l ) est la probabilité que el soit la prochaine expression à évaluer
une fois que el est fini.
– Πx (v) est la probabilité que la variable x vaut v pendant l’exécution
du programme.
– Πl (S) =

v∈S

Πl (v) si S ⊆ Val

– Πx (S) =

v∈S

Πx (v) si S ⊆ Val+

L’idée principale ici, c’est qu’on essaye de modeler le programme comme
un système de contrainte (sous une forme d’un système d’équation entre les
Πl (v),χl et Kl (v)). Puis, on cherche une solution ‘acceptable’ de ce système.
On espère que cette solution ‘se reflète’ les valeurs de Π et χ.

5.2

Système d’équation

Les règles pour calculer les Πl (v),χl et Kl (v)) ici sont basées sur l’idée :
"Si on connaît les valeurs des Πl (v),χl et Kl (v) au pas n , comment peut-on
les calculer au pas n + 1 ?"

5.2.1

Règles pour calculer Πl :

– Pour el = #fl
Πl (v) =


 1 si v = #f ;



si v ∈ Val

0 si non.

– Pour el = xl
Πx (µi )Πi (v) si v ∈ Val

Πl (v) = Πx (v) +
µi ∈V al+

20