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 TIEU LUAN MOI download : skknchat@gmail.com Remerciements Je voudrais remercier professeur Danny Dubé au Département d’Infor- matique 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 TIEU LUAN MOI download : skknchat@gmail.com 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 mor- ceaux 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ésul- tat 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. TIEU LUAN MOI download : skknchat@gmail.EXECUTION Table des matières 1 Introduction 1 1.2 Types de profiling .3 Sujet de stage .2 Particularité des langages fonctionnels .1 Absence des effets de bord .3 Peu de structures de contrôle .4 Fonctions comme objets de première classe .5 Gestion de la mémoire de façon automatiquement .2 La syntaxe du lambda calcul .2 Analyse de jetons .3 L’algorithme en bref .3 Génération des contraintes.
17 i TIEU LUAN MOI download : skknchat@gmail.EXECUTION 5 Analyse statique 19 5.1 Règles pour calculer Πl : .2 Règles pour calculer Πx : .3 Règles pour calculer χl et Kl (l0 ) : .3 Vérifier les équations .4 Résoudre le système d’équations. 31 6 Conclusion 34 ii TIEU LUAN MOI download : skknchat@gmail.EXECUTION Chapitre 1 Introduction 1.1 Profiling Les outils pour analyser les programmes (profiling) jouent un rôle très im- portant dans la compréhension des comportements des programmes. En effet, les constructeurs de matériel informatique ont en besoin pour évaluer com- ment 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’op- timisation.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 permet- tant 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’ana- lyse 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é statis- tique des événements observés (un profil ) 1 TIEU LUAN MOI download : skknchat@gmail.EXECUTION 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’ana- lyse.
Le logiciel ATOM utilise cette technique.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 TIEU LUAN MOI download : skknchat@gmail.EXECUTION 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 uti- lisé, 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 programma- tion 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 Particularité des langages fonctionnels 2.1 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, contrai- rement à 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 TIEU LUAN MOI download : skknchat@gmail.EXECUTION 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 consi- dé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 à com- prendre.2 Transparence référentielle Une autre propriété liée à la programmation fonctionnelle, c’est la trans- parence 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 pro- gramme 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 trans- parent est que l’analyse de code statique est plus facile et que des transforma- tions 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 TIEU LUAN MOI download : skknchat@gmail.EXECUTION Donc, ce morceau de code : int foo(int n) { for (int i = 0 ; i <n ; i++) printf(square (5)) ; } peut être remplacé par int foo(int n) { int y = square (5) ; for (int i = 0 ; i <n ; i++) printf(y) ; } 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 ; i<n ; i++) sum += i ; est récrite en Scheme : (let loop ((i 0)) (if (= i n) 0 (+ i (loop (+ i 1))))) 5 TIEU LUAN MOI download : skknchat@gmail.4 Fonctions comme objets de première classe Les langages fonctionnels traitent les fonctions en tant qu’objets de pre- miè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 don- nées : (define lst (list 1 (lambda (x) ( + x 1)))) (set ! f (list-ref lst 1)) 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.1 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 TIEU LUAN MOI download : skknchat@gmail.EXECUTION 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. Cette dernière fonction pourrait être appliquée à notre plutôt ajoutent-deux la fonction comme suit : (λf. Donc les trois expressions (λf.x + 2)3 et 3 + 2 sont équivalentes. Une fonction de deux variables est exprimée en calcul de lambda en fonc- tion d’un argument qui renvoie une fonction d’un argument.
Par exemple, la fonction f (x, y) = x − y serait écrite comme λy.x − y Les trois expressions (λyx.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. 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 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éfi- nition 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’équi- valent du renommage de variable et la bêta - réduction, qui est l’équivalent de l’appel de fonction.