Programmation Fonctionnelle et Symbolique - Notions de sémantique
-
6.a Quelques généralités
-
6.b Notion d'Environnement
-
6.c Sémantique de l'Affectation
-
6.d Sémantique de la Composition Séquentielle
-
6.e Sémantique de la Répétition
-
6.f Conclusion
6.a Quelques généralités
Terme de linguistique, la sémantique est (selon le dictionnaire Lexis),
«l'étude du sens (ou contenu) des mots et des énoncés, par opposition à
l'étude des formes (morphologie) et à celle des rapports entre les termes
dans la phrase».
A la différence des langues naturelles, les langages de programmation sont
des objets linguistiques relativement simples :
- ayant une syntaxe assez rigide (il faut qu'un programme -le compilateur-
puisse analyser une «phrase» sans trop de peine). Voici par exemple la
description de la grammaire d'un petit langage de programmation :
<programme> ::=<entête> <bloc>
<bloc>::= début <liste d'instructions> fin
<liste d'instructions>
::= rien
| <instruction> ; <liste d'instructions>
<instruction>::= <affectation>
| <bloc>
| <boucle tantque>
| <alternative>
....
<affectation>::= <variable> := <expression>
<expression>::= <constante>
| <variable>
| <expression> + <expression>
| <expression> * <expression>
....
<tantque>::= tantque <condition> faire <instruction>\/
<alternative>::= si <condition> alors <instruction> sinon <instruction>
<condition>::= <expression> < <expression>
| ....
| <condition> et <condition>
| ...
- Possédant une sémantique volontairement très pauvre (une instruction d'un
programme doit avoir un sens clairement défini).
En informatique, la sémantique est l'étude de la «signification» des
programmes. Comment définir formellement la signification d'un programme ?
C'est assez simple en fait; prenons par exemple le programme suivant :
programme m
donnée en entrée : x,y (entiers positifs)
résultat en sortie : r (entier)
début
r := 0;
tantque x>0 faire
debut
x:=x-1;
r:=r+y;
fin
fin
La signification de ce programme est tout simplement la fonction S[m]
(S pour
Sémantique) qui à deux entiers x et y fait correspondre un certain résultat r
en fin de traitement :
S[m]: N x N -> N.
S[m][n,p] = n*p
Plus généralement la signification d'un programme p est représentée par une
certaine fonction S[p] : D -> R, qui à une donnéee fait correspondre
un résultat. Cette fonction est souvent une fonction
partielle, dans le sens où le calcul de P sur certaines données peut ne pas
conduire à un résultat (le programme boucle, il y a eu une division par zéro,
etc..). Le domaine de définition de S[p] est donc naturellement l'ensemble
des données pour lesquelles le calcul se termine normalement.
Remarques :
- Il est d'usage assez courant de noter par (E -> F)
l'ensemble des fonctions
partielles qui vont d'un ensemble E dans un ensemble F.
-
Réfléchissons un peu sur le statut de S dans la notation :
«S[p] : D -> R»
S est une fonction qui associe à un programme p sa signification (qui est
elle-même une fonction qui fabrique un résultat à partir d'une donnée ).
Notons P l'ensemble des programmes, on a alors :
S : P -> (D -> R)
Il est clair que cette fonction S existe (nous venons de la définir
implicitement - par compréhension- ); le problême qui se pose est de savoir
comment on peut la construire, c'est-à-dire calculer la signification d'un
programme sans avoir besoin de le faire tourner sur toutes les données
possibles. Méditez bien ce point avant de passer à la suite...
Nota: Nous limitons ici à une classe très simple de programmes impératifs:
programmes structurés, pas d'entrées-sorties, pas de procédures.
6.b Notion d'Environnement
Le petit programme donné en exemple va nous permettre de préciser quelques
notions importantes. Tout d'abord la notion d'environnement : un
environnement c'est l'association, à un moment donné de l'exécution de ce
programme, de valeurs aux variables du programme.
Par exemple si on lance le programme pour x=2 et y=3, on a au départ
| l'environnement initial | e: x -> 2 , y -> 3
|
| puis après l'initialisation | e:x -> 2 , y -> 3 , r -> 0
|
| et ensuite (dans la boucle) | e: x -> 1 , y -> 3 , r -> 0
|
| et encore .... | e: x -> 1 , y -> 3 , r -> 3
|
| etc...
à la fin on aura | e: x -> 0 , y -> 3 , r -> 6
|
Deux choses à remarquer :
- Un environnement peut être vu comme une fonction qui part de l'ensemble Id
des identificateurs du programme (ici Id = {x,y,r}) et qui va dans l'ensemble
des V des valeurs (ici des entiers) . Soit donc E = (Id -> V) l'ensemble des
environnements.
-
Lorsqu'une instruction, (ou une séquence d'instructions) s'exécute, elle
modifie l'environnement. On peut donc décrire la signification d'une
instruction i (ou d'une séquence) par une fonction S[i] qui associe à un
environnement (celui où on est juste avant d'exécuter i) un autre
environnement (celui d'après l'exécution de i).
S[i] : E -> E
Ceci est tout à fait compatible avec la définition précédente de S !
6.c Sémantique de l'Affectation
Considérons l'instruction «r:=r+y». Nous voulons l'exécuter dans un certain
environnement e. Comment fait on ? Tout simplement on additionne les valeurs
de r et de y (prises dans l'environnement e) et on modifie la valeur de la
variable r dans e; plus exactement on crée un environnement e1 semblable à
e, sauf en ce qui concerne la valeur de r.
Nous avons besoin de définir une nouvelle fonction sémantique V
qui renvoie la valeur d'une expression (si cette valeur existe) dans
un certain
environnement. Par exemple V[r+y](e) = 3
Par induction sur la structure des expressions :
| Pour toute constante c : | V[ c ](e) = c
|
| Pour tout identificateur id : | V[ id](e) = e(id) (si défini)
|
| Pour toute somme exp+exp: | V[ exp+exp](e) = V[ exp](e)+V[ exp](e)
(si ces valeurs existent)
|
etc ...
En général, si l'on a une affectation var := expr, la fonction sémantique
S[var := expr] qui lui est associée est définie de la manière suivante :
pour tout environnement e dans E :
S[var := expr](e) =
si V[expr](e) existe
alors e1 environnement tel que:
e1(var) = V[expr](e)
e1(id) = e(id) pour tout autre identificateur id.
6.d Sémantique de la Composition Séquentielle
Lorsqu'on sait faire une instruction, on peut légitimement essayer d'en faire
deux à la suite l'une de l'autre! Interrogeons nous sur la séquence
d'instructions « x:=x-1; r:=r+y»..
Supposons que nous l'exécutions en partant de l'environnement e. Après la
première instruction on se retrouve dans l'env. e1 = S[x:=x-1](e); puis la
seconde nous fait passer dans e2 = S[r:=r+y](e1). Donc:
S[x:=x-1;r:=r+y](e) = S[r:=r+y](S[x:=x-1](e))
= (S[r:=r+y] o S[x:=x-1])(e)\^
Pour résumer, si on a deux instructions i et i :
S[i; i] = S[i] o S[i]S
Simple composition de deux fonctions...
6.e Sémantique de la Répétition
Examinons maintenant la boucle «tant que». Une telle boucle comporte deux
éléments : une condition et un corps. Nous savons, grâce à la fonction V,
calculer la valeur d'une condition (c'est une expression booléenne). Nous
savons également définir la signification du corps de la boucle. Comment
recoller les morceaux ?
Soit <boucle> l'instruction : «tantque <cond> faire <corps>»
pour exécuter <boucle> dans l'environnement e, que fait on ?
-
on évalue la condition (dans e)
-
si la condition est fausse, on s'arrête (l'environnement n'a pas changé)
- si elle est vraie, on exécute le corps (l'environnement est modifié) et on
recommence au début (avec ce nouvel environnement e1).
Ce qui s'écrit :
S[<boucle>](e) =
si V[<cond>](e)=faux alors e
si V[<cond>](e)=vrai alors S[<boucle>]( S[<corps>](e) )
Et voilà..
Exercices
- Définir la sémantique de l'alternative :
si <condition> alors <i> sinon <i>
-
Définir la sémantique de répétition :
répéter <i> jusqu'à <condition>
Utiliser cet arsenal mathématique pour démontrer que
Pour tout environnement e avec
e(x)=a et e(y)=b (a,b entiers positifs), on a :
(S[m](e))(r) = a*b
6.f Conclusion
La programmation s'apprend en général par tâtonnements, ce qui fait parfois
conclure un peu hâtivement qu'il s'agit d'un art (ou d'un artisanat, voire un
bricolage) plutôt que d'une technique. Il convenait donc de montrer que
l'édifice repose sur de robustes fondations mathématiques: composition de
fonctions et calcul par récurrence. Qu'en conclure ?
-
La notion d'environnement est fondamentale pour la compréhension de la
programmation impérative. Cette notion ne fait pas partie du bagage
mathématique usuel. D'où les réticences initiales à l'acceptation
d'instructions du type : i:=i+1, qui violent l'apparence déclarative.
-
toute tentative de compréhension -et d'explication- d'un programme non
trivial (comportant par exemple une boucle) utilise nécessairement le
raisonnement par récurrence, sous une forme plus ou moins apparente. C'est
donc une technique qu'il convient de maîtriser.
-
Ceci justifie l'apprentissage de la programmation fonctionnelle, à la
fois comme langage de programmation familiarisant le programmeur avec
le raisonnement explicite par récurrence, et comme formalisme
descriptif/explicatif de la programmation impérative.
M. BILLAUD Département Informatique IUT-A Bordeaux (1989)