Quel est le formalisme de prouver les instructions sur l'originalité des fonctions avec certaines signatures

Question

Supposons que je veux une fonction comme

f: ((A, B) -> C) -> A -> B -> C

Une affirmation que j'ai souvent vu que f n'a qu'une seule mise en œuvre, à savoir le "curry de fonction", c'est à dire g => a => b => g(a, b)

Pris à leur valeur nominale, cela ne semble pas être réellement vrai, je peux toujours définir un f à agir différemment de ce que dans des cas spéciaux, par exempleJe peux dire que c'est g => a => b => g(a, b) sauf quand A = B puis-je définir comme g => a => b => g(b, a).

Néanmoins, il est intuitivement assez claire de ce que l'on entend par "a juste une mise en œuvre".

Je voudrais savoir le bon formalisme dans lequel les instructions comme ci-dessus peut être prouvé.

À l'suppose que je soupçonne que c'est la catégorie de la théorie?Le ci-dessus se sent un peu comme la notion de transformation naturelle, mais je ne vois pas vraiment les détails.

Answer 1

Je suis sûr qu'il y est un lien vers la catégorie de la théorie, mais vous pouvez réellement faire avec (ce que je considère être ) un outil plus simple:parametricity.

Ils l'idée de base est que, quand une langue a la propriété de types polymorphes faire exactement la même chose pour chaque type ils sont instanciés (par exemple,il n'y a pas typecase de construire), nous pouvons le prouver très puissantes propriétés propos de la langue, sous la forme d'une relation logique.

Cela empêche exactement le "cas particulier" de la mise en œuvre de ce que vous décrivez dans votre question.Il est également intéressant de mentionner que ces implémentations sont tous extensionally l'égalité:ils peuvent sembler différentes, mais de produire des résultats égaux pour l'égalité des entrées.par exemplevous pouvez remplacer n'importe quel terme $t$ avec $(\lambda x \ldotp x) t $ et d'obtenir une fonction équivalente.

Les déclarations au sujet des fonctions uniquement à partir de leur type sont généralement appelés gratuit théorème, nommé d'après le document, qui a introduit l'idée: Théorèmes Gratuitement par Phil Wadler.Si vous êtes intéressé à ce domaine, je vous recommande fortement le livre, car c'est une bonne introduction au sujet.

L'idée derrière cela va beaucoup plus loin que celle du papier, de John Reynolds travail avec le Système F et l ' "abstraction théorème", mais il a fallu un certain temps avant que l'idée est devenue populaire.

Vous pouvez effectivement générer des théorèmes à http://free-theorems.nomeata.de/, bien qu'il puisse prendre un peu de masser pour obtenir de l'information utile sur les théorèmes qu'ils donnent là.

Si vous êtes intéressé par parametricity utilisé pour prouver d'autres choses que de gratuit théorèmes, comme le type de sécurité, puis Amal Ahmed thèse est la meilleure introduction que j'ai vu.Elle a vraiment fait un bon travail de description de la sémantique des types:le type de programme est en fait une propriété de la façon dont il fonctionne et ce qu'elle produit, et ce que nous appelons les "types" sont syntaxique, le rapprochement de ces plus général de la sémantique des types.