Comment prouver que le remplacement d'un caractère dans une chaîne dans C et JavaScript est équivalent?

Question

Je voudrais essayer des preuves différentes, en particulier dans la preuve de l'équivalence de la mise en œuvre d'une certaine caractéristique dans deux langages de programmation différentes (C et JS dans cette question).

Il s'agit de prouver que remplace un caractère dans une chaîne est équivalent dans C et JS.

dans JS, par exemple, Les chaînes sont immuables , tandis que dans C, Les chaînes sont mutables . Donc, dans JS, vous devrez peut-être faire cela:

functioni replaceAt(string, index, replacement) {
  return string.substr(0, index) + replacement + string.substr(index + replacement.length)
}

tandis que dans C, vous pourriez juste faire quelque chose comme ceci:

#include<stdio.h>

int
main() {
  char string[11] = "hello world";
  string[1] = 'i';
  printf("%s", string);
  return 0;
}

Fondamentalement, j'essaie de trouver un exemple où, l'effet perçu ou le résultat souhaité est à toutes fins utiles < fort> le même . C'est-à-dire que le résultat final est que le caractère a été remplacé à une position spécifique (la même position dans chaque langue). Même si dans une langue, la chaîne était mutable , tandis que dans l'autre, c'était immuable . Qu'est-ce qui doit être pris en compte ici pour faire une preuve dire que celles-ci sont équivalentes? Comment pouvons-nous capturer la notion d'équivalence partielle ou «équivalence perçue»? (Par là, je veux dire, le résultat est à peu près la même chose, nous souhaitons donc faire une déclaration de preuve que celles-ci sont les mêmes en ce qui concerne certaines spécifications).

Answer 1

Je commencerais par créer une définition formelle de la fonction que vous souhaitez, puis prouvant l'exactitude chacune des implémentations.

Considérez la définition axiomatique suivante:

$$ remplacement: chaîne * \ mathbb z * char \ to string $$

$$ \ Forall C: Char. (\ Forall i \ in \ mathbb z ~. ~ Remplacement (`` `, i, c)=` `) $$

$$ \ Forall C: Char. (\ Forall s: string. (\ Forall i \ in 0 .. Len (s) -1 ~. ~ Remplacement (S, I, C) [I]= c)) $$

$$ \ Forall C: Char. (\ Forall s: string. (\ Forall i \ in 0 .. len (s) -1 ~. ~ len (S, i, c))= Len (s))) $$ < / p>

$$ \ Forall c: char. (\ Forall s: chaîne. (\ Forall i, j \ in 0.Len (s) -1. I \ NEQ J \ implique de remplacement (s, i, c) [j]= s [j])) $$

$$ \ Forall c: Char. (\ Forall s: chaîne. (\ Forall i \ in \ mathbb z. I \ geq len (s) \ implique de remplacement , i, c)= s) $$

Si vous pouvez prouver l'exactitude de chaque implémentation à ces axiomes, je dirais qu'ils sont équivalents. Pour le moment, votre implémentation C n'est même pas une fonction. Votre fonction javascript prend une chaîne et non un caractère. Aucun d'entre eux n'est défini pour les index supérieurs à votre entrée.

Je ne pense pas que la comparaison de la mise en œuvre à la mise en œuvre a du sens, car il existe de nombreuses différences dans les modèles de mise en œuvre de chaque langue.