Teoría de tipos

Concepto en lógica matemática

En matemáticas e informática teórica , una teoría de tipos es la presentación formal de un sistema de tipos específico . ^[a] La teoría de tipos es el estudio académico de los sistemas de tipos.

Algunas teorías tipográficas sirven como alternativas para establecer la teoría como fundamento de las matemáticas . Dos teorías de tipos influyentes que se han propuesto como fundamentos son el cálculo λ tipificado de Alonzo Church y la teoría de tipos intuicionista de Per Martin-Löf .

La mayoría de los sistemas computarizados de redacción de pruebas utilizan una teoría de tipos como base . Uno común es el Cálculo de construcciones inductivas de Thierry Coquand .

Historia

La teoría de tipos se creó para evitar una paradoja en una ecuación matemática basada en la teoría de conjuntos ingenua y la lógica formal . La paradoja de Russell (descrita por primera vez en Los fundamentos de la aritmética de Gottlob Frege ) es que, sin axiomas adecuados, es posible definir el conjunto de todos los conjuntos que no son miembros de sí mismos; este conjunto se contiene a sí mismo y no se contiene a sí mismo. Entre 1902 y 1908, Bertrand Russell propuso varias soluciones a este problema.

En 1908, Russell llegó a una teoría ramificada de tipos junto con un axioma de reducibilidad , los cuales aparecieron en los Principia Mathematica de Whitehead y Russell publicados en 1910, 1912 y 1913. Este sistema evitó las contradicciones sugeridas en la paradoja de Russell al crear una jerarquía de tipos y luego asignar cada entidad matemática concreta a un tipo específico. Las entidades de un tipo determinado se construyeron exclusivamente a partir de subtipos de ese tipo, ^[b] impidiendo así que una entidad se defina utilizando sí misma. Esta resolución de la paradoja de Russell es similar a los enfoques adoptados en otros sistemas formales, como la teoría de conjuntos de Zermelo-Fraenkel . ^[3]

La teoría de tipos es particularmente popular junto con el cálculo lambda de Alonzo Church . Un ejemplo temprano notable de teoría de tipos es el cálculo lambda simplemente tipificado de Church . La teoría de tipos de Church ^[4] ayudó al sistema formal a evitar la paradoja de Kleene-Rosser que afectó al cálculo lambda original sin tipos. Church demostró ^[c] que podía servir como base de las matemáticas y se la denominó lógica de orden superior .

En la literatura moderna, "teoría de tipos" se refiere a un sistema tipificado basado en el cálculo lambda. Un sistema influyente es la teoría de tipos intuicionista de Per Martin-Löf , que fue propuesta como base para las matemáticas constructivas . Otro es el cálculo de construcciones de Thierry Coquand , que Coq , Lean y otros asistentes de pruebas informáticas utilizan como base . La teoría de tipos es un área activa de investigación, una de las cuales es el desarrollo de la teoría de tipos de homotopía .

Aplicaciones

Fundamentos matemáticos

El primer asistente de prueba por computadora, llamado Automath , utilizó la teoría de tipos para codificar matemáticas en una computadora. Martin-Löf desarrolló específicamente la teoría de tipos intuicionista para codificar todas las matemáticas y servir como una nueva base para las matemáticas. Hay investigaciones en curso sobre los fundamentos matemáticos que utilizan la teoría de tipos de homotopía .

Los matemáticos que trabajan en teoría de categorías ya tenían dificultades para trabajar con la base ampliamente aceptada de la teoría de conjuntos de Zermelo-Fraenkel . Esto llevó a propuestas como la Teoría elemental de la categoría de conjuntos (ETCS) de Lawvere. ^[6] La teoría de tipos de homotopía continúa en esta línea utilizando la teoría de tipos. Los investigadores están explorando las conexiones entre los tipos dependientes (especialmente el tipo de identidad) y la topología algebraica (específicamente la homotopía ).

Asistentes de prueba

Gran parte de la investigación actual sobre la teoría de tipos está impulsada por verificadores de pruebas , asistentes de pruebas interactivos y demostradores de teoremas automatizados . La mayoría de estos sistemas utilizan una teoría de tipos como base matemática para codificar pruebas, lo cual no es sorprendente, dada la estrecha conexión entre la teoría de tipos y los lenguajes de programación:

• Twelf utiliza LF , a menudo para definir otras teorías de tipo;
• la familia de demostradores HOL y PVS utilizan muchas teorías de tipos que caen bajo la lógica de orden superior ;
• NuPRL utiliza la teoría de tipos computacionales ;
• el cálculo de construcciones y sus derivados son utilizados por Coq , Matita y Lean ;
• Agda utiliza UTT (Teoría unificada de tipos dependientes de Luo), que es a la vez un lenguaje de programación y un asistente de prueba.

LEGO e Isabelle apoyan muchas teorías de tipos . Isabelle también apoya fundaciones además de las teorías de tipos, como ZFC . Mizar es un ejemplo de un sistema de prueba que solo admite la teoría de conjuntos.

Lenguajes de programación

Cualquier análisis de programa estático , como los algoritmos de verificación de tipos en la fase de análisis semántico del compilador , tiene una conexión con la teoría de tipos. Un buen ejemplo es Agda , un lenguaje de programación que utiliza UTT (Teoría unificada de tipos dependientes de Luo) para su sistema de tipos.

El lenguaje de programación ML fue desarrollado para manipular teorías de tipos (ver LCF ) y su propio sistema de tipos estuvo fuertemente influenciado por ellas.

Lingüística

La teoría de tipos también se usa ampliamente en teorías formales de la semántica de los lenguajes naturales , ^{[7] [8]} especialmente en la gramática Montague ^[9] y sus descendientes. En particular, las gramáticas categoriales y las gramáticas de pregrupo utilizan ampliamente constructores de tipos para definir los tipos ( sustantivo , verbo , etc.) de palabras.

La construcción más común toma los tipos básicos y para individuos y valores de verdad , respectivamente, y define el conjunto de tipos de forma recursiva de la siguiente manera: ${\displaystyle e}$ ${\displaystyle t}$

• si y son tipos, entonces también lo es ; ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \langle a,b\rangle }$
• nada excepto los tipos básicos, y lo que se puede construir a partir de ellos mediante la cláusula anterior son tipos.

Un tipo complejo es el tipo de funciones desde entidades de tipo hasta entidades de tipo . Así, tenemos tipos que se interpretan como elementos del conjunto de funciones desde entidades hasta valores de verdad, es decir, funciones indicadoras de conjuntos de entidades. Una expresión de tipo es una función desde conjuntos de entidades hasta valores de verdad, es decir, una (función indicadora de a) conjunto de conjuntos. Este último tipo se considera estándar como el tipo de cuantificadores del lenguaje natural , como todos o nadie ( Montague 1973, Barwise y Cooper 1981). ^[10] ${\displaystyle \langle a,b\rangle }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \langle e,t\rangle }$ ${\displaystyle \langle \langle e,t\rangle ,t\rangle }$

La teoría de tipos con registros es un marco de representación semántica formal que utiliza registros para expresar tipos de teoría de tipos . Se ha utilizado en el procesamiento del lenguaje natural , principalmente en semántica computacional y sistemas de diálogo . ^{[11] [12]}

Ciencias Sociales

Gregory Bateson introdujo una teoría de tipos lógicos en las ciencias sociales; sus nociones de doble vínculo y niveles lógicos se basan en la teoría de tipos de Russell.

La teoría de tipos como lógica

Una teoría de tipos es una lógica matemática , es decir, una colección de reglas de inferencia que resultan en juicios . La mayoría de las lógicas tienen juicios que afirman "La proposición es verdadera" o "La fórmula es una fórmula bien formada ". ^[13] Una teoría de tipos tiene juicios que definen tipos y los asignan a una colección de objetos formales, conocidos como términos. Un término y su tipo suelen escribirse juntos como . ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \mathrm {term} :{\mathsf {type}}}$

Términos

Un término en lógica se define recursivamente como un símbolo constante , una variable o una aplicación de función , donde un término se aplica a otro término. Los símbolos constantes podrían incluir el número natural , el valor booleano y funciones como la función sucesora y el operador condicional . Por tanto, algunos términos podrían ser , , y . ${\displaystyle 0}$ ${\displaystyle \mathrm {true} }$ ${\displaystyle \mathrm {S} }$ ${\displaystyle \mathrm {if} }$ ${\displaystyle 0}$ ${\displaystyle (\mathrm {S} \,0)}$ ${\displaystyle (\mathrm {S} \,(\mathrm {S} \,0))}$ ${\displaystyle (\mathrm {if} \,\mathrm {true} \,0\,(\mathrm {S} \,0))}$

Juicios

La mayoría de las teorías de tipos tienen 4 juicios:

• " es un tipo" ${\displaystyle T}$
• " es un término de tipo " ${\displaystyle t}$ ${\displaystyle T}$
• "Tipo es igual a tipo " ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$
• "Los términos y ambos de tipo son iguales" ${\displaystyle t_{1}}$ ${\displaystyle t_{2}}$ ${\displaystyle T}$

Los juicios pueden derivarse de suposiciones. Por ejemplo, se podría decir "suponiendo que es un término de tipo y es un término de tipo , se deduce que es un término de tipo ". Tales sentencias se escriben formalmente con el símbolo del torniquete . ${\displaystyle x}$ ${\displaystyle {\mathsf {bool}}}$ ${\displaystyle y}$ ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle (\mathrm {if} \,x\,y\,y)}$ ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle \vdash }$

${\displaystyle x:{\mathsf {bool}},y:{\mathsf {nat}}\vdash ({\textrm {if}}\,x\,y\,y):{\mathsf {nat}}}$

Si no hay suposiciones, no habrá nada a la izquierda del torniquete.

${\displaystyle \vdash \mathrm {S} :{\mathsf {nat}}\to {\mathsf {nat}}}$

La lista de supuestos de la izquierda es el contexto de la sentencia. Las letras mayúsculas griegas, como y , son opciones comunes para representar algunos o todos los supuestos. Por tanto, las cuatro sentencias diferentes suelen redactarse de la siguiente manera. ${\displaystyle \Gamma }$ ${\displaystyle \Delta }$

Algunos libros de texto utilizan un triple signo igual para enfatizar que se trata de igualdad jurídica y, por tanto, de una noción extrínseca de igualdad. ^[14] Las sentencias exigen que todo término tenga un tipo. El tipo restringirá qué reglas se pueden aplicar a un término. ${\displaystyle \equiv }$

Reglas de inferencia

Las reglas de inferencia de una teoría de tipos dicen qué juicios se pueden hacer, basándose en la existencia de otros juicios. Las reglas se expresan como una deducción al estilo Gentzen usando una línea horizontal, con los juicios de entrada requeridos encima de la línea y el juicio resultante debajo de la línea. ^[15] Por ejemplo, la siguiente regla de inferencia establece una regla de sustitución para la igualdad de criterio.

$${\displaystyle {\begin{array}{c}\Gamma \vdash t:T_{1}\qquad \Delta \vdash T_{1}=T_{2}\\\hline \Gamma ,\Delta \vdash t:T_{2}\end{array}}}$$

reescriturametavariables ${\displaystyle \Gamma }$ ${\displaystyle \Delta }$ ${\displaystyle t}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

Para generar un juicio particular en la teoría de tipos, debe haber una regla para generarlo, así como reglas para generar todas las entradas requeridas de esa regla, y así sucesivamente. Las reglas aplicadas forman un árbol de prueba , donde las reglas superiores no necesitan suposiciones. Un ejemplo de una regla que no requiere entradas es aquella que establece el tipo de un término constante. Por ejemplo, para afirmar que existe un término de tipo , se escribiría lo siguiente. ${\displaystyle 0}$ ${\displaystyle {\mathsf {nat}}}$

$${\displaystyle {\begin{array}{c}\hline \vdash 0:nat\\\end{array}}}$$

Tipo habitacion

Generalmente, la conclusión deseada de una prueba en teoría de tipos es la de habitabilidad de tipos . ^[16] El problema de decisión de tipo habitacional (abreviado por ) es: ${\displaystyle \exists t.\Gamma \vdash t:\tau ?}$

Dado un contexto y un tipo , decida si existe un término al que se le pueda asignar el tipo en el entorno de tipos . ${\displaystyle \Gamma }$ ${\displaystyle \tau }$ ${\displaystyle t}$ ${\displaystyle \tau }$ ${\displaystyle \Gamma }$

La paradoja de Girard muestra que la ocupación de tipos está fuertemente relacionada con la coherencia de un sistema de tipos con la correspondencia Curry-Howard. Para ser sólido, tal sistema debe tener tipos deshabitados.

Una teoría de tipos suele tener varias reglas, incluidas algunas para:

• crear un juicio (conocido como contexto en este caso)
• agregar una suposición al contexto ( debilitamiento del contexto )
• reorganizar las suposiciones
• utilizar una suposición para crear una variable
• definir reflexividad , simetría y transitividad para la igualdad de juicio
• definir la sustitución para la aplicación de términos lambda
• enumerar todas las interacciones de igualdad, como la sustitución
• definir una jerarquía de universos de tipo
• afirmar la existencia de nuevos tipos

Además, para cada tipo "por regla", existen 4 tipos diferentes de reglas

• Las reglas de "formación de tipos" dicen cómo crear el tipo.
• Las reglas de "introducción de términos" definen los términos canónicos y las funciones constructoras, como "par" y "S".
• Las reglas de "eliminación de términos" definen las otras funciones como "primera", "segunda" y "R".
• Las reglas de "cálculo" especifican cómo se realiza el cálculo con las funciones específicas del tipo.

Para ver ejemplos de reglas, un lector interesado puede seguir el Apéndice A.2 del libro Teoría de tipos de homotopía ^[14] o leer la Teoría de tipos intuicionista de Martin-Löf. ^[17]

Conexiones a cimientos

El marco lógico de una teoría de tipos se parece a la lógica intuicionista o constructiva. Formalmente, la teoría de tipos se cita a menudo como una implementación de la interpretación de la lógica intuicionista de Brouwer-Heyting-Kolmogorov . ^[17] Además, se pueden establecer conexiones con la teoría de categorías y los programas informáticos .

Lógica intuicionista

Cuando se utilizan como fundamento, ciertos tipos se interpretan como proposiciones (afirmaciones que pueden probarse), y los términos que habitan el tipo se interpretan como pruebas de esa proposición. Cuando algunos tipos se interpretan como proposiciones, existe un conjunto de tipos comunes que se pueden usar para conectarlos y crear un álgebra booleana a partir de tipos. Sin embargo, la lógica no es lógica clásica sino lógica intuicionista , es decir, no tiene ley del tercero excluido ni doble negación .

Según esta interpretación intuicionista, existen tipos comunes que actúan como operadores lógicos:

Como la ley del tercero excluido no se cumple, no existe un término de tipo . Asimismo, la doble negación no se cumple, por lo que no existe un término de tipo . ${\displaystyle \Pi a.A+(A\to \bot )}$ ${\displaystyle \Pi A.((A\to \bot )\to \bot )\to A}$

Es posible incluir la ley del tercero excluido y la doble negación en una teoría de tipos, por regla o supuesto. Sin embargo, es posible que los términos no se calculen hasta los términos canónicos e interferirá con la capacidad de determinar si dos términos son desde el punto de vista igual entre sí. ^{[ cita necesaria ]}

Matemáticas constructivas

Per Martin-Löf propuso su teoría de tipos intuicionista como base para las matemáticas constructivas . ^[13] Las matemáticas constructivas requieren que, al demostrar que "existe un con propiedad ", se debe construir un particular y una prueba de que tiene propiedad . En la teoría de tipos, la existencia se logra utilizando el tipo de producto dependiente y su prueba requiere un término de ese tipo. ${\displaystyle x}$ ${\displaystyle P(x)}$ ${\displaystyle x}$ ${\displaystyle P}$

Un ejemplo de prueba no constructiva es la prueba por contradicción . El primer paso es asumir que eso no existe y refutarlo por contradicción. La conclusión de ese paso es "no es cierto que no exista". El último paso es, por doble negación, concluir que existe. La matemática constructiva no permite el último paso de eliminar la doble negación para concluir que existe. ^[18] ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

La mayoría de las teorías tipo propuestas como fundamentos son constructivas, y esto incluye la mayoría de las utilizadas por los asistentes de prueba. ^{[ cita necesaria ]} Es posible agregar características no constructivas a una teoría de tipos, por regla o suposición. Estos incluyen operadores en continuaciones como llamadas con continuación actual . Sin embargo, estos operadores tienden a romper propiedades deseables como la canonicidad y la parametricidad .

Correspondencia Curry-Howard

La correspondencia Curry-Howard es la similitud observada entre lógicas y lenguajes de programación. La implicación en lógica, "A B" se asemeja a una función del tipo "A" al tipo "B". Para una variedad de lógicas, las reglas son similares a las expresiones en los tipos de un lenguaje de programación. La similitud va más allá, ya que las aplicaciones de las reglas se parecen a programas en lenguajes de programación. Por tanto, la correspondencia se resume a menudo como "pruebas como programas". ${\displaystyle \to }$

La oposición de términos y tipos también puede verse como una oposición de implementación y especificación . Mediante síntesis de programas , (la contraparte computacional de) tipo de habitación se puede utilizar para construir (todos o parte de) programas a partir de la especificación dada en forma de información de tipo. ^[19]

Inferencia de tipos

Muchos programas que trabajan con teoría de tipos (por ejemplo, demostradores de teoremas interactivos) también realizan inferencias de tipos. Les permite seleccionar las reglas que el usuario pretende, con menos acciones por parte del usuario.

Áreas de investigación

Teoría de categorías

Aunque la motivación inicial de la teoría de categorías estaba muy alejada del fundacionalismo, los dos campos resultaron tener conexiones profundas. Como escribe John Lane Bell : "De hecho, las categorías en sí mismas pueden verse como teorías de tipos de cierto tipo; este hecho por sí solo indica que la teoría de tipos está mucho más estrechamente relacionada con la teoría de categorías que con la teoría de conjuntos". En resumen, una categoría puede verse como una teoría de tipos al considerar sus objetos como tipos (o clases), es decir, "en términos generales, se puede pensar en una categoría como una teoría de tipos despojada de su sintaxis". De esta manera se obtienen varios resultados significativos: ^[20]

• las categorías cartesianas cerradas corresponden al cálculo λ tipificado ( Lambek , 1970);
• Los monoides C (categorías con productos y exponenciales y un objeto no terminal) corresponden al cálculo λ sin tipo (observado de forma independiente por Lambek y Dana Scott alrededor de 1980);
• las categorías cerradas localmente cartesianas corresponden a teorías de tipo Martin-Löf (Seely, 1984).

La interacción, conocida como lógica categórica , ha sido objeto de investigación activa desde entonces; véase, por ejemplo, la monografía de Jacobs (1999).

Teoría del tipo de homotopía

La teoría de tipos de homotopía intenta combinar la teoría de tipos y la teoría de categorías. Se centra en las igualdades, especialmente las igualdades entre tipos. La teoría de tipos de homotopía se diferencia de la teoría de tipos intuicionista principalmente por su manejo del tipo de igualdad. En 2016 se propuso la teoría de tipos cúbicos, que es una teoría de tipos de homotopía con normalización. ^{[21] [22]}

Definiciones

Términos y tipos

términos atómicos

Los tipos más básicos se denominan átomos, y un término cuyo tipo es un átomo se conoce como término atómico. Los términos atómicos comunes incluidos en las teorías de tipos son números naturales , a menudo anotados con el tipo , valores lógicos booleanos ( / ), anotados con el tipo , y variables formales , cuyo tipo puede variar. ^[16] Por ejemplo, los siguientes pueden ser términos atómicos. ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle \mathrm {true} }$ ${\displaystyle \mathrm {false} }$ ${\displaystyle {\mathsf {bool}}}$

• ${\displaystyle 42:{\mathsf {nat}}}$
• ${\displaystyle \mathrm {true} :{\mathsf {bool}}}$
• ${\displaystyle x:{\mathsf {nat}}}$
• ${\displaystyle y:{\mathsf {bool}}}$

Términos de función

Además de los términos atómicos, la mayoría de las teorías de tipos modernas también permiten funciones . Los tipos de funciones introducen un símbolo de flecha y se definen de forma inductiva : si y son tipos, entonces la notación es el tipo de una función que toma un parámetro de tipo y devuelve un término de tipo . Los tipos de esta forma se conocen como tipos simples . ^[dieciséis] ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \sigma \to \tau }$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$

Algunos términos pueden declararse directamente como de tipo simple, como el siguiente término, que toma dos números naturales en secuencia y devuelve un número natural. ${\displaystyle \mathrm {add} }$

${\displaystyle \mathrm {add} :{\mathsf {nat}}\to ({\mathsf {nat}}\to {\mathsf {nat}})}$

Estrictamente hablando, un tipo simple solo permite una entrada y una salida, por lo que una lectura más fiel del tipo anterior es que es una función que toma un número natural y devuelve una función de la forma . Los paréntesis aclaran que no tiene el tipo , que sería una función que toma una función de números naturales y devuelve un número natural. La convención es que la flecha es asociativa hacia la derecha , por lo que los paréntesis se pueden eliminar del tipo. ^[dieciséis] ${\displaystyle \mathrm {add} }$ ${\displaystyle {\mathsf {nat}}\to {\mathsf {nat}}}$ ${\displaystyle \mathrm {add} }$ ${\displaystyle ({\mathsf {nat}}\to {\mathsf {nat}})\to {\mathsf {nat}}}$ ${\displaystyle \mathrm {add} }$

términos lambda

Se pueden construir nuevos términos de función utilizando expresiones lambda y se denominan términos lambda. Estos términos también se definen inductivamente: un término lambda tiene la forma , donde es una variable formal y es un término, y su tipo está anotado , donde es el tipo de y es el tipo de . ^[16] El siguiente término lambda representa una función que duplica un número natural de entrada. ${\displaystyle (\lambda v.t)}$ ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle \sigma \to \tau }$ ${\displaystyle \sigma }$ ${\displaystyle v}$ ${\displaystyle \tau }$ ${\displaystyle t}$

${\displaystyle (\lambda x.\mathrm {add} \,x\,x):{\mathsf {nat}}\to {\mathsf {nat}}}$

La variable es y (implícita del tipo del término lambda) debe tener tipo . El término tiene tipo , que se ve aplicando la regla de inferencia de aplicación de función dos veces. Por lo tanto, el término lambda tiene tipo , lo que significa que es una función que toma un número natural como argumento y devuelve un número natural. ${\displaystyle x}$ ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle \mathrm {add} \,x\,x}$ ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle {\mathsf {nat}}\to {\mathsf {nat}}}$

Un término lambda a menudo se denomina ^[d] como función anónima porque carece de nombre. El concepto de funciones anónimas aparece en muchos lenguajes de programación.

Reglas de inferencia

Aplicación de funciones

El poder de las teorías de tipos reside en especificar cómo se pueden combinar los términos mediante reglas de inferencia . ^[4] Las teorías de tipos que tienen funciones también tienen la regla de inferencia de aplicación de función : si es un término de tipo , y es un término de tipo , entonces la aplicación de a , a menudo escrita , tiene tipo . Por ejemplo, si uno conoce las notaciones de tipo , y , entonces las siguientes notaciones de tipo se pueden deducir de la aplicación de funciones. ^[dieciséis] ${\displaystyle t}$ ${\displaystyle \sigma \to \tau }$ ${\displaystyle s}$ ${\displaystyle \sigma }$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle (t\,s)}$ ${\displaystyle \tau }$ ${\displaystyle 0:{\textsf {nat}}}$ ${\displaystyle 1:{\textsf {nat}}}$ ${\displaystyle 2:{\textsf {nat}}}$

• ${\displaystyle (\mathrm {add} \,1):{\textsf {nat}}\to {\textsf {nat}}}$
• ${\displaystyle ((\mathrm {add} \,2)\,0):{\textsf {nat}}}$
• ${\displaystyle ((\mathrm {add} \,1)((\mathrm {add} \,2)\,0)):{\textsf {nat}}}$

Los paréntesis indican el orden de las operaciones ; sin embargo, por convención, la aplicación de la función se deja asociativa , por lo que se pueden eliminar los paréntesis cuando corresponda. ^[16] En el caso de los tres ejemplos anteriores, todos los paréntesis podrían omitirse en los dos primeros y el tercero podría simplificarse a . ${\displaystyle \mathrm {add} \,1\,(\mathrm {add} \,2\,0):{\textsf {nat}}}$

Reducciones

Las teorías de tipos que permiten términos lambda también incluyen reglas de inferencia conocidas como -reducción y -reducción. Generalizan la noción de aplicación de funciones a términos lambda. Simbólicamente, están escritos. ${\displaystyle \beta }$ ${\displaystyle \eta }$

• ${\displaystyle (\lambda v.t)\,s\rightarrow t[v\colon =s]}$( -reducción). ${\displaystyle \beta }$
• ${\displaystyle (\lambda v.t\,v)\rightarrow t}$, si no es una variable libre en ( -reducción). ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle \eta }$

La primera reducción describe cómo evaluar un término lambda: si se aplica una expresión lambda a un término , se reemplaza cada aparición de in por . La segunda reducción hace explícita la relación entre expresiones lambda y tipos de funciones: si es un término lambda, entonces debe ser un término de función porque se está aplicando a . Por lo tanto, la expresión lambda es equivalente a just , ya que ambas toman un argumento y se aplican a él. ^[4] ${\displaystyle (\lambda v.t)}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle (\lambda v.t\,v)}$ ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle t}$

Por ejemplo, el siguiente término puede reducirse. ${\displaystyle \beta }$

${\displaystyle (\lambda x.\mathrm {add} \,x\,x)\,2\rightarrow \mathrm {add} \,2\,2}$

En las teorías de tipos que también establecen nociones de igualdad para tipos y términos, existen reglas de inferencia correspondientes de -igualdad e -igualdad. ^[dieciséis] ${\displaystyle \beta }$ ${\displaystyle \eta }$

Términos y tipos comunes

tipo vacío

El tipo vacío no tiene términos. El tipo suele escribirse o . Un uso para el tipo vacío son las pruebas de tipo de habitación . Si para un tipo es consistente derivar una función de tipo , entonces está deshabitado , es decir, no tiene términos. ${\displaystyle \bot }$ ${\displaystyle \mathbb {0} }$ ${\displaystyle a}$ ${\displaystyle a\to \bot }$ ${\displaystyle a}$

Tipo de unidad

El tipo de unidad tiene exactamente 1 término canónico. Se escribe el tipo o y se escribe el único término canónico . El tipo de unidad también se utiliza en pruebas de tipo de habitación. Si para un tipo es consistente derivar una función de tipo , entonces está habitado , es decir, debe tener uno o más términos. ${\displaystyle \top }$ ${\displaystyle \mathbb {1} }$ ${\displaystyle \ast }$ ${\displaystyle a}$ ${\displaystyle \top \to a}$ ${\displaystyle a}$

tipo booleano

El tipo booleano tiene exactamente 2 términos canónicos. El tipo suele escribirse o o . Los términos canónicos suelen ser y . ${\displaystyle {\textsf {bool}}}$ ${\displaystyle \mathbb {B} }$ ${\displaystyle \mathbb {2} }$ ${\displaystyle \mathrm {true} }$ ${\displaystyle \mathrm {false} }$

Números naturales

Los números naturales suelen implementarse al estilo de la Aritmética de Peano . Hay un término canónico para cero. Los valores canónicos mayores que cero utilizan aplicaciones iteradas de una función sucesora . ${\displaystyle 0:{\mathsf {nat}}}$ ${\displaystyle \mathrm {S} :{\mathsf {nat}}\to {\mathsf {nat}}}$

Mecanografía dependiente

Algunas teorías de tipos permiten que los tipos de términos complejos, como funciones o listas, dependan de los tipos de sus argumentos. Por ejemplo, una teoría de tipos podría tener el tipo dependiente , que debería corresponder a listas de términos, donde cada término debe tener tipo . En este caso, tiene el tipo , donde denota el universo de todos los tipos en la teoría. ${\displaystyle {\mathsf {list}}\,a}$ ${\displaystyle a}$ ${\displaystyle {\mathsf {list}}}$ ${\displaystyle U\to U}$ ${\displaystyle U}$

Algunas teorías también permiten que los tipos dependan de términos en lugar de tipos. Por ejemplo, una teoría podría tener el tipo , donde es un término de tipo que codifica la longitud del vector . Esto permite una mayor especificidad y seguridad de tipo : funciones con restricciones de longitud de vector o requisitos de coincidencia de longitud, como el producto escalar , pueden codificar este requisito como parte del tipo. ^[24] ${\displaystyle {\mathsf {vector}}\,n}$ ${\displaystyle n}$ ${\displaystyle {\mathsf {nat}}}$

Hay cuestiones fundamentales que pueden surgir de los tipos dependientes si una teoría no tiene cuidado con las dependencias permitidas, como la paradoja de Girard . El lógico Henk Barendegt introdujo el cubo lambda como marco para estudiar diversas restricciones y niveles de tipificación dependiente. ^[25]

Tipo de producto

El tipo de producto depende de dos tipos y sus términos comúnmente se escriben como pares ordenados o con el símbolo . El par tiene el tipo de producto , donde es el tipo de y es el tipo de . El tipo de producto suele definirse con funciones eliminadoras y . ${\displaystyle (s,t)}$ ${\displaystyle \times }$ ${\displaystyle (s,t)}$ ${\displaystyle \sigma \times \tau }$ ${\displaystyle \sigma }$ ${\displaystyle s}$ ${\displaystyle \tau }$ ${\displaystyle t}$ ${\displaystyle \mathrm {first} :(\Pi \,\sigma \,\tau .\sigma \times \tau \to \sigma )}$ ${\displaystyle \mathrm {second} :(\Pi \,\sigma \,\tau .\sigma \times \tau \to \tau )}$

• ${\displaystyle \mathrm {first} \,(s,t)}$regresa , y ${\displaystyle s}$
• ${\displaystyle \mathrm {second} \,(s,t)}$devoluciones . ${\displaystyle t}$

Además de los pares ordenados, este tipo se utiliza para los conceptos de conjunción e intersección lógica .

tipo de suma

El tipo de suma depende de dos tipos y comúnmente se escribe con el símbolo o . En los lenguajes de programación, los tipos de suma pueden denominarse uniones etiquetadas . El tipo generalmente se define con constructores y , que son inyectivos , y una función eliminadora tal que ${\displaystyle +}$ ${\displaystyle \sqcup }$ ${\displaystyle \sigma \sqcup \tau }$ ${\displaystyle \mathrm {left} :\sigma \to (\sigma \sqcup \tau )}$ ${\displaystyle \mathrm {right} :\tau \to (\sigma \sqcup \tau )}$ ${\displaystyle \mathrm {match} :(\Pi \,\rho .(\sigma \to \rho )\to (\tau \to \rho )\to (\sigma \sqcup \tau )\to \rho )}$

• ${\displaystyle \mathrm {match} \,f\,g\,(\mathrm {left} \,x)}$regresa , y ${\displaystyle f\,x}$
• ${\displaystyle \mathrm {match} \,f\,g\,(\mathrm {right} \,y)}$devoluciones . ${\displaystyle g\,y}$

El tipo suma se utiliza para los conceptos de disyunción y unión lógica .

Productos y sumas dependientes

Dos tipos de dependencias comunes , los tipos de producto dependiente y suma dependiente, permiten que la teoría codifique la lógica intuicionista BHK actuando como equivalentes a la cuantificación universal y existencial ; esto está formalizado por la correspondencia Curry-Howard . ^[24] Como también se conectan con productos y sumas en la teoría de conjuntos , a menudo se escriben con los símbolos y , respectivamente. ^[17] Los tipos de producto y suma dependientes suelen aparecer en tipos de funciones y se incorporan con frecuencia en lenguajes de programación. ^[26] ${\displaystyle \Pi }$ ${\displaystyle \Sigma }$

Por ejemplo, considere una función , que toma un término de tipo y devuelve la lista con el elemento al final. La anotación de tipo de dicha función sería , que puede leerse como "para cualquier tipo , pase a y an y devuelva a ". ${\displaystyle \mathrm {append} }$ ${\displaystyle {\mathsf {list}}\,a}$ ${\displaystyle a}$ ${\displaystyle \mathrm {append} :(\Pi \,a.{\mathsf {list}}\,a\to a\to {\mathsf {list}}\,a)}$ ${\displaystyle a}$ ${\displaystyle {\mathsf {list}}\,a}$ ${\displaystyle a}$ ${\displaystyle {\mathsf {list}}\,a}$

Los tipos de suma se ven en pares dependientes , donde el segundo tipo depende del valor del primer término. Esto surge naturalmente en la informática, donde las funciones pueden devolver diferentes tipos de resultados según la entrada. Por ejemplo, el tipo booleano suele definirse con una función eliminadora , que toma tres argumentos y se comporta de la siguiente manera. ${\displaystyle \mathrm {if} }$

• ${\displaystyle \mathrm {if} \,\mathrm {true} \,x\,y}$regresa , y ${\displaystyle x}$
• ${\displaystyle \mathrm {if} \,\mathrm {false} \,x\,y}$devoluciones . ${\displaystyle y}$

El tipo de retorno de esta función depende de su entrada. Si la teoría de tipos permite tipos dependientes, entonces es posible definir una función tal que ${\displaystyle {\mathsf {bool}}}$ ${\displaystyle \mathrm {TF} \colon {\mathsf {bool}}\to U\to U\to U}$

• ${\displaystyle \mathrm {TF} \,\mathrm {true} \,\sigma \,\tau }$regresa , y ${\displaystyle \sigma }$
• ${\displaystyle \mathrm {TF} \,\mathrm {false} \,\sigma \,\tau }$devoluciones . ${\displaystyle \tau }$

El tipo de entonces puede escribirse como . ${\displaystyle \mathrm {if} }$ ${\displaystyle (\Pi \,\sigma \,\tau .{\mathsf {bool}}\to \sigma \to \tau \to (\Sigma \,x:{\textsf {bool}}.\mathrm {TF} \,x\,\sigma \,\tau ))}$

Tipo de identidad

Siguiendo la noción de Correspondencia Curry-Howard, el tipo de identidad es un tipo introducido para reflejar la equivalencia proposicional , a diferencia de la equivalencia de juicio (sintáctica) que ya proporciona la teoría de tipos.

Un tipo de identidad requiere dos términos del mismo tipo y se escribe con el símbolo . Por ejemplo, si y son términos, entonces es un tipo posible. Los términos canónicos se crean con una función de reflexividad . Para un término , la llamada devuelve el término canónico que habita en el tipo . ${\displaystyle =}$ ${\displaystyle x+1}$ ${\displaystyle 1+x}$ ${\displaystyle x+1=1+x}$ ${\displaystyle \mathrm {refl} }$ ${\displaystyle t}$ ${\displaystyle \mathrm {refl} \,t}$ ${\displaystyle t=t}$

Las complejidades de la igualdad en la teoría de tipos la convierten en un tema de investigación activo; La teoría de tipos de homotopía es un área de investigación notable que se ocupa principalmente de la igualdad en la teoría de tipos.

tipos inductivos

Los tipos inductivos son una plantilla general para crear una gran variedad de tipos. De hecho, todos los tipos descritos anteriormente y más se pueden definir utilizando las reglas de los tipos inductivos. Dos métodos para generar tipos inductivos son inducción-recursión e inducción-inducción . Un método que sólo utiliza términos lambda es la codificación Scott .

Algunos asistentes de prueba , como Coq y Lean , se basan en el cálculo para construcciones inductivas, que es un cálculo de construcciones con tipos inductivos.

Diferencias con la teoría de conjuntos

La base más comúnmente aceptada para las matemáticas es la lógica de primer orden con el lenguaje y los axiomas de la teoría de conjuntos de Zermelo-Fraenkel con el axioma de elección , abreviado ZFC. Las teorías de tipos que tienen suficiente expresabilidad también pueden actuar como fundamento de las matemáticas. Hay una serie de diferencias entre estos dos enfoques.

• La teoría de conjuntos tiene reglas y axiomas , mientras que las teorías de tipos solo tienen reglas. Las teorías de tipos, en general, no tienen axiomas y se definen por sus reglas de inferencia. ^[14]
• La teoría y la lógica de conjuntos clásicas tienen la ley del tercero excluido . Cuando una teoría de tipos codifica los conceptos de "y" y "o" como tipos, conduce a una lógica intuicionista y no necesariamente tiene la ley del tercero excluido. ^[17]
• En la teoría de conjuntos, un elemento no está restringido a un conjunto. El elemento puede aparecer en subconjuntos y uniones con otros conjuntos. En la teoría de tipos, los términos (generalmente) pertenecen a un solo tipo. Cuando se usaría un subconjunto, la teoría de tipos puede usar una función de predicado o usar un tipo de producto de tipo dependiente, donde cada elemento se combina con una prueba de que la propiedad del subconjunto es válida para . Cuando se utilizaría una unión, la teoría de tipos utiliza el tipo suma, que contiene nuevos términos canónicos. ${\displaystyle x}$ ${\displaystyle x}$
• La teoría de tipos tiene una noción incorporada de computación. Por lo tanto, "1+1" y "2" son términos diferentes en la teoría de tipos, pero calculan el mismo valor. Además, las funciones se definen computacionalmente como términos lambda. En la teoría de conjuntos, "1+1=2" significa que "1+1" es simplemente otra forma de referirse al valor "2". El cálculo de la teoría de tipos requiere un concepto complicado de igualdad.
• La teoría de conjuntos codifica números como conjuntos . La teoría de tipos puede codificar números como funciones utilizando la codificación de Church , o más naturalmente como tipos inductivos , y la construcción se parece mucho a los axiomas de Peano .
• En la teoría de tipos, las pruebas son tipos, mientras que en la teoría de conjuntos, las pruebas son parte de la lógica subyacente de primer orden. ^[14]

Los defensores de la teoría de tipos también señalarán su conexión con las matemáticas constructivas a través de la interpretación BHK , su conexión con la lógica mediante el isomorfismo de Curry-Howard y sus conexiones con la teoría de categorías .

Propiedades de las teorías de tipos.

Los términos suelen pertenecer a un solo tipo. Sin embargo, existen teorías establecidas que definen la "subtipificación".

El cálculo se lleva a cabo mediante la aplicación repetida de reglas. Muchos tipos de teorías son fuertemente normalizadoras , lo que significa que cualquier orden de aplicación de las reglas siempre terminará en el mismo resultado. Sin embargo, algunos no lo son. En una teoría de tipos normalizadora, las reglas de cálculo unidireccionales se denominan "reglas de reducción" y la aplicación de las reglas "reduce" el término. Si una regla no es unidireccional, se denomina "regla de conversión".

Algunas combinaciones de tipos son equivalentes a otras combinaciones de tipos. Cuando las funciones se consideran "exponenciación", las combinaciones de tipos se pueden escribir de manera similar a las identidades algebraicas. ^[26] Así, , , , , . ${\displaystyle {\mathbb {0} }+A\cong A}$ ${\displaystyle {\mathbb {1} }\times A\cong A}$ ${\displaystyle {\mathbb {1} }+{\mathbb {1} }\cong {\mathbb {2} }}$ ${\displaystyle A^{B+C}\cong A^{B}\times A^{C}}$ ${\displaystyle A^{B\times C}\cong (A^{B})^{C}}$

Axiomas

La mayoría de las teorías de tipos no tienen axiomas . Esto se debe a que una teoría de tipos se define por sus reglas de inferencia. Esto es una fuente de confusión para las personas familiarizadas con la teoría de conjuntos, donde una teoría se define tanto por las reglas de inferencia de una lógica (como la lógica de primer orden ) como por los axiomas sobre conjuntos.

A veces, una teoría de tipos agregará algunos axiomas. Un axioma es un juicio que se acepta sin derivación utilizando reglas de inferencia. A menudo se agregan para garantizar propiedades que no se pueden agregar limpiamente mediante reglas.

Los axiomas pueden causar problemas si introducen términos sin una forma de calcularlos. Es decir, los axiomas pueden interferir con la propiedad normalizadora de la teoría de tipos. ^[27]

Algunos axiomas comúnmente encontrados son:

• El "Axioma K" garantiza la "singularidad de las pruebas de identidad". Es decir, que todo término de un tipo de identidad es igual a reflexividad. ^[28]
• El "axioma de univalencia" sostiene que la equivalencia de tipos es igualdad de tipos. La investigación sobre esta propiedad condujo a la teoría del tipo cúbico, donde la propiedad se cumple sin necesidad de un axioma. ^[22]
• A menudo se agrega la "Ley del Medio Excluido" para satisfacer a los usuarios que desean lógica clásica , en lugar de lógica intuicionista.

No es necesario agregar el axioma de elección a la teoría de tipos, porque en la mayoría de las teorías de tipos puede derivarse de las reglas de inferencia. Esto se debe a la naturaleza constructiva de la teoría de tipos, donde demostrar que existe un valor requiere un método para calcular el valor. El axioma de elección es menos poderoso en la teoría de tipos que la mayoría de las teorías de conjuntos, porque las funciones de la teoría de tipos deben ser computables y, al estar impulsadas por la sintaxis, el número de términos de un tipo debe ser contable. (Ver Axioma de elección § En matemáticas constructivas ).

Lista de teorías de tipos

Importante

• Cálculo lambda simplemente escrito, que es una lógica de orden superior
• teoría de tipos intuicionista
• sistema F
• LF se utiliza a menudo para definir otras teorías de tipos.
• cálculo de construcciones y sus derivadas

Menor

• autómata
• Teoría del tipo ST
• UTT (Teoría unificada de tipos dependientes de Luo)
• algunas formas de lógica combinatoria
• otros definidos en el cubo lambda (también conocidos como sistemas de tipo puro )
• otros bajo el nombre de cálculo lambda mecanografiado

Investigación activa

• La teoría de tipos de homotopía explora la igualdad de tipos
• La teoría de tipos cúbicos es una implementación de la teoría de tipos de homotopía.

Ver también

• Fundamentos de las matemáticas
• Lógica

Otras lecturas

• Aarts, C.; Casa trasera, R.; Hoogendijk, P.; Voermans, E.; van der Woude, J. (diciembre de 1992). "Una teoría relacional de tipos de datos". Universidad Técnica de Eindhoven.
• Andrews B., Pedro (2002). Introducción a la lógica matemática y la teoría de tipos: hacia la verdad a través de la prueba (2ª ed.). Kluwer. ISBN 978-1-4020-0763-7.
• Jacobs, Bart (1999). Lógica categórica y teoría de tipos. Estudios de Lógica y Fundamentos de las Matemáticas. vol. 141. Elsevier. ISBN 978-0-444-50170-7. Archivado desde el original el 10 de agosto de 2023 . Consultado el 19 de julio de 2020 .Cubre la teoría de tipos en profundidad, incluidas las extensiones de tipos polimórficos y dependientes. Da semántica categórica .
• Cardelli, Luca (1996). "Sistemas de tipos". En Tucker, Allen B. (ed.). El manual de ingeniería y ciencias de la computación . Prensa CRC. págs. 2208–36. ISBN 9780849329098. Archivado desde el original el 10 de abril de 2008 . Consultado el 26 de junio de 2004 .
• Collins, Jordania E. (2012). Una historia de la teoría de tipos: desarrollos después de la segunda edición de 'Principia Mathematica'. Publicación académica Lambert. hdl :11375/12315. ISBN 978-3-8473-2963-3.Proporciona un estudio histórico de los desarrollos de la teoría de tipos centrándose en el declive de la teoría como fundamento de las matemáticas durante las cuatro décadas posteriores a la publicación de la segunda edición de 'Principia Mathematica'.
• Constable, Robert L. (2012) [2002]. "Teoría ingenua de tipos computacionales" (PDF) . En Schwichtenberg, H.; Steinbruggen, R. (eds.). Prueba y confiabilidad del sistema . Serie científica de la OTAN II. vol. 62. Saltador. págs. 213–259. ISBN 9789401004138. Archivado (PDF) desde el original el 9 de octubre de 2022.Diseñado como una contraparte de la teoría de tipos de la Teoría ingenua de conjuntos de Paul Halmos (1960).
• Coquand, Thierry (2018) [2006]. "Teoría de tipos". Enciclopedia de Filosofía de Stanford .
• Thompson, Simón (1991). Teoría de tipos y programación funcional. Addison-Wesley. ISBN 0-201-41667-0. Archivado desde el original el 23 de marzo de 2021 . Consultado el 3 de abril de 2006 .
• Hindley, J. Roger (2008) [1995]. Teoría básica de tipos simples . Prensa de la Universidad de Cambridge. ISBN 978-0-521-05422-5.Una buena introducción a la teoría de tipos simples para informáticos; Sin embargo, el sistema descrito no es exactamente el STT de Church. Reseña del libro Archivado el 7 de junio de 2011 en Wayback Machine.
• Kamareddine, Fairouz D.; Laan, Twan; Nederpelt, Rob P. (2004). Una perspectiva moderna de la teoría de tipos: desde sus orígenes hasta la actualidad . Saltador. ISBN 1-4020-2334-0.
• Ferreirós, José; Domínguez, José Ferreirós (2007). "X. Lógica y teoría de tipos en el período de entreguerras". Laberinto de pensamiento: una historia de la teoría de conjuntos y su papel en las matemáticas modernas (2ª ed.). Saltador. ISBN 978-3-7643-8349-7.
• Laan, TDL (1997). La evolución de la teoría de tipos en lógica y matemáticas (PDF) (Doctor). Universidad Tecnológica de Eindhoven. doi :10.6100/IR498552. ISBN 90-386-0531-5. Archivado (PDF) desde el original el 9 de octubre de 2022.
• Montague, R. (1973) "El tratamiento adecuado de la cuantificación en inglés corriente". En KJJ Hintikka, JME Moravcsik y P. Suppes (eds.), Approaches to Natural Language (Synthese Library, 49), Dordrecht: Reidel, 221–242; reimpreso en Portner y Partee (eds.) 2002, págs. 17–35. Ver: Montague Semantics, Enciclopedia de Filosofía de Stanford.

Notas

1. Ver § Términos y tipos
2. En el sistema de tipos de Julia , por ejemplo, los tipos abstractos no tienen instancias, pero pueden tener subtipos, ^{[1] : 110} mientras que los tipos concretos no tienen subtipos pero pueden tener instancias, para " documentación, optimización y envío ". ^[2]
3. Church demostró su método logístico con su simple teoría de tipos, ^[4] y explicó su método en 1956, ^[5] páginas 47-68.
4. En Julia , por ejemplo, una función sin nombre, pero con dos parámetros en alguna tupla (x,y) se puede indicar, por ejemplo, (x,y) -> x^5+ycomo una función anónima. ^[23]

Referencias

1. Balbaert, Ivo (2015) Introducción a la programación de Julia ISBN 978-1-78328-479-5
2. Tipos docs.julialang.org v.1 Archivado el 24 de marzo de 2022 en Wayback Machine.
3. Enciclopedia de Filosofía de Stanford (rev. lunes 12 de octubre de 2020) La paradoja de Russell Archivado el 18 de diciembre de 2021 en Wayback Machine 3. Primeras respuestas a la paradoja
4. , Alonzo (1940). "Una formulación de la sencilla teoría de tipos". La revista de lógica simbólica . 5 (2): 56–68. doi :10.2307/2266170. JSTOR  2266170. S2CID  15889861.
5. Alonzo Church (1956) Introducción a la lógica matemática Vol 1
6. ETCS en el laboratorio n
7. Chatzikyriakidis, Stergios; Luo, Zhaohui (7 de febrero de 2017). Perspectivas modernas en semántica teórica de tipos. Saltador. ISBN 978-3-319-50422-3. Archivado desde el original el 10 de agosto de 2023 . Consultado el 29 de julio de 2022 .
8. Invierno, Yoad (8 de abril de 2016). Elementos de la semántica formal: una introducción a la teoría matemática del significado en el lenguaje natural. Prensa de la Universidad de Edimburgo. ISBN 978-0-7486-7777-1. Archivado desde el original el 10 de agosto de 2023 . Consultado el 29 de julio de 2022 .
9. Cooper, Robin. "Teoría de tipos y semántica en proceso de cambio Archivado el 10 de mayo de 2022 en Wayback Machine ". Manual de Filosofía de la Ciencia 14 (2012): 271-323.
10. Barbismo, Jon; Cooper, Robin (1981) Cuantificadores generalizados y lenguaje natural Linguistics and Philosophy 4 (2):159--219 (1981)
11. Cooper, Robin (2005). "Registros y tipos de registros en teoría semántica". Revista de Lógica y Computación . 15 (2): 99-112. doi : 10.1093/logcom/exi004.
12. Cooper, Robin (2010). Teoría de tipos y semántica en proceso de cambio . Manual de Filosofía de la Ciencia. Volumen 14: Filosofía de la Lingüística . Elsevier.
13. Martin-Löf, Per (1 de diciembre de 1987). "Verdad de una proposición, evidencia de un juicio, validez de una prueba". Síntesis . 73 (3): 407–420. doi :10.1007/BF00484985. ISSN  1573-0964.
14. Programa de Fundaciones Univalentes (2013). Teoría de tipos de homotopía: fundamentos univalentes de las matemáticas. Teoría del tipo de homotopía.
15. Herrero, Pedro. «Tipos de sistema de prueba» (PDF) . logicmatters.net . Archivado (PDF) desde el original el 9 de octubre de 2022 . Consultado el 29 de diciembre de 2021 .
16. Henk Barendregt; Wil Dekkers; Richard Statman (20 de junio de 2013). Cálculo Lambda con tipos. Prensa de la Universidad de Cambridge. págs. 1–66. ISBN 978-0-521-76614-2.
17. "Reglas de la teoría de tipos intuicionista de Martin-Löf" (PDF) . Archivado (PDF) desde el original el 21 de octubre de 2021 . Consultado el 22 de enero de 2022 .
18. "prueba por contradicción". laboratorio . Archivado desde el original el 13 de agosto de 2023 . Consultado el 29 de diciembre de 2021 .
19. Heineman, George T.; Bessaí, enero; Düdder, Boris; Rehof, Jakob (2016). "Un camino largo y sinuoso hacia la síntesis modular". Aprovechamiento de aplicaciones de métodos formales, verificación y validación: técnicas fundamentales . ISoLA 2016. Apuntes de conferencias sobre informática. vol. 9952. Saltador. págs. 303–317. doi :10.1007/978-3-319-47166-2_21. ISBN 978-3-319-47165-5.
20. Campana, John L. (2012). «Tipos, Conjuntos y Categorías» (PDF) . En Kanamory, Akihiro (ed.). Conjuntos y Ampliaciones en el Siglo XX . Manual de historia de la lógica. vol. 6. Elsevier. ISBN 978-0-08-093066-4. Archivado (PDF) desde el original el 17 de abril de 2018 . Consultado el 3 de noviembre de 2012 .
21. Libra esterlina, Jonathan; Angiuli, Carlo (29 de junio de 2021). "Normalización de la teoría de tipos cúbicos". 2021 36.º Simposio anual ACM/IEEE sobre lógica en informática (LICS) . Roma, Italia: IEEE. págs. 1-15. arXiv : 2101.11479 . doi :10.1109/LICS52264.2021.9470719. ISBN 978-1-6654-4895-6. S2CID  231719089. Archivado desde el original el 13 de agosto de 2023 . Consultado el 21 de junio de 2022 .
22. Cohen, Cirilo; Coquand, Thierry; Huber, Simón; Mörtberg, Anders (2016). "Teoría del tipo cúbico: una interpretación constructiva del axioma de univalencia" (PDF) . XXI Congreso Internacional sobre Tipos de Pruebas y Programas (TYPES 2015) . arXiv : 1611.02108 . doi :10.4230/LIPIcs.CVIT.2016.23 (inactivo el 31 de enero de 2024). Archivado (PDF) desde el original el 9 de octubre de 2022.{{cite journal}}: CS1 maint: DOI inactive as of January 2024 (link)
23. Balbaert,Ivo (2015) Empezando con Julia
24. Bove, Ana; Dybjer, Peter (2009), Bove, Ana; Barbosa, Luis Soares; Pardo, Alberto; Pinto, Jorge Sousa (eds.), "Dependent Types at Work", Ingeniería del lenguaje y desarrollo riguroso de software: Escuela de verano internacional LerNet ALFA 2008, Piriápolis, Uruguay, 24 de febrero - 1 de marzo de 2008, Conferencias tutoriales revisadas , Apuntes de conferencias en informática Science, Berlín, Heidelberg: Springer, págs. 57–99, doi :10.1007/978-3-642-03153-3_2, ISBN 978-3-642-03153-3, recuperado el 18 de enero de 2024
25. Barendegt, Henk (abril de 1991). "Introducción a los sistemas de tipos generalizados". Revista de programación funcional . 1 (2): 125-154. doi :10.1017/S0956796800020025. hdl : 2066/17240 - vía Cambridge Core.
26. Milewski, Bartosz. "Programación con matemáticas (exploración de la teoría de tipos)". YouTube . Archivado desde el original el 22 de enero de 2022 . Consultado el 22 de enero de 2022 .
27. "Axiomas y Computación". Demostración de teoremas en Lean . Archivado desde el original el 22 de diciembre de 2021 . Consultado el 21 de enero de 2022 .
28. "Axioma K". nLaboratorio . Archivado desde el original el 19 de enero de 2022 . Consultado el 21 de enero de 2022 .

enlaces externos

Material introductorio

• Type Theory en nLab, que tiene artículos sobre muchos temas.
• Artículo sobre la teoría de tipos intuicionista en la Enciclopedia de Filosofía de Stanford
• Libro Lambda Calculi con tipos de Henk Barendregt
• Cálculo de construcciones / Documento tipo libro de texto de Cálculo Lambda mecanografiado de Helmut Brandl
• Notas sobre la teoría intuicionista de tipos de Per Martin-Löf
• Programación en el libro de teoría de tipos de Martin-Löf
• Libro de teoría de tipos de homotopía, que proponía la teoría de tipos de homotopía como base matemática.

Material avanzado

• Robert L. Constable (ed.). "Teoría de tipos computacionales". Scholarpedia .
• El Foro TYPES: foro de correo electrónico moderado centrado en la teoría de tipos en informática, en funcionamiento desde 1987.
• El libro de Nuprl: "Introducción a la teoría de tipos".
• Tipos Apuntes de proyectos de escuelas de verano 2005-2008
  • La escuela de verano de 2005 cuenta con conferencias introductorias.
• Escuela de verano de lenguajes de programación de Oregon, muchas conferencias y algunas notas.
  • Conferencias de verano de 2013, incluidas las charlas de Robert Harper en YouTube
  • Verano de 2015 Tipos, lógica, semántica y verificación
• El blog de Andrej Bauer