Séance 10
Programmer avec l'état

Dans cette séance, nous allons utiliser les cellules pour implémenter des algorithmes. Nous allons ainsi pouvoir comparer des versions déclaratives et non déclaratives de plusieurs algorithmes.

Dans ces exercices, nous utiliserons souvent des boucles for, sur des listes et des intervalles d'entiers. La syntaxes des deux types de boucle est schématisée ci-dessous. La boucle à gauche exécute l'instruction donnée pour chaque élément X de la liste Xs. La boucle à droite exécute l'instruction donnée pour chaque entier I entre A et B (dans l'ordre de A à B).

   for X in Xs do instruction end

   for I in A..B do instruction end

Chacune est en fait une notation pour un appel d'une procédure récursive.

Enoncés des exercices

1. Accumulateurs et état. Pour implémenter des fonctions efficaces dans le paradigme déclaratif, nous avons utilisé des accumulateurs dans les paramètres des fonctions. Un accumulateur est une forme d'état implicite. Un exemple typique est la fonction Reverse, qui renvoie la liste passée en argument avec ses éléments dans l'ordre inverse.

      fun {Reverse Xs}
         fun {ReverseAux Xs Ys}
            case Xs of nil then Ys
            [] X|Xr then {ReverseAux Xr X|Ys}
            end
         end
      in
         {ReverseAux Xs nil}
      end
   

   Réécrivez cette fonction pour rendre explicite l'état passé dans l'argument Ys de ReverseAux. En d'autres mots, construisez une implémentation de la fonction qui utilise une cellule. Conseil: Utilisez une boucle for.

   • A votre avis, votre fonction est-elle efficace, comparée à la définition avec accumulateur ci-dessus?

   • L'état explicite que vous avez introduit est-il visible ou encapsulé? S'il est encapsulé, à quel endroit? Combien de fois créez-vous une cellule?

   • Pouvez-vous également créer un état explicite pour l'argument Xs? Si c'est le cas, implémentez-le. Sinon, expliquez pourquoi.

2. Une calculatrice. Dans cet exercice, nous allons implémenter une calculatrice utilisant la notation postfixe (ou notation polonaise inversée). Dans cette notation, l'opérateur est écrit après ses deux opérandes. Par exemple, l'expression (13+45)*(89-17) se note "13 45 + 89 17 - *". L'avantage de cette notation est qu'elle ne nécessite pas l'utilisation de parenthèses.

   L'évaluation d'une expression postfixe est très simple. On utilise une pile pour stocker les résultats intermédiaires. Il suffit de parcourir l'expression de gauche à droite, et de traiter les éléments (valeurs et opérateurs) un à un. Lorsqu'on lit une valeur, on la met sur la pile. Lorsqu'on lit un opérateur, on retire les deux valeurs au sommet de la pile, on leur applique l'opérateur, puis on met le résultat sur la pile. A la fin, la pile doit contenir une seule valeur: le résultat du calcul. Ci-dessous, de gauche à droite, les étapes du calcul de l'expression postfixe "13 45 + 89 17 - *". La ligne supérieure contient le reste de l'expression, la ligne inférieure la pile des valeurs intermédiaires.

   13 45 + 89 17 - *	45 + 89 17 - *	+ 89 17 - *	89 17 - *	17 - *	- *	*
   	13	45 13	58	89 58	17 89 58	72 58	4176

   Ecrivez une abstraction de données pile. Cette abstraction est définie par quatre opérations: NewStack, IsEmpty, Push et Pop. Push est une procédure, les autres sont des fonctions.

   • {NewStack} renvoie une nouvelle pile.
   • {IsEmpty S} renvoie true si la pile S passée en argument est vide, false sinon.
   • {Push S X} empile l'élément X sur la pile S.
   • {Pop S} enlève le sommet de la pile S et le renvoie.

   Une pile est représentée par une cellule contenant une liste. La liste contient les éléments de la pile, du sommet à la base. Le premier élément de la liste est donc le sommet de la pile.

   Ensuite, écrivez une fonction Eval qui prend en paramètre une expression postfixe et renvoie son évaluation. L'expression est représentée par une liste dont chaque élément est soit un entier, soit un des atomes '+', '-', '*' et '/', cette dernière devant être interprétée comme la division entière. L'expression de l'exemple ci-dessus sera représentée par la liste [13 45 '+' 89 17 '-' '*']. La fonction Eval parcourt cette liste et met à jour le contenu d'une pile, en suivant l'algorithme présenté informellement ci-dessus.

      {Browse {Eval [13 45 '+' 89 17 '-' '*']}}   % affiche 4176 = (13+45)*(89-17)
      {Browse {Eval [13 45 '+' 89 '*' 17 '-']}}   % affiche 5145 = ((13+45)*89)-17
      {Browse {Eval [13 45 89 17 '-' '+' '*']}}   % affiche 1521 = 13*(45+(89-17))
   

3. Encapsulation de l'état de la pile. Nous allons maintenant implémenter une variante de l'abstraction pile présentée dans l'exercice précédent. Cette variante rend l'état de la pile invisible à l'utilisateur. Il s'agit donc de ``cacher'' la cellule contenant la liste par portée lexicale. La fonction NewStack ne peut donc pas renvoyer directement la cellule. Elle va plutôt renvoyer une liste de fonctions et procédures:

      {NewStack} -> [IsEmpty Push Pop]
   

   Les fonctions IsEmpty, Pop et la procédure Push sont spécifiques à la pile qui vient d'être créée. Voici un exemple d'utilisation, avec deux piles.

      declare
      [IsEmpty1 Push1 Pop1]={NewStack}   % pile 1
      [IsEmpty2 Push2 Pop2]={NewStack}   % pile 2
   
      {Browse {IsEmpty1}}                % affiche true; la pile 1 est vide
      {Push1 13}                         % empile 13 sur la pile 1
      {Browse {IsEmpty1}}                % affiche false; la pile 1 n'est pas vide
      {Browse {IsEmpty2}}                % affiche true; la pile 2 est toujours vide
      {Push1 45}                         % empile 45 sur la pile 1
      {Push2 {Pop1}}                     % enlève 45 de la pile 1 et l'empile sur la pile 2
      {Browse {IsEmpty2}}                % affiche false; la pile 2 n'est pas vide
      {Browse {Pop1}}                    % enlève 13 de la pile 1 et l'affiche
   

   Voici un squelette d'implémentation pour NewStack. Complétez-le.

      fun {NewStack}
         ...
         fun {IsEmpty} ... end
         proc {Push X} ... end
         fun {Pop} ... end
      in
         [IsEmpty Push Pop]
      end
   

   Adaptez la fonction Eval que vous avez écrite dans l'exercice précédent afin qu'elle utilise cette implémentation de l'abstraction de données pile.

4. Mélanger une liste. Dans cet exercice, nous allons utiliser un tableau pour "mélanger" les éléments d'une liste. Vous devez définir une fonction Shuffle qui prend en argument une liste Xs et renvoie une liste, contenant les mêmes éléments que Xs, mais dans un ordre aléatoire.

      {Browse {Shuffle [a b c d e]}}   % peut afficher [d c a b e]
   

   Vous utiliserez la fonction Random définie ci-dessous pour effectuer des tirages aléatoires d'entiers entre 1 et l'argument N.

      %% renvoie un nombre aleatoire entre 1 et N
      fun {Random N} {OS.rand} mod N + 1 end
   

   Voici un rappel des principales opérations sur les tableaux en Oz.

   Opération	Description	Complexité temporelle
   {NewArray I J X}	renvoie un tableau indicé de I à J dont les éléments sont initialisés avec la valeur X	Θ(n)
   A.I	renvoie le Ième élément du tableau A	Θ(1)
   A.I:=X	affecte la valeur X au Ième élément de A	Θ(1)

   L'algorithme que vous devez utiliser est le suivant. Tout d'abord, mettez les éléments de la liste dans un tableau a, indicé de 1 à n, où n est le nombre d'éléments de la liste. Ensuite, tirez un nombre aléatoire i entre 1 et n. Le ième élément de a est la tête de la liste résultat. Copiez l'élément a(n) à l'indice i. Les éléments a(1), ..., a(n-1) sont les éléments restants. Faites un nouveau tirage en remplaçant n par n-1 pour choisir le deuxième élément de la liste résultat, et ainsi de suite jusqu'au dernier.

   Voici une représentation de l'exécution de l'exemple ci-dessus. La colonne de gauche représente les états successifs du tableau. la seconde colonne est l'indice i choisi, et la colonne à droite montre le résultat "en construction". La partie non grisée dans le tableau montre les éléments restants.

   tableau	i	résultat
   a b c d e a b c e e a b e e e e b e e e e b e e e e b e e e	4 3 1 2 1	d|_ d|c|_ d|c|a|_ d|c|a|b|_ d|c|a|b|e|_ d|c|a|b|e|nil

   Quelle est la complexité de votre algorithme? Pourriez-vous trouver un algorithme déclaratif simple qui résoud le même problème avec la même complexité?