Strukturierte Spezifikationen:

Umbenennung und Parameter

149

Strukturierte Spezifikationen:Umbenennung

Umbenennung:

• Benennt die Operationen einer Spezifikation um

• Nützlich um 2 Kopien zu erhalten

• Syntax: rename <SPEC> by morphism<renaming1>;...<renamingn>;

end rename

• renaming = <sort/op/var> → <sort/op/var>;

• Identische Umbenennungen weglassen(werden beim Ansehen der Spezifikation aber angezeigt)

• Nicht 2 Symbole auf dasselbe abbilden: Injektiv umbenennen

• Entweder alle Variablen oder keine umbenennen

150

Beispiel Umbenennung:Listen zu Stacks

rename List by morphismlist → stack;[] → empty;(: Typangabe f ur uberladenes Symbol :)+ :: (elem × list → list) → push;(: pop nicht mehr postfix, Schreibweise stattdessen pop(x) ,

default ist in/prae/postfix uebernehmen :).rest → pop prio 0;(: top soll nun praefix sein :).first → top .;(: eigentlich keine Stack-Operation,

nur um Overloading zu zeigen :)+ :: (list × list → list) → concat prio 0;x → st;y → st0;z → st1;

end rename 151

Strukturierte Spezifikationen:Generische Spezifikation

Generische Spezifikation:

• Syntax: generic specificationparameter <SPEC>using <SPEC1>, ..., <SPECn>target

<signature><induction><axioms>

end generic specification

• Wie Anreicherung (von <SPEC>, <SPEC1>, ..., <SPECn> ), nurwird von <SPEC>explizit gesagt, dass es sich um einen Parameterhandelt

• Vereinigung und Anreicherung übernimmt den (oder die) Parameter derUnterspezifikationen

• Variante: generic data specification : Wie data specification nur mitParameter 152

Strukturierte Spezifikationen:Aktualisierung (1)

Aktualisierung:

• Instanziert Parameter (oder einen Parameter) einer Spezifikation

• Beispiel: Listen beliebiger Elemente → Listen von Zahlen

• Syntax: actualize <SPEC> with <ASPEC1>,...,<ASPECn> by morphism<renaming1>;...<renamingn>;

end actualize

• renaming = <sort/op/var> → <sort/op/var>;

• Die Vereinigung von <ASPEC1>,...,<ASPECn> heisst aktuelleSpezifikation

• Identische Umbenennungen weglassen

• Entweder alle Variablen oder keine umbenennen

153

Strukturierte Spezifikationen:Aktualisierung (2)

Aktualisierung:

• Der Parameter muss in die aktuelle Spez. abgebildet werden

• Abbildung darf nicht-injektiv sein: pair(elem1 , elem2 ) → pair(nat ,nat)

• Der Nicht-Parameter-Teil darf nur injektiv und disjunkt zur aktuellenSpezifikation umbenannt werden, z. B. list → natlist

• Die instanzierten Axiome des Parameters müssen Axiome in deraktuellen Spezifikation sein

• Verallgemeinerung instantiated specification :⋆ Axiome werden bewiesen⋆ mapping statt morphism erlaubt es, eine Sorte auf ein Tupel von

Sorten abzubilden

154

Aktualisierung: Beispiel (1)

Order =specificationsorts elem;constants d : elem;predicates ≪ : elem × elem;variables a, b, c : elem;axioms¬ a ≪ a; a ≪ b ∧ b ≪ c → a ≪ c;¬ a ≪ d; (: d ist minimal :)end specification

List-Ord =generic data specificationparameter Orderusing Natlist = [] | . + . (. .first : elem; . .rest : list);size functions length : list → nat;end generic data specification

155

Aktualisierung: Beispiel (2)

NatList =actualize List-Ord with Nat by morphismlist → natlist;elem → nat;≪ → <;d → 0;a → n; b → n0; c → n1;end actualize

Die instanzierten Axiome (u. a. ¬ n < 0) sind (modulo Umbenennung) in Natvorhanden.

Die Listenoperationen (+, .rest etc.) werden nicht umbenannt (siebekommen nur die neuen Sorten als Argumente).

156

Strukturierte Spezifikation:

Nichtfreie Datentypen

157

Nichtfreie Datentypen: Der typische Fehler

Orderedlist =enrich List3 withpredicates

. < . : elem × elem ;ordered : list ;

axioms¬ a < a; a < b ∨ a = b ∨ b < a;a < b ∧ b < c → a < c;ordered([]); ordered(a + []);ordered(a + b + l) ↔ a < b ∧ ordered (b + l);

end enrich

NICHT ∀ l. ordered(l) addieren!!! Das wäre INKONSISTENT!!!

Allgemein: Ein generierter Datentyp enthält immer alle Konstruktorterme.Man kann nicht nachträglich welche ausschliessen. Man kann nur einennichtfreien Datentyp bilden, der Terme identifiziert

158

Spezifikation nichtfreier Datentypen

• Spezifikationen nichtfreier Datentypen werden sehr leicht inkonsistentoder uneindeutig

• Konstruiere nichtfreien Datentyp dadurch, daß alle Terme, die diegleichen Elemente repräsentieren sollen, in einer Klassezusammengefaßt werden

• Deshalb als erstes nach der Bestimmung der Konstruktoren:Definiere Gleichheit durch Extensionalitätsaxiom: x = y ↔ ϕ(x, y)

• Dann: Die in ϕ benutzten Operationen werden rekursiv definiert

• Damit: Monomorph: Höchstens ein Datentyp spezifiziert

• Vorsicht: Rek. Def. kann inkonsistent sein!

• Jetzt: Arrays, im Praktikum: Mengen (einfacher)

159

Beispiel: Arrayspezifikation, Teil 1

Array=specification

using Nat; Elem;sorts array;functions

mkar : nat × elem → array;. [ . ] : array × nat × elem → array;. [ . ] : array × nat → elem;# . : array → nat;

inductionarray generated by mkar, [];

variables d : elem; a, a’ : array;

160

Beispiel: Arrayspezifikation, Teil 2

Festlegungen:

• Konstruktor mkar(n, d) bekommt Initialelement d(Alternative: Unspezifizierte Initialisierung)

• Für m ≥ # a ist Selektion a[m] unspezifiziert

• Für m ≥ # a ist Modifikation Identität: a[m,d] = a

axiomsa = a’ ↔ # a = # a’ ∧ ∀ n. n < # a → a[n] = a’[n];

# mkar(n,d) = n; # a[m , d] = # a;

m < n → mkar(n,d)[m] = d;

m < # a → a[m , d][m] = d; n 6= m → a[m , d][n] = a[n];end specification

161

Inkonsistente rekursive Definition

• Annahmen:⋆ Mengen von nat. Zahlen definiert⋆ Die Mengen sind von ∅ und insert generiert⋆ Für Mengen gilt: insert(a,insert(a,∅)) = insert(a,∅)

• Rekursive Definition:sum(∅) = 0,sum(insert(a, s)) = a + sum(s)

• Inkonsistent, da aus insert(1,insert(1,∅))) = insert(1,∅) folgt:2 = sum(insert(1,insert(1,∅))) = sum(insert(1,∅)) = 1

• Korrekte Definition:sum(∅) = 0,¬ a ∈ s→ sum(insert(a, s)) = a + sum(s)(im Fall a ∈ s ist insert(a, s) = s)

• Operation sum muss mit der Definition der Gleichheit auf Mengen,i. e. dem Extensionalitätsaxiom verträglich sein!

162

Anforderungen an nichtfreie Datentypen

• Semantische Überlegungen zur Spezifikation nichtfreier Datentypen:⋆ Es gibt den Datentyp ⇒ Konsistenz (wenn Axiome für den

intendierten Datentyp gelten)⋆ Die im Extensionalitätsaxiom durch ϕ beschriebene Relation muss

wenigstens Äquivalenzrelation sein:− Reflexivität: ϕ(a, a)− Kommutativität: ϕ(a, b) → ϕ(b, a)− Transitivität: ϕ(a, b) ∧ ϕ(b, c) → ϕ(a, c)

• Für gleiche Konstruktorterme t1, t2 muss Operation f dasselbe liefern:ϕ(t1, t2) → f(t1) = f(t2)⇒ Beweisverpflichtungen

• Äquivalenzrel. + Verträglichkeit = Kongruenz

163

Korrekte Spez. der geordneten Listen (1)

Orderedlist = specificationsorts elem; ordlist;constants [] : ordlist;functions

. + . : elem × ordlist → ordlist ;min : ordlist → elem ;butmin : ordlist → ordlist ;

predicates

. < . : elem × elem ;variables

a, b, c : elem;l, l ′ : ordlist;

inductionordlist generated by [], +;

164

Korrekte Spez. der geordneten Listen (2)

axioms¬ a < a; a < b ∨ a = b ∨ b < a;a < b ∧ b < c → a < c;

l = l′ ↔ l = [] ∧ l’ = []∨ l 6= [] ∧ l’ 6= []

∧ min(l) = min(l′)∧ butmin(l) = butmin(l′);

min(a + []) = a;a < b → min(a + b + l) = min(a + l);¬ a < b → min(a + b + l) = min(b + l);

butmin(a + []) = [];a < b → butmin(a + b + l) = b + butmin(a + l);¬ a < b → butmin(a + b + l) = a + butmin(b + l);

end specification

165

Noethersche Induktion

166

Noethersche Relationen

Definition (Noethersche Relationen)Sei ≪ ⊆ A×A. Die Relation ≪ heißt noethersch (oder wohlfundiert, engl.well-founded) wenn es keine unendlichen ≪-Ketten gibt:

. . .≪ a3 ≪ a2 ≪ a1 ≪ a0

Beispiele:

• < auf natürlichen Zahlen ist noethersch, aber nicht >

• < auf ganzen Zahlen ist nicht noethersch

• m ≪ n ⇔ n = m + 1 ist noethersch (nicht transitiv)

• ⊂ (echte Teilmenge) ist noethersch auf endlichen Mengen

167

Eigenschaften noetherscher Relationen

• < ist immer irreflexiv

• Die Relation muss nicht transitiv sein, ihre transitive Hülle ist aber auchnoethersch (und transitiv)deshalb häufig o.B.d.A nur noethersche Ordnungen betrachtet

• Die Relation muss kein kleinstes Element besitzen.Beispiel: echte Teilmenge auf nichtleeren Mengen

• kleinstes Element existiert 6⇒ noethersch.Beispiel: < auf rationalen Zahlen ≥ 0

• Wenn < noethersch und ≪ stärker, i.e. x≪ y → x < y,dann erst Recht ≪ noethersch

168

Bedeutung noetherscher Relationen

Bedeutung:

• betrachte Folge der Zustände, die ein Programm durchläuft.Definiere s′ ≪ s :⇔ s′ ist Nachfolgezustand von s

Dann gilt: ≪ noethersch ⇔ Programm terminiert immer

• stärkeres Induktionsprinzip als strukturelle Induktion:noethersche Induktion

• eingesetzt zum Beweis der Terminierung

169

Beispiele für noethersche Prädikate

Ordnungsprädikate: Ordnungsprädikate < von Datendefinitionen sindnoethersch.

Zur Erinnerung: x < y ⇔ „x (als Konstr.term) ist echter Unterterm von y“.Z. Bsp. bei Listen : x < a + x, x < a + (b + x), x 6= [] → [] < xkeine Grössenordnung, nicht: a + x < a + b + x (ausser wenn a = b)

Größenordnung:Sei size : s→ nat . Dann ist ≪ noethersch mit

x≪ y :↔ size(x) < size(y).

Lexikalische Ordnung:Betrachte Spezifikation Pair2 von vorher. Seien <1 : elem1 × elem1 und <2 :elem2 × elem2 noethersch. Dann auch ≪ mit

mkpair(a, b) ≪ mkpair(a′, b′) :⇔ a <1 a′ ∨ (a = a′ ∧ b <2 b

′).

170

Noethersche Induktion

Satz (Noethersche Induktion)Genau für noethersche Relationen ≪ gilt:Wenn für jedes a aus E(a′) für alle Elemente a′ ≪ a die Aussage E(a)gefolgert werden kann, so gilt E für alle Elemente:

(∀ a. (∀ a′. a′ ≪ a⇒ E(a′)) ⇒ E(a)) ⇒ ∀ b. E(b)

Definition (Noethersche Induktionsregel)Sei y := free(Γ ⊢ ∆) \ {x} und ≪ noethersch. Induktion über x:

IND(≪)

∀ y.∀ x′. x′ ≪ x→ (∧

Γ →∨

∆)x′

x ,Γ ⊢ ∆

Γ ⊢ ∆

speziell für Formel:

∀ y.∀ x′. x′ ≪ x→ ϕx′

x ⊢ ϕ

⊢ ϕ

171

Noethersche Induktion (Beispiele)

Beispiel: Natürliche Zahlen

∀ n0. n0 < n→ ϕ(n0) ⊢ ϕ(n)

⊢ ∀ n. ϕ(n)

Beispiel: Listen

∀ l0. (l0 ≪ l) → ϕ(l0) ⊢ ϕ(l)

⊢ ∀ l. ϕ(l)

172

Noethersche Induktion in KIV

• In KIV ist die Regel induction für noethersche Induktion vorhanden

• Für Variablen x eines freien Datentyps wird angeboten⋆ Ind. über vordefiniertes Ordnungsprädikat

(pro Sorte eines; Induktion über x wird angeboten)⋆ Ind. über vordedefinierte Grössenfunktion

(pro Sorte eine Fkt. #; Induktion über # x)

• Grössenfunktionen für nichtfreie Datentypen kann man mit„Unit-Add HeuristicInfo“ addieren

• es ist auch möglich einen Term anzugeben, über dessen Grösseinduziert wird (z.Bsp. # x− # y)

• Die Induktionshypothese wird in KIV mit Ind-Hyp abgekürzt.

• „Goal-Again with Ind-Hyp“ zeigt die Induktionshypothese an.

• Anwendung der Induktionshypothese mit apply induction (statt all left )

173