Programmation impérative, projet 2023

Dates et principe

Cette page peut être mise à jour, avec informations complémentaires, précisions, questions bonus, etc. Pensez à y revenir souvent.

Ajout du 13 décembre : schéma montrant comment aller au bloc suivant.

Ajout du 15 décembre : description de résultats attendus pour les programmes fournis en exemple (fichier README.md dans l'archive)

Correction du 3 janvier : nom des actions out(nombre) et out(char) dans la description des actions

Projet à rendre pour le 8/1/2024 à 23h59, aucun retard ne sera toléré.
Des soutenances pourront potentiellement être organisées ensuite.

Lire tout le sujet.

Un rendu de projet comprend :

Un rapport typographié précisant vos choix, les problèmes techniques qui se posent et les solutions trouvées ; il présente en introduction le contexte et le sujet du projet, et il précise en conclusion les limites de votre programme. Le rapport sera de préférence composé avec LATEX. Le soin apporté à la grammaire et à l'orthographe est largement pris en compte.
Un code abondamment commenté ; la première partie des commentaires comportera systématiquement les lignes :
1. @ requires décrivant les préconditions : c'est-à-dire conditions sur les paramètres pour une bonne utilisation (pas de typage ici),
2. @ assigns listant les zones de mémoire modifiées,
3. @ ensures décrivant la propriété vraie à la sortie de la fonction lorsque les préconditions sont respectées, le cas échéant avec mention des comportements en cas de succès et en cas d'échec,
En outre chaque boucle while doit contenir un commentaire précisant la raison de sa terminaison (le cas échéant). De même en cas d'appels récursifs.
On pourra préciser des informations additionnelles si des techniques particulières méritent d'être mentionnées.

Le code doit enfin compiler sans erreur (évidemment) et sans warning lorsque l'option -Wall est utilisée. Un code qui ne compile pas se verra attribuer la note de 0.
Un manuel d'utilisation de votre exécutable, même minimal, est toujours bienvenu.

Avez-vous lu tout le sujet ?

Protocole de dépôt

Vous devez rendre

votre rapport (en pdf) et
vos fichiers de code

rassemblés dans une archive tar gzippée identifiée comme votre_prénom_votre_nom.tgz.
La commande devrait ressembler à :
tar zcvf randolph_carter.tgz rapport.pdf fichiers.c autres_trucs_éventuels.c…
N'OUBLIEZ surtout PAS de mettre le nom identifiant l'archive (donc nouveau) en PREMIER.
Lisez le man ! et testez le contenu de votre archive (une commande comme par exemple :
tar tvf randolph_carter.tgz doit lister les fichiers et donner leur taille).

Une archive qui ne contient pas les fichiers demandés ne sera pas excusable.
**Une archive qui n'est pas au format demandé (archive tar gzippée avec suffixe .tgz) ne sera pas corrigée** donc c'est 0/20.

Toute tentative de fraude (plagiat, etc.) sera sanctionnée. Si plusieurs projets ont des sources trop similaires (y compris sur une partie du code uniquement), tous leurs auteurs se verront attribuer la note 0/20. En particulier, il faudra prendre soin de ne pas publier son travail sur un dépôt public (en tout cas pas avant la date de fin de rendu). On évitera également de demander (ou de donner) des conseils trop précis à ses camarades (y compris des promotions précédentes), ces conseils ayant pu être donnés à plusieurs personnes. Les rendus seront comparés deux à deux.

Procédure de dépôt
Vous devez enregistrer votre archive tgz dans le dépôt dédié au cours PRIM11 (prim11-2023) en vous connectant à http://exam.ensiie.fr. Ce dépôt sera ouvert jusqu'au 8 janvier inclus.

Contexte

Le but de ce projet est d'implémenter un interpréteur pour un langage de programmation dont les programmes sont des images.

Cornelis est un langage de programmation fortement inspiré du langage Piet, qui se définit comme un langage dont les programmes ressemblent à des tableaux d'art abstrait. (Cornelis est le second prénom de Pieter Mondriaan, plus connu sous son nom d'artiste Piet Mondrian.) En Cornelis comme en Piet, les programmes sont donnés sous la forme d'image en deux dimensions. Le contenu de l'image est parcouru, ce qui entraîne un certain nombre d'actions.

Géométrie de l'image

L'image est constituée d'une grille de pixels de composantes rouge/verte/bleue. Chaque pixel a un voisin à gauche, à droite, en haut et en bas. En particulier, l'image doit être considérée comme un tore : le voisin d'un pixel située sur la ligne tout en haut est le pixel de la même colonne situé tout en bas, et réciproquement ; de même, le voisin d'un pixel située sur la colonne tout à droite est le pixel de la même ligne situé tout à gauche, et réciproquement.

Couleurs

En Cornelis, il y a 18 couleurs codantes, que l'on peut donner par leur code HTML :

#FF8080 rouge clair	#FFFF80 jaune clair	#80FF80 vert clair	#80FFFF cyan clair	#8080FF bleu clair	#FF80FF magenta clair
#FF0000 rouge	#FFFF00 jaune	#00FF00 vert	#00FFFF cyan	#0000FF bleu	#FF00FF magenta
#800000 rouge foncé	#808000 jaune foncé	#008000 vert foncé	#008080 cyan foncé	#000080 bleu foncé	#800080 magenta foncé

Les autres couleurs seront réparties en deux catégories en fonction de leur luminance : celles dont la luminance est strictement inférieure à 128 seront bloquantes, les autres seront passantes. La luminance sera calculée à l'aide de la formule : 0.202 × rouge + 0.707 × vert + 0.071 × bleu.

Blocs

On ne considérera pas les pixels individuellement mais pas regroupés par blocs de même couleur. Un bloc est un ensemble de pixels contigus de même couleur, délimités par des pixels d'une autre couleur. Attention, comme l'image est un tore, les blocs peuvent déborder des limites de l'image et continuer de l'autre côté.

Pour faire un traitement sur un bloc (par exemple pour calculer sa taille ou pour trouver son pixel le plus en haut à gauche), on pourra utiliser un algorithme de type remplissage, avec un tableau supplémentaire, initialement rempli de zéros, qui indiquera les pixels déjà traités et limitera les appels récursifs :

traitement(i : image, init : couleur, x : colonne, y : ligne, traité : tableau)
  traité[x,y] := 1
  si init = i[x, y]
    ... traitement du pixel en x, y ...
    pour chacun des quatre voisins vx, vy de x,y
      si non traité[vx,vy]
        traitement(i, init, vx, vy, traité)

État de l'interpréteur

L'interpréteur du code comportera

les coordonnées du pixel courant ;
la direction actuelle parmi est, sud, ouest et nord ;
le bord actuel parmi bâbord (gauche) et tribord (droite) ;
un pile d'entier.

Les coordonnées initiales seront celles du pixel en haut à gauche. La direction initiale sera vers l'est. Le bord initial sera bâbord. La pile sera initialement vide.

Exécution du programme

Un pas du programme consiste à chercher le prochain bloc vers lequel aller. Pour cela, on considère la frontière du bloc courant qui est la plus loin dans la direction actuelle (par exemple, la plus à droite si la direction est vers l'est). Ensuite, sur cette frontière, on considère le pixel le plus du bord actuel (par exemple, le plus en haut si la direction est vers l'est et le bord bâbord). Le pixel recherché est résumé dans le tableau suivant :

direction	bord	pixel retenu
est	bâbord	frontière droite, le plus haut
est	tribord	frontière droite, le plus bas
sud	bâbord	frontière basse, le plus à droite
sud	tribord	frontière basse, le plus à gauche
ouest	bâbord	frontière gauche, le plus bas
ouest	tribord	frontière gauche, le plus haut
nord	bâbord	frontière haute, le plus à gauche
nord	tribord	frontière haute, le plus à droite

Attention, puisque l'image est un tore, la limite de l'image n'est pas forcément une frontière pour le bloc car il peut continuer de l'autre côté s'il s'agit de la même couleur.

Si jamais un bloc n'a pas de frontière dans la direction donnée (parce que c'est un bandeau tout le long de l'image), alors le comportement est indéfini.

Une fois sur ce pixel, on se déplace à nouveau dans le sens de la direction.

Si le nouveau pixel est une couleur codante, il indique le nouveau bloc.
Si c'est une couleur bloquante, on inverse le bord et on recommence depuis l'ancien bloc. Si on tombe à nouveau sur une couleur bloquante, on tourne la direction dans le sens des aiguilles d'une montre, et on recommence depuis l'ancien bloc. On continue comme ceci en modifiant le bord et la direction de façon alternée. Si après 8 tentatives on n'a obtenu que des couleurs bloquantes, le programme s'arrête.
Si le nouveau pixel a une couleur passante, alors on continue dans la direction jusqu'à atteindre une couleur non passante. Si c'est une couleur codante, c'est le nouveau bloc. Si c'est une couleur bloquante, alors on procède comme indiqué ci-dessus, mais en repartant du premier pixel passant et non de l'ancien bloc. Le fait d'être passé par une couleur passante remet à zéro les tentatives par rapport à l'arrêt du programme.

Exemple (on est dans le bloc rouge entouré de pointillés) :

direction	bord	pixel retenu	bloc suivant	action (cf. infra)
est	bâbord	a	magenta (a')	in(char)
est	tribord	b	jaune (b')	rien
sud	bâbord	c	bleu (c')	duplique
sud	tribord	d	bleu (d')	rien
ouest	bâbord	e	bleu (e')	duplique
ouest	tribord	d	bleu clair (d")	in(nombre)
nord	bâbord	f	bleu (f')	duplique
nord	tribord	g	cyan foncé (g')	direction

Actions

À chacun des pas, on va potentiellement agir sur la pile. L'action à effectuer dépend des différences de couleurs entre le bloc d'origine et celui où on est arrivé.

Si on est passé par des pixels de couleur passante, alors on ne fait rien, quelle que soit la couleur des blocs d'origine et de destination.

Sinon, on va considérer la différence entre les couleurs dans le cycle rouge -> jaune -> vert -> cyan -> bleu -> magenta -> rouge et la différence de luminosité dans le cycle clair -> normal -> foncé -> clair.

	Différence de luminosité
Différence de couleur	Aucune	1 plus foncé	2 plus foncé
Aucune		empile	dépile
1 cran	plus	moins	fois
2 crans	divise	reste	non
3 crans	plus grand	direction	bord
4 crans	duplique	tourne	in(nombre)
5 crans	in(char)	out(nombre)	out(char)

Attention, clair est donc considéré comme une fois plus foncé que foncé.

empile

on ajoute sur la pile la taille de l'ancien bloc

dépile

on supprime un élément de la pile (on ne fait rien avec)

plus

on dépile deux éléments et on empile leur somme

moins

on dépile deux éléments et on empile la différence entre le second et le premier

fois

on dépile deux éléments et on empile leur produit

divise

on dépile deux éléments et on empile le quotient du second par le premier

reste

on dépile deux éléments et on empile le reste de la division entière du second par le premier

non

on dépile un élément et on empile 1 si l'élément vaut 0 et 0 sinon

plus grand

on dépile deux éléments et on empile 1 si le second est plus grand que le premier, 0 sinon

direction

on dépile un élément et on fait tourner ce nombre de fois la direction dans le sens des aiguilles d'une montre

bord

on dépile un élément et on inverse ce nombre de fois le bord

duplique

on dépile un élément et on le rempile deux fois

tourne

on dépile deux éléments et on va faire "tourner" la pile jusqu'à la profondeur donnée par le second, autant de fois que le premier élément. Faire tourner la pile une fois jusqu'à la profondeur d consiste à enlever l'élément au sommet de la pile et à le remettre à la profondeur d en faisant remonter les autres. Par exemple, en partant de la pile

2 5 1 2 3 4 5 6 7

(le sommet est à gauche), on va tourner deux fois à la profondeur cinq le reste de la pile, ce qui donnera la pile

3 4 5 1 2 6 7

in(nombre)

on lit un entier sur l'entrée standard et on l'empile

in(char)

on lit un caractère sur l'entrée standard et on empile son code ASCII

out(nombre)

on dépile un élément et on l'affiche sur la sortie standard

out(char)

on dépile un élément et on affiche sur la sortie standard le caractère possédant ce code ASCII

Si jamais il n'y a pas assez d'éléments dans la pile pour effectuer l'action demandée, on ne fait rien et on laisse la pile comme elle était avant le changement de bloc. On fera en particulier attention au cas de tourne.

Interface

L'exécutable final prendra en premier argument le nom d'un fichier au format PPM qui contiendra l'image contenant le code. Les entrées et sorties se feront sur l'entrée et la sortie standard.

Si le programme final s'appelle prog, et qu'on a un fichier d'entrée nommé test.ppm, il devrait être possible d'entrer la commande

./prog test.ppm

pour interpréter le code contenu dans test.ppm.

Exemples

On trouvera dans le fichier cornelis.tgz un certains nombres de fichiers d'entrées (exemple.ppm).

D'autres exemples seront possiblement proposés d'ici la date de rendu.

Lors de la correction, votre programme sera testé avec des exemples qui n'auront pas été fournis à l'avance ; faire passer les exemples ne suffira donc pas, il faudra bien respecter la spécification.

Bonus

Faire un environnement de débogage qui permet de suivre l'exécution du code, ajouter des points d'arrêt, etc.
Permettre de lire d'autres formats d'image que PPM (potentiellement en utilisant une bibliothèque).

Conseils

Pour la récupération d'une entrée de l'utilisateur, plutôt que faire un scanf directement, il vaut parfois mieux récupérer une ligne en entier avec fgets puis utiliser sscanf dessus ; on peut utiliser la suite de commandes suivantes :

char buf[256];
 .
 .
 .
fgets(buf, 256, stdin);
sscanf(buf, "format", ...);

Pour lire un seul caractère, on pourra utiliser getc, qui renvoie EOF en cas d'erreur ou en fin de fichier.

Il pourra être opportun d'utiliser certaines fonctions de la bibliothèque standard comme memcpy ou memset. Se reporter aux pages de manuel pour leur fonctionnement.

Vous devez avoir lu jusqu'ici avant de commencer.