Comment prouver un effet secondaire dans une fonction

Question

J'ai posé une question plus tôt sur Enregistrer dans la base de données, ce qui était très général et sur les exigences pour une preuve lorsque vous passez par de nombreuses couches de systèmes non vérifiés tels que le réseau et les bases de données.

Dans cette question, je me demande une preuve plus de niveau intermédiaire, cette fois sur la transformation d'un objet $ f: a to b $ avec l'effet secondaire $ c $. Disons que j'ai comme entrée une chaîne $ a $, et comme sortie Syntaxe abstrait (Ast) $ b $. Tout cela se produit en mémoire avec une petite chaîne de quelques Ko. À l'heure actuelle, ignorer tous les détails de l'implémentation matérielle et tous les détails d'une langue particulière.

Je me demande un niveau élevé ce qu'il faut pour prouver quelque chose comme ça. Plus précisément, je voulais me concentrer sur Effets secondaires dans cette question. Disons pendant le processus d'analyse, nous créons un global table de symbole pour stocker des cours. Ensuite, comme nous analysons le code et que nous rencontrons la classe, nous ajoutons à la table des symboles. Donc, au lieu de $ f: a à b $, nous avons vraiment:

begin {align} f: a & to b & downarrow & c end {align}

C'est-à-dire pour le tableau des symboles $ C $ et la sortie AST $ B $. Quelque part dans l'implémentation de la fonction $ f $, il existe une autre fonction $ g: {c, c } à c '$, qui ajoute le nouveau symbole $ c $ à $ c $.

Ce que je voudrais prouver (dans cette question, juste à un niveau élevé, certains points clés), c'est que la fonction génère le tableau des symboles $ C $, même si le production de la fonction est l'AST $ B $. Dans la théorie des types, la preuve de AST $ B $ pourrait être simplement la séquence des définitions et transformations de types, Similaire à Hoare Logic. Mais pour prouver que la fonction $ f $ a un effet secondaire $ c $ semble beaucoup plus difficile / plus délicat.

Il semble que vous deviez faire passer l'algorithme une étape à la fois, et (en supposant que tout est fortement tapé), déterminez à quoi ressemblerait «l'état actuel» à ce moment-là (de l'ensemble du programme). Alors vous compareriez votre motif (L'affirmation de la condition post-condition si elle était Hoare Logic) avec l'état actuel du programme à ce stade, et voyez s'il s'agissait d'un match. Et voyez si cela est resté vrai jusqu'à la fin de la fonction / algorithme. Mais ce genre de Vérification du modèle, dont je ne connais que les bases, je ne sais pas si c'est correct de supposer. De plus, cette marche à une étape à travers l'algorithme semble être programme simulation, Je me demande si c'est vrai ou non ou si la simulation a un rôle ici.

Je me demande donc, à un niveau élevé, ce qui est nécessaire pour prouver que la fonction $ f $ génère un effet secondaire $ c $. En tant que spécification, j'écrirais "$ f $ génère le tableau de symboles $ C $".