Programmation:Introduction

Introduction à la programmation

Présentation générale de l'année

Le cours d'informatique pratique de deuxième année des classes préparatoire à pour objectif d'introduire et d'approfondir les notions fondamentales de la programmation. Ce cours s'appuie sur quatre axes:

1. Programmation fonctionnelle (OCaml)
2. Programmation procédurale, impérative et structurée (C)
3. Programmation système
4. Conception et organisation des programmes

Ces quatre axes ne correspondent pas forcément à un déroulement chronologique du cours, mais plus à un objectif de connaissances à acquérir sur cette année de spé. Les deux premiers axes sont les plus gros et occuperont des séances entières tandis que les deux autres (système et organisation) apparaîtront en filigrane de nombreux cours.

Cours d'introduction

Ce premier chapitre du cours introduit les quatre axes cités plus haut, présente les objectifs et les motivations de ce cours et termine par une introduction à la programmation d'un point de vue conception.

Qu'est ce que programmer ?

Cette question est plus complexe qu'elle n'en a l'air. En effet, la programmation semble se définir simplement par le fait d'écrire des programmes (ce qui parait bien logique) mais en réalité, les choses ne s'arrête pas là. Écrire des programmes est une activité plutôt simple, par contre la conception, l'organisation et la validation de ces programmes est quelque chose de bien plus complexe.

Même si, on a parfois tendance à séparer ces activités amont de la programmation et à les rattacher à d'autre domaine (besoins métiers, génie logiciel, modélisation, algorithme ... ) elles font partie intégrante de la programmation et ne peuvent se concevoir sans une forte compréhension de l'activité de programmation à proprement parler.

Au final, la programmation est donc la coordination d'activités de conception (étude des besoins, spécifications, modélisations ... ) et d'activité de réalisation à proprement parler (implantations, programmations, optimisations ... ) On ne doit pas non plus oublier les activités de validation (scénarios, tests unitaires, intégrations, recettes ... )

Notre objectif cette année sera de bien comprendre les fondements de la partie technique sans pour autant négliger certains aspects de conception et validation.

Evolve or die !

Un monde changeant

Un autre aspect important de la programmation concerne le caractère dynamique du monde de l'informatique. L'informatique est une science jeune, dans laquelle de nombreux progrès sont encore à faire, notamment en terme de technologie, de langage ou de système. Il est donc important pour un vrai programmeur d'être adaptable.

L'informatique a beaucoup évoluée depuis les débuts à la fin de la seconde guerre mondiale: arrivée des transistors puis des circuits intégrés, développement des langages de programmation, développement des systèmes d'exploitation, amélioration de l'interface avec l'utilisateur (de la carte perforée aux bureaux graphiques d'aujourd'hui en passant par les télétypes, les terminaux textes ... ) Ces évolutions continuent et touchent tout autant le matériel que le logiciel, mais aussi les fondements théoriques ou la modélisation.

L'histoire de l'informatique a montré qu'il était souvent difficile de faire des prédictions efficaces sur l'avenir des technologies qui feront l'informatique de demain. Certains langage par exemple ont disparu alors que beaucoup leur prévoyaient un grand avenir (connaissez vous Algol, Simula, Modula, CPL, BCPL, Snobol, PL/1, self ... ) À l'inverse, certains langages dont la disparition semblait inévitable ont perduré (notamment BASIC ou COBOL, les deux exemples les plus caractéristiques.) Et ce qui est vrai pour les langages, est vrai pour tout un tas d'autres éléments de l'informatique (les systèmes d'exploitation, les outils ... )

Il est donc dangereux de tenter de se former de manière trop spécifique sur des outils dont la durée de vie n'est pas garantie. Par contre, même s'il y a des changements en surface (syntaxe, environnement ... ) les concepts fondamentaux restent relativement vrai. C'est pourquoi une bonne formation à la programmation doit passer par l'apprentissage des fondamentaux et la dure école du kit de survie du programmeur (voir plus loin.)

Mais avant d'explorer les outils du programmeur, voici venues les traditionnelles maximes à l'usage des programmeurs.

Règles pour la programmation

De nombreux ouvrages de programmation appuient souvent leur propos par des règles ou des maximes comme GOTOs are evil ou Keep It Simple Stupid (l'un des points de départ de cette habitude est le livre de Brian W. Kernighan et P. J. Plauger 'The Elements of Programming Style' et qui s'inspire lui même d'un ouvrage sur la pratique de la langue anglaise 'The Elements of Style'.) Ce cours n'échappera pas à la règle, voici donc mes règles pour la programmation:

• Allez au plus simple;
• Le Copier/Coller est votre ennemis;
• Diviser pour mieux régner;
• La fin justifie les moyens;
• "Souvent" n'est pas assez pour une sauvegarde, presque assez pour une compilation et tout juste assez pour un test;

Bien évidement, ces remarques nécessitent un peu d'explications.

Allez au plus simple

L'un des grands classiques de la programmation, l'injonction est simple, mais on ne la répète pourtant jamais assez: programmer est déjà une activité intellectuellement suffisament intense, ne cherchez pas à rendre les choses plus compliquées, préférez la voie de la simplicité, les approches évidentes.

Une petite citation illustrant l'importance d'aller au plus simple:

"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." – Brian W. Kernighan and P. J. Plauger in The Elements of Programming Style

Le Copier/Coller est votre ennemi

Derrière le côté un peu commique de cette phrase se cache une mécanique importante de la programmation: la factorisation. Il n'existe pas de bonne raison pour que deux blocs de code, suffisamment similaires pour que vous utilisiez le Copier/Coller, ne soient pas factorisé d'une manière ou d'une autre.

Cette maxime a un corollaire:

Copier du code, c'est copier des bugs.

Lorsque vous recopiez un bloc de code, vous dispersez dans votre code des erreurs (existantes ou potentielles) et vous multipliez les points à contrôler lors des modifications. En factorisant, vous concentrez le travail de maintenance.

Diviser pour mieux régner

Un classique (de l'informatique comme de la stratégie ou de la politique), qui comme tous les classiques requiert quelques mises au point.

Diviser en informatique peut se comprendre de bien des façons (il existe notamment de nombreux algorithmes basés sur ce principe.) En terme de conception et de gestion de la conception d'un projet, on identifie en général deux axes de division: un axe horizontal (ou fonctionnel) qui divise le projet en parties indépendantes et un axe verticale (ou organisationnel) qui divise le déroulement du projet en activités.

Du point de vue du programmeur, la division complète la factorisation: on commence par diviser les activités, puis on cherche à identifier celle qui méritent factorisation (ce qui induit souvent une nouvelle division.)

Le point le plus important de cette règle est son application mesurée: la division implique un cloisonnement, or trop cloisonner augmente souvent la redondance et la complexité du code. Il faut donc ajuster l'usage de la division pour éviter de perdre le gain qu'elle apporte dans d'autres problèmes dûs à l'excès de cloisonnement.

La fin justifie les moyens

Comme pour la maxime précédante, il s'agit encore d'un classique adapté. Cette phrase a souvent une connotation négative, elle semble impliquer que le résultat justifie toute sorte de sacrifices (notamment, ceux impliquant les autres.)

Il faut ici la comprendre de manière pragmatique. L'important c'est le résultat final, pas la méthodologie employée, ni le respect de règles esthétiques, voir religieuses. Bien évidement, il faut correctement définir l'objectif (et donc le résultat à atteindre.)

Pour un programme classique, le résultat peut se résumer par les points suivants:

• Satisfaction du cahier des charges ou des attentes de l'utilisateur;
• Absence (ou presque) de bugs et autres disfonctionnement;
• Maintenance (corrections, modifications, ajouts de fonctionnalités) relativement aisées;
• Respect des contraintes (délais, chartes ... )

Par contre, on peut très bien imaginer que vous écrivez un bout de code pour automatiser une tâche ponctuelle, dans ce cas l'objectif est plus direct et il n'est pas nécessaire de satisfaire tous les points précédants.

En pratique. la satisfaction des objectifs initiaux est suffisament contraingnante pour que le code produit reste propre sans avoir à inventer des règles arbitraires. De même, il vaut mieux utiliser une petite astuce (un hack) qui marche, que de tenter de tout faire dans les règles de l'art sans résultat.

"Souvent" n'est pas assez pour une sauvegarde, presque assez pour une compilation et tout juste assez pour un test

Si vous avez eu l'occasion de travailler longtemps (une journée complète par exemple) sur un ordinateur, vous savez que les incidents sont courrants. Il pourrait sembler idiot d'institer sur ce point, mais sauver très souvent est un précepte qui protège de nombreuses mauvaises surprises.

De plus, l'expérience montre que (surtout en période d'apprentissage) l'une des erreurs qui fait perdre le plus de temps est le syndrome des modifs-qui-ne-font-rien: c'est ce qui se produit lorsque vous recompilez et testez une modification de code sans l'avoir sauvegardée. Parfois l'erreur (le fichier non sauvé) peut se cacher assez loin et vous pouvez passer beaucoup de temps dessus.

La recompilation suit la même logique: lorsque vous écrivez du code, même si vous êtes bon, vous ferez des fautes de frappes ou d'inattention, compiler souvent vous permet de détecter ces erreurs rapidement.

Il est également important de bien vérifier que votre chaîne de compilation (quelqu'elle soit) recompile bien tout votre code correctement. Là encore on risque de tomber sur le syndrome des modifs-qui-ne-font-rien et y perdre beaucoup de temps.

Enfin, je terminerai sur un autre aphorisme:

Un code non-testé et un code qu'il faudra réécrire.

kit de survie du programmeur

Ce que j'appelle le kit de survie du programmeur est l'ensemble minimal d'outils nécessaires à la programmation. Il peut être adapté à certains cas et certains pourront prétendre que l'on peut faire encore plus minimaliste (mais à cela je dirais de retourner utiliser leur panneau frontale et ses commutateurs pour remplir à la main la mémoire de leur ordinateur ... )

Le kit peut être perçu sur deux points de vues:

1. le point de vue général: la liste des types d'outils nécessaires
2. le point de vue du cours: la liste des outils que vous aurez à votre disposition cette année.

Les deux sections suivantes détaillent ces points de vue.

L'indispensable de la programmation

Les outils indispensables au programmeur sont les suivants:

Un compilateur

Le compilateur est l'outil essentiel, sans vous pouvez regarder vos programme dans les yeux imaginer ce qu'ils pourraient faire si vous les exécutiez, mais ça s'arrête là. Attention, sous le terme compilateur on regroupe en général un ensemble un peu plus vaste (interpréteur, éditeur de lien, assembleur ... )

Un éditeur de texte

Pour taper votre code, il vous faut un éditeur de texte. On attend de cette éditeur qu'il permette d'ouvrir ou de créer de nouveaux fichiers, de les modifier et de les sauver. Mais en général il vaut mieux que celui-ci soit pleine page (des amateurs de ed ?) et fournisse une forme de syntax highlighting ainsi que des outils d'édition évolués (recherche intelligente, presse-papiers ... )

Un gestionnaire de compilation

Les programmes que l'on écrits sont rarement limités à un seul fichier, il est donc nécessaire d'effectuer plusieurs appels au compilateur dans un ordre particulier. Quand le programme grossit cela devient fastidieux et infaisable à la main. Un bon gestionnaire de compilation est capable de gérer les dépendances entre unités de compilation, il est capable de ne recompiler que les éléments nécessaires et enfin il doit permettre d'effectuer quelques opérations annexes (copies, suppressions, déplacements de fichier ... )

Un gestionnaire de versions

La gestion de l'évolution d'un projet dans le temps est relativement important, il est donc souvent utile d'utiliser un gestionnaire de version qui permettra de conserver au moins un historique linéaire du projet, de synchroniser des répertoires de travail à différents endroits, d'obtenir un différentiel entre plusieurs versions d'un même fichiers ...

Un debuggeur

Enfin, pour partir à la chasse aux erreurs obscures et incompréhensible, un bon debuggeur symbolique est souvent bien pratique. Celui-ci doit vous permettre d'exécuter votre code pas à pas, d'observer le contenu de la mémoire ou des variables de votre programme, de placer des points d'arrêt ...

Ce que l'on va utiliser cette année

L'environnement de travail sera un système de la famille UNIX, en l'occurrence Linux (le PIE propose également quelques machines sous FreeBSD accessibles à distances), avec un environnement graphique minimal (entendez par là que vos fenêtre ne seront pas transparente et ne feront pas le tour de votre écran avant de disparaître, que vous n'aurez pas d'explorateur de fichiers mais un bon vieux shell dans un xterm ... )

Compilateurs

Pour la partie C nous utiliserons l'inévitable gcc. Pour la partie OCaml[1] nous utiliserons principalement le compilateur natif ocamlopt (bien que nous verrons aussi l'usage de l'interpréteur et du compilateur bytecode.)

Éditeurs

Je n'ai pas de directives particulières, la tradition de l'école est d'utiliser emacs, mais si vous avez d'autres préférences et que votre éditeur favori est installé ne vous gênez pas (par contre, je ne fournis pas d'aide sur ce point, vous assumez vos choix.)

Gestionnaire de compilation

Nous utiliserons le traditionnel make (nous verrons d'ailleurs un peu d'écriture de Makefile dans l'année.) Attention, j'attache de l'importance à ce que vous évitiez d'utiliser des fonctionnalités trop spécifique à une version particulière de make. Vous essaierez donc d'écrire des Makefile portable (à défaut compatible avec les deux versions majeures, BSD et GNU.)

Gestionnaire de versions

Le choix du gestionnaire de versions est à votre discrétion, les clients pour cvs, svn, ou git sont normalement installé. Par contre, il n'y a pas vraiment de mise en place de dépôt à l'école, à vous de vous débrouillez.

Debuggeur

Le choix est ici relativement restreint: gdb pour le C et ocamldebug pour l'OCaml ...

Styles, langages et paradigmes

L'apprentissage de la programmation passe forcément par la pratique, mais comme je l'ai dit plus haut, il est dangereux de se focaliser sur une (ou quelques) technologie(s) particulière(s). Seulement, faire le tour des langages de programmation est quasiment impossible (aller voir ces sites[2][3] pour avoir une idée du nombre de langage qui peuvent exister.)

Dans ces conditions quels langages choisir ? On ne peut pas se limiter aux langages à la mode (pour les raisons évoquées plus haut.) La solution usuelle (qui est plus ou moins la notre) est de choisir un panel des différents types de langages que l'on pourrait rencontrer.

Classer les langages de programmation

La question qui suit est assez évidente, comment établissons nous ce panel ? En règle générale, on va trier les langages en établissant des familles regroupant des langages aux caractéristiques similaires. Faisons donc un tour des différents axes permettant de classer les langages de programmation:

• Le type d'exécution: le langage est-il interprété (BASIC, OCaml, Python, Ruby, D ... ), compilé (C, C++, OCaml, D, Java, C# ... ), le compilateur produit il du code natif (C, C++, OCaml, D ... ) ou du code destiné à une machine virtuelle (Java, C#, OCaml ... ) ?
• Le modèle de sa sémantique: s'appuie-t-il sur une sémantique formelle bien fondée (OCaml, SML, Prolog, Haskell ... ) ou plutôt sur la description du code généré (C, C++, D ... ) ou encore correspond-il à un équilibre entre les deux mondes (Java, C#, Pascal ... )
• Son modèle de typage: la langage est-il typé ? si oui, dynamiquement (Lisp) ou statiquement (OCaml) ? S'agit-il d'un typage fort (OCaml, Java, C#, Haskell, Pascal ... ) ou d'un typage faible (C, C++, D ... )
• Son modèle d'exécution: le langage s'inscrit-il dans une logique procédurale (Pascal, C, C++ ... ) ou plutôt dans une logique fonctionnelle (OCaml, Haskell, SML, Lisp ... ) ? Dans une logique déclarative (Prolog, SQL ... ) ?
• Ses capacités de généricité: le langage est-il monomorphe (Pascal), monomorphe mais avec une certaine souplesse (C), polymorphe par typage (OCaml, SML, Haskell ... ), polymorphe par sous-typage (C++, Java, C# ... ) ? Dispose-t-il d'un modèle de réutilisation de code générique (template façon C++ ou D, foncteur d'OCaml, types generics objets comme dans Java ou C# ... ) ?

Comme on le voit dans les exemples cités, ces axes ne permettent pas toujours de faire émerger des classes claires de langage. Par contre, on voit assez bien où certains styles de programmation pourront s'appliquer le mieux. Malgré tout, nous n'avons pas vraiment avancé dans notre classification des langages de programmation. On voit assez clairement que de nombreux langages offrent par exemple des méthodes pour écrire du code relativement générique (OCaml ou C++ par exemple) mais que ces langages y parviennent par des voies différentes (typage polymorphe et foncteur pour OCaml, sous-typage, héritage et template pour C++.) Existe-il d'autre façon de classer les langages ?

Paradigmes de programmation

Les paradigmes de programmation sont une tentative de classer les langages dans des familles au contour relativement délimités qui en générale regroupent plusieurs caractéristique de styles déjà évoqués. Voyons les paradigmes usuels:

• Programmation impérative structurées: c'est le plus ancien paradigme, très proche du modèle sous-jacent (déroulement linéaire instruction par instruction, modification en place de la mémoire.) Les langages qui sont centrés autour de ce paradigme sont souvent considérés comme étant de bas niveau et n'offrant pas beaucoup d'abstraction. Ils sont par contre plus simple à apprendre et correspondent assez à la façon dont l'algorithmique et les bases de l'informatique ont été pensées.
• Programmation fonctionnelle: le deuxième paradigme de programmation (voir le premier si on tient compte de son modèle mathématique sous-jacent.) C'est un paradigme fortement lié au mathématique (notamment le $\lambda$ calcul) qui s'appuie sur la vision que tout est fonction et sur un monde sans effet de bord, c'est à dire un mode où l'on ne modifie rien mais où l'on crée systématiquement de nouvelles valeurs. Beaucoup plus abstraite que la programmation impérative, la programmation fonctionnelle a pendant longtemps souffert d'un modèle de compilation plus complexe à mettre en œuvre, bien que maintenant de nombreux langages modernes disposent de compilateur efficace (OCaml par exemple.)
• La programmation logique: dérivée d'une approche à la fois fonctionnelle et déclarative, la programmation logique (et sa compagne la programmation par contrainte) est sûrement le paradigme le plus abstrait. Incarné quasiment exclusivement par le langage Prolog et ses dérivés, la programmation logique permet une écriture très compacte d'algorithme relativement complexe. L'aspect déclaratif, par contre, implique une difficulté de l'écriture des compilateurs relativement élevée et encore aujourd'hui après presque 30 ans d'existence les compilateurs Prolog ne sont toujours pas complètement satisfaisant.
• La programmation orientée objet: à la croisée de différent monde (modélisation, typage, génie logicielle, simulation et concurrence) le paradigme objet est un des modèle le plus en vogue depuis la fin des années 70. Basée sur une notion d'encapsulation forte (dans la lignée des types abstraits de Dijkstra) et de réutilisation intelligente du code, la POO (programmation orientée objets) permet à la fois de maintenir un certain niveau d'abstraction tout en préservant éventuellement des aspects plus bas niveau.
• Les autres: aspects, composants, méta-prog, prototypes ... il existe d'autre pseudo-paradigme, qui sont en général des dérivés des modèles à objets dans lesquels des aspects particuliers de modélisation ont été érigés en règle stricte avec plus ou moins de réussite.

La découpage par paradigme semble déjà un peu plus clair. Certains paradigmes (comme la programmation logique) sont complètement détachés des autres approches. Certains autres sont plus transversal, comme la POO, en effet, dans le cas de l'objet, le modèle peut s'appuyer sur des langages à dominante impérative (C++, Java, C#, D ... ) ou fonctionnelle (OCaml, Erlang ... )

Même si ce découpage semble pertinent, il faut garder à l'esprit que tous ces langages de programmation s'appuie au final, d'un manière ou d'une autre, sur des processeurs au modèle bêtement procédurale. Il ne faut donc pas leur accorder trop d'importance non plus.

Les langages

Toute cette discussion a mis en avant la complexité de la classification des langages de programmation. Mais aussi le fait qu'il existe de nombreux point commun entre les langages les plus courant. Faisons maintenant un tour d'horizon des langages classiques avant de motiver les choix des deux langages étudiés cette année.

C

Considéré par beaucoup comme le langage de programmation par excellence.Impératif structuré, il offre pas mal de libertés au programmeur. Mais son caractère bas niveau et son absence de vérification statique fiable, en font un langage difficile à maîtriser. Historiquement C est le langage de la programmation système, puisque initialement il fut conçu dans le but d'écrire les premières versions d'UNIX.

C++

L'une des références majeures dans le monde de la POO. Il s'agit à l'origine d'une simple extension de syntaxe pour C (le nom original est C with classes). Il a maintenant évolué en un langage indépendant. Puissant (portant avec lui de nombreuse qualité du C) et fournissant des constructions très pratique aux programmeurs (template, surcharge d'opérateur ... ) en plus des éléments POO. Par contre, sa syntaxe un peu (beaucoup) lourde a souvent été critiquée, tandis que son lien fort avec le C rapporte certains aspects négatifs du C que l'on souhaiterait éviter dans un langage de haut niveau.

Java et C#

Les deux autres protagonistes forts de la POO. Le Java (C# est à l'origine un dérivé de Java) fut conçu dans l'objectif de mettre en œuvre (entre autre) les aspects forts de la programmation objet. Il en résulte un langage (enfin 2) que l'on pourrait qualifier de pure objet. C'est langage ont également bénéficié des avancées dans le domaine de la théorie des types et sur les modèles modernes de compilation. Une de leur qualité majeure (mais qui est aussi parfois perçu comme un défaut) est l'utilisation d'une machine virtuelle comme cible d'exécution. La critique principale que l'on fait à Java (et un peu aussi à C#) tient au caractère un peu trop stricte de sa vision objet qui est parfois perçu comme une contrainte trop forte au vue du gain en terme d'expressivité.

OCaml et la famille ML

Les langages de la famille ML (OCaml, SML et leurs dérivés) sont un peu l'antithèse du C et du C++. Construit sur un modèle théorique et mathématique fort ($\lambda$ calcul et inférence de type polymorphe) ils ont un peu parcouru le chemin inverse des langages d'origine plus pratique. Aujourd'hui, un langage comme OCaml possède un modèle de compilation aussi efficace que C, tout en offrant une approche beaucoup plus abstraite et éloignée de la machine. Mais contrairement aux puriste du monde fonctionnel (Haskell, Lisp, Scheme ... ) OCaml intègre des fonctionnalités impératives (boucles, références, valeurs mutable) et même objet. Le défaut majeure des langages de la famille ML (si on met de côté les choix syntaxiques) tient dans leur qualité de langage de recherche. En effet, il manque de continuité (changement de syntaxe, incompatibilités binaires) et d'une maintenance plus orientée utilisation qu'expérimentation.

Ada et Pascal

Ces deux langages sont le fleuron de la théorie des langages ... d'il y a 40 ans ! Ils représentent à eux deux la raison pour laquelle les langages de bases théoriques ont souvent été considérés comme peu intéressants. Les deux langages sont particulièrement strictes et assez lourd à utiliser. Par certains côtés, Ada est quand même un langage très intéressant puisqu'il intègre des aspects fonctionnels, objets, de la validation statique très poussée (c'est un des seuls langage à intégrer de mécanisme de validation de borne de valeur ou de vérification des unités dans le calcul scientifique), des outils fiables pour la programmation concurrente ... Mais cette qualité à son revers: le langage est une véritable usine à gaz dans son design, sa syntaxe est lourde et complexe et les contraintes liées à ses aspects sécurités sont particulièrement fatigante pour le programmeur. De son côté Pascal a moins d'excuse de ce genre si ce n'est son âge et son objectif initial (l'apprentissage forcé de la programmation structurée.) La vocation militaire d'Ada en fait tout de même un outil de choix pour la programmation à très hautes fiabilités comme dans le pilotage de fusées ou le guidage de missiles.

Python, Ruby et leurs amis

Nouveaux venus dans le paysage de la programmation, ces langages tentent (avec plus ou moins de succès) d'allier les aspects les plus modernes de la programmation (POO, ordre supérieurs ... ) et le côté facile des langages de script. Le choix d'un modèle interprété les limites tout de même à une utilisation un peu gadget.

Les langages étudiés en spé

Comme je l'ai dit en introduction à ce cours, les langages étudiés en spé sont C et OCaml. Voici un rapide tour de ce que nous verrons et des motivations de notre choix.

C

Ce langage est probablement un passage obligatoire pour tous les programmeurs actuels. Il permet de voir les aspects durs de la programmation (gestion de la mémoire, encodage concret de l'information, aspects systèmes ... ) et est probablement le meilleur pont entre l'ancien monde (les vieux langages procéduraux et un peu rébarbatifs) et le nouveau (notamment le C fournit une bonne base pour l'apprentissage de langage objet tel que C++ ou Java.)

La partie C s'articule sur deux aspects:

• écriture concrète d'algorithmes en C
• programmation système

Le premier point vient en complément des cours et TD d'algorithmique tandis que le second est une introduction à la programmation UNIX, notamment telle que vous la verrez en ing1. En vrac nous aborderons les points suivants (liste non exhaustive et sujettes à modifications):

• Structures de donnée linéaires chaînées (pointeurs et listes)
• Arbres et graphes
• Manipulation externe de la mémoire (malloc(3), tableaux dynamiques, pointeurs ...)
• Manipulation interne de la mémoire (gestion du tas, algorithme simple pour l'écriture d'une fonction de type malloc(3) ... )
• Gestions des processus (fork(2), exec*(3) ... )
• Manipulation des file descriptors (redirections, tubes ... )
• Threads et synchronisation (mutex, condition, sémaphores ... )

OCaml

Moins évident que le choix de C, OCaml reste également un incontournable pour tous ceux qui veulent ouvrir leur esprit à d'autre forme de programmation. Les aspects typages forts complétés par l'inférence et le polymorphisme permettent de prendre des bonnes habitudes qui ne nuisent pas à l'écriture de programme plus génériques. Enfin, la méthodologie fonctionnelle (récursivité, partage de valeurs ... ) permet d'appréhender une autre façon de voir l'algorithmique.

L'apprentissage d'OCaml comblera la partie vu en sup pour les bases et s'étendra sur des notions plus avancées:

• Principes de l'approche fonctionnelle
• Programmation fonctionnelle et impérative dans OCaml
• Modules et foncteurs
• Manipulation d'arbre et en particulier d'arbres de syntaxe abstraite (AST.)
• POO en OCaml
• Interfacage avec le langage C

Organisation et bonne pratique de la programmation

Ce cours n'a pas pour but de vous enseigner les différentes méthodes de gestion de projet, de conception ou de modélisation. Pourtant, on ne peut parler de programmation sans évoquer ces différents aspects. Dans cette section, nous nous attacherons à donner des conseils généraux sur la manière de conduire un projet.

D'une idée à un programme

Le point de départ de tout projet est en général, un concept ou idée un peu flou. Au delà de la programmation, une bonne partie du travail de conception est de faire la mise au point. Il va falloir travailler à partir d'éléments vagues et informels, leur donner une forme exploitable, cibler les besoins réels (et les souhaits) de l'utilisateur final, affiner ces concepts pour pouvoir les décrire et les programmer.

Voici le scénario classique pour première phase d'analyse:

1. Identifier les besoins et les souhaits de l'utilisateur, établir un cahier des charges clair qui décrit ce que veut et ne veut pas l'utilisateur final.
2. Écrire des scénarios d'utilisation (avec l'utilisateur final si possible) simple mais complet.
3. Identifier les données externes (entrées et résultats) que va devoir manipuler le programme. Éventuellement réfléchir au format d'échange s'il y a lieu.
4. Établir si possible, la nature des opérations à effectuer sur les données d'origine.
5. Identifier les données internes et si possible les décrire abstraitement.
6. Établir une spécification claire du programme.
7. Découper et Affiner

Ce processus va se répéter récursivement (mise à part la première étape), jusqu'à être en mesure d'écrire le programme. À chaque fois, à la fin, on obtient une vision claire du niveau actuel, on découpe, à partir de cette vision, la partie qui nous intéresse actuellement on petits éléments sur lequel on va recommencer les étapes précédentes.

Attention, il ne s'agit pas de s'étaler dans une analyse laborieuse qui découpe le projet jusqu'aux instructions à écrire. Le but est de faire émerger une structure cohérente qui réalise un certain équilibre entre généricité (d'où les spécifications abstraites) et spécialisation.

Modularité et abstraction

L'objectif de cette phase initiale d'analyse, au delà de l'apport structurel, est avant tout de faire émerger les données au travers de leur usage, plus qu'au travers de leur contenu.

Prenons un exemple concret: la partie du programme sur laquelle vous travaillez actuellement nécessite la réalisation d'un algorithme de plus court chemin. Suivant, les conditions, votre choix se portera relativement logiquement vers l'algorithme de Dijkstra (ou sa variante A*.) Ces deux algorithmes utilisent un ensemble ordonné pour stocker (et retrouver) les sommets à traiter. Même s'il est évident qu'un tas binaire sera probablement la meilleur implantation, vous spécifierez ces ensembles le plus simplement possible. Pourquoi ?

Parce que vous ne devez pas figer vos choix algorithmique, trop tôt. Les raisons sont multiples. On reviendra sur l'optimisation dans la partie suivante, pour se focaliser ici sur les problématiques de fiabilité et de tests.

Si nous reprenons notre exemple, quels sont les opérations nécessaires:

• Création d'un nouvel ensemble
• Test du vide
• Ajout d'un élément
• Mise à jour d'un élément
• Récupération de l'élément minimum

À partir de cet ensemble d'opérations, nous pouvons rédiger une spécification détaillée de la structure de données: nom, type et contraintes (pré-conditions, invariants ... ) de chaque opération. Notre algorithme de plus court chemin pourra être écrit en suivant cette spécification, alors que celle-ci n'est peut être pas encore implantée.

Cette approche va nous permettre de mettre en place la partie importante de notre travail (dans notre exemple l'algorithme de plus court chemin) indépendamment des éléments secondaires (notre structure d'ensemble.) On peut même tester notre algorithme de plus court chemin avec une implantation simple (et facilement vérifiable) de la structure décrite par la spécification. Le bénéfice est multiple: l'objectif principal est atteint plus vite (ce qui permet par exemple de faire des présentations au client pour affiner le cahier des charges) et validé, sans pour autant fermer la porte à des améliorations ultérieures des éléments secondaires (on pourra ainsi implanter plusieurs variantes d'ensemble, du moment que la spécification est respectée.)

Pour résumer, dans notre exemple, la stratégie de développement est la suivante:

1. Choix de l'algorithme (Dijkstra ou A* ... )
2. Rédaction des spécifications des structures de données annexes (ensemble ordonné pour les sommets ouverts, ensemble pour les sommets fermés ... )
3. Implantation de l'algorithme
4. Implantation rapide des structures annexes (avec validation)
5. Validation de l'algorithme
6. Amélioration des structures annexes.

L'abstraction des structures annexes présentent un autre avantage: lorsque l'on met en avant les aspects externes d'une structure de données, on verra probablement plus facilement les points commun avec d'autres structures utilisées dans l'application ou avec des collections fournies par la bibliothèque du langage, permettant ainsi de factoriser le travail et d'éviter de recréer plusieurs fois des éléments similaires.

Détaillons un peu notre exemple: dans une implantation en C, nous utiliserions la spécification suivante pour les ensembles ordonnés:

/* ordset.h: Ordered Set Headers */
 
/*
 * Sets' elements are pairs of integer and float. The float element of
 * each pair serves as ordering key, while the integer is the stored
 * value. The integer value is meant to be unique.
 */
 
#ifndef _ORDSET_H
#define _ORDSET_H
 
/*
 * the type definition: the structure s_oset is opaque
 * and defined in the implementation
 */
typedef struct s_oset *t_ordset;
 
/* init a new set */
t_ordset        new_oset        ();
 
/* Emptyness test*/
int	        oset_is_empty   (t_ordset s);
 
/* Member test: true if (val,key) is in s */
int             oset_mem        (t_ordset s, int val);
 
/* Adding the pair (val,key) to the set */
void		oset_add        (t_ordset s, int val, float key);
 
/* Replace (val,key) with (val,nkey), adding it if needed */
void	        oset_update     (t_ordset s, int val, float nkey);
 
/* get min: return val where the pair (val,key) is in s and key is the
   minimal key. Store key in *k if k is not NULL. (val,key) is removed
   from s. */
int	        oset_getmin     (t_ordset s, float *k);
 
#endif

On ajoutera probablement au moins une contrainte sur oset_getmin pour s'assurer que l'ensemble en paramètre est non vide et une autre sur oset_add pour ne pas ajouter deux fois la même valeur:

/*
 * - Result and behavior of oset_getmin(s,k) is defined if and only if
 *   oset_is_empty(s) == 0.
 * - Behavior of oset_add(k,val,key) is defined if and only if
 *   oset_mem(s,val) == 0.
 */

On peut maintenant implanter un algorithme de plus court chemin. Voici par exemple une implantation de l'algorithme de Dijkstra sur des graphes dans une représentation chaînée (tableau de sommets et listes d'adjacence) assez classique.

/*
 * Quick and dirty Dijkstra shortest path algo.
 * Build a spanning tree, rooted in src, where all path starting from
 * src to any node are minimal.
 */
void dijkstra(t_graphe g, int src, int path[])
{
  t_ordset      open;
  float	       *dist, d;
  int		i;
  t_listsom	ps;
  t_listadj	pa;
 
  dist = malloc(g->ordre * sizeof (float));
  for (i=0; i<g->ordre; i++)
    {
      path[i] = 0;
      dist[i] = INFTY;
    }
 
  path[src] = src;
  dist[src] = 0;
 
  open = new_oset();
  oset_add(open, src, 0);
 
  do
    {
      ps = g->som[get_min(open,&d)];
      for (pa = ps->succ; pa; pa = pa->suiv)
	{
	  if (dist[pa->som] > d + pa->cout)
	    {
	      dist[pa->som] = d + pa->cout;
	      path[pa->som] = ps->som;
	      oset_update(open, pa->som, d + pa->cout);
	    }
	}
    }
  while (!oset_is_empty(open));
}

On peut maintenant valider cette implantation de l'algorithme avec n'importe quelle implantation du type t_ordset. On peut même pousser la modularité plus loin: si le graphe n'est pas vraiment valué (tous les coûts sont égaux) on peut implanter une simple file à la place de nos ensembles (et dans ce cas oser_getmin renvoie le plus ancien élément de la file) et on obtient un classique parcours en largeur (qui donne le même résultat que Dijkstra dans ce cas là, le coût de la recherche du minimum en moins.)

Optimisation

L'optimisation est un point important, qu'il convient de ne pas négliger. Mais il faut faire attention, de nombreuses erreurs sont commises au nom de l'optimisation et la perception que l'on a de cette activité est souvent fausse. On commencera par l'éternelle citation de Donald Knuth:

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."

Cette phrase est un très bon résumé des problèmes de l'optimisation dans la programmation. On y retrouve deux des points importants: l'inutilité de l'optimisation des détails et le danger de la poursuite de l'optimisation trop tôt.

Motivations et pertinence

L'optimisation des programmes est une quête dans laquelle beaucoup de programmeurs se perdent. Il est important de comprendre pourquoi, quand et quoi optimiser, plutôt que de se lancer dans des bricolages improductifs qui final n'apporteront rien peut être aucun gain de performance notable.

Bien évidement, ça ne veut pas dire qu'il ne faut pas optimiser. La performance d'un programme est un point crucial dans bien des cas, et, au pire, un argument non négligeable lorsqu'il s'agit de se détacher de la concurrence.

Il est important d'annalyser les points suivants pour bien aborder le problème:

• Nécessité: quels sont les besoins réels en terme de performance ?
• Gain: le gain en performance est-il vraiment mesurable ?
• Pertinence: si le gain en performance sur une partie spécifique de l'application est non négligeable, cela a-t-il un impact réel sur l'ensemble ?
• Rendement: le gain en performance vaut-il l'effort fournit pour la réalisation de l'optimisation ?
• Effets indésirables: quels sont les conséquences des modifications effectuées ?

Ces questions sont primordiales, elles évitent des efforts inutiles et recentrent le travail sur les points réellement importants. Revenons sur chaqu'un de ces points:

Nécessité

Que ce soit en terme d'attente des utilisateurs (ou du client) ou en terme de contraintes externes, vos programmes doivent répondent à des besoins de performances. Il est important de mettre en avant les parties nécessitant une attention particulière, afin de bien définir les priorité dans ce domaine.

Gain

Lorsque l'on commence à penser à une amélioration pouvant augmenter les performances, il faut mesurer le gain réel de cette amélioration. Beaucoup d'amélioration n'ont que peu d'impact au final. Nous verrons certains critères qui permettent de réfléchir un peu mieux sur ces questions pour pouvoir estimer le gain d'une optimisation sans réellement implanter celle-ci.

Pertinence

Une fois l'évaluation du gain potentiel effectuer, la suite logique du raisonnement et la pertinence de l'amélioration au sein de l'ensemble de l'application. Il faut mettre dans la balance le gain et l'usage de ce gain: si vous pouvez gagner 50% sur une partie du programme qui occupe moins de 5% du temps global d'exécution, cela reste moins intéressant que de gagner 10% sur une partie occupant 50% du temps d'exécution.

Rendement

L'une des erreurs classiques lorsque l'on tente d'optimiser un programme est de se lancer dans des améliorations complexes qui impliquent de nombreuses modifications, sans pour autant apporter un gain significatif. Le point important ici est de mesurer l'impact sur le code de votre amélioration: que devez vous modifier, quelles modifications impliqueront une nouvelle série de tests de validation, quel est la quantité de code à écrire/réécrire ... Vous appliquerez ici le même genre de raisonnement que pour la répartition des tâches de développement classique: chaque optimisation se verra attribuer un temps de réalisation (comprennant l'optimisation elle même, mais aussi les tests et les modifications impliqués dans l'ensemble du projet) proportionnel au gain final apporté.

Effets indésirables

Modifier du code existant a souvent des effets secondaires sur l'ensemble du programme. Il est important de mettre dans la balance ces effets face au gain de l'optimisation. Ces effets de bord peuvent aller à la nécessité de refaire toute la phase de validation du projet, jusqu'à des modifications dans le comportement ou la qualité des résultats du programme.

Stratégie et optimisation

Même si chaque programme, chaque problème est différent, il existe quelques "règles" pour orienter le travail d'optimisation. Ces règles, ou stratégies, permettent de faire des choix plus pertinents sur les points à explorer en priorité. Ils sont basés d'une certaine manière sur une expérience partagée, et donc par nature peuvent être amenés à évoluer suivant votre propre expérience.

1. Les gains de performances les plus importants (et de loin) sont le résultat d'amélioration au niveau algorithmique ou architectural. Ce qui veut dire, en clair, que la première chose à améliorer dans un programme sont ses algos et son architecture (enchainement des tâches, flux d'exécution et d'information ... )
2. Optimiser les détails doit être le dernier point à mettre en œuvre. Le gain des optimisations bas niveau (remplacement d'opération, déroulage de boucle ... ) est en général très faible. Par contre, ces optimisations ont souvent un grand impact sur la modularité et la lisibilité du code. Il s'agit donc de n'effectuer ce genre d'améliorations que lorsqu'il n'y aura plus d'autre opération sur le code. Sachant que le gain est souvent inintéressant, on essaie d'éviter de perdre son temps avec.
3. Une bonne annalyse des besoins et des usages réels des futurs utlisateurs peut conduire à d'important gain de performance au niveau architectural. Il n'est pas rare de constater dans une application qu'une opération peu utile est intégrée dans une chaîne de traitements sans pouvoir la contourner, dans ce genre de cas, il serait pertinant de sortir l'opération de la chaîne pour la rendre optionnelle.
4. Augmenter la modularité et la lisibilité du code ne nuit jamais aux performances, bien au contraire. Une plus grande modularité et une meilleure organisation permettent souvent de mettre en œuvre des optimisations architecturales et algorithmiques. De plus, contrairement aux idées reçues, un code lisible et modulaire n'est pas forcément plus lent qu'un code compacte, monolithique et figé.
5. Le compilateur est souvent meilleur qu'un humain sur les optimisations de bas niveau. En règle générale, il est plus opportun de laisser le compilateur se débrouiller et d'écrire du code abstrait, afin de lui laisser une plus grande marge de manœuvre dans ses optimisations.

De ces règles, on peut déduire une stratégie de travail en ce qui concerne l'optimisation:

• L'optimisation concrète (points techniques, interractions à bas niveau ... ) doit être une tâche séparée qui n'interviendra qu'une fois la réalisation finie.
• Pour maximiser les possibilités d'amélioration et d'optimisation, la conception et l'annalyse doit maintenir un niveau important d'abstraction et de modularité: découpage par activités, description des données par usage (types abstraits, classes ... ), mise en place de scénarios et d'annalyses sur le déroulement des traitements.
• Toutes les structures de données de l'application doivent être spécifiées et séparées des traitements, même lorsque ces structures sont limitées à une tâche en particulier. Vous devez vous laissez la possibilité de changer d'implantation pour chaqu'une de vos structures. La méthode la plus fiable est de rédiger une spécification détaillée (type abstrait, interface, classe ... ) basé sut l'usage des données et de n'utiliser que cette spécification.
• La réalisation doit avoir comme objectif premier le fonctionnement: votre programme doit remplir ses objectifs fonctionnels avant d'essayer d'être performant. Si vous maintenez un bon niveau d'abstraction, vous pourrez aisément améliorer chaque bloc indépendement sans régression.
• Une optimisation n'est pertinente que si:
  • les performances en l'état ne sont pas satisfaisantes;
  • le gain global est humainement mesurable;
  • l'effort de réalisation est proportionnel au gain global;
  • les effets de bords (code cassé, validation à refaire, régression, perte de précision ... ) sont soit acceptables, soit peuvent être corriger avec un effort proportionnel au gain;
  • L'optimisation ne casse pas la modularité ou les possibilités d'évolution du programme.
• Sauf dans certains cas très particuliers, vous devez absolument éviter les techniques d'optimisation bas niveau (déroulage de boucles, entrelacement de code, suppression des fonctions ... ) Le compilateur est souvent capable de le faire pour vous et le fait probablement mieux.
• Si vous êtes amené à faire des optimisations bas niveau, vous devez, dans la mesure du possible, éviter les constructions qui figent le comportement du compilateur (directive sur l'utilisation des registres, inlining, allocation manuelle bas niveau ... )
• Éviter les optimisations hardware: si vous voulez vraiment profiter de spécificités matérielles, faîtes de l'assembleur ou payez vous le compilateur du constructeur !

Conclusion

La programmation est un vaste sujet. L'objectif de ce cours est d'ouvrir votre esprit aux concepts clefs et de vous donner les points de départs principaux qui vous permettront d'appréhender correctement l'apprentissage de ce domaine pillier de l'informatique.

Ce premier cours dresse un horizon des notions non techniques qu'il vous faudra acquérir cette année (et dans les année à venir.) La suite du cours sera beaucoup plus technique et s'appuiera sur la compréhension des concepts énnoncés ici.