|
|
|
La description d'un langage, fût-il de programmation, peut difficilement se faire
sans l'aide d'une notation grammaticale, comme celle utilisée au chapitre 2
page ![[*]](http://www.pasteur.fr/recherche/unites/sis/Intro_Programmation/cross_ref_motif.gif)
,
![$[\mathcal{F}]$](http://www.pasteur.fr/recherche/unites/sis/Intro_Programmation/img24.gif){kind=small}
.
Il nous faudra en effet décrire les formes du langage que nous sommes en train de définir (le langage spécifié, par exemple ici Scheme). Pour cela il nous faudra mélanger des fragments de texte écrits dans le langage spécifié (par exemple des formes déjà introduites, ou celles que nous voulons introduire) et des fragments écrits dans le langage de spécification, et il faudra que la différence entre les deux apparaisse clairement.
Nous nous contenterons provisoirement d'une notation très simple qui permet de spécifier la façon de construire une forme du langage en mêlant dans la spécification des éléments du langage spécifié, destinés à être reproduits tels quels dans la forme spécifiée (on les appelle les éléments terminaux du langage), et des entités décrites dans le langage de spécification, qui pourra souvent être le français agrémenté de notations que nous allons introduire (ce seront des non-terminaux, qui servent à nommer les constructions intermédiaires).
Reprenons l'exemple du chapitre 2
page
:
Les parenthèses et le mot if sont des terminaux (des éléments du langage spécifié Scheme), ils sont écrits en caractères romains et doivent être reproduits tels quels.
Le nom du prédicat condition est un non-terminal (un élément du langage de spécification) qui décrit une entité en cours de spécification, destinée à être remplacée par le nom du vrai prédicat lors de l'écriture du programme. Il est écrit en caractères italiques.
Les locutions <expression si vrai> et <expression si faux> sont aussi des non-terminaux, mais comme ils sont constitués de plusieurs mots ils sont entourés de signes < et >. Tout ce qui est placé entre < et > représente la description d'une seule entité du langage spécifié, qui viendra en prendre la place lors de l'écriture du programme.
La locution <expression si faux> est de surcroît entre crochets, ce qui signifie qu'elle est facultative.
On écrira ainsi la règle de construction, appelée aussi production :
< forme if >::= (if <condition>
<expression
si vrai>
[<expression si
faux>])
où ce qui est à gauche du signe ::= désigne l'entité non-terminale que nous sommes en train de spécifier et ce qui est à droite la spécification.
Reprenons l'exemple ![$[\mathcal{AA}]$](http://www.pasteur.fr/recherche/unites/sis/Intro_Programmation/img11.gif){kind=small}
de la page
:
(S-expression ... S-expression)
Le sens des ... est intuitif : il y a plusieurs S-expressions possibles à cet endroit. Mais on aimerait mieux une notation plus précise. La voici :
(S-expression {S-expression}*)
ce qui s'interprète : tout ce qui est compris entre accolades { et } sera présent 0 ou plusieurs fois. Le nom familier de cette notation * est l'opérateur de Kleene, qui dénote la fermeture de Kleene.
L'opérateur de Kleene, les « crochets pointus » < et > et des opérateurs analogues omis ici permettraient de se passer des accolades et des crochets carrés. Nous les introduisons ici parce qu'ils apparaissent fréquemment dans la littérature et qu'ils ne risquent pas d'introduire de confusion syntaxique avec des éléments de Scheme (ils ne sont actuellement pas utilisés par Scheme, mais réservés pour un usage futur éventuel).
Il est possible enfin de définir des éléments alternatifs, entre lesquels le programmeur devra choisir :
S-expression ::= nombre
| caractère
| <chaîne
de caractères>
| booléen
| symbole
| (S-expression
{S-expression}*)
Une S-expression est soit un nombre, soit un caractère, soit etc.
Ces éléments grammaticaux seront développés ultérieurement de façon à construire des systèmes de définition vraiment rigoureux. La réalisation de traducteurs de langages (compilateurs et interprètes) nécessite des grammaires assez puissantes pour décrire sans équivoque toute construction du langage.
En formant les expressions que nous avons vues jusqu'à présent nous avons défini et utilisé des données. Une variable dotée d'un nom est une donnée, mais une constante donnée de façon immédiate sous la forme d'une expression auto-évaluante aussi.
Toutes les données ne se ressemblent pas : nous soupçonnons qu'entre un nombre et une chaîne de caractères il y a beaucoup de différences, et que l'opération d'addition s'applique mieux à celui-là qu'à celle-ci. Nous dirons que ce sont des données de types différents.
Cette notion de type a pour utilité la plus terre à terre de permettre d'éviter des confusions, comme d'additionner un nombre et une chaîne de caractères. Le typage consiste à ranger les données selon des types convenables, de façon à ce que le programme dispose de ces informations de type pour vérifier la pertinence des opérations avant de les entreprendre. On dit que le typage introduit de la sûreté dans la programmation.
Lorsque l'on sait que dans les langages anciens, dépourvus d'une notion claire de type, 90% des erreurs de programmation étaient provoquées par des ambiguïtés de type, par des redéfinitions d'un même objet avec plusieurs types différents, on mesure l'intérêt du typage.
La notion de type peut être apparentée à celle de structure algébrique, comme les groupes, les anneaux et les corps. Ainsi, un type de données sera défini par deux caractéristiques :
Par exemple, un langage de programmation pourra admettre le type « entier », dont le domaine de définition sera un sous-ensemble fini de l'ensemble des nombres entiers et qui sera doté des opérations arithmétiques usuelles telles que l'addition, la soustraction, la multiplication, la division entière, les relations « inférieur à », « supérieur à », etc.
Nous pouvons définir par la méthode ci-dessus des types élémentaires, dits aussi scalaires, comme les nombres ou les caractères. À partir de ces types de base nous pouvons définir des types construits, ou types structurés ; ainsi les chaînes de caractères constituent un type construit à partir du type de base caractère. Nous verrons d'autres types construits.
En fait, la plupart des langages de programmation utilisent une synthèse plus ou moins explicite de ces deux définitions. Les types les plus élémentaires sont introduits algébriquement, et à partir d'eux on construit ce que l'on appelle des types abstraits de données (abstract data types, ADT), c'est à dire des types complexes définis de manière constructive par les procédures qui peuvent créer des objets du type, y accéder et les modifier.
Certains langages imposent ou autorisent la déclaration explicite du type des variables lors de leur création. Généralement, une fois qu'une variable s'est vu attribuer un type, elle ne peut pas en changer : on parle de typage statique.
D'autres un peu démodés n'ont pas une notion claire de type.
Scheme, à l'instar de tous les Lisp, se distingue de ces deux écoles en pratiquant le typage dynamique : un même nom de variable peut à des instants successifs dans le déroulement du programme désigner des objets de types différents, comme un nombre et une chaîne de caractères (nous savons déjà qu'une redéfinition peut produire ce résultat, mais les chapitres 7 et 8 introduiront de nouvelles tournures propres à causer cette situation). Cela ne signifie pas qu'il n'y a pas de typage, mais il est dynamique.
Le typage dynamique a une conséquence importante : avec un langage à typage statique, la détection des erreurs de type évoquées en 4.2.1 peut se faire à l'examen du texte du programme, lors de sa traduction par l'interprète ou le compilateur.
En Scheme, comme à tout instant une variable peut changer de type, il faut pouvoir à tout instant s'en enquérir. Cette détection ne peut avoir lieu qu'à l'exécution, c'est à l'auteur du programme de vérifier au moyen de prédicats de type que les deux expressions qu'il s'apprête à additionner s'évaluent bien en nombres, par exemple.
Voici des exemples de prédicats de type et de leur usage :
1:=> (define a 4)
A
1:=> (number? a)
#t
1:=> (define a #\Z)
*** WARNING:bigloo:eval
redefinition of variable - A
A
1:=> (number? a)
#f
1:=> (char? a)
#t
Scheme connaît neuf types fondamentaux (que nous ne connaissons pas encore tous) caractérisés par des prédicats de type :
| boolean? | pair? | symbol? |
| number? | char? | string? |
| vector? | procedure? | port? |
La norme [CKR98] stipule qu'aucun objet ne peut satisfaire à plus d'un de ces prédicats. Cette règle assure ce que l'on appelle la « disjonction des types ». Pour des raisons qui s'éclaireront bientôt, le prédicat pair? est celui satisfait par les listes.
Du point de vue mathématique, les nombres sont classés en une série d'ensembles, infinis, inclus les uns les autres :
{entiers relatifs}
{rationnels}
{réels}
{complexes}
Du point de vue de l'architecture des ordinateurs, deux sortes de représentations en machine4.1peuvent être utilisées pour représenter les nombres :
Le processeur de l'ordinateur comporte des circuits aptes à effectuer les opérations arithmétiques portant sur des données représentées d'une de ces façons.
Pour le langage Scheme tel que défini par [CKR98], les nombres sont de deux sortes : exacts ou inexacts.
Les différents interprètes et compilateurs Scheme utilisent les différentes représentations en machine pour modéliser les différents types de nombres au sens mathématique, et ce de façon assez diverse. La leçon à retenir de ceci est que nous ne rencontrerons pas de difficulté numérique tant que nous utiliserons l'addition, la soustraction et la multiplication avec des nombres entiers compris dans l'intervalle autorisé par le système de programmation ou l'architecture matérielle4.2 (si nous ne le connaissons pas, le supposer égal à [-229, +229-1] est prudent). Le système Bigloo utilisé sur ordinateur Digital autorise [-260, +260-1]. Au-delà de ces limites, il conviendra de se poser des questions de précision des calculs, ce qui sera abordé dans un autre cours.
La version de Scheme que nous utiliserons principalement, Bigloo, utilise la représentation en virgule fixe pour représenter les nombres entiers et les considère comme exacts, et la représentation en virgule flottante pour représenter les nombres « avec des chiffres après la virgule », considérés comme inexacts. Ce choix peut être considéré comme raisonnable parce qu'il se conforme aux caractéristiques de l'architecture matérielle, ce qui autorise de bonnes performances.
Comme signalé plus haut, les entiers, sur architecture Digital Alpha, sont sur [-260, +260-1]. Bigloo utilise trois chiffres binaires de tag sur les machines à architecture 64 bits, et deux sur les machines à architecture 32 bits.
Voici les principales procédures disponibles dans Bigloo pour traiter les nombres (pour la liste complète voir [Ser98]) :
| (number? obj) | |
| (integer? obj) | (real? obj) |
| (exact? obj) | (inexact? obj) |
| (fixnum? obj) | (flonum? obj) |
| (zero? obj) | |
| (positive? obj) | (negative? obj) |
| (even? obj) | (odd? obj) |
| Procédure | Arithmérique | Arithmétique virgule |
| standard | entière de Bigloo | flottante de Bigloo |
| (= z1 z2...) | (=fx n1 n2) | (=fl x1 x2) |
| (<= z1 z2...) | (<=fx n1 n2) | (<=fl x1 x2) |
| (< z1 z2...) | (<fx n1 n2) | (<fl x1 x2) |
| (+ z1 ...) | (+fx n1 n2) | (+fl x1 x2) |
| (* z1 ...) | (*fx n1 n2) | (*fl x1 x2) |
| (/ z1 z2) | (/fx n1 n2) | (/fl x1 x2) |
| (abs x) | (quotient n1 n2) | (remainder n1 n2) |
| (modulo n1 n2) | (gcd n1 ...) | (lcm n1 ...) |
| (floor x) | (ceiling x) | (truncate x) |
| (exp x) | (log x) | (sqrt x) |
| (sin x) | (cos x) | (tan x) |
| (asin x) | (acos x) | (atan x) |
| (expt z1 z2) |
| (exact->inexact z) | (inexact->exact z) |
| (number->string x) | (integer->string n) |
| (string->number string) | (real->string z) |
La notion d'égalité, en informatique comme en mathématiques, est loin d'être simple. Nous avons déjà utilisé le prédicat = qui s'applique aux nombres :
: (= 1 2)
#f
En toute rigueur ce prédicat ne devrait s'appliquer qu'aux nombres entiers, qui seuls sont décrits exactement par les dispositifs matériels de l'ordinateur, alors que les nombres fractionnaires sont décrits de façon approchée. Une comparaison entre nombres fractionnaires devrait (doit) s'écrire ainsi :
: (define *epsilon* 1.e-7)
: (define (assez-proches? u v)
(< (abs (- u v)) *epsilon*))
: (assez-proches? 1. 1.5)
#f
: (assez-proches? 1.00000001 1.)
#t
où le prédicat assez-proches? se substitue à =, abusif. Attention néanmoins : assez-proches? n'est pas pourvu des propriétés habituelles de =, et notamment ne définit pas une relation transitive. La valeur choisie pour *epsilon* dépend du problème traité. En bref ceci est un conseil de programmation, pas une règle universelle.
Les objets booléens standard sont #t et #f, le prédicat (boolean? obj) et la procédure not s'y appliquent. La liste vide est vraie.
| (symbol? obj) | (symbol->string symbol) |
| (string->symbol string) | |
Les symboles sont insensibles à la casse :
(eq? 'toto 'TOTO) 
#t
Signalons la procédure Bigloo non-standard gensym41 qui retourne un nouveau symbole garanti unique. Les symboles que l'on peut donner simplement, par exemple, en les tapant à l'invite de l'interprète obéissent aux règles syntaxiques des identifiants, mais string->symbol permet de construire des symboles à partir de chaînes quelconques.
| (char? obj) | (char-alphabetic? char) |
| (char-numeric? char) | (char-whitespace? char) |
| (char-upper-case? char) | (char-lower-case? char) |
Pour transformer et convertir :
| (char-upcase char) | (char-downcase char) |
| (char->integer char) | (integer->char n) |
Les types de données scalaires possèdent des prédicats de comparaison spécialisés qu'il est conseillé d'utiliser chaque fois que c'est possible à la place des prédicats généraux parce que cela facilite le travail du lecteur du programme, qu'il soit un humain ou un programme. Ainsi pour les caractères :
| (char=? char1 char2) | |
| (char<? char1 char2) | (char>? char1 char2) |
| (char<=? char1 char2) | (char>=? char1 char2) |
Ces prédicats comparent les caractères en distinguant les lettres majuscules des
minuscules. Il existe un jeu de prédicats pour faire des comparaisons insensibles à la
casse (pour lesquels #\a = #\A) :
| (char-ci=? char1 char2) | |
| (char-ci<? char1 char2) | (char-ci>? char1 char2) |
| (char-ci<=? char1 char2) | (char-ci>=? char1 char2) |
(string? obj)
Les chaînes de caractères disposent de prédicats de comparaison analogues à ceux décrits pour les caractères en 4.2.6 :
| (string=? string1 string2) | |
| (string<? string1 string2) | (string>? string1 string2) |
| (string<=? string1 string2) | (string>=? string1 string2) |
| (string-ci=? string1 string2) | |
| (string-ci<? string1 string2) | (string-ci>? string1 string2) |
| (string-ci<=? string1 string2) | (string-ci>=? string1 string2) |
on doit avoir :
0 
start
end
(string-length string)
substring retourne une nouvelle chaîne formée des caractères de string commençant à l'indice start (inclus) et se terminant à l'indice end (exclus), toujours avec l'indice 0 pour le premier caractère.
On notera que si start = end la chaîne retournée sera la chaîne nulle et que si start = 0 et end = (string-length string) la sous-chaîne retournée sera équivalente à string.
retourne une nouvelle chaîne formée des caractères de string1 suivis des caractères des chaînes suivantes.
|
|
|