Modélisation des opérations Spécifier les transformations détat que lon attend des services de...

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