Cómo escribir las reglas y el tipo de solidez funcionan en lenguajes de programación centrales y divertidos

Tabla de enlaces

1. Introducción

2. Traduciendo al cálculo secuente

   2.1 Expresiones aritméticas

   2.2 Leting Bindings

   2.3 Definiciones de nivel superior

   2.4 Datos algebraicos y tipos de Codata

   2.5 Funciones de primera clase

   2.6 Operadores de management

3. Evaluación dentro de un contexto

   3.1 Contextos de evaluación para la diversión

   3.2 Centrarse en la evaluación en el núcleo

4. Reglas de escritura

   4.1 Reglas de escritura para la diversión

   4.2 Reglas de escritura para el núcleo

   4.3 Tipo de solidez

5. Perspectivas

   5.1 Los contextos de evaluación son de primera clase

   5.2 Los datos son duales a Codata

   5.3 Los vínculos de alquiler son duales para los operadores de management

   5.4 La transformación del caso del caso

   5.5 consumidores directos e indirectos

   5.6 Llamado por valor, llamado por nombre y eta-laws

   5.7 Lógica lineal y la dualidad de las excepciones

6. Trabajo relacionado

7. Conclusión, declaración de disponibilidad de datos y reconocimientos

A. La relación con el cálculo secuente

B. Reglas de escritura para la diversión

C. Semántica operativa de la etiqueta/goto

Referencias

4.2 Reglas de escritura para el núcleo

Las reglas de escritura completas para Centro se dan en la Figura 2, pero los presentaremos paso a paso. Ahora tenemos productores, consumidores y declaraciones como diferentes categorías sintácticas. Para cada una de estas categorías, utilizamos un formulario de juicio separado:

Todos los juicios de escritura también están implícitamente indexados por el programa 𝑃 que contiene las definiciones de nivel superior. Sin embargo, como estas definiciones solo son necesarias al typeche -Typecking sus llamadas (llamada de regla), generalmente omitimos el índice de la presentación.

4.2.1 Tipos de datos y Codata. La Figura 2 contiene las reglas de tipificación tanto para par y lista; Dado que sus reglas son tan similares, solo discutimos las de pares explícitamente:

En la regla TUP, escribemos un constructor de pares de par aplicado a dos argumentos como productor, y en el par de casos de la regla escribimos el caso, que coincide con el patrón en este constructor y pone dos variables en el alcance, como consumidor.

Las reglas de escritura para los tipos de Codata se ven exactamente iguales, solo se cambian los roles de los productores y los consumidores.

La mayoría de las otras reglas corresponden directamente a una regla related para la diversión. Al escribir expresiones aritméticas, por ejemplo, solo tenemos que asegurarnos de que todos los subterros tengan tipo int.

Typecheck programas utilizando las dos reglas WF-vacía y WF-coms. El primero se usa para tipecar un programa vacío, y la regla WF-Cons extiende un programa typechecked con una nueva definición de nivel superior. Cuando tipecamos el cuerpo de esta definición de nivel superior que estamos a punto de agregar, ampliamos el programa con esta definición para que pueda referirse a sí mismo de manera recursiva.

4.3 Tipo de solidez

En esta sección, discutimos la solidez de los sistemas de tipos para diversión y núcleo y mostramos que la traducción [−] conserva la tipilidad de los términos. Seguimos a Wright y Felleisen [1994] Al presentar la solidez del tipo como la combinación de un progreso y un teorema de preservación. Teorema 4.1 (progreso, diversión).

Teorema 4.1 (progreso, diversión). Sea 𝑡 un término cerrado en diversión, de modo que ⊢ 𝑡: 𝜏 para algún tipo 𝜏. Entonces 𝑡 es un valor o hay algún término 𝑡 ′ tal que 𝑡 ⊲ 𝑡 ′.

Esto se puede probar fácilmente con una inducción en las derivaciones de tipificación. Debido a la presencia de la construcción Label/GOTO, la formulación estándar del teorema de preservación (fuerte) no es de inmediato para la diversión (ver también la discusión en el Apéndice C). La siguiente forma débil de preservación puede volver a probar fácilmente mediante inducción.

Teorema 4.2 ((débil) preservación, diversión). Sea 𝑡, 𝑡 ′ términos en diversión tal que 𝑡 ⊲ 𝑡 ′, γ un entorno y 𝑃 un programa tal que γ ⊢𝑃 𝑡: 𝜏. Luego hay un tipo 𝜏 ′ tal que γ ⊢𝑃 𝑡 ′: 𝜏 ′.

El teorema de preservación sólido ordinary requiere 𝜏 ′ = 𝜏. Pero de hecho, se puede probar una ligera variación de esta forma fuerte para la diversión al adaptar la técnica que se encuentra en la Sección 6 en [Wright and Felleisen 1994]. Por lo tanto, la solidez de tipo fuerte todavía se mantiene.

Antes de que podamos indicar los teoremas análogos para el núcleo, necesitaremos una definición adicional como condición de terminación para la evaluación.

Definición 4.3 (Declaración terminal). Si 𝔭 es un valor de productor en el núcleo y ⋆ una covariable que no parece libre en 𝔭, entonces ⟨𝔭 | ⋆⟩ se llama declaración terminal.

Las declaraciones terminales en el núcleo tienen el mismo papel que los valores en la diversión. Algunos idiomas basados ​​en el cálculo secuencial utilizan una declaración especial realizada en lugar de declaraciones terminales para este propósito.

Teorema 4.4 (progreso, núcleo). Sea 𝑠 una declaración centrada en el núcleo de tal manera que ⊢ 𝑠. Entonces o 𝑠 es una declaración terminal, o hay algunos 𝑠 ′ tal que 𝑠 ⊲ 𝑠 ′.

Para este teorema, requerimos que 𝑠 se centre, en contraste con la diversión, donde el progreso se mantiene para cualquier término (bien tipo). Esto se debe a que hemos utilizado el enfoque estático para la evaluación completa en el núcleo. Si usamos el enfoque dinámico en su lugar, este requisito podría eliminarse, correspondiente al uso de contextos de evaluación (dinámicos) en diversión, en lugar de una traducción a forma regular (estática).

El teorema de preservación para el núcleo es análogo a la diversión.

Teorema 4.5 (preservación, núcleo). Sea 𝑠, 𝑠 ′ declaraciones en núcleo con 𝑠 ⊲ 𝑠 ′, γ un entorno y 𝑃 un programa. Si γ ⊢𝑃 𝑠, entonces γ ⊢𝑃 𝑠 ′.

Por último, llegamos a una propiedad importante de la traducción entre estos idiomas: