Valid XHTML 1.0!                  

 

 

  [petite] histoire des
  Langages de Programmation

 

     (gH) gilles.hunault@univ-angers.fr

 

 

3. Qu'est-ce qu'un langage de programmation ?

 

Programmer un ordinateur c'est lui donner des ordres, des instructions que la machine doit exécuter. Ces ordres sont écrits dans un langage informatique particulier, nommé langage de programmation. Comme tout langage informatique, et contrairement à une langue [humaine], ce langage est rigide, fixe, normalisé, de façon à ce que l'ordinateur puisse controler, vérifier, exécuter les phrases de ce langage.

Il y a plusieurs paradigmes pour classer les langages de programmation, selon

  • l'objectif du langage,
  • le type de traitement des programmes,
  • l'importance du langage,
  • le type de licence et le cout du langage.

Ces diverses propriétés pour les langages ne sont pas orthogonales ni même contradictoires et certains langages possèdent plusieurs de ces caractéristiques dans diverses versions, dialectes, implémentations...

L'objectif du langage peut être le calcul scientifique (Fortran, Apl) ou le calcul mathématique formel et/ou appliqué (Maple, Mathematica). Ce peut être aussi des travaux de gestion (Cobol) ou de bases de données (Dbase, Sql, Sasl). L'objectif peut enfin être déductif ou "logique" (Prolog) à moins que ce ne soit un objectif "universaliste" pour "tout" programmer -- avec plus ou moins de facilités -- avec ou sans interface graphique (C, Pascal, Java, Perl).

Le type de traitement des instructions, en fonctions, procédures, prédicats, programmes se fait via la compilation ou l'interprétation. La compilation traduit l'ensemble des instructions de départ nommé le "code-source" en un code machine intermédiaire qui après une édition de liens est un code-assembleur exécutable par la machine. On peut ne fournir que cet "exécutable" et l'utilisateur ne sait alors rien de ce qu'il y a dans le programme sauf ce qu'il utilise et ce qu'il voit dans l'interface utilisateur (menus, fenêtres...) si elle existe. L'interprétation consiste à lire les instructions une à une au fur et à mesure de l'exécution. L'analogie classique avec un serveur de restaurant compare la compilation à la prise de la commande pour l'ensemble d'un groupe de personnes alors que l'interprétation consiste à demander à une personne ce qu'elle veut, traiter sa commande puis passer à une autre personne ainsi de suite. De nombreux interpréteurs ont aujourd'hui un mécanisme de précompilation, notamment pour tester la validité de la syntaxe des programmes. Pour exécuter un programme interprétable, il faut disposer du code-source et d'un "exécutable" nommé "interpréteur du langage". Traditionnellement C, C++, Pascal, Ada, Java, Fortran, Cobol... sont des langages compilés alors que Apl, Awk, Rexx, Perl, Prolog, Javascript, Tcl/Tk, ont des langages interprétés.

 

Au bout du compte, même pour une affectation simple telle que




   A <-- B + C x D



c'est un code "binaire" qui est exécuté, comme



   000100111011000101001010101010
   010000101010101010101010101010



même si le plus souvent
  • on le lit en hexadécimal
    
    
       41 30 C1 A4
       3A 20 C1 A8
       1A 30 C1 A0
       50 30 C2 A4
    
    
    
    
  • on l'écrit en assembleur...
    
    
    
       LDA C
       MUL D
       ADD B
       STO A
    
    
    
    
  • ... ou dans un langage dit "évolué"
    
    
    
       #  on ajoute à la commande en cours (A)
       #  le solde précédent (B) et la vente
       #  réalisée : produit du prix unitaire (C)
       #  par le nombre d'articles (D)
    
       cmdCour_A  <-- solde_B + (prixu_C x nbArt_D)
    
    
    
    

 

L'importance du langage se décline en cinq genres principaux :

  • les "petits" langages de script (Awk, Rexx, Perl, Tcl),
  • les langages d'interrogation (Sql, Dbase, Sasl),
  • les langages d'interfaces graphiques (Tk) ou d'interface Web (Javascript, Php),
  • les "grands" langages quasi-universels ou ciblés comme (C, C++, Pascal, Ada, Java, SmallTalk et Lisp, Prolog, Maple, Mathematica),
  • les langages "exotiques" dont le but n'est pas toujours clair.

Dans un langage de programmation, on peut soit indiquer comment faire avec un langage impératif, soit indiquer ce qu'on veut faire avec un langage déclaratif (spécificatif ?), le mécanisme de gestion du langage gérant alors comment réaliser ce qu'on veut faire.

Les langages impératifs peuvent être divisés en trois catégories :

  • les langages peu structurés comme Basic, Fortran,
  • les langages structurés par blocs comme Pascal, C,
  • les langages conçus comme langages objets comme SmallTalk, C++, Java, Ada.

Les langages déclaratifs ont des natures différentes : on distingue

  • les langages fonctionnels comme Lisp,
  • les langages logiques comme Prolog,
  • les langages orientés bases de données comme Dbase, Sql, Sas.

Certains langages sont typés explicitement ce qui signifie que les variables doivent être déclarées selon des moules prédéfinis nommés types, comme par exemple byte, integer, longint pour une variable entière. Le typage impose des restrictions car il contraint le programmeur à déclarer beaucoup de choses. En retour la machine peut vérifier que tout se passe comme prévu et que rien ne "déborde". Un langage peu typé ou typé non explicitement permet au programmeur de passer "du coq à l'ane" sans que cela pose problème à condition qu'il connaisse bien la zoologie ! Traditionnellement, les langages de script (Awk, Rexx, Perl, Tcl/Tk) ainsi qu'Apl sont non typés explicitement. Par contre les langages compilés (C, C++, Pascal, Ada, Java, Fortran, Cobol) sont pratiquement toujours [fortement] typés explicitement.

Pour les langages impératifs, l'exécution d'un programme est linéaire, c'est à dire qu'elle s'effectue d'une instruction à la suivante, sachant que l'instruction suivante n'est pas forcément la ligne consécutive dans le fichier à cause des mécanismes de "controle du flot" que sont les tests, les boucles et les appels de sous-programmes. Pour un langage déclaratif, une fois le but à atteindre ou le calcul à effectuer, l'exécution du langage suit un mécanisme d'exploration, de résolution ou d'interrogation qui est en général propre au langage.

Le cout du langage à l'achat varie de zéro pour des langages libres ou avec une licence GNU, comme pour Awk, Rexx/Regina, Perl, Gcc à plusieurs centaines voire plusieurs milliers d'euros pour les logiciels développés par des sociétés privées, comme par exemple Maple, Oracle... Toutefois dans un certain nombre de cas, des versions plus ou moins limitées, sont disponibles, sous l'appellation "éducation" ou "étudiant" à moins que ces versions ne soient utilisables que pour une durée déterminée, soit traditionnellement un mois.

La gestion des "exceptions" dans une mauvaise traduction de l'anglais est ce qui touche à la surveillance des erreurs, que ce soit des erreurs d'exécution interne, comme par exemple une division par zéro ou une erreur d'exécution externe comme la lecture d'un fichier qui n'existe pas.

L'apport de la méthodologie objet a contraint certains anciens langages à modifier la syntaxe de base pour conserver des adeptes. Ainsi Pascal, langage non objet de conception est devenu Pascal Objet puis Delphi ; de même Lisp non objet à ses débuts a vu une variante nommée Clos lui conférer le statut de langage à objets. On nomme souvent ces langages "orientés objets" pour les distinguer des langages vraiment objets ou encore "langages objets purs" dont SmallTalk est le plus pur, suivi par C++ et Java.

 

S'il est relativement facile d'apprendre un petit langage comme Awk, Rexx ou Perl lorsqu'on sait déjà programmer dans un autre langage, il est beaucoup plus difficile d'aborder des langages originaux comme Apl, Lisp ou Prolog. La plupart des langages impératifs ont d'ailleurs souvent une syntaxe voisine qui permet d'utiliser un langage algorithmique commun comme celui de Galg que nous avons implémenté en français offrir une traduction presque totalement automatique dans ces langages, ce qui ne peut pas être le cas ni pour Apl ni pour Lisp et Prolog.

Dans ce genre de langage algorithmique impératif, il y a peu d'instructions à connaitre, la richesse et la difficulté venant du nombre d'instructions contenues dans l'algorithme ou le programme. On distingue classiquement

  • les commentaires,
  • les affectations,
  • les structures (tests et boucles),
  • les appels de "fonctions standards",
  • les appels de sous-programme.

Le but des algorithmes est de faciliter la communication entre humains alors que le but des programmes est de commander les machines. Les algorithmes sont donc souvent [ou ils devraient l'être] plus lisibles, moins ambigus, moins contextuels. Si on utilise une même notation dans les langages pour indiquer la fin d'une instruction composée, c'est parce que cela fait moins de texte à manipuler. La gestion par l'ordinateur en sera plus rapide. Par contre, pour un humain, avoir plus de mots est un gage de meilleure lisiilité. Il suffit de comparer les deux textes suivants pour s'en rendre compte.




  Programme
  ---------


    AAAAAAAA  ;
    if ($x==2) {
       BBBBBB ;
    } else {
      foreach CCCCCC  (sort split(" ",$vvvt)) {
          DDDDDD ;
      } ;
    } ;

  Algorithme
  ----------

    AAAAAAAA  ;
    si x=2
    |  alors BBBBBB ;
    |  sinon
    |    pour chaque mot # du tableau trié
    |       DDDDDD
    |    fin pour #
    fin si # sur x = 2




S'il est vrai que la traduction des algorithmes en programmes demande une certaine souplesse (le "bol de café" français devient la "cup of tea" des anglais), les algorithmes à notre sens sont incontournables. Pourtant, peu de gens écrivent des algorithmes. Et on trouve encore parfois [ce qu'il faudrait pourtant éviter], à savoir des textes comme (exemples vus sur le net) :

algorithme 1                algorithme 2

Notre manuel d'Algorithmiques raisonnées essaie de convaincre depuis quelques années les étudiants de faire "bon et bien" en français (ou dans une langue natale). On verra ce qu'il en restera...

L'interface et l'analyseur d'algorithmes développés [par des étudiants de la licence informatique à la Faculté des Sciences d'Angers] pour aller avec le langage asocié (Galg) évitent lorqu'on apprend à programmer ou lorsqu'on ne s'intéresse qu'à l'exactitude de l'algorithme d'avoir à traduire, à exécuter. C'est presque trop beau !

Contrairement aux programmes, les algorithmes ne sont pas limités, que ce soit par la taille des tableaux ou par les problèmes d'implémentation... Par exemple depuis le langage Awk, la notion de tableau associatif ou table de hachage, qui revient à utiliser une chaine de caractère comme indice est devenu un standard des nouveaux langages. L'utiliser en algorithmique est naturel : on passe de l'écriture


clar[ numi ]

à l'écriture


naar[ stri ]

c'est à dire qu'on utilise une même syntaxe


tableau[ indice ]


même si dans le premier cas numi est numérique comme dans


score[ 2 ] <--  vdsc  # on a trouvé le deuxième meilleur score


alors que dans le second cas stri est caractère comme dans


ventes[ "pierre" ] <--  mnvt # valeur des ventes pour pierre


La même remarque s'applique à la gestion "moderne" et "évoluée" des chaines de caractères qu'on nomme "expressions régulières" qui permette de définir des ensembles de "mots" à partir de modèles, comme par exemple "a*s" pour exprimer qu'il s'agit de mots qui commencent par "a" et qui finissent par "s". On peut toujours écrire en algorithmique


txt <-- retrouveExpReg("Donald*Mickey",histoire)


même si on ne sait pas (encore) si ce sera disponible dans le langage... Il sera toujours temps de l'inventer au cas où...

 

 

Voici sur quelques exemples les difficultés que pose la programmation, une fois qu'on sait que le problème peut être résolu par un programme, ce qui n'est pas une mince affaire.

1. Tout d'abord essayons de voir pourquoi un énoncé simple comme celui de la permutation de deux variables pose problème, à savoir "quelle solution choisir ?" (si déjà on arrive à en trouver plusieurs...) C'est pourquoi il faut écrire beaucoup de commentaires pour bien décrire la méthode utilisée et les choix retenus.

La permutation des variables consiste à échanger leurs contenus. Par exemple, si la variable valA vaut 2 et la variable valB vaut 6, quelles instructions faut-il écrire pour que valA contienne la valeur de valB c'est à dire 6 et que valB contienne la valeur de valA c'est à dire 2 ?

L'algorithme immédiat


     affecter valA  <--  valB
     affecter valB  <--  valA

est bien sur faux car dès la première instruction il ne reste plus aucune trace de la valeur de valA . Avec un peu de réflexion, on peut trouver divers algorithmes qui viennent résoudre le problème (ce qui va nous amener à établir des critères de choix entre les algorithmes).

Comme première solution, on peut utiliser la méthode des "petits pas" et écrire soigneusement un algorithme en quatre instructions avec une sauvegarde de chacune des variables valA et valB :


     # permutation des variables valA et valB
     # solution 1 : les "petits pas " (ou : la double sauvegarde)

       affecter sovA  <-- valA // sauvegardes
       affecter sovB  <-- valB

       affecter valA  <-- sovB // affectations
       affecter valB  <-- sovA

D'aucuns préféreront une seule sauvegarde et des transpositions menant à ce qu'on appelle en mathématiques une permutation cyclique (ou circulaire) :

bouteilles

     # permutation des variables valA et valB
     # solution 2 : les permutations circulaires
     # solution aussi nommée "pain et saucisson"

       affecter vin   <-- valA
       affecter valA  <-- valB
       affecter valB  <-- vin

Cette méthode s'appelle aussi la méthode "de la bouteille" (d'où l'appellation "vin" comme nom de la variable de sauvegarde). Elle correspond aux manipulations à effectuer (rinçage des bouteilles non compris) quand on veut transvaser le contenu de deux bouteilles nommées valA et valB : on commence par mettre le contenu de valA dans une autre bouteille (vin) puis on remplit valA avec le contenu de valB et il ne reste plus qu'à remplir valB avec le contenu de vin. D'autres encore préféreront ne pas faire de sauvegarde mais de savants calculs, comme :


     # permutation des variables valA et valB
     # solution 3 : les calculs bijectifs

       affecter valA   <-- valA + valB
       affecter valB   <-- valA - valB
       affecter valA   <-- valA - valB

Il y a bien sûr bien d'autres algorithmes répondant au problème, notamment ceux qui sont duaux de ceux présentés, (qu'on obtient en interchangeant le nom des variables) ou similaires ; ainsi le dernier algorithme peut se réécrire


     # permutation des variables valA et valB
     # solution 3 bis : d'autres calculs bijectifs

       affecter valB   <-- valB - valA
       affecter valA   <-- valA + valB
       affecter valB   <-- valA - valB

Par contre, ce serait maladroit de réécrire un algorithme avec les opérations * et / à la place de + et - (même si l'algorithme est acceptable pour des valeurs non nulles).

Un algorithme tel que


     # permutation des variables valA et valB
     # solution 3 ter : calculs bijectifs (maladroits)

       affecter valA   <-- valA * valB
       affecter valB   <-- valA / valB
       affecter valA   <-- valA / valB

est donc déconseillé car il introduit des cas particuliers (celui où valA vaut 0, celui où valB vaut 0) et peut se révéler incorrect lors de calcul d'arrondi (une division par 3 ou par 7 par exemple, peut ne pas donner le "bon" résultat en pratique).

Si le choix de l'algorithme se fait sur la justesse, il faut rejeter la solution 3 ter. Si on cherche la lisibilité, il faut écarter la solution 3. Les solutions 1 et 2 sont peu différentes et notre préférénce ira à la solution 2 car plus courte. Signalons au passage que ces solutions 1 et 2 sont générales : elles s'appliquent aussi lorsque valA et valB sont des variables caractères, ce qui n'est pas le cas des solutions calculatoires.

Il peut paraitre étonnant de trouver autant de solutions pour un problème aussi simple. Après réflexion, pour chaque situation il y a souvent de nombreuses façons d'arriver au but. L'analyse et la discussion algorithmique servent aussi à explorer cette diversité des méthodes, à fixer les choix (ou tout au moins à les expliciter), sachant que le libre arbitre et les justifications sont ici affaire de gout et d'esprit plutôt qu'application de la science.

Il faut donc en déduire qu'un «bon» ne se définit pas par son nombre de lignes, son interface utilisateur ou le langage sous-jacent mais bien par la qualité de sa documentation.

2. Comme deuxième problème posé par la programmation, citons celui de la lisibilité, de la relecture et de la maintenance des programmes. Si on doit afficher par ordre croissant le contenu de trois variables nommées valA, valB et valC, alors l'algorithme 1 que voici

en ordre


     SI (valA < valB) et (valB < valC)
        ALORS ECRIRE valA, valB, valC
        SINON Si (valA < valC) et (valC < valB)
                 Alors Ecrire valA, valC, valB
                 Sinon si (valB < valA) et (valA < valC)
                          alors ecrire valB, valA, valC
                          sinon sI (valB < valC) et (valC < valA)
                                   aLORS ecrire valB, valC, valA
                                   sINON si (valC<valA) et (valA<valB)
                                            alors ecrire valC, valA, valB
                                            sinon ecrire valC, valB, valA
                                         finsi...
                                fINSI (# valB < valC) et (valC < valA)
                       finsi # (valB < valA) et (valA < valC)
              Finsi # (valA < valC) et (valC < valB)
     FINSI # (valA < valB) et (valB < valC)

répond au problème (après vérification) mais il est un peu "lourd".

L'algorithme numéro 2 que voici


     SI valA < valB
        ALORS Si valB < valC
                 Alors Ecrire valA, valB, valC
                 Sinon si valC < valA
                          alors ecrire valC, valA, valB
                          sinon ecrire valA, valC, valB
                       finsi si valC < valA
              Finsi #  valB < valC
        SINON Si valA < valC
                 Alors Ecrire valB, valA, valC
                 Sinon si valC < valB
                          alors ecrire valC, valB, valA
                          sinon ecrire valB, valC, valA
                       finsi
              Finsi #...
     FINSI # lA < valB

est un peu plus lisible, quoique...

Si on n'a pas peur de lister tous les cas, on peut écrire l'algorithme 3 que voici


    aux cas où
     cas (valA < valB) et (valB < valC)
          ecrire valA, valB, valC
     cas (valA < valC) et (valC < valB)
          ecrire valA, valC, valB
     cas (valB < valA) et (valA < valC)
          ecrire valB, valA, valC
     cas (valB < valC) et (valC < valA)
          ecrire valB, valC, valA
     cas (valC < valA) et (valA < valB)
          ecrire valC, valA, valB
     cas (valC < valB) et (valB < valA)
          ecrire valC, valB, valA
    fin des cas

L'algorithme 4, plus mathématique, s'écrit


     affecter VALu  <-- min( valA, min(valB,valC) )

     affecter VALd  <-- min( max(valA,valB),
                    min( max(valA,valC),max(valB,valC) ) )

     affecter VALt  <-- max( valA, max(valB,valC) )

     ECRIRE VALu, VALd, VALt { comme Un, Deux, Trois }

mais encore faut-il être capable de l'inventer.

Une "bonne solution" à ce problème est sans doute de transférer les variables dans un tableau puis de trier le tableau avant de l'afficher, soit l'algorithme


     affecter tabVAL[1]  <-- valA
     affecter tabVAL[2]  <-- valB
     affecter tabVAL[3]  <-- valC

     appeler  triTableau( tabVAL , 1, 3)
     appeler  afficheTableau( tabVAL , 1, 3)

3. Comme troisième problème, à savoir la difficulté de bien programmer, prenons le fameux problème des

tours de hanoi
tours de Hanoi... et de la fin du monde !

Vous pouvez vous entrainer à essayer de le résoudre à l'aide de la page suivante

hanoi.htm

Pour ceux qui veulent lire en détail les explications mathématiques, nous conseillons la page Web de cut the knot pour les explications informatiques, sans oublier des exemples de programmes sur le site imprononçable htonwebe.

Avec un bel appel récursif, le problème se réduit à écrire :



      procédure hanoi(h,f,w,t) // exemple d'appel : hanoi(5,'A','B','C')

      si (height >= 1) alors

            hanoi(height-1, fromPole, withPole, toPole);
            moveDisk(fromPole, toPole);
            hanoi(height-1, withPole, toPole, fromPole);

      fin_de_si

ce qui peut même se simplifier (avec une seule seule variable paramètre) en


     procédure hanoi(h) // exemple d'appel : hanoi(5)

     si (height >= 1) alors

            appeler  hanoi(height-1);
            appeler  moveDisk(height);
            affecter Pole <-- Neighbor((TowerHeight - height + 1) %2);
            appeler  hanoi(height-1);
            affecter Pole <-- Neighbor((TowerHeight - height) %2);

     fin_de_si

Une solution non récursive (c'est à dire qui ne s'appelle pas elle-même) est donnée par


            pour s de puissance(2, height) à -1 par pas de -1
              affecter height <-- 1;
              affecter power2Height <-- 2;
              tant que (s % power2Height = 0)
                 affecter height <-- height + 1
                 affecter power2Height <--  power2Height * 2
              fin_tant que
              appeler moveDisk(height);
           fin_pour s

 

Suite de l'exposé : quels problèmes ne peut-on programmer  ?

 

 

        retour au plan de l'exposé  

 

  retour gH    Retour à la page principale de   (gH)