LA RIVALITÉ KABILA-KAMERHE;VUE PAR WASHINGTON!

09/02/2011 à 09h:34 Par Pierre Boisselet


...Tous les champs marqués * sont obligatoires
Le président congolais Joseph Kabila, et son ancien allié Vital Kamerhe. Le président congolais Joseph Kabila, et son ancien allié Vital Kamerhe. © AFP/Vincent Fournier pour J.A.

Selon un câble diplomatique américain recueilli par WikiLeaks, le président congolais Joseph Kabila aurait usé de pots-de-vin, voire de menaces, pour obtenir la démission de Vital Kamerhe du perchoir de l’Assemblée nationale, en 2009. En cause : les ambitions présidentielles de son ancien allié, qui commençait à lui faire de l'ombre.

Alors que la campagne pour la présidentielle paraît déjà lancée en République démocratique du Congo (RDC), WikiLeaks lâche une nouvelle bombe. Selon l’ambassadeur américain à Kinshasa, Joseph Kabila aurait usé en mars 2009 de différents types de pressions, dont de très copieux pots-de-vin (il est plusieurs fois question de 200 000 dollars) et de possibles menaces, afin d’obtenir la démission de Vital Kamerhe, lequel était alors président de l’Assemblée nationale mais était tombé en disgrâce pour sa liberté de ton.

Constitutionnellement, le président congolais n’a pas le pouvoir de révoquer le président de l’Assemblée nationale, en vertu de la séparation des pouvoirs. A en croire le rapport qu’a établi à l’époque l’ambassadeur américain à Kinshasa William Garvelink pour le Secrétariat d’État américain*, Kabila aurait donc entrepris de l’obtenir d'abord par des pressions indirectes.

Vital Kamerhe venait de s’opposer publiquement au chef de l’État sur deux points sensibles de sa politique : les « contrats chinois » négociés par Kinshasa et son alliance avec le Rwanda dans la guerre dans l’Est de la RDC (où Kamerhe dispose de nombreux soutiens). Pour Joseph Kabila, qui voyait en Kamerhe un sérieux rival potentiel, le président de l’Assemblée nationale venait de franchir la ligne rouge.

« Le gang des quatre »

Selon le câble diplomatique, Joseph Kabila a offert 200 000 dollars à chacun des membres du bureau de Kamerhe pour qu’ils démissionnent. L’ambassadeur précise que cette affirmation est confirmée par « plusieurs sources ». Et le jour où le câble était rédigé, trois membres du bureau avaient déjà démissionné.

À en croire le diplomate américain, outre la carotte, Joseph Kabila aurait aussi manié le bâton en constituant un groupe informel, baptisé « le gang des quatre », pour mettre directement la pression sur Vital Kamerhe lui-même. Ce groupe était constitué d’Augustin Katumba Mwanke (très proche conseiller de Joseph Kabila), Ghislain Chikez (ancien ministre de la Défense), Olivier Kamitatu (toujours ministre du Plan) et Évariste Boshab (à l’époque secrétaire général du parti de Kabila avant de succéder à Vital Kamerhe à la présidence de l’Assemblée nationale où il officie toujours).

Kabila aurait également formé une délégation de quatre chefs tribaux pour intervenir auprès de Kamerhe. L’un d’entre eux, qui sera interrogé ultérieurement par deux représentants (un de l’ONU et un de la France), confiera que Kabila « voulait éliminer » Kamerhe. Une déclaration que les occidentaux ne prennent toutefois pas au sérieux, car émanant d’un chef « manquant de crédibilité », notamment à cause de son « alcoolisme sévère ».

Au représentant de l’Union européenne (UE) pour les Grands lacs, Roeland van der Geer, Kamerhe aurait lui-même confié qu’il craignait qu’on s’en prenne à lui physiquement et qu’il n’avait d’autre choix que de démissionner et de quitter le pays. Là encore, les ambassadeurs occidentaux, qui surveillent ensemble cette « première crise politique majeure » dans le camp de Kabila, mettent en doute cette version qu’ils considèrent comme probablement exagérée. Pourtant, quelques jours après la rencontre avec Van der Geer, c’est un Vital Kamerhe « tremblant » qui réaffirme les risques pesant sur sa sécurité au chef de la Mission des nations unies en RDC (Monuc), Alan Doss, et à l’ambassadeur de l’UE, Richard Zink.

Les Occidentaux, qui semblent tenir Vital Kamerhe en piètre estime, décident toutefois de ne pas intervenir « tant que la Constitution est respectée ». Et le président de l’Assemblée nationale annoncera finalement sa démission le 25 mars 2009.

Kamerhe : « C’est moi la victime »

Interrogé par RFI lundi, Vital Kamerhe dit avoir pris connaissance du contenu des câbles « comme tout le monde ». « Dans ces documents, c’est moi la victime. Je n’ai pas été associé à une quelconque opération de corruption », plaide-t-il.

Le ministre de la Communication, Lambert Mende, également interviewé, estime quant à lui que l’ambassadeur américain, auteur du câble, avait « été abusé, pour autant que le texte vienne de lui ». Vital Kamerhe « a fini par jeter l’éponge de lui même [...] après qu’il s’est rendu compte que [l’Assemblée nationale] n’était pas pour lui en majorité », juge-t-il.

Lambert Mende estime par ailleurs « tout à fait incroyable » que les membres du bureau ait pu recevoir 200 000 dollars affirmant que « le président n’est pas quelqu’un qui distribue de l’argent ni à ses visiteurs et encore moins à ses députés... ». Mais selon le câble diplomatique, les tentatives « d’acheter les votes » au Parlement congolais sont « souvent efficaces dans cette culture politique hautement corrompue »…

 

Cette question est en fait bien de nature plus pratique que théorique. Étant acquis que l'on sait déjà ce qu'est un langage de programmation et un programme. On constate en pratique deux façons d'exécuter ses programmes. La première technique est dite interprétation, un programme (l'interpréteur) lit votre programme à vous et l'exécute. Cette technique tend à disparaître pour les langages d'usage général, mais elle survit bien dans des contextes plus spécialisés. Par exemple, la vaste majorité des imprimantes fabriquent les pages qu'elles impriment en interprétant un langage (le Postscript), les commandes que vous tapez en Unix sont interprétées (et exécutées) par le shell qui n'est rien d'autre qu'un interpréteur, on peut aussi citer JavaScript, interprété par les brouteurs (browsers) web, etc. L'autre technique consiste à compiler. En pratique, un compilateur lit votre programme et le transforme en un exécutable, c'est à dire quelque chose que la machine peut exécuter directement, disons une suite d'entiers que le processeur de votre machine comprend comme des instructions. L'expérience montre l'avantage principal de la compilation sur l'interprétation : les programmes s'exécutent plus rapidement. Cela s'explique par ce que certaines opérations sont faites par le compilateur et ne seront donc plus à faire lors de l'exécution. Pour bien comprendre prenons un programme qui contient l'affectation d'un entier 123 à une variable x. L'interpréteur doit lire les trois caractères, les transformer en un entier machine, puis ranger cet entier dans x. Le compilateur va, quant à lui, lire les caractères, les transformer en un entier machine, puis produire le code qui range l'entier dans la variable x. Dès lors, à l'exécution le programme compilé se contente de ranger l'entier machine dans x, soit grosso-modo une seule instruction machine, tandis que l'interpréteur doit exécuter des dizaines, voire des centaines d'instructions pour arriver au même résultat. Bien sûr, dans la réalité, les choses sont moins nettes, (par exemple, si l'affectation précédente est dans une boucle, un interpréteur ne lira généralement les trois caractère qu'une seule fois) mais l'idée à retenir est que le compilateur réalise par avance certaines des opérations demandées par l'exécution du programme. Cette idée va assez loin, des opérations qui semblent élémentaires telles que « lire le contenu d'une variable », pouvant se décomposer en des opérations effectuées à la compilation (ici, associer le nom de la variable à disons un emplacement dans la mémoire) et des opérations effectuées à l'exécution (ici, lire le contenu de l'emplacement mémoire). De façon parfois un peu abusive, on étend le sens du mot compilateur (présenté ci-dessus comme un traducteur d'un langage de programmation vers des instructions machines) pour l'appliquer à n'importe quel traducteur. Typiquement, toutefois on s'attend à ce que le langage d'entrée, ou langage source, soit de plus haut-niveau que le langage de sortie, ou langage cible. Cette idée de haut-niveau signifie que le langage source contient des construction synthétiques, faciles à comprendre par un homme, tandis que le langage cible exprime des opération élémentaires, faciles à réaliser par une machine. Par exemple, on peut légitiment considérer qu'un traducteur qui transforme la construction de filtrage de Caml (le match) en cascades de tests simples (des if) est bien un compilateur. En poussant un peu le raisonnement dans ses retranchements, un traducteur de Pascal vers C peut être vu comme un compilateur, car Pascal contient nombre de constructions qui n'existent pas en C (par exemple, les constructions d'ensemble ou les procédures locales). 1.1 Qu'est-ce exactement qu'un compilateur ? La présentation introductive des compilateurs est extrêmement simplifiée. La chaîne qui va du programme source à l'exécutable comprend un certain nombre de tâches qui regardent plus le système d'exploitation de la machine (le format exact des fichiers exécutables par exemple) que le processus de traduction du langage source vers des instructions machines. La compilation proprement dite est ce dernier processus, les autres tâches sont déléguées à des programmes spécialisés. Cette section n'entend pas décrire en détail les techniques mises en œuvre par ces outils, mais vous permettre d'en comprendre les principes. 1.1.1 Assembleur Il est bien plus simple de définir une suite d'instructions de la machine par des symboles (par exemple de représenter une addition par « add » que par un code entier quelconque). Dans la pratique les programmes en langage machine se présentent sous la forme de fichiers de texte obéissant à des conventions simples. Ces fichiers sont donc écrits dans un langage particulier dit assembleur, qui sera lui même traduit en suite d'entiers par un programme particulier dit aussi assembleur. Cette transformation n'offre pas d'intérêt particulier, seulement des difficultés techniques qu'il est opportun de laisser régler par le fabricant de la machine ou le concepteur du système d'exploitation. Soit, en première approximation, le compilateur transforme le langage source en assembleur, expression humainement compréhensible des instructions de la machine. Sous Unix, on peut produire un fichier assembleur en donnant une option au compilateur, généralement « -S ». Considérons le fichier suivant bonjour.c : #include <stdio.h> int main (int argc, char **argv) { printf("bonjour\n") ; return 0 ; } Sur un PC quelconque, on le compile ainsi : # cc -S bonjour.c Et on obtient le fichier d'assembleur suivant (quelques détails sont omis !) : .LC0: .string "bonjour\n" .text .align 4 .globl main .type main,@function main: subl $24, %esp pushl $.LC0 call printf addl $28, %esp xorl %eax, %eax ret Chaque ligne de ce fichier s'interprète ainsi : comme une instruction du processeur (par ex. subl $24, %esp, qui doit être une soustraction), comme une directive donnée à l'assembleur (par ex. .align 4 ou .data), débutant par un point, ou comme une étiquette, nom symbolique que l'on donne à une adresse mémoire, suffixée par « : ». Par exemple, l'étiquette main est définie comme égale au début du code de la fonction homonyme. 1.1.2 Édition de liens Jusqu'ici j'ai prétendu que le travail de l'assembleur est de transformer le source d'assemblage en exécutable. Mais en fait j'ai menti. Il est impossible de procéder aussi directement : dans bonjour.s on peut remarquer l'instruction call printf, qui réalise l'appel de la fonction printf. L'instruction call prend en argument une adresse qui est celle du début du code de la fonction appelée ; logiquement cette adresse est présente dans le code assembleur sous forme d'un symbole. Or la fonction printf ne fait pas partie de notre programme, son code est ailleurs. De fait cette fonction fait partie de la librairie standard de C et elle est présente sous forme compilée quelque part. L'assembleur utilisé seul ne peut traduire le symbole printf en une adresse. Son produit sera bien une suite d'entiers représentant des instructions, supplémentée par des indications sur les symboles utilisés (et non résolus), ainsi que sur les symboles définis (par exemple ici main). On appelle ce produit le code objet et les fichiers qui le contiennent portent généralement l'extension « .o ». C'est un autre programme, dit éditeur de liens qui prend tous les fichiers objets et fabrique l'exécutable. L'éditeur de lien s'occupe essentiellement de mettre tous les fichiers objets les uns derrière les autres et de résoudre les références symboliques entre ces fichiers. En Unix, l'éditeur de liens est normalement le programme ld. 1.1.3 Chargement dynamique Une fois encore j'ai menti par souci de simplicité. Il y a encore deux éléments à considérer. Tout d'abord, lorsque l'on compile (sans les lier) de nombreux fichiers, on obtient logiquement de nombreux fichiers objets (les « .o »). C'est en particulier le cas pour la librairie standard. Il n'est pas très pratique de manipuler tous ces fichiers, on les regroupe donc dans une bibliothèque (en anglais library), que l'on appelle parfois aussi archive. En Unix c'est la commande ar qui fabrique ces bibliothèques, leur suffixe est traditionnellement « .a » et leur nom commence généralement par « lib ». Ainsi, la libraire standard de C (dite aussi libc) est généralement un fichier libc.a, qui contient le code de toutes les fonctions de la librairie standard. Mon second mensonge est plus grave, la description de l'édition de liens de la section précédente présente l'édition de liens traditionnelle, dite également statique. Cette technique présente l'inconvénient, lorsque l'on utilise une librairie (et on en utilise forcément) de copier le code des fonctions de librairie dans l'exécutable. Dès lors, tous les programmes C qui utilisent printf contiennent une copie du code de printf, une copie du code de toutes les fonctions appelées par printf, etc. Par conséquent les fichiers exécutables deviennent systématiquement assez gros. Une technique plus maligne dite chargement dynamique, consiste à reporter le chargement en mémoire du code des bibliothèques lors de l'exécution du programme. En gros cela revient, à la compilation, à remplacer l'édition de liens statique par l'ajout de code et d'informations suffisants pour aller chercher les symboles non encore résolus. L'inconvénient majeur de cette technique est que la compilation et l'exécution doivent de dérouler dans des environnements offrant les mêmes bibliothèques, enfin pour le moins des bibliothèques compatibles. Cela complique notablement la distribution de code exécutable et s'applique a fortiori à l'exécution des applets : l'environnement hôte doit fournir une machine virtuelle et des libraires compatibles avec celles de l'environnement de compilation. 1.1.4 En résumé Le simple appel « cc bonjour.c » invoque en fait plusieurs programmes dont un seulement est le compilateur proprement dit. On peut voir ce qui se passe en donnant l'option « -v » à cc. En simplifiant un peu, on a : # cc -v bonjour.c Reading specs from /usr/lib/gcc-lib/i386-redhat-linux/2.96/specs gcc version 2.96 20000731 (Red Hat Linux 7.1 2.96-98) /usr/lib/gcc-lib/i386-redhat-linux/2.96/cpp0 ... bonjour.c /tmp/cc9oRNcK.i /usr/lib/gcc-lib/i386-redhat-linux/2.96/cc1 /tmp/cc9oRNcK.i -o /tmp/cck4wLml.s as -V -Qy -o /tmp/ccNUF1EX.o /tmp/cck4wLml.s /usr/lib/gcc-lib/i386-redhat-linux/2.96/collect2 ... On distingue les appels à l'assembleur (as) et à l'éditeur de liens (collect2). Le compilateur proprement dit est cc1. On notera au passage que java pousse très loin l'idée du chargement dynamique, la tentative de chargement d'un code objet (.class en Java) plus vieux que son source (d'extension .java) allant jusqu'à provoquer une recompilation. Enfin, Caml, le langage de ce cours, suit plus ou moins le principe simple de l'édition de liens statique. Les fichiers objets portant cette fois l'extension .cmo. Au passage encore, le fait que tant javac que ocamlc produisent du bytecode et non pas du code natif ne change pas grand chose à l'affaire. 1.2 La chaîne de compilation Nous avons donc défini un compilateur au sens de ce cours comme un traducteur d'un langage source (de programmation) vers l'assembleur. On décompose cette traduction en traductions plus élémentaires. Tout ceci est idéalement représenté par un schéma (cf. figure 1.1). -------------------------------------------------------------------------------- Figure 1.1: Les phases d'un compilateur -------------------------------------------------------------------------------- Dans ce dessin, les flèches correspondent à des transformations et les boites à des résultats. La colonne de gauche correspond à la partie avant du compilateur (front-end) et la colonne de droite à la partie arrière (back-end). En première approximation ces deux parties sont indépendantes, le front-end dépendant du langage de programmation et le back-end de la machine ciblée. Dans la pratique de ce cours, la majeure partie du front-end va dépendre du langage source, car il implémente réellement la sémantique du langage compilé. Tandis que la plus grande partie du back-end peut sera réalisée dans un style générique, les sous-parties clairement dépendantes de la machine cible étant bien isolées. 1.3 Gestion des compilation et recompilations Pour des raisons diverses, on en vient rapidement à répartir le source d'un programme en plusieurs fichiers. Une des plus convaincantes de ces raisons découle du principe d'abstraction. On construit un programme compliqué par l'assemblage de briques individuellement simples. C'est précisément ce que nous allons faire dans ce cours en écrivant un compilateur, dont les briques de bases (ou phases) seront reparties dans divers fichiers source. C'est pourquoi je prendrai l'exemple d'un gros programme écrit en Caml, langage d'implémentation de notre cours. Une brique s'appelle aussi une unité de compilation, ou parfois un module, ce qui est légèrement impropre. Le principe d'abstraction conduit à séparer une brique B de programme en deux : d'une part un fichier d'implémentation (extension .ml) et d'autre part un fichier d'interface (extension .mli) qui contient les informations suffisantes pour compiler d'autres briques du programme qui utilisent B. Ces informations sont essentiellement les noms des fonctions de B utilisables de l'extérieur (dites fonctions exportées), leurs types, et des commentaires qui disent comment les utiliser. Pour des raisons d'efficacité les fichiers .mli sont compilés en des fichiers objets bien particuliers qui portent l'extension .cmi. Il en résulte une première dépendance : la compilation du fichier nom.ml étant l'occasion de vérifier que le module Nom définit bien ce qu'il affirme exporter dans nom.mli, il importe de compiler l'interface avant l'implémentation. La séparation des unités de compilation en implémentation et interface mène à la propriété de compilation séparée : pour compiler b.ml qui utilise des fonctions de a.ml il n'est pas nécessaire d'avoir compilé a.ml, la compilation préalable de a.mli suffit. Si l'on se place maintenant dans le cadre d'un développement d'un programme zyva, dont le source est réparti en trois unités de compilation, A, B et Zyva. Supposons en outre que Zyva utilise des fonctions de A et de B, tandis que B utilise des fonctions de A. Pour fabrique le programme zyva, on pourra donc enchaîner les commandes suivantes : # ocamlc a.mli produire a.cmi # ocamlc -c a.ml l'option -c évite l'édition de liens, production de a.cmo # ocamlc b.mli # ocamlc -c b.ml # ocamlc -c zyva.ml # ocamlc -o zyva a.cmo b.cmo zyva.cmo édition de liens (On aurait pu tout aussi bien compiler a.mli et b.mli en premiers.) Mieux, si nous modifions a.ml et seulement lui, il suffit pour recréer zyva de procéder ainsi : # ocamlc -c a.ml inclus la vérification de la nouvelle implémentation par rapport à l'interface # ocamlc -o zyva a.cmo b.cmo zyva.cmo édition de liens Dans la pratique il hors de question de gérer compilation et recompilations soi-même, on dispose pour ce faire d'un outil : make. Je présente maintenant quelques principes, qui devraient suffire pour comprendre les exemples donnés en TP. Dans le principe make est un outil simple : à l'aide d'une description des règles de production de fichiers et de leur dépendances, contenue dans un fichier de nom Makefile, l'outil make invoque les commandes nécessaires à la production d'un fichier passé en argument. Soit ici, si on a écrit le Makefile idoine, la commande « make zyva » reconstruira zyva pour nous. Pour ce faire il analyse le graphe des dépendances entre fichiers et invoque les commandes nécessaires (typiquement des appels au compilateur), il s'agit là d'un bête tri topologique que vous connaissez déjà. Dans le cadre de notre exemple, il nous faut donc à la fois définir les règles de production et les dépendances. Voici quelques explications sur ce qu'on peut mettre dans le Makefile. Le cas de l'edition de liens est assez simple : zyva: a.cmo b.cmo zyva.cmo ocamlc -o zyva a.cmo b.cmo zyva.cmo La première ligne décrit les dépendances, la seconde indique comment fabriquer zyva. Attention, la seconde ligne doit obligatoirement commencer par une tabulation. Pour les diverses compilations, les règles de production s'expriment par des règles dites implicites, dont voici la syntaxe : .ml.cmo: ocamlc -c $< .mli.cmi: ocamlc $< C'est à lire comme : en cas de besoin d'un fichier nom.cmo dépend de et se construit avec un fichier nom.ml (qui doit donc exister ou pouvoir être construit), avec la commande ocamlc -c nom.ml. La variable spéciale $< représente le nom du source. Les autres dépendances sont écrites à part, ici on aura : a.cmo: a.cmi b.cmo: a.cmi b.cmi zyva.cmo: a.cmi b.cmi À lire par exemple comme a.cmo doit être refait après a.cmi. On dispose d'un outil spécifique pour produire ces dépendances, ocamldep, qui prend en argument les noms des fichiers sources. Généralement, on met les dépendances dans un fichier nommé .depend, fichier qui est inclus dans le Makefile ainsi : include .depend Il est pratique d'appeler ocamldep à l'aide de make, on utilise donc une cible depend correspondant à la règle suivante : depend: ocamldep *.mli *.ml > .depend On construira (et reconstruira) les dépendances par « make depend ». Notons que l'on ne peut pas appeler la cible .depend, car alors cette cible ne dépendrait de rien et elle serait toujours à jour dès qu'elle existe. 2.1 Les processeurs On entend par code machine le langage du processeur de l'ordinateur. Le modèle d'un processeur est toujours sensiblement le même, il correspond grosso-modo au modèle de Van Neuman, modèle fondateur de l'ordinateur concret. Selon ce modèle, l'ordinateur est composé en première approximation d'un processeur d'un banc de registres et d'une mémoire, la mémoire est un grand tableau d'entiers, dit aussi mots mémoire. Les registres sont une petite quantité de mémoire rapidement accessible. Le processeur lit une instruction à partir de la mémoire, l'exécute, lit une autre instruction l'exécute etc. Les instructions du processeur sont élémentaires, ce peuvent être des lectures ou des écritures en mémoire, des opérations arithmétiques simples entières ou flottantes, des sauts (qui font que l'instruction exécutée ensuite ne suit pas l'instruction de saut dans la mémoire). Elle sont simples parce que réalisées par des circuits électroniques. L'innovation de Van Neuman est que le programme réside dans la mémoire et que le processeur l'interprète en quelque sorte. Une machine connue précédente (l'ENIAC) n'était pas un ordinateur au sens moderne, mais plutôt une grosse calculatrice : il n'existait pas à proprement parler de programme, pour calculer un résultat spécifique, il fallait changer les câblages entre les diverses unités de calcul. Par contraste la machine de Van Neuman est un calculateur dont la tâche est d'interpréter des programmes, on parle aussi de machine universelle. En particulier, et c'est cela qui nous intéresse dans notre cours les programmes sont des données résidant en mémoire, ils peuvent être lus ou produits par d'autre programmes. En ce sens, la machine de Van Neuman ouvre la porte de la compilation. On comprendra donc que les processeurs se ressemblent tous du point de vue de l'utilisateur, puisqu'ils se conforment tous au modèle initial. Les différences entre processeurs proviennent surtout du jeu d'instructions. On distingue : Les (vieux) processeurs CISC (Complex Instruction Set). Leurs instructions sont complexes, de tailles variables, Beaucoup réalisent des transferts avec la mémoire; ils possèdent en général peu de registres. Une opération CISC typique est l'addition d'un registre et d'une case de la mémoire, le résultat étant rangé dans la mémoire, ou une instruction spécialisée dans le transfert des zones de mémoire. Ce type de conception correspond d'abord à l'idée d'une programmation directe de la machine, le programmeur apprécie alors les instructions synthétiques qui lui permettent de faire réaliser des opérations compliquées plus rapidement que par une suite d'instructions. Notons que cette attitude perdure, par exemple les instructions MMX réalisent directement en machine des opérations flottantes sur de petits vecteurs, afin d'accélérer les applications de traitement du signal (ie. image et son). Toutefois, les compilateurs ont du mal à bien utiliser ces instructions. Plus grave, leur présence complique notablement le décodage des instructions par le processeur. En particulier, le format des instructions est peu uniforme : les instructions peuvent occuper un nombre variable de mots. Il s'agit plutôt de processeurs un peu anciens, conçus avant 1985. Typiquement: Intel 8086 et Motorola 68000. Les (nouveaux) processeurs RISC (Reduced Instruction Set) Le jeu d'instruction est réduit et très régulier. Les registres sont nombreux (typiquement 32). En radicalisant, seules deux instructions lisent et écrivent la mémoire (lecture dans un registre, écriture d'un registre). Toutes les autres opèrent entre registres, toujours selon le même schéma. La simplicité du jeu d'instruction autorise des logiques de décodage simples et surtout plus facilement réalisables en parallèle, selon le principe du tuyau (pipe). Par exemple, pendant qu'une addition s'exécute dans l'unité de calcul du processeur, l'unité de de décodage des instructions peut être en train de s'occuper de l'instruction suivante, tandis que l'unité de chargement des instructions peu être en train de lire l'instruction suivant l'instruction suivante. En pratique pour une tâche donnée, on peut s'attendre à ce qu'une machine RISC se montre plus rapide qu'une machine CISC, en raison de ce parallélisme interne. Notons aussi que, lors de l'apparition des RISC, la simplicité des processeurs entraînait une conception rapide et donc la mise à disposition du public des technologies de fabrication des circuits les plus récentes (et les plus efficaces). Un compilateur se débrouille bien avec un jeu d'instruction peu étendu et très régulier. Il sait exploiter des registres nombreux. D'autre part, l'exécution en parallèle des instructions impose des contraintes supplémentaires (par ex, le résultat d'une opération n'est pas disponible pour l'instruction suivante) difficiles (mais aussi inhabituelles) pour un humain. Conçus après 1985. Typiquement: Alpha, Sparc et Mips. G4. Il faut tout de même reconnaître que le fossé entre RISC et CISC n'est pas aussi grand que l'on le pensait dans les années 80. Ici tout est affaire de degré. Les premiers processeurs RISC ne possédaient pas de multiplications câblée (sous prétexte que la multiplication est rare en pratique !), ce n'est plus le cas. À l'inverse, le Pentium (héritier du 8086) a un jeu d'instructions très varié, mais ses diverses incarnations exécutent bien les instructions en parallèle, ce qui était présenté comme propre aux purs RISC à l'origine. 2.1.1 Un peu de culture : le bytecode On ne saurait passer sous silence le bytecode : le compilateur ne produit pas de code pour un processeur réel, mais pour un processeur conventionnel, une machine virtuelle. Les instructions, sont bien représentées par une suite d'entiers, mais c'est un programme qui les lira et les interprétera. Ce dernier programme est bien évidemment écrit dans un langage d'assez bas niveau, typiquement en C. L'avantage de cette technique est la portabilité, pour obtenir un système fonctionnant sur une nouvelle architecture, il n'y a pas besoin de modifier le compilateur, il suffit a priori de porter le programme qui implémente la machine virtuelle. On peut aller jusqu'à considérer que la portabilité s'applique aussi aux programmes compilés : « Compile once, run everywhere » comme on dit pour Java. C'est un peu exagéré en pratique, car un environnement d'exécution ne se compose pas, dans le cas de Java, seulement d'un processeur, mais aussi de nombreuses fonctions de librairie chargées dynamiquement qui doivent alors se trouver à la fois sur le lieu de compilation et sur celui de l'exécution. On comprend cependant bien le principe, qui autorise les applets de Java. Évidemment, l'exécution de bytecode est plus lente que l'exécution directe de code du processeur, dit aussi code natif, car il y a, entre autres, un surcoût dû à la mécanique d'interprétation des instructions. Des exemples de cette technique sont le système de Java (compilateur javac, machine virtuelle java) et le système Objective Caml (compilateur ocamlc, machine virtuelle ocamlrun). Notons que certains compilateurs Java produisent du code natif, tandis que Caml propose un compilateur natif (ocamlopt). Notons également qu'il est possible, lors, disons de la première exécution d'une fonction, de transformer le bytecode en instructions de la machine hôte, on parle alors de compilation à la volée (Just In Time ou JIT). Cela revient un peu à déléguer une partie de la compilation au moment de l'exécution et ne se justifie vraiment qu'en cas de chargement de code à l'exécution entre machines hétérogènes. Dans le cas du bytecode, le concepteur du langage a le choix de la machine cible. Il va donc l'adapter au langage. C'est par exemple le cas de la machine Java qui fournit des instructions d'appel de méthode et de la machine Caml qui fournit des instructions d'appel de fermeture et des opérations arithmétiques sur les 31 bits de poids fort des entiers. Pourtant une machine virtuelle peut à priori fournir une plate-forme d'exécution indépendante à la fois du langage (c'est bien ce que fait une machine réelle après tout) et de la machine réelle. C'est un peu le sens du projet .NET de Microsoft, mais il y a loin de la coupe au lèvres, le modèle de la machine .NET étant spécifiquement objet, et bien plus complexe qu'une machine réelle. Des développement sont d'ailleurs en cours dans le sens de l'extension de la machine machine .NET pour s'adapter aux langages fonctionnels. Une référence intéressante sur la conception d'une machine virtuelle (celle de Caml-Light) est le rapport ZINC. 2.2 Description d'un processeur Dans ce cours nous considérerons un processeur RISC particulier : le MIPS, parce qu'il est simple et exemplaire des processeurs modernes, mais aussi parce que nous disposons d'un simulateur de ce processeur. Le simulateur SPIM est disponible en http://www.cs.wisc.edu/~larus/spim.html. Voici des liens sur le manuel en HTML et en Postscript 2.2.1 La mémoire Tous les processeurs modernes comportent une unité mémoire (MMU) qui permet de manipuler des adresses virtuelles, ie. de faire un renommage, transparent pour l'utilisateur, entre les adresses virtuelles du programme et les adresses réelles en mémoire. Cela permet à chaque programme de choisir ses adresses indépendamment des autres programmes (qui peuvent être exécutés en même temps sur la même machine avec les mêmes adresses virtuelles mais des adresses réelles différentes). Du point de vue de l'utilisateur, la mémoire est un (grand) tableau dont les indices sont les adresses. Généralement, la plus petite unité adressable dans la mémoire est l'octet (8 bits) ou byte. Mais la taille naturelle des entiers manipulés par le processeur, c'est à dire la taille des entiers contenus dans les registres, mais aussi la taille des adresses, est plus grande, typiquement 32 ou 64 bits (soit 4 ou 8 octets). On notera donc que sur un processeur 32 bits, les adresses des mots mémoires successifs sont croissantes de 4 en 4. Les accès à la mémoire non-alignés, c'est à dire ceux qui ne correspondent pas à des adresses multiples de la taille en octets de la valeur accédée, sont soit interdits soit pénalisés. Par exemple, pour le MIPS, l'instruction générique de lecture d'un mot en mémoire lw Avant de décrire les phases de notre compilateur une à une, en suivant l'ordre de leur application, il me paraît plus malin de commencer par décrire d'abord notre langage de programmation, en détaillant sa sémantique plutôt que sa syntaxe. 3.1 Expressivité des langages de programmation Les langages de programmation sont les langages que l'être humain utilise pour dire à un ordinateur ce qu'il doit faire. On peut évoquer les catégories suivantes : Langages généraux Ils doivent être complets, ie. permettre d'exprimer tous les algorithmes calculables. Au minimum, il faut une mémoire réputée infinie (c'est à dire grande) et la possibilité d'exprimer la récursion (construction primitive ou boucle while). Ex: Fortran, Pascal, C, Caml, etc. Langages spécialisés (DSL pour Domain Specific Languages) Ce sont par exemple les langages pour le graphisme, pour commander des robots ou encore la calculette. Ils peuvent ne pas être complets. Bien qu'ils permettent d'exprimer tous les calculs possibles, (c'est approximativement la thèse de Church), les langages généraux ne sont pas tous équivalents stricto-sensu. Ils se distinguent par leur expressivité, c'est à dire par leur capacité d'exprimer des algorithmes succinctement (et directement). Par exemple, on peut toujours implémenter un algorithme récursif à l'aide d'une pile explicite (un tableau plus un indice), mais le langage qui offre la récursivité permet une implémentation plus concise et élégante. Plus précisément, lorsque l'on se pose la question de l'expressivité d'un langage on peut examiner les points suivants : Les fonctions Les fonctions peuvent être définies localement à d'autres fonctions, comme en Pascal, ou pas, comme en C. Les fonctions peuvent être des valeurs du langages comme en Caml (ou en C !), ou pas, comme en Pascal où une fonction ne peut pas rendre une autre fonction comme résultat. Les structures de données Au delà des divers entiers et des tableaux la plupart des langages fournissent des produits (records de C et Pascal, paires de ML) et des sommes (enums et surtout unions de C, types dits concrets de ML). Lisp organise toutes ses données autour de la liste que l'on peut voir comme la somme de la liste vide (nil) et de la cellule de liste (cons). Certaines structures de données comme les chaînes (des tableaux de caractères de taille variable) ne semblent pas à première vue étendre beaucoup l'expressivité du langage, mais leur intérêt pratique apparaît très vite dès que l'on programme. Les modules, les objets sont des traits qui autorisent la programmation incrémentale. Le typage restreint l'expressivité au profit de la sécurité. On considérera d'abord le système de type du langage, par exemple en ML on dispose d'un polymorphisme dit générique qui n'existe pas en Java — en ML on pourra écrire une fonction identité qui accepte tous les arguments possibles, c'est impossible en Java. On pourra aussi s'intéresser à l'impact du système de type sur la programmation : les types sont-ils construits par le compilateur comme en ML, essentiellement donnés par le programmeur comme en C, Pascal et Java, inexistant dans les programmes comme en Lisp et Basic, mais bien présents à l'exécution. Attention, contrairement à une opinion assez répandue, il existe très peu de langages absolument non-typés, à part peut être l'assembleur, on distinguera plutôt entre langages typés statiquement (ML, C, Pascal) : le compilateur vérifie que le programme est bien typé, l'exécution n'échoue jamais (ou rarement) ; et langages typés dynamiquement (Lisp, Basic) : le compilateur ne vérifie rien, mais l'exécution vérifie le bien fondé d'une opération avant de la réaliser. On notera que Java est peu les deux à la fois et on se gardera de trop conclure. Note : Pour comparer l'expressivité formellement, il faut en général le faire point à point en exhibant un codage d'un langage dans un autre qui respecte certaines règles (compositionalité, localité, etc.) 3.2 Comment définir un langage 3.2.1 Syntaxe La syntaxe décrit les mots et les phrases du langage. Elle ne donne aucun sens aux phrases. On peut distinguer syntaxe concrète et syntaxe abstraite. La syntaxe concrète est le discours lui-même, en informatique c'est un fichier, mais on pourrait conceptuellement déclamer des programmes. C'est disons une suite de lettres qui forment des mots qui forment des phrases. La syntaxe abstraite est la structure du discours, en informatique c'est un arbre. Dans les compilateurs, le programme à compiler est bien un arbre, dans le discours sur le langage c'est un dessin. La grammaire est la définition de tous les arbres possibles c'est à dire de tous les discours syntaxiquement bien formés d'un langage. En pratique il est bien commode de commencer par reconnaître les mots avant de s'attaquer aux phrases. On passe donc de la syntaxe concrète à la syntaxe abstraite en deux temps, d'abord par l'analyse lexicale qui traduit une suite de caractères en suite de mots puis par l'analyse grammaticale qui transforme une suite de mots en arbre de syntaxe abstraite. L'exemple du langage des expressions arithmétiques éclairera un peu ces notions. Commençons par définir les entiers, comme une suite de chiffres, les variables comme des suites de caractères alphabétiques, les blancs comme des suites d'espaces et quelques caractères particuliers comme des mots (« ( », « + », etc.) On exprimera les deux syntaxes à partir des mots ainsi définis. Syntaxe concrète représentée par une grammaire, (dans le style dit BNF) expression ::= ENTIER | VARIABLE | expression binop expression | ( expression ) binop ::= + | - | * | / Dans ce style de description, on distingue les terminaux, qui sont les mots, et les non-terminaux qui sont les noms définis par la grammaire. Syntaxe abstraite (en Caml) Représentée par le type expression. type expression = | Const of int | Variable of string | Bin of opérateur * expression * expression and opérateur = Plus | Moins | Mult | Div;; Exemple Ainsi les expressions « (1 - x) * 3 » et « (1-x)*(3) » ont la même syntaxe abstraite : Bin (Mult, Bin (Moins, Const 1, Variable "x"), Const 3);; Les malins remarqueront que l'arbre ci-dessus est décrit sous forme de syntaxe (concrète !) Caml. On devrait donc plutôt dessiner un arbre : On voit alors que le principal effet de l'analyse syntaxique est de remplacer une structure arborescente décrite à l'aide de parenthèses en cette structure elle-même. La syntaxe concrète peut aussi permettre d'exprimer la même construction de syntaxe abstraite sous différentes formes. Ainsi, le caractère « A » peut être représenté par « 'A' » et « '\065' », ou plus significativement la construction de liaison de Caml(-Light) peut s'écrire « let d in e » ou « e where d ». Il convient en général de ne pas abuser de cette possibilité, car elle va contre le principe d'économie de moyens : à quoi bon donner deux façons d'exprimer la même chose ? En outre elle peut rendre les messages d'erreur du compilateur inintelligibles. 3.2.2 Sémantique Il s'agit de donner un sens aux phrases. C'est beaucoup plus facile à faire dans le cas d'un langage de programmation que dans le cas de la langue naturelle. Il s'agit ici d'expliquer ce qu'un programme fait. On distinguera en gros trois façons de procéder. Sémantique informelle Un document de référence décrit la sémantique. Ce document est écrit dans un langage technique qui fait appel à la culture informatique du lecteur. Voici par exemple la sémantique de la boucle while en C. L'instruction while est de la forme : while (expression) instruction la sous-instruction est exécutée de manière répétée tant que la valeur de l'expression reste non nulle. On teste l'expression avant d'exécuter l'instruction. L'avantage est bien entendu que la langue naturelle se prête bien aux vastes concepts et aux descriptions synthétiques et qu'elle est connue du lecteur. On notera ici le choix du mot reste, à mettre en rapport avec l'idée qu'une boucle peut être exécutée plusieurs fois et que la valeur d'une expression peut changer au cours du temps. L'inconvénient est le manque de rigueur, en particulier la fameuse culture informatique est en perpétuelle évolution et il n'est pas toujours évident de faire la part des concepts généraux (comme « un appel de fonction ») et des détails d'implémentation (comme « une adresse mémoire » ou « la zone de code »). En outre, il est impossible de faire des preuves satisfaisantes sans une description plus formelle. On pourrait par exemple vouloir prouver qu'une optimisation compliquée ne change pas les résultats d'un programme, ou qu'un programme bien typé n'échoue pas lors de l'exécution. Sémantique dénotationnelle C'est exactement le contraire de la précédente, on cherche à associer à un programme un objet construit selon les règles de l'art mathématique. Les valeurs d'un langage sont généralement modélisées comme des treillis, les fonctions comme des fonctions continues sur les treillis, la récursion comme un opérateur Chapitre 4 Analyse lexicale Enjeux Les langages formels Expressions régulières ocamllex Bibliothèque des expressions régulières Un peu de théorie L'analyse lexicale se trouve tout au début de la chaîne de compilation, elle collabore avec l'analyse grammaticale pour passer de la syntaxe concrète à la syntaxe abstraite. La mission de l'analyse lexicale est de transformer une suite de caractères en une suite de mots, dit aussi lexèmes (tokens). Procéder ainsi en deux temps, en reconnaissant d'abord les mots, puis les phrases, n'est pas justifié par la théorie. En effet, un analyseur grammatical est strictement plus puissant qu'un analyseur lexical et il pourrait reconnaître les mots. La justification est pratique, l'analyseur grammatical est bien plus facile à écrire une fois les mots reconnus. 4.1 Enjeux La production d'un arbre (de syntaxe abstraite) à partir d'une suite de caractères se retrouve comme première passe dans de nombreuses applications (analyses des commandes, des requêtes, etc.). Les deux analyses (lexicales et syntaxiques) utilisent de façon essentielle les automates, mais on retrouve aussi les automates dans de nombreux domaines de l'informatique. L'analyse lexicale s'explique dans le cadre restreint des automates finis et des expressions régulières (le terme français « autorisé » est expression rationnelle, mais je préfère adapter la terminologie anglaise). Les expressions régulières sont utilisées dans de nombreux outils Unix (éditeur de textes, commande grep etc.), et fournies en bibliothèque dans la plupart des langages de programmation. Note L'étude détaillée des automates constitue un cours à part entière. Nous nous contentons ici de la présentation formelle minimale, avec comme but : d'expliquer le fonctionnement des analyseurs de façon à pouvoir écrire soi-même des analyseurs lexicaux ou grammaticaux, de se familiariser aussi avec les expressions régulières et les automates. Le but du cours n'est pas d'écrire le moteur d'un analyseur, ni de répertorier toutes les techniques d'analyse, mais un peu de théorie ne nuit jamais (voir la section 4.6). 4.2 Les langages formels On se donne un ensemble Σ appelé alphabet, dont les éléments sont appelés caractères. Un mot (sur Σ) est une séquence de caractères (de Σ). On note є le mot vide, uv la concaténation des mots u et v (la concaténation est associative avec є pour élément neutre). On note Σ ∗ l'ensemble des mots sur Σ. Un langage sur Σ est un sous-ensemble L de Σ∗. On se donne quelques opérations sur les langages. Si U et V sont des langages sur Σ, on note U V l'ensemble des mots obtenus par la concaténation d'un mot de U et d'un mot de V; U ∗ (resp. U +), l'ensemble des mots obtenus par la concaténation d'un nombre arbitraire, éventuellement nul (resp. non nul) de mots de U. 4.2.1 Exemples Σ1 est l'alphabet français et L1 l'ensemble des mots du dictionnaire français avec toutes leurs variations (pluriels, conjugaisons, etc.). Σ2 est L1 et L2 est l'ensemble des phrases grammaticalement correctes de la langue française. Un ensemble bien difficile à définir formellement. Ou bien, L2' est le sous-ensemble des palindromes de L2. Σ3 est l'ensemble des caractères ASCII, et L3 est composé de tous les mots-clés de Pseudo-Pascal, de l'ensemble des symboles, de l'ensemble des identificateurs et de l'ensemble des entiers décimaux. Σ4 est L3 et L4 est l'ensemble des programmes Pseudo-Pascal. Σ5 est {a, b} et L5 est l'ensemble { a n b n ∣ n ∈ IN} (sous ensemble des expressions bien parenthésées). 4.3 Expressions régulières La description de langages des mots (voir L1 et L3) qui servent à leur tour à définir des langages des phrases (voir L2 et L4) est relativement simple. On précise formellement cette simplicité en disant que ces langages des mots se décrivent à l'aide du formalisme relativement limité des expressions régulières. On note a, b, etc. des lettres de Σ, M et N des expressions régulières, [[M]] le langage associé à M. Une lettre de l'alphabet a désigne le langage {a}. Epsilon : є désigne le langage {є}. Concaténation : M N désigne le langage [[M]] [[N]]. Alternative : M ∣ N désigne le langage [[M]] ∪ [[N]]. Répétition : M∗ désigne le langage [[M]] ∗. D'autres constructions sont utiles en pratique et exprimables à l'aide des précédentes : [abc] pour (a ∣ b ∣ c) et [a1−a2] pour {c ∈ Σ, a1 ≤ c ∧ c ≤ a2}, en supposant que l'alphabet est ordonné. M? pour M ∣ є, et M+ pour M M∗. [^abc] désigne le complémentaire de {a, b, c} dans Σ, vu comme des mots (et de même pour [^a1−a2]). L'interprétation est facile quand Σ est fini ce qui est toujours le cas. On a aussi parfois point « . » (ou underscore _) pour Σ et ∗ pour Σ∗. La première de ces construction est exprimable comme l'alternative de tous les caractères de l'alphabet, la seconde comme la répétition de la première. Notons un point de vocabulaire. Lorsqu'un mot appartient à un langage défini par une expression régulière, on dit aussi l'expression (ici dénommée motif) filtre le mot. Les langages réguliers sont ceux qui peuvent se définir à l'aide des expressions régulières. Dans nos exemples, L1 est clairement régulier (alternative de tous les mots du dictionnaire, qui est fini) et nous allons voir comment exprimer L3 avec des expressions régulières. C'est essentiellement l'absence de la récursion qui limite les langages réguliers, ainsi on peut montrer que le langage L5 (les parenthèses) n'est pas régulier. Le shell Unix utilise les expressions régulières pour spécifier les noms de fichiers. La commande suivante donne la liste de tous les sources Caml dans le répertoire courant : # ls *.ml{,[ily]} Notez bien qu'ici l'alternative est exprimée avec la virgule « , », le mot vide par rien, et que les accolades sont un simple parenthésage. Dès lors, la commande précédente donne la liste des fichiers dont l'extension est .ml, .mli, .mll (sources du générateur d'analyseurs lexicaux ocamllex), et .mly (sources du générateur d'analyseurs syntaxiques ocamlyacc). 4.3.1 Utilisation pour l'analyse lexicale Les lexèmes sont définis par l'alternative d'expressions régulières. Par exemple : Les mots-clés : "let", "in". En général, les mots-clés ne peuvent pas être utilisés comme noms de variables. Ce parti pris évite pas mal d'ambiguïtés lors de l'analyse grammaticale ultérieure. Les variables : ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9']*. Les noms des variables sont des suites de lettres et de chiffres commençant obligatoirement par une lettre. Les entiers : ['0'-'9']+ Les symboles : '(', ')', '+', '*', '-', '/','='. Un blanc : [' ' '\n' '\t']. Les caractères '\n' et '\t' sont respectivement le retour à la ligne et la tabulation. On est passé ici en notation Caml, où un caractère est donné entre quotes (et une suite de caractères entre double quotes), si on veut le caractère quote « ' », il vaut mieux écrire '\''. Une fois les lexèmes reconnus, ils sont représentés par un type somme dont nous noterons au passage qu'il n'est pas récursif : type token = | LET | IN (* mots-clés *) | VAR of string (* variables *) | INT of int (* entiers *) | LPAR | RPAR | ADD | SUB | MUL | DIV | EQUAL (* symboles *) On notera aussi que les blancs sont omis, c'est à dire qu'ils sont peut être des mots du langage mais sont oubliés en route. De fait les blancs servent surtout à séparer les lexèmes. Il est bien connu que les automates finis (j'en dis un peu plus par la suite) savent reconnaître les langages réguliers, c'est à dire qu'étant donné un langage régulier L on peut construire un automate qui, lorsque l'on lui présente un mot sait répondre par oui ou par non à la question de l'appartenance du mot à L. Très rapidement, l'automate est un graphe dont les sommets sont des états et les arcs des transitions, l'automate est à un instant donné dans un état donné et la consommation d'une lettre du mot le fait changer d'état en suivant une transition. Lorsque le mot est entièrement consommé le mot est reconnu si l'état courant est un état particulier dit final. Par exemple, voici deux automates finis qui reconnaissent respectivement le mot-clé let et les entiers (suite non vide de chiffres). Dans ces dessins, les état initiaux sont grisés et les états finaux encerclés. Dans le second automate, chaque transition en remplace dix, si on suit le formalisme strict des automates. Ensuite, pour reconnaître le mot clé let ou un entier, on peut regrouper les deux automates précédents : On a, ici dans un cas simple, construit l'automate qui reconnaît l'alternative de deux expressions régulières. Selon l'état final atteint (4 ou 5) on connaîtra le lexème reconnu. Toutefois, ceci ne suffit pas tout à fait pour expliquer l'analyse lexicale, nous savons peut être reconnaître si un mot est dans L, mais nous devons, d'une part, reconnaître une suite de mots de L, et d'autre part, savoir de quels mots il s'agit. Intuitivement, un automate peut facilement reconnaître que le mot présenté est bien une suite de mots de L. En effet, le langage d'une suite de mots de L se définit à l'aide de l'opérateur de répétition ∗. Mais on ne sait pas alors quels mots ont été reconnus, il vaut mieux reconnaître les mots un par un. Conceptuellement, il suffit d'arrêter l'automate dans un état final sans attendre la fin du mot, puis de recommencer sur la partie non consommée du mot présenté. Mais il y a encore des cas douteux : let pourrait être reconnu comme une variable. lettre pourrait aussi être reconnu comme la séquence LET; VAR "tre" ou encore comme la séquence VAR "let"; VAR "tre". Ces ambiguïtés se lèvent à l'aide de règles spécifiques. Lors de la reconnaissance d'un mot de L, on cherchera : Le lexème le plus long possible. Entre deux lexème de longueur maximale, l'ordre de présentation des sortes de mots lève l'ambiguïté, la première gagne. Ainsi la phrase let lettre = 3 in 1 + fin devrait produire la suite de lexèmes : LET; VAR "lettre"; EQUAL; INT 3; IN; INT 1; PLUS; VAR "fin" En raison de la règle du lexème le plus long et à condition que, à taille égale, la reconnaissance des mots-clés prime celle des variables. La règle de priorité numéro deux (sur l'ordre de présentation) se réalise simplement au moment de la fabrication de l'automate. Voici par exemple un automate qui reconnaît le mot-clé let ainsi que les identificateurs composés simplement de lettres minuscules, le mot-clé étant prioritaire. L'état final 4 pourrait bien correspondre à une variable ou à let, on choisit de le faire correspondre à la reconnaissance du mot-clé. Sur cet exemple on peut aussi appréhender la réalisation de la règle du lexème le plus long. Tout en consommant les caractères de l'entrée, on peut se souvenir du dernier état final rencontré. Ensuite, lorsque l'automate est bloqué, ici par exemple si il y a un chiffre dans l'entrée, alors on peut revenir au dernier état final vu. Le blocage est facilement détecté en ajoutant un état dit bloqué à l'automate et en complétant les transitions issues de tous les états par des transitions vers l'état bloqué. 4.4 ocamllex Nous ne savons pas précisément comment, à partir de la définition des lexèmes donnés comme expressions régulières, fabriquer l'automate qui les reconnaît. Nous admettons que cet automate existe. Bien mieux, il existe un programme ocamllex qui sait le construire pour nous. L'outil ocamllex est lui même un compilateur, qui prend comme source les expressions régulières (dans un fichier nom.mll) et produit un programme Ocaml (dans un fichier nom.ml), programme qui réalise l'automate. 4.4.1 Un exemple simple -------------------------------------------------------------------------------- Figure 4.1: Analyseur lexical de la calculette { open Token exception Error } rule token = parse (* Les lexèmes stricto-sensu *) | '(' {LPAR} | ')' {RPAR} | '+' {ADD} | '-' {SUB} | '*' {MUL} | '/' {DIV} | '=' {EQUAL} | "let" {LET} | "in" {IN} | ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9']* {VAR (Lexing.lexeme lexbuf)} | ['0'-'9']+ {INT (int_of_string (Lexing.lexeme lexbuf))} (* Règles supplémentaires *) | eof {EOF} | [' ''\n''\t' ] {token lexbuf} | "" {raise Error} -------------------------------------------------------------------------------- Commençons par un exemple, celui d'un analyseur lexical pour calculette avec let. On écrit le source de la figure 4.1 dans un fichier lexer.mll, la commande : # ocamllex lexer.mll produit un nouveau fichier lexer.ml. L'exemple suffit déjà pour expliquer pas mal de choses sur la structure des fichiers source de ocamllex. Le source commence par du code source Caml entre accolades, ocamllex copie ce code quel au début du fichier lexer.ml, de même on peut mettre du code Caml à la fin. Ici, le code donné en prélude commence par ouvrir le module Token, qui est supposé contenir la définition interne des lexèmes (autrement dit il existe un fichier token.mli qui contient la définition de type de la section 4.3.1). Cela permet d'écrire par exemple LPAR au lieu de Token.LPAR. Ensuite, on trouve la définition de l'automate (ici dénommé token) sous forme d'une suite de règles introduites par les mots-clés (de ocamllex) rule et parse. Chaque règle est constituée d'une expression régulière (le motif) et d'une action, du code Caml à exécuter après reconnaissance. Les premières règles de la parenthèse ouvrante au mot-clé (de la calculette) in ne posent pas de problème, l'action est de rendre le lexème reconnu. Ça se complique un peu pour les identificateurs, on voit apparaître la variable lexbuf et la fonction Lexing.lexeme dans l'action. La première est en fait l'argument implicite de l'analyseur, ie. la suite de caractère analysée, la seconde extrait la suite de caractères reconnue de lexbuf passé en argument. Le type des lexbuf est défini par le module Lexing de la bibliothèque standard, c'est une réalisation des suites de caractères qui répond aux besoins des analyseurs lexicaux. Dans ce cas l'entrée s'appelle aussi un flux. La règle des entiers s'explique de la même façon. En outre on convertit au passage la chaîne reconnue en entier. Notons qu'à partir de la version 3.07 de Caml, on peut écrire. | ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9']* as lxm {VAR lxm} | ['0'-'9']+ as lxm {INT (int_of_string lxm)} C'est à dire qu'il est possible de lier la chaîne reconnue à une variable quelconque (ici lxm) à l'aide de la construction as. Dans la règle suivante, le motif est le mot-clé (de ocamllex) eof. Cela indique la fin du flux d'entrée, l'automate rend alors un lexème spécifique qui aurait dû être ajouté à la définition des lexèmes de la section 4.3.1. Ensuite, vient la règle de reconnaissance des blancs. On se contente de « manger » le blanc reconnu et de rappeler l'analyseur token, en lui passant explicitement l'entrée. Enfin la dernière règle reconnaît le lexème vide. En raison de la règle du lexème le plus long, cette règle s'applique lorsqu'aucune des autres règles ne s'applique. Dès lors, elle identifie les erreurs. Après la compilation de lexer.mll, le fichier lexer.ml contient donc la réalisation de l'automate token sous la forme d'une fonction de type Lexing.lexbuf -> Token.token. La « mission » de cette fonction est de reconnaître et renvoyer le lexème présent au début de son entrée et de consommer les caractères correspondants. La consommation des caractères n'est pas explicitée par le type, elle s'opère par effet de bord sur le flux passé en argument. À titre d'exemple, voici un petit bout de code Caml qui compte les lexèmes présents dans l'entrée standard. let entrée = Lexing.from_channel stdin in (* Fabriquer le flux *) let count = ref 0 in while Lexer.token entrée <> Token.EOF do count := !count + 1 done ; Printf.printf "J'ai lu %d lexèmes\n" !count 4.4.2 Exemples plus compliqués Mon propos n'est pas donner une description exhaustive de ocamllex. Ceux qui sont intéressés peuvent commencer par consulter le manuel. Je vais plutôt décrire quelques exemples et en profiter pour introduire d'autres traits de ocamllex. Éliminer les commentaires Commençons donc par considérer le cas des commentaires. Il est naturel de supprimer les commentaires dès l'analyse lexicale, ainsi les commentaires n'ont aucun impact sur toutes les phases suivantes du compilateur. Il y a trois sortes de commentaires. Les commentaires s'étendent d'un mot particulier jusqu'à la fin de la ligne. C'est par exemple le cas en Java : // Je suis un commentaire. On élime facilement ce type de commentaire en ajoutant une règle à l'analyseur token. | "//" [^'\n']* '\n'? {token lexbuf} L'élimination s'opère comme pour les blancs en rappelant token récursivement. On doit bien remarquer que le motif qui filtre le texte du commentaire est [^'\n']* (une suite de caractères différents du retour à la ligne) et non pas _* (n'importe quel mot). En effet, avec le second motif, les commentaires s'étendraient du premier // au dernier retour à la ligne, en raison de la règle du lexème le plus long. On notera encore que le retour à la ligne est optionnel '\n'?, afin de considérer aussi un commentaire en fin d'entrée et sans retour à la ligne. Les commentaires sont compris entre deux mots particuliers. mais ils ne peuvent pas être imbriqués. C'est le cas de la seconde sorte de commentaires de Java. /* Je suis un commentaire, sur deux lignes. */ Pour éliminer ce type de commentaires on ne peut pas s'inspirer du cas précédent, car il n'y a pas de motif exprimant que l'entrée est différente d'un certain mot, comme il existe un motif exprimant que l'entrée est différente d'un certain caractère. Pour s'en sortir on a recours à un deuxième automate incomment, lancé à l'ouverture du commentaire et chargé de reconnaître la fin du commentaire. rule token = parse ... | "/*" {incomment lexbuf} and incomment = parse | "*/" {token lexbuf} | _ {incomment lexbuf} | eof {raise Error} L'automate incomment rappelle token dès qu'il voit la fin du commentaire, mange un caractère du commentaire et se rappelle, ou signale une erreur si l'entrée touche à sa fin avant la fermeture du commentaire. À la reflexion, l'expression régulière suivante fonctionne aussi : rule token = parse ... | "/*" ([^'*']|('*'+[^'*''/']))* '*'+ '/' {token lexbuf} L'expression régulière ([^'*']|('*'+[^'*''/']))* décrit touts les mots qui ne contiennent pas "*/", sauf les suites non vides de '*', tandis que '*'+ '/' décrit les suites (possiblement vides) de '*' suivies de "*/". On peut trouver le premier motif en cherchant à expliciter le complément de "*/". Vous trouverez à la fin de la leçon une autre méthode pour trouver cette expression régulière. Les commentaires sont compris entre deux mots particuliers et ils peuvent être imbriqués. Ce dernier type de commentaires permet de neutraliser du source dans un programme, y compris si le source commenté contient des commentaires. C'est le cas des commentaires de Caml. (* Un commentaire (* avec un commentaire dedans *) *) On ne peut plus utiliser un deuxième automate comme précédemment, car le niveau d'imbrication des commentaires est arbitraire. De fait, le langage formel défini informellement ci-dessus n'est pas régulier (c'est plus ou moins le langage des expression bien parenthésées) et donc il ne peut pas être reconnu par un automate fini. On pourrait en utilisant deux automates supplémentaires, reconnaître les commentaires imbriqués au plus une fois mais ce n'est pas très général. Pour s'en sortir on va ajouter de l'état aux automates, en se donnant un compteur depth du nombre de commentaires ouverts. { let depth = ref 0 } rule token = parse ... | "(*" {depth := 1 ; incomment lexbuf} and incomment = parse | "*)" {depth := !depth-1 ; if !depth <= 0 then (* où en sommes nous ? *) token lexbuf (* on ferme le premier "(*" *) else (* on ferme un autre "(*" *) incomment lexbuf} | "(*" {depth := !depth+1 ; incomment lexbuf} | _ {incomment lexbuf} | eof {raise Error} Le compteur depth est logiquement incrémenté par chaque ouverture et décrémenté par chaque fermeture. Il est possible de se passer du compteur global réalisé à l'aide de la référence depth et de le remplacer par un argument supplémentaire donné à la règle incomment. rule token = parse ... | "(*" {incomment 1 lexbuf} and incomment depth = parse | "*)" {if depth <= 1 then (* où en sommes nous ? *) token lexbuf (* on ferme le premier "(*" *) else (* on ferme un autre "(*" *) incomment (depth-1) lexbuf} | "(*" {incomment (depth+1) lexbuf} | _ {incomment lexbuf} | eof {raise Error} On notera enfin que les commentaires du source ci-dessus ne seraient pas correctement éliminés, en raison de la présence de la chaîne "(*" dans les commentaires. Il faudrait pour dépasser ce petit inconvénient, ignorer le contenu des chaînes dans les commentaires à l'aide d'un troisième automate. Récupérer les chaînes Considérons maintenant les chaînes (du langage analysé) définies comme tout ce qui se trouve entre deux caractères double quote « " ». On ajoute donc un lexème STRING of string au type des lexèmes et on cherche comment reconnaître les chaînes de l'entrée. Si le double quote est interdit dans les chaînes, alors il n'y a pas de difficulté on s'en tire un peu comme dans le cas des variables. | '"' [^'"']* '"' as lxm (* Noter: '"' est le caractère « " » *) {(* supprimer le premier et le dernier caractère de lxm *) STRING (String.sub lxm 1 (String.length lxm-2))} On peut éviter l'appel aux fonctions du module String, car la construction as permet aussi de nommer des sous-chaînes de la chaîne reconnue par le motif. On écrira donc: | '"' ([^'"']* as content) '"' {STRING content} Mais le programmeur peut légitimement vouloir mettre un double quote dans une chaîne. Le concepteur prévoit alors un mécanisme de citation (quotation) : à l'intérieur d'une chaîne \" veut dire « " » et \\ veut dire « \ » (pour donner un moyen de mettre « \ » à la fin d'une chaîne). Je me félicite des guillemets français qui signifient ce caractère là. Comme il n'y a pas de notion de chaînes imbriquées dans les chaînes, on a le net sentiment que l'on va pouvoir s'en sortir à l'aide d'un automate supplémentaire instring, comme pour les commentaires /*… */. Il y a une petite différence, ici on doit renvoyer en résultat les caractères de la chaîne reconnue et non plus les ignorer. Pour éviter les recopies de chaîne en pagaille, ou pourrait employer des listes de caractères. Nous allons plutôt employer un tampon (buffer) tel que défini par le module Buffer de la bibliothèque standard (c'est en gros le même fonctionnement que la classe StringBuffer de Java). -------------------------------------------------------------------------------- Figure 4.2: Reconnaissance des chaînes { let sbuff = Buffer.create 16 (* fabriquer le buffer *) } rule token = parse ... | '"' {STRING (instring lexbuf)} and instring = parse (* Fin de la chaîne *) | '"' {let r = Buffer.contents sbuff in (* récupérer le contenu de sbuff *) Buffer.clear sbuff ; (* réinitialiser sbuff *) r} (* Caractères cités *) | '\\' ('"'|'\\' as c) (* c est le second caractère reconnu *) {Buffer.add_char sbuff c ; (* à mettre à la fin de sbuff *) instring lexbuf} | _ as c {Buffer.add_char sbuff c ; instring lexbuf} | eof {raise Error} -------------------------------------------------------------------------------- On notera d'abord, dans le code de la figure 4.2, l'utilisation de la la construction as pour récupérer un caractère de l'entrée. Ce qu'il faut remarquer c'est que, dans la construction motif as variable, variable est de type char quand motif est un motif caractères ou une alternative de motifs caractère. Jusqu'ici, motif pouvait filter des chaînes de longueur diverses et le type de variable était string. On remarquera aussi que le type de l'automate instring est Lexing.lexbuf -> string. Enfin, on ne se laissera pas intimider par les mécanismes de citation de Caml : la notation '\\' désigne bien le caractère « \ ». Abondance de mots-clés Dans un langage programmation normal il y a souvent un nombre important de mots-clés. En principe cela ne pose pas de problème, il suffit de se donner une règle de reconnaissance par mot-clé et ocamllex construit l'automate. Mais en pratique, si il y beaucoup de mots-clés, l'automate sera gros voire énorme. On peut surmonter cet inconvénient en utilisant la clé anglaise de la programmation : la table de hachage. (La clé anglaise taiwanaise est un outil bon marché et polyvalent, mais moins efficace qu'une clé plate Facom de la bonne taille.) Les tables de hachage sont disponibles en Caml dans le module Hashtbl de la bibliothèque standard. Les tables de hachage définissent des associations de n'importe quoi à n'importe quoi, on les utilise ici pour définir une association des chaînes aux lexèmes. Une fois une suite de lettres reconnue, on vérifie si par hasard cette suite de lettres n'est pas un mot-clé. Si oui, on a reconnu le mot-clé, si non, on a reconnu un identificateur (voir la figure 4.3). -------------------------------------------------------------------------------- Figure 4.3: Reconnaissance a posteriori des mots-clés { let keywords = Hashtbl.create 17 (* création de la table de hachage *) (* initialisation de la table *) let _ = Hashtbl.add keywords "let" LET ; (* associer LET à "let" *) Hashtbl.add keywords "in" IN ; (* associer IN à "in" *) ... } rule token = parse ... | ['a'-'z']+ {let lxm = Lexing.lexeme lexbuf in try Hashtbl.find keywords lxm (* chercher lxm dans la table *) with Not_found -> (* lxm n'est pas un mot-clé *) Var lxm } (* c'est donc un identificateur *) -------------------------------------------------------------------------------- On remarquera l'utilisation plutôt simple des tables de hachage et le respect de la sémantique des mots-clés prioritaires sur les identificateurs. Les erreurs Pour le moment nos analyseurs se contentent signaler les erreurs, sans donner aucune information spécifique. On peut enrichir l'information donnée au programmeur en différenciant les erreurs, pour signaler un caractère illégal, une chaîne non-terminée etc. Mais l'information qui aidera sans doute le plus le programmeur est une position dans le fichier analysé. Or, dans une action, la fonction Lexing.lexeme_start (resp. Lexing.lexeme_end) fournit la position dans l'entrée du début (resp. de la fin) du dernier lexème reconnu. On peut alors transmettre cette position comme argument de l'exception Error en l'accompagnant d'un message d'erreur explicatif. { exception Error of int * string let error pos = raise (Error (pos,msg)) } rule token = parse ... | "" {error (Lexing.lexeme_start lexbuf) "Caractère illégal"} and incomment = parse ... | eof {error (Lexing.lexeme_start lexbuf) "commentaire non terminé"} En fait, il faudrait travailler un petit peu plus pour par exemple transmettre la position du commentaire ouvert et non refermé. Dans le cas où l'entrée est un fichier, la position comptée en caractères à partir du début du fichier est assez peu pratique, même si un éditeur tel que emacs sait automatiquement retrouver une telle position. Il est plus pratique de donner la position sous la forme d'un numéro de ligne et d'un compte de caractères à partir du début de la ligne. Considérons par exemple le fichier er.ml suivant : let x = 1 let y = "coucou let z = 1 La tentative de compilation ocamlc er.ml donne : File "er.ml", line 2, characters 8-9: String literal not terminated Le compilateur retrouve assez facilement un numéro de ligne à partir d'une position (en réouvrant le fichier), et le confort d'utilisation gagné vaut ce petit effort. Une autre possibilité est de tenter de corriger les erreurs (en les signalant tout de même !) et de reprendre l'analyse. On pourra par exemple simplement ignorer les caractères spéciaux. Mais c'est en fait difficile et souvent un peu vain, car l'analyseur aura du mal à deviner ce que le programmeur a en tête. Il ne saura pas, par example, où refermer une chaîne qui court jusqu'à la fin de l'entrée. 4.5 Bibliothèque des expressions régulières Un outil tel que ocamllex facilite l'écriture des analyseurs lexicaux, mais il n'est pas très pratique pour programmer à l'aide des expressions régulières, comme on le fait par exemple beaucoup en Perl. En effet, on doit mettre l'analyseur dans son propre fichier .mll ce qui est un peu lourd. Par ailleurs, les générateurs d'analyseurs lexicaux visent plutôt un public de concepteurs de compilateurs et leurs concepteurs ne proposent pas toujours quelques traits courants et pratiques qui séduisent le plus vaste public des programmeurs. Des bibliothèques « d'expressions régulières » répondent à ce besoin de plus grande flexibilité et d'expressivité étendue. En Caml, on dispose de la bibliothèque Str. Elle ne sera pas décrite ici, ceux qui sont intéressés peuvent consulter le manuel. Il y a deux points notables : Le parti-pris syntaxique est à l'opposé de ocamllex : au lieu de citer les caractères de l'alphabet on cite les constructions des expressions régulières. En ocamllex on écrivait ('a'|'b'), en Str on écrira \(a\|b\). Enfin, ce n'est pas tout à fait exact, les caractères $^.*+?[] sont spéciaux et doivent parfois être cités avec « \ » pour se signifier eux mêmes. Un trait supplémentaire intéressant est que, en cas de réussite du filtrage, le parenthésage permet d'extraire des sous-chaînes de la chaîne filtrée. Nous nous contenterons donc d'un exemple simple. Nous cherchons à reconnaître des adresses de courrier électroniques de la forme Prénom.Nom@polytechnique.fr, afin d'en extraire le nom. En outre, nous acceptons les variations de casse dans le nom de domaine polytechnique.fr. Le code est donné par la figure 4.4. -------------------------------------------------------------------------------- Figure 4.4: Exemple d'utilisation de la bibliothèque Str open Str open Printf (* - ^ initial -> début de ligne - [^.] -> tout sauf le point - \. -> un point - \(... \) -> groupage, groupes numérotés de gauche à droite - .* -> n'importe quelle chaîne - $ -> fin de ligne *) let auto = regexp "^[^.]+\.\([^@.]+\)@\(.*\)$" (* compilation de l'automate *) let extrait s = if string_match auto s 0 && (* filtrage *) String.lowercase (matched_group 2 s) = (* extraction 2ème groupe *) "polytechnique.fr" then printf "Le nom est %s\n" (matched_group 1 s) (* extraction 1er groupe *) else printf "Ce n'est pas une adresse de l'X\n" -------------------------------------------------------------------------------- La bibliothèque Str ne fait pas partie de la bibliothèque standard. Par conséquent, l'argument str.cma doit être donné explicitement lors de l'édiction de liens: # ocamlc options str.cma files… 4.6 Un peu de théorie Cette section culturelle explique les principes des générateurs d'analyseurs lexicaux tels que ocamllex. Le principe général est celui d'une véritable compilation des expressions régulières aux automates. 4.6.1 Automates finis déterministes (DFA) Un automate fini déterministe M est un quintuplet (Σ, Q, δ, q0, F) où Σ est un alphabet; Q est un ensemble fini d'états; δ : Q × Σ → Q est la fonction (partielle) de transition; q0 est l'état initial; F est un ensemble d'états finaux. On peut étendre δ sur Q × Σ ∗→ Q par ⎧ ⎨ ⎩ δ (q, є) = q δ (q, aw) = δ (δ (q, a), w) Le langage L(M) reconnu par l'automate M est l'ensemble { w ∣ δ (q0, w) ∈ F } des mots permettant d'atteindre un état final à partir de l'état initial. Exemple Soit un automate : L'automate reconnaît le langage {aab, bbb}, La formalisation comme un quintuplet est laissée en exercice. 4.6.2 Automates finis non-déterministes (NFA) La définition est la même que celle de automates déterministes, compte tenu des deux détails suivants : Les transitions sont définies par une relation et non plus par une fonction, c'est à dire que plusieurs transitions issues d'un état donné peuvent porter la même étiquette. Il existe des transitions « spontanées » qui portent une étiquette spéciale, classiquement є. On peut exprimer ces modifications en définissant les transitions entre états comme une relation δ (fonction dans les booléens) sur Q × (Σ ∪ {є}) × Q. Une telle relation peut aussi très bien se noter comme une liste de triplets q ↦a q'. On étend δ sur Q × Σ ∗× Q par ⎧ ⎪ ⎨ ⎪ ⎩ δ(q,є, q) δ(q,є, q'') ∧ δ(q'', w, q') ⇒ δ(q, w, q') δ(q, a, q'') ∧ δ(q'', w, q') ⇒ δ(q, aw, q') (Il y a un peu d'abus, la relation définie est le point fixe des implications et il y a quelques quantificateurs implicites.) Le langage L(M) reconnu par un automate non déterministe est {w ∣ ∃ qf ∈ F, δ (q0, w, qf)} . Notons, et c'est assez intéressant, que les transitions définissent aussi une fonction de Q × Σ ∗ vers 2Q (ensembles d'états) : à un état q et un mot w, on associe l'ensemble Q' des états q' tels que la relation δ(q, w, q') tient. Exemple Soit un automate : L'automate reconnaît le langage des mots d'au moins une lettre formés avec a et b. On note que le mot ab peut être reconnu de deux façons différentes (à q0 et ab, on associe {q0, F1, F2}). On peut intuitivement voir la reconnaissance d'un mot par un tel automate comme le calcul d'un ensemble d'états effectués ainsi. Initialement, l'ensemble des états est l'état initial plus tous les états accessibles par une suite de transitions spontanées. Pour consommer un caractère a, l'automate suit toutes les transitions étiquetées par a et issues de son ensemble d'états courant. Ensuite, il complète le nouvel ensemble d'états courants comme initialement. Ainsi la consommation du mot ab peut se décrire par les trois dessins suivants (cette fois ci, c'est l'ensemble des états courants qui est grisé). 4.6.3 Compilation des expressions régulières Nous sommes maintenant équipés pour décrire la fabrication d'un automate fini déterministe reconnaissant un langage régulier donné. Il s'agit d'une véritable compilation qui comprend trois phases successives1. Des expressions régulières aux NFA L'intérêt des automates non-détermistes est qu'il est facile d'associer un automate (Q, δ, s, F) reconnaissant un langage L à une expression régulière M définissant le langage L. [[a]] = ({s, f}, {s ↦a f}, s, {f}) [[є]]= ({s, f}, {s ↦єf}, s, {f}) [[M ∣ M']] = (Q ∪ Q' ∪ {s''}, δ ∪ δ' ∪ { s'' ↦єs, s'' ↦єs' }, s'', F ∪ F') [[M M']] = (Q ∪ Q', δ ∪ δ' ∪ {f ↦єs', f ∈ F}, s, F') [[M∗]] = (Q, δ ∪ {f ↦єs, f ∈ F}, s, {s}) Ce n'est pas la seule construction possible. Par exemple, on peut exprimer graphiquement une construction légèrement différente (la modification ne porte que sur l'alternative). La nouvelle construction produit des automates à un seul état initial et un seul état final. Ces automates sont représentés par des boîtes portant le nom du motif représenté, leur état initial est à gauche et leur état final à droite. -------------------------------------------------------------------------------- Chapitre 7 Sélection des instructions Principes La sélection en pratique Un exemple simple Quelques détails 7.1 Principes Le source de la passe de sélection des instructions est donc le code intermédiaire canonisé et linéarisé (voir le chapire précédent), sa cible est le langage assembleur de la machine ciblée, c'est à dire dans notre cas celui du MIPS (voir la section 2.2). Les instructions du MIPS opèrent principalement sur le schéma « trois-adresses », c'est à dire que la plupart des instructions effectuent une opération sur deux registres machines et rangent le résulat dans un troisième. Par exemple l'addition : add r1, r2, r3 Nous noterons ce style d'instruction r1 ← r2+r3. En fait la deuxième source r3 peut aussi être un petit entier sur 16 bits. Il d'agit d'une instruction machine différente, même si elle a le même mnémonique add, on la note r1 ← r2+i16. Deux autres instructions importantes du MIPS sont l'écriture et la lecture de la mémoire (store et load). sw r1, i16(r2) # charge le contenu de r1 dans la case mémoire d'adresse i16+r2 lw r1, i16(r2) # idem pour lire la mémoie Nous les noterons [i16+r2] ← r1 et r1 ← [i16+r2] (rappelons que l'adresse mémoire écrite ou lue est la somme du petit entier i (seize bits) et du contenu du registre r2 (trente-deux bits). Le chargement en registre d'une constante ou d'une adresse (une étiquette) s'effectue par les instructions : li r1, i la r1, l Notées r1 ← i et r1 ← l. Du point de vue strictement machine, ces instructions sont en fait identiques : charger un entier en registre. Le mnémonique la indique simplement à l'assembleur de la présence d'une étiquette à resoudre. Toutefois, si l'entier tient sur 16 bits, il s'agit d'une unique instruction machine et de deux sinon. Pour distinguer ces deux cas, donnons nous deux instructions r1 ← i16 et r1 ← i32 (pour l'instruction la nous ne pouvons rien faire). Enfin, il reste une dernière instruction importante, celle qui transfère le contenu d'un registre r2 dans un autre r1 move r1, r2 La sélection opérée sur une instruction du code intermédiaire consiste à parcourir l'arbre de cette instruction en émettant la ou les instructions machines qui la réalisent. Il s'agit essentiellement d'un parcours postfixe, on compile les arguments avant d'emettre l'instruction machine qui realise de calcul demandé par un nœud. Chaque bout de code rend son résultat dans un temporaire frais alloué pour l'occasion. Soit par exemple l'instruction Move (t0, Mem (Bin (Plus , Temp t1, Const i16))), présentée sous forme d'arbre avec la simplification de montrer l'addition comme un arbre binaire : On obtient alors ces trois codes possibles, qui tous sont corrects. t2 ← i16 t3 ← t1 + t2 t4 ← [0 + t3] t0 ← t4 t3 ← t1 + i16 t0 ← [0 + t3] t0 ← [i16 + t1] Le premier code prend au pied de la lettre la notion de sélection comme parcours postfixe, le second remarque l'existence d'une instruction d'addition dont la seconde source est un entier et que l'on peut éviter un transfert de registre, le dernier code se rend compte d'entrée de jeu de tout le pouvoir de l'instruction de chargement en mémoire du MIPS. Une bonne façon de voir est de regrouper les nœuds de l'arbre qui se retrouvent réalisés par une même instruction machine. On appelle traditionellement ces regroupement des tuiles (tiles). On obtient alors logiquement les recouvrements de l'arbre en quatre, deux ou une tuiles de la figure 7.1. -------------------------------------------------------------------------------- Figure 7.1: Trois recouvrements de la même instruction du code intermédiaire. -------------------------------------------------------------------------------- On notera que les temporaires (et l'entier i16) sont laissés en dehors des tuiles. En effet, ils n'ont pas d'intérêt, seule compte l'instruction sélectionnée. Les malins remarqueront que, pour bien recouvrir tout les nœuds de l'arbre, il nous faudrait une tuile supplémentaire recouvrant le nœud Temp et correspondant à aucune instruction. Sur notre exemple nous pouvons dresser deux tableaux des tuiles correspondant à chaque instruction machine (voir figure 7.2). Il y a un tableau pour les expressions du code intermédiaire, et un autre pour ses instructions. -------------------------------------------------------------------------------- Figure 7.2: Les tuiles utilisées dans notre exemple Tuiles à recouvrir les expressions r1 ← i16 : r1 ← r2 + r3 : r1 ← r2 + i16 : r1 ← [i16 + r2] : Tuiles à recouvrir les instructions r1 ← r2 : r1 ← [i16 + r2] : -------------------------------------------------------------------------------- La sélection revient à couvrir les constructions du code intermédiaire à l'aide de tuiles définies à partir du jeu d'instruction de la machine. Pour une instruction donnée, le jeu de tuile associé exprime son « pouvoir couvrant ». Ainsi, en tenant compte de la commutativité de l'addition, le jeu de tuiles « à couvrir les expressions du code intermédiaire » de l'instruction machine r1 ← r2 + i16 est constitué de deux tuiles. Tandis que l'instruction machine r1 ← [i16 + r2] possède quatre tuiles à couvrir les instructions du code intermédiaire. La dernière tuile provient de l'identité x − i = x + (−i). Une tuile du même genre ne semble pas utile dans le cas de l'instruction r1 ← r2 + i16 car la tuile de l'instruction de soustraction immédiate r1 ← r2 − i16, couvre ce cas. Si les coûts de l'addition et de la soustractions étaient différents, nous pourrions adopter l'une ou l'autre tuile1. Une fois les tuiles définies, le jeu consiste donc à en recouvrir les arbres du code intermédiaire. Si on associe à chaque instruction machine (et donc aux tuiles) un coût, on peut distinguer deux classes de recouvrement d'intérêt particulier. Les recouvrements optimaux, tels qu'on ne peut pas regrouper deux tuiles adjacentes pour produire une nouvelle tuile de coût inférieur à la somme des deux tuiles fusionnés. Les recouvrements optimums, tels que la somme du coût de leurs tuiles est mimimale. Le coût des instructions machine peut par exemple s'estimer en considérant le nombre de cycles du processeur nécessaires pour les exécuter. Dans le cas du MIPS il suffit alors de compter le nombre d'instructions machines des expansions des instructions de l'assembleur (celles que nous sélectionnons en fait). Cette estimation ne rend bien entendu pas compte exactement du temps d'exécution d'une instruction, qui dépend de nombreux autres facteurs (état des caches, du pipeline, …). Une estimation encore plus simple est d'associer un coût unité à chaque instruction de l'assembleur, il y a alors confusion entre coût, nombre de tuiles et longueur de la séquence d'instructions assembleur générée. Toutes ces estimations sont grossièrement fausses dans le cas de la multiplication et de la division qui coûtent toujours plus qu'une instruction ordinaire. Pour le moment gardons juste ce point en mémoire. Selon les définitions, un optimum est forcément optimal mais pas le contraire. De fait, l'optimal est un optimun local. La différence de coût entre optimal et optimum n'apparaît que sur des recouvrement plus compliqués que le nôtre et surtout pour un jeu d'instructions plus étendu. Cette différence est de toute façon rarement significative en pratique. Or, il existe un algorithme simple et efficace pour atteindre un optimal, tandis que trouver un optimum demande un algorithme de programmation dynamique plus compliqué et coûteux. Nous nous cantonerons donc à l'optimal, ce qui n'est pas le cas des concepteurs de générateurs de sélecteurs d'instructions. Ces générateurs sont de véritables compilateurs qui transforment des jeux de tuiles (et de coûts) en des programmes réalisant la sélection d'instructions. L'intérêt de ces outils n'est pas évident dans le cas des processeurs RISC. L'estimation du coût individual des instructions ne rend pas très bien compte des temps effectifs d'exécution. La différence entre optimum et optimal se fait surtout lorsque qu'il y a choix possible entre deux instructions coûteuses différentes, une situation exceptionelle dans le cas d'un processeur RISC. La recherche de l'optimal se programme assez facilement en ML. Ainsi, quand le jeu d'instruction est simple, on rechigne à se donner la peine d'apprendre le fonctionnement d'un outil qui réalise un travail que l'on peut faire soi-même assez facilement. On comparera par exemple avec l'analyse grammaticale : la complexité de l'analyse des grammaires LALR(1) et leur expressivité justifient l'emploi d'un outil genre yacc. En effet, la recherche d'un recouvrement optimal se fait à partir de la racine de l'arbre, on essaie d'abord toutes les tuiles possibles en retenant celle de moindre coût parmi les tuiles qui convienent ; dans le modèle simple de coût, la tuile à choisir est celle qui a le plus nœuds. Ensuite, on opère récursivement sur les sous-arbres qui dépassent de la tuile. Cela semble peut être un peu compliqué, mais l'idée des tuiles précède la venue des langages genre ML, qui possèdent la construction du filtrage (pattern matching). Une tuile est réellement une description des nœuds du sommet d'un arbre avec des trous, c'est à dire exactement un motif (pattern) au sens de ML, et la recherche de l'optimal se fait donc par une bête fonction récursive qui filtre son argument selon les tuiles. Par exemple, le programme Caml de la figure 7.3 génère du bon code et n'est guère moins concis qu'une spécification équivalente pour un générateur de sélecteurs. -------------------------------------------------------------------------------- Figure 7.3: Un petit sélecteur d'instructions en Caml (* Les entiers relatifs de l'intervalle [−2b−1… 2b−1[ sont représentables sur b bits *) let seize_bits i = -(1 lsl 15) <= i && i < (1 lsl 15) let emit s = Printf.printf "%s\n" let rec emit_exp e = match e with | Temp _ -> () (* cas de base, pas d'instruction *) (* Constante entière *) | Const i -> emit "r1 ← i" (* l'assembleur distingue r1 ← i16 et r1 ← i32 *) (* Addition *) | Bin (Plus, Const i, e2) when seize_bits i -> emit_exp e2 ; emit "r1 ← r2 + i16" | Bin (Plus, e1, Const i) when seize_bits i -> emit_exp e1 ; emit "r1 ← r2 + i16" | Bin (Plus, e1, e2) -> emit_exp e1 ; emit_exp e2 ; emit "r1 ← r2 + r3" (* Accès mémoire *) | Mem (Bin (Plus, Const i, e2)) when seize_bits i -> emit_exp e2 ; emit "r1 ← [i16 + r2]" | Mem (Bin (Plus, e1, Const i)) when seize_bits i -> emit_exp e1 ; emit "r1 ← [i16 + r2]" | Mem (Bin (Sub , e1, Const i)) when seize_bits (-i) -> emit_exp e1 ; emit "r1 ← [i16 + r2]" (* i16 est -i *) | Mem e -> emit_exp e ; emit "r1 ← [0 + r2]" | ... and emit_stm stm = match stm with ... -------------------------------------------------------------------------------- En fait, à condition de présenter les motifs les plus spécifiques en premier, c'est le compilateur Caml qui fait le plus gros travail : la compilation du filtrage On notera aussi que l'emploi de la clause when qui résout oportunément le problème des entiers sur 16 bits. 7.2 La sélection en pratique 7.2.1 Les registres Les registres réels du processeurs sont connus de la sélection, pour émettre certaines instructions qui opèrent sur des registres fixés, mais aussi pour réaliser les conventions d'appel. Ces registres sont représentés par des temporaires, le module Gen définissant un tableau de temporaires registers à cet effet. Le sélecteur assigne un usage à ces temporaires pré-alloués. Le plus pratique est de ranger chaque temporaire de registre machine dans une variable qui porte son nom conventionel. À l'intention de l'assembleur on se donne aussi un tableau de chaînes des noms conventionnels. (figure 7.4). -------------------------------------------------------------------------------- Figure 7.4: Les registres du MIPS dans la sélection. let r = Array.sub registers 0 32 (* Le MIPS a 32 registres *) let zero = r.(0) and at = r.(1) and v0 = r.(2) ... and fp = r.(30) and ra = r.(31) let name_of_register = [| "zero"; "at"; "v0"; "v1"; "a0"; "a1"; "a2"; "a3"; "t0"; "t1"; "t2"; "t3"; "t4"; "t5"; "t6"; "t7"; "s0"; "s1"; "s2"; "s3"; "s4"; "s5"; "s6"; "s7"; "t8"; "t9"; "k0"; "k1"; "gp"; "sp"; "fp"; "ra"; |] (* Usage standard des registres MIPS *) let arg_registers = [a0; a1; a2; a3] and res_registers = [v0] and caller_save_registers = [t0; t1; t2; t3; t4; t5; t6; t7; t8; t9] and callee_save_registers = [ra ; s0; s1; s2; s3; s4; s5; s6; s7] (* Une autre convention, 3 registres disponibles let arg_registers = [a0] and res_registers = [v0] and caller_save_registers = [] and callee_save_registers = [ra] *) -------------------------------------------------------------------------------- On regroupe ensuite facilement les registres par catégories. Un fois encore, il s'agit de conventions que nous pouvons changer, afin par exemple de tester l'allocateur de registres sous pression. Toutefois, le registre ra doit impérativement être inclus dans la liste des callee-saves, nous verrons pourquoi dans la section sur les fonctions. 7.2.2 Les instructions assembleur Nous devons sélectionner les instructions mais pas encore choisir les registres. Un type Ass.instr explicitant les temporaires et leur usage mais paramétré par les mnémoniques permet cette opération étrange à première vue (figure 7.5). -------------------------------------------------------------------------------- Figure 7.5: Le type des instructions assembleur, interface ass.mli type temp = Gen.temp type label = Gen.label type instr = | Oper of string * temp list * temp list * label list option (* Oper (mnémonique, sources, destinations, sauts) *) | Move of string * temp * temp | Label of string * label -------------------------------------------------------------------------------- Examinons un peu le principe de l'instruction la plus générale Oper. Soit donc la presqu'instruction MIPS add t1, t2, t3. Ce n'est pas tout à fait une instruction de l'assembleur en raison des temporaires qui prennent la place des registres. On la représente par : Oper ("add ^d0, ^s0, ^s1", [t2 ; t3], [t1], None) La chaîne est l'instruction de l'assembleur, avec les registres arguments de remplacés par ^di ou ^si. Ces chapeaux étranges désignent l'emplacement dans l'instruction des registres lus et écrits par elle. L'entier i désigne le i plus unième registre de chaque catégorie. La numérotation s'entend par rapport aux listes de temporaires qui suivent, la première liste contient les registres lus (ou sources, d'où le « s ») la seconde les registres écrits (ou destinations, d'où le « d »). Enfin le dernier argument indique les sauts effectués par l'instruction, ici il n'y en pas, donc c'est None. Plus précisément, None signifie que le contrôle passe nécessairement à l'instruction suivante. Selon cette représentation l'instruction d'addition « immédiate » add t1, t2, 20 sera donc : Oper ("add ^d0, ^s0, 20", [t2], [t1], None) Les sauts s'expriment aussi avec Oper. Il faut d'abord bien voir que les étiquettes ont une représentation conforme à nos besoins (type Gen.label) et une représentation externe conforme aux exigences lexicales de l'assembleur (genre que des caractères alphanumériques). On passe de la repésentation interne à la représentation externe par la fonction Frame.string_label. Soit donc une étiquette l de représentation externe L123. Alors, un saut vers cette étiquette s'exprime comme : Oper ("b L123", [], [], Some [l]) Pour l'instruction de saut conditionnel beq t1, t2, L123 on aura donc : Oper ("beq ^s0, ^s1 L123", [t1 ; t2], [], Some [l ; l']) Surprise ! Une deuxième étiquette apparaît dans les branchements, c'est celle de la condition invalidée, qui est le dernier argument de l'instruction Cjump du code intermédiaire. Après canonisation, la définition de cette seconde étiquette suit nécessairement en séquence. Voilà une occasion de découvrir l'encodage de la pose des étiquettes dans le code assembleur. Soit donc L321 la représentation externe de l'étiquette l', on aura : Label ("L321:", l') On note le « : » suffixant l'étiquette. Enfin l'insruction move t1, t2 de transfert de registre à registre est particularisée, en raison de son importance lors de l'allocation de registres, dont une des missions est justement de supprimer les moves si il est arrivé à assigner le même registre machine à t1 et t2. Move ("move ^d0, ^s0", t2, t1) Ne vous laissez pas surprendre par l'échange des arguments, toutes les conventions ont leurs défauts. 7.2.3 Sélection pour les expressions Les instructions assembleur seront au final donées en argument à une fonction emit comme dans le code de la figure 7.3. Mais là où le selecteur théorique affichait l'instruction selectionnée, le selecteur réel doit renvoyer une liste d'instructions machine. Plutôt que de faire renvoyer la liste d'instruction par le selecteur, je préfère conserver une programmation impérative (et oui ça m'arrive) et donc continuer d'appeler la « fonction » emit pour son effet de bord. La fonction emit doit donc maintenant accumuler les instructions dans une structure de donnée quelconque, que j'appelle une table (figure 7.6). -------------------------------------------------------------------------------- Figure 7.6: Interface du module Table. type 'a t val create : 'a -> 'a t (* Créer une table *) val emit : 'a t -> 'a -> unit (* Ajouter un element à la fin de la table *) val trim_to_list : 'a t -> 'a list (* Vider la table dans une liste *) -------------------------------------------------------------------------------- La table est une structure impérative, on définira emit ainsi : let nop = Oper ("nop", [], [], None) (* instruction qui ne fait rien *) let my_table = Table.create nop (* le typage de Caml exige cet argument *) let emit ins = Table.emit my_table ins Il se révèle pratique de regrouper les cas semblables à l'aide de fonctions d'émission spécifiques. Par exemple, pour les opérations arithmétiques on peut écrire : let memo_of_op = function | Uplus -> "addu" (* addition non signée, pour les calculs d'adresse *) | Plus -> "add " | Minus -> "sub " ... | Eq -> "seq " | Ne -> "sne " (* opérations booléennes *) let emit_op3 op d s0 s1 = emit (Oper (memo_of_op op^" ^d0, ^s0, ^s1"),[s0 ; s1], [d], None) let emit_op2 op d s i = emit (Oper (memo_of_op op^" ^d0, ^s0, "^string_of_int i),[s], [d], None) let emit_move d s = emit (Move ("move ^d0, ^s0", s, d)) Enfin, la fonction de sélection emit_exp doit maintenant rendre le temporaire destination de l'instruction émise. La figure 7.7 décrit un selecteur complet pour les expressions. On peut comparer avec la figure 7.3 qui décrit l'algorithme employé, donc un sélecteur « théorique ». -------------------------------------------------------------------------------- Figure 7.7: Un sélecteur effectif let rec emit_exp e = match e with (* Temporaire *) | Temp t -> t (* Constantes *) | Const 0 -> zero (* c'est un registre *) | Const i -> let d = new_temp () in emit (Oper ("li ^d0, "^string_of_int i, [], [d], None)) ; d | Name l -> let d = new_temp () in emit (Oper ("la ^d0, " ^label_string l, [], [d], None)) ; d (* Opérations *) | Bin ((Plus|Times|Uplus) as op, Const i, e2) -> emit_binop op e2 (Const i) | Bin (op, e1, e2) -> emit_binop op e1 e2 (* Accès mémoire *) | Mem e -> let d = new_temp () and s,i = emit_addr e in emit (Oper ("lw ^d0, "^string_of_int i^"(^s0)", [s], [d], None)) ; d (* Les expressions sont canoniques *) | Call (_,_) -> assert false and emit_binop op e1 e2 = match e2 with | Const i when seize_bits i -> let s = emit_exp e1 and d = new_temp () in emit_op2 op d s i ; d | _ -> let s0 = emit_exp e1 and s1 = emit_exp e2 and d = new_temp () in emit_op3 op d s0 s1 ; d and emit_addr e = match e with (* seuls cas intéressants à repérer *) | Bin (Uplus, Temp r, Const i) when seize_bits i -> r,i | Bin (Uplus, Const i, Temp r) when seize_bits i -> r,i (* cas général *) | _ -> emit_exp e, 0 -------------------------------------------------------------------------------- Les temporaires renvoyés sont pour la plupart des temporaires frais, sauf pour les cas particuliers d'un temporaire Temp t (t est renvoyé) et de la constante entière 0 (le registre zero est renvoyé). On notera l'astuce employée pour exploiter l'éventuel seconde source entière et l'usage de fonctions appelées quand le sommet de la tuile identifie l'instruction lw ou le groupe des instructions arithmétiques. On remarquera aussi que le selecteur n'essaie pas d'effectuer les opérations dont les deux arguments sont connus. Cette mission est dévolue à des phases d'optimisation (avec notre représentation des instructions machines ce type d'optimisation n'est possible qu'en amont). Enfin, j'ai un peu triché avec les additions signées et non-signées pour avoir plus de tuiles dans le sélecteur théorique. La selection sur les instructions du code intermédiaire ne sera pas décrite en détail : c'est exactement la même chose que pour les expressions. La seule différence notable est que les instructions du code intermédiaire n'ont pas de valeur. La fonction emit_stm se contentera donc d'émettre le code machine qui exécute son argument et renverra void (() de type unit). val emit_stm : Code.stm -> unit 7.2.4 Les fonctions Le sélecteur est chargé de réaliser les conventions d'appel de la machine ciblée. Les conventions qui nous intéressent ici sont surtout celles qui déterminent les rapports entre l'usage des registres et les fonctions. Ces conventions pour le MIPS sont décrites à la section 2.4.6. On a principalement. Une fonction prend ses quatre premiers arguments dans les registres a0, a1, a2 et a3. Une fonction rend son résultat dans v0. Les registres s0 à s7 sont les callee-saves. C'est à dire que leur contenu n'est pas affecté par l'appel de fonction. En pratique cela veut dire qu'avant d'écrire dans un callee-save, une fonction doit sauvegarder son ancien contenu, afin de le remettre dans le callee-save avant de retourner. D'où le nom, callee voulant dire « fonction appelée ». Les registres t0 à t9 sont les caller-saves. Le contenu d'un caller-save peut être détruit par un appel de fonction. En pratique cela veut dire que si on range une valeur dans un caller-save et que l'on souhaite encore l'utiliser après un appel de fonction, alors il faudra sauvegarder le contenu du caller-save avant l'appel. D'où le nom, caller voulant dire « fonction appelante ». Appels Après canonisation, l'appel de fonction n'apparaît plus que dans les instructions du code intermédiaire. Suposons donc un appel de procédure (de fonction) à deux arguments. Exp (Call (f, e1, e2)) Move_temp (t, Call (f, e1, e2)) (En fait l'argument de Call est une liste d'expressions.) Nous devons d'abord émettre les instructions qui calculent la valeur de e1 et la rangent dans a0, puis celles qui calculent la valeur de e2 dans a1. Ensuite nous pouvons émettre l'instruction d'appel de sous-routine jal (figure 7.8). -------------------------------------------------------------------------------- Figure 7.8: Appel de fonction, passage des arguments en registres let emit_jal lab sources dests = emit (Oper ("jal "^lab, sources, dest, None)) let emit_call2 f e1 e2 = emit_move a0 (emit_exp e1) ; emit_move a1 (emit_exp e2) ; let lab = Gen.label_string (Frame.frame_name f) in emit_jal lab [a0; a1] (ra::v0::args_registers@caller_save_registers) let is_fun = match Frame.frame_result f with Some _ -> true | None -> false in if is_fun then Some v0 else None -------------------------------------------------------------------------------- Examinons d'un peu plus près l'instruction jal. L'adresse de la sous-routine est extraite du frame de la fonction, à l'aide de la fonction idoine du module Frame. On constate ensuite que, du point de vue de son dernier argument, l'instruction ne branche pas : elle s'exécute en séquence. Le point de vue est donc de voir l'appel de sous-routine comme une instruction ordinaire. En fait, cette instruction ordinaire remplace les instructions du corps de la fonction f, que nous ne pouvons pas connaître en général puisqu'elles peuvent être émises après l'émission de l'appel. Les sources de cette instruction sont les deux registres arguments a0 et a1, même si ces registres n'apparaissent pas explicitement dans le mnémonique (pas de ^s0, ni de ^s1). On découvre ensuite une liste impressionante de destinations. La présence de ra ne surprend pas car l'instruction jal écrit dedans, la présence de v0 non plus car si f est une fonction, elle y rangera son résultat, comme le dit emit_call2 elle même. Mais si f est une procédure ? Et bien f peut aussi écrire dans v0, si par exemple f appelle une autre fonction. Il en va de même pour tous les registres arguments et tous les registres caller-save2. Les callee-saves sont exclus de la liste parce que, même si f écrit dedans, elle doit les rendre dans l'état où elle les a trouvés, ce qui vu de l'extérieur revient à ne pas écrire dedans. Il en va de même pour tous les autres temporaires, car la sémantique des temporaires ordinaires est de ne pas être concernés par l'appel de fonction (section 6.2.2). Il faut bien comprendre que nous sommes justement en train de réaliser cette sémantique. Elle est à voir comme une donnée qui aide à comprendre comment le sélecteur réalise les conventions d'appel. En fait, les sources et les destinations des instructions sont une information destinées à l'analyse de durée de vie (liveness) préalable à l'allocation des registres. De son point de vue, les sources sont des temporaires nécessaires à l'exécution d'une instruction et les destinations sont les temporaires dont cette execution détruit le contenu. Ou plus exactement, comme cette information ne peut être totalement connue, les sources comprennent au moins les temporaires nécessaires et les destinations au moins les temporaires détruits. Adopter ce point de vue dès maintenant aide à comprendre les « lus » et les « ecrits » du type Ass.instr. Les primitives sont un cas particulier, elles sont réalisées par de petites fonctions écrites en assembleur qui effectuent au final les appels système (qui bizarrement ne détruisent aucun registre, même pas ra) On connaît donc exactement les registres utiles et détruits de ces fonctions. Il convient de profiter de ce cas particulier. Par exemple, voici le source assembleur de la primitive alloc : sw $a0, 0($fp) sll $a0, $a0, 2 addu $v0, $fp, 4 addu $fp, $v0, $a0 j $ra La sous-routine alloc renvoie dans v0 l'adresse d'une zone de a0 mots de mémoire allouée dynamiquement. Le registre fp est réservé pour servir de pointeur vers la zone de mémoire encore libre. L'examen du code révèle que la sous-routine alloc lit le registre a0 et écrit dans les registres a0 et v0. Notons au passage que fp est réservé, c'est à dire que le code produit ne peut pas l'utiliser, il est donc totalement ignoré. Nous confions désormais le soin de determiner les registres détruits par une sous-routine à une fonction trash qui prend une fonction (un frame) en argument et renvoie la liste des registres potentiellement détruits par cette fonction. Nous nous livrons ici à un comportement de gagne-petit. Dans un compilateur normal, on peut éviter ce genre de suppositions peu rénumératrices et dangereuses (si on réécrit un bout d'assembleur). Si la fonction f a plus de quatre arguments l'appelant doit empiler les arguments en excès. Pour simplifier supposons plutôt que seul le premier argument est passé en registre et que f a trois arguments. Rappelons que le frame de l'appelant de f s'étend de son frame-pointeur au pointeur de pile (registre sp). Si le frame-pointer reside dans un registre fp, l'appelant est libre de modifier sp, il se contente donc d'empiler les paramètres effectifs. Mais nous avons reservé fp pour un autre usage. Qu'à cela ne tienne, nous devons ranger les deuxième et troisième arguments au sommet de la pile, et nous pouvons donc nous repérer par rapport à sp. Mais pour être bien sûrs de ne rien écraser d'important à cette occasion, nous devons signaler à tout le back-end que le sélecteur a besoin de deux mot au sommet de la pile. On opère en avertissant le frame de l'appelant qui doit donc être passé en argument à emit_call (et donc aussi à emit_stm qui appelle emit_call). -------------------------------------------------------------------------------- Figure 7.9: Appel de fonction, passage de deux arguments sur la pile. let emit_store_sp_offset o t = emit (Oper ("sw ^s0,"^string_of_int o^"($sp)", [t], [], None)) let emit_call_1_2 caller_frame f e1 e2 e3 = emit_move_to a0 (emit_exp e1) ; emit_store_sp_offset 0 (emit_exp e2) ; emit_store_sp_offset 4 (emit_exp e3) ; Frame.make_space_for_args caller_frame 2 ; ... -------------------------------------------------------------------------------- La fonction make_space_for_args enregistre la demande en ajustant la taille du sommet du frame de l'appelant en conséquence (il se souvient de la demande maximale). On note donc au passage que le type frame définit une structure de donnée légèrement impérative. -------------------------------------------------------------------------------- Figure 7.10: Partage du frame entre fond (locaux) et sommet (paramètres sortants). -------------------------------------------------------------------------------- La figure 7.10 résume la situation, à la sélection des appels de fonction nous sommes en train de calculer la taille de la zone des paramètres sortants, zone à allouer au sommet du frame de l'appelant. La taille de la zone des locaux, à allouer au fond du frame, sera calculée par l'allocation de registres. La taille totale du frame, size, ne sera donc connue que tout à la fin de la compilation. Sélection des instructions du corps La sélection des instructions du corps d'une fonction s'opère normalement, en itérant emit_stm. Le gros morceau est l'insertion du prologue au début et de l'épilogue à la fin (voir section 6.3.3). Programmatiquement nous avons donc : let emit_fun f body = (* f est le frame *) let saved_callees = emit_prolog f in List.iter (fun i -> emit_stm f i) body ; emit_epilog f saved_callees ; Table.trim_to_list my_table Prologue et épilogue réalisent notre modèle de gestion des environnements des fonctions. Le prologue commence par l'étiquette du point d'entrée de la fonction f. Il procède succesivement aux opérations suivantes : Allouer le frame en pile (diminuer le pointeur de pile). Transférer tous les registres callee-saves dans des temporaires frais, dits sauvegardes des callee-saves. Copier les arguments de leurs positions définies par les conventions d'appel vers les temporaires définis pour eux lors de la génération du code intermédiaire. Pour l'épilogue, qui commence par son étiquette (connue de la structure frame représentant f) la repose est à l'inverse de la dépose, selon la formule irritante de la Revue technique automobile. Si f n'est pas une procédure, copier le temporaire résultat défini lors de la génération du code intermédiaire dans le registre résultat de la convention d'appel (pendant de 3 du prologue). Transférer les sauvegardes des callee-saves dans les callee-saves (repose de 2 du prologue). Rendre l'espace alloué en augmentant le pointeur de pile (repose de 1 du prologue). Revenir de la fonction par l'instruction idoine (repose de l'instruction d'appel). Les étapes 3 du prologue et 1 de l'épilogue sont logiques, elles assurent l'indépendance de la génération de code intermédiaire vis à vis de du processeur ciblé. Elle ne posent qu'un léger problème technique dans le cas des arguments en excès passés en pile. Les étapes 2 du prologue et de l'épilogue sont plus troublantes. Pour les réaliser l'émetteur du prologue renvoie la liste des sauvegardes des callee-saves qui est donnée en argument à l'émetteur de l'épilogue. La fonction f a la responsabilité de rendre les callee-saves dans l'état où elle les a trouvés. Le fonctionnement du processeur ne garantit rien à ce sujet, puisque toute écriture dans un registre est visible de partout. Mais la sémantique des temporaires garantit qu'un temporaire reste insensible aux appels de fonctions que f peut effectuer. Donc, comme le code de f se gardera bien de toucher aux sauvegardes des callee-saves, la combinaison de l'étape 2 du prologue et de l'étape 2 de l'épilogue garantit que f fait face à ses responsabilités. Soit s0 un callee-save, en pratique on s'attend à l'un où à l'autre des scénarios suivants. Si le code de f ne touche pas au registre s0, alors son temporaire de sauvegarde sera un registre et idéalement ce registre sera s0 lui même. Dès lors, les transferts entre s0 et sa sauvegarde seront éliminés du code. Si le code de f touche au registre s0, alors son temporaire de sauvegarde sera une case de la zone des locaux du frame de f. La sauvegarde de s0, s'effectuera donc en pile. L'allocateur de registres se dénommerait donc moins publicitairement, allocateur de registres ou de cases de piles. Reste enfin la dernière étape 4 de l'épilogue. L'emission de l'instruction de retour d'une fonction qui rend son résultat dans v0 se fait ainsi : emit (Oper "j $ra", v0::callee_save_registers, [], Some []) (Pour une procédure les temporaires sources de l'instruction de retour ne comprennent pas v0) On remarque d'abord que les sauts indiqués sont Some [], ce qui signifie qu'il y a bien saut mais que la destination est inconnue. L'instruction de retour lit effectivement le seul registre ra qui est inclus dans la liste des calle-saves. Et il est assez logique de considérer que f doit présenter à sa dernière instruction le registre ra dans l'état où elle l'a trouvé. Mais du point de vue de l'usage qui peut être fait des registres machine, l'instruction de retour remplace toutes les instructions qui peuvent suivre au cours de l'exécution. Or, la suite du code de l'appelant peut selon les conventions d'appel lire v0 et les (vrais) callee-saves en toute confiance. Plus précisément, l'appelant doit, quand il lira ces registres, y trouver ce qu'il croit qu'ils contiennent, à savoir le resultat de l'appel pour v0 le cas échéant, et un contenu inchangé pour les callee-saves. Les autres registres (arguments et caller-saves) ne sont pas un problème car l'appelant sait toujours selon ces mêmes conventions que leur contenu n'est plus fiable. (voir les registres « écrits » par l'instruction d'appel). Enfin, on peut aussi inclure les registres spéciaux (genre zero, sp, etc.) dans la liste des sources de l'instruction de retour. Je n'en voit pas trop l'intérêt, car ces registres sont réservés c'est à dire que leur usage n'est pas contrôlé selon le mécanisme général des temporaires lus et écrits par les instructions d'appel et de retour de sous-rou

Microsoft Word est un logiciel considéré comme étant le traitement de texte vedette de Microsoft.

Sa première version a été distribuée en 1983 sous le nom de Mult-Tool Word (Multi-Outil de traitement de texte) et dédié au système d'exploitation Xenix qui était une version du système Unix à la fin des années 1970.

Des versions futures furent écrites pour plusieurs autres plates-formes dont IBM PC sous système d'exploitation DOS en 1983, Apple Macintosh en 1984, SCO UNIX, OS/2 et les premières versions Microsoft Windows en 1989.

Word a été intégré en tant qu'élément de la suite Microsoft Office depuis 1993 même s'il était également vendu seul ou inclus dans la suite Microsoft Works.

Depuis 2003, la version de Word a vu son appellation modifiée afin de souligner le fait qu'il fait partie intégrante de la suite Microsoft Office ; Microsoft a donc décidé le renommer Microsoft Office Word au lieu de Microsoft Word. La dernière version en date est la version 2007 ; elle fait partie de la suite Microsoft Office 12.

Un logiciel de traitement de texte couvre deux notions, assez différentes en pratique : un éditeur de textes interactif et un compilateur pour un langage de mise en forme de textes (notions que nous précisons dans l'article plus général Traitement de texte).

Au cours de son évolution, Word a intégré l'outil de dessin qui permet d'effectuer des opérations de publication comme l'ajout de graphiques (diagrammes, graphiques économiques, formes géométriques, illustrations, équations) aux documents.

Microsoft Word 2007 intègre un système de menu d'un nouveau genre où les sous-menus n'apparaissent pas sous forme de texte mais sous forme de barre d'icône changeant de contenu.

Sommaire [masquer] 1 Historique 1.1 Word de 1981 à 1989 1.2 Word de 1990 à 1995 1.3 Microsoft Word 5.1a (Macintosh) 1.4 Word 6.0 1.5 Le projet Pyramide 1.6 Évolution de Word 1.7 Word 97 1.8 Word 98 1.9 Word 2000 1.10 Word 2001 et Word 2002 - Word 10 1.11 Word 2003 1.12 Word 2004 1.13 Word 2007 1.14 Word 2008 2 Les formats des fichiers Word 2.1 Le format binaire 2.2 La naissance du HTML dans les documents 2.3 Le format binaire et OLE 2.3.1 Décomposition grossière d'un document 2.3.2 L'universalité des formats 2.4 Le format ouvert Microsoft Office Open XML 3 Caractéristiques et critiques 3.1 Outils de mise en forme 3.2 Polices et alignement 3.3 Les styles 3.4 Objets OLE 3.5 Sections et mise en page 3.6 Les champs 3.7 Création de tableaux dans les documents 3.8 Le sommaire automatique 3.9 Le résumé automatique 3.10 Le modèle Normal.dot 4 Les macros 4.1 Word Basic pour Word 6.0 4.2 Visual Basic Editor (VBE) 4.3 Les virus dans les macros 5 Les critiques du logiciel 5.1 La calligraphie 5.2 Les puces et la numérotation 6 Vocabulaire lié au logiciel Word 7 Les différentes versions de Word 8 Notes 9 Voir aussi 9.1 Articles connexes 9.2 Liens externes

<script type="text/javascript"></script>

Historique [modifier]

Word de 1981 à 1989 [modifier]

Word fut le premier logiciel de traitement de texte populaire pour compatibles PC à utiliser le mode graphique pour montrer immédiatement les mises en forme…

Beaucoup de concepts et d'idées sont issues du premier éditeur WYSIWYG implanté en 1974 sur le système Bravo (Le PC Xerox Alto). Cette machine originale de traitement de texte développée par Xerox a permis à Word d'exister. Charles Simonyi, le créateur de Bravo a quitté le parc Xerox pour rejoindre et travailler chez Microsoft en 1981.

Par la suite, Simonyi débaucha Richard Brodie qui avait également travaillé avec lui sur le projet Bravo, pour venir le rejoindre chez Microsoft.

Le 1^er février 1983, le développement de ce qui allait être nommé Multi-Tool Word commença.

Microsoft sortit le programme le 25 octobre 1983 pour IBM PC en le rebaptisant Microsoft Word .

Des versions de démonstration furent distribuées dans le magazine Monde de PC en novembre 1983 faisant de Microsoft Word, le premier programme à être distribué sur disquettes dans un magazine. Toutefois, le pli n’a pas bien pris et cette initiative n’a pas eu de répercussions probantes sur les ventes face à des produits rivaux comme WordPerfect.

Word a élaboré le concept du WYSIWYG, en d’autres termes, Ce que Vous Voyez Est Ce que Vous Obtenez . Il fut la première application capable d’offrir la possibilité d’afficher les polices de caractères en gras et en italique sur système IBM et autre compatible PC . Par ailleurs, Word implémenta l’usage intégral de la souris qui était jusqu’alors inhabituel et Microsoft proposa même une solution packagée Word avec souris offerte.

Même si MS-DOS restait un système dit en mode caractères, Microsoft Word était le premier traitement de texte pour l'IBM PC à pouvoir afficher de véritables sauts de ligne ainsi que les différents styles de police de caractères comme la mise en gras ou en italique directement sur l'écran. Pour autant, Word n’était pas un authentique système WYSIWIG du fait que la résolution disponible des machines utilisées ne permettait pas d’afficher la taille réelle des caractères.

Les précédents traitements de texte sous MS-DOS, comme WordStar et WordPerfect, utilisaient plutôt le mode texte (80 colonnes et 25 à 50 lignes) avec des codes de mise en page ou quelquefois, des couleurs différentes. Jusqu'alors, un éditeur de texte restait un programme qui permettait de saisir et modifier interactivement des textes et n'était pas vraiment concerné par la mise en forme.

Word de 1990 à 1995 [modifier]

Microsoft Word 5.1a (Macintosh) [modifier]

La première version de Word pour Windows a été publiée en 1989 au prix de 500 dollars US. Avec la parution de Windows 3.0 l'année suivante, les ventes ont commencé à reprendre (La version 1.0 de Word pour Windows a été conçue pour être utilisée avec Windows 3.0 mais offrait des performances moindres que la première version publiée auparavant avec la première de Windows disponible).

Word 1.0 pour Windows
Développeur	Microsoft
Environnement	Microsoft Windows
Type	Traitement de texte
Licence	propriétaire EULA

WordPerfect essuya à son tour un échec de sa version pour Windows et sa commercialisation fut aussi une erreur fatale. Toutefois, la version 2.0 de Word finit par voir le jour et se vit reconnue comme une version leader du marché.

Après MacWrite, Word pour Macintosh n'avait jamais eu de concurrents sérieux, bien que les programmes comme Nisus Writer (Traitement de texte de l'époque pour Apple Macintosh) proposaient déjà des caractéristiques comme la sélection non contiguë qui n'a été implémentée qu'à partir de la version 2002 (XP) de Word. En parallèle, plusieurs utilisateurs se sont plaints du fait que les mises à jours majeures tardèrent. Deux ans restait une durée bien trop longue pour les utilisateurs professionnels en entreprise.

La version 5.1 de Word pour Macintosh publiée en 1992, était un traitement de texte populaire de par son ergonomie, sa facilité d'utilisation et l'ensemble des ses caractéristiques. Cependant, version 6.0 pour ce même Macintosh qui fut, elle, publiée en 1994 devint une dérision, contrairement à la même version pour Windows. C'était la première fois que Word pour Macintosh et pour Windows portèrent un même numéro de version ; de nombreuses accusations tombèrent à l'égard de sa lenteur et sa grosse consommation de ressource de mémoire . Pour répondre à la demandes des utilisateurs d'Apple, Microsoft offrit une version antérieure 5.1 gratuite à tous ceux ayant acquis une version 6.0. Bien que le numéro de la version précédente pour Windows était la 2.0, Microsoft préféra coordonner les numéros de version pour les deux plateformes.

Quand Microsoft fut informé du problème de l´an 2000, il mit à disposition une version intégrale de Word 5.5 pour DOS au lieu de prioriser une mise à jour.

Word 5.5 pour DOS
Développeur	Microsoft
Environnement	Microsoft Windows
Type	Traitement de texte
Licence	propriétaire EULA

En février 2008, il est encore disponible en téléchargement sur le site Web de Microsoft.

Word 6.0 [modifier]

Word 6.0 fut la seconde tentative de développer une version commune de Word. La première tentative, dont le nom de code était Pyramide, consista à envisager de réécrire complètement la version existante de Word.

Icône de Word 6.0

Cette idée fut abandonnée quand Microsoft se rendit compte du temps que cela nécessiterait vis-à-vis de ses équipes de développement alors que de nouvelles fonctionnalités pouvaient très bien être ajoutées dans ce même laps de temps pour améliorer les versions existantes.

Word 6.0 pour Windows
Développeur	Microsoft
Environnement	Microsoft Windows
Type	Traitement de texte
Licence	propriétaire EULA

Le projet Pyramide [modifier]

Les partisans du projet Pyramide clamèrent qu'une nouvelle version aurait été plus rapide, plus petite et plus stable que la version pour Macintosh déjà publiée et compilé avec la version bêta 2.0 de Visual C++ . A cause de cela, de nombreuses optimisations furent arrêtées (La version 4.2.1 de d’Office a été finalement compilée en utilisant la dernière version du compilateur incluant une couche des API Windows). Le projet Pyramide aura été un projet de réflexion faisant l’objet de nombreuses polémiques, notamment sur le point de vue de la nécessité de redévelopper les applications

Les versions les plus récentes de Word pour Macintosh ne furent pas développées à la hauteur de celles pour Windows  ; pour autant, des fonctionnalités plus appropriées pour tourner sous un environnement Windows furent portées sur les versions pour Macintosh.

Évolution de Word [modifier]

Au cours de l'évolution des versions, Word se vit enrichir de nombreuses fonctionnalités et il devint alors bien plus qu’un simple traitement de texte :

• Un panel d’outils permet d'effectuer des insertions d'objets graphiques divers comme du texte en 3 dimensions, des formes géographiques de base avec quelques effets, des graphiques tels que des diagrammes, des illustrations, des équations etc ;
• Un module des collaboration permettant la relecture selon différents utilisateurs ;
• Un outil de comparaison de documents ;
• Un support de plusieurs langues au sein de différents paragraphes ;
• et bien d'autres fonctionnalités toujours plus élaborées avec les années qui suivirent.

Word 97 [modifier]

Icône de Word 97

La version 97 possède de façon globale les même caractéristiques et performance que la version 2000. Elle fut la première version de Word pour laquelle Microsoft implanta un Assistant Office (le Compagnon Office) sous forme de personnage animé qui faisait son apparition au sein d'une session en cours d'utilisation…

Le compagnon Microsoft Office

Ce fut une tentative de compensation de l'échec de l'interface Microsoft Bob. Celle-ci était dédiée à être installé sur les plateformes Windows 3.1 et 95 dans le but d'offrir une interface non technique pour l'utilisation de Windows au quotidien dans l'objectif de remplacer le Gestionnaire de programmes. Ce projet fut alors abandonné.

Word 98 [modifier]

La version 98 de Word, réservée aux plateformes Macintosh, se vit octroyer le plus grand nombre de caractéristiques de la version 97 pour Windows. Dans le but d'en faire un allié commun aux deux environnements pourtant distincts, Microsoft mit en place une règle de compatibilité entre les deux versions, ce qui ouvrit l'échange de documents d'une plateforme à l'autre. Malheureusement, cette mouture pour Mac ainsi que les versions futures devinrent aussi vulnérables que les versions pour Windows en ce qui concerne les Virus potentiellement implantés dans les macros. Cette nouvelle génération d'attaque jusqu'alors inconnue avait pour but de compromettre les documents Word (mais aussi les classeurs Excel) et cette condition de multiplateforme facilita leur affluence.

Word 2000 [modifier]

Pour la plupart des utilisateurs, le changement le plus prépondérant de la version 2000 de Word fut le presse-papiers qui pouvait contenir plusieurs éléments restituables à souhait. Un second changement, non négligeable fut l'amélioration de l'apparition exagérée du Compagnon Office qui ennuyait plus d'utilisateurs qu'il rendait service : il devint plus discret.

Word 2001 et Word 2002 - Word 10 [modifier]

La version 2001 de Word, sortie en octobre 2000, fut empaquetée dans la suite Microsoft Office pour les plateformes Macintosh et possédait la plupart des caractéristiques de la version 2000 pour Windows. Cette version fut également proposée en version individuelle, dissociée de Microsoft Office ; elle fut rééditée en 2001 pour pouvoir être utilisée dans un environnement Mac OS X.

La version 2002 de Word pour Windows, sortie en octobre 2001, fut empaquetée dans la suite Microsoft Office XP pour les plateformes Windows. Bien que son apparence autant que son interface ressemblait en beaucoup de points à la version 2000, cette version possédait déjà la plus grande partie des caractéristiques de la future version 2003.

Word 2003 [modifier]

Pour la version 2003, la suite Microsoft Office incluant Word fut éditée de telle sorte à ce que la marque Word entre en phase avec le nom de la suite pour devenir officiellement Microsoft Office Word. Les utilisateurs, indifférents à ce changement, continuent d'employer l'une ou l'autre appellation.

Word 2003 pour Windows
Développeur	Microsoft
Environnement	Microsoft Windows
Type	Traitement de texte
Licence	propriétaire EULA

La version 2003 de Word a été l'une des plus utilisées. Microsoft a diffusé cette version à la suite des commentaires et remontées de ses des clients et associer les innovations en rapport avec les versions précédentes en permettant de créer des documents de grande qualité de manière plus efficace.

Word 2004 [modifier]

Une nouvelle mouture de Word pour Macintosh fut éditée en 2004. Quelques mises au point substantielles des différentes applications de la suite Office (Word, Excel PowerPoint) furent effectuées pour s'accorder en partie avec la version 2003 pour Windows. À travers les années, Microsoft proposa différents patches correctifs pour éliminer nativement les macros virus connues à partir de cette version tandis qu'Apple publia différentes pages et une communauté Open Source créa NéoOffice. Word restait le traitement de texte le plus largement utilisé sur Macintosh.

 

Word 2007 [modifier]

Word 2007 est la version la plus récente de Microsoft de Word pour Windows. La version est dotée d'un grand nombre de changements, notamment, le nouveau format XML, une interface graphique totalement remodelée, un éditeur d'équations intégré et un gestionnaire de livres. En parallèle à cela, un module nommé Custom XML et conteneur de données XML a été implémenté dans le but d'être accessible par le modèle objet et le format de fichier de Word, ce qui permet une utilisation conjointe avec les nouvelles caractéristiques (Contrôle de contenu) des documents structurés. La nouvelle interface graphique agit sur les onglets de façon contextuelle ce qui permet d'offrir à l'utilisateur les différentes fonctionnalités en fonction de ce qui est effectué sur le document ou en fonction du contrôle qui possède le focus… Il existe plein d'autres caractéristiques avancées comme :

• Une mini barre d'outils flottante qui fait son apparition sur un mot ou un paragraphe afin d'en changer la mise en forme (ce qui réduit les manipulations du clavier et de la souris),
• De nouveaux composants appelés Quick Parts,
• Une barre d'outils d'accès aux commandes courantes,

• Des composants 'SmartArt (qui permettent une transformation dynamique de certains éléments texte en éléments graphiques),
• etc.

Le nouveau format de document Word 2007 ne permet pas d'être exploité par les anciennes versions de Microsoft Word, que ce soit dans un environnement Windows ou bien Macintosh (respectivement les versions 2003 et 2004). Il existe cependant des convertisseurs compatibles à installer séparément sur ces anciennes versions de manière à pouvoir lire ce format 2007…

Pour pouvoir uniformiser la compatibilité des documents, il est préférable de sélectionner le format Word 2003 au moment de la sauvegarde des documents. La version 2008 de Microsoft Office pour Macintosh permet d'exploiter les documents au format .docx, mais les plus anciennes versions de chacune des plates-formes ne possèdent pas ce privilège.

Word 2008 [modifier]

A l'instar de la version 2007 de Word pour Windows, Word 2008 est la plus récente version pour Macintosh ; elle a été publiée le 15 janvier 2008 et possède la plupart des nouvelles caractéristiques de la version 2007, en particulier le nouveau ruban. Cette même version inclut de façon native le nouveau format XML ouvert Office appelé Open XML .

Les formats des fichiers Word [modifier]

Bien que l'extension .doc ait été utilisée dans beaucoup de versions différentes de Word, le format a en réalité existé sous quatre formats de fichier distincts :

• Word for DOS
• Word for Windows 1.0 et 2.0 pour Windows - Word 4 et 5 pour Mac
• Word 6.0 et Word 95 pour Windows - Word 6.0 pour Mac
• Word 97, 2000, 2002, 2003 et 2007 pour Windows - Word 98, 2001, X, et 2004 pour Mac

La nouvelle extension .docx est représentative des documents exploités par les versions 2007 et 2008 respectivement pour les plateformes Windows et Macintosh.

De ce fait, Microsoft ne garantit pas un affichage uniformément correct des documents sur différentes stations de travail même si deux d'entre elles utilisent la même version de Word. En d'autres termes, cela signifie qu'un destinataire et un expéditeur visionnant un même document peut très bien ne pas être strictement identique.

 

Le format binaire [modifier]

Du fait que Word a été le traitement de texte le plus dominant du marché, le format .doc est devenu de facto le standard le plus populaire des documents texte. Depuis de la version 97 à ce jour et en combinaison avec la naissance d'Internet, le couple de mots « Format & Word » désigne une appellation de format de fichier par défaut des documents texte échangés entre utilisateurs tout comme le format PDF.

Le format RTF (Rich Text Format) a été quant à lui la première initiative de créer un format non-propriétaire qui permettait de pouvoir échanger des documents formatés entre différentes applications. Ce format est disponible dans les formats de documents enregistrables et permet de préserver le contenu et quasiment toute la mise en forme du document.

La naissance du HTML dans les documents [modifier]

Plus tard, juste après l'apparition du langage HTML, Word a pu lui aussi supporter ce format dérivé comme solution complémentaire de préservation du contenu et du format des documents tout comme que le fait le format RTF mais avec une taille de fichier bien moindre.

Cette solution permit en plus de pouvoir visualiser les documents à partir d'un navigateur Web.

Word 2007 utilise par défaut le format XML ouvert comme format par défaut mais conserve les anciens formats des versions précédentes afin de préserver la compatibilité. Il offre également la possibilité d'enregistrer (sans pouvoir les ouvrir après), les documents au format 'PDF' d'Adobe et au format XPS, ce dernier étant voué à concurrencer le format PDF...

Microsoft a publié des pages sur les spécifications techniques des formats binaires des versions 97 à 2007 autant que d'autres pour le format de fichier ouvert Open XML.

Les formats de documents des différentes versions ont changé de façon plus ou moins subtile. Ce format proposé dans cette nouvelle version n'est pas exploitable dans les versions plus anciennes. Toutefois, une certaine forme de compatibilité a perduré entre la version 97 et la version 2003, période où 4 versions de Microsoft Word ont vu le jour.

Le format binaire et OLE [modifier]

Le format binaire de Word des versions 97 à 2007 implémente la technologie OLE (Object Linking and Embedding) de façon structurée de telle sorte à ce ces derniers puissent gérer la structure de celle-ci. OLE se comporte un peu comme le système de fichier d'un disque dur ; il est constitué de plusieurs composants clés.

Décomposition grossière d'un document [modifier]

Chaque document Word est composé de ce que l'on appelle des blocs qui sont presque toujours divisés en portions de 512 octets. C'est pourquoi les documents Word ont toujours des tailles de fichiers qui sont des multiples de 512.

Le stockage de ces blocs est similaire à celui des dossiers d'un disque dur. Le texte d'un document Word est stocké dans la section WordDocument .

• Le premier gros bloc est celui de l'entête du fichier ; il fournit un grand nombre d'informations à propos du document et notamment, l'emplacement des différentes structures de données majeures au sein du document.
• Le bloc Stockages de Propriétés fournit des informations sous forme de méta données sur le contenu du fichier .doc comme par exemple où il commence, son nom et ainsi de suite.
• Le bloc d'informations du fichier contient les spécifications définissant où le texte commence, où il se termine, quelle version de Word a permis sa création et bien d'autres attributs…

L'universalité des formats [modifier]

Les personnes qui n'utilisent pas Microsoft Office se trouvent souvent confrontées à des difficultés lorsqu'il s'agit de pouvoir lire des documents Word. Plusieurs solutions furent alors mises en place. La première fut la mise à disposition par Microsoft d'une visionneuse Word (et aussi PowerPoint) afin de permettre aux intéressés de pouvoir ouvrir sans les modifier les documents Word sur leur PC dans un environnement Windows. Il a également mis à disposition des utilisateurs, des convertisseurs, nécessitant une version appropriée de Word et permettant de convertir au format voulu, tel ou tel document.

Il existe aujourd'hui toutes les solutions pour ouvrir n'importe quel type de document Word, notamment avec le pack de compatibilité 97-2003 depuis la sortie de Word 2007. Mais déjà avec les versions pour Windows 3.x, (1.0, 2.0 et 6.0), il était possible d'ouvrir et d'enregistrer des documents aux formats des versions précédentes.

D'autres solutions concurrentes cette fois, avec l'utilisation de programmes de traitement de textes gratuit sous licence publique Writer issu de la suite OpenOffice.org et AbiWord, petit traitement de textes d'origine espagnole, gratuit lui aussi dans les mêmes conditions (GNU), permettent d'ouvrir et d'enregistrer des documents au format binaire Microsoft Word.

Il y a également la solution Apache Jakarta POI qui est une source ouverte de la librairie Java (Open Source Java library) et qui est à même d'ouvrir et d'enregistrer ce type de documents. Les utilisateurs de Macintosh quant à eux pouvaient utiliser le programme MacLinkPro qui avait la faculté de pouvoir ouvrir indifféremment les fichiers de format Word, Works, WordPerfect, NisysWriteret bien d'autres formats encore. La plupart de ces interopérabilités ont pu être menées grâce au procédé de technologie d'ingénierie inversée (reverse engineering). Excepté le format RTF, aucune documentation sur le format Word n'a été rendue publique et disponible avant février 2008.

Le format ouvert Microsoft Office Open XML [modifier]

Le format de Word mentionné ci-dessus est un format binaire. Microsoft a mis en place un format XML ouvert pour ses applications Office avec la version 2007 : Microsoft Office XML Ouvert. Bien que portant ce nom, le format XML de Microsoft Office ne de conforme pas intégralement au standard de la norme XML. Il est toutefois publiquement documenté sous la norme Ecma 376. Cette publication est une première pour Word et le rend ainsi considérablement plus facile pour l'accessibilité des documents que ce soit pour ses concurrents que pour son interopérabilité.

La volonté de le définir comme une norme standard ISO est une vocation de Microsoft qui voit celle-ci se concrétiser bientôt. Il existe en parallèle un second format XML de base supporté aussi par Word 2003 : ce format est le WordprocessingML qui n'a rien à voir avec le format de fichier ouvert Open XML.

Il est par ailleurs possible (et autorisé) de concevoir des plugins pour Word permettant de pouvoir lire ou enregistrer des documents dotés de format qu'il ne supporte pas nativement.

Caractéristiques et critiques [modifier]

Autant de caractéristiques pour un traitement de texte a soulevé autant de succès que de discordes…

Outils de mise en forme [modifier]

Word se veut à la fois une application intuitive pour les débutants, comme le logiciel le plus complet pour la préparation des ouvrages en amont des logiciels professionnels de mise en page (XPress, InDedig ) avec lesquels il communique. Beaucoup de professionnels du prépresse connaissent ce logiciel et s'en servent.

Si la rédaction de textes courts peut se faire de façon spontanée, la gestion de documents volumineux demande de la rigueur.

Word possède des centaines de commandes correspondant à des tâches particulières, seules certaines sont visibles dans les menus. Le professionnel peut même avoir accès à un langage de programmation évolué pour spécialiser et automatiser les fonctions ou en créer de nouvelles. Exemple : Combien de temps vais-je mettre pour lire le texte sélectionné ?

Polices et alignement [modifier]

Comme tous les logiciels de traitement de texte, Microsoft Word permet de définir les polices utilisées ainsi que les alignements du texte. Ces dispositions seront immédiatement visibles à l'écran.

Notons qu'en mode justifié, Word gère difficilement le gris typographique à la justification ; ainsi, pour maintenir un paragraphe justifié, il peut introduire de très grandes espaces entre les mots, là où un typographe préférerait faire une césure ou bien rompre la justification (fin du mot en retrait ou dépassant dans la marge).

Il n'est pas recommandé d'introduire un trait d'union pour provoquer la césure car le risque à ce qu'il se retrouve dans la ligne suivante, si la justification changeait, était envisageable. Il faut alors gérer automatiquement les césures possibles et éventuellement introduire des autorisations de coupure dans le mot.

Les styles [modifier]

Il convient de distinguer le style, terme usuel, qui modifie directement le caractère (gras, italique, souligné, couleur) et la feuille de style qui est une mémoire du style de texte appliquée à un paragraphe ou à un groupe de mots. Word ne distingue pas ces termes.

Boîte de dialogue de définition des styles (Word 2000)

La feuille de style était présente jusqu'à la naissance des versions pour Windows. Un style, est la base de la composition. Il peut s'exporter du document, être copié et modifié dynamiquement.

Un style est une mise en forme de texte destinée à être appliquée en plusieurs endroits. La modification du style change la mise en forme pour tous les paragraphes ou portions de texte utilisant ce style. Un ouvrage peut comporter de nombreuses feuilles de style.

Si plusieurs paragraphes utilisent une même mise en forme, il faut utiliser un style, sinon on n'utilise pas la fonction principale du traitement de texte et on ne fait que de la bonne dactylographie.

Le style met en mémoire, police, style et attributs, couleur, corps, interlignage, espacement, retraits, alinéa, tabulateurs et spécificités de Word, visibilité, ordre hiérarchique, etc.

Le style de caractère mis en mémoire pour quelques mots du paragraphe ne concerne que le caractère, style et attributs.

On peut rendre les styles actifs, par exemple en mettant le texte dans une couleur juste le temps de vérifier sa répartition dans l'ouvrage. On peut aussi facilement rechercher/remplacer des termes seulement dans une catégorie de texte.

Les styles permettent de séparer le fond de la forme. Lorsque l'on indique que le texte est de style Titre n, on indique la fonction du texte sans indiquer la manière dont il sera mis en forme ; celle-ci est définie dans la boîte de dialogue de gestion des styles. Ainsi, pour les titres de chapitre ou de section, il est recommandé d'utiliser les styles Titre 1, Titre 2, … ce qui permettra de construire la table des matières automatiquement. Un utilisateur peut définir ses propres styles, par exemple créer un style Patronyme pour les noms de famille (qui figurent en petites capitales) dans les listes ou exergues mais jamais dans les textes.

En outre, l'utilisateur peut rechercher tous les éléments de texte d'un style de caractère donné, par exemple pour en faire une liste (ceci peut être automatisé par une macro-instruction).

Objets OLE [modifier]

Sous Microsoft Windows, on peut intégrer des objets OLE (qui est une technologie propriétaire Microsoft), qui permet d'exploiter des propriétés propres à l'objet et à l'application qui l'a créé, avec l'inconvénient que l'application en question est indispensable à la lecture du document.

Par exemple, si on copie un graphique fait sous Microsoft Excel et qu'on le colle en utilisant l'option Collage spécial Graphique Microsoft Office Excel Objet, on peut alors éditer le graphique sous Word comme si l'on était sous Excel (y compris modifier les valeurs des cellules dans les feuilles de calcul).

L'éditeur d'équation, Microsoft Equation, insère des objets OLE en s'exécutant à l'intérieur de Word.

Un objet n'est pas nécessairement OLE. On peut insérer un graphique ou une image comme un simple [modifier], sans qu'il soit lié à l'application qui l'a créé. Les équations peuvent aussi être représentées par des champs, sans faire appel à aucun éditeur d'équation.

Il est à noter que sur Mac, lorsqu'on insère des objets OLE dans Word, ceux-ci ne sont plus reconnus comme tels dans Word sous Windows. Il apparaissent alors comme simples images. Ceci peut poser de sérieux problèmes de portabilité entre les deux plateformes. Plus grave, Word 2008 pour Mac ne reconnaît même plus les objets OLE, même quand ils viennent d'être collés dans un document créé avec cette même application.

Sections et mise en page [modifier]

La mise en page — c'est-à-dire pour Word le format de feuille (A4, letter…), l'orientation (paysage, portrait), les marges, la numérotation des pages, les en-têtes et pieds de page — peut différer d'une partie à l'autre du document. Un saut de section peut coïncider avec un saut de page, un saut de colonne (si le texte est sur plusieurs colonnes) ou bien être continu.

La mise en page est définie pour une section. Insérer un saut de saut de section (section break) la fait varier d'une page sur l'autre : autorisant de montrer un tableau en pleine page au format paysage alors que le reste du document est en portrait.

Lorsque le saut de section est un saut de page, on peut imposer que la nouvelle page soit paire ou impaire ; cela permet par exemple de toujours commencer un chapitre sur une page impaire, Word se chargeant d'ajouter une page blanche si nécessaire. On peut imposer que le première page d'une section soit différente des autres, par exemple que son en-tête soit différente, comme cela se fait pour une première page de chapitre. On peut donc avoir à insérer un saut de section même s'il n'y a pas de variation de mise en page.

Les champs [modifier]

Un champ est un texte généré automatiquement à partir du contenu du reste du document.

Parmi les nombreux champs citons : la tables des matières (générée à partir des titres de chapitre et de section), l'index (généré à partir des champs entrées d'index ), le numéro de page, le nom du chapitre courant, le numéro du chapitre, des calculs numériques (ex {a + b/2}), ...

Un champ est figuré sous la forme d'un code de champs entre accolades sur fond gris ou par sa valeur sur fond gris.

Ainsi, le code {TOC \o 1-3} génère une table des matières (TOC, table of contents) référençant les titres de niveau 1 à 3 (c'est-à-dire titres de chapitre, de section et de sous-section). Ce code est remplacé par du texte au moment de l'impression, ou sur requête de l'utilisateur (mise à jour des champs). Il n'est en général pas nécessaire de connaître les codes, celui-ci est généré à partir des options sélectionnées au moment de l'insertion du champ.

Création de tableaux dans les documents [modifier]

La création de tableaux dans Word à été possible dès les premières versions de Word pour Windows. En parallèle à cela, Word peut au sein de ces tableaux, effectuer des calculs simples entre cellules, en ligne ou en colonne. Il est également possible de mettre en place des formules prédéfinies.

Le sommaire automatique [modifier]

Word propose un générateur de sommaire automatique dépendant des styles de titres hiérarchisés dans le document. Il peut ainsi créer automatiquement des tables des matières, des listes d'index pour afficher par exemple un glossaire etc.

Le résumé automatique [modifier]

Word fournit un outil de résumé automatique qui permet de mettre en évidence les mots ou expressions jugées importantes. L'utilisateur peut définir les paramètres de pourcentage de texte à conserver par rapport la quantité totale du texte. Ron Fein de l'équipe de Word 97 explique que ce système fonctionne par coupure de mots en fonction de la pertinence des phrases. Dans un premier temps, Word identifie les mots les plus courants dans le document en ignorant les mots comme un, une, le, la, etc, puis attribut un rang pour ceux d'entre-eux qui sont le plus utilisés ; il peut alors établir un score. C'est par un processus d'opérations de division et de moyenne du nombre de mots par rapport aux phrases que Word parvient à proportionner un résultat et d'en retourner un résumé.

Le modèle Normal.dot [modifier]

Normal.dot est le modèle principal à partir duquel tous les documents vierges sont créés. Il est l'un des fichiers les plus importants dans Microsoft Word. Il permet de définir toutes les caractéristiques d'un document et en particulier, les marges et les polices de caractères par défaut. Ce modèle est fourni avec des caractéristiques par défaut que tout utilisateur peut changer à sa convenance et en fonction de ces besoins. Tout changement sur ce modèle impactera tous les nouveaux documents générés et tous ceux dont l'option de mise à jour automatique des styles de formatage est activée.

Les macros [modifier]

Toit comme les autres documents de la suite Microsoft Office, les fichiers Word peuvent embarquer des macros et autres programmes incorporés.

Word Basic pour Word 6.0 [modifier]

Nativement, ce fut la version 6.0 (et par voie de conséquence la version 95) qui bénéficia de ce privilège avec le langage WordBasic :

Word Basic (Word 6.0 pour Windows)
Développeur	Microsoft
Environnement	Microsoft Windows
Type	Outil de génération de macro dans Word
Licence	propriétaire EULA

Un module Programmation avec Microsoft Word puissant pemettant de créer des programmes et des application dans Word.

Ce mode de programmation sommaire fut remplacé par Visual Basic pour Application (VBA) à partir de la version 97.

Visual Basic Editor (VBE) [modifier]

Le successeur de WordBasic est également un éditeur de macros que Microsoft a nommé Visual Basic Editor (VBE). C'est l'environnement de développement où la modification et l'enrichissement de macros enregistrées voire celle de programmes en Visual Basic est possible.

• Il comporte une gestion des références (Librairies externes).
• La création la modification ou suppression des procédures et macros dans vos documents.
• La génération d'objets dynamiques avec association d'événements.

Visual Basic Editor (VBA)
Développeur	Microsoft
Environnement	Microsoft Windows
Type	Traitement de texte
Licence	propriétaire EULA

Avec l'ensemble des composants disponibles dans Visual Basic, de nombreuses possibilité étaient dès lors offertes aux développeurs. La gestion des contrôles ActiveX (composants actifs réutilisables dans vos applications) qui offrent souplesse et puissance par le biais de fonctions avancées comme l'accès aux bases de données, la gestion des fichiers locaux ou en réseau, l'échange de données, etc.

Les virus dans les macros [modifier]

La puissante évolution de la gestion des macros a pu permettre à de nombreuses personnes malveillantes de propager des virus à travers les documents.

La tendance qu'ont les utilisateurs à s'échanger des documents via un E-Mail, une clé USB, un CD ROM ou même encore aujourd'hui sur disquette sont les principaux vecteurs de leur propagation.

Le plus prédominant de ces virus a été le ver Melissa mais un grand nombre d'autres virus a vu le jour grâce à cette opportunité ouverte des macros . Certains logiciel antivirus peuvent depuis détecter et nettoyer des macros virus connus. Certains pare-feux peuvent eux aussi empêcher la propagation de virus sous cette forme vers d'autres systèmes.

Ces macros virus sont les seules menaces connues des plateformes Windows et Macintosh. Elles furent uniquement le vecteur d'infections visant à affecter les systèmes Windows et MacOS X allant jusqu'à l'apparition de CODEC vidéo sous forme de Cheval de Troie en 2007. Ce fut au cours des ces mésaventures que Microsoft mis à disposition des packs correctifs voués à éliminer et lutter contre ces virus.

Un processus d'alerte macro fait alors son apparition dès qu'un document contenant des macros est ouvert. Le procédé est ajustable par palier de degré de sévérité par l'utilisateur lui-même mais dans les versions récentes de Word, cette option est définie au plus haut niveau par défaut afin de prévenir les risques et paradoxalement à cela, ces macros virus se font de plus en plus rares.

Dans la version 2007 de Word, un utilisateur souhaitant enregistrer un document avec des macros est contraint de choisir le format approprié, à savoir .docm pour un document ou .dotm pour un modèle. Le fait de voir ces extensions permet de savoir que ce document ou ce modèle de document est pourvu de macros embarquées.

Les critiques du logiciel [modifier]

Avec autant de caractéristiques, Word s'est vu un grand succès mais aussi quelques critiques...

La calligraphie [modifier]

Que ce soit pour Windows ou pour Macintosh, Word n'a jamais été en mesure de manipuler les ligatures définies sur certaines polices de caractères TrueType à cause des problèmes qui pourraient être rencontrés lors d'éventuelles corrections orthographiques. Ce type de police peut toutefois être inséré manuellement mais n'est pas reconnu par Word par ce qu'il représente.

Une autre caractéristique de Word est son incapacité à pouvoir exploiter des espaces réduits lors de la mise en forme du texte en mode justifié notamment mais aussi les repères de rognage. Diverses solutions de contournement furent alors développées. Le processus de substitution de police de caractère a été mis en place à partir de la version 2002 pour contourner le problème rencontré lorsqu'une certaine police employée dans un document était indisponible sur le système en cours : il n'est pas prévu de pouvoir désactiver ce comportement par défaut.

Dans la version 2004 de Word pour Macintosh, le support de l'écriture complexe était aussi faible que pour la version 97 de Word pour Windows et Word n'a jamais su interpréter la typographie avancée des systèmes Apple gérant parfaitement ces fameuses ligatures et autant de variétés de glyphes.

Les puces et la numérotation [modifier]

Quelques utilisateurs ont soulevé que le système de numérotation des paragraphes par puces ou par numéros est fortement problématique et en particulier lorsqu'il s'agit de reprendre la numérotation à partir d'un nouveau jeu de paragraphes. Toutefois, il s'avère que ce dernier a été considérablement révisé depuis la version 2007 de Word. Il a été aussi rapporté que ce comportement était d'autant plus ennuyeux qu'en comparaison aux autres traitements de texte comme par exemple Openoffice.org, ce système était pauvre en fonctionnalités par rapport aux besoins.

Les problèmes relevés à l'égard des puces et des numéros dans Word comprennent notamment :

• l'altération ou le changement inattendu des caractères représentant les puces,
• l'indentation qui changeait au sein d'une même hiérarchie de paragraphe
• ou encore, les séquences de numérotation qui ne correspondaient pas entre-elles.

En dehors de cela et dans la majeure partie des cas, le système restait tout de même opérationnel et voyait sa vulnérabilité naître à cause des langues des correcteurs orthographiques installés autres que le français et l'anglais…

Vocabulaire lié au logiciel Word [modifier]

Barre d'outils: Barres intégrés à la page de travail du traitement de texte contenant les raccourcis principaux sous forme d'icône.

Justifié: Permet d'aligner le texte a droite et a gauche.

Lettrine: Première lettre d'un paragraphe ou d'un texte qui occupe la hauteur de plusieurs ligne.

Icône: Image symbolisant une fonction. Celle ci apparait en passant la souris dessus.

Modèle: La procédure de création de modèles de documents rajoute automatiquement au nom du modèle l'extension .DOT. Cette extension est obligatoire pour le bon fonctionnement du modèle.

Les différentes versions de Word [modifier]

PC et compatibles (environnement MS-DOS)

1983 — Word 1

1985 — Word 2

1986 — Word 3

1987 — Word 4 (Microsoft Word 4.0 pour PC)

1989 — Word 5

1991 — Word 5.1

1991 — Word 5.5

1993 — Word 6.0 pour Windows

Macintosh (Mac OS et Mac OS X)

1985 — Word 1 for the Macintosh

1987 — Word 3

1989 — Word 4

1991 — Word 5

1993 — Word 6

1998 — Word 98

2000 — Word 2001, la dernière version compatible avec Mac OS 9

2001 — Word X, la première version pour Mac OS X seulement

2004 — Word 2004, faisant partie de la suite Office 2004 pour Mac

2008 — Word 2008 faisant partie de la suite Office 2008 pour Mac

PC et compatibles(environnement Windows)

Novembre 1989 — Word pour Windows 1.0 pour Windows 2.x, nom de code : Opus

Mars 1990— Word 1.1 pour Windows 3.0, Nom de code : Bill the Cat

Juin1990 — Word 1.1a pour Windows 3.1

1991 — Word 2.0 pour Windows, Nom de code : Spaceman Spiff

1993 — Word pour Windows 6.0, nom de code T3 (Cette version a été renommée 6.0 pour s'accorder avec la version pour DOS et Macintosh mais aussi pour son concurrent direct WordPerfect et enfin pour la version 32-bit de Windows NT)

1995 — Word pour Windows 95 (version 7.0) faisant partie de la suite Office 95

1997 — Word 97 (version 8.0) faisant partie de la suite Office 97

1998 — Word 98 (version 8.5) faisant partie de la suite Office 97 – Cette version a été produite uniquement pour le Japon et la Corée.

1999 — Word 2000 (version 9.0) faisant partie de la suite Office 2000

2001 — Word 2002 (version 10.0) faisant partie de la suite Office XP

2003 — Word 2003 (Officiellement nommé Microsoft Office Word 2003) - (version 11.0) faisant partie de la suite Office 2003

2006 — Word 2007 (Officiellement nommé Microsoft Office Word 2007) - (version 12.0) faisant partie de la suite Office 2007 – La version pour les enterprises 30 novembre 2006 et c'est le 30 janvier 2007 que l'on pouvais se procurer une version en magasin.

Versions pour SCO UNIX

Microsoft Word pour UNIX Systems version 5.1

Versions pour OS/2

1992 — Microsoft Word pour OS/2 version 1.1B

Notes [modifier]

• (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Microsoft Word ».

Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des données sous forme binaire, ou bits. Cette machine permet de traiter des informations selon des séquences d'instructions prédéfinies, appelées aussi programmes.

Elle interagit avec l'environnement grâce à des périphériques comme le moniteur, le clavier, le modem, le lecteur de CD, la carte graphique (liste non-exhaustive). Les ordinateurs peuvent être classés selon plusieurs critères^[1] (domaine d'application, taille ou architecture).
Historique [modifier]

En 1936, la publication de l'article fondateur de la science informatique (en)On Computable Numbers with an Application to the Entscheidungsproblem par Alan Mathison Turing allait donner le coup d'envoi à la création de l'ordinateur programmable. Il y présente sa machine de Turing, le premier calculateur universel programmable, et invente les concepts de programmation et de programme.

Peu avant la seconde guerre mondiale apparurent les premières calculatrices électromécaniques, construites selon les idées d'Alan Turing. Les machines furent vite supplantées par les premiers calculateurs électroniques, nettement plus performants.

Le premier ordinateur fonctionnant en langage binaire fut le Colossus, conçu lors de la 2^e guerre mondiale, il n'était pas Turing-complet bien qu'Alan Turing ait travaillé au projet. À la fin de la guerre, il fut démonté et caché à cause de son importance stratégique. L'ENIAC, créé en 1945, est le premier ordinateur entièrement électronique construit pour être Turing-complet.

Le mot ordinateur fut introduit par IBM France en 1955. François Girard, alors responsable du service publicité de l'entreprise, eut l'idée de consulter son ancien professeur de lettres à Paris, Jacques Perret, afin de lui demander de proposer un mot caractérisant le mieux possible ce que l'on appelait vulgairement un calculateur (traduction littérale du mot anglais « computer »). Ce dernier proposa « ordinateur », un mot tombé en désuétude désignant anciennement un ordonnateur, voire la notion d'ordre ecclésiastique dans l'église catholique (ordinant)^[2],[3]. Le professeur suggéra plus précisément « ordinatrice électronique », le féminin ayant pu permettre, selon lui, de mieux distinguer l'usage religieux de l'usage comptable du mot.^[4],[5]

 

Généralités [modifier]

Les ordinateurs furent d'abord utilisés pour le calcul (en nombres entiers d'abord, puis flottants).

• On ne peut cependant les assimiler à de simples calculateurs : en effet, le résultat du traitement d'un ordinateur peut être non seulement une série de nombres, mais aussi un nouveau programme (utilisable par cet ordinateur ou par un autre).
• Dans l'architecture de von Neumann, les données sont banalisées et peuvent être interprétées indifféremment comme des nombres, des instructions, des valeurs logiques ou tout symbole défini arbitrairement (lettre de l’alphabet, par exemple).

• Le calcul représente une des applications possibles. Dans ce cas, les données sont traitées comme des nombres.
• L’ordinateur est utilisé aussi pour ses possibilités d'organisation de l’information, entre autres sur des périphériques de stockage magnétique. On a calculé à la fin des années 1980 que sans les ordinateurs il faudrait toute la population française juste pour faire dans ce pays le seul travail des banques.
  • Cette capacité d’organiser les informations a généralisé l’usage du traitement de texte dans le grand public ;
  • la gestion des bases de données relationnelles permet également de retrouver et de consolider des informations réparties vues par l'utilisateur comme plusieurs tables indépendantes.

Cette création d'un néologisme fut à l'origine de traductions multiples des expressions Supercomputer, superordinateur ou supercalculateur, et Quantum computer, calculateur quantique ou ordinateur quantique. Dans ce dernier cas, l'utilisation du mot "ordinateur" est justement surfaite car les possibilités envisageables pour le calcul quantique sont loin de la polyvalence d'un "ordinateur".

L’expérience a appris à distinguer dans un ordinateur deux aspects, dont le second avait été au départ sous-estimé :

• l’architecture physique, matérielle (alias hardware ou hard) ;
• l’architecture logicielle (alias software ou soft) ; un ordinateur très avancé techniquement pour son époque comme le Gamma 60 de la compagnie Bull n’eut pas le succès attendu, pour la simple raison qu’il existait peu de moyens de mettre en œuvre commodément ses possibilités techniques. Le logiciel - et son complément les services (formation, maintenance, etc.) - forme depuis le milieu des années 1980 l’essentiel des coûts d’équipement informatique, le matériel n’y ayant qu’une part minoritaire.

Les ordinateurs pourraient être sensibles aux bombes EMP.

Fonctionnement d’un ordinateur [modifier]

Parmi toutes les machines inventées par l'homme, l'ordinateur est celle qui se rapproche le plus du concept anthropologique suivant :

Organe d'entrée. Organe de traitement de l'information. Organe de sortie

Chez l'homme les organes d'entrée sont les cinq sens, l'organe de traitement est le cerveau dont les logiciels sont l'apprentissage avec des mises à jour constantes en cours de vie, puis les organes de sortie sont les muscles. Pour les ordinateurs modernes les organes d'entrée sont le clavier et la souris et les organes de sortie, l'écran, l'imprimante, le graveur de DVD etc.

Les techniques utilisées pour fabriquer ces machines ont énormément changé depuis les années 1940 et sont devenues une technologie (c’est-à-dire un ensemble industriel organisé autour de techniques) à part entière depuis les années 1970. Beaucoup utilisent encore les concepts définis par John von Neumann, bien que cette architecture soit en régression : les programmes ne se modifient plus guère eux-mêmes (ce qui serait considéré comme une mauvaise pratique de programmation), et le matériel prend en compte cette nouvelle donne en séparant aujourd'hui nettement le stockage des instructions et des données, y compris dans les caches.

L’architecture de von Neumann décomposait l’ordinateur en quatre parties distinctes :

1. L’unité arithmétique et logique (UAL) ou unité de traitement : son rôle est d’effectuer les opérations de base, un peu comme le ferait une calculette.
2. L’unité de contrôle. C’est l’équivalent des doigts qui actionneraient la calculette.
3. La mémoire qui contient à la fois les données et le programme qui dira à l’unité de contrôle quels calculs faire sur ces données. La mémoire se divise entre mémoire volatile (programmes et données en cours de fonctionnement) et mémoire permanente (programmes et données de base de la machine).
4. Les entrées-sorties : dispositifs qui permettent de communiquer avec le monde extérieur.

UAL et UC [modifier]

L’unité arithmétique et logique ou UAL est l’élément qui réalise les opérations élémentaires (additions, soustractions, etc.), les opérateurs logiques (ET, OU, NI, etc.) et les opérations de comparaison (par exemple la comparaison d’égalité entre deux zones de mémoire). C’est l’UAL qui effectue les calculs de l’ordinateur.

L’unité de contrôle prend ses instructions dans la mémoire. Celles-ci lui indiquent ce qu’elle doit ordonner à l’UAL et, comment elle devra éventuellement agir selon les résultats que celle-ci lui fournira. Une fois l’opération terminée, l’unité de contrôle passe soit à l’instruction suivante, soit à une autre instruction à laquelle le programme lui ordonne de se brancher.

L'unité de contrôle facilite la communication entre l'unité arithmétique et logique, la mémoire ainsi que les périphériques. Il gère la plupart de l'exécution des instructions dans l'ordinateur.

Mémoire [modifier]

Au sein du système, la mémoire peut être décrite comme une suite de cellules numérotées contenant chacune une petite quantité d’informations. Cette information peut servir à indiquer à l’ordinateur ce qu’il doit faire (instructions) ou contenir des données à traiter. Dans la plupart des architectures, c'est la même mémoire qui est utilisée pour les deux fonctions. Dans les calculateurs massivement parallèles, on admet même que des instructions de programmes soient substituées à d’autres en cours d’opération lorsque cela se traduit par une plus grande efficacité. Cette pratique était jadis courante, mais les impératifs de lisibilité du génie logiciel l'ont fait régresser, hormis dans ce cas particulier, depuis plusieurs décennies.

Cette mémoire peut être réécrite autant de fois que nécessaire. La taille de chacun des blocs de mémoire ainsi que la technologie utilisée ont varié selon les coûts et les besoins : 8 bits pour les télécommunications, 12 bits pour l’instrumentation (DEC) et 60 bits pour de gros calculateurs scientifiques (Control Data). Un consensus a fini par être trouvé autour de l’octet comme unité adressable et d’instructions sur format de 4 ou 8 octets.

Dans tous les cas de figure, l'octet reste adressable, ce qui simplifie l'écriture des programmes.

Les techniques utilisées pour la réalisation des mémoires ont compris des relais électromécaniques, des tubes au mercure au sein desquels étaient générées des ondes acoustiques, des transistors individuels, des tores de ferrite et enfin des circuits intégrés incluant des millions de transistors.

Entrées-Sorties [modifier]

Les dispositifs d’entrée/sortie permettent à l’ordinateur de communiquer avec l’extérieur. Ces dispositifs sont très importants, du clavier à l’écran.

Le point commun entre tous les périphériques d’entrée est qu’ils convertissent l’information qu’ils récupèrent de l’extérieur en données compréhensibles par l’ordinateur. À l’inverse, les périphériques de sortie décodent l’information fournie par l’ordinateur afin de la rendre compréhensible par l’utilisateur.

Bus [modifier]

Ces différentes parties sont reliées par trois bus, le bus d'adresse, le bus de données et le bus de commande. Un bus est un groupement d'un certain nombre de fils électriques réalisant une liaison pour transporter des informations binaires codées sur plusieurs bits.

• Le bus d'adresse transporte les adresses générées par l'U.C.T. (Unité Centrale de Traitement) pour sélectionner une case mémoire ou un registre interne de l'un des blocs. Le nombre de bits véhiculés par ce bus dépend de la quantité de mémoire qui doit être adressée.
• Le bus de données transporte les données échangées entre les différents éléments du système.
• Le bus de contrôle transporte les différents signaux de synchronisation nécessaires au fonctionnement du système : signal de lecture (RD), signal d'écriture (WR), signal de sélection (CS : Chip Select).

Architecture [modifier]

La miniaturisation permet d’intégrer l’UAL et l’unité de contrôle au sein d’un même circuit intégré connu sous le nom de microprocesseur.

• Typiquement, la mémoire est située sur des circuits intégrés proches du processeur, une partie de cette mémoire, la mémoire cache, pouvant être située sur le même circuit intégré que l’UAL.
• L’ensemble reste sur la plupart des architectures complété d’une horloge qui cadence le processeur. Bien sûr, on souhaite qu'elle soit le plus rapide possible, mais on ne peut pas augmenter sans limites sa vitesse pour deux raisons :
  • plus l’horloge est rapide et plus il chauffe toutes choses égales par ailleurs, comme le carré de sa fréquence. Une trop grande température peut le détériorer ;
  • il existe une cadence où le processeur devient instable; son comportement devient erratique ce qui amène le plus souvent à des plantages.
• La tendance a été à partir de 2004 de regrouper plusieurs UAL dans le même processeur, voire plusieurs processeurs dans la même puce. En effet, la miniaturisation progressive (voir Loi de Moore) le permet sans grand changement de coût. Une autre tendance, depuis 2006 chez ARM, est aux microprocesseurs sans horloge : la moitié de la dissipation thermique est en effet due aux signaux d'horloge quand le microprocesseur fonctionne ; de plus, un microprocesseur sans horloge a une consommation presque nulle quand il ne fonctionne pas : le seul signal d'horloge nécessaire est alors celui destiné au rafraîchissement des mémoires. Cet atout est important pour les modèles portables.
• Le principal écart fonctionnel aujourd’hui par rapport au modèle de Von Neumann est la présence sur certaines architectures de deux antémémoires différentes : une pour les instructions et une pour les données (alors que le modèle de Von Neumann spécifiait une mémoire commune pour les deux). La raison de cet écart est que la modification par un programme de ses propres instructions est aujourd’hui considérée (sauf sur les machines hautement parallèles) comme une pratique à proscrire. Dès lors, si le contenu du cache de données doit être récrit en mémoire principale quand il est modifié, on sait que celui du cache d’instructions n’aura jamais à l’être, d’où simplification des circuits et gain de performance.

Instructions [modifier]

Les instructions que l’ordinateur peut comprendre ne sont pas celles du langage humain. Le matériel sait juste exécuter un nombre limité d’instructions bien définies. Des instructions typiques comprises par un ordinateur sont « copier le contenu de la cellule 123 et le placer dans la cellule 456 », « ajouter le contenu de la cellule 321 à celui de la cellule 654 et placer le résultat dans la cellule 777 » et « si le contenu de la cellule 999 vaut 0, exécuter l’instruction à la cellule 345 ». Mais la plupart des instructions se composent de deux zones : l’une indiquant quoi faire, qu’on nomme le code opération, et l’autre indiquant où le faire, qu’on nomme opérande.

Au sein de l’ordinateur, les instructions correspondent à des codes - le code pour une copie étant par exemple 001. L’ensemble d’instructions qu’un ordinateur supporte se nomme son langage machine, langage qui est une succession de chiffres binaires, car les instructions et données qui sont comprises par le CPU sont constituées uniquement de 0 (zéro) et de 1 (un). 0 = Le courant électrique ne passe pas. 1 = Le courant électrique passe.

En général, les programmeurs n’utilisent plus ce type de langage, mais passent par ce que l’on appelle un langage de haut niveau qui est ensuite transformé en langage binaire par un programme dédié (interpréteur ou compilateur selon les besoins). Les programmes ainsi obtenus sont des programmes compilés compréhensibles par l'ordinateur dans son langage natif.

Certains langages de programmation, comme l’assembleur sont dits langages de bas niveau car les instructions qu’ils utilisent sont très proches de celles de l’ordinateur. Les programmes écrits dans ces langages sont ainsi très dépendants de la plate-forme pour laquelle ils ont été développés. Le langage C, beaucoup plus facile à relire que l’assembleur, permet donc aux programmeurs d’être plus productifs. Pour cette raison, on l’a vu de plus en plus utilisé à mesure que les coûts du matériel diminuaient et que les salaires horaires des programmeurs augmentaient.

Logiciels [modifier]

Les logiciels informatiques sont de longues listes d’instructions exécutables par un ordinateur. De nombreux programmes contiennent des millions d’instructions, effectuées pour certaines de manière répétitive. En 2009, un ordinateur personnel exécute plusieurs milliards d’instructions par seconde.

Depuis le milieu des années 1960, des ordinateurs exécutent plusieurs programmes simultanément. Cette possibilité est appelée multitâche. C’est le cas de tous les ordinateurs aujourd’hui.

En réalité, le processeur n’exécute qu’un programme à la fois, passant de l’un à l’autre chaque fois que nécessaire. Si la rapidité du processeur est suffisamment grande par rapport au nombre de tâches à exécuter, l’utilisateur aura l’impression d’une exécution simultanée des programmes. Les priorités associées aux différents programmes sont, en général, gérées par le système d'exploitation.

Système d’exploitation [modifier]

Le système d’exploitation est le programme central qui contient les programmes de base nécessaires au bon fonctionnement des applications de l’ordinateur.

Le système d’exploitation alloue les ressources physiques de l’ordinateur (temps processeur, mémoire, etc.) aux différents programmes en cours d’exécution. Il fournit aussi des outils aux logiciels (comme les pilotes) afin de leur faciliter l’utilisation des différents périphériques sans avoir à en connaître les détails physiques.

Ceci est le premier article de ce blog !
Utilisez la barre d'outils située en haut de la page pour gérer vos rubriques, menus, configuration...etc.
Cliquez sur "Ecrire un article" dans le menu "Actions" pour écrire un nouvel article.

Lancer la visite guidée