Regla de mecanografía
Cómo un sistema de tipos asigna un tipo a una construcción sintáctica

En teoría de tipos , una regla de tipado es una regla de inferencia que describe cómo un sistema de tipos asigna un tipo a una construcción sintáctica . [1] : 94  Estas reglas pueden ser aplicadas por el sistema de tipos para determinar si un programa está bien tipado y qué expresiones de tipo tienen. Un ejemplo prototípico del uso de reglas de tipado es la definición de inferencia de tipos en el cálculo lambda de tipado simple , que es el lenguaje interno de las categorías cerradas cartesianas . [2]

Notación

Las reglas de tipificación especifican la estructura de una relación de tipificación que relaciona los términos sintácticos con sus tipos. [1] : 92  Sintácticamente, la relación de tipificación se suele indicar con dos puntos, por ejemplo, indica que una expresión tiene tipo . Las reglas en sí mismas se suelen especificar utilizando la notación de deducción natural . [1] : 26  Por ejemplo, las siguientes reglas de tipificación especifican la relación de tipificación para un lenguaje simple de booleanos : [1] : 93  mi : τ {\displaystyle e:\tau} mi {\estilo de visualización e} τ {\estilo de visualización \tau}

a a tú mi : B o o yo F a yo s mi : B o o yo mi 1 : B o o yo mi 2 : τ mi 3 : τ i F   mi 1   a yo mi norte   mi 2   mi yo s mi   mi 3 : τ {\displaystyle {\frac {}{{\mathsf {true}}:{\mathsf {Bool}}}}\qquad {\frac {}{{\mathsf {false}}:{\mathsf {Bool}}} }\qquad {\frac {e_{1}:{\mathsf {Bool}}\quad \;e_{2}:\tau \quad \;e_{3}:\tau }{\mathbf {si} \ e_{1}\ \mathbf {entonces} \ e_{2}\ \mathbf {else} \ e_{3}:\tau }}}

Cada regla establece que la conclusión que se encuentra debajo de la línea puede derivarse de las premisas que se encuentran sobre la línea. Las dos primeras reglas no tienen premisas que se encuentren sobre la línea, por lo que son axiomas . La tercera regla tiene premisas que se encuentran sobre la línea (específicamente, tres premisas), por lo que es una regla de inferencia .

En los lenguajes de programación, el tipo de una variable depende de dónde está enlazada , lo que requiere reglas de tipado sensibles al contexto. Estas reglas se dan mediante un juicio de tipado , generalmente escrito como , que establece que una expresión tiene tipo bajo un contexto de tipado que relaciona las variables con sus tipos. Los contextos de tipado se complementan ocasionalmente con los tipos de variables individuales; por ejemplo, puede leerse como "el contexto complementado con la información de que la expresión tiene tipo produce el juicio de que la expresión tiene tipo ". Esta notación se puede utilizar para dar reglas de tipado para referencias de variables y abstracción lambda en el cálculo lambda de tipado simple : [1] : 101–102  Γ ⊢ mi : τ {\displaystyle \Gamma \vdash e:\tau } mi {\estilo de visualización e} τ {\estilo de visualización \tau} Γ {\estilo de visualización \Gamma} Γ , incógnita : τ 1 ⊢ mi : τ 2 {\displaystyle \Gamma ,x{:}\tau _{1}\vdash e:\tau _{2}} Γ {\estilo de visualización \Gamma} incógnita {\estilo de visualización x} τ 1 estilo de visualización {\displaystyle \tau_{1}} mi {\estilo de visualización e} τ 2 Estilo de visualización: {\displaystyle \tau_{2}}

incógnita : τ ∈ Γ Γ ⊢ incógnita : τ Γ , incógnita : τ 1 ⊢ mi : τ 2 Γ ⊢ ( la incógnita : τ 1 . mi ) : τ 1 → τ 2 {\displaystyle {\frac {x{:}\tau \in \Gamma }{\Gamma \vdash x:\tau }}\qquad {\frac {\Gamma ,x{:}\tau _{1}\vdash e:\tau _{2}}{\Gamma \vdash (\lambda x{:}\tau _{1}.\,e):\tau _{1}\rightarrow \tau _ {2}}}}

De manera similar, la siguiente regla de tipificación describe la construcción del aprendizaje automático estándar : yo mi a {\displaystyle \mathbf {dejar}}

Γ ⊢ mi 1 : τ 1 Γ , incógnita : τ 1 ⊢ mi 2 : τ 2 Γ ⊢ yo mi a   incógnita = mi 1   i norte   mi 2   mi norte d : τ 2 {\displaystyle {\frac {\Gamma \vdash e_{1}:\tau _{1}\qquad \Gamma ,x{:}\tau _{1}\vdash e_{2}:\tau _{2} }{\Gamma \vdash \mathbf {let} \ x=e_{1}\ \mathbf {in} \ e_{2}\ \mathbf {end} :\tau _ {2}}}}

No todos los sistemas de reglas de tipificación especifican directamente un algoritmo de verificación de tipos . Por ejemplo, la regla de tipificación para aplicar una función paramétricamente polimórfica en el sistema de tipos Hindley-Milner requiere "adivinar" el tipo apropiado en el que se debe instanciar la función. [3] Adaptar un sistema de reglas declarativas a un algoritmo decidible requiere la producción de un sistema algorítmico separado que pueda demostrarse que especifica la misma relación de tipificación. [4]

Véase también

Referencias

  1. ^ abcde Pierce, Benjamin C. (2002). Tipos y lenguajes de programación (1.ª ed.). Cambridge, Mass.: MIT Press. ISBN 0262162091.
  2. ^ Baez, John. "El Café de la Categoría N". golem.ph.utexas.edu . Consultado el 30 de septiembre de 2022 .
  3. ^ Clément, Dominique; Despeyroux, Thierry; Kahn, Gilles; Despeyroux, Joëlle (8 de agosto de 1986). "Un lenguaje aplicativo simple: Mini-ML". Actas de la conferencia ACM de 1986 sobre LISP y programación funcional - LFP '86 (PDF) . Association for Computing Machinery. págs. 13–27. doi :10.1145/319838.319847. ISBN 0897912004. Número de identificación del sujeto  5126579.
  4. ^ Dunfield, Jana; Krishnaswami, Neel (23 de mayo de 2021). "Tipo bidireccional". Encuestas de computación de ACM . 54 (5): 98:19. arXiv : 1908.05839 . doi : 10.1145/3450952 . ISSN  0360-0300. S2CID  201058734.

Lectura adicional

  • Cardelli, Luca (marzo de 1996). "Sistemas de tipos" (PDF) . ACM Computing Surveys . 28 (1): 263–264. doi :10.1145/234313.234418. S2CID  227408784.
Γ ⊢ {\displaystyle \Gamma \!\vdash }

Este artículo relacionado con la teoría de lenguajes de programación o teoría de tipos es un esbozo . Puedes ayudar a Wikipedia expandiéndolo.

Obtenido de "https://es.wikipedia.org/w/index.php?title=Regla_de_mecanografía&oldid=1193481683"