Informatique 2 - Page principale - Environnement de développement - Syntaxe de Oz |
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.
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} endRéé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.
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 |
58 |
89 |
17 |
72 |
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))
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'afficheVoici 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.
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 endVoici 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 |
4 |
d|_ |
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é?