Available nodes

Cette page donne quelques recommandations quant aux attentes des encadrants de l'école par rapport aux projets, qu'il s'agisse des séances d'encadrement, des rapports ou des soutenances finales. Il ne faut pas la considérer comme une liste de recettes à appliquer, mais comme un ensemble de grandes lignes à suivre dans la démarche adoptée durant le projet.
Avertissement : ces conseils sont volontairement écrits de manière vague et abstraite. C'est au lecteur d'adapter la démarche à son problème, et pas le contraire.
La dernière section donne quelques exemples de choses à faire et à ne pas faire.

 La démarche scientifique

L'aspect primordial à établir consiste à faire preuve d'une démarche scientifique. Une telle démarche part du principe que pour répondre à une question ou résoudre un problème, il faut émettre des hypothèses et les soumettre à l'expérience, quitte à les modifier en fonction des résultats obtenus. Aucune allégation, aucun choix ne doit se faire de manière gratuite. Aucune conclusion ne doit être tirée sans se demander dans quelle mesure elle répond à la question initiale.

Pourquoi mettre en place une telle démarche ? Parce qu'elle demande à chaque étape de décrire ses choix, de les expliquer et de les remettre en cause. Comme pour une preuve scientifique, une telle attitude renforce considérablement la confiance que l'on peut placer dans le projet. A l'opposé, toute série d'affirmations gratuites rend le travail produit suspect.

Cette allégorie s'adapte naturellement à de nombreux contextes (surtout scientifiques), parmi lesquels on trouve le développement logiciel. Ainsi, face à un problème à résoudre, elle propose d'agir systématiquement de la manière suivante

  • Définir le problème précisément, ce qui en pratique demande de poser les définitions des objets considérés, d'évaluer l'existant et de le comparer au problème posé, et autant que possible de le décomposer en sous-problèmes indépendants, auxquels on appliquera la même méthode. En développement logiciel, on parlera d'analyse des besoins, fonctionnels ou non fonctionnels.
  • Établir des hypothèses, ce qui dans un projet de développement logiciel consiste à construire un ou plusieurs modèles abstraits censés répondre au problème, puis à planifier leur résolution. Comme les hypothèses, ces modèles sont faits pour être remis en cause au fur et à mesure de l'avancement du projet, mais ces remises en cause doivent absolument être justifiées par l'expérience ou le raisonnement.
  • Mettre en place un protocole de validation, qu'il s'agisse d'expériences, d'observations, ou de tests. Ce protocole peut être défini au tout début du projet, comme il peut évoluer au fur et à mesure de son avancement. Il sert de mètre-étalon pour vérifier si les résultats finaux permettent de valider les choix initiaux.
  • Justifier les résultats, c'est-à-dire comparer les besoins initiaux suivant le protocole de validation, et critiquer (au sens d'analyser objectivement) la pertinence desdits résultats. Cerner les limites du travail réalisé, et éventuellement proposer des pistes pour ses évolutions futures.
Et le code ? Une personne sagace se rendra compte que la démarche ne donne pas directement de place au fait même de réaliser le projet, en particulier le code même. C'est une illusion. Le code est une partie intrinsèque du projet. Lui aussi doit être analysé, justifié (par ses qualités), et potentiellement remis en cause (comme dans le cas de bug logiciel).

 Exemples et contre-exemples

Les points suivants donnent quelques idées permettant de mettre en place la démarche évoquée ci-dessus en utilisant les outils fournis dans la formation.
  • Systématiquement se référer à ses cours, les méthodes qu'ils décrivent sont toutes candidates pour décrire précisément votre démarche;
  • Les cours d'algorithmique proposent une démarche pour définir des objets algorithmiques, écrire, analyser et comparer les algorithmes, ainsi que des outils précis comme l'analyse de complexité;
  • Les cours de programmation proposent une démarche pour l'écriture de code (comme les conventions de codage), le développement logiciel en général (à travers des notions comme la modularité, la généricité ...), et en particulier test logiciel pour les cours plus avancés;
  • Toute réalisation admet un certain nombre de limites (pour une certaine valeur de "toute"), aucun projet ne peut se terminer sans évaluation critique;
  • Toute illustration d'une question par un exemple ou un dessin peut permettre de clarifier le propos.
  • Toute affirmation gratuite, tout dessin ou tout morceau de code non analysé, n'ont aucune valeur scientifique.
  • Toute expérience non reproductible n'est pas une expérience acceptable. Par corollaire, tout code qui ne fournit pas de méthode de compilation et d'exécution claire et stable est inutile.

 Thèmes d'algorithmique et programmation

Les projets du premier semestre mettent en valeur un ensemble de concepts liés à la programmation et l'algorithmique. Lors des soutenances, l'important n'est pas de mettre au premier plan le sujet ou le travail réalisé, et de préférer valoriser les leçons que l'on peut retenir de ce travail. Plusieurs thèmes de réflexion sont possibles:
  • le découpage du code en fichiers, la chaîne de compilation et d'exécution, le principe de la compilation séparée, la notion de dépendances lorsqu'on compile le code, et comment éviter de recompiler les fichiers non modifiés (PG101, IF104, make),
  • la présentation et l'analyse d'un algorithme, le calcul de sa complexité (en temps et en espace), l'évaluation de variantes plus ou moins efficaces (IF101, IF102, IF107),
  • le découpage du code en plusieurs unités de code différentes, les dépendances entre ces unités, le graphe d'architecture engendré, le choix du découpage (PG101),
  • l'écriture d'un type de données (abstrait ou pas), les opérations qui lui sont associées, leurs complexités, la facilité de réutilisation de ce type de données (PG101, IF101, IF102, IF107),
  • les tests, leur écriture, leur utilisation pour développer, comment synthétiser leurs résultats, la méthodologie utilisée pour s'assurer qu'ils couvrent une partie raisonnable du code et de ses fonctionnalités (PG101),
  • l'analyse d'un bug, à travers la description du problème, les effets constatés, l'explication de la solution, et la stratégie pour sa résolution (PG101, IF104, printf, gdb, valgrind),
  • les contraintes liées à l'utilisation de la mémoire, les pointeurs, les tailles d'objets, les stratégies pour allouer de la mémoire (statique vs dynamique), les avantages et les limites de ces stratégies (PG101, difficile).
Exemple de traitement d'un thème (hors-liste) : l'utilisation d'un type abstrait dans le code
Introduction : le C autorise de déclarer des types structurés (struct) de manière concrète (la définition est publique et explicite) ou de manière abstraite (la définition est masquée, seul le nom est disponible). Selon le choix qui est fait, les utilisations qui peuvent être faite des types en question sont très différentes:
• Exemple type de donnés concret: struct token_t
struct token_t {
  unsigned int c[NUM_COLORS];
};

struct token_t create_simple_token(enum color_t c);
int token_equals(const struct token_t t1, const struct token_t t2);
Le type struct token_t est ici une simple structure contenant un tableau de 5 entiers, définie dans le fichier token.h. Cette structure est complètement connue. En particulier dans tout fichier incluant token.h, le compilateur peut calculer la taille de la structure. Aussi, les fonctions associées manipulent le type directement, en le passant en paramètre et en le retournant.
• Exemple type de donnés abstrait: struct builder_t
struct builder_t;



struct builder_t* make_builder(unsigned int index);
unsigned int builder_level(const struct builder_t* g);
Le type struct builder_t est une structure définie dans le fichier builder.h, et son contenu n'est pas connu. Ce contenu est censé être défini ailleurs, dans notre cas dans le fichier builder.c. Si un fichier inclut builder.h, le compilateur ne connaît pas la taille de la structure, et il ne peut la manipuler qu'à travers des pointeurs (dont il connaît la taille). C'est aussi le cas des fonctions manipulant le type.
Discussion : lorsque le type est concret, il est forcément public. C'est avantageux, parce que tout le reste du code peut en créer des instances, les copier et les modifier à l'envi (insérer ici un exemple d'utilisation dans les marchés). Par contre, modifier ce type (par exemple en renommant un champ) oblige à modifier toutes les utilisations de ce type associées à ce champ. Cela rend l'architecture moins flexible.

Lorsque le type est abstrait, il devient possible de séparer le code en deux parties : la partie connaissant effectivement le type, et la partie ne le connaissant pas. C'est ce que l'on fait dans ce projet avec le fichier builder.c. Ce fichier représente la partie interne/privée du type données. Le reste du code n'a accès qu'à la partie publique du type correspondant au fichier builder.h.

Une telle séparation est plus difficile à mettre en place, parce qu'elle force à séparer public et privé. Dans nos exemples, il était impossible de créer des struct builder_t à l'extérieur de builder.c (insérer ici un exemple d'utilisation des guildes). Néanmoins, cette séparation laisse plus de flexibilité, dans la mesure où il devient plus facile de modifier la partie interne sans casser la partie publique. Dans le projet, on a pu remplacer builder.c par une autre implémentation sans perdre de fonctionnalité.

 Thèmes de développement logiciel

Les projets du second semestre mettent en valeur deux grands styles de programmation : la programmation impérative d'une part et la programmation fonctionnelle d'autre part. Lors des soutenances, il est essentiel de prendre le temps de comparer les façons de travailler ces deux styles. Plusieurs thèmes de réflexion sont possibles:
  • les types abstraits de données / interfaces, comment ils sont créés et utilisés dans le code pour spécifier les interactions entre les composants, profiter de l'abstraction et permettre des implémentations multiples (PG116, PG104),
  • l'utilisation de fonctions de 1ère classe et la généricité, comment elles permettent d'augmenter la réutilisation et la flexibilité du code (PG104, PG116),
  • la comparaison programmation pure / impure, comment des styles différents permettent d'obtenir des codes aux qualités différentes, par exemple à travers l'indépendance des composants (PG104),
  • l'architecture, le découpage du code et la modularité, comment un découpage efficace permet de simplifier l'écriture de code à plusieurs, et comment le cloisonnement des composants permet de les rendre indépendants (et donc potentiellement interchangeables, réutilisables, extensibles) (PG104),
  • les tests, pas comme une liste, mais comme un moyen d'aider à la vérification du code et à assurer la non-régression, en couvrant au maximum les fonctionnalités présentes dans le code, tout en prenant un temps de développement non négligeable (PG104, PG106, PG116),
  • les différences entre les aspects statiques (compilation avec gcc, tsc) et dynamiques (exécution avec node, mais aussi les aspects dynamiques du C comme l'utilisation de dlopen), ce qu'il est envisageable de vérifier dans le premier cas, mais aussi ce qu'il est possible de faire dans le second cas si on abaisse les contraintes par exemple des types (PG104, PG106, P116),
  • l'environnement de développement / la gestion des dépendances externes, qu'est-ce qu'ils permettent de faire, comment ils facilitent le développement (automatisation des tâches, installation des dépendances) et comment ils deviennent potentiellement complexes (multiplicité des dépendances, gestion des versions, édition des liens entre les composants) (PG106),
Exemple de traitement d'un thème (hors-liste) : l'utilisation de la récursivité dans les algorithmes
Introduction : la récursivité est une technique particulière pour écrire des algorithmes, typiquement en étant proche d'une description formelle / mathématique des objets manipulés (ex. : les listes, vues en cours). Elle a tendance à être utilisée en programmation fonctionnelle parce qu'elle se marie bien avec la programation pure.
• Exemple de structure de donnée récursive (projet Robot): une pile
type Stack<T> = { top: T, sub: Stack<T> }
function push<T>(s : Stack<T>, e : T) : void
function pop<T>(s : Stack<T>) : T
function top<T>(s : Stack<T>) : T
function forEach<T>(s : Stack<T>, f : (t: T) => void) : void
Une pile peut naturellement être représentée de manière récursive : soit elle est vide, soit elle est constituée d'un haut de pile et d'une autre pile contenant les éléments subséquents. Les algorithmes peuvent profiter de cette structure en étant récursifs et purs. Tous les cas d'erreur possibles sont connus (i.e principalement ceux où on cherche à accéder aux éléments dans une pile vide). On peut facilement profiter de la pureté en transmettant l'adresse de la pile dans le code, tout en sachant que ce que l'adresse représente n'est pas modifié. On peut aussi profiter de la persistance pour potentiellement préserver les calculs précédents et donc, par exemple, garder un historique des calculs.
• Le cadre impératif (projet Flood) peut aussi être propice à la récursivité, même si elle n'y est pas particulièrement favorisée. Un exemple d'algorithme récursif est celui de calcul de composante connexe dans un graphe. Contrairement à l'exemple ci-contre, un graphe n'a pas une structure récursive naturelle. Néanmoins, le calcul de composante connexe peut lui se faire par un algorithme récursif:
vertex_list get_connected_comp(vertex_list visited, vertex_list to_visit) {
  if (to_visit is empty)
    return visited;
  else
    vertex v = be the first vertex in to_visit;
    if (v is already in visited)
      return get_connected_comp(visited, to_visit - v);
    else
      vertex_list vnbrs = the neighbors of v;
      return get_connected_comp(visited + v, to_visit - v + vnbrs);
}
Le style décrit clairement les entrées du calcul (les sommets restant à visiter et les sommets déjà visités) et l'action à entreprendre pour continuer le calcul. Comme pour la pile, les cas à gérer sont connus et apparaissent dans l'algorithme. Il n'y a pas d'état intermédiaire comme dans un algorithme impératif, les paramètres définissent complètement l'état de l'algorithme.

Conclusion : la récursivité est ici un choix pour écrire les algorithmes, et pouvoir avoir une idée claire / formaliser le fonctionnement des algorithmes. Le test et la vérification de tels codes en est facilité.
L'exemple ci-dessus montre une décomposition de la présentation : une introduction, un exemple tiré de chaque projet, et une conclusion. L'argumentation vise à montrer que la programmation récursive aide à spécifier les algorithmes. Ces arguments sont repris dans la conclusion. Il ne faut pas trop s'effrayer du style utilisé ci-dessus, c'est le plan général et la conduite de l'argumentation qui sont importants. Noter que le but n'est pas de faire des listes de tout ce qui a été fait dans les projets, mais de choisir des exemples pour défendre un point de vue.