24
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

Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

Embed Size (px)

Citation preview

Page 1: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 2: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 3: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 4: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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 )

Page 5: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 6: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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)

Page 7: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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)

Page 8: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 9: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 10: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 11: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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 !

Page 12: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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.

Page 13: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 14: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 15: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 16: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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)

Page 17: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 18: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

Exemples

res,val:=TRUE,f(x)

homme,sexe:=,

courant,ancien:=suiv(actuel),courant

x,y:=y,x

x:=y || y:=x+1

Page 19: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 20: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 21: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 22: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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 !!!

Page 23: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

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

Page 24: Modélisation des opérations Spécifier les transformations détat que lon attend des services de la machine Létat dune machine entièrement déterminée par

Retour sur reserver

statut <-- reserver(nbPlace) =PRE

nbPlace NATURALTHEN

IFnbPlace nbPlaceLibre

THENnbPlaceLibre :=nbPlaceLibre – nbPlace ||statut:=TRUE

ELSEstatut := FALSE

ENDEND