¿Cómo derivar eliminadores de tipo dependiente?

10

En la programación de tipo dependiente, hay dos formas principales de descomponer datos y realizar recursividad:

  • Dependencia de patrones dependientes : las definiciones de funciones se dan como múltiples cláusulas. La unificación asegura que todos los casos omitidos son imposibles, y un solucionador externo asegura que la recursión esté bien fundada.
  • Eliminadores : Cada tipo de datos inductiva tiene una constante asociada , que actúa como un principio de inducción, y como función recursiva que se descompone valores de tipo . Estos son más detallados, pero tienen la ventaja de ser totales (todos los casos están cubiertos por ) y terminar por construcción.remireremire

He visto eliminadores para tipos de datos comunes, como , donde el eliminador es básicamente una inducción matemática, o , donde el eliminador es básicamente un pliegue.norteuntLyost

He estado leyendo varios artículos sobre coincidencia de patrones dependientes, y muchos se refieren a teorías de tipos en las que se pueden definir tipos de datos, y la teoría proporciona los eliminadores. Por ejemplo, eliminación de coincidencia de patrones Dependiente describe cómo UTT se basa en los eliminadores, y cómo la coincidencia de patrones se puede convertir a la eliminación en presencia de axioma . Entiendo que, una vez que se define un tipo de datos, la teoría proporciona el eliminador.K

Lo que no he encontrado (o al menos, no he reconocido si lo he visto) es una buena descripción de cómo se pueden derivar los eliminadores, tanto sus tipos como su semántica.

¿Alguien puede señalarme una referencia que describa cómo se puede obtener un eliminador de la definición de un tipo de datos?

reference-request recursion type-theory dependent-types inductive-datatypes jmite
fuente
Estoy seguro de que hay una descripción en el cálculo de las construcciones o la literatura de Coq (para tipos estrictamente positivos, los eliminadores de Coq en tipos más complejos no son completamente generales).
Gilles 'SO- deja de ser malvado'
@Gilles Entendí que Coq no usaba eliminadores, sino que usaba operadores separados y de reparación (resguardados).
jmite
3
El lenguaje central no usa eliminadores, pero cuando define un tipo, Coq genera un eliminador que se define en términos de fixy match. No tengo una referencia a mano, pero sé que he leído algo sobre cómo se genera este eliminador. cs.stackexchange.com/questions/104/… puede ser de interés.
Gilles 'SO- deja de ser malvado'
Para cualquier tipo inductivo T, Coq define un principio de inducción T_indque es un eliminador dependiente. Esto se define en términos de recurrencia y coincidencia de patrones, pero, en principio, podría suponerse como una nueva constante que tiene el mismo tipo (con la misma semántica).
chi

Respuestas:

8

La referencia canónica para esto es Peter Dybjer, Inductive Families , que ofrece un tratamiento bastante completo de familias inductivas basado en eliminadores.

cody
fuente
6

Puede encontrar algunos de nuestros documentos recientes sobre esto útiles, ya que derivamos eliminadores para los tipos de datos codificados en lambda. Por ejemplo, ver esto uno para la derivación genérica de eliminadores, y esto uno para la técnica básica aplica sólo para el tipo de NAT.

Aaron Stump
fuente