Cher Hugo,
Je te propose une petite utilisation amusante du langage
Objective Caml : le codage et décodage de messages.
Les messages seront présentés sous forme de chaînes de
caractères. Par exemple :
# "LA CIMAISE ET LA FRACTION" ;;
- : string = "LA CIMAISE ET LA FRACTION"
Je n'utilise que des lettres majuscules sans accent pour simplifier.
Comme il nous servira par la suite, nous allons donner le nom
message à ce message :
# let message = "LA CIMAISE ET LA FRACTION" ;;
val message : string = "LA CIMAISE ET LA FRACTION"
On applique à message une mystérieuse fonction code
et on obtient :
# code message ;;
TI KQUIQAM MB TI NZIKBQWV
- : unit = ()
Attention, notre fonction modifie la valeur du message qu'on lui
donne :
# message ;;
- : string = "TI KQUIQAM MB TI NZIKBQWV"
On a, bien sûr, la fonction inverse (decode) qui permet de
retrouver le message original :
# decode message ;;
LA CIMAISE ET LA FRACTION
- : unit = ()
Tout le travail maintenant est d'écrire les fonctions
code et decode. Mais avant d'en arriver là, voici quelques
mots sur le principe de codage utilisé.
Principes du codage par substitution
Outre l'espace qui sépare les mots, que l'on a laissé intact, le
message est uniquement composé des lettres de l'alphabet
latin majuscule. Pour obtenir le message codé, on a simplement
remplacé chacune des lettres du message de départ par une autre
(d'oùle terme << codage par substitution >>)
L'association entre lettres du message de départ et lettres du
message codé que l'on a utilisée est la suivante :
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
On a donc remplacé le A par I, le B par J,
..., le R par Z, le S par A, etc.
Remplacement d'un caractère par un autre dans une chaîne de
caractères
La première opération qu'il faut savoir effectuer est de remplacer
une lettre par une autre dans un message.
Je te rappelle que les << messages >> dont nous nous occupons sont, du
point de vue du langage de programmation, des chaînes de
caractères : ce que l'on prononce string en Objective Caml. Et les
lettres sont appelées de façon plus générale des
caractères : ce que l'on prononce char en Objective Caml. Les
caractères sont écrit entre apostrophes :
# 'A' ;;
- : char = 'A'
Dans une chaîne, les caractères sont rangés dans un certain
ordre, ce qui fait que l'on peut parler du 1ier caractère, du
2ième, ..., du i-ième, etc. En d'autres termes : chaque
caractère présent dans une chaîne de caractère y possède un
numéro ; en informatique, on dit un indice. Curieusement,
mais il y a de bonnes raisons pour cela, les numéros des
caractères commencent à 0 et non pas à 1. Ainsi, le premier
caractère de message a le numéro 0 et on peut y accéder
en écrivant :
# message.[0] ;;
- : char = 'L'
Le deuxième caractère a le numéro 1 :
# message.[1] ;;
- : char = 'A'
etc. jusqu'au dernier, qui a le numèro 24 :
# message.[24] ;;
- : char = 'N'
Si l'on essaie d'aller au-delà du dernier caractère, on obtient
une erreur d'exécution :
# message.[25];;
Uncaught exception: Invalid_argument("String.get")
On peut modifier la valeur d'un caractère d'une chaîne en
écrivant :
# message.[2] <- 'X' ;;
- : unit = ()
Pour voir le résultat obtenu, on peut utiliser la fonction
d'affichage à l'écran des chaînes de caratères :
# print_string message ;;
LAXCIMAISE ET LA FRACTION- : unit = ()
On a ici remplacé l'espace entre LA et CIMAISE par le
caractère 'X'.
Parcours des caractères d'une chaîne
Si on veut répéter l'opération ci-dessus de remplacement des
espaces, par un X, on peut écrire un petit programme qui
examinera chacun des caractères de message et leur
substituera un X chaque fois qu'elle trouvera un espace.
Pour savoir si un caractère de message est égal à l'espace ou
non, on utilise un test d'égalité. La valeur de ce test est
true (i.e vrai) ou false (i.e. faux). Par
exemple :
# message.[2] = ' ' ;;
- : bool = false
# message.[10] = ' ' ;;
- : bool = true
Si l'on veut effectuer une action lorsque qu'un test est vrai, on
utilise une instruction des langages de programmation appelée
conditionnelle et que l'on écrit si ... alors ... en
anglais. Par exemple on va tester ici l'égalité du caratère numéro
10 avec l'espace et si ce test est vrai, on fera deux choses :
remplacer l'espace par un X puis afficher le nouveau contenu de
message.
# if message.[10] = ' ' then
(message.[10] <- 'X'; print_string message) ;;
LAXCIMAISEXET LA FRACTION- : unit = ()
On a mis entre parenthèses les deux actions à effectuer et on les
a séparées par un point-virgule.
Si le caractère testé n'est pas un espace, l'action associée
aprés le then n'est pas effectuée :
# if message.[10] = ' ' then
(message.[10] <- 'X'; print_string message) ;;
- : unit = ()
Ici donc, message n'est pas réaffiché et il n'a pas étémodifé. Ce que l'on peut vérifier en demandant sa valeur :
# message ;;
- : string = "LAXCIMAISEXET LA FRACTION"
Pour examiner chacun des caractères de message, on utilise
une instruction particulière des langages de programmation appelée
boucle. Une boucle est destinée à répéter un certain
nombre de fois une action. L'action que nous allons ici répéter
est l'instruction conditionnelle suivante
if message.[i] = ' ' then message.[i] <- 'X'
Remarque que le numéro de caractère testé n'est pas donné par
un nombre, mais par une variable i. C'est la structure
d'instruction de boucle qui donne à cette variable toutes les valeurs
comprise entre une première (on prendra ici 0) et une dernière (on
prendra ici, 24 qui le numéro du dernier caractère de
message). Aprés la boucle, on affichera la valeur modifée
de message.
Voici ce petit programme :
let message = "LA CIMAISE ET LA FRACTION" ;;
for i=0 to 24 do
if message.[i] = ' ' then message.[i] <- 'X'
done;
print_string message ;;
LAXCIMAISEXETXLAXFRACTION- : unit = ()
Je te laisse faire en exercice le petit programme qui fait le travail
inverse : remplacer les X par des espaces.
Listes d'association
Pour obtenir le programme de codage des messages, il faut faire
connaître à la machine l'aasociation entre lettres de
l'alphabet utilisée. Comme à chacune des lettre correspond une
autre lettre, on utilisera, pour chaque lettre, ce que l'on appelle
une structure de couple. Un couple contient deux élément
séparés par une virgule et l'on peut mettre le tout entre
parenthèses. Ainsi, l'association entre A et I
s'écrit :
# ('A','I') ;;
- : char * char = 'A', 'I'
Pour obtenir toutes les associations, on écrit un couple pour chaque
lettre et on regroupe tous ces couples dans une structure de
liste que l'on appelera clef :
# let clef =
[ ('A', 'I') ; ('B', 'J') ; ('C', 'K') ; ('D', 'L') ; ('E', 'M') ;
('F', 'N') ; ('G', 'O') ; ('H', 'P') ; ('I', 'Q') ; ('J', 'R') ;
('K', 'S') ; ('L', 'T') ; ('M', 'U') ; ('N', 'V') ; ('O', 'W') ;
('P', 'X') ; ('Q', 'Y') ; ('R', 'Z') ; ('S', 'A') ; ('T', 'B') ;
('U', 'C') ; ('V', 'D') ; ('W', 'E') ; ('X', 'F') ; ('Y', 'G') ;
('Z', 'H') ] ;;
val clef : (char * char) list =
['A', 'I'; 'B', 'J'; 'C', 'K'; 'D', 'L'; 'E', 'M'; 'F', 'N'; 'G', 'O';
'H', 'P'; 'I', 'Q'; 'J', 'R'; 'K', 'S'; 'L', 'T'; 'M', 'U'; 'N', 'V';
'O', 'W'; 'P', 'X'; 'Q', 'Y'; 'R', 'Z'; 'S', 'A'; 'T', 'B'; 'U', 'C';
'V', 'D'; 'W', 'E'; 'X', 'F'; 'Y', 'G'; 'Z', 'H']
Remarque que la réponse du système est plus paresseuse que le
programmeur puisqu'elle ne contient plus les parenthèses.
Le problème maintenant est de savoir trouver quelle lettre il faut
substituer à une lettre du message en clair. Pour cela, le langage
Objective Camlfournit une fonction prédéfinie appelée List.assoc
Ce nom en deux partie vient du fait que les fonctions sont
regroupées par thèmes dans des fichiers appelés
modules. Ainsi, il existe un module donnant des fonctions sur
les listes et il s'appelle List. La fonction de ce module qui
nous interresse s'appelle assoc, pour <<association>>.
On utilise cette fonction en lui donnant en premier argument la lettre
dont on veut la correspondante et en second argument la liste des
associations. Par exemple :
# List.assoc 'L' clef ;;
- : char = 'T'
Pour obtenir le codage d'une lettre de message, on utilise
l'écriture permettant d'accéder aux caratères d'une chaîne
en premier argument :
# List.assoc message.[0] clef;;
- : char = 'T'
On a obtenu 'T' car le caractère numéro 0 de
message est 'L'.
Le programme de codage
On a maintenant tout ce qu'il faut pour écrire le programme de
codage. On a la boucle pour examiner et modifier chacune des lettres
du message, la conditionnelle pour savoir si la lettre examinée est
un espace ou non (ici on ne veut pas remplacer les espaces, on utilise
le test de différence noté <>) et les listes d'association
pour obtenir le code de chaque lettre.
# let message = "LA CIMAISE ET LA FRACTION" ;;
# for i=0 to 24 do
if message.[i] <> ' ' then
message.[i] <- List.assoc message.[i] clef
done ;
print_string message;
print_newline() ;;
TI KQUIQAM MB TI NZIKBQWV
- : unit = ()
Programmes et fonctions
On voudrait pouvoir utiliser le programme ci-dessus pour coder autre
chose que le message LA CIMAISE ET LA FRACTION, par exemple,
LA FRACTION N EST PAS PREVISIBLE. Une solution simple est de
remplacer la première ligne du programme et de garder le
reste. Ça donne ;
# let message = "LA FRACTION N EST PAS PREVISIBLE" ;;
# for i=0 to 24 do
if message.[i] <> ' ' then
message.[i] <- List.assoc message.[i] clef
done ;
print_string message;
print_newline() ;;
TI NZIKBQWV V MAB XIA XZMVISIBLE
- : unit = ()
Le résultat obtenu n'est pas tout à fait celui escompté : les
sept derniers caratères de message n'ont pas été codés.
En effet, notre second message contient 31 caractères alors que le
premier en contenait 24. On pourrait remplacer 24 par 31 dans le
programme, mais l'on peut faire mieux. La boucle de codage commence
toujours au premier caractère et fini toujours au dernier. Si,
étant donnée une chaîne de caractères, on sait calculer le
numéro du dernier caractère, on pourra écrire une boucle qu'il
n'y aura pas besoin de modifier quand on change la valeur de
message.
Pour effectuer ce calcul, on fait appel à la fonction
String.length qui nous donne le nombre de caractères que
contient une chaîne (on dit qu'elle donne la longueur de la
chaîne). Attention, comme la numérotation commence à 0, le
numéro du dernier caractère est égal au nombre de caratères
moins un ! On obtient le programme suivant :
# let message = "LA FRACTION N EST PAS PREVISIBLE" ;;
# for i=0 to (String.length message) - 1 do
if message.[i] <> ' ' then
message.[i] <- List.assoc message.[i] clef
done ;
print_string message;
print_newline() ;;
TI NZIKBQWV V MAB XIA XZMDQAQJTM
- : unit = ()
La programmation bien comprise est une activité pour fainéants :
on ne veut pas écrire trente six fois la même chose. Et les
langages de programmation sont faits pour aller dans le sens de cette
qualité (la fainéantise :) en fournissant au programmeur la
possibilité de définir des fonctions. Ici, la seule chose
qui changera lorsque l'on voudra coder un nouveau message, sera la
valeur dudit message. Autrement dit, message est un
paramètre du programme de codage. Et on peut définir une
fonction qui prendra en paramètre (ou en argument) un message (c'est
à dire une chaîne de caractères). Voici comment :
# let code message =
for i=0 to (String.length message) - 1 do
if message.[i] <> ' ' then
message.[i] <- List.assoc message.[i] clef
done ;
print_string message;
print_newline() ;;
val code : string -> unit = <fun>
Pour obtenir le code d'un autre message, il suffit d'appliquer la
fonction ainsi définie à ce message :
# code "EH BIEN DEBAGOULEZ MAINTENANT" ;;
MP JQMV LMJIOWCTMH UIQVBMVIVB
- : unit = ()
Exercice
Comment écrire une fonction de décodage decode ? Peut-on
faire en sorte que la même fonction puisse servir à la fois au
codage et au décodage ?
Bien à toi, Pascal.
PS: j'utilise Objective Caml sous un système unix, c'est pourquoi mes
exemples se présentent sous la forme :
# "phrase tapée par le programmeur" ;;
- : type = réponse du système commençant par - ou un nom
Sous Windows, lorsque tu lances Objective Caml, tu obtiens trois
fenêtres. Les <<phrases tapées par le programmeur>> (qui sont
précédées du signe # et terminées par le double point
virgule ;;) doivent l'être (tapées) dans la
fenêtre d'entrée en bas à gauche et la << réponse du
système >> apparaîtra dans la fenêtre de gauche au-dessus.
This document was translated from LATEX by HEVEA.