Hispanopedia Wiki
Articulo de referencia

Tipo dependiente

En informática y lógica , un tipo dependiente es aquel cuya definición depende de un valor. Es una característica común a la teoría de tipos y a los sistemas de tipos . En la te...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática y lógica , un tipo dependiente es aquel cuya definición depende de un valor. Es una característica común a la teoría de tipos y a los sistemas de tipos . En la teoría de tipos intuicionista , los tipos dependientes se utilizan para codificar cuantificadores lógicos como "para todo" y "existe". En lenguajes de programación funcional como Agda , ATS , Rocq (anteriormente conocido como Coq ), F* , Epigram , Idris y Lean , los tipos dependientes ayudan a reducir errores al permitir al programador asignar tipos que restringen aún más el conjunto de posibles implementaciones.

Dos ejemplos comunes de tipos dependientes son las funciones dependientes y los pares dependientes . El tipo de retorno de una función dependiente puede depender del valor (no solo del tipo) de uno de sus argumentos. Por ejemplo, una función que toma un entero positivo.norte{\displaystyle n}puede devolver una matriz de longitudnorte{\displaystyle n}donde la longitud del array forma parte del tipo del array. (Cabe destacar que esto difiere del polimorfismo y la programación genérica , ya que ambos incluyen el tipo como argumento). Un par dependiente puede tener un segundo valor, cuyo tipo depende del primero. Siguiendo con el ejemplo del array, un par dependiente puede utilizarse para emparejar un array con su longitud de forma segura en cuanto a tipos.

Los tipos dependientes añaden complejidad a un sistema de tipos. Decidir la igualdad de tipos dependientes en un programa puede requerir cálculos. Si se permiten valores arbitrarios en los tipos dependientes, entonces decidir la igualdad de tipos puede implicar decidir si dos programas arbitrarios producen el mismo resultado; por lo tanto, la decidibilidad de la verificación de tipos puede depender de la semántica de igualdad de la teoría de tipos dada, es decir, si la teoría de tipos es intensional o extensional . [ 1 ]

Historia

En 1934, Haskell Curry observó que los tipos utilizados en el cálculo lambda tipado , y en su contraparte de lógica combinatoria , seguían el mismo patrón que los axiomas en la lógica proposicional . Más aún, para cada demostración en la lógica, existía una función (término) correspondiente en el lenguaje de programación. Uno de los ejemplos de Curry fue la correspondencia entre el cálculo lambda tipado simple y la lógica intuicionista . [ 2 ]

La lógica de predicados es una extensión de la lógica proposicional, que añade cuantificadores. Howard y de Bruijn extendieron el cálculo lambda para que coincidiera con esta lógica más potente mediante la creación de tipos para funciones dependientes, que corresponden a "para todo", y pares dependientes, que corresponden a "existe". [ 3 ]

Debido a esto, y a otros trabajos de Howard, la noción de proposiciones como tipos se conoce como la correspondencia Curry-Howard .

Definición formal

En la teoría de tipos dependientes, un tipo dependiente es un tipo cuya especificación puede variar con un valor, y puede considerarse análogo a una familia indexada de conjuntos .U{\displaystyle {\mathcal {U}}}denotan un universo de tipos y escribenA:U{\displaystyle A:{\mathcal {U}}}para indicar queA{\displaystyle A}es un tipo enU{\displaystyle {\mathcal {U}}}Por un términoa{\displaystyle a}de tipoA{\displaystyle A}, escribira:A{\displaystyle a:A}. Una familia dependiente de tipos sobreA{\displaystyle A}está escritoB:A→U{\displaystyle B:A\to {\mathcal {U}}}, lo que significa que a cada términoa:A{\displaystyle a:A}La familia asigna un tipoB(a):U{\displaystyle B(a):{\mathcal {U}}}. Por lo tanto, dadoA:U{\displaystyle A:{\mathcal {U}}}yB:A→U{\displaystyle B:A\to {\mathcal {U}}}, la expresiónB(a){\displaystyle B(a)}denota un tipo que depende del valor particulara{\displaystyle a}En la terminología estándar, esto se describe diciendo que el tipoB(a){\displaystyle B(a)}varía cona{\displaystyle a}.

tipo Π

Una función cuyo tipo de valor de retorno varía con su argumento (es decir, no hay un codominio fijo ) es una función dependiente y el tipo de esta función se llama tipo de producto dependiente , tipo pi ( tipo Π ) o tipo de función dependiente . [ 4 ] De una familia de tiposB:A→U{\displaystyle B:A\to {\mathcal {U}}}podemos construir el tipo de funciones dependientes∏incógnita:AB(incógnita){\textstyle \prod _{x:A}B(x)}, cuyos términos son funciones que toman un términoa:A{\displaystyle a:A}y devolver un término enB(a){\displaystyle B(a)}. Para este ejemplo, el tipo de función dependiente se escribe normalmente como∏incógnita:AB(incógnita){\textstyle \prod _{x:A}B(x)}o∏(incógnita:A)B(incógnita){\textstyle \prod {(x:A)}B(x)}.

SiB:A→U{\displaystyle B:A\to {\mathcal {U}}}es una función constante, el tipo de producto dependiente correspondiente es equivalente a un tipo de función ordinaria . Es decir,∏incógnita:AB{\textstyle \prod _{x:A}B}es equivalente en cuanto a juicioA→B{\displaystyle A\to B}cuandoB{\displaystyle B}no depende deincógnita{\displaystyle x}.

El nombre "tipo Π" proviene de la idea de que estos pueden considerarse como un producto cartesiano de tipos. Los tipos Π también pueden entenderse como modelos de cuantificadores universales .

Por ejemplo, si escribimosVec⁡(R,norte){\displaystyle \operatorname {Vec} (\mathbb {R} ,n)}para n -tuplas de números reales , entonces∏norte:norteVec⁡(R,norte){\textstyle \prod _{n:\mathbb {N} }\operatorname {Vec} (\mathbb {R} ,n)}Sería el tipo de una función que, dado un número natural n , devuelve una tupla de números reales de tamaño n . El espacio de funciones usual surge como un caso especial cuando el tipo de rango no depende realmente de la entrada. Por ejemplo∏norte:norteR{\textstyle \prod _{n:\mathbb {N} }{\mathbb {R} }}es el tipo de funciones de números naturales a números reales, que se escribe comonorte→R{\displaystyle \mathbb {N} \to \mathbb {R} }en cálculo lambda tipado.

Para un ejemplo más concreto, tomemosA{\displaystyle A}ser del tipo de enteros sin signo del 0 al 255 (los que caben en 8 bits o 1 byte) yB(a)=incógnitaa{\displaystyle B(a)=X_{a}}paraa:A{\displaystyle a:A}, entonces∏incógnita:AB(incógnita){\textstyle \prod _{x:A}B(x)}se convierte en el producto deincógnita0×incógnita1×incógnita2×…×incógnita253×incógnita254×incógnita255{\displaystyle X_{0}\times X_{1}\times X_{2}\times \ldots \times X_{253}\times X_{254}\times X_{255}}.

tipo Σ

El dual del tipo de producto dependiente es el tipo de par dependiente , el tipo de suma dependiente , el tipo sigma o (de forma confusa) el tipo de producto dependiente . [ 4 ] Los tipos sigma también pueden entenderse como cuantificadores existenciales . Continuando con el ejemplo anterior, si, en el universo de tiposU{\displaystyle {\mathcal {U}}}, hay un tipoA:U{\displaystyle A:{\mathcal {U}}}y una familia de tiposB:A→U{\displaystyle B:A\to {\mathcal {U}}}, entonces hay un tipo de par dependiente∑incógnita:AB(incógnita){\textstyle \sum _{x:A}B(x)}(Las notaciones alternativas son similares a las de los tipos Π ).

El tipo de par dependiente captura la idea de un par ordenado donde el tipo del segundo término depende del valor del primero. Si(a,b):∑incógnita:AB(incógnita),{\textstyle (a,b):\sum _{x:A}B(x),}entoncesa:A{\displaystyle a:A}yb:B(a){\displaystyle b:B(a)}. SiB{\displaystyle B}es una función constante, entonces el tipo de par dependiente se convierte (es a juicio igual a) el tipo de producto , es decir, un producto cartesiano ordinarioA×B{\displaystyle A\times B}. [ 4 ]

Para un ejemplo más concreto, tomemosA{\displaystyle A}ser nuevamente de tipo enteros sin signo del 0 al 255, yB(a){\displaystyle B(a)}volver a ser igual aincógnitaa{\displaystyle X_{a}}para 256 más arbitrarioincógnitaa{\displaystyle X_{a}}, entonces∑incógnita:AB(incógnita){\textstyle \sum _{x:A}B(x)}se descompone en la sumaincógnita0+incógnita1+incógnita2+…+incógnita253+incógnita254+incógnita255{\displaystyle X_{0}+X_{1}+X_{2}+\ldots +X_{253}+X_{254}+X_{255}}.

Ejemplo como cuantificación existencial

DejarA:U{\displaystyle A:{\mathcal {U}}}ser de algún tipo, y dejarB:A→U{\displaystyle B:A\to {\mathcal {U}}}. Según la correspondencia Curry-Howard,B{\displaystyle B}puede interpretarse como un predicado lógico en términos deA{\displaystyle A}. Para un dadoa:A{\displaystyle a:A}, ya sea el tipoB(a){\displaystyle B(a)}está habitado indica sia{\displaystyle a}satisface este predicado. La correspondencia puede extenderse a la cuantificación existencial y a pares dependientes: la proposición∃a∈AB(a){\displaystyle \exists {a}{\in }A\,B(a)}es verdadero si y solo si el tipo∑a:AB(a){\textstyle \sum _{a:A}B(a)}está habitado.

Por ejemplo,metro:norte{\displaystyle m:\mathbb {N} }es menor o igual quenorte:norte{\displaystyle n:\mathbb {N} }si y solo si existe otro número naturalk:norte{\displaystyle k:\mathbb {N} }de tal manera quemetro+k=norte{\displaystyle m+k=n}En lógica, esta afirmación se codifica mediante la cuantificación existencial:

metro≤norte⟺∃k∈nortemetro+k=norte.{\displaystyle m\leq n\iff \exists {k}{\in }\mathbb {N} \,m+k=n.}

Esta proposición corresponde al tipo de par dependiente:

∑k:nortemetro+k=norte.{\displaystyle \sum _{k:\mathbb {N} }m+k=n.}

Es decir, una prueba de la afirmación de quemetro{\displaystyle m}es menor o igual quenorte{\displaystyle n}es un par que contiene un número no negativok{\displaystyle k}, que es la diferencia entremetro{\displaystyle m}ynorte{\displaystyle n}y una prueba de la igualdadmetro+k=norte{\displaystyle m+k=n}.

Sistemas del cubo lambda

Henk Barendregt desarrolló el cubo lambda como un medio para clasificar los sistemas de tipos a lo largo de tres ejes. Los ocho vértices del diagrama resultante, con forma de cubo, corresponden a un sistema de tipos, con el cálculo lambda de tipos simples en el vértice menos expresivo y el cálculo de construcciones en el más expresivo. Los tres ejes del cubo corresponden a tres aumentos diferentes del cálculo lambda de tipos simples: la adición de tipos dependientes, la adición de polimorfismo y la adición de constructores de tipos de orden superior (funciones de tipos a tipos, por ejemplo). El cubo lambda se generaliza aún más mediante sistemas de tipos puros .

Teoría de tipos dependientes de primer orden

El sistemaλΠ{\displaystyle \lambda \Pi }de tipos dependientes de primer orden puros, que corresponden al marco lógico LF , se obtiene generalizando el tipo de espacio de funciones del cálculo lambda simplemente tipado al tipo de producto dependiente.

Teoría de tipos dependientes de segundo orden

El sistemaλΠ2{\displaystyle \lambda \Pi 2}de tipos dependientes de segundo orden se obtiene deλΠ{\displaystyle \lambda \Pi }al permitir la cuantificación sobre constructores de tipos. En esta teoría, el operador de producto dependiente engloba tanto el→{\displaystyle \to }operador del cálculo lambda simplemente tipado y el∀{\displaystyle \forall }ligante del Sistema F.

Cálculo lambda polimórfico de orden superior con tipos dependientes

El sistema de orden superiorλΠω{\displaystyle \lambda \Pi \omega }extiendeλΠ2{\displaystyle \lambda \Pi 2}a las cuatro formas de abstracción del cubo lambda : funciones de términos a términos, de tipos a tipos, de términos a tipos y de tipos a términos. El sistema corresponde al cálculo de construcciones, cuya derivada, el cálculo de construcciones inductivas, es el sistema subyacente de Rocq.

Lenguaje de programación y lógica simultáneos

La correspondencia de Curry-Howard implica que se pueden construir tipos que expresen propiedades matemáticas de complejidad arbitraria. Si el usuario puede proporcionar una prueba constructiva de que un tipo está habitado (es decir, que existe un valor de ese tipo), un compilador puede verificar la prueba y convertirla en código ejecutable que calcule el valor mediante la construcción. La función de verificación de pruebas hace que los lenguajes con tipado dependiente estén estrechamente relacionados con los asistentes de prueba . El aspecto de generación de código proporciona un enfoque potente para la verificación formal de programas y el código portador de pruebas , ya que el código se deriva directamente de una prueba matemática verificada mecánicamente.

Comparación de lenguajes con tipos dependientes

  1. ↑ Esto se refiere al lenguaje central , no a ninguna táctica ( procedimiento de demostración de teoremas ) ni a ningún sublenguaje de generación de código.
  2. ↑ Sujeto a restricciones semánticas, como las restricciones del universo.
  3. ↑ Solucionador de anillos [ 6 ]
  4. ↑ Universos opcionales, polimorfismo de universos opcionales y universos opcionales especificados explícitamente
  5. ↑ Universos, restricciones de universo inferidas automáticamente (no es lo mismo que el polimorfismo de universo de Agda) e impresión explícita opcional de las restricciones de universo.
  6. ↑ Ha sido reemplazado por ATS
  7. ↑ El último documento de Sage y la última instantánea del código datan de 2006.

Véase también

Referencias

  1. ↑ Hofmann, Martin (1995), Conceptos extensionales en la teoría de tipos intensionales (PDF)
  2. ↑ Sørensen, Morten Heine B.; Urzyczyn, Pawel (1998), Lecciones sobre el isomorfismo de Curry-Howard , CiteSeerX 10.1.1.17.7385 
  3. ↑ Bove, Ana; Dybjer, Peter (2008). Tipos dependientes en el trabajo (PDF) (Informe). Universidad Tecnológica de Chalmers.
  4. 1 2 3 Altenkirch, Thorsten; Danielsson, Nils Anders; Löh, Andres; Oury, Nicolas (2010). "ΠΣ: Dependent Types without the Sugar" (PDF) . En Blume, Matthias; Kobayashi, Naoki; Vidal, Germán (eds.). Functional and Logic Programming, 10th International Symposium, FLOPS 2010, Sendai, Japón, 19-21 de abril de 2010. Actas . Lecture Notes in Computer Science. Vol. 6009. Springer. pp. 40– 55. doi : 10.1007/978-3-642-12251-4_5 .  
  5. ↑ "Página de descarga de Agda" .
  6. ↑ "Solucionador de anillos Agda" .
  7. 1 2 "Anuncio: Agda 2.2.8" . Archivado del original el 18 de julio de 2011. Recuperado el 28 de septiembre de 2010 .
  8. ↑ "Registro de cambios de Agda 2.6.0" .
  9. ↑ "Descargas de ATS2" .
  10. ↑ "Correo electrónico del inventor de ATS, Hongwei Xi" .
  11. ↑ Xi, Hongwei (marzo de 2017). "Sistema de tipos aplicado: un enfoque para la programación práctica con demostración de teoremas" (PDF) . arXiv : 1703.08683 .
  12. ↑ "Cambios de Coq en el repositorio Subversion" .
  13. ↑ "Introducción de SProp en Coq 8.10" .
  14. ↑ "F* cambia en GitHub" . GitHub .
  15. ↑ "Notas de la versión F* v0.9.5.0 en GitHub" . GitHub .
  16. ↑ "Guru SVN" .
  17. 1 2 Aaron Stump (6 de abril de 2009). "Programación verificada en Guru" (PDF) . Archivado del original (PDF) el 29 de diciembre de 2009. Recuperado el 28 de septiembre de 2010 .
  18. ↑ Petcher, Adam (mayo de 2008). Decidiendo la unibilidad módulo ecuaciones fundamentales en la teoría de tipos operacionales (PDF) (MSc). Universidad de Washington . Recuperado el 14 de octubre de 2010 .
  19. ↑ "Repositorio git de Idris" . GitHub . 17 de mayo de 2022.
  20. ↑ Brady, Edwin. "Idris, un lenguaje con tipos dependientes — resumen extendido" (PDF) . CiteSeerX 10.1.1.150.9442 . 
  21. ↑ "Matita SVN" . Archivado del original el 8 de mayo de 2006. Consultado el 29 de septiembre de 2010 .

Lecturas adicionales

  • Martin-Löf, Per (1984). Teoría de tipos intuicionista (PDF) . Bibliopolis.
  • Nordström, Bengt; Petersson, Kent; Smith, enero M. (1990). Programación en la teoría de tipos de Martin-Löf: una introducción . Prensa de la Universidad de Oxford. ISBN 9780198538141.
  • Barendregt, H. (1992). "Cálculos lambda con tipos" . En Abramsky, S.; Gabbay, D.; Maibaum, T. (eds.). Manual de lógica en informática . Oxford Science Publications . doi : 10.1017/CBO9781139032636 . hdl : 2066/17231 .
  • Brandl, Helmut (2022). Cálculo de construcciones
  • McBride, Conor ; McKinna, James (enero de 2004). "La perspectiva desde la izquierda" . Journal of Functional Programming . 14 (1): 69–111 . doi : 10.1017/s0956796803004829 . S2CID 6232997 . 
  • Altenkirch, Thorsten ; McBride, Conor ; McKinna, James (2006). «Por qué importan los tipos dependientes» (PDF) . Actas del 33.er Simposio ACM SIGPLAN-SIGACT sobre Principios de Lenguajes de Programación, POPL 2006, Charleston, Carolina del Sur, EE. UU., 11-13 de enero . ISBN 1-59593-027-2.
  • Norell, Ulf (septiembre de 2007). Hacia un lenguaje de programación práctico basado en la teoría de tipos dependientes (PDF) (Tesis doctoral). Gotemburgo, Suecia: Departamento de Informática e Ingeniería, Universidad Tecnológica de Chalmers. ISBN 978-91-7291-996-9.
  • Oury, Nicolas; Swierstra, Wouter (2008). "El poder de Pi" (PDF) . ICFP '08: Actas de la 13.ª conferencia internacional ACM SIGPLAN sobre programación funcional . pp. 39–50 . doi : 10.1145/1411204.1411213 . ISBN  9781595939197. S2CID 16176901 . 
  • Norell, Ulf (2009). "Programación escrita de forma dependiente en Agda" (PDF) . En Koopman, P.; Plasmeijer, R.; Swierstra, D. (eds.). Programación funcional avanzada. AFP 2008 . Apuntes de conferencias sobre informática. vol.  5832. Saltador. págs. 230–266 . doi : 10.1007/978-3-642-04652-0_5 . ISBN  978-3-642-04651-3.
  • Sitnikovski, Boro (2018). Introducción sencilla a los tipos dependientes con Idris . Lean Publishing. ISBN 978-1723139413.
  • McBride, Conor ; Nordvall-Forsberg, Fredrik (2022). «Sistemas de tipos para programas que respetan dimensiones» (PDF) . Herramientas matemáticas y computacionales avanzadas en metrología y ensayos XII . Avances en matemáticas para ciencias aplicadas. World Scientific. pp. 331–345 . doi : 10.1142/9789811242380_0020 . ISBN  9789811242380. S2CID 243831207 . 
  • Programación con tipos dependientes 2008
  • Programación con tipos dependientes 2010
  • Programación con tipos dependientes 2011
  • "Tipo dependiente" en la wiki de Haskell
  • Teoría de tipos dependientes en el Laboratorio n
  • tipo dependiente en el laboratorio n
  • tipo de producto dependiente en el laboratorio n
  • tipo de suma dependiente en el laboratorio n
  • producto dependiente en el laboratorio n
  • suma dependiente en el laboratorio n