Comment dériver des éliminateurs typés de manière dépendante?

10

Dans la programmation de type dépendant, il existe deux façons principales de décomposer les données et d'effectuer la récursivité:

  • Correspondance de modèle dépendante : les définitions de fonction sont données sous forme de clauses multiples. L'unification garantit que tous les cas omis sont impossibles, et un solveur externe garantit que la récursivité est bien fondée.
  • Eliminators : Chaque type de données inductif a une constante associée , qui agit en tant que principe d'induction, et que la fonction récursive qui décompose les valeurs de type . Celles-ci sont plus verbeuses, mais ont l'avantage d'être totales (tous les cas sont couverts par ) et de se terminer par construction.réEréréEré

J'ai vu des éliminateurs pour les types de données courants, comme , où l'éliminateur est essentiellement une induction mathématique, ou , où l'éliminateur est essentiellement un pli.NunetLjest

J'ai lu plusieurs articles sur la correspondance de modèles dépendants, et beaucoup se réfèrent à des théories de types dans lesquelles les types de données peuvent être définis, et les éliminateurs sont fournis par la théorie. Par exemple, L' élimination Pattern Matching charge décrit comment UTT est basé sur éliminateurs et comment appariement de formes peut être converti en l' élimination en présence d'axiome . Ma compréhension est que, une fois qu'un type de données est défini, la théorie fournit l'éliminateur.K

Ce que je n'ai pas trouvé (ou du moins, je n'ai pas reconnu si je l'ai vu) est une bonne description de la façon dont on peut dériver les éliminateurs, à la fois leurs types et leur sémantique.

Quelqu'un peut-il m'indiquer une référence qui décrit comment obtenir un éliminateur à partir de la définition d'un type de données?

reference-request recursion type-theory dependent-types inductive-datatypes jmite
la source
Je suis sûr qu'il y a une description dans le calcul des constructions ou dans la littérature Coq (pour les types strictement positifs - les éliminateurs de Coq sur les types plus complexes ne sont pas complètement généraux).
Gilles 'SO- arrête d'être méchant'
@ Gilles Ma compréhension était que Coq n'utilisait pas d'éliminateurs, mais utilisait à la place des opérateurs de correspondance et de correction (protégés).
jmite
3
Le langage principal n'utilise pas d'éliminateurs, mais lorsque vous définissez un type, Coq génère un éliminateur qui est défini en termes de fixet match. Je n'ai pas de référence à portée de main, mais je sais que j'ai lu quelque chose sur la façon dont cet éliminateur est généré. cs.stackexchange.com/questions/104/… peut être intéressant.
Gilles 'SO- arrête d'être méchant'
Pour tout type inductif T, Coq définit un principe d'induction T_indqui est un éliminateur dépendant. Ceci est défini en termes de récursivité et d'appariement de motifs, mais vous pouvez en principe le supposer comme une nouvelle constante ayant le même type (avec la même sémantique).
chi

Réponses:

8

La référence canonique pour cela est Peter Dybjer, Inductive Families , qui donne un traitement assez complet des familles inductives basées sur des éliminateurs.

cody
la source
6

Vous pourriez trouver certains de nos articles récents à ce sujet utiles, car nous dérivons des éliminateurs pour les types de données encodés en lambda. Par exemple, voir celui- ci pour la dérivation générique des éliminateurs, et celui- ci pour la technique de base appliquée uniquement au type Nat.

Aaron Stump
la source