PROGRAMMATION

Programme, interpréteur et compilateur

Un programme est tout d'abord un texte, c'est-à-dire une séquence de symboles. Pour prendre son sens en tant que programme, ce texte doit être mis en présence d'un mécanisme capable de le décoder et de produire un certain nombre de transformations. Ce mécanisme est appelé un interpréteur et l'ensemble des symboles utilisés est appelé le vocabulaire. Toutes les séquences de symboles ne forment pas des programmes : elles doivent respecter des règles de syntaxe, et celles-ci définissent le langage de programmation utilisé. Il s'agit là d'une description très générale pouvant se décliner de manières extrêmement variées, selon la nature du texte (vocabulaire, syntaxe) et de l'interpréteur (électronique, électromécanique voire mécanique, comme dans les pianos mécaniques, chimique dans le cas des cellules vivantes, ou logiciel). Du point de vue du programmeur, il est évidemment préférable que le langage de programmation soit riche et aisé à manipuler. Mais cela complique considérablement la réalisation de l'interpréteur : le décodage même du texte en symboles structurés conformément à la syntaxe devient un problème ardu, hors de portée d'une réalisation électronique. En pratique, dans les systèmes informatiques, les interpréteurs les plus primitifs sont précisément des processeurs électroniques, dont les langages correspondants (langages machine) se réduisent à des blocs de 8, 16, 32 ou 64 bits (appelés mots machine) placés consécutivement. Il n'y a donc pas véritablement de syntaxe, en revanche les mots sont assez élaborés et une bonne part du travail effectué par le processus consiste à reconnaître leur structure, pour déterminer par exemple s'il s'agit d'une instruction arithmétique, de branchement ou d'une donnée. Un programme présenté sous cette forme est incompréhensible à un œil humain – rien ne ressemble plus à une suite de 0 et de 1 qu'une autre suite de 0 et de 1. On utilise à ce niveau un langage d'assemblage, sorte de syntaxe mnémonique codifiée en correspondance biunivoque avec le langage machine (et, comme ce dernier, propre à chaque type de processeur) : les instructions sont donc les mêmes, par exemple « ajouter 3 au contenu du mot mémoire placé à tel endroit ». Un programme ainsi rédigé n'est pas directement interprétable par le processeur : il est d'abord traduit en langage machine, cette étape étant effectuée par un programme appelé assembleur. Dans le cas d'un langage de programmation plus élaboré, comme ceux que nous aborderons dans la suite, on peut mettre en œuvre les deux idées évoquées ci-dessus. Une première possibilité consiste à réaliser un programme capable d'interpréter le langage en question. Une seconde possibilité, préférable pour des raisons d'efficacité, consiste à effectuer une traduction du code source en langage machine ; un tel traducteur est appelé compilateur. On trouve également des solutions intermédiaires, comme la compilation vers un interpréteur raisonnablement efficace présent sur des processeurs différents, appelé aussi machine virtuelle ; c'est par exemple le cas de Java.

Pour terminer, remarquons que les premiers modèles abstraits de calcul étaient eux-mêmes des interpréteurs. Ainsi, Alan Mathison Turing (1912-1954) considérait dès les années 1930, c'est-à-dire bien avant la naissance du premier ordinateur, des machines imaginaires composées d'une tête de lecture-écriture et d'un ruban, une instruction consistant à lire le symbole présent dans la case située sous la tête puis, en fonction de ce dernier, à écrire un autre symbole ou à déplacer la tête d'un côté ou de l'autre. Programmer une machine de Turing est assez fastidieux mais, en dépit des apparences, des mathématiciens comme Alonzo Church (1903-1995), Stephen Cole Kleene (1909-1994) et Turing lui-même ont montré que ce modèle permettait de coder n'importe quel algorithme. Un autre résultat fondamental démontré par Turing énonce qu'il n'existe pas de programme pouvant répondre à coup sûr à la question de savoir si l'exécution d'un programme va se terminer ou non (techniquement, on dit que le problème de l'arrêt des machines de Turing est indécidable). Les démonstrations utilisent de manière intensive les notions d'interprétation et de compilation : une étape clé consiste à définir une machine de Turing (dite universelle) capable de simuler le fonctionnement d'un interpréteur de machines de Turing – ce n'est donc rien d'autre qu'un interpréteur logiciel, programmé dans le langage très limité des machines de Turing. De nombreuses conséquences pratiques en découlent pour les activités de programmation. Par exemple, un compilateur doit, pour préparer la traduction d'un programme, effectuer une analyse de ce dernier. On pourrait espérer profiter de cette phase pour répondre à des questions portant sur ce programme, telles que : y a-t-il une borne sur le nombre d'itérations effectuée à tel endroit, ou encore, la valeur de tel mot mémoire sera-t-elle toujours non nulle ? Or de telles questions se réduisent au problème de l'arrêt et s'avèrent donc indécidables. Moralité : le programmeur est amené, dans le cas général, à réfléchir par lui-même et à faire preuve de créativité dans ses raisonnements. Et l'un des premiers enjeux importants, pour la conception des langages de programmation, a été de fournir des constructions appropriées au raisonnement.

Constructions fondamentales

Les premiers langages de programmation comme Fortran, inventé vers 1955 par John Warner Backus (1924-2007), offraient une syntaxe plus compréhensible que l'assembleur et permettaient l'utilisation d'expressions arithmétiques, ce qui constituait un gros progrès. Mais le modèle de programmation sous-jacent restait proche de la notion de séquence d'instructions numérotées, avec éventuellement indication explicite du numéro de la prochaine instruction – la fameuse instruction de branchement GOTO. Deux faits ont été établis dans les années 1960. Le premier, c'est que l'utilisation anarchique des GOTO est une source de complications dévastatrices. Le second, c'est que l'on peut, sans perte de généralité, limiter l'usage du GOTO à un tout petit nombre de schémas bien définis : l'alternative, la boucle tant-que (avec une ou deux variantes mineures) et, dans un registre un peu différent, l'appel de procédure ou de fonction. Cela constituait une avancée majeure : alors que la programmation avec GOTO condamnait à raisonner d'emblée sur la totalité du programme, l'utilisation de schémas élémentaires s'emboîtant les uns dans les autres fournissait un moyen de découper et structurer la conception, la mise au point et la maintenance. Elle procure également de bien meilleures conditions pour donner une définition mathématique de la sémantique des programmes et fournir toutes sortes d'outils (on y reviendra au chapitre 2).

Voici les principales structures de contrôle rencontrées en programmation. Elles combinent des instructions I₁, I₂... (ou blocs d'instructions) préalablement formées, soit de manière primitive, soit au moyen de structures de contrôle. Les instructions primitives sont l'instruction vide (qui joue le rôle d'élément neutre), l'affectation de la forme x ← E et l'appel de procédure P(E₁,... E_n), où x représente un emplacement mémoire et E, E₁,... E_n sont des expressions. Les structures de contrôle proprement dites sont :

1. La séquence, généralement notée par un point-virgule, « I₁ ; I₂ » ; le contrôle passe successivement à I₁, puis à I₂ .

2. L'alternative, « si E alors I₁ sinon I₂ » (où E est une expression booléenne) : l'expression E est d'abord évaluée ; selon que la valeur obtenue est vrai ou faux, le contrôle passe à I₁ ou à I₂.

3. La boucle, « tant-que E boucle I finboucle » : au point de départ, l'expression E est évaluée ; si la valeur obtenue est faux, le schéma se comporte comme l'instruction vide ; sinon, le contrôle passe à l'instruction I puis revient à l'évaluation de E au départ de la boucle (c'est ici que se pose le problème de l'arrêt).

La syntaxe précise de ces structures de contrôle varie d'un langage de programmation à l'autre. Il faut par ailleurs, comme dans les expressions mathématiques, pouvoir regrouper des instructions au moyen de symboles jouant le rôle de parenthèses.

Appels de procédure, récursivité

Un autre outil important pour maîtriser la complexité des programmes consiste à emballer un groupe cohérent d'instructions et à lui donner un nom : on obtient un sous-programme ou procédure ; l'invocation de son nom lui transfère le contrôle, qui, après exécution de la procédure, reviendra au point suivant immédiatement l'appel. Dans le cas général, une procédure comporte des paramètres et des données locales. Cela permet de factoriser une partie du code et constitue l'une des formes les plus simples de modularité – d'autres, plus évoluées, apparaîtront plus bas, avec les notions de types abstraits et de classes. Lorsque la procédure rend une valeur en fin d'exécution, on la nomme une fonction et au lieu d'être appelée en tant qu'instruction, elle est invoquée à l'intérieur d'une expression. Par exemple, on peut créer une fonction de calcul de la racine carrée n'utilisant que des opérations arithmétiques plus simples comme la somme, la soustraction et le produit. Les langages de programmation viennent en fait non seulement avec un jeu d'instructions et de structures de contrôle, mais avec des bibliothèques de procédures et de fonctions parfois très volumineuses. En outre, dans un développement de logiciel, on commence toujours, en pratique, par créer des procédures et fonctions appropriées à l'application visée.

Lorsque le corps d'une procédure ou d'une fonction comporte des appels à la procédure ou fonction en cours de définition, on dit qu'elle est récursive. On peut ainsi définir des fonctions comme les suites récurrentes en mathématique, par exemple u(0) = u(1) = 1 et u(n+2) = u(n) + u(n + 1). On trouve de nombreuses applications de la récursivité, par exemple en compilation dans les procédures d'analyse du code source.

Structures de contrôle et structures de données, systèmes de types

Un autre élément important en programmation se trouve dans la structuration des données à manipuler. L' algorithmique (science de la conception d'algorithmes) repose pour une bonne part sur la définition de structures de données efficaces et adaptées au problème ciblé. Les données élémentaires sont représentées par des mots mémoire de taille fixe : cela inclut les entiers (bornés), les caractères et les flottants (une approximation de précision finie des réels, entraînant des erreurs d'arrondi). On introduit ensuite des données composées. Leur taille peut être fixée statiquement, par exemple pour des couples ou des n-uplets de données élémentaires, ou évoluer dynamiquement, c'est-à-dire en cours d'exécution, par exemple pour des listes, des tables ou des arbres. La réalisation des dernières nécessite l'allocation et la libération dynamique de zones mémoire et l'utilisation de mots mémoire particuliers, appelés pointeurs, pour désigner ces zones. Ces manipulations s'avèrent à la fois essentielles pour de nombreux programmes et très délicates à utiliser : avant de libérer l'espace désigné par un pointeur, il faut s'assurer que ce pointeur ne fera plus l'objet d'un accès et – ce qui est bien plus difficile – qu'il en est de même pour tous les alias de ce pointeur. Le pointeur est un peu le GOTO des structures de données, et les langages de programmation modernes présentés ci-dessous délivrent le programmeur de la gestion mémoire en lui offrant des structures de données abstraites (le problème est donc reporté et résolu une fois pour toutes au niveau du compilateur). En outre, il est important de ne pas appliquer à des données des traitements prévus pour d'autres – on ne va pas additionner des caractères par exemple. Ceci peut être contrôlé au moyen d'un système de types, qui attribue un type (par exemple entier ou liste de caractères) à chaque expression d'un programme donné, avec vérification de la cohérence du type des opérations avec celui de leurs arguments. La notion de structure de donnée est en fait intimement liée à celle de type de donnée. Il existe deux grandes approches de cette question : l'une est issue des langages fonctionnels et l'autre de la programmation par objets.

Programmation fonctionnelle

La première approche prend sa source dans un modèle de calcul différent de celui des machines de Turing, dû à Church : le lambda-calcul. Les machines de Turing exposent une vue très opérationnelle du calcul donnée par des transitions entre états. En lambda-calcul pur, on ne manipule que des fonctions, avec pour seul mécanisme de calcul l'évaluation d'expressions fonctionnelles, c'est-à-dire la substitution des arguments appelés dans le corps de la fonction appelante. Il s'avère que le lambda-calcul pur a la puissance des machines de Turing. En pratique, tant pour des raisons d'efficacité que de facilité d'usage, les langages fondés sur ce modèle incorporent des types de données et des mécanismes de réduction supplémentaires, par exemple les entiers et les opérations arithmétiques usuelles. Pour revenir à la discussion précédente, la programmation fonctionnelle établit un parallèle saisissant entre structures de données et structures de contrôle, par le biais d'une correspondance issue de la théorie de la démonstration, introduite par Haskell Brooks Curry (1900-1982), William Alvin Howard (né en 1926) et Nicolaas Govert de Bruijn (né en 1918), entre formules logiques et types d'une part, démonstrations et programmes d'autre part. Au passage, elle nous fait prendre conscience de l'importance de la notion de somme de types à côté de la notion de produit : remarquons que les produits ont été introduits très tôt en programmation, à travers les agrégations (records) ou les tableaux, alors que les sommes, reconnues tardivement avec des langages fonctionnels modernes comme ML ou Haskell, restent souvent ignorées, quoique présentes dans le langage de description de données XML. La théorie des types nous propose une vision dans laquelle chaque type de données est défini par un nombre fini de procédés canoniques exhaustifs de construction (ou principes d'introduction), desquels découlent des procédés systématiques d'analyse (ou principes d'élimination). Un programme P, appliqué à des arguments E₁,... E_n, pourra fabriquer un résultat de type T ; autrement dit, P(E₁, ... E_n) est aussi une construction de type T. Ce n'est pas une construction canonique, et on peut en imaginer un très grand nombre, voire une infinité de semblables. Cependant, l'exécution de tels programmes, une fois terminée, ne peut aboutir qu'à des valeurs construites canoniquement. Pour utiliser (plus exactement, analyser) un résultat de type T, il suffit donc de considérer les différentes constructions canoniques. Prenons un exemple, celui où T = N × N, le type des couples d'entiers. On emploie la notation E : T pour indiquer que l'expression E est de type T. Par définition, le principe de construction de N × N est le suivant : si u : N et v : N, alors (u, v) : N × N. Considérons le programme P qui prend un couple d'entiers (u, v) et rend la permutation (v, u). Si c est de type N × N, par exemple c = (3, 8), alors P(c) est aussi de type N × N, ainsi que P(P(c)), etc. Et pour analyser de telles expressions, il suffit d'énoncer que leur version canonique est nécessairement de la forme (x, y), avec x : N et y N. Selon Curry, Howard et de Bruijn, la notion logique correspondante est la conjonction, car une preuve canonique de A et B est un couple (a, b) formé d'une preuve canonique a de A et d'une preuve canonique b de B ; le principe d'élimination associé peut s'exprimer soit au moyen d'une fonction prenant deux arguments, l'un dans A et l'autre dans B, soit au moyen de la première et de la seconde projection. Qu'en est-il maintenant de la disjonction ? Du point de vue logique, on a cette fois deux manières canoniques de démontrer A ou B : soit en partant d'une preuve canonique de A, soit en partant d'une preuve canonique de B. On distinguera toujours ces deux options, même si A = B. Du point de vue de la programmation, on obtient ainsi une notion pour représenter une donnée pouvant être soit de type A, soit de type B, qui est bien meilleure que l'union de types proposée dans le langage C : c'est la somme des types A et B, dont les éléments sont des couples qui sont soit de la forme (0, a) avec a : A, soit de la forme (1, b) avec b : B. La présence obligatoire de l'indicateur valant 0 ou 1 fait toute la différence avec l'union de types : on obtient le principe d'élimination associé qui analyse l'indicateur et, suivant la valeur obtenue, dirige la suite du calcul vers une expression utilisant une donnée de type A ou vers une autre expression utilisant une donnée de type B. Le système de types est préservé, alors que rien de tel n'est possible avec l'union. Observons en passant que cette notion généralise celle de booléen : le type booléen peut être vu comme la somme de deux types (non informatifs) à une seule valeur. Le principe d'élimination associé se réduit alors au si.... alors... sinon... bien connu.

Programmation par objets

L'autre grande approche fournissant une structuration de haut niveau pour les données se trouve dans la programmation par objets. Elle trouve son origine dans les types abstraits, notion qui consiste à réunir au sein d'une même entité données et fonctions constituant l'interface obligée pour y accéder ou les modifier. Cette localisation est un élément de structuration très important pour les gros logiciels, qui réduit considérablement les risques de modifications malencontreuses et permet de préserver les invariants attendus des données ainsi emballées. Dans les langages à objets, les types abstraits sont étendus par un mécanisme d'héritage et prennent le nom de classes, les objets sont précisément des exemplaires d'éléments d'une classe. L'héritage consiste à définir une sous-classe à partir d'une classe existante en complétant les données et/ou les fonctions d'accès (au passage, ces dernières sont renommées méthodes ; il est bien connu que l'art des mathématiques consiste à donner le même nom à des choses différentes ; en informatique, c'est l'inverse...). Par exemple, dans une application logicielle graphique, on pourra avoir une classe de figures géométriques comportant des fonctions de translation et de rotation, une sous-classe des figures colorées comportant des opérations supplémentaires (on peut par exemple les repeindre). Dans une sous-classe, on a la possibilité de redéfinir les fonctions de la classe d'origine ; par exemple, on ne réalise pas de la même manière la translation dans la sous-classe des cercles que dans la sous-classe des polygones. Cela implique un mécanisme particulier pour déterminer, à l'exécution, quelle procédure sera appelée sous un nom donné, suivant que l'objet se trouve dans telle ou telle sous-classe : c'est ce qu'on appelle la liaison tardive.

De la programmation en logique à la programmation par contraintes

Une autre manière d'aborder la programmation, introduite au début des années 1970 par Alain Colmerauer (né en 1941) et Robert Anthony Kowalski (né en 1941), consiste à considérer certaines formules logiques comme des programmes. Cette idée, issue de recherches en démonstration automatique, avait une certaine efficacité dans les situations se décrivant sous forme d'une conjonction de clauses de Horn, c'est-à-dire d'implications A₁, A₂,..., A_n => B avec, implicitement, quantification universelle sur la clause de toutes ses variables. Il est alors possible de rechercher si une formule atomique (sans connecteur logique) C, appelée le but, est une conséquence des clauses de Horn en identifiant C aux conclusions possibles B, puis en posant A₁, A₂,... A_ncomme nouveaux sous-buts ; et ainsi de suite, jusqu'à ne rencontrer que des clauses sans hypothèse A_i. Ici, le rôle de l'interpréteur est joué par le programme de recherche de démonstrations. Au cours de cette recherche, les étapes d'identification d'un sous-but à une conclusion peuvent imposer des contraintes entre des variables et des termes. Le résultat du calcul est alors une réponse indiquant soit « oui, C est bien une conséquence des clauses, moyennant telles égalités sur les variables de C » – ces égalités sont appelées substitutions-réponses –, soit « non, aucune substitution appliquée à C ne donne une telle conséquence ».

Le langage de programmation en logique le plus connu est Prolog, dont une autre filiation se trouve dans les systèmes-Q de Colmerauer destinés à des calculs grammaticaux. Prolog est particulièrement adapté aux calculs sur des données structurées en arbre, le calcul progressant par accumulation de contraintes équationnelles entre des arbres. À partir des années 1990, ce paradigme de programmation a évolué en introduisant d'autres contraintes, portant par exemple sur des nombres, des intervalles ou des ensembles finis : c'est ce qu'on a appelé la programmation par contraintes.

Méthodes de programmation, ingénierie du logiciel

Les logiciels modernes se caractérisent par une très grande taille, des contraintes très dures et de nombreuses interactions avec leur environnement, induisant une grande complexité de réalisation. En outre ces logiciels évoluent : on y ajoute de nouvelles fonctionnalités, ils sont portés sur de nouvelles architectures ou doivent tout simplement être corrigés. Il est donc indispensable de disposer de méthodes de travail et d'outils appropriés. Sans entrer dans le détail, mentionnons que les méthodes traditionnelles s'appuient sur l'établissement préalable de modèles et diagrammes plus ou moins précis, la difficulté étant d'en assurer la cohérence et de garantir que les différents intervenants interprètent ces documents très volumineux de la même manière. En outre il faut maintenir la documentation à jour lors des évolutions. Plus récemment sont apparues des méthodes plus légères, dites méthodes agiles, fondées sur des cycles d'interaction beaucoup plus courts entre les commanditaires et les réalisateurs.