|
|
|
Le propos de ce cours est d'apprendre à programmer les ordinateurs. N'importe quel ordinateur, puisqu'ils sont tous équivalents, et pour tout programme, puisque le propre d'un ordinateur est l'universalité, c'est à dire la capacité à traiter tous les problèmes traitables effectivement.
Avant de commencer, il convient de faire un tour d'horizon sommaire des questions mises en jeu par ces premiers mots.
L'informatique moderne est née de la recherche entreprise au début du XXème siècle par Bertrand Russel et Alfred North Whitehead sous le titre Principia Mathematica pour constituer les mathématiques en un système formel où toute proposition pourrait être démontrée par un calcul logique. David Hilbert et Kurt Gödel accomplissent des pas décisifs dans l'exploration de ce programme. En 1931 Gödel démontre que pour tout système formel suffisant pour représenter l'arithmétique il existe des propriétés vraies dont on ne peut démontrer la vérité ni la fausseté avec les règles du système lui-même. Le théorème de Gödel ruine le rêve de réunir les mathématiques dans un système déductif parfaitement cohérent, mais de l'effervescence intellectuelle autour du projet des Principia vont sortir les idées fondatrices de l'informatique.
En 1936 Alan Turing, à la suite de Gödel, s'attaque à un problème de décidabilité : un système est décidable s'il existe une procédure effective pour distinguer les propositions démontrables des autres. Pour définir plus rigoureusement la notion de procédure effective, Turing élabore un modèle d'automate appelé par la suite machine de Turing , qui lui permet de préciser la notion d'exécution d'un algorithme.
Inventer des procédures effectives (des algorithmes) consiste à déterminer un enchaînement d'opérations élémentaires qui exécuteront les calculs nécessaires à la solution de problèmes pour lesquels existent des solutions calculables (il y a des problèmes sans solution et des solutions incalculables). Ce cours enseigne l'art de réaliser des algorithmes. Turing montre que son modèle de calcul est universel, c'est à dire que toutes les machines de Turing sont équivalentes. Il formule la thèse selon laquelle tout algorithme est calculable par une machine de Turing. Ces idées fondent la théorie de la programmation des ordinateurs. Il revient à von Neumann de concevoir en 1945 l'architecture générale des appareils concrets qui vont réaliser les calculs selon le modèle de Turing, architecture si élégante que les ordinateurs d'aujourd'hui sont encore construits, pour l'essentiel, selon ses principes.
L'architecture que von Neumann propose pour l'ordinateur est la suivante :
Les unités de contrôle 1.1, arithmétique et d'entrée-sortie constituent à elles trois l'unité centrale, ou le processeur de l'ordinateur. Le processeur est constitué de circuits électroniques qui peuvent exécuter des actions. L'ensemble des actions « câblées » dans le processeur constitue le jeu d'instructions du processeur et détermine le langage élémentaire de son utilisation, appelé « langage-machine ».
Le rôle de l'unité de contrôle consiste à permettre le déclenchement de l'action (l'instruction) voulue au moment voulu. Cette instruction peut appartenir à l'unité arithmétique, à l'unité d'entrée-sortie ou à l'unité de contrôle elle-même. Une instruction peut en outre consulter le contenu de la mémoire (la « lire ») ou modifier le contenu de la mémoire (y « écrire »). De façon générale, une action consiste soit à consulter ou à modifier l'état de la mémoire ou d'un des registres A ou R (qui sont des éléments de mémoire spéciaux incorporés à l'unité centrale), soit à déclencher une opération d'entrée-sortie (communication avec le monde extérieur et notamment l'utilisateur humain).
Comment indique-t-on à l'unité de contrôle le « moment voulu » pour déclencher telle ou telle action ? C'est écrit dans le texte d'un programme. Où est le programme ? Dans la mémoire.
La mémoire est constituée d'éléments susceptibles de prendre des états. Un élément de base de la mémoire peut prendre deux états distincts et peut servir à représenter une information élémentaire, ou bit (binary digit, chiffre binaire). Cette représentation d'une information par un élément de mémoire s'appelle un code. Une mémoire avec beaucoup de bits permet le codage d'informations complexes, dans la limite de la taille de la mémoire.
Le codage fait correspondre des groupes de bits à des symboles. Les symboles les plus simples sont les chiffres et les lettres. Pour représenter des informations complexes on peut définir des méthodes, des règles pour regrouper des symboles puis associer un élément d'information à un groupe de symboles construit selon les règles. On appellera langage un ensemble de symboles ou de groupes de symboles, construits selon certaines règles, qui sont les mots du langage. La syntaxe du langage est l'ensemble des règles de construction des mots du langage. La signification (ou encore la sémantique) d'un mot d'un langage est affaire d'interprétation, et peut dépendre du contexte.
Les numéros d'immatriculation des automobiles, les numéros INSEE des personnes (dits faussement numéros de sécurité sociale), le langage machine d'un ordinateur sont des langages 1.2.
La mémoire de l'ordinateur (c'est l'idée fondamentale de von Neumann) contient des informations de deux types : des programmes et des données. Les programmes et les données sont représentés avec les mêmes symboles, seule la sémantique permet d'interpréter leurs textes respectifs. D'ailleurs, le texte d'un programme peut parfois être envisagé comme des données pour un autre programme, par exemple un programme de traduction d'un langage dans un autre.
L'informatique est la science du traitement de l'information. Nous avons donné une idée sommaire de la nature de l'information. Qu'est son traitement ? C'est, en partant d'informations connues appelée données, faire élaborer par un agent exécutant des informations nouvelles appelées résultats. Un traitement est l'application d'une méthode de passage d'un ensemble de données D à un ensemble de résultats R : à toute donnée d de D on fait correspondre un élément r de R. Cette définition est inspirée de la notion mathématique de fonction.
La méthode de passage invoquée doit être adaptée à l'agent exécutant. Par exemple, pour l'opération « somme de deux nombres entiers », la façon d'obtenir à partir d'un couple de nombres leur somme sera décrite différemment selon que l'agent exécutant sera un être humain muni d'un crayon et de papier ou le processeur d'un ordinateur.
Le traitement des données doit être effectif, c'est à dire que la méthode de passage doit pouvoir aboutir pratiquement au résultat. Prenons un exemple, soit D l'ensemble des numéros d'immatriculation des voitures immatriculées en France. Les symboles utilisés sont des chiffres et des lettres. Les règles de formation des numéros d'immatriculation sont la syntaxe du langage. La sémantique d'un numéro est l'identité de la voiture qui le porte. Considérons R, l'ensemble des départements français. La correspondance qui, à tout numéro d'immatriculation bien formé, fait correspondre le département d'immatriculation de la voiture qui le porte est un traitement de D, on sait comment le réaliser. Par contre la correspondance qui, à tout numéro d'immatriculation bien formé, ferait correspondre la commune d'immatriculation de la voiture associée n'est pas un traitement de D, car on ne sait pas élaborer cette information à partir du numéro, bien qu'elle existe sûrement. Cette correspondance ne peut pas être décrite de manière effective, c'est à dire par un algorithme.
Un algorithme est la description, pour un exécutant donné, d'une méthode de résolution d'un problème, autrement dit d'une suite d'opérations qui fournissent le résultat cherché.
La description de la méthode, c'est à dire l'algorithme, doit être adaptée à l'exécutant chargé d'effectuer le traitement. L'exécutant sait effectuer un nombre fini d'actions, que l'on nomme ses primitives (ce sont par exemple les instructions du jeu d'instructions du processeur décrit ci-dessus). L'algorithme doit être constitué d'une combinaison de ces primitives. Pour construire toutes les combinaisons possibles de primitives, on démontre qu'il suffit de savoir réaliser l'enchaînement de deux primitives (effectuer une action à la suite d'une autre), la répétition d'une primitive donnée et le choix, pendant l'exécution d'un traitement, entre deux primitives selon le résultat d'un test.
Un algorithme fournit, pour un exécutant donné, la décomposition de la tâche à réaliser en primitives de l'exécutant.
Au point où nous en sommes, si nous résumons notre description introductive et simplifiée de ce qu'est un ordinateur, nous dirons qu'il dispose d'un processeur capable d'effectuer des actions dites primitives, de les enchaîner dans l'ordre voulu, de les répéter et surtout de choisir, en fonction du résultat des actions précédentes, la prochaine action à effectuer entre deux ou plusieurs possibilités (ces cas possibles sont en nombre fini et connus à l'avance).
Notre ordinateur dispose aussi d'une mémoire qui contient des informations codées, qui sont de deux types : des programmes et des données. Pour l'instant nous pouvons nous contenter de dire que des conventions sémantiques relatives au contexte de démarrage de l'ordinateur permettent de distinguer le programme des données à traiter : lorsqu'il commence à agir, le processeur va par convention aller chercher dans la mémoire, à un emplacement convenu, le texte de la première instruction à exécuter. Les règles d'enchaînement du langage assurent en principe le déroulement cohérent de la suite.
Le programme est le texte rédigé dans le langage-machine de l'ordinateur de l'algorithme dont l'exécution est désirée. Ce texte énumère les primitives de l'ordinateur dont l'exécution mènera à la production du résultat recherché. Le programme est dit juste s'il se termine 1.3.
Fondamentalement, un ordinateur est une machine qui effectue les traitements décrits par des algorithmes rédigés dans son langage-machine. Il existe, heureusement, beaucoup d'autres langages de programmation.
Un langage de programmation est un système de notation au moyen duquel un être humain peut transmettre un algorithme à un ordinateur ou à un autre être humain. Toute une gradation existe entre les langages bien adaptés aux ordinateurs mais difficiles à comprendre pour les personnes et les langages proches de notations habituelles aux personnes mais difficiles à faire interpréter par un ordinateur. Chaque ordinateur possède un langage qui lui est intrinsèque, son langage machine, et les programmes écrits dans des langages plus commodes doivent, pour être exécutés, être traduits en langage machine. Cette traduction est effectuée par des programmes spéciaux dont il existe deux grandes catégories : les compilateurs et les interprètes.
Le premier problème posé par l'usage des ordinateurs fut de communiquer des algorithmes à la machine. À l'origine le seul moyen disponible était la programmation directe en langage machine, chaque instruction codée en binaire correspondant à un circuit logique de l'unité centrale, et les données étant désignées par leur adresse, c'est à dire le rang de la « case » mémoire les contenant. Dès l'EDSAC (le premier ordinateur, en 1949) fut utilisé un langage permettant de désigner les instructions par un code alphabétique mnémonique et d'utiliser des adresses symboliques (alphabétiques) au lieu des adresses physiques : ce type de langage est appelé un assembleur. Il faut un programme de traduction (ou assembleur) pour le traduire en langage machine, et notamment pour traduire les symboles en adresses (physiques).
Mais le besoin se faisait sentir de langages moins dépendants de la structure de l'ordinateur et plus adaptés à la description des problèmes à traiter, que l'on appellera les langages évolués, traduits en langage machine par des compilateurs ou des interprètes, et qui sont des métalangages par rapport à l'assembleur.
Les premiers langages évolués qui apparurent sont des langages dits « impératifs », fondés sur la notion d'état de la mémoire. Ces langages, inspirés du modèle de von Neumann, comportent comme le langage-machine des instructions qui produisent des modifications de la mémoire (instruction d'affectation). La rédaction d'un programme en langage impératif consiste à écrire la suite des instructions qui vont causer les états successifs par lesquels devra passer la mémoire pour que, en partant d'un état initial permettant l'initialisation du programme, elle arrive dans un état final fournissant les résultats recherchés. Un tel programme explicite COMMENT RÉALISER le traitement voulu par le programmeur. Le langage que nous utiliserons au cours de cette introduction N'EST PAS un langage impératif.
Une autre approche pour concevoir des langages de programmation est de s'inspirer du modèle de la machine de Turing. Ces langages reposent sur la notion de fonction, et sont donc appelés langages fonctionnels 1.4. Ils ne comportent pas d'instructions, mais le calcul est exprimé par des fonctions qui, appliquées à des arguments, rendent le résultat recherché. Des programmes rédigés avec de tels langages explicitent QUOI RÉALISER pour obtenir le résultat voulu. Pour cette introduction nous utiliserons un langage fonctionnel.
Il importe de se convaincre (ce ne sera pas en un jour) que tous les programmes que
nous pourrons écrire dans différents langages sont équivalents. La machine de Turing est un modèle d'automate dont on trouvera ci-dessous une description
très terre à terre. Alonzo Church, le directeur de thèse d'Alan
Turing à Princeton, pour approfondir la notion de fonction, invente le 
-calcul,
dont on montre que les expressions bien formées sont équivalentes à des machines de
Turing. Les langages fonctionnels dérivent étroitement du -calcul.
L'architecture de von Neumann, conçue pour réaliser efficacement les
traitements décrits par une machine de Turing, engendre les langages
impératifs. Tout programme, fonctionnel ou impératif, destiné à être exécuté, sera
traduit dans un langage impératif, le langage-machine de l'ordinateur utilisé. La
cohérence de l'informatique, et l'équivalence sémantique des programmes écrits en
divers langages, qui assurent la validité de cette opération, sont le fruit non pas du
hasard, mais d'une conception théorique originelle commune. Gödel, Church, von Neumann et Turing étaient tous à Princeton en 1936.
Un modèle formel pour une procédure effective (pour décrire un algorithme) doit posséder certaines propriétés. Premièrement, chaque procédure doit recevoir une définition finie. Deuxièmement, la procédure doit être composée d'étapes distinctes, dont chacune doit pouvoir être accomplie mécaniquement. Dans sa simplicité, la machine de Turing déterministe composée des éléments suivants répond à ce programme :
La configuration d'une machine de Turing peut être représentée par un triplet (q, m, u) où q est l'état de la machine, m le mot qui apparaît sur le ruban avant la position de la tête de lecture, u le mot figurant sur le ruban entre la position de la tête de lecture et le dernier caractère non blanc.
Un arc du graphe de la fonction de transition peut être représenté par un quintuplet (qi, si, sj, x, qj) où :
Pour se donner une intuition de la chose, imaginons une M.T. (machine de Turing) avec un alphabet {0, 1,<espace>} ; nous conviendrons d'utiliser le système de numération unaire (celui que vous utilisez pour marquer les points au ping-pong, autrement dit « les bâtons ») et de séparer les nombres par des 0. Pouvons nous additionner deux nombres ?
Le ruban mentionne successivement les nombres 4 et 3. Pour les additionner il suffit que la tête de lecture lise successivement les quatre chiffres unaires qui constituent le nombre 4, dont la fin sera indiquée par l'occurrence du signe zéro. Il faudra alors supprimer le zéro et réécrire d'une case à droite les chiffres du nombre 3, jusqu'à la rencontre d'un signe zéro, qui subira le même traitement, pour obtenir 7. L'écriture de la table des transitions constituera pour le lecteur un exercice amusant.
On peut doter sa Machine de Turing de l'alphabet fini de son choix. Son ruban peut être infini dans les deux sens ou dans un seul. Elle peut même avoir plusieurs rubans. On montre que ces diverses machines sont équivalentes.
|
|
|
![\includegraphics[scale=0.8]{../Images/Fondations/von-Neumann.epsi}](http://www.pasteur.fr/recherche/unites/sis/Intro_Programmation/img6.gif)
67![\includegraphics[scale=0.8]{../Images/Fondations/turing.epsi}](http://www.pasteur.fr/recherche/unites/sis/Intro_Programmation/img8.gif)
67