Beweisbar korrekte Software - informatik.uni-augsburg.de · Strukturierte Spezikationen Motivation...

Beweisbar korrekte Softwareeine praktische Einfuhrung

Simon Baumler, Jonathan Schmitt

Strukturierte Spezifikationen

MotivationSpezifikationen werden sehr schnell sehr gro� Strukturierung erforderlich

1. Übersichtlichkeit & Verständlichkeit

2. Wiederverwendung von Komponenten

3. unabhängige Entwicklung von Komponenten

4. Strukturierung und Wiederverwendung von Beweisen

Strukturierte Spezifikationen

Definition(Spezifikationsoperator)Ein Spezifikationsoperator op ist ein Konstruktor, der für gegeignetestrukturierte Spezifikationen SP � , . . . , SP � und passende Zusatzinformation�

eine neue strukturierte Spezifikation

op(SP � , . . . , SP � , �)

aufbaut.

op : SPEC

��� � � SPEC

Strukturierte Spezifikationen

Definition (Modelle und Gültigkeit)Zu jeder strukturierten Spezifikation SP wird eine zugehörigeBasisspezifikation flatten(SP) := (Sig(SP),Gen(SP),Ax(SP)) definiert, die dieStrukturierung entfernt. Die Modelle von SP werden als die Modelle vonflatten(SP) definiert:� Mod(SP) � � � Mod(flatten(SP))

Somit ist ein Theorem gültig über SP, wenn es über flatten(SP) gültig ist:

SP

�� B � � flatten(SP)

�� B

Strukturierte Spezifikationen

Definition(Spezifikationsgraph)Ein Spezifikationsgraph ist ein azyklischer Graph, dessen Knoten entweder

� eine elementare Spezifikation SP� einen Spezifikationsoperator op und ein

�

enthalten, so daßop(specs(succs(node)),

�

) eine strukturierte Spezifikation ist

Bemerkung (KIV)

� In KIV enthält jeder Knoten außerdem eine Theorembasis� Die Theorembasis enthält eine Menge von Theoremen (Sequenzen)über der Signatur von flatten(SP)� Für jede Sequenz kann ein Beweis vorhanden sein, der zeigt, daß dieSequenz aus SP und anderen Theoremen folgt (keine zyklischenAbhängigkeiten)

Anreicherung

Definition (Anreicherung)SP’ := enrich SP with ((S’,F’,P’),Gen’,Ax’)ist eine Anreicherung (engl. enrichment) von SP, wenn

� Sig(SP) � (S’, F’,P’) = (

�

,

�

,

�

)� Sig(SP’) := Sig(SP) � (S’, F’,P’)ist eine Signatur� Gen’ und Ax’ sind über Sig(SP’) gebildet� Gen(SP’) := Gen(SP) � Gen’� Ax(SP’) := Ax(SP) � Ax’

Anreicherung

Motivation für weiteres Vorgehen

� Wichtigste Eigenschaften für Spezifikationen:Konsistenz (hat mindestens ein Modell)Monomorphie (hat höchstens ein Modell)� Frage: Hat SP’ ein Modell, wenn SP eines hatte?� Insbesondere: Enthält das SP’-Modell das SP-Modell?� Dann Anreicherung gut strukturiert(Modelle „zusammenbaubar“)� Frage: Ist SP’ monomorph, wenn SP monomorph?

Anreicherung

Definition (Expansion, Redukt)Sei

� � ���� �� � �

,

�� � �

,

� Alg

� � �

,

�� Alg

� � � �

Falls� � � � � �� für ! �

� "$# � "$#% für

" �

�& # � & #% für

" �

gilt, so ist

� �

’ Expansion (Fortsetzung) von�

� �

Redukt von

��

auf

�(geschrieben

�� (' � �)

Anreicherung

Faktum (Anreicherung)� Mod(enrich SP with

�

)� � *)+-, ./0 1 Mod(SP)und

� �� Gen(

�

) � Ax(

�

)

Definition (Hierarchiepersistenz)Sei SP’ := enrich SP with (

�

’,Gen’,Ax’). Die Anreicherung heißthierarchiepersistent (oder: konservativ, frei parametrisierbar,konsistenzerhaltend), wenn sich jedes Modell

� Mod(SP) zu einemModell

�� Mod(SP’) fortsetzen läßt:�� (' � �

Faktum (Konsistenz und Hierarchiepersistenz)Sei SP’ := enrich SP with (

�’,Gen’,Ax’). Ist SP konsistent und die

Anreicherung hierarchiepersistent, so ist SP’ konsistent.

Anreicherung

Definition (Eindeutigkeit)Sei SP’ := enrich SP with (

�

’,Gen’,Ax’). Die Anreicherung heißt eindeutig(oder: monomorphieerhaltend), wenn für je zwei Modelle

��,

2 � Mod(SP’)aus

�� 3' =

2 � ' (oder auch:

�� 3' 4� 2 � ' ) folgt, da�� 4� 2 �

gilt.

Faktum (Monomorphie und Eindeutigkeit)Sei SP’ := enrich SP with ((S’,F’,P’),Gen’,Ax’). Ist SP monomorph und dieAnreicherung eindeutig, so ist SP’ monomorph.

Anreicherung

POElem =specificationsorts elem;predicates . 5 . : elem� elem;variables a, b, c : elem;axioms6 a 5 a;a 5 b 7 b 5 c � a 5 c;end specification

TOElem1 =enrich POElem witha 5 b 8 a = b 8 b 5 a;end enrich

Die Anreicherung TOElem1 ist nicht hierarchiepersistent, aber (trivial)eindeutig.

Anreicherung

TOElem2 =enrich TOElem1 withconstants 0 : elem;a

9� 0 � 0 5 a;end enrich

Die Anreicherung TOElem2 ist nicht hierarchiepersistent, aber eindeutig

Anreicherung

Faktum (Anreicherungen ohne neue Signatur)

� Jede Anreicherung, die keine neue Signatur addiert, ist eindeutig� Eine Anreicherung um Axiome ist nur dann hierarchiepersistent, wenndie neuen Axiome schon über der alten Spezifikation gelten� Eine Anreicherung um eine Generiertheitsklausel für eine Sorte, dienoch keine besitzt, ist nicht hierarchiepersistent.

Anreicherung

BemerkungIn der Mathematik sind solche Anreicherungen um Axiome(“Spezialisierung”, Einschränkung der Modelle) häufig: Monoid zu Gruppe,Gruppe zu abelscher Gruppe, Ring zu Körper, Körper zu geordnetemKörper, Verband zu boolescher Algebra, beliebige Topologie zu kompakter,etc.In der Informatik kommt Spezialisierung dagegen üblicherweise nur zurImplementierung, nicht zur Spezifikation vor.

Anreicherung

Ring =specificationsorts elem;constants 0,1 : elem;functions

. + . : elem� elem � elem ;

. * . : elem� elem � elem ;

. : . : elem � elem ;axiomsa + 0 = a; a + ( : a) = 0; 1 * a = aa * (b + c) = a * b + a * c;. . .end specification

Anreicherung

Field =enrich Ring withfunctions . ; � : elem� elem � elem;axiomsa

9� 0 � a * ( < ; � ) = 1end enrichDie Anreicherung Field ist nicht hierarchiepersistent, aber eindeutig

Anreicherung

Faktum (Anreicherungen um nichtrekursiv definiertes Prädikat)Jede Anreicherung

SP’ = enrich SP with ((

�

,

�

,{p}),

�

,{p(x) = B})mit B For(Sig(SP),{x}) ist hierarchiepersistent und eindeutig.

Ersetzt man die Äquivalenz durch eine Implikation (egal in welche Richtung)bleibt die Anreicherung hierarchiepersistent, wird aber im allg. nicht mehreindeutig sein.

Anreicherung

NatDiv =enrich Nat withpredicates

: nat� nat;axiomsm

n = >

k. k * m = n;end enrich

Die Anreicherung NatDiv ist hierarchiepersistent und eindeutig

Anreicherung

NatPrime =enrich NatDiv withpredicates prime : nat;axioms6 prime(0);6 prime(1);

n

?

2� (prime(n) = @

m. m

n � m = 1 8 m = n);end enrich

Die Anreicherung NatPrime ist hierarchiepersistent und eindeutig

Anreicherung

Faktum (Anreicherungen um nichtrekursiv definierte Funktion)Jede Anreicherung

SP’ = enrich SP with ((

�

,{f},

�

),

�

,{f(x) = t})mit t T(Sig(SP),{x}) ist hierarchiepersistent und eindeutig.

Schreibt man vor die Gleichung eine Bedingung, so bleibt die Anreicherunghierarchiepersistent, wird aber im allg. nicht mehr eindeutig sein.

Anreicherung

Nat12 =enrich Nat withconstants 1 : nat; 2 : nat;axioms1 = 0 +1;2 = 0 +1 +1;end enrich

Die Anreicherung Nat12 ist hierarchiepersistent und eindeutig

Anreicherung

NatMinus =enrich Nat + Less withfunctions : : nat� nat �: nat;axioms6 m 5 n � (m : n = k = n + k = m);end enrich

Die Anreicherung NatMinus ist hierarchiepersistent aber nicht eindeutig

Anreicherung

Faktum(Rekursive Funktionsdefinition über freien Datentypen)enrich SP with ((

�

,{f},

�

),

�

,Ax)ist hierarchiepersistent und eindeutig, wenn� f F A �BDCE E E �GF HC �

� s freely generated by {c � , . . . c I} Gen(SP)

und f durch Ax vollständig durch Rekursion über den Konstruktoren c J

definiert ist.

Anreicherung

Bemerkung (Rekursive Def. mit Fallunterscheidung)Jedes rekursive Axiom kann durch vollständige Fallunterscheidung zerlegtwerden. Läßt man Axiome (oder Fälle in den Axiomen) weg, so bleibt dieAnreicherung hierarchiepersistent, aber die Eindeutigkeit geht i.a. verloren.

Definition und Satz(Rekursive Funktionsdefinition über nichtfreien Datentypen)Eine rek. Definition über einem Datentyp, in dem die Sorte nur generiertstatt frei generiert ist, ist eindeutig aber im allg. nicht hierarchiepersistent(d.h. möglicherweise inkonsistent).

Anreicherung

Append =enrich List withfunctions ++ : list� list � list;axiomsnil ++ l = l;(a + l) ++ l’ = a + (l ++ l’);end enrichAppend ist hierarchiepersistent und eindeutig

Anreicherung

FList =enrich List � Nat withfunctions f : list� nat � list;axiomsf(nil, x) = nil;f(a + l, 0) = a + l;f(a + l, x +1) = f(l, x);end enrich

Flist ist hierarchiepersistent und eindeutig

Anreicherung

Definition und Satz(Rekursive Prädikatdefinition über freien Datentypen)enrich SP with ((

�

,

�

,{p}),

�

,Ax)ist hierarchiepersistent und eindeutig, wenn� p P A �B CE E E � F H

� es gibt ein s J , i {1, . . . , n} mits J freely generated by {c � , . . . c I} Gen(SP)

und p ist durch Ax vollständig durch Rekursion über den Konstruktoren c K

definiert ist.

Anreicherung

Definition und Satz(Rekursive Prädikatdefinition über nichtfreien Datentypen)Eine rek. Prädikatdefinition über einem Datentyp, in dem die Sorte nurgeneriert statt frei generiert ist, ist eindeutig aber im allg. nichthierarchiepersistent (d.h. möglicherweise inkonsistent).

Anreicherung

IsLast =enrich List withpredicates islast : list� elem;axioms6 islast(nil,c);islast(a + nil,c) = a = c;islast(a + b + l,c) = islast(b + l,c);end enrich

IsLast ist hierarchiepersistent und eindeutig

Anreicherung

Faktum (Freie Datentypen)Jede Anreicherungenrich SP with

(({s},F,

�

,),{s freely generated by F},

�

)ist hierarchiepersistent und eindeutig

Korollar (Freie Datentypen)Jede Spezifikation

(({s},F,

�

,),{s freely generated by F},

�

)ist konsistent und monomorph

Korollar (Datendefinitionen)Die Anreicherung einer Spezifikation um eine Datendefinition isthierarchiepersistent und bis auf die unspezifizierte Definition von Selektorenauf falsche Konstruktoren eindeutig.

Anreicherung

Satz (Vergleich von Enrichments mit denselben Sorten)Seien

� SP1 = enrich SP0 with (

�

,Gen,Ax)� SP2 = enrich SP0 with (

�

,Gen’,Ax’)� Gen

�

Gen’, Ax

�

Ax’

Dann gilt

� SP2 hierarchiepersistent� SP1 hierarchiepersistent� SP1 eindeutig � SP2 eindeutig� speziell: SP2 kons. � SP1 kons.� speziell: SP1 monomorph � SP2 monomorph

Anreicherung

Satz (Transivität von Hierarchiepersistenz und Eindeutigkeit)Seien

SP1 = enrich SP0 with

�

,SP2 = enrich SP1 with

� �

SP3 = enrich SP0 with

� � � �

Dann gilt:

� Mod(SP2) = Mod(SP3) (trivial)� SP1 hp. und SP2 hp. � SP3 hp.� SP1 eind. und SP2 eind. � SP3 eind.

Vereinigung

Definition (Vereinigung)SP = SP1 + SP2 heißt Vereinigung (engl. union) zweier Spezifikationen.

� Sig(SP) = Sig(SP1) � Sig(SP2)� Gen(SP) = Gen(SP1) � Gen(SP2)� Ax(SP) = Ax(SP1) � Ax(SP2)

Faktum (Vereinigung)� Mod(SP1 + SP2)� � )+-, .)L � 1 Mod(SP1)und

� )+-, .)L M 1 Mod(SP2)

Vereinigung

Faktum (Eindeutigkeit)Jede Vereinigung SP = SP1 + SP2 ist eindeutig: Für�� Mod(SP1),

�M Mod(SP2)gibt es höchstens ein Modell

�

mit� N)+-, .)L � 1 = �� bzw.

� )+-, .) L M 1 = �M .So ein Modell gibt es genau dann, wenn�� O)+-, .) L � 1P )+-, .)L M 1 = �M )+-, .)L � 1P )+-, .)L M 1 ,(also insb. falls Sig(SP1) � Sig(SP2) =

�),

und das Modell ist dann

�

:=

�� � �M .

Folgerung (Monomorphie)Sind SP1 und SP2 monomorph, so auch SP1 + SP2.

Vereinigung

Faktum (Disjunkte Vereinigung)Zu je zwei Modellen

� Mod(SP1) und

2 Mod(SP2) gibt es nur dannimmer ein Modell von SP1 + SP2, falls Sig(SP1) � Sig(SP2) =

�(disjunkte

Vereinigung).

Definition (Hierarchiepersistenz)SP = SP1 + SP2 heißt hierarchiepersistent, wenn

� �� Mod(SP1)� es gibt

� Mod(SP) mit

� )+-, .) L � 1 = ��

� �M Mod(SP2)� es gibt

� Mod(SP) mit� )+-, .) L M 1 = �M

Vereinigung

FaktumSP = SP1 + SP1 ist hierarchiepersistent, wenn beide Anreicherungenenrich SP1 with (Sig(SP2)

Q

Sig(SP1),Gen(SP2)

Q

Gen(SP1),Ax(SP2)

Q

Ax(SP1))enrich SP2 with (Sig(SP1)

Q

Sig(SP2),Gen(SP1)

Q

Gen(SP2),Ax(SP1)

Q

Ax(SP2))hierarchiepersistent sind.

Vereinigung

BeispieleNatc = enrich Nat with

constants c : nat; end enrichNatc=n = enrich Nat with

constants c : nat;axioms c = n; end enrich

Natc

?

n = enrich Nat withconstants c : nat;axioms c

?

n; end enrichNatc

R

n = enrich Nat withconstants c : nat;

axioms c

R

n; end enrich

Vereinigung

Natc=1 + Natc=2 ist nicht hierarchiepersistentNatc + Natc ist hierarchiepersistentNatc + Natc=2 ist nicht hierarchiepersistentNat + Natc=2 ist hierarchiepersistentNatc

?

1 + Natc=1 ist nicht hierarchiepersistentNatc

?

1 + Natc ist nicht hierarchiepersistentNatc=1 + Natc=1 ist hierarchiepersistentNatc

?

0 + Natc ist nicht hierarchiepersistent(Natc

R

1 + Natc

?

1) + Natc=1 ist hierarchiepersistent

FaktumVereinigung von 2 Spezifikationen, die gemeinsame Signatur inverschiedenen Unterspezifikationen definieren, ist fast immer nichthierarchiepersistent. �Verbieten!

Umbenennung

Grundidee: Benenne Operationen um, z. Bsp. um identische Kopien zuerhalten

Definition (Signaturmorphismus)Seien

�

= (

�

,

�

,

�

) und

� �

= (

� �

,

� �

,

� �

) zwei Signaturen.Eine Abbildung S � � � � � � � � � � � � � � �

heisst(Signatur-)Morphismus von

�

nach

� �

(geschrieben S : � � � �

), wenn� S �� � � � �

� S � � � � � �

� S � � � � � �

� !� ! �� T T T� ! � � ,

" � A �BDCE E E C �GF HC � und S � " � � " �

� " � � �AVU . �B 1C E E E C U . � F 1 HC U . � 1

� !� ! �� T T T� ! � � ,& � A �WBXC E E E C � F H und S �& � � & �

�& � � �AVU . �B 1CE E E C U . �YF 1 H

Umbenennung

Anwendung von MorphismenIst S ein Signaturmorphismus, der zusätzlich Variablen aus X� injektivVariablen aus XU . � 1 zuordnet läßt sich der Morphismus auf Terme, Formelnund Erzeugtheitsklauseln anwenden:

� S(f(t � , . . . , t �)) : Z S(f)( S(t � ), . . . , S(t �))� S(t � = t �) : Z S(t � ) = S(t M)� S( @

x. B) : Z ( @ S(x). S(B))� . . .� S(s generated by c � , . . . , c I) : ZS(s) generated by S(c � ), . . . , S(c I)

Umbenennung

Signaturmorphismen und Algebrenmorphismen

Sei S � � � � �

ein Signaturmorphismus undsei

�� Alg

� � � �

mit

�� � � � ��� � � [ / % � � "$#% �3\ [ ]% � �& #% �_^ [0 % �.

Dann ist

�� � � ��U . � 1 � � [ /� � S � " � #% �`\ [ ]� � S �& � #% �^ [0 � Alg� � �

Jeder Signaturmorphismus S � � � � �

induziert einenAlgebrenmorphismus S ; �abdc : Alg(

� �) � Alg(

�)

durch die oben angegebene Konstruktion.

Ist S � � � � �

ein injektiver Signatur-Morphismus, so läßtsich die Abbildung umkehren, d. h. es gibt einenAlgebrenmorphismus S abdc : Alg(

�

) � Alg(

� �

)

Umbenennung

Definition (Umbenennung)rename SP by S

heißt Umbenennung (engl. renaming) einer Spezifikation SP, falls S

injektiver Morphismus mit dom( S) = Sig(SP). In diesem Fall definiert man:

� Sig(rename SP by S) = S(Sig(SP))� Gen(rename SP by S) = S(Gen(SP))� Ax(rename SP by S) = S(Ax(SP))

Faktum (Umbenennung)Die Modelle einer umbenannten Spezifikation sind genau die umbenanntenModelle der Originalspezifikation:

Mod(rename SP by S) = S abdc (Mod(SP))

Umbenennung

Faktum (Eliminierbarkeit von Umbenennungen)Aus jedem Spezifikationsgraph lassen sich Umbenennungen eliminierendurch wiederholtes Anwenden von:

� rename (

�

, Gen, Ax) by S� ( S( �

), S(Gen), S(Ax))� rename (enrich SP with

�

) by S� enrich (rename SP by S )+-, .)L 1 )with S( �

)� rename (SP1 + SP2) by S� (rename SP1 by S )+-, .) L � 1 )+ (rename SP2 by S )+-, .) L M 1 )

Jede der Regelanwendungen erhält die Semantik der Spezifikation.

Aktualisierung

Definition (direkte Unterspezifikation)SP ist direkte Unterspezifikation von SP

�

(SP 5 � SP

�

), wenn

� SP

�

= enrich SP with

�

oder� SP

�

= SP + SP2, SP

�

= SP1 + SP

Definition (Unterspezifikation)SP ist Unterspezifikation von SP

�

(SP

RSP

�), wenn es SP1, . . . , SPn gibt

mitSP = SP1 5 � SP2 5 � . . . 5 � SPn = SP

�

Insbesondere gilt SP

R

SP.

Aktualisierung

Grundidee: Ersetze einen Parameter durch konkretere Spezifikation

Definition (Aktualisierung) Sei PSP

R

SP, und S : PSP � ASP einSignaturmorphismus. Dann heißt

SP

�

:= actualize PSP

R

SP with ASP by SAktualisierung (engl. actualization) des Parameters PSP von SP durch ASP,falls

� ASP

�� S(Gen(PSP)) und ASP

�� S(Ax(PSP))� (Sig(SP)

Q

Sig(PSP)) � Sig(ASP) =�

Mit S � := S � id e+-, .)L 1f e+-, .L )L 1 ist

� Sig(SP

�

) = (Sig(SP)

QSig(PSP)) � Sig(ASP)� Gen(SP

�

) = S �(Gen(SP)) � Gen(ASP)� Ax(SP

�

) = S �(Ax(SP)) � Ax(ASP)

Aktualisierung

Definition (Amalgamsumme)Sei S : � � � � �

,

� � � �

, sowie

� Alg(

� � �

),

2 Alg(

� �

) mit S ; � ( �) =

2 ' .Dann ist �� U 2

die durch g �� � � g � h < i ikj j � � �

l � jm nj o

h #% � � h # h < i ikj h � � �

hqp jm nj o

r #% � � r # h < i ikj r � � �

r p jm nj o

eindeutig definierte Algebra.

Aktualisierung

Faktum (Aktualisierung)Mod(SP

�

) = {

�� U 2

: 2 Mod(SP)und

� Mod(ASP)und

� 2 )+-, .L )L 1 � = S ; � ( �

)}

Aktualisierung

Definition (Hierarchiepersistenz)

Eine Aktualisierung ist hierarchiepersistent, wenn� Mod(ASP)� es gibt

2 Mod(SP

�

) :

2 e+-, .s )L 1 = �Satz (Hierarchiepersistenz)

Ist die Anreicherung von PSP zu SP hierarchiepersistent, so ist auch jedeAktualisierung von PSP in SP hierarchiepersistent.

Aktualisierung

Faktum (Eliminierbarkeit von Aktualisierung)Besteht SP nur aus Basisspezifikationen, Anreicherungen und Vereinigung,so kann eine Aktualisierung

actualize PSP

R

SP with ASP by Ssemantikerhaltend durch die folgenden Transformationen beseitigt werden:

� actualize SP

R

SP with ASP by S� ASP� actualize SP

R

(enrich SP with

�)

with ASP by S� enrich ASP with

�

� actualize SP

� R

(enrich SP with

�)

with ASP by S� enrich (actualize SP

� RSP

with ASP by S) with

�

Aktualisierung

� actualize SP1

R

(SP1 + SP2)with ASP by S� ASP + SP2� actualize SP

� R

(SP1 + SP2)with ASP by S� (actualize SP’

R

SP1 with ASP by S) + SP2falls SP

� R

SP1

Theorem (Elimination von Aktualisierung und Umbenennung)

Aus jedem Spezifikationsgraph können Umbenennungen undAktualisierungen senantikerhaltend beseitigt werden.

� Praktisch recht aufwendig!� Sinnvoll für Codegenerierung.