Ist es möglich zu berechnen, ob zwei Funktionen in der Erweiterung gleich sind?

9

Wenn Sie zwei Funktionen haben, die einen unterschiedlichen Sortieralgorithmus implementieren, können Sie dann anhand des Quellcodes schließen, dass beide dieselben externen Eigenschaften haben? Bedeutet das, dass beide eine mögliche unsortierte Sequenz als Eingabe und eine sortierte Sequenz als Ausgabe haben? Wie könnten diese externen Eigenschaften durch den Quellcode bestimmt werden? Und wie würden Sie diese externen Eigenschaften beschreiben? Welche Notation würde verwendet?

Die externen Eigenschaften könnten bekannt gemacht werden, indem sie explizit definiert werden, beispielsweise innerhalb eines Typsystems, aber ich frage mich, ob dies implizit erfolgen könnte. Oder ist es theoretisch unmöglich, auf diese Art von Semantik zu schließen? Ich bin daran interessiert, ob dies für beliebige Funktionen möglich ist, nicht nur für Sortieralgorithmen, vorausgesetzt, Dinge wie Funktionen werden immer angehalten und haben keine Nebenwirkungen.

Sollte ich mir die Denotationssemantik ansehen oder ist sie nicht verwandt?

Ich interessiere mich für Hinweise auf die Forschung in diesem Bereich und für verschiedene Begriffe, die zur Beschreibung des Themas verwendet werden, das meiner Literatursuche helfen könnte.

Matthijs Steen
quelle

Antworten:

8

Ja. Wenn Sie überprüfen können, ob sie identisch sind, kann dies auch ein Computer tun.

Hier ist eine kurze Spezifikation für eine ganzzahlige Sortierung in Coq:

Inductive natlist : Type :=
| nil : natlist
| cons : nat → natlist → natlist.

Fixpoint is_sorted (l : natlist ) : bool :=
    match l with
    |  nil => true
    |  (cons x nil) => true
    |  (cons x (cons y r)) => if x <= y then is_sorted (cons y r) else false
    end.

...

Theorem sort_spec : forall l, is_sorted (sort_list l).

Eine Spezifikation kann mit abhängigen Typen direkt in die Sortierdeklaration codiert werden.

Für dieses spezielle Problem hat John Darlington in den 70er Jahren gezeigt, dass 6 Familien von Sortieralgorithmen abgeleitet werden können, indem die Spezifikation einer Sortierung mechanisch in eine Implementierung umgewandelt wird. Ich glaube, dies wird unter dem Namen "semantikbasierte Programmableitung" geführt.

In der Welt der Softwareentwicklung wird das Auffinden von äquivalent äquivalenten Funktionen als "semantische Klonerkennung" bezeichnet.

Dave Clarke gab auch eine gute Antwort auf diese Frage im CS StackExchange: /cs/2059/how-do-you-check-if-two-algorithms-return-the-same-result -für-jede-Eingabe

Dies alles fällt unter das Dach formaler Methoden und Programmiersprachen . Denotationale Semantik ist eine Klasse von Techniken zur Modellierung der Semantik, aber sie sind in Ungnade gefallen, weil sie im Vergleich zur operativen Semantik schwierig zu verwenden sind.

James Koppel
quelle
Danke für die Antwort! Genau das habe ich gesucht.
Matthijs Steen
4
Ich bin mit der Aussage, dass die Denotationssemantik "in Ungnade gefallen" ist, überhaupt nicht einverstanden. Das hängt weitgehend davon ab, wen Sie fragen.
Andrej Bauer
5

Die erweiterte Gleichheit bei der Erstellung vollständiger Programmiersprachen ist im Allgemeinen unentscheidbar. Dies sollte Sie jedoch nicht daran hindern, zu überprüfen oder zu verfälschen, ob zwei bestimmte Funktionen weitgehend gleich sind.

f=Gxα.f(x)=G(x)fGαβ

Martin Berger
quelle
Danke für die Antwort. Ich werde mich mit der Hoare-Logik befassen. Ist die Denotationssemantik im Vergleich zur Hoare-Logik schwer zu definieren, oder ist sie für die meisten Sprachen nur weniger geeignet? Ist die Erweiterungsgleichheit aufgrund des Halteproblems im Allgemeinen unentscheidbar? Wenn Funktionen dann immer anhalten würden, wie in total funktionalen Sprachen, wäre es dann nicht generell entscheidbar? Oder gibt es andere Gründe, im Allgemeinen unentscheidbar zu sein?
Matthijs Steen
P.0
... hat eine entscheidbare kontextuelle Gleichheit. Beachten Sie jedoch, dass R. Loader gezeigt hat, dass selbst die endgültige PCF eine unentscheidbare kontextbezogene Äquivalenz aufweist.
Martin Berger
-2

Eine schnelle Antwort (ich gebe zu, ich habe nicht viel Zeit verbracht ...) Der Reissatz besagt, dass es für jede nicht triviale Frage unentscheidbar ist zu sagen, ob die von einem Programm berechnete Funktion die Eigenschaft hat oder nicht. Daher ist die Frage hier unentscheidbar

normaler Typ
quelle
1
Gibt es nicht "... für eine nicht triviale Eigenschaft von Teilfunktionen ..." an, wäre es also möglicherweise nicht für Gesamtfunktionen entscheidbar?
Matthijs Steen