Quand peut-on dire que deux programmes sont différents?

Q1. Quand peut-on dire que deux programmes (écrits dans certains langages de programmation comme C ++) sont différents?

Le premier extrême est de dire que deux programmes sont équivalents s'ils sont identiques. L'autre extrême est de dire que deux programmes sont équivalents s'ils calculent la même fonction (ou montrent le même comportement observable dans des environnements similaires). Mais ce n'est pas bon: tous les programmes vérifiant la primalité ne sont pas identiques. Nous pouvons ajouter une ligne de code sans effet sur le résultat et nous le considérerions toujours comme le même programme.

Q2. Les programmes et algorithmes sont-ils le même type d'objet? Sinon, quelle est la définition d'un algorithme et en quoi diffère-t-elle de la définition d'un programme? Quand peut-on dire que deux algorithmes sont équivalents?

Q1: Il existe de nombreuses notions d'équivalence de programme (équivalence de trace, équivalence contextuelle, équivalence observationnelle, bisimilarité) qui peuvent ou non prendre en compte des éléments tels que le temps, l'utilisation des ressources, le non-déterminisme, la terminaison. Beaucoup de travail a été fait pour trouver des notions utilisables d'équivalence de programme. Par exemple: Théories opérationnelles de l'équivalence des programmes d'Andy Pitts . Mais cela raye à peine la surface. Cela devrait être utile même si vous êtes intéressé lorsque deux programmes ne sont pas équivalents. On peut même raisonner sur des programmes sans interruption (utilisant la bisimulation et la coinduction).

Q2: Une réponse possible à une partie de cette question est que les programmes interactifs ne sont pas des algorithmes (en supposant que l'on considère un algorithme pour prendre toutes ses entrées à la fois, mais cette définition étroite exclut les algorithmes en ligne). Un programme pourrait être un ensemble de processus interactifs qui interagissent également avec leur environnement. Cela ne correspond certainement pas à la notion d'algorithme de la théorie de Turing / machine.

L'autre extrême est de dire que deux programmes sont équivalents s'ils calculent la même fonction (ou montrent le même comportement observable dans des environnements similaires). Mais ce n'est pas bon: tous les programmes vérifiant la primalité ne sont pas identiques. Nous pouvons ajouter une ligne de code sans effet sur le résultat et nous le considérerions toujours comme le même programme.

Ce n'est pas un extrême: l'équivalence de programme doit être définie par rapport à une notion d'observation.

La définition la plus courante dans la recherche sur le PL est l'équivalence contextuelle. Dans l'équivalence contextuelle, l'idée est que nous observons les programmes en les utilisant comme composants de programmes plus importants (le contexte). Donc, si deux programmes calculent la même valeur finale pour tous les contextes, ils sont alors jugés égaux. Étant donné que cette définition quantifie sur tous les contextes de programme possibles, il est difficile de travailler directement avec. Un programme de recherche typique en PL consiste donc à trouver des principes de raisonnement compositionnel qui impliquent une équivalence contextuelle.

Cependant, ce n'est pas la seule notion possible d'observation. Par exemple, nous pouvons facilement dire que la mémoire, le temps ou le comportement de puissance d'un programme sont observables. Dans ce cas, il y a moins d'équivalences de programme, car nous pouvons distinguer plus de programmes (par exemple, mergesort se distingue désormais de quicksort). Si vous voulez (par exemple) concevoir des langages à l'abri des attaques de canaux de synchronisation, ou concevoir des langages de programmation limités par l'espace, alors c'est le genre de chose que vous devez faire.

De plus, nous pouvons choisir de juger certains des états intermédiaires d'un calcul comme observables. Cela se produit toujours pour les langues simultanées, en raison de la possibilité d'interférence. Mais vous voudrez peut-être prendre cette vue même pour les langues séquentielles --- par exemple, si vous voulez vous assurer qu'aucun calcul ne stocke de données non chiffrées dans la mémoire principale, alors vous devez considérer les écritures dans la mémoire principale comme observables.

Fondamentalement, il n'y a pas de notion unique d'équivalence de programme; elle est toujours relative à la notion d'observation que vous choisissez, et cela dépend de l'application que vous envisagez.

Q2: Je pense que les définitions théoriques habituelles ne font pas vraiment de distinction entre les algorithmes et les programmes, mais "algorithme" tel qu'il est couramment utilisé ressemble plus à une classe de programmes. Pour moi, un algorithme est un peu comme un programme dont certains sous-programmes ne sont pas entièrement spécifiés (c'est-à-dire que leur comportement souhaité est défini mais pas leur mise en œuvre). Par exemple, l'algorithme d'élimination gaussien ne spécifie pas vraiment comment la multiplication d'entiers doit être effectuée.

Je suis désolé si c'est naïf. Je ne fais pas de recherche sur le PL.