Cours PLURITAL 2013-2014

Supplément au Cours n° 3 (22 octobre 2013) : Note sur la "sémantique des chaînes"

Jean-François Perrot

1. Problème de représentation en mémoire
2. Interprétation : octets ou caractères ?
3. Diversité linguistique

1. Problème de représentation en mémoire
   

   La notion commune de chaîne de caractères (alias string) pose à la technique informatique un délicat problème de représentation en mémoire.
   En effet, la notion même de chaîne comporte l'idée d'une longueur arbitraire, il n'est donc pas question de la loger dans un format fixe.
   
   Les nombres, au contraire, supportent très bien qu'on limite leur taille :
   
   • comme la place requise pour leur représentation croît de manière logarithmique par rapport à leur valeur,
   • on peut faire beaucoup de choses utiles en logeant chaque nombre dans un mot-mémoire de 32 bits (a fortiori, de 64 bits !)
   • et ce n'est que récemment qu'on s'est préoccupé de manipuler des entiers de taille quelconque (les bignums)
     
   
   La représentation des chaînes en machine demande donc d'allouer de la mémoire, ce qui entraîne une kyrielle de difficultés que les différents langages de programmation résolvent chacun à sa manière.
   La diversité des solutions se répercute directement dans l'appareillage mis en place par chaque langage pour manipuler les chaînes.
   
   
   • en C, il n'y a pas de type spécifique, une chaîne apparaît comme un pointeur sur son premier caractère ;
     char *s
     le parcours de la chaîne se fait, à travers la notation indicée s[...], par incrémentation du pointeur
     et la fin de la chaîne est marquée par l'octet 0.
     
     
   • en C++, les chaînes sont des instances de la classe string ;
     accès aux caractères individuels par la notation s[...].
     
     
   • en Perl, elles constituent un type scalaire de base, sans accès direct aux caractères individuels
     (les expressions régulières sont là pour ça)
     
     
   • en PHP,  également type scalaire de base, accès direct aux caractères individuels par la notation s[...].
     
     
   • en Java, elles sont instances de la classe (très spéciale) java.lang.String,
     accès direct aux caractères individuels par la fonction (méthode) charAt(...).
     
   
   

2. Interprétation : octets ou caractères ?

   Puisqu'on parle de chaînes de caractères, c'est que les composants élémentaires des chaînes sont des caractères !
   Mais justement, qu'est-ce qu'un caractère ?
   En fait, la structure sous-jacente est celle d'une séquence d'octets (en laissant de côté les complications liées à l'allocation de la mémoire, plus ou moins fragmentée), et tout va bien si on admet l'équation caractère = octet.
   
   Les choses se compliquent avec l'arrivée des jeux de caractères multi-octets, au premier rang desquels Unicode.
   Un choix de nature "politique" se présente :
   
   • la longueur d'une chaîne (length() ou string-length(), ou strlen(), suivant les langages) est-elle le nombre des octets qui la composent, ou bien celui de ses caractères (p.ex. chinois) ?
     
   • l'accès par la notation indicée s[k] (ou par charAt(k)) conduit-il au k-ième octet ou au k-ième caractère (chinois) ?
     
     
   C'est de ce choix qu'il est question quand on parle de sémantique des chaînes (alias string semantics).
   Les différents langages suivent des politiques différentes...
   
   

3. Diversité linguistique

   • En C, seuls existent les octets (sous la forme du type char, c'est-à-dire une donnée codée sur un octet, interprétée comme un entier signé).
     
     
   • En C++, fluctuat nec mergitur. Je cite un courrier de M.-A. Moreaux :
     

     Les string de type « string » sont des chaînes d'éléments de type « char » [...]
     On le voit bien si l'on utilise les différentes "sortes" de caractères de c++11 (la norme publiée en août 2011).
     Dans c++11, on peut déclarer des « wstring » qui sont alors des chaînes de « wchar_t »,
     « wchar_t » étant maintenant un type (et pas comme précédemment défini par une macro).
     Le nombre d'octets occupé par un « wchar_t » n'est pas défini dans le langage, mais par le compilateur.
     On peut fixer le nombre d'octets dans « wide character » par les nouveaux types char16_t et char32_t
     et déclarer des « u16string » et des « u32string », où length = nb d'éléments du type de car. déclaré.

     Exemple.
     
     
   • En Perl, autre forme de fluctuation.
     Initialement, les chaînes de Perl étaient des chaînes d'octets, interprétés comme des caractères sur la base du codage Latin-1.
     Ensuite, Perl s'est converti à Unicode, et désormais les chaînes sont des chaînes de caractères codée en UTF-8.
     L'histoire a laissé de multiples traces, comme les pragma use byte, use utf8, etc, ainsi que la spécification de l'encodage dans les entrées-sorties.
     
     
   • En PHP5, comme en Perl autrefois, les chaînes sont des chaînes d'octets, interprétés comme des caractères sur la base du codage Latin-1.
     Une bibliothèque supplémentaire mbstring permet de manipuler des chaînes avec des encodages multi-octets (en passant l'encodage en paramètre).
     Par exemple mb_strlen($chn, 'UTF-8') donnera la longueur de $chn supposée contenir de l'UTF-8.
     
     
   • En Java, la distinction est bien nette entre la classe String (chaînes de char) et la notion de tableau d'octets byte array (byte[]).
     La fonction d'accès charAt() de la classe String renvoie un char, et length() donne la longueur en char.
     Le type de base char est fondé explicitement sur le plan de base du catalogue Unicode (n°s sur 16 bits).
     Les questions de codage des caractères sont renvoyées aux opérations d'entrées-sorties.
     
     
   • Un peu d'histoire : Unicode apparaît en 1991, Java en 1994.
     En ce temps-là Unicode se contentait de 16 bits (ce n'est qu'en 1996, avec Unicode v. 2, que cette barrière sera franchie).
     Dès sa naissance, Java a adopté Unicode comme base de son type char, en spécifiant que ce type occuperait 16 bits, et n'a pas changé depuis, malgré l'évolution d'Unicode.
     Cette histoire met en lumière la contradiction entre l'ouverture réclamée par les applications (Unicode) et la stabilité exigée par la technique (Java). Passer d'un octet à deux octets a représenté un grand pas pour l'humanité...
     Un coup d'œil aux autres langages montre combien l'aggiornamento leur est difficile !