TREMENGE 용 대체 보관함

Question

TAPL (549 페이지)은 시스템 F 유형 시스템의 건전성을 증명하기 위해 다음 레몬을 제안합니다.

대체 lemma 유형 :

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

t-tapp 케이스의 증명 :

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

및 규칙 t-tapp에 의해 우리는 다음과 같습니다 :

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

유도 가설에 의해

그래서 :

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

그래서 우리는 T-Tapp 규칙을 적용합니다 :

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

그러나 $ [y \ mapsto a] t= [x \ mapsto s] t= [x \ mapsto a] t $

$ a, s $ 은 $ y $ 을 포함 할 수 없다고 생각합니다.

그러나 $ a $ 은 $ x $ 을 포함하는 경우 어떻게됩니까? 그런 다음 이러한 유형은 일치하지 않습니다.

$ T $ 은 $ y $ 을 포함합니다. 그런 다음 LHS 유형은 $ x $ 의 결과에서

기타 소스

다음 강의 노트 . 그러나이 경우는 즉각적인 것처럼 보입니다.

Answer 1

대체 보조 정리는 $ S $ 만을 포함 할 수있는 경우에만 $ e $ . T-Tapp의 응용 프로그램에서 $ y $ 은 $ e, x, \ delta에 없습니다. $ . 특히 $ y \nx $ , $ y \ notin s $ 및 $ y \ notin a $ .

변수 이름을 모델링하고 이름을 바꾸는 몇 가지 방법이 있습니다.

• 섀도 잉 다른 바인더 내부의 바인더가 같은 이름 (예 : $ \ lambda x. \ lambda x. m $ )을 사용하도록합니다. 내부 구조물 ( $ x $ 에서 $ m $ 에서 숨겨진 (그림자) Inner $ x $ ). 예를 들어 베타 감소를 수행하는 데는 바깥 쪽 변수를 참조하려면 먼저 변수 중 하나를 이름 바꾸려면 먼저 명시 적 알파 변환을 수행해야합니다.
• 암시 적 이름 바꾸기는 항상 표현식의 어느 곳에서나 존재하는 두 개의 바인더에 대해 별개의 이름을 사용합니다 (그래서 $ \ 색상 {red} {\ lambda x. \ lambda x. m} $ 또는 심지어 $ \ color {red} {(\ lambda x. m) (\ lambda x. m)} $ , 그러나 $ \ lambda y. \ lambda x. m $ 및 $ (\ lambda xm) (\ lambda y. \ lambda y] m ) $ ) 및 용어를 복제하는 감소 후에 암시 적 알파 변환이 있습니다. 이를 BARENDREGT 컨벤션 이라고합니다.
• 대부분의 문헌은 Barendregt 협약을 사용하도록 주장하지만 실제로 중첩 된 바인더가 동일한 이름을 사용하지 않는 중간 규칙을 사용하지만 서로 겹치지 않는 바인더는 같은 이름을 사용할 수 있으며 암시 적 알파가 있습니다. 섀도 잉 후 즉시 변환 단계가 발생합니다. 예를 들어 $ (\ lambda xm) (\ lambda xm) $ 은 서면으로 허용되지만 메타 - 표기법 $ x $ 은 두 개의 지부가 두 가지 변수를 나타내는 것으로 간주됩니다. 내가 기억하는 한 Tapl 은이 협약을 사용합니다.

환경은 바인더 모음이므로 섀도 잉없이 동일한 변수 이름을 두 번 이상 정의 할 수 없습니다 ( $ \ gamma_1, x, \ gamma_2, x, \ gamma_3 no) $ ).

이제 T-Tapp의 응용 프로그램을 살펴 보겠습니다. 전제는 $ \ gamma '\ vdash t': \ forall y. t '$ $ \ gamma'= ( e, [x \ mapsto s] \ delta) $ , $ t '= [x \ mapsto s] t $ 및 $ t '= [x \ mapsto s] t $ . 이 전제에서 결론을 내릴 수 있습니다 $$ \ GAMMA '\ VDASH \ LAMBDA T'[A '] : [Y \ MAPSTO A'] T '$$ 잘 구성된 $ a '$ 의 경우. $ \ gamma '\ vdash [x \ mapsto s] (t [a]) : [x \ mapsto s] [y \ mapsto a] t $ . 따라서 $ a '= [x \ mapsto s] a $ 을 찍으십시오. 결론은이다 $$ \ gamma '\ vdash ([x \ mapsto s] t) [[x \ mapsto s] a] : [y \ mapsto [x \ mapsto s] a] [x \ mapsto s] T $$ 그리고 이것은 실제로입니다 $$ \ gamma '\ vdash [x \ mapsto s] (t [a]) : [x \ mapsto s] [y \ mapsto a] t $$ $ y \nx $ 및 $ y \ notin s $ .