Teoría de tipos

Concepto en lógica matemática

En matemáticas y ciencias de la computación 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 de tipos sirven como alternativas a la teoría de conjuntos como fundamento de las matemáticas . Dos teorías de tipos influyentes que se han propuesto como fundamentos son:

• Cálculo λ tipificado de Alonzo Church
• Teoría de tipos intuicionista de Per Martin-Löf

La mayoría de los sistemas informáticos de redacción de pruebas utilizan una teoría de tipos como base . Uno de los más comunes es el Cálculo de construcciones inductivas de Thierry Coquand .

Historia

La teoría de tipos fue creada 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 propios, 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 , ambos aparecidos en los Principia Mathematica de Whitehead y Russell publicados en 1910, 1912 y 1913. Este sistema evitaba las contradicciones sugeridas en la paradoja de Russell al crear una jerarquía de tipos y luego asignar a cada entidad matemática concreta un tipo específico. Las entidades de un tipo dado se construían exclusivamente a partir de subtipos de ese tipo, ^[b] impidiendo así que una entidad se definiera utilizándose a 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 en conjunción con el cálculo lambda de Alonzo Church . Un ejemplo temprano notable de teoría de tipos es el cálculo lambda de tipos simples de Church . La teoría de tipos de Church ^[4] ayudó al sistema formal a evitar la paradoja de Kleene-Rosser que afligía al cálculo lambda original sin tipos. Church demostró ^[c] que podía servir como base de las matemáticas y se lo denominó lógica de orden superior .

En la literatura moderna, la "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 se propuso como base para las matemáticas constructivas . Otro es el cálculo de construcciones de Thierry Coquand , que se utiliza como base en Coq , Lean y otros asistentes de pruebas por computadora . La teoría de tipos es un área activa de investigación, una de cuyas direcciones es el desarrollo de la teoría de tipos de homotopía .

Aplicaciones

Fundamentos matemáticos

El primer asistente de pruebas por ordenador, llamado Automath , utilizó la teoría de tipos para codificar las matemáticas en un ordenador. Martin-Löf desarrolló específicamente la teoría de tipos intuicionista para codificar todas las matemáticas y que sirviera como una nueva base para las matemáticas. Actualmente se están realizando investigaciones sobre los fundamentos matemáticos utilizando la teoría de tipos de homotopía .

Los matemáticos que trabajaban en la teoría de categorías ya tenían dificultades para trabajar con la teoría de conjuntos de Zermelo-Fraenkel, ampliamente aceptada . Esto condujo 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 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 se basa en comprobadores de pruebas , asistentes de pruebas interactivos y demostradores de teoremas automáticos . La mayoría de estos sistemas utilizan una teoría de tipos como base matemática para codificar pruebas, lo que 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 tipos;
• La familia de probadores HOL y PVS utilizan muchas teorías de tipos que caen dentro de 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 pruebas.

Muchas teorías de tipos están respaldadas por LEGO e Isabelle . Isabelle también respalda fundamentos además de las teorías de tipos, como ZFC . Mizar es un ejemplo de un sistema de prueba que solo respalda la teoría de conjuntos.

Lenguajes de programación

Cualquier análisis de programas estáticos , 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 fue fuertemente influenciado por ellas.

Lingüística

La teoría de tipos también se utiliza ampliamente en las teorías formales de la semántica de los lenguajes naturales , ^{[7] [8]} especialmente la gramática de Montague ^[9] y sus descendientes. En particular, las gramáticas categoriales y las gramáticas de pregrupos utilizan ampliamente los constructores de tipos para definir los tipos ( sustantivo , verbo , etc.) de las 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 recursivamente 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 más que los tipos básicos, y lo que se puede construir a partir de ellos por medio de la cláusula anterior, son tipos.

Un tipo complejo es el tipo de funciones de entidades de tipo a entidades de tipo . Por lo tanto, se tienen tipos como que se interpretan como elementos del conjunto de funciones de entidades a valores de verdad, es decir, funciones indicadoras de conjuntos de entidades. Una expresión de tipo es una función de conjuntos de entidades a valores de verdad, es decir, un (función indicadora de un) conjunto de conjuntos. Este último tipo se toma de manera estándar como el tipo de cuantificadores del lenguaje natural , como everybody o nobody ( 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 los tipos de la 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, es una colección de reglas de inferencia que dan como resultado 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 a menudo se escriben 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 de constante , variable o aplicación de función , donde un término se aplica a otro término. Los símbolos de constante pueden incluir el número natural , el valor booleano y funciones como la función sucesora y el operador condicional . Por lo tanto, algunos términos pueden 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))}$

Sentencias

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}$
• "El tipo es igual al tipo " ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$
• "Los términos y ambos tipos 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 del tipo y es un término del tipo , se sigue que es un término del tipo ". Tales juicios 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 que aparece a la izquierda es el contexto de la sentencia. Las letras griegas mayúsculas, como y , son opciones comunes para representar algunos o todos los supuestos. Por lo tanto, los 4 juicios diferentes se escriben generalmente de la siguiente manera. ${\displaystyle \Gamma }$ ${\displaystyle \Delta }$

Algunos libros de texto utilizan un triple signo igual para enfatizar que se trata de una igualdad de juicio y, por lo tanto, de una noción extrínseca de igualdad. ^[14] Los juicios imponen que cada término tiene 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 indican qué juicios se pueden hacer, en función de la existencia de otros juicios. Las reglas se expresan como una deducción de estilo Gentzen utilizando una línea horizontal, con los juicios de entrada requeridos sobre 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 juicio. Las reglas son sintácticas y funcionan reescribiendo . Las metavariables , , , , y pueden consistir en términos y tipos complejos que contienen muchas aplicaciones de funciones, no solo símbolos individuales. $${\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}}}$$ ${\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 ninguna entrada es una que establece el tipo de un término constante. Por ejemplo, para afirmar que hay 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 de habitabilidad

En general, la conclusión deseada de una prueba en teoría de tipos es la de habitabilidad del tipo . ^[16] El problema de decisión de habitabilidad del tipo (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 tipo . ${\displaystyle \Gamma }$ ${\displaystyle \tau }$ ${\displaystyle t}$ ${\displaystyle \tau }$ ${\displaystyle \Gamma }$

La paradoja de Girard muestra que la presencia de tipos está estrechamente relacionada con la consistencia de un sistema de tipos con correspondencia Curry-Howard. Para que sea sólido, un sistema de este tipo debe tener tipos no presentes.

Una teoría de tipos suele tener varias reglas, incluidas las siguientes:

• crear un juicio (conocido como contexto en este caso)
• añadir una suposición al contexto ( debilitamiento del contexto )
• reordenar las suposiciones
• Utilice una suposición para crear una variable
• definir reflexividad , simetría y transitividad para la igualdad de juicio
• definir 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 tipos
• Afirmar la existencia de nuevos tipos

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

• Las reglas de "formación de tipos" indican 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 otras funciones como "primero", "segundo" y "R".
• Las reglas de "cálculo" especifican cómo se realiza el cálculo con las funciones específicas del tipo.

Para encontrar ejemplos de reglas, un lector interesado puede consultar 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 con fundaciones

El marco lógico de una teoría de tipos guarda cierta similitud con la lógica intuicionista o constructiva. Formalmente, la teoría de tipos suele citarse como una implementación de la interpretación de Brouwer-Heyting-Kolmogorov de la lógica intuicionista. ^[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 base, ciertos tipos se interpretan como proposiciones (enunciados que se pueden demostrar), y los términos que habitan en 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 hacer 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 la ley del tercio excluido ni la doble negación .

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

Como la ley del tercero excluido no se cumple, no hay término de tipo . Asimismo, la doble negación no se cumple, por lo que no hay 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 tercio excluido y la doble negación en una teoría de tipos, mediante una regla o una suposición. Sin embargo, los términos pueden no ser computados hasta llegar a los términos canónicos y ello interferirá con la capacidad de determinar si dos términos son, en términos de juicio, iguales entre sí. ^{[ cita requerida ]}

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 probar que "existe un con la propiedad ", se construya un particular y una prueba de que tiene la 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 una prueba no constructiva es la prueba por contradicción . El primer paso es asumir que no existe y refutarlo por contradicción. La conclusión de ese paso es "no es el caso que no existe". El último paso es, por doble negación, concluir que existe. Las matemáticas constructivas no permiten 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 de tipos propuestas como fundamentos son constructivas, y esto incluye la mayoría de las que utilizan los asistentes de demostración. ^{[ cita requerida ]} Es posible agregar características no constructivas a una teoría de tipos, mediante reglas o suposiciones. Estas incluyen operadores sobre continuaciones como call with current continuation . 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 la lógica y los lenguajes de programación. La implicación en la lógica es que "A B" se parece 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 los programas en los lenguajes de programación. Por lo tanto, la correspondencia a menudo se resume como "pruebas como programas". ${\displaystyle \to }$

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

Inferencia de tipos

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

Áreas de investigación

Teoría de categorías

Artículo principal: Teoría de categorías

Aunque la motivación inicial de la teoría de categorías estaba muy alejada del fundacionalismo, ambos campos resultaron tener profundas conexiones. Como escribe John Lane Bell : "De hecho, las categorías pueden ser vistas como teorías de tipos de un cierto tipo; este hecho por sí solo indica que la teoría de tipos está mucho más relacionada con la teoría de categorías que con la teoría de conjuntos". En resumen, una categoría puede ser vista como una teoría de tipos al considerar sus objetos como tipos (o clases), es decir, "a grandes rasgos, una categoría puede ser considerada como una teoría de tipos despojada de su sintaxis". De este modo se desprenden varios resultados significativos: ^[20]

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

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

Teoría de tipos 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 los números naturales , a menudo notados con el tipo , los valores lógicos booleanos ( / ), notados con el tipo , y las 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 función 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 . ^[16] ${\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 pueden eliminarse del tipo de . ^[16] ${\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 de forma inductiva: un término lambda tiene la forma , donde es una variable formal y es un término, y su tipo se anota , 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ícito a partir del tipo del término lambda) debe tener tipo . El término tiene tipo , lo que se ve al aplicar 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}}}$

A menudo se hace referencia a un término lambda ^[d] como una 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 está 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 escrito , 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 función. ^[16] ${\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 los paréntesis se pueden eliminar cuando sea apropiado. ^[16] En el caso de los tres ejemplos anteriores, todos los paréntesis podrían omitirse de 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 admiten términos lambda también incluyen reglas de inferencia conocidas como -reducción y -reducción. Estas generalizan la noción de aplicación de funciones a términos lambda. Simbólicamente, se escriben ${\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 ocurrencia de en con . La segunda reducción hace explícita la relación entre expresiones lambda y tipos de función: si es un término lambda, entonces debe ser que es un término de función porque se está aplicando a . Por lo tanto, la expresión lambda es equivalente a simplemente , 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 ser -reducido. ${\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. ^[16] ${\displaystyle \beta }$ ${\displaystyle \eta }$

Términos y tipos comunes

Tipo vacío

El tipo vacío no tiene términos. El tipo se escribe normalmente o . Un uso del tipo vacío es la demostración de la habitabilidad del tipo . Si para un tipo , es consistente derivar una función del tipo , entonces es 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 unidad tiene exactamente 1 término canónico. El tipo se escribe o y el término canónico único se escribe . El tipo unidad también se utiliza en pruebas de habitabilidad de tipos. Si para un tipo , es consistente derivar una función de tipo , entonces está habitada , 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 se escribe normalmente 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 . Existe un término canónico para el 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}}}$

Tipificación 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 el 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 : las 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}}}$

Existen problemas fundamentales que pueden surgir a partir de tipos dependientes si una teoría no es cuidadosa 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 se escriben comúnmente 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 se define generalmente 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)}$devuelve , y ${\displaystyle s}$
• ${\displaystyle \mathrm {second} \,(s,t)}$devuelve . ${\displaystyle t}$

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

Tipo de suma

El tipo suma depende de dos tipos y se escribe comúnmente con el símbolo o . En los lenguajes de programación, los tipos suma pueden denominarse uniones etiquetadas . El tipo se define generalmente 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)}$devuelve , y ${\displaystyle f\,x}$
• ${\displaystyle \mathrm {match} \,f\,g\,(\mathrm {right} \,y)}$devuelve . ${\displaystyle g\,y}$

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

Productos y sumas dependientes

Dos dependencias de tipo comunes , los tipos de producto dependiente y suma dependiente, permiten que la teoría codifique la lógica intuicionista BHK al actuar como equivalentes a la cuantificación universal y existencial ; esto se formaliza mediante la correspondencia de 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 dependiente y suma aparecen comúnmente 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 a y 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 se puede leer como "para cualquier tipo , pase a y un , y devuelva un ". ${\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 observan en pares dependientes , donde el segundo tipo depende del valor del primer término. Esto surge de manera natural en la informática, donde las funciones pueden devolver diferentes tipos de salidas en función de la entrada. Por ejemplo, el tipo booleano suele definirse con una función eliminator , que toma tres argumentos y se comporta de la siguiente manera. ${\displaystyle \mathrm {if} }$

• ${\displaystyle \mathrm {if} \,\mathrm {true} \,x\,y}$devuelve , y ${\displaystyle x}$
• ${\displaystyle \mathrm {if} \,\mathrm {false} \,x\,y}$devuelve . ${\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 }$devuelve , y ${\displaystyle \sigma }$
• ${\displaystyle \mathrm {TF} \,\mathrm {false} \,\sigma \,\tau }$devuelve . ${\displaystyle \tau }$

El tipo de puede entonces 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 identidad es un tipo introducido para reflejar la equivalencia proposicional , a diferencia de la equivalencia juiciosa (sintáctica) que la teoría de tipos ya proporciona.

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 la inducción-recursión y la inducción-inducción . Un método que solo 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 como ZFC. Las teorías de tipos que tienen suficiente expresividad también pueden actuar como base de las matemáticas. Existen varias 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 de conjuntos clásica y la lógica tienen la ley del medio excluido . Cuando una teoría de tipos codifica los conceptos de "y" y "o" como tipos, conduce a la lógica intuicionista y no necesariamente tiene la ley del medio 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 (por lo general) pertenecen a un solo tipo. Cuando se utilizaría un subconjunto, la teoría de tipos puede utilizar una función de predicado o utilizar un tipo de producto de tipo dependiente, donde cada elemento se empareja con una prueba de que la propiedad del subconjunto se cumple para . Cuando se utilizaría una unión, la teoría de tipos utiliza el tipo de 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". La computación de la teoría de tipos requiere un concepto complicado de igualdad.
• La teoría de conjuntos codifica los números como conjuntos . La teoría de tipos puede codificar los números como funciones utilizando la codificación de Church o, de manera más natural, 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 de primer orden subyacente. ^[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 a través del isomorfismo 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 único tipo. Sin embargo, existen teorías 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, algunas no lo son. En una teoría de tipo normalizador, 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] Por lo tanto, , , , , . ${\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 para una lógica (como la lógica de primer orden ) como por axiomas sobre conjuntos.

A veces, una teoría de tipos añade algunos axiomas. Un axioma es un juicio que se acepta sin derivación mediante las reglas de inferencia. A menudo se añaden para garantizar propiedades que no se pueden añadir de forma clara mediante las reglas.

Los axiomas pueden causar problemas si introducen términos sin una manera 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" asegura la "uniformidad de las pruebas de identidad", es decir, que cada término de un tipo de identidad es igual a la reflexividad. ^[28]
• El "Axioma de Univalencia" sostiene que la equivalencia de tipos es la igualdad de tipos. La investigación sobre esta propiedad condujo a la teoría de tipos cúbicos, donde la propiedad se cumple sin necesidad de un axioma. ^[22]
• A menudo se agrega la "Ley del Tercio Excluido" para satisfacer a los usuarios que desean lógica clásica , en lugar de lógica intuicionista.

El axioma de elección no necesita ser añadido a la teoría de tipos, porque en la mayoría de las teorías de tipos puede ser derivado de las reglas de inferencia. Esto se debe a la naturaleza constructiva de la teoría de tipos, donde probar que un valor existe requiere un método para calcular el valor. El axioma de elección es menos poderoso en la teoría de tipos que en 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 en un tipo debe ser contable. (Véase Axioma de elección § En matemáticas constructivas .)

Lista de teorías de tipos

Importante

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

Menor

• Automático
• 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 tipificado

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.

Véase también

• Clase (teoría de conjuntos)
• Lógica
• Distinción entre tipo y token

Lectura adicional

• 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., Peter (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-7Archivado desde el original el 10 de agosto de 2023. Consultado el 19 de julio de 2020 .Abarca la teoría de tipos en profundidad, incluidas las extensiones de tipos polimórficas y dependientes. Ofrece semántica categórica .
• Cardelli, Luca (1996). "Sistemas de tipos". En Tucker, Allen B. (ed.). Manual de ingeniería y ciencias de la computación . CRC Press. págs. 2208–36. ISBN 9780849329098Archivado desde el original el 10 de abril de 2008. Consultado el 26 de junio de 2004 .
• Collins, Jordan E. (2012). Una historia de la teoría de tipos: avances posteriores a la segunda edición de 'Principia Mathematica'. Lambert Academic Publishing. hdl :11375/12315. ISBN 978-3-8473-2963-3.Proporciona un estudio histórico de los desarrollos de la teoría de tipos con un enfoque 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]. "Naïve Computational Type Theory" (PDF) . En Schwichtenberg, H.; Steinbruggen, R. (eds.). Prueba y fiabilidad del sistema . Nato Science Series II. Vol. 62. Springer. págs. 213–259. ISBN. 9789401004138. Archivado (PDF) del original el 9 de octubre de 2022.Concebida como una contraparte de la teoría de tipos de la teoría de conjuntos ingenua de Paul Halmos (1960).
• Coquand, Thierry (2018) [2006]. "Teoría de tipos". Stanford Encyclopedia of Philosophy .
• Thompson, Simon (1991). Teoría de tipos y programación funcional. Addison–Wesley. ISBN 0-201-41667-0Archivado 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 . Cambridge University Press. ISBN 978-0-521-05422-5.Una buena introducción a la teoría de tipos simple para los científicos 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 sobre la teoría de tipos: desde sus orígenes hasta la actualidad . Springer. 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) (PhD). Universidad Tecnológica de Eindhoven. doi :10.6100/IR498552. ISBN 90-386-0531-5. Archivado (PDF) del original el 9 de octubre de 2022.
• Montague, R. (1973) "El tratamiento adecuado de la cuantificación en el inglés ordinario". 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, pp. 17–35. Véase: Montague Semantics, Stanford Encyclopedia of Philosophy.

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), puede denotarse, por ejemplo, (x,y) -> x^5+ycomo una función anónima. ^[23]

Referencias

1. Balbaert, Ivo (2015) Introducción a la programación en Julia ISBN 978-1-78328-479-5
2. docs.julialang.org v.1 Tipos Archivado el 24 de marzo de 2022 en Wayback Machine
3. Stanford Encyclopedia of Philosophy (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. Church, Alonzo (1940). "Una formulación de la teoría simple de tipos". The Journal of Symbolic Logic . 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 de teoría de tipos. Springer. ISBN 978-3-319-50422-3Archivado desde el original el 10 de agosto de 2023. Consultado el 29 de julio de 2022 .
8. Winter, Yoad (8 de abril de 2016). Elementos de semántica formal: Introducción a la teoría matemática del significado en el lenguaje natural. Editorial de la Universidad de Edimburgo. ISBN 978-0-7486-7777-1Archivado 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 constante cambio Archivado el 10 de mayo de 2022 en Wayback Machine ." Handbook of the Philosophy of Science 14 (2012): 271-323.
10. Barwise, Jon; Cooper, Robin (1981) Cuantificadores generalizados y lenguaje natural Lingüística y Filosofía 4 (2):159--219 (1981)
11. Cooper, Robin (2005). "Registros y tipos de registros en la 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 flujo . Manual de filosofía de la ciencia. Volumen 14: Filosofía de la lingüística . Elsevier.
13. Martin-Löf, Per (1987-12-01). "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 Fundamentos Univalentes (2013). Teoría de tipos de homotopía: Fundamentos univalentes de las matemáticas. Teoría de tipos de homotopía.
15. Smith, Peter. "Tipos de sistemas de prueba" (PDF) . logicmatters.net . Archivado (PDF) del original el 2022-10-09 . 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". nlab . Archivado desde el original el 13 de agosto de 2023 . Consultado el 29 de diciembre de 2021 .
19. Heineman, George T.; Bessai, Jan; Düdder, Boris; Rehof, Jakob (2016). "Un largo y sinuoso camino hacia la síntesis modular". Aprovechamiento de las aplicaciones de métodos formales, verificación y validación: técnicas fundamentales . ISoLA 2016. Apuntes de clase en informática. Vol. 9952. Springer. págs. 303–317. doi :10.1007/978-3-319-47166-2_21. ISBN . 978-3-319-47165-5.
20. Bell, John L. (2012). "Tipos, conjuntos y categorías" (PDF) . En Kanamory, Akihiro (ed.). Conjuntos y extensiones en el siglo XX . Manual de historia de la lógica. Vol. 6. Elsevier. ISBN. 978-0-08-093066-4Archivado (PDF) del original el 17 de abril de 2018. Consultado el 3 de noviembre de 2012 .
21. Sterling, Jonathan; Angiuli, Carlo (29 de junio de 2021). "Normalización para 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, Cyril; Coquand, Thierry; Huber, Simon; Mörtberg, Anders (2016). "Teoría de tipos cúbicos: una interpretación constructiva del axioma de univalencia" (PDF) . 21.ª Conferencia internacional sobre tipos para pruebas y programas (TYPES 2015) . arXiv : 1611.02108 . doi : 10.4230/LIPIcs.CVIT.2016.23 (inactivo el 1 de noviembre de 2024). Archivado (PDF) desde el original el 2022-10-09.{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)
23. Balbaert, Ivo (2015) Introducción a Julia
24. Bove, Ana; Dybjer, Peter (2009), Bove, Ana; Barbosa, Luís 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, Revised Tutorial Lectures , Lecture Notes in Computer Science, Berlín, Heidelberg: Springer, pp. 57–99, doi :10.1007/978-3-642-03153-3_2, ISBN 978-3-642-03153-3, consultado el 18 de enero de 2024
25. Barendegt, Henk (abril de 1991). "Introducción a los sistemas de tipos generalizados". Journal of Functional Programming . 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". nLab . Archivado desde el original el 19 de enero de 2022 . Consultado el 21 de enero de 2022 .

Enlaces externos

Material introductorio

• Teoría de tipos 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 de cálculos lambda con tipos de Henk Barendregt
• Cálculo de construcciones / Cálculo Lambda mecanografiado, artículo de estilo de libro de texto de Helmut Brandl
• Notas sobre la teoría de tipos intuicionista 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 propuso la teoría de tipos de homotopía como fundamento matemático.

Material avanzado

• Robert L. Constable (ed.). "Teoría de tipos computacionales". Scholarpedia .
• El Foro TYPES es un foro de correo electrónico moderado que se centra en la teoría de tipos en la informática y que funciona desde 1987.
• El libro de Nuprl: "Introducción a la teoría de tipos".
• Tipos Proyecto Notas de clase de las escuelas de verano 2005-2008
  • La escuela de verano de 2005 incluye conferencias introductorias.
• Escuela de verano de lenguajes de programación de Oregón, muchas conferencias y algunas notas.
  • Conferencias del verano de 2013, incluidas las charlas de Robert Harper en YouTube
  • Verano 2015 Tipos, lógica, semántica y verificación
• El blog de Andrej Bauer