Nehmen Sie das folgende C ++ 14 Code-Snippet:
%Vor% Anweisung: Die Funktion f gibt das Maximum ihrer Argumente zurück.
Nun ist die Aussage "offensichtlich" wahr, aber ich habe sie nicht streng genug in Bezug auf die ISO / IEC 14882: 2014 (E) Spezifikation bewiesen.
Erstens: Ich kann die Eigenschaft nicht formell angeben.
Eine formalisierte Version könnte sein: Für jede Anweisung s , wenn die abstrakte Maschine (die in der Spezifikation definiert ist) im Zustand P und s wie "f ( expr_a , expr_b ) "und 'f' in s wird in die betreffende Funktion aufgelöst, s (P) .return = max (ausdruck_a (P) .return, ausdruck_b (P) .return) .
Hier für einen Zustand P und Ausdruck s ist s (P) der Zustand der Maschine nach der Auswertung von s
Frage: Was wäre eine korrekt formalisierte Version der Anweisung? Wie kann man die Aussage anhand der Eigenschaften der oben genannten Spezifikation beweisen? Für jeden deduktiven Schritt verweisen Sie bitte auf das entsprechende Snippet aus dem Standard, das diesen Schritt erlaubt (die Nummer des Segments ist ausreichend).
Bearbeiten: Vielleicht in Coq formalisiert
Bitte entschuldigen Sie mich für mein ungefähres alterndes mathematisches Wissen.
Das Maximum für eine geschlossene Teilmenge der natürlichen Zahl (BN) kann wie folgt definiert werden:
%Vor%wo das Symbol die gemeinsame mathematische Bedeutung hat.
Während Ihre Funktion könnte wie folgt umgeschrieben werden, wobei UN das Ensemble von unsigned int :
Wo symbol = ist operator==(unsigned int,unsigned int) , etc ...
Es stellt sich also die Frage, ob der Standard angibt, dass die mathematische Struktur (en) von unsigned integer mit C ++ arithmetischen Operatoren und Vergleichsoperatoren isomorph zu den matematischen Strukturen (Klassen, Kategorien) ist ) gebildet durch eine geschlossene Teilmenge von N mit der gemeinsamen arithmetischen Operation und Relationen. Ich denke, die Antwort ist ja, dies ist in einfachem Englisch ausgedrückt:
C ++ 14 Standard, [expr.rel] / 5 (Relationale Operatoren)
Wenn beide Operanden (nach Konvertierungen) arithmetischer oder Aufzählungstyp sind, muss jeder der Operatoren
trueergeben, wenn die angegebene Beziehung wahr ist, undfalse, wenn sie falsch ist.
C ++ 14 Standard, [basic.fundamental] / 4 (Grundtypen)
Vorzeichenlose Ganzzahlen müssen den Gesetzen der arithmetischen Modulo 2n folgen, wobei n die Anzahl der Bits in der Wertdarstellung dieser bestimmten Ganzzahl ist.
Dann könnte man auch beweisen, dass ({ true , false }, && , || ) auch isomorph zu boolescher Arithmetik ist, indem man den Text in [expr.log.and]
und [expr.log.or]
Ich denke nicht, dass Sie weiter gehen sollten, als zu zeigen, dass es diesen Isomorphismus gibt, denn weiter würde bedeuten, Axiome zu demonstrieren.
Es scheint mir, dass die einfachste Lösung ist, dies rückwärts zu beweisen. Wenn das erste Argument für f das maximale Argument ist, beweisen Sie, dass das erste Argument zurückgegeben wird (relativ einfach - das maximale Argument a ist definitionsgemäß größer als b ). Wenn das zweite Argument das maximale Argument ist, beweisen Sie, dass das zweite Argument zurückgegeben wird. Wenn die beiden gleich sind, zeige, dass es kein eindeutiges maximales Element gibt, also ist das zweite Argument immer noch ein maximales Argument.
Beweisen Sie abschließend, dass diese drei Optionen vollständig sind. Wenn ein eindeutiges maximales Argument übergeben wird, muss es entweder als erstes oder zweites Argument übergeben werden, da f binär ist.
Ich bin unsicher was du willst. Betrachtet man eine frühere Version, N3337, können wir leicht erkennen, dass fast alles spezifiziert ist:
Sie versuchen jedoch, mit f (expr_a, expr_b) zu beginnen; und die Bewertung der Argumente für f erfordert möglicherweise viel mehr; vor allem, weil sie nicht sequenziert sind - und könnte jeder Funktion-Aufruf sein.
Tags und Links c++ coq static-analysis proof-of-correctness