Question

Étant donné que:

  1. Une langue avec des systèmes de type très expressif (par exemple Idris) peut également avoir des mécanismes d'échappement comme les interfaces de fonction étrangères / dangeperformio.
  2. Il existe des assistants de preuve qui peuvent être utilisés pour prouver certaines propriétés d'un programme écrit dans une langue qui n'a pas de système de type capable d'exprimer ces propriétés.
  3. La correspondance Curry - Howard montre qu'une implémentation de type réussi d'une fonction avec un type donné est la preuve de ce qui est exprimé par ce type.

Peut-on exprimer des preuves non triviales de certaines propriétés du code de la langue étrangère dans le système de type de la langue maternelle?

Par exemple, faites semblant d'avoir une fonction C appelée stable_qsort qui trie les nombres d'une manière terriblement intelligente et efficace tout en maintenant l'ordre d'éléments déjà égaux, et un programme IDRIS qui appelle stable_qsort via son FFI, mais je ne fais pas confiance à ce problème relativement obscur C fonction. Puis-je prouver que la fonction ne réorganise pas les éléments égaux, pour toutes les entrées, dans mon code IDRIS au lieu d'utiliser un assistant de preuve distinct?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top