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.

  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.

    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é?


Raphaël Collet - 25 novembre 2005