Upload
eneas-martel
View
107
Download
2
Embed Size (px)
Citation preview
Modélisation des opérations
Spécifier les transformations d’état que l’on attend des services de la machine L’état d’une machine entièrement déterminée par la valeur
de ses variables Langage pour exprimer les propriétés des nouvelles
valeurs des variables en fonction de leurs anciennes valeurs et d’éventuels paramètres (le quoi pas le comment)
Le langage proposé = Substitutions généralisés Dispose de constructions proches de l’affectation et des
conditionnelles Absences de séquences et boucles Constructions adaptées à la spécification : pré-condition,
substitution multiple, substitutions indéterministes
Spécifier les changements d’états
Utiliser des prédicats Pre-Post Convention une variable prime indique la valeur
d’une variable après l’opération Exemple
x’ = x +1 Dans le nouvel état la variable x a sa valeur
incrémentée de 1 par rapport à sa valeur dans l’ancien état
x’ > x Dans le nouvel état la valeur de la variable x n’est pas
connue mais elle sera supérieure à la valeur précédente
Exemple : Système de réservation à capacité infinie
MACHINEReservation
VARIABLESnbPlaceLibre
INVARIANTnbPlaceLibreNATURAL
OPERATIONSreserver = … /* réserve une place */ ;annuler = … /* annule la réservation d’une place */
ENDnbPlaceLibre’ = nbPlaceLibre + 1
Obligation de preuve
Une opération doit respecter les lois statiques du systèmeSi : la valeur des variables avant l’opération respecte l’invariant Alors : quelque soit les nouvelles valeurs prises par les variables
parmi les valeurs caractérisées par le prédicat Pre-PostForcément : ces nouvelles valeurs des variables respectent
l’invariant.
Inv(v) => v’.(PrePost(v,v’) => Inv(v’)) Exemple de annuler : nbPlaceLibreNATURAL => nbPlaceLibre’. ( nbPlaceLibre’=nbPlaceLibre+1
=> nbPlaceLibre’NATURAL )
Introduction des substitutions
Objectif : simplifier l’expression des opérations et la démonstration des preuves
Rappel : une substitution est une application des variables dans des expressions {x’|->x+1, y|->y+1, z|->w, v|->x+y}
En B on considère des substitutions simples portant sur une unique variable {x|->e} que l’on note x:=e
L’application d’une substitution (simple) à une formule F consiste à remplacer dans la formule F toutes les occurrences d’une variable libre x par une expression. On note [x:=e]F
Exemple : [x:=x+1](x N) donne x+1 N
Remplacement des Pre-Post par des substitutions
Théorème d’équivalence entre substitution et prédicat Pre-Post fonctionnel
x. (x=e => F) <=> [x:=e]F si x n’a pas d’occurrence libre dans e
Application à l’exemple précédentnbPlaceLibre NATURAL => nbPlaceLibre’. ( nbPlaceLibre’=nbPlaceLibre+1
=> nbPlaceLibre’NATURAL )
nbPlaceLibre NATURAL => [nbPlaceLibre’ := nbPlaceLibre + 1] (nbPlaceLibre’ NATURAL)
Simplification
Suppression des variables primeInv(v’) <=> [v:=v’]Inv(v)
Sur l’exemple : nbPlaceLibre NATURAL
=> [nbPlaceLibre’:=nbPlaceLibre+1] [nbPlaceLibre:=nbPlaceLibre’](nbPlaceLibreNATURAL)
Donc par composition :nbPlaceLibre NATURAL
=> [nbPlaceLibre:=nbPlaceLibre+1](nbPlaceLibreNATURAL)
Spécification des transformation fonctionnelle
Toute transformation fonctionnelle d’une variable peut donc être modélisée par une substitution simple [S] de type [x:=e] et engendrera l’obligation de preuve :
I => [S]I
Avantage : simplification des preuves Pas de nouvelles variables Pas de quantificateur
L’opération annuler sera donc modélisée :
annuler = BEGIN nbPlaceLibre := nbPlaceLibre + 1 END
Le langage des substitutions généralisées
Objectif : étendre la modélisation des transformations par des substitutions pour : Permettre l’expression de pré-condition Permettre les substitutions multiples Permettre l’expression de conditionnelles Permettre les substitutions
indéterministes
La substitution précondition
Objectif : spécifier des opérations « pas toujours utilisable » Exemple : reserver =
BEGIN nbPlaceLibre := nbPlaceLibre - 1 END
Obligation associée nbPlaceLibre NATURAL
=> [nbPlaceLibre:=nbPlaceLibre-1] nbPlaceLibre NATURAL qui donne nbPlaceLibre NATURAL => nbPlaceLibre-1 NATURAL non valide (cas où nbPlaceLibre=0).
L’opération réserver n’est utilisable que si il y a encore des places libres à réserver
La substitution précondition
Exprimer la précondition[P|S], ou PRE P THEN S END
Exemplereserver =
PREnbPlaceLibre 0
THENnbPlaceLibre := nbPlaceLibre - 1
END Intuitivement cela signifie que
La transformation S n’est opérationnelle que si la condition P est remplie
Sinon la machine peut se retrouver dans un état quelconque (ne respectant pas l’invariant).
Ce n’est pas un si P alors S finsi !
La substitution pré-condition
Interprétation de la précondition
[P|S]F P [S]F L’obligation de preuve des opérations pré-
conditionnées doit tenir compte du fait que l’on ne veut prouver la préservation d’invariant que sous-condition de la précondition P
I P => P [S]I I P => [S]I Sur l’exemple :
nbPlaceLibre NATURAL nbPlaceLibre0
=> nbPlaceLibre-1 NATURAL.
Les initialisations
L’INITIALISATION fixe l’état (éventuellement indéterministe) initial
Elle est modélisée par une substitution Qui ne dépend pas de valeurs préexistantes des
variables Uniquement les SETS, CONSTANTS, paramètres de la
machine Ne peut pas faire l’objet de pré-condition (ni de
conditionnelles) Uniquement les substitution simples, multiples, indéterministes
L’obligation de preuve associée est simplement :[S]I
Opérations avec paramètres
Paramètres d’entrée nécessitent l’utilisation d’une substitution pré-condition Au minimum typer ces paramètres.
Paramètres de sortie imposent de définir à l’aide d’une substitution simple la valeur (éventuellement indéterministe) du paramètre en sortie d’opération Cette valeur ne donne pas lieu à vérification lors
des obligations de preuve liées à la cohérence interne de la machine
Mais utile pour les contrôles des appels de service
Opérations avec paramètres
MACHINE A MACHINE B MACHINE C … … … s<--opX = opY(e) = opZ = BEGIN PRE BEGIN … P … s := Exp THEN v <-- A.opX ; … … B.opY(v) ; END END …
END
IA => [s :=Exp] [v :=s] [e :=v] P
Spécification défensive
statut <-- reserver(nbPlace) =PRE
nbPlace NATURALTHEN
IFnbPlace nbPlaceLibre
THENstatut, nbPlaceLibre :=TRUE, nbPlaceLibre –
nbPlaceELSE
statut := FALSEEND
END
substitution multiple et conditionnelle (choix borné et garde)
La substitution multiple
Objectif : modifier simultanément plusieurs variables
x,y:=Ex,Ey Sémantique :
[x,y:=Ex,Ey] F [z:=Ey][x:=Ex][y:=z] Foù z est une nouvelle variable n’apparaissant ni dans F, ni dans Ex
Notation équivalente :x:=Ex || y:=Ey x,y:=Ex,Ey
Exemples
res,val:=TRUE,f(x)
homme,sexe:=,
courant,ancien:=suiv(actuel),courant
x,y:=y,x
x:=y || y:=x+1
Le choix borné
Objectif : Spécifier que l’implémentation pourra au choix réaliser S ou T ou … Substitution indéterminisme
S [] T CHOICE S OR …OR T END (en ASCII)
Sémantique
[S[]T]F [S]F [T]F
Exemple : inscription dans registre état civil
res<--declarer(p,s)=PRE
pPERSONNE-personne sSEXETHEN
CHOICEpersonne := personne {p} ||sexe(p) := s ||res := ok
ORres := impossible
ENDEND
Tient compte d’impossibilités non encore connues, mais qui pourront exister dans l’implantation
La garde
Objectif : Introduire une notion de faisabilité d’une substitution Cas où une substitution S ne peut être réalisée
que sous une certaine hypothèse P qui « garde » la substitution
P==>SSELECT P THEN S END
Sémantique
[P==>S]F P => [S]F
Garde vs. Pré-condition
Pré-condition P|S On ne se pose le problème d’établir la propriété d’un état
POST que si on a auparavant prouvé que l’état PRE respectait P (lors de l’appel à l’opération)
S’il ne le respecte pas, la substitution échoue elle ne permet pas d’atteindre un état POST (si on force l’exécution d’une telle substitution, on sort du fonctionnement normal du service)
Garde P==>S On fait l’hypothèse de P pour établir la propriété de l’état
POST Si P n’est pas vérifié, la substitution permet d’établir
n’importe quelle propriété pour l’état POST On dira qu’elle est « infaisable ». Une telle substitution
n’est pas implantable !!!
Garde et Choix Borné = IF
Une garde traduit bien l’idée de la partie ALORS d’une alternative qui n’est réalisée que sous la condition du SI En combinant 2 gardes avec un choix borné, on peut donc
spécifier le fonctionnement d’un SiAlorsSinon
IF P THEN S ELSE T END
On dispose aussi d’une forme particulière de IF introduite par l’opérateur bool
x:=bool(P)
P==>S [] P==>T
IF P THEN x :=TRUE ELSE x :=FALSE END
Retour sur reserver
statut <-- reserver(nbPlace) =PRE
nbPlace NATURALTHEN
IFnbPlace nbPlaceLibre
THENnbPlaceLibre :=nbPlaceLibre – nbPlace ||statut:=TRUE
ELSEstatut := FALSE
ENDEND