He estado aprendiendo algo sobre la implementación de tipos dependientes, como este tutorial , pero la mayoría de ellos está implementando intérpretes. Mi pregunta es, parece que implementar un compilador para el tipo dependiente es mucho más difícil que un compilador, porque realmente puede evaluar los argumentos del tipo dependiente para la verificación de tipos.
Entonces
- ¿Es correcta mi ingenua impresión?
- Si es correcto, ¿algún ejemplo / recurso sobre la implementación de un lenguaje comprobado estáticamente que admita el tipo dependiente?
type-systems
compilers
dependent-type
molikto
fuente
fuente
ocamlopto GHC :-) (Este es el enfoque de Coq y Agda, por cierto.)Respuestas:
¡Esta es una pregunta interesante! Como sugiere la respuesta de Anthony, uno puede usar los enfoques habituales para compilar un lenguaje funcional no dependiente, siempre que ya tenga un intérprete para evaluar los términos para la verificación de tipo .
Este es el enfoque adoptado por Edwin Brady. Ahora, esto es conceptualmente más simple, pero pierde las ventajas de velocidad de la compilación cuando se realiza la verificación de tipo. Esto se ha abordado de varias maneras.
Primero, uno puede implementar una máquina virtual que compila términos para codificar en bytes sobre la marcha para realizar la verificación de conversión. Esta es la idea detrás
vm_computeimplementada en Coq por Benjamin Gregoire . Aparentemente también existe esta tesis de Dirk Kleeblatt sobre este tema exacto, pero desciende el código de máquina real en lugar de una máquina virtual.En segundo lugar, uno puede generar código en un lenguaje más convencional que, después de la ejecución, verifica todas las conversiones necesarias para verificar un programa mecanografiado de forma dependiente. Esto significa que podemos usar Haskell, por ejemplo, para verificar el tipo de un módulo Agda. El código puede compilarse y ejecutarse, y si acepta, entonces se puede suponer que el código en el lenguaje de tipo dependiente está bien escrito (salvo la implementación y los errores del compilador). Escuché por primera vez este enfoque sugerido por Mathieu Boesflug .
fuente
La tesis doctoral de Edwin Brady describe cómo construir un compilador para un lenguaje de programación de tipo dependiente. No soy un experto, pero diría que no es extremadamente difícil que implementar un compilador similar a System F. Muchos de los principios son bastante similares y algunos son iguales (por ejemplo, compilación de supercombinador). La tesis cubre muchas otras preocupaciones.
fuente