Capsule : Algorithmes et langages de programmation

Notion d’algorithme

Avant d’aborder le sujet de la programmation proprement dit, il est nécessaire d’introduire une notion importante : la notion d’algorithme. Comme on va le voir à l’aide de quelques exemples, cette notion vous est déjà familière même si le mot vous est inconnu.

Exemple 1 : Imaginez que vous êtes dans une ville inconnue et que vous devez vous rendre à la gare. Vous abordez un passant pour lui demander votre chemin. Il pourrait vous répondre en disant, par exemple : « Prenez la première à gauche, allez tout droit jusqu’à la poste qui se trouvera sur votre gauche et de là, prenez la deuxième à droite. »

Exemple 2 : Imaginez que vous souhaitez inviter des amis pour le goûter, mais que vous ne savez rien de la pâtisserie. Il vous suffit de vous munir d’un livre de recettes et moyennant les bons ingrédients ainsi que quelques connaissances de base (savoir se servir d’un couteau, d’une balance et d’un four), vous serez à même de leur proposer un délicieux gâteau au chocolat.

Exemple 3 : Dans un ouvrage du IXe siècle, le mathématicien perse Al-Khwârizmî décrit la manière de résoudre une équation du deuxième degré de la forme :

x2 + ax = b en prenant l'exemple suivant : x2 + 10x = 39

Voici ce qu’il nous dit : « Un carré et des racines égaux à un nombre, c’est comme si tu disais : un carré et dix racines sont égaux à trente-neuf dirhams. La règle dans ce cas est de prendre la moitié des racines, soit cinq, que tu multiplies par lui-même. Cela donne vingt-cinq. En y ajoutant trente-neuf, tu obtiens soixante-quatre. Prends-en la racine, qui est huit, et enlève à ce résultat la moitié du nombre des racines, qui est cinq. Il reste trois, qui est la racine du carré que tu veux. Et le carré est neuf. »

Dans ce dernier exemple, on peut facilement vérifier que 3 est bien une solution de l’équation et il n’a pas été nécessaire de comprendre (ni même de mentionner) la construction géométrique qui y conduit. Le point commun de ces trois exemples est que pour réaliser la tâche, il n’y a qu’à suivre les instructions. Chacune d’elles repose sur un savoir-faire très simple qui ne nécessite pas de connaissances particulières. On n’a pas besoin de connaître la ville pour rendre à la gare, on n’a pas besoin d’être pâtissier pour faire un gâteau, on n’a pas besoin de connaître la géométrie pour résoudre l’équation. Dans ces trois exemples, la procédure à suivre pour réaliser la tâche est ce que l’on appelle aujourd’hui un algorithme.

De manière un peu plus formelle : Un algorithme est défini comme une suite finie d’instructions qui permettent d’obtenir dans un temps fini la solution d’un problème. Chaque instruction correspond à une action simple et bien définie.

Programmation

Dans un article écrit en 1936, intitulé « On Computable Numbers, With An Application To The Entscheidungsproblem », Alan Turing pose les fondations de ce qui deviendra les ordinateurs que l’on connaît aujourd’hui en décrivant une machine capable d’exécuter n’importe quel algorithme : la machine de Turing universelle. Nos ordinateurs actuels étant, d’un point de vue pratique, équivalent à des machines de Turing universelle, on peut dire qu’un ordinateur est une machine capable d’exécuter n’importe quel algorithme.

Il va de soi qu’on ne va pas aller loin si l’on essaye de communiquer avec notre ordinateur en lui parlant. Pour permettre à un ordinateur d’exécuter un algorithme, on doit décrire cet algorithme dans un langage qu’il peut comprendre. Un tel langage est un appelé langage de programmation.

En première approximation, on peut donner la définition suivante : un langage de programmation est une langue artificielle qui permet de décrire un algorithme de telle manière qu’un ordinateur soit en mesure de l’exécuter.

À partir de cette définition, « programmer » est l’activité qui consiste à décrire un algorithme à l’aide d’un langage de programmation. Durant ce module, nous allons apprendre à décrire des algorithmes à l’aide du langage de programmation Java.

Langage de programmation et langue naturelle

Si les langues naturelles permettent de décrire des algorithmes (nos exemples décrivent des algorithmes en français) pourquoi ne pas les utiliser pour la programmation ? Le principal problème des langues naturelles est qu’elles ne sont généralement pas assez précises et beaucoup trop compliquées pour cet usage.

Les langues artificielles que sont les langages de programmation ne permettent certes pas d’écrire de la poésie ou des romans, mais sont beaucoup plus simples et adaptées à la description d’algorithme. Le langage Java permet de décrire n’importe quel algorithme (on dit qu’il est Turing-complet) avec seulement une cinquantaine de mots de vocabulaire appelé mots clés (keywork) et quelques dizaines de règles simples sans exception qui régissent la manière de combiner ces mots pour former des instructions (les règles de syntaxe).

Si le vocabulaire et les règles sont simples, le revers de la médaille est qu’ils doivent être scrupuleusement respectées. Un programme ne pourra pas être exécuté s’il contient la moindre erreur de syntaxe ou si un mot clé n’est pas écrit correctement. Heureusement, comme on le verra durant la première activité, les logiciels que nous utiliserons pour programmer nous viennent en aide pour faciliter la détection et la correction de ces erreurs.

Langage de programmation, langage machine et compilateur

Il est dit plus haut qu’un ordinateur peut exécuter un programme écrit dans un langage de programmation. En réalité, un ordinateur n’est capable d’exécuter un programme que si celui-ci est écrit dans son propre langage qu’on appelle langage machine. Il existe autant de langages machine que de types d’ordinateur. Un langage machine se distingue d’un langage de programmation par le fait que les instructions ne sont pas représentées par des mots, mais par des séquences de bits (des nombres binaires, des zéros et des uns). On s’en doute bien, un langage machine n’est pas un langage destiné à être lu ou compris par un humain.

Dans ces conditions, on a besoin d’un moyen pour traduire les langages de programmation que nous utilisons et avec lesquels nous pouvons raisonner, en langage machine exécutable. Heureusement, il est possible de démontrer que tous les langages Turing-complets — dont Java ainsi que tous les langages machine — sont équivalents et qu’il existe un algorithme capable de traduire un programme écrit dans un langage en un programme équivalent écrit dans un autre langage. Puisqu’il existe un tel algorithme, il est possible de concevoir un programme capable de traduire un langage dans un autre. C’est ce qu’on appelle un compilateur.

Pour résumer, un compilateur est un programme qui sert à traduire un programme écrit dans un langage de programmation appelé langage source en un programme équivalent écrit dans un autre langage appelé langage cible. Le langage cible peut être un langage machine ou un autre langage de programmation. Le code du programme écrit dans le langage source est appelé code source. Le code produit par le compilateur est appelé code objet.

De manière plus pragmatique, pour compiler un programme Java, on peut soit invoquer directement le compilateur javac en ligne de commande, soit utiliser la commande « Build Project » ou « Clean and Build Project » de NetBeans. Selon les cas, le code objet se trouve dans un fichier dont l’extension est .class ou .jar.

Nous ne sommes toutefois pas encore au bout de nos peines. En effet, le code objet produit par le compilateur javac est du bytecode Java qui ne peut pas être exécuté par le processeur du PC, mais uniquement par la machine virtuelle de Java.

La machine virtuelle de Java (Java Virtual Machine ou JVM) est un exemple de ce que l’on appelle un environnement d’exécution (runtimer). D’autres exemples sont le common langage runtime de .NET (.NET CLR) et les navigateurs web. Un environnement d’exécution est un système logiciel (un ensemble de plusieurs programmes) qui comprend notamment, une bibliothèque standard, des outils (compilateur, débogueur, etc.), et un interpréteur dont la tâche est de simuler un ordinateur capable d’exécuter le langage machine portable dans lequel sont compilés les programmes. Le but est de permettre d’exécuter des programmes sur n’importe quel système d’exploitation et n’importe quelle machine sans avoir à les recompiler.

Un environnement d’exécution est l’une des manières possibles d’exploiter le fait qu’un ordinateur peut être simuler par un programme, d’autres possibilités sont, par exemple, les émulateurs et les hyperviseurs (voir machine virtuelle).

Pour résumer, lorsque l’on programme avec le langage Java, on utilise le compilateur javac pour traduire le code Java (code source) dans un langage machine portable appelé bytecode Java (code objet) et l’interpréteur java pour exécuter ce code dans l’environnement d’exécution de Java (Java Virtual Machine ou JVM).