CSC 3101 – Algorithmique et langage de programmation

Dans un projet nommé ast, créez une classe tsp.ast.Main contenant une méthode main.

Écrivez une classe nommée Scalar avec un unique champ (privé) de type entier nommé value. Outre un constructeur permettant d'initialiser le champ value, ajoutez les méthodes d'instance suivantes à Scalar :

• public int get() : cette méthode renvoie la valeur du scalaire,
• public String toString() : cette méthode retourne une chaîne de caractères représentant la valeur du scalaire en utilisant la méthode statique Integer.toString(int i).

Dans la méthode main, créez le scalaire 1 et affichez-le dans le terminal.

On souhaite maintenant créer un arbre capable d'additionner deux scalaires. Écrivez une classe nommée Add contenant deux champs de type Scalar nommés left et right. Le constructeur de Add doit prendre en argument les opérandes de gauche et de droite et les affecter aux champs. Ajoutez les méthodes suivantes à Add :

• public int execute() : renvoie le résultat de l'addition de l'opérande de gauche avec l'opérande de droite.
• public String toString() : renvoie la chaîne de caractères (+ e1 e2), dans laquelle e1 est la représentation de left sous la forme d'une chaîne de caractères et e2 celle de right.

Dans la méthode main, utilisez Add pour calculer et afficher le résultat de l'addition de 1 et 2. Vous veillerez aussi à afficher l'expression et à vérifier que l'affichage produit est bien (+ 1 2).

Créez une interface nommée Node définissant la méthode int execute(). Comme Add possède déjà une méthode execute, vous pouvez aussi directement déclarer que Add met en œuvre Node sans autre modification.

Modifiez Scalar de façon à ce que Scalar mette en œuvre Node. L'évaluation d'un scalaire doit simplement renvoyer sa valeur.

Dans Add, modifiez les types des membres de gauche et de droite de façon à ce que ce qu'ils aient le type générique Node. Modifiez le constructeur de façon à prendre en paramètre deux nœuds, et modifiez la méthode execute de façon à ce qu'elle additionne le résultat de execute() sur le membre de gauche avec le résultat de execute() sur le membre de droite. Vérifiez que vous arrivez toujours à calculer la somme de 1 et 2.

Construisez l'expression correspondant à (+ (+ 1 2) (+ 3 4)) dans la méthode main. Affichez cette expression sur le terminal avant d'afficher le résultat de son évaluation. Sur le terminal, vous devriez voir :

Nous modifions notre code étape par étape pour introduire une nouvelle classe générique représentant n'importe quelle opération. Dans un premier temps, nous insérons une classe abstraite nommée Operation dans l'arbre d'héritage. Cette classe représente une opération quelconque. Pour le moment, cette classe est vide, le but de la question n'étant que de l'insérer de façon à obtenir l'arbre d'héritage/mise en œuvre suivant :

Créez donc une classe abstraite nommée Operation et mettant en œuvre Node. Cette classe est abstraite car elle ne met pas elle-même en œuvre la méthode execute qui est mise en œuvre dans les classes filles. Modifiez ensuite la classe Add de façon à ce qu'elle ne mette plus en œuvre Node, mais hérite de Operation.

La classe Operation représente n'importe quelle opération et le nombre d'opérandes n'est donc pas fixe (l'inversion du signe a une unique opérande alors que l'addition en a deux). Pour cette raison, ajoutez à la classe Operation :

• un champ privé Node[] ops contenant l'ensemble des opérandes,
• une méthode publique Node op(int i) permettant d'accéder à la i^ième opérande,
• une méthode publique int nbOps() renvoyant le nombre d'opérandes,
• un constructeur publique Operation(Node... ops) permettant d'initialiser le champ ops de Operation. On vous rappelle que Node... ops permet de déclarer une méthode avec un nombre variable d'arguments, et que les arguments sont rangés sous la forme d'un tableau dans ops.

Pour finir, dans le constructeur de Add, utilisez super pour initialiser de façon adéquate le tableau d'opérandes de Operation via le constructeur de Operation. À cette étape, les opérandes sont donc représentées deux fois : une fois dans Operation sous la forme d'un tableau, et une fois dans Add sous la forme des champs left et right. Pour le moment, conservez cette double représentation.

Modifiez les méthodes int execute() et String toString() de Add de façon à utiliser la méthode Node op(int i) pour accéder aux opérandes. Vous pouvez maintenant vous débarrasser des champs left et right de Add de façon à ne conserver qu'une unique représentation des opérandes dans la classe Operation.

Nous souhaitons maintenant rendre la méthode String toString() générique en la déplaçant de Add vers Operation. Dans Operation, on connaît les opérandes, mais pas encore l'opération. Pour cette raison, nous effectuons une étape intermédiaire avant de déplacer la méthode String toString(). À cette étape on vous demande donc juste d'ajouter une méthode abstraite String opString() à la classe Operation et de la mettre en œuvre dans Add. Cette mise en œuvre doit renvoyer la chaîne de caractères "+". Enfin, modifiez Add.toString() de façon à utiliser opString() pour générer le '+'.

Déplacez maintenant String toString() de Add vers Operation. Au lieu de considérer que votre opération a forcément deux opérandes, modifiez la méthode toString() pour qu'elle concatène les nbOps() opérandes.

Écrivez une classe Neg héritant de Operation et permettant d'inverser le signe de son opérande. Modifiez la méthode main de façon à afficher et évaluer l'arbre (+ (+ 1 2) (- (+ 3 4))) qui devrait donner comme résultat -4.

Ajoutez une classe Variable héritant de Scalar et contenant :

• un champ String name indiquant le nom de la variable,
• un constructeur prenant en argument le nom de la variable et pré-initialisant la variable à 0 en utilisant super.

Évaluer une variable revient à renvoyer sa valeur. La méthode int execute() mise en œuvre dans Scalar effectue déjà ce travail et il n'est donc pas nécessaire de la redéfinir dans Variable. En revanche, lorsqu'on affiche une variable avec String toString(), on veut afficher le nom de la variable et non sa valeur. Redéfinissez donc la méthode String toString() dans Variable de façon à afficher le nom de la variable. Dans la méthode main, allouez une variable x, puis affichez et évaluez l'arbre (+ x 20), qui devrait donc être évalué à 20 puisque x est pré-initialisé à 0.

Ajoutez une classe Set, héritant de Operation, et permettant de modifier une variable. Cette opération prend deux arguments : une variable et un nœud quelconque. L'affichage d'une expression doit produire la chaîne de caractère (set! var val) où var est la variable et val un nœud quelconque.

Testez votre opération Set en affichant et évaluant l'expression (set! x 22) avant d'afficher et évaluer l'expression (+ x 20). Ces affichages et évaluations devrait produire l'affichage suivant :

De façon à afficher des résultats intermédiaires, ajoutez une classe Echo héritant de Opération. Cette classe représente une opération (echo expr), qui affiche sur le terminal le résultat de l'évaluation de expr avant de renvoyer ce résultat. Vérifiez que (+ (echo (+ 1 2)) 7) affiche bien 3 pendant l'évaluation et que l'évaluation de l'expression est bien égale à 10.

Pour gérer les conditions, nous avons besoin de booléens. Dans notre petit interpréteur, un scalaire est directement considéré comme un booléen : si sa valeur est égale à 0, c'est que le scalaire est un booléen faux, sinon, c'est que c'est un booléen vrai. À partir de ce choix, ajoutez une classe If permettant d'évaluer une condition. L'arbre d'une condition est (if condition ifTrue ifFalse), où condition, ifTrue et ifFalse sont des nœuds. Vérifiez que (if 1 42 666) s'évalue bien en 42 et (if 0 42 666) s'évalue bien en 666.

Pour écrire des programmes avancés, nous avons besoin de blocs. Un bloc est simplement une opération dont le nombre d'opérandes est variable et telle que son évaluation évalue chacune des opérandes avant de renvoyer le résultat de l'évaluation de sa dernière opérande. Lorsque nous affichons l'arbre, nous représentons l'expression correspondant à un bloc par (begin e1 ... en). Ajoutez une classe Begin permettant d'évaluer un bloc. Vérifiez que (if 1 (begin (echo 0) 42) 666) affiche bien 0 pendant l'évaluation et que le résultat de cette évaluation est bien 42.

Ajoutez maintenant la classe Lt permettant d'évaluer un arbre (< e1 e2). Cette évaluation doit renvoyer vrai (1) si e1 est plus petit que e2 et faux (0) sinon.

Finalement, ajoutez une classe While permettant d'évaluer l'arbre (while cond body). L'évaluation doit commencer par évaluer cond. Si le résultat de cette évaluation est vrai (un nombre différent de 0), l'évaluation doit continuer en évaluant body avant de recommencer l'évaluation de cond. Le résultat de l'évaluation doit être celui du dernier body exécuté. Si body n'est jamais exécuté, le résultat de l'évaluation doit être le nombre 0.

Construisez, affichez et interprétez l'arbre (begin (set! x 0) (while (< x 10) (begin (echo x) (set! x (+ x 1))))). Qu'affiche votre programme ?