Spécification de programmes et de systèmes A. Introduction B. Spécification de programmes Introduction Opérationnelle ( Calculatoire ) Dénotationelle (

Spécification de programmes et de systèmes

A. Introduction B. Spécification de programmes Introduction Opérationnelle ( Calculatoire ) Dénotationelle ( Relationnelle ) C. Spécification de systèmes Introduction Idées générales Usage Qualités Orientation Spécification algébrique Spécification relationnelle Spécification Z


� Introduction

• Spécifier un problème c'est le définir de manière la plus rigoureuse possible.

• Le langage naturel était d'abord le seul mode de spécification.

• Son Ambiguïté et son manque de précision a conduit à définir des langages mieux adaptés.


� Introduction

• Parallèlement on a cherché à fonder le processus de spécification sur des bases rigoureuses et donc on proposait des théories.

• Les premières tentatives de spécifications rigoureuses ont porté sur les langages de programmation. Ce sont les outils de base de la construction de logiciel et toute définition de la validité d'un programme nécessite une définition de la sémantique du langage.

• Actuellement, les spécifications ont une vue et une approche tout à fait opposée à celle des langages de programmation : On désire à partir du cahier de charges définir les programmes de manière automatique

Spécification de programmes

� Introduction

• Définir de façon plus précise la sémantique des programmes grâce à des outils formels pour la description de la sémantique des langages de programmation.

• L'objectif est bien entendu l'écriture automatique de compilateur.


� Introduction

• La spécification d'un langage de programmation a été abordée par 2 voies :• a) opérationnelle : revient à spécifier une machine abstraite qui interprète le

programme. . Interprétative . Calculatoire

• b) dénotationnelle : exprime les constructions d'un langage au moyen d ’outils mathématiques. Le programme est ainsi une composition de fonctions.

. Fonctionnelle . Axiomatique . Relationnelle


� Sémantique interprétative

• Utilise aussi le concept de structure d'informations pour formaliser la notion d'état mémoire.

• Décrire ponctuellement l'action du programme(pas à pas),


• Sémantique calculatoire : définition

• Cette méthode utilise aussi le concept de structure d'informations pour formaliser la notion d'état mémoire.

• Décrire le programme plus globalement en construisant l'ensemble des calculs qu'ils lui soit associés.

• Cet ensemble est donc la valeur sémantique du programme considéré.

• Un calcul est défini comme une suite de modifications élémentaires de la SI associé au langage.


• Sémantique calculatoire : Exemple

à la portion de programme

début var x ; debut cst y = x+1; x := x+2

est associé le calcul

declvar(x).declcst(y,eval(x+1)).affect(x,eval(x+2))


• Sémantique calculatoire : Notion de calcul et ensemble de calculs

• Soit M un ensemble de modifications élémentaires de la SI du langage. Par exemple M = { declvar, declcst, eval, affect...}

• Un calcul est une suite fini ou non d'éléments de M. C'est donc un élément de l'ensemble M* ( monoïde, fermeture transitive). Ce dernier désigne l'ensemble de tous les calculs possibles.

• Posons Minfini = M* U Mw

• Avec Mw l'ensemble des calculs infinis.


• Sémantique calculatoire : Notion de calcul et ensemble de calculs

• Tout calcul fini C = µ1.µ2.....µn peut être interprété comme une modification µn o un-1 o .... µ1. de SI en interprétant la concaténation comme la composition des modifications élémentaires.

• Si la concaténation permet d'exprimer l'exécution des phrases séquentielles, il faut trouver des solutions pour l'exécution des phrases conditionnelles et itératives.

• A ces dernières on associe un ensemble de calculs.


• Sémantique calculatoire :

A l'instruction

Si x>=0 alors y := x sinon y := -x fsi

est associe l'ensemble des calculs

{Ega(Eval(x>=0), vrai).Affect(y, x)} U

{Diff(Eval(x>=0), faux).Affect(y, -x) }

Avec

Ega(u, v) (e) = e si u=v dans l'état e, w sinon

Diff(u, v) (e) = e si u<>v dans l'état e, w sinon

w est un état mémoire particulier (état infini) caractérisé par le fait que m(w) = w pour tout m dans M.


• Tous les calculs sont construits à partir de modifications élémentaires par application de deux lois de composition interne dans P(Minfini).

— . Concaténation

— U Union ensembliste.


� Système de calcul associé à une phrase• L'ensemble des calculs associé à une phrase composée dépend des

ensembles de calculs qui sont associés aux phrases qui la composent. Il peut donc être défini par un système d'égalité.

• Exemple 1 : Si P est " Si exp alors P1 sinon P2 fsi " Posons P^ l'ensemble des calculs associés à P A(P) : système de calcul associé à P. A(P) = P^ = Ega(Eval(exp, vrai).P1^ U Ega(Eval(exp, faux).P2^ A(P1) A(P2)


� Système de calcul associé à une phrase

• Le système de calculs associé à P est formé :

- d'une part de l'équation liant l'inconnu P^ aux inconnu P1^ et P2^.

- d'autre part des systèmes de calculs associés à P1 et P2.

• Exemple 2 :

Si P est " Tantque exp : E Fintantque"

P^ = Ega(Eval(exp), vrai).E^.P^ U Ega(Eval(exp), faux)

Ainsi pour une phrase P qui est une itération, A(P) est un système à point fixe sur l'ensemble P(Minfini) des calculs. ( Car on P^ = f (P^,....)

• L ’ensemble des calculs muni de l'inclusion est un ensemble ordonné inductif ( treuilli complet )



• Plus généralement, à toute phrase P et en particulier à tout programme (d'un langage) est associé un système à point fixe(appelé système de calcul) A(P) sur P(Minfini) de la forme

A(P) P^=f(P1^, P2^, ...., P^k)

A(Pi), i=1, ..,k



• f est la composée des fonctions de base : concaténation et Union qui sont continues dans P(Minfini) muni de l'inclusion. f est par conséquent continue ( théorème : si f et g sont continue, alors f o g est continue.

• Le théorème du point fixe peut s'appliquer ici et on peut affirmer l'existence d'une solution minimale. La composante relative à P(dans le système à point fixe ) est l'ensemble des calculs qui est la valeur sémantique de P.


� Sémantique relationnelle

• Le programme "Si e : P1 sinon P2 Fsi" spécifie la relation (e;R1) U (Non e;R2)

avec P1 spécifiant R1 et P2 spécifiant R2.

• R1 Inclus R2 : si P1 peut fournir y à partir de x, il en est de même pour P2.

• Le programme " Tantque e : P Fintantque " spécifie la relation (e*R) = (e;R)*;Non e

Spécification de systèmes

� Introduction : idées générales

• Le schéma général d'élaboration un logiciel peut être le suivant :

- Cahier de charge

- Spécification des besoins

- Transformations ( ou conception et implémentation)

- Programmes



• Principe adopté : abstraction

• la description du comportement d'un objet est distincte de la description de sa réalisation. L'application de ce principe conduit aux notions de procédures , modules, ...

• Le principe de l'abstraction conduit à considérer la spécification comme un contrat entre le concepteur et l'utilisateur.

• Pour l'utilisateur, la spécification définit le mode d'emploi et décrit son comportement en toute circonstance.

• Pour le concepteur, la spécification est l'objectif à atteindre.



• Pour spécifier les besoins, généralement on commence par des spécifications élémentaires pour construire progressivement des spécifications complexes ( à l'aide d'opérations).

• Il n'existe pas un procédé automatique qui permet de construire la spécification à partir du cahier de charge.

• Une fois qu'on a obtenu la spécification du système, On aimerait aller automatiquement vers des programmes ( stade de la recherche actuellement)

• Ainsi la spécification peut être vue comme un processus de développement de logiciel.

• Il est clair que ce processus augmente la qualité du système et réduit les coûts de développement.


� Introduction : usage

• La spécification sert à établir ou à vérifier des propriétés d'un système : idéalement toutes les propriétés doivent pouvoir être déduites de la spécification.

• Elle sert de base à la validation, c'est à dire la vérification de la conformité du système aux propriétés requises.

• Elle sert de guide pour la réalisation. Idéalement on aimerait concevoir un moyen de transformation automatique de la spécification à la réalisation.

• Elle est un moyen important de documentation du système.


� Introduction : qualités

• Précision : description sans ambiguïté.

• Cohérence : description ne contenant pas d'énoncés caractéristiques.

• Complétude: description la plus complète possible.

• Concision : description doit être minimale.

• Modifiabilité : description doit être aisément modifiable

• Réutilisabilité : description doit être paramétrée.


� Introduction : orientation • Spécifications algébriques : spécifications de type abstrait : classes d'objets muni d'un ensemble

d'opérations— Spécifications fonctionnelles : Les propriétés de ses fonctions sont exprimées à l'aide de fonctions.— Spécifications relationnelles : Les propriétés de ses fonctions sont exprimées à l'aide de relations.

• Développement de langages de spécification exécutable : idéalement on veut supprimer la distinction entre spécification et programme. On peut ainsi obtenir rapidement une version prototype destiné à l'expérimentation.( par exemple Prolog)


� Spécification algébrique

• Une spécification est composée de 4 parties

1. En-tête : nom, paramètres et les spécifications requises. Le paramètre peut être générique.

2. Description informelle

3. Signature des opérations.

4. Axiomes définissant les opérations sur les types.


� Spécification algébrique : exemple

Coord

Sort Coord

Import Integer, Boolean

Create(integer, integer) --> Coord

X(coord) --> Integer

Y(Coord) --> Integer

Eq(Coord, Coord) --> Boolean

X(Create(x, y)) = x

Y(Create(x, y)) = y

Eq(Create(a, b), Create(c, d)) = (a=c) & ( b=d)

Fin


� Spécification algébrique

• pour spécifier tout un système, il faut définir une bibliothèque de spécification élémentaires en vu de construire des opérations complexes.

• De Coord on construit une zone (Zone)

• On Construit une liste( Liste)

• De Liste on construit Liste ordonnée

• De Zone et Liste ordonnée on construit une liste ordonnée de zones.

• Liste ordonnée de zone peut rentrer dans la construction d'un éditeur de texte.


� Spécification relationnelles : pré-requis ( Algèbre des relations)

• Soit S un ensemble. Une relation binaire sur S est un sous ensemble du produit cartésien SXS. En d'autres termes un ensemble de couples d'éléments de S.

• Domaine : Dom(R) = { x tel qu'il existe y x R y }

• Co-domaine ou Rang Rng(R) = { y tel qu'il existe x x R y }

• Ensemble image d'un élément x par la relation R

• x.R = {y tel que x R y }



• Composition ( ou produit noté R1 o R2)

• R1; R2 = {(x,y) dans S2 tel que il existe z dans S x R1 z et z R2 y }

• Union : R1 U R2 = {(x,y) tels que x R1 y ou x R2 y }

• Intersection : R1 Inter R2 = {(x,y) tels que x R1 y et x R2 y }

• Inverse d'une relation R-1 = { (x, y) tel que y R x }



• Relations constantes

V : relation vide : Il n'existe aucun couple pour lequel on a x V y.

E : relation identité : E = { (x, x) tel que x dans S }

U : relation universelle : U = { (x, y) tels que x dans S et y dans S }

• Remarques :

Toute relation binaire est incluse dans U. En particuliers V et E.

E! = V.



• Montrons que R;E = E;R = R x (R;E) y ==> Il existe z tel que x R z et z E y Il existe z tel que x R z et z = y x R y donc R;E = R

x (E;R) y ==> Il existe z tel que x E z et z R y Il existe z tel que x = z et z R y x R y donc E;R = R



• Inclusion R1 Inclus dans R2 = { (x,y) tel que si x R1 y alors x R2 y } R2 Inclus dans R1 <==> R1 U R2 = R1 <==> R1 Inter R2 = R2 R1 ; (R2 U R3) = (R1 ; R2) U (R1 ; R3)

R1 Inclus dans R2 ==> R1; R Inclus dans R2; R R; R1 Inclus dans R; R2 V Inclus dans R R Inclus dans U Pour tout prédicat p : V Inclus dans p et p Inclus dans E.



• Itéré d'une relation :

C'est la fermeture réflexive transitive notée R*. Elle est définie comme suit :

R* = R0 U R U (R;R) U (R;R;R)....

R0 = E et Rn = Rn-1;R



• Relation associée à un prédicat :

A tout prédicat p on peut associer une relation

p = { (x,y) tel que p(x) vrai }

p!= { (x,y) tel que p(x) faux }

p;q est la relation associée au prédicat p et q

pUq est la relation associée au prédicat p ou q



• Justifions :

x (p;q) y ==> il existe z tel que x p z et z p y

Or x p z entraîne x = z

donc x p x et x q x

c'est à dire p(x) et q(x)

ou encore p et q.

On peut facilement montrer que

x (p;R) y <==> p(x) et x R y

x (p;R;q) y <==> p(x) et x R y et q(y)


� Spécification relationnelles : définition

• Définie par la donnée - d'un ensemble X d'entrée. Contient toutes les opérations du types

de données à spécifier. - d'un ensemble Y de sortie. Contient toutes les sorties jugées valides

par le concepteur. - d'une relation R de X* --> Y. Donc R Inclus X* X Y

• R = { (Q, y) tel que Q est une séquence d'entrée légale, y sortie correcte pour Q }

• Si pour une entrée Q, on peut avoir plusieurs sorties y, R est non déterministique.


� Spécification relationnelles : exemple

• Concevoir un système permettant de lire une séquence d'entiers naturels et de fournir à la demande par l'intermédiaire de l'opération max le plus grand entier depuis la dernière initialisation(init). Quand l'entrée est différente de max la sortie est insignifiante.


� Spécification relationnelles : exemple

X = N U {init, max}

Y = N

Relation R inclus (N U {max, init}* X N.

R = {(Q, y) Il existe q, q'

Q = q'.init.q.max & init n'appartient pas q & y = max{q} } U {(Q, y) tel que init appartient Q & der(Q) # max }


� Spécification Z : définition

• Basé sur la logique du premier ordre et la théorie des ensembles. Les spécifications sont décrites à l'aide de schémas.

• Un schéma Nom Déclaration ------------ Prédicat• Exemple S Racine : N Nombre : Z ------------ Nombre >=0 & Racine <= Nombre


� Spécification Z : opérations

• x : S définir la variable x de types S, c'est à dire une variable à deux composante Nombre et Racine et telle que Nombre >= 0 et Racine <= Nombre.

• Tuple(S) : donne (Racine, Nombre)

• Pred(S) : donne partie prédicat de s

• On peut ajouter une déclaration, ajouter un prédicat, substituer une variable par une autre, décorer(renommage des variables)

• On peut faire l'union, l'intersection, ..


� Spécification Z : opérations

• On peut aussi faire des projections sur une liste de variables, c'est à dire enlever les variables qui n'occurrent pas dans la liste et les quantifier existentiellement dans la partie prédicat

• Projection de S sur Racine donne

Racine : N

-------------------------------------------------

Il existe Nombre : Nombre >=0 et Racine <= Nombre


� Spécification Z : exemple

• Spécification d'un contenaire Contenaire Contenu : N Capacité: N ------------------- Contenu <= Capacité• Spécification d'un indicateur Indicateur Voyant : (On, Off) Valeur : N Danger : N --------------------------- Voyant = On <==> valeur <= Danger


� Spécification Z : exemple

• Spécification d'un type de contenaire : Un_contenaire @Contenaire @Indicateur ------------------------ Valeur = Contenu Capacité = 500 Danger = 50

• Le voyant devient 'On' quand son contenu est inférieur à 50%.

Documents

Spécification de programmes et de systèmes A. Introduction B. Spécification de programmes Introduction Opérationnelle ( Calculatoire ) Dénotationelle (