LEMMA DE SUSTITUCIÓN PARA TIPOS

Question

TAPL (página 549) Propone la siguiente lema para demostrar la solidez del sistema de tipo F System:

Lemma de sustitución para tipos:

$ e, x, \ delta \ vdash t: t \ implies e, [x \ mapsto s] \ delta \ vdash [x \ mapsto s] t: [x \ MAPSTO S] T $

Prueba del caso T-TAPP:

$ e, x, \ delta \ vdash t [a]: [y \ mapsto a] t $

y por regla T-TAPP tenemos:

$ e, x, \ delta \ vdash t: \ lambda y. T $

Por lo tanto por hipótesis de inducción:

$ e, [x \ mapsto s] \ delta \ vdash [x \ mapsto s] t: \ lambda y. [x \ mapsto s] t $

Aplicando la regla T-TAPP que tenemos:

$ e, [x \ mapsto s] \ delta \ vdash [x \ mapsto s] t [a]: [y \ mapsto a] [x \ mapsto s] t $

Sin embargo, debo necesitar $ [y \ mapsto a] [x \ mapsto s] t= [x \ mapsto s] [y \ mapsto a] t $

Creo que puedo asumir que $ a, s $ no puede contener $ y $ .

Sin embargo, ¿qué pasa si $ a $ contiene $ x $ ? Entonces estos tipos no coinciden.

Asumir $ t $ contiene $ y $ . Luego, el tipo LHS deja $ x $ 's en el resultado, mientras que el tipo RHS no se deja.

Otras fuentes

Puede encontrar una prueba esbozada en la prueba de LEMMA 17, de la siguiente Notas de la conferencia . Pero este caso parece ser inmediato.

Answer 1

La sustitución LEMMA solo tiene si lo que está sustituyendo está bien formado: $ s $ solo puede contener variables de tipo enumeradas en $ e $ . En la aplicación de T-TAPP, $ y $ es una variable fresca, no presente en $ e, x, delta $ . En particular, $ y \ NE x $ , $ y \ notin s $ y $ y \ Notin A $ .

Hay varias formas de modelar nombres de variables y cambio de nombre.

• Shadowing permite a un aglutinante dentro de otra carpeta para usar el mismo nombre (por ejemplo, $ \ lambda x. \ lambda x. M $ ), y luego el nombre exterior es escondido (sombreado) en el constructo interno (cualquier ocurrencia de $ x $ en $ m $ se refiere a la Interior $ x $ ). Si desea referirse a la variable exterior (que puede suceder para realizar una reducción beta, por ejemplo), debe realizar primero una conversión alfa explícita para cambiar el nombre de una de las variables.
• El cambio de nombre implícito siempre usa nombres distintos para cuales dos carpetas presentes en cualquier lugar de una expresión (para que nunca escribas $ \ color {rojo} {\ lambda x. \ lambda x. m} $ o incluso $ \ color {rojo} {(\ lambda x. m) (\ lambda x. m)}} $ , pero $ \ lambda y. \ lambda x. M $ y $ (\ lambda xm) (\ lambda y. [x \ mapsto y] m ) $ ), y hay una conversión alfa implícita después de cualquier reducción que duplique un término. Esto se llama la convención Barendregt .
• La mayoría de las literatura afirman utilizar el Convenio de Barendregt, pero de hecho utiliza una convención intermedia donde los aglutinantes anidados nunca usan el mismo nombre, pero los aglutinantes que no se superponen pueden usar el mismo nombre, y hay un alfa implícito Paso de conversión inmediatamente después de que se produce la sombra. Así, por ejemplo, $ (\ lambda xm) (\ lambda xm) $ se permite por escrito, pero la meta-notación $ Se supone que x $ en los dos subtermones que representan dos variables diferentes. Por lo que recuerdo, Tapl usa esta convención.

Un entorno es una colección de aglutinantes, por lo que sin sombrear, no puede definir el mismo nombre de variable más de una vez (no $ \ gamma_1, x, \ gamma_2, x, \ gamma_3 $ ).

Ahora, veamos la aplicación de T-TAPP. La premisa es $ \ gamma '\ Vdash t': \ forall y. t '$ donde $ \ gamma'= ( E, [x \ mapsto s] \ delta) $ , $ t '= [x \ mapsto s] t $ y $ t '= [x \ mapsto s] t $ . Desde esta premisa, puedes concluir. $$ \ gamma '\ Vdash \ lambda t' [a ']: [y \ mapsto a'] t '$$ para cualquier $ a '$ . Desea probar $ \ gamma '\ Vdash [x \ mapsto s] (t [a]): [x \ mapsto s] [y \ mapsto a] t $ . Así que tome $ A '= [X \ MAPSTO S] A $ . La conclusión es $$ \ GAMMA '\ VDASH ([X \ MAPSTO S] T) [[X \ MAPSTO S] A]: [Y \ MAPSTO [X \ MAPSTO S] A] [x \ mapsto s] t $$ Y esto es de hecho $$ \ gamma '\ Vdash [x \ mapsto s] (t [a]): [x \ mapsto s] [y \ mapsto a] t $$ desde $ y \ ne x $ y $ y \ notin s $ .