Wie beweisen Sie, dass das Ersetzen eines Zeichens in einer Zeichenfolge in beiden C und JavaScript gleichwertig ist?

Question

Ich möchte verschiedene Proofs probieren, insbesondere bei der Nachweis der Gleichwertigkeit der Implementierung einiger Funktion in zwei verschiedenen Programmiersprachen (C und JS in dieser Frage).

Dies geht darum, dass das ein Zeichen in einer Zeichenfolge in c und js äquivalent ist.

in js, zum Beispiel Saiten sind unveränderlich , während in c Saiten sind veränderbar . Also in JS müssen Sie dies möglicherweise tun:

generasacodicetagpre.

Während in c vielleicht etwas so etwas tun:

generasacodicetagpre.

Grundsätzlich versuche ich, ein Beispiel zu finden, bei dem der wahrgenommene Effekt oder gewünschtes Ergebnis für alle Absichten und Zwecke ist < stark> das gleiche . Das heißt, das Endergebnis ist, dass das Zeichen an einer bestimmten Position (derselben Position in jeder Sprache) ersetzt wurde. Obwohl in einer Sprache die Zeichenfolge umstechbar war , während in der anderen, war es unveränderlich . Was muss hier berücksichtigt werden, um einen Beweis dafür zu machen, dass diese gleichwertig sind? Wie erfassen wir den Begriff der "partiellen Äquivalenz" oder "wahrgenommenen Äquivalenz"? (Dadurch meine ich, das Ergebnis ist ungefähr gleich, daher wollen wir eine Beweisaussage erstellen, dass dies in Bezug auf ein gewisses Spezell ist).

Answer 1

Ich würde beginnen, indem Sie eine formale Definition der Funktion erstellen, die Sie wünschen und dann die Richtigkeit jeder der Implementierungen nachweisen.

Betrachten Sie die folgende axiomatische Definition:

$$ Ersetzene: String * \ mathbb z * char \ to string $$

$$ FORALL C: CHAR. (\ FORALL I \ IN \ MATHBB Z ~. ~ ersetzen (``, i, c)= `` `) $$

$$ FORALL C: CHAR. (\ FORALL S: String. (\ FORALL I \ IN 0 .. Len (S) -1 ~. ~ Ersetzen (S, I, C) [I]= C)) $$

$$ FORALL C: CHAR. (\ FORALL S: String. (\ Vorall I \ in 0 .. Len (S) -1 ~. len (ersetzen (S, I, C))= len (s))) $$ < / p>

$$ \ FORALL C: CHAR. (\ FORALL S: String. (\ FORALL I, J \ IN 0..LEN (S) -1. I \ NEQ J \ Impliziert Ersetze (S, I, C) [J]= S [J])) $$

$$ \ FORALL C: CHAR. (\ FORALL S: String. (\ Vorall I \ in \ mathbb z. i \ geq len (s) \ Impliziert ersetzte (s , i, c)= s)) $$

Wenn Sie die Richtigkeit jeder Implementierung an diesen Axiomen nachweisen können, würde ich sagen, dass sie gleichwertig sind. Im Moment ist Ihre c implementierung nicht einmal eine Funktion. Ihre javascript -funktion nimmt eine Zeichenfolge und nicht ein Zeichen. Keiner von ihnen ist für Indizes, die größer als Ihre Eingabe sind, definiert.

Ich denke nicht, dass der Vergleich der Implementierung der Implementierung einen Sinn macht, da es in den Implementierungsmodellen jeder Sprache viele Unterschiede gibt.