Aplicaciones diarias de la teoría de tipos

10

Quiero entender la teoría de tipos, pero primero tengo que saber cómo puedo aplicarla. ¿Podría haber más aplicaciones no obvias de la teoría de tipos aparte de los sistemas de tipos en programación? ¿Podría haber otras aplicaciones, digamos en el perfil de personalidad y los gustos?

Tamad Lang
fuente
2
¿Por qué algo tiene que tener aplicaciones fuera de lo que fue inventado?
Raphael
3
¿Fundamentos de las matemáticas? Las personas también han usado la teoría de tipos para formalizar cosas como la teoría de dominios sintéticos, la topología, etc. También está el trabajo de Chris Martens sobre el uso de herramientas teóricas de tipos para modelar narraciones narrativas. Enlace de disertación
Daniel Gratzer
1
¿Podría aclarar los recuentos como una aplicación?
Jake
44
No estoy convencido por tu premisa. Supongamos que alguien dice: "Quiero entender la ingeniería automotriz pero primero tengo que saber para qué puedo usar un automóvil. ¿Podría haber más aplicaciones no obvias de automóviles además del transporte?" Reciben respuestas que dicen que algunas personas duermen en sus autos, y Ansel Adams usó la suya como plataforma para tomar fotografías . Bueno, eso es genial, pero no ayuda a nadie a comprender la ingeniería y es probable que lleve a nuestro hipotético estudiante a diseñar automóviles con asientos súper reclinables y una suspensión muy rígida.
David Richerby
3
El hecho es que gran parte de la informática teórica (incluidas las cosas en las que trabajo) es prácticamente inútil, aunque matemáticamente hermosa. Lamentablemente tienes que elegir lados.
Yuval Filmus

Respuestas:

10

Puede interesarle el trabajo sobre Ceptre , resultado de la investigación de doctorado de Chris Martens , que utiliza la teoría de tipos para la narración interactiva. A continuación se cita el resumen de la tesis :

La narración interactiva entrelaza ideas computacionales profundas con la rica historia de la historia y el juego de la humanidad, proporcionando un contexto importante para la construcción de herramientas e idiomas. Al mismo tiempo, los lenguajes de especificación formales ofrecen una paleta de técnicas de representación e inferencia típicamente reservadas para el análisis de lenguajes de programación y sistemas deductivos complejos. Esta tesis conecta problemas en el dominio de la narración interactiva con soluciones en la especificación formal.

Específicamente, examinamos la narrativa desde un punto de vista estructural y observamos que los caminos narrativos alternativos juegan un papel complementario a las líneas de tiempo de interacción simultánea. La lógica lineal proporciona las herramientas de representación necesarias para investigar esta estructura, y al extender la correspondencia a las pruebas y la construcción de pruebas, encontramos un conjunto de posibilidades computacionales. Presentamos tres esfuerzos para aprovechar esas posibilidades: (1) el uso de la programación de lógica lineal para generar narrativas; (2) un nuevo lenguaje de programación para crear narraciones interactivas, juegos y simulaciones; y (3) técnicas para establecer y probar las propiedades del programa a nivel de diseño.

Encontramos que la programación lógica lineal, enriquecida con una extensión mínima a su semántica lógica, permite una amplia gama de modismos de programación y codificaciones de dominio. Como evidencia, damos cinco estudios de caso, que incluyen simulación social, juegos de aventura basados ​​en combate y juegos de mesa. Para apoyar el razonamiento sobre la corrección del diseño, presentamos técnicas para declarar y probar invariantes de programas, así como una prueba de capacidad de decisión para verificar automáticamente que esos invariantes tengan un gran fragmento del lenguaje.

Estos hallazgos muestran que la lógica lineal es un lenguaje de representación fructífero que sirve como base para modelar y ejecutar mundos interactivos, e invitan a futuras investigaciones sobre el uso de metodologías teóricas de prueba para sistemas creativos.

gasche
fuente
1
Eso suena como un uso de la lógica lineal, en lugar de la teoría de tipos per se .
David Richerby
66
La lógica lineal es un tema fundamental de la teoría de tipos. Este trabajo es en gran parte parte de la teoría de tipos como disciplina (algunas personas describen su trabajo como "teoría de prueba" cuando es igualmente relevante para la teoría de tipos, aunque los nombres no son equivalentes, ya que otros trabajos en "teoría de prueba" se considerarían como más específico para la teoría de la prueba en lugar de central para la teoría de tipos).
gasche
9

Ha habido usos interesantes de la teoría de tipos en lingüística. Véanse, por ejemplo, las obras lingüísticas de Chung-chieh Shan o Christian Rétoré .

A continuación se cita la descripción del libro de Rétoré sobre gramáticas categoriales:

Este libro es una introducción contemporánea e integral a las gramáticas categoriales en la tradición lógica iniciada por el trabajo de Lambek. Guía a estudiantes e investigadores a través de los resultados fundamentales en el campo, proporcionando pruebas modernas de muchos teoremas clásicos, así como avances recientes originales. Numerosos ejemplos y ejercicios ilustran las motivaciones y aplicaciones de estos resultados desde un punto de vista lingüístico, computacional y lógico. El cálculo de Lambek y sus variantes, y las gramáticas correspondientes, están en el centro de estas notas de clase. Un capítulo está dedicado a una característica clave de estas gramáticas categoriales: su interfaz semántica-sintaxis muy elegante. Además, adaptamos redes de prueba de lógica lineal a estos cálculos, ya que proporcionan algoritmos de análisis eficientes como se ejemplifica en el analizador Grail.

La siguiente cita se encuentra en la introducción del capítulo del libro de Efectos secundarios lingüísticos de Shan :

Este artículo relaciona casos de aparente no composicionalidad en lenguajes naturales con aquellos en lenguajes de programación. Tiene forma de reloj de arena: comienzo en §1 con un enfoque de la interfaz de sintaxis-semántica que nos ayuda a construir teorías semánticas compositivas. Ese enfoque consiste en establecer una analogía entre los efectos secundarios computacionales en los lenguajes de programación y lo que yo llamo por efectos secundarios lingüísticos analógicos en los lenguajes naturales.

Esta conexión puede beneficiar tanto a los informáticos como a los lingüistas, pero aquí me concentro en la última dirección de la transferencia de tecnología. Las continuaciones han sido útiles para tratar los efectos secundarios computacionales. En §2, presento un nuevo metalenguaje para continuar en semántica.

El metalenguaje que presento es útil para analizar tanto los lenguajes de programación como los lenguajes naturales. Para intuición, examino el primer uso en §3, luego señalo las virtudes de este tratamiento en §4.

Pasando al lenguaje natural en §5, describo en detalle cómo esta perspectiva ayudó a Chris Barker y a mí a estudiar el enlace y el crossover, así como las preguntas y la superioridad. También he usado continuaciones para estudiar el cuantificador y el alcance indefinido wh, particularmente en chino mandarín, pero aquí solo hay espacio para esbozar estos desarrollos adicionales, en §6.

gasche
fuente
9

Debido a la correspondencia de Curry-Howard , los tipos pueden interpretarse como proposiciones y las proposiciones como tipos.

Como resultado de esto, la teoría de tipos es aplicable literalmente a cualquier campo que use lógica formal para sus pruebas. Esto puede ser verificación de circuito, análisis real, lógica simbólica, geometría, etc.

Por ejemplo, algunas herramientas de verificación de pruebas automatizadas funcionan utilizando este principio: verifican la validez de la prueba al verificar un término en particular en algún sistema de tipos. El comprobador de pruebas LF se basa en este enfoque, al igual que HOL Light . Como aplicación de ejemplo, el código de transporte de pruebas utilizó LF para verificar las pruebas de seguridad de memoria de código no confiable. El beneficio de usar este tipo de comprobador de pruebas es que la implementación puede ser muy simple y, por lo tanto, podemos asegurarnos de que la implementación sea correcta. Ver, por ejemplo, el siguiente documento:

Damas de prueba fundacional con pequeños testigos . Dinghao Wu, Andrew W. Appel, Aaron Stump. PPDP 2003.

jmite
fuente
Esto podría ayudar: math.ucr.edu/home/baez/rosetta.pdf
Seudónimo
No creo que esto responda la pregunta. ¿Qué pasa con las aplicaciones reales?
Yuval Filmus
@YuvalFilmus ¿Definir "actual"?
David Richerby
1
¿Sabes si alguien ha usado la teoría de tipos para probar algo nuevo sobre la verificación de circuitos, análisis real, lógica simbólica o geometría? ¿O solo estamos hablando de casos en los que alguien usa 20 páginas de teoría de tipos para probar algo que toma tres líneas en un libro de texto de primaria?
David Richerby
@David Esta respuesta es que, en principio, puedes usar la teoría de tipos para probar cosas. Además, en principio podemos usar autómatas celulares para probar cosas, ya que la Regla 110 es completa de Turing. Creo que la primera declaración no tiene tanto sentido como la segunda.
Yuval Filmus
7

Un artículo interesante que explica las aplicaciones de los tipos dependientes es The Power of Pi , que muestra cómo Agda puede usarse para resolver problemas interesantes.

Otro buen ejemplo es el uso de tipos dependientes para el control de recursos. Un buen ejemplo es la API de gestión de archivos de Efectos de Idris . Por ejemplo, la función para leer una línea de un archivo tiene el siguiente tipo

readLine  : { [FILE_IO (OpenFile Read)] } Eff String

que especifica que esta función solo es aplicable si hay un archivo abierto. La lista entre llaves indica qué efectos están disponibles. En este caso, tenemos que esta función requiere el efecto de tener un archivo abierto para leer.

Puede encontrar más información sobre la biblioteca de efectos aquí .

Una aplicación más es el uso de tipos dependientes para la concurrencia como se informa en el siguiente artículo por el creador de Idris.

Rodrigo Ribeiro
fuente
1
Más ejemplos añadidos.
Rodrigo Ribeiro
3

como se menciona en la respuesta de jmite, la lógica de orden superior / teoría de tipos en la verificación de circuitos / hardware / electrónica ha existido durante décadas y ahora es tan rutinaria que ni siquiera se percibe / considera tanto como una "aplicación" después de un esfuerzo de transferencia aparentemente importante en la década de 1990 aunque todavía es un área activa de investigación También hay mucha aplicación de Coq y su lógica de tipo, en particular para la verificación de circuitos / hardware / electrónica desde la lógica de compuerta de bajo nivel hasta estructuras / subsistemas de nivel / orden mucho más altos. aquí hay algunas referencias clave

vzn
fuente
1
Sin embargo, para ser justos, la mayoría de la verificación real de hardware a escala industrial se ha realizado utilizando la verificación de modelos, una tecnología de verificación que generalmente no está relacionada con la teoría de tipos (aunque se han trazado puentes recientemente). La teoría de tipos se ha utilizado para construir lenguajes de descripción de hardware (no exagerados de los lenguajes de programación), y la mayoría de los lenguajes que da están en esta categoría, y algunos de los asistentes de prueba diseñados para la verificación de hardware (especialmente el HOL original, pero no son los PVS más utilizados) son transposiciones de Curry-Howard de la teoría de tipos.
gasche
Si tiene una experiencia más profunda en la verificación de hardware, sería interesante escuchar más detalles en Computer Science Chat, pero pensar / sospechar líneas / generalizaciones estrechas / distintas no es fácil de dibujar en esta área, por ejemplo, entre la verificación de modelos y la teoría de tipos. puede tomar un análisis histórico muy sutil para descubrir / reconstruir de manera integral las conexiones entre dos campos diferentes con objetivos diferentes y, a veces, incluso está fuera de las capacidades de los expertos en cada campo individualmente ... los árbitros en general muestran conexiones fuertes que podrían analizarse más a fondo. ..
vzn 01 de