« DépressionClasses surchargées »

Anatomie d'un langage de programmation

08.10.13 | par Le Grincheux | Catégories: Je hais l'informatique, Matheux pervers

Comme demandé récemment, je vais tenter d'expliquer ici ce qu'est pour moi un bon langage de programmation. Je suis souvent sidéré du panurgisme patent du microcosme du développement informatique prétextant que si tout le monde utilise tel ou tel langage, on ne risquera rien à développer dans ce langage précis. Accessoirement, cela permet de se garantir des échecs dus au choix du langage en rappelant à qui veut bien l'entendre que tout le monde aurait fait de même.

Le système de défense me paraît un peu court.

En effet, il existe au moins trois types de langages :

  • les langages écrits par des informaticiens pour des informaticiens (exemples : C, C++, Forth, liste non exhaustive) ;
  • les langages écrits par les informaticiens pour des scientifiques (exemples : Fortran, Ada, Lisp, liste non exhaustive elle aussi) ;
  • les langages de prototypage (souvent mauvais comme Matlab, Python, liste encore moins exhaustive).

Les deux premières catégories doivent pouvoir être compilées ou semi-compilées. Quant à la troisième, rien ne s'oppose à ce qu'elle soit interprétée. Et chacun des langages peut être impératif, procédural, fonctionnel, objet voire ne ressembler à rien de connu. Il existe dans le bizarre, l'ésotérique ou le carrément mal foutu mais utilisé un nombre de langages assez impressionnant dont php et Perl.

Commençons par regarder de près les différents paradigmes de programmation et éludons immédiatement celui de la programmation impérative (typiquement celle des Basic historiques ou du Cobol à l'ancienne) qui n'a aucun intérêt sur les calculateurs modernes. La programmation impérative se justifiait à une époque où les piles des processeurs étaient limitées et où l'on n'avait pas encore inventé autre chose. Aujourd'hui, c'est une hérésie.

Un peu plus complexes, les langages procéduraux ou fonctionnels sont intéressants. Ils permettent une bonne isolation des données et sont structurés. Les données procèdent des programmes, ce qui est assez logique. En d'autres termes, le développeur écrit un programme qu'il va appliquer sur des données. En revanche, à l'autre bout du tableau figurent les langages orientés objets. Le concept de langage objet poussé à l'extrême revient à affirmer que les programmes procèdent des données. Il s'agit donc dans un premier temps de décrire les structures des données utilisées avant d'écrire les méthodes permettant de les manipuler. C'est, d'un point de vue logique assez intéressant, mais d'un point de vue de la consommation des ressources totalement contre-productif. En effet, manipuler des objets sous la forme de classes qui héritent d'un ou de plusieurs parents et qui contiennent des fonctions virtuelles résolues ou non lors de la compilation ne se fait qu'avec une débauche de mémoire et de temps processeur.

Pour fixer les idées, je vais évoquer une petite expérience. J'ai dû utiliser un algorithme de recherche du meilleur chemin dans un graphe orienté, le graphe en question contenant 15 millions d'arcs orientés. J'avais estimé que sur une machine de calcul munie de 8 Go de mémoire, cela devait passer sans aucun problème. Étant d'une fainéantise crasse, j'ai tenté de réutiliser la fonction A* de la bibliothèque Boost, programmée en C++. J'ai rapidement abandonné l'idée, les 8 Go de mémoire suffisant à peine à faire tourner un calcul. En implantant le même algorithme A* en RPL/C (un langage inspiré du C, procédural, permettant de s'interfacer avec le RPL/2), j'ai divisé l'empreinte mémoire du graphe par 20 et le temps d'exécution par 25. En effet, avec un langage procédural ou fonctionnel, lorsqu'on demande une banane, on la prend dans le panier. On n'est pas contraint à appeler un singe qui vient avec tous ses copains de la jungle pour apporter la banane.

Ainsi, un langage efficace du point de vue des ressources de la machine est un langage procédural ou fonctionnel. Le langage impératif est efficace, mais n'offre pas d'isolation entre les données des différents sous-programmes.

Parlons de la syntaxe et des fonctionnalités d'un langage. Il n'est pas tout de déclarer qu'un langage efficace du point de vue de la machine et non des neurones du développeur doit être procédural ou fonctionnel (risquons même le fonctionnel impur), faut-il encore que sa syntaxe évite les erreurs grossières, voulues ou non. En effet, il y a plusieurs écoles de pensée radicalement différentes. D'un côté se trouvent les langages où tout est permis, langages bizarrement écrits dans la période suivant 1968. Sans doute un relicat du slogan il est interdit d'interdire… Figurent dans cette classe les langages comme le C. Le compilateur ne fait aucune vérification sur l'air du « vous l'avez voulu ? Eh bien tant pis pour vous ! ». Les résultats peuvent être assez dramatiques, allant de la simple violation d'accès à l'explosion d'ariane V.

Là, il me faut tout de même parler de l'opérateur d'affectation. En C comme dans l'immense majorité des langages, il s'agit du signe « = ». Logique me direz-vous. Mais comme en C, contrairement au Basic, il est possible d'écrire plusieurs expressions encapsulées les unes dans les autres et qu'il est aussi possible d'omettre implicitement les comparaisons à 0 et que, selon l'implantation, l'évaluation d'une expression contenant des et logiques peut se faire de gauche à droite et s'arrêter à la première sous-expressions fausse, on peut trouver des choses amusantes qui ressemblent à :

if ((options == (__WCLONE|__WALL)) && (current->uid = 0))
retval = -EINVAL;

Vous ne revez pas. Cette ligne était une backdoor introduite dans le noyau Linux quelque part entre les noyaux 2.4 et les 2.6. Comment est évaluée l'expression du test ? Si la variable options vaut exactement __WCLONE|__WALL, le résultat de la première sous-expression est vrai et l'exécution se poursuit par l'évaluation de current->uid = 0 qui n'est pas un test mais une affectation. Comme la valeur affectée est nulle, la clause de test est toujours fausse et le programme ne positionne jamais retval. Au passage, l'uid courant passe à 0, ce qui donne les droit root au programme utilisant cet appel système avec les paramètres __WCLONE|__WALL. Propre, efficace et parfaitement licite du point de vue du C.

Je passe sous silence le bloc de commandes

retval = -EINVAL;

qui n'est pas délimité car réduit à une seule expression. Que se serait-il passé si par pure étourderie un point-virgule avait malencontreusement terminé la ligne précédente ? Un bloc de programme ne doit jamais être défini implicitement. Comme il ne doit pas être défini non plus en fonction de la forme comme en Python.

Dans un langage à la syntaxe bien conçue, cela ne devrait jamais arriver. Un test doit toujours être explicite en notation algébrique et les blocs doivent être clairement indiqués. Par ailleurs, utiliser une répétition de symbole « == » comme opérateur de test alors que le symbole « = » correspond à une affectation est une aberration. À minima, il faudrait écrire :

if ((options.eq.(__WCLONE+__WALL)).and.(current%uid.eq.0)) then
retval = -EINVAL
end if

Si par malheur l'opérateur de comparaison « .eq. » avait été remplacé par une affectation, le compilateur aurait refusé de faire son œuvre. Le compilateur C aurait tout aussi bien pu râler parce qu'il effectue une opération booléenne entre un booléen et un entier. Mais comme cela n'est pas interdit en C, il ne trouve rien à y redire. Des choses plus amusantes peuvent être écrites en C comme :

unsigned char *ptr;
...
if ((!ptr) && (ptr->n == 0)) retval = -EINVAL;

Je vous laisse deviner le résultat si le compilateur ne s'arrête pas à la première sous-expression fausse ou s'il décide de ne pas évaluer l'expression de gauche à droite. Sans compter le fait que le pointeur NULL n'est pas forcément défini comme étant 0x0. J'ai un souvenir d'un système sur lequel NULL valait 0x1. De deux choses l'une, soit le compilateur considère alors qu'un test !ptr était implicitement fait par rapport à NULL et non à 0 parce que l'opérande est un pointeur, soit il s'en tient à un comportement qui n'est pas plus bête qui consiste à comparer l'adresse par rapport à 0. Passons. Dans 99,9% des cas, le compilateur est gentil et fait ce que le développeur lui demande implicitement. Restent les 0,1% des cas.

Un autre problème et une source d'ennuis incommensurable. Dans la plupart des langages, les données sont typées parce que les variables doivent être déclarées et qu'une donnée ne peut exister en dehors d'une variable. Hormis quelques langages à inférence de types, l'immense majorité des langages considère que les données doivent avoir un type et un seul, que ce type soit affecté explicitement lors de la déclaration de la variable, cas du C, d'Ada, du Cobol, de Java ou du Fortran, ou qu'il le soit implicitement en fonction du nom de cette variable comme en Basic. Le problème sous-jacent est alors le choix de la structure algébrique dans laquelle les calculs vont se faire.

Si lors de calculs en flottants, la majorité des langages est tombée d'accord pour travailler sur la droite achevée réelle, le cas est un peu différent lors des calculs en entiers. Certains langages utilisent une arithmétique brutale en complément à deux sans aucune vérification d'intégrité. Ainsi, si une variable est déclarée sur un octet, 127+1 donne… -128 ! Sans aucune erreur récupérable par le programme. D'autres langages considèrent que 127+1 vaut toujours 127. D'autres encore génèreront une erreur de dépassement. Aucun des résultats n'est mathématiquement acceptable. De la même façon, l'extraction de la racine de -1 provoquera une erreur même si -1 est déclaré comme un flottant.

Un langage — je parle ici d'un langage destiné à des calculs, pas à un langage comme le C destiné surtout à l'écriture de systèmes d'exploitation et de programmes de bas niveau — doit donc pouvoir changer le type de la donnée au vol en fonction du résultat d'une commande. Si un calcul ne peut se faire jusqu'au bout en entier, il doit passer automatiquement en flottant voire en complexe. Mais cela ne peut se faire de façon efficace que si les données existent indépendamment des variables, ce qui implique un langage à pile comme le Forth.

Mais le Forth n'est pas satisfaisant car il n'utilise ni pile banalisée ni typage fort. C'est au développeur de savoir ce qu'il a empilé, combien d'emplacements sur la pile cela prend et comment il doit les relire. Ainsi, si le Forth permet de coder très rapidement des petits programmes, son utilisation devient assez rapidement très complexe et fastidieuse.

Un dernier problème et non des moindres. La gestion de la mémoire, de la pile système et, insidieusement, celle des goto's considérés comme nuisibles par certains. La mémoire peut être gérée de façon explicite par allocation dynamique, donc par augmentation de la taille du tas, ce qui est le cas avec les fonctions allocate() du Fortran, malloc() du C et new du C++. En C++, new crée un nouvel objet en appelant son constructeur. Sauf erreur manifeste du programme, le delete correspondant va se charger de libérer toute la mémoire occupée par cet objet (pas forcément dans le sens contraire aux appels effectués par new, ce qui peut poser des problèmes complexes dans le cas de fonctions virtuelles). Mieux, si l'objet est alloué comme une variable automatique, l'appel au destructeur sera implicite lors du retour de la fonction. L'utilisateur n'a donc pas à se soucier des problèmes de gestion de la mémoire. En C et en Fortran, il faut explicitement appeler deallocate() ou free(). Le compilateur ne le fera pas de son propre chef. Il faut donc savoir très exactement ce que l'on fait et quand on doit le faire. En cas de retour anticipé d'une fonction, par exemple en cas d'erreur, ce qui est fait automatiquement en C++ la plupart du temps doit se faire à la main dans d'autres langages. Et c'est généralement là qu'on rigole ! Ou qu'on pleure, c'est selon. J'ai eu l'occasion de fréquenter des doctorants, pourtant spécialistes des mathématiques qui s'évertuaient à coder des bouts de programmes en C en effectuant des malloc() à chaque besoin de mémoire sans jamais ne penser à appeler free(). Pourquoi en C ? Parce qu'un marteau, c'est tellement pratique pour enfoncer un clou lorsqu'on n'a jamais vu de tournevis ! Ce qui aurait été trivial en Fortran ne l'était réellement pas pour eux en C parce qu'ils ne maîtrisaient pas du tout le langage ni ses implications.

Et le rapport avec les goto's, me direz-vous ? Il est pourtant assez simple. La plupart des langages autorise ces branchements à l'intérieur d'une procédure. C'est pratique, cela économise souvent l'écriture de boucles longues et fastidieuses sous l'air de un goto et ça repart ! Mais cela impose aussi au compilateur de réserver sur la pile toutes les variables automatiques en début de procédure même si celles-ci ne sont utilisables que dans un bloc de programme. La conséquence de ce choix est que seule l'analyse syntaxique effectuée durant la compilation permet de masquer ces variables. Sans cela, l'utilisation des goto's aboutirait à une corruption de la pile système ou à une complexité démentielle. Le corollaire de la disponibilité du goto dans un langage est un côté implicitement statique des variables déclarées dans des blocs de programme à moins que le compilateur ne fasse un travail d'allocation spécifique et coûteux.

Une réflexion de quelques années sur tous ces problèmes et la rencontre avec des doctorants n'ayant aucune compétence en développement informatique mais étant contraints de programmer des algorithmes m'a décidé de me pencher sur ces différents problèmes. Un langage utilisable par un non spécialiste de l'architecture des systèmes, typiquement un mathématicien ou quelqu'un qui n'a pas à connaître les entrailles des calculateurs pour écrire un programme, doit répondre aux caractéristiques suivantes :

  • langage procédural ou fonctionnel impur ;
  • langage à inférence de type ;
  • séparation stricte de la notion de donnée de celle de variable, la variable n'étant qu'une donnée de type nom référençant une autre donnée ;
  • aucune allocation ou libération de la mémoire explicite, aucun accès à des pointeurs ;
  • aucune instruction de type GOTO, mais possibilité de sortir d'une boucle par anticipation ou de boucler par anticipation ;
  • évaluation de tous les éléments d'une expression même si le résultat est connu d'avance ;
  • extension des domaines de définition des fonctions mathématiques pour garder autant que possible un résultat exact à la précision près du processeur ;
  • aucun mécanisme d'affectation en notation algébrique ;
  • des garde-fous pour éviter les erreurs manifestes (éléments en dehors d'un tableau…) ;
  • séparation du fond et de la forme.

La somme de tous ces critères aboutit à un langage utilisant la notation polonaise inversée sans laquelle le troisième critère n'est pas atteignable, semi-compilé et à préprocesseur. Ce langage, quoique très structuré, ne connaît pas la notion de ligne. Il permet de se concentrer sur l'écriture d'un algorithme au sens mathématique du terme tout en évitant de se poser les questions inhérentes à l'architecture cible.

Ceux qui sont intéressés par mes travaux trouveront plus d'informations ici.

 

2 commentaires

Commentaire de:
atg

Merci de tout coeur pour cette contribution !

09.10.13 @ 10:23
Commentaire de: Le Grincheux

Je vous en prie.

09.10.13 @ 12:18


Formulaire en cours de chargement...

Une erreur inattendue est survenue!

Si cette erreur persiste, merci de la signaler à l'administrateur.

Retourner à la page d'accueil

Informations additionnelles à propos de cette erreur:

MySQL error!

Incorrect key file for table './b2evolution/evo_hitlog.MYI'; try to repair it(Errno=126)

Your query: Autopruning hit log

DELETE
  FROM evo_hitlog
 WHERE hit_datetime < "2018-01-08"