DM 1 - Langage de description de dessins


On va s'intéresser à la construction de dessins par la juxtaposition de carreaux élémentaires, comme cela se pratique pour diverses techniques artisanales (frises, dessus de lit, ...). Ce sujet est inspiré du langage Little Quilt décrit dans le livre Programming Languages: Concepts and Constructs de Ravi Sethi.

1 - Travail demandé

Il s'agit d'écrire un programme pouvant lire sur l'entrée standard des descriptions de dessin et afficher le dessin correspondant.

Par exemple,
java Quilt < mon_dessin.txt
avec un fichier mon_dessin.txt qui contient : 

def bb = b + rot b + rot rot b + rot rot rot b;
def bbb = rot bb + rot rot rot bb;
show (rot bbb[3])[2];
doit produire le dessin :

Quelques explications
Par convention, le terme b désigne le carreau de base . L'opérateur rot permet de le tourner d'un quart de tour dans le sens des aiguilles d'une montre. Et l'opérateur + sert à juxtaposer de la gauche vers la droite. L'expression  b + rot b + rot rot b + rot rot rot b  correspond donc au dessin .
L'instruction  def bb = b + rot b + rot rot b + rot rot rot b;  permet de nommer ce dessin bb. On utilise bb pour construire un autre dessin nommé bbb :


La première colonne de bbb est définie par  rot bb  et la seconde correspond à bb tourné dans l'autre sens, ce qu'on dit par  rot rot rot bb. Finalement, ce bloc bbb est instancié 3 fois par  bbb[3], un raccourci pour  bbb+bbb+bbb. Le tout est tourné d'un quart de tour, ce qui forme la moitié gauche du dessin final et que l'on duplique par  [2]. C'est l'instruction show ... qui produit effectivement le dessin, les instructions def ... ne sont que des définitions.
Une instruction size ... permet d'afficher la taille d'un dessin (en nombre de carreaux).
Par exemple size bbb; répond 2x4 et size (rot bbb[3])[2]; répond 8x6.

Ce qui est demandé
Le travail minimal demandé consiste à programmer la lecture et l'interprétation de telles descriptions de dessins dont la sémantique est précisée ci dessous, en partie 2. La syntaxe du langage et les règles d'interprétation sont données ensuite en parties 3 et 4.

Un certain nombre d'extensions indépendantes et facultatives sont proposées en partie 5. Elles permettent respectivement de colorier un dessin, d'utiliser des expressions arithmétiques dans les descriptions et de définir de nouvelles fonctions.

La remise des travaux se fera par la commande
/users/profs/info/Depot/INF_431/deposer documents DM_1 groupe
avant la date limite du 23 avril 2003.
documents désigne un ou plusieurs fichiers sources (terminaison en .java) et des fichiers d'exemple. Un fichier, avec un nom comme lisez_moi.txt, contenant des explications sur votre travail, comment utiliser le programme, ..., est également souhaité.
groupe doit être remplacé par le numéro de groupe de TD, de 1 à 12.

Pour faciliter la correction, il est demandé que la classe principale s'appelle Quilt et que l'exécution se fasse par :
java Quilt < mon_dessin.txt
Un mode spécial permettant de voir l'ordre de dessin est décrit en 4.2, il sera activé par :
java Quilt debug < mon_dessin.txt

En parallèle, est lancé le concours du plus beau dessin qui servira à décorer le poly de l'an prochain. Le réglement du concours est donné à la fin de l'énoncé.

2 - Sémantique des dessins

Il y a 4 dessins primitifs (a, b, c et d) et 3 opérations (juxtaposition, rotation et répétition) dont les définitions suivent :

a =   b =   c =   d =

+ =

rot =

[n] = ...    (n fois)

Pour tout dessin u, la largeur L(u) et la hauteur H(u), exprimées en nombre de carreaux, sont définies comme suit :
L(a) = L(b) = L(c) = L(d) = H(a) = H(b) = H(c) = H(d) = 1
L(u+v) = L(u)+L(v)  et  H(u+v) = H(u) = H(v)
L(rot(u)) = H(u)  et  H(rot(u)) = L(u)
L(u[n]) = n*L(u)  et  H(u[n]) = H(u) pour n entier positif ou nul.

Lorsqu'un dessin est considéré comme une partie d'un dessin plus grand, son emplacement a aussi de l'importance. On utilise alors le coin supérieur gauche, ie. un point SG(u) dont les coordonnées sont exprimées en nombre de carreaux. Le coin supérieur gauche, la largeur et la hauteur déterminent le rectangle occupé par un dessin.

L'opération de rotation, notée rot consiste à faire tourner un dessin de 90o dans le sens des aiguilles d'une montre.
La rotation inverse n'existe pas en tant que transformation de base, on devra l'exprimer par trois rotations successives.
Par exemple, le dessin qui est la rotation inverse de rot(b)+rot(rot(b)), peut s'écrire rot(rot(rot( rot(b)+rot(rot(b)) ))).

La juxtaposition de deux dessins, u et v, n'est définie que si les deux dessins ont la même hauteur, ie. H(u)=H(v). Cette opération, notée u+v revient à coller v à droite de u, en les alignant horizontalement. Il n'y a pas d'opérateur pour une juxtaposition verticale, on peut l'exprimer en combinant une juxtaposition horizontale avec des rotations.
Par exemple, le dessin est aussi la valeur de l'expression rot( b+rot(rot(rot(b))) ).

Voici d'autres exemples :
s'exprime par rot( rot(rot(a)) + rot(a) ) + rot( rot(rot(rot(a))) + a)
s'exprime par rot( rot(rot(a))+b )+rot( b+rot(rot(b)) ).

3 - Syntaxe du langage

Le langage va permettre de construire des expressions de dessins, de les nommer (par def) et de les visualiser (par show). Pour faciliter la mise au point, on a ajouté l'instruction size qui affiche les dimensions d'un dessin.
Pour faciliter l'écriture des expressions, on rend certaines parenthèses facultatives, notamment pour rot et les [ ].

Les non-terminaux sont écrits en lettres capitales et | sert à séparer plusieurs choix possibles pour la dérivation d'un même non-terminal. 

DESCRIPTION     ::= 
                   | DEFINITION DESCRIPTION
                   | INSTRUCTION DESCRIPTION

DEFINITION      ::=  def IDENTIFICATEUR = DESSIN ;

INSTRUCTION     ::=  show DESSIN ;
                   | size DESSIN ;

DESSIN          ::=  PRIMITIVE
                   | IDENTIFICATEUR
                   | ( DESSIN )
                   | DESSIN + DESSIN
                   | rot DESSIN
                   | DESSIN [ ENTIER ]
Dans un premier temps, on considère que ENTIER désigne une constante numérique entière (ie. une suite de chiffres), positive ou nulle. Le passage à des expressions à valeurs entières constitue une extension, cf. 5.2.
PRIMITIVE désigne un identificateur de carreau prédéfini, c'est-à-dire, a, b, c, d. L'analyse lexicale devra le reconnaître comme tel.
IDENTIFICATEUR désigne alors un identificateur autre qu'un nom de carreau ou qu'un mot réservé.

Règles de précédence
On fera en sorte que + ait une précédence inférieure à rot et que rot ait une précédence inférieure à [ ].
Si bien que l'expression rot a[4]+bbb se comprend comme (rot(a[4]))+bbb et, dans l'exemple d'introduction, rot bbb[3][2] aurait donné un résultat différent de (rot bbb[3])[2].

4 - Interprétation du langage

Le traitement de def IDENTIFICATEUR = DESSIN ; et l'utilisation des variables qui sont expliqués en 4.3, peuvent être différés pour se concentrer sur la réalisation de 4.1 et 4.2. En attendant, les exemples qui utilisent def peuvent être reproduits en se servant du copier-coller.
De toute façon, il faudra traiter correctement 4.3 qui fait partie du travail minimal demandé.

4.1 Réalisation des dessins

Tous les éléments graphiques nécessaires sont donnés dans le fichier PatchWork.java. Pour réaliser le travail minimal demandé, il est hautement recommandé de ne pas modifier la classe PatchWork.

Il faudra faire un appel du type PatchWork.init(java.awt.Color.lightGray); au début du programme pour initialiser le graphique.
La couleur passée en paramètre est utilisée comme fond d'écran. Dans un premier temps, il est préférable d'utiliser une couleur différente du blanc et du noir qui sont les deux couleurs de dessin. La réalisation de dessins en couleur constitue une extension, cf. 5.1.

La méthode PatchWork.clear() efface tout avec la couleur passée à init.

Pour réaliser le dessin d'un carreau, on utilisera la fonction :
PatchWork.paint(int num, int x, int y, int r);
Le paramètre num indique le numéro de primitive, avec les valeurs PatchWork.A, PatchWork.B, PatchWork.C, PatchWork.D, ... respectivement pour les dessins primitifs a, b, c, d, ... La constante PatchWork.NB donne le nombre de primitives définies dans PatchWork.
Les coordonnées x et y du coin supérieur gauche doivent être exprimées en nombre de carreaux, le passage à des coordonnées en pixels est fait automatiquement par PatchWork.
Le paramètre r ne prend que l'une des valeurs 0, 1, 2 ou 3 qui sert à coder le nombre de quarts de tour (dans le sens des aiguilles d'une montre) pour l'orientation du carreau. Voici le dessin des différents carreaux réalisables par PatchWork.paint :

a b c d 4 orientations de a 4 orientations de b
On obtient ces trois dessins par : 
show a+b+c+d;
show a + rot a + rot rot a + rot rot rot a;
show rot(rot rot b + rot b) + rot(rot rot rot b + b);
Le premier dessin est obtenu en enchaînant les appels suivants : 
PatchWork.paint(PatchWork.A, 0, 0, 0); 
PatchWork.paint(PatchWork.B, 1, 0, 0); 
PatchWork.paint(PatchWork.C, 2, 0, 0); 
PatchWork.paint(PatchWork.D, 3, 0, 0);
le deuxième dessin est obtenu par : 
PatchWork.paint(PatchWork.A, 0, 0, 0); 
PatchWork.paint(PatchWork.A, 1, 0, 1); 
PatchWork.paint(PatchWork.A, 2, 0, 2); 
PatchWork.paint(PatchWork.A, 3, 0, 3);
et le troisième dessin est obtenu par : 
PatchWork.paint(PatchWork.B, 0, 0, 3); 
PatchWork.paint(PatchWork.B, 0, 1, 2); 
PatchWork.paint(PatchWork.B, 1, 0, 0); 
PatchWork.paint(PatchWork.B, 1, 1, 1);

4.2 Interprétation d'un dessin

L'exécution d'une instruction show ou size va consister à interpréter récursivement une expression de dessin dans un certain contexte géométrique et dans un contexte de définitions des variables.

Un contexte géométrique est formé de :
- les coordonnées du coin supérieur gauche du dessin, en nombre de carreaux,
- une orientation parmi 4 (ie. rotations de 90o) qui résulte du cumul des rotations utilisées pour l'instanciation du dessin.
Le contexte géométrique initial correspond à un coin supérieur gauche en (0,0) et à l'orientation 0o. L'axe des y est orienté vers le bas, comme souvent en graphique.

Le résultat retourné par l'interprétation d'un dessin u est le couple (L(u),H(u)). Cette information est généralement nécessaire pour placer le reste du dessin.

L'instruction size exécute le dessin dans le contexte géométrique initial sans tracé à l'écran et imprime les dimensions du dessin.

L'instruction show efface l'écran (cela consiste simplement à appeler PatchWork.clear()) puis exécute le dessin dans le contexte géométrique initial en traçant à l'écran. Pour fignoler, on peut passer les dimensions du dessin à PatchWork.resize qui ajuste les dimensions de la fenêtre graphique.

Juxtaposition
La manière de procéder à la réalisation du dessin dépend du contexte d'orientation dans lequel on évalue la somme. Il faut commencer par placer le sous-dessin qui sera le plus en haut et à gauche dans le résultat final puis placer l'autre, soit juste à droite, soit juste en dessous, selon le contexte. Par exemple, pour dessiner rot(rot(a+b+c)), on commencera par placer c le plus à gauche, puis b et a à droite pour finir, tous les trois dans un contexte augmenté de deux rotations. On remarquera que cela ne changerait pas le résultat si on avait parenthésé a+(b+c) ou (a+b)+c.

Pour : 

def disque = rot (rot rot a + rot a) + rot (rot rot rot a + a);
show disque + rot disque;
le dessin se fait dans l'ordre .
On peut obtenir le dessin avec l'ordre d'affichage des carreaux en faisant PatchWork.DEBUG=true; avant de lancer le dessin. On devra passer dans ce mode en mettant debug comme argument du programme, ie :
java Quilt debug < mon_dessin.txt

4.3 Variables de dessins

Une variable de dessin donne un nom à un dessin. Pour interpréter un dessin, il faut connaître les valeurs associées aux variables. Pour simplifier la programmation, on supposera qu'il existe un seul contexte de définition des variables (ce qu'on appelle la liaison dynamique des variables).
Le contexte de définition est réalisé par une classe Environnement qui correspond à une liste d'associations (liste de paires (identificateur,ASA)). Pour retrouver une valeur, on parcourera la liste d'associations jusqu'à retrouver l'identificateur de même nom et on prend l'arbre de syntaxe abstraite correspondant. Si cette identificateur n'existe pas, il y aura une erreur d'exécution lors de l'interprétation du dessin.

Autrement dit, on pourra écrire : 

def x = a;
def quatre_x = rot(rot rot x + rot x) + rot(rot rot rot x + x);
show quatre_x;
def x = rot(rot(rot rot a+b)+rot(b+rot rot b));
show quatre_x;
et obtenir successivement deux dessins différents pour quatre_x, respectivement
et

Remarque
Pour ne pas utiliser trop de mémoire, on évite de construire explicitement un arbre de syntaxe abstraite correspondant à la totalité du dessin à réaliser. Par exemple, pour dessiner aaa avec : 

def aa = a + rot a + rot rot a + rot rot rot a;
def aaa = rot aa + rot rot rot aa;
on ne construit pas l'expression
rot(a + rot a + rot rot a + rot rot rot a) + rot rot rot(a + rot a + rot rot a + rot rot rot a).
On interprète aa, une première fois dans le contexte résultant d'un rot. On interprète de nouveau aa, avec 3 rot et un déplacement du coin supérieur gauche.

5 - Extensions (facultatives)

Ces trois extensions proposées sont indépendantes et peuvent être traitées dans un ordre quelconque.

5.1 Spécification de la couleur


Pour gérer la couleur, on ajoute un opérateur particulier : 
DESSIN    	::=  ...
                   | color ( COLOR_SPEC , COLOR_SPEC ) DESSIN

COLOR_SPEC ::=  COLOR_IDENT
              | ( ENTIER , ENTIER , ENTIER )
La construction color ( ... ) est vue comme un opérateur unaire, de même précédence que rot et permet de spécifier les deux couleurs utilisées pour le dessin des carreaux (par défaut black et white).
La première forme de COLOR_SPEC permet d'utiliser des identificateurs de couleurs, par exemple cyan. On trouvera des définitions de couleurs dans le fichier rgb.txt de la librairie X11. Les couleurs y sont codées par un triplet d'entiers compris entre 0 et 255 qui donnent respectivement les composantes rouge, verte et bleue. La seconde forme de COLOR_SPEC permet d'entrer directement un tel triplet.

On obtient ensuite un objet java.awt.Color par le constructeur Color(int r, int g, int b) et le changement effectif de couleur se fait par un appel à :
PatchWork.setColor(Color c1, Color c2);
Cela affecte tous les appels à PatchWork.paint qui suivent. En fin de portée d'un changement de couleur, il faudra donc restaurer les couleurs précédentes.

Voici quelques exemples :
s'obtient par
show color(red,yellow)disque+color(yellow,red)disque;

s'obtient par 

def x = rot(rot rot b+b)+rot(b+rot rot color(black,red)b);
show color(black,yellow)(rot(rot rot rot x+rot rot x)+rot(x+rot x));

5.2 Arithmétique

Le non-terminal ENTIER désigne maintenant une expression arithmétique à valeur entière (positive ou nulle) et on ajoute la possibilité d'utiliser des variables globales. On a donc une instruction d'affectation qui évalue son membre droit avant d'affecter sa valeur. On ajoute aussi un mécanisme d'itération un peu plus puissant que [], puisqu'il permet d'incrémenter une variable : 
DESCRIPTION     ::=  ...
                   | AFFECTATION DESCRIPTION

AFFECTATION     ::=  let IDENTIFICATEUR = ENTIER ;

DESSIN    	::=  ...
                   | for IDENTIFICATEUR = ENTIER to ENTIER do DESSIN

Par exemple :
show for i = 0 to 4 do rot (c[i]+rot b+d[4-i]);
donne le dessin de taille 5x5 :

5.3 Fonctions

Dans un premier temps, il est plus simple de se limiter à des fonctions unaires, dont l'argument est un dessin. Pour simplifier encore, le nom du paramètre formel sera toujours x. 
DEFINITION      ::=  ...
                   | fun IDENTIFICATEUR ( x ) = DESSIN ;
DESSIN    	::=  ...
                   | IDENTIFICATEUR ( DESSIN )

Par exemple : 

fun irot(x) = rot rot rot x;
def bb = rot(aa) + irot(aa);
Ensuite seulement, on pourra essayer de généraliser, par exemple :
fun stack(x,y) = rot(irot(x) + irot(y));

Ce sujet a été réalisé avec la contribution de Jean-Jacques Lévy, Luc Maranget et Laurent Viennot.

URL: http://www.enseignement.polytechnique.fr/profs/informatique/Philippe.Chassignet/02-03/INF_431/dm_1.html
Dernière mise à jour : 18/07/2003

Pour toutes suggestions, commentaires ou remarques, email : Philippe.Chassignet@polytechnique.fr