카테고리 보관물: cstheory

cstheory

왜 무한 유형 계층 구조입니까? λC와 같은 두 가지 유형,

Coq, Agda 및 Idris는 무한 유형 계층 구조를 갖습니다 (유형 1 : 유형 2 : 유형 3 : …). 그러나 λC, λC와 같은 구조의 계산법에 가장 가까운 람다 큐브의 시스템 인 λC와 같은 두 가지 유형,

및 과이 규칙은 어떻습니까?

∅⊢∗:◽

Γ⊢T1:s1Γ,x:T1⊢t:T2Γ⊢(λx:T1,t):(Πx:T1,T2)

Γ⊢T1:s1Γ,x:T1⊢T2:s2Γ⊢(Πx:T1,T2):s2

이것은 더 단순 해 보인다. 이 시스템에는 중요한 제한이 있습니까?



답변

실제로 CoC의 접근 방식은보다 표현력이 뛰어나며 임의의 즉석 정량화를 허용합니다. 예를 들어,

∀a.a→a

얻을 자체를 인스턴스화 할 수 있습니다

(∀a.a→a)→(∀a.a→a)

우주 계층 불가능합니다.

널리 사용되지 않는 이유는 즉석 정량화가 고전적인 논리와 호환되지 않기 때문입니다. 만약 당신이 그것을 가지고 있다면, 당신은 타입이 순진한 방식으로 세트로 해석되는 타입 이론의 모델을 줄 수 없습니다 — John Reynolds의 유명한 논문 Polymorphism is Set-theoretic 참조 .

많은 사람들이 일반적인 수학 증거를 기계 검사하는 방법으로 유형 이론을 사용하기를 원하기 때문에 일반적으로 일반적인 기초와 호환되지 않는 유형 이론적 특징에 대해서는 열의가 없습니다. 실제로, Coq는 원래 불확실성을 지원했지만 꾸준히 포기했습니다.


답변

나는 레벨이 실제로 사용되는 이유에 대해 조금 더 설명하면서 Neel의 답변을 평소와 같이 칭찬합니다.

CoC의 첫 번째 중요한 한계는 사소한 것입니다! 놀랍게도 한 가지 이상의 요소가 있음증명할 수있는 유형이없고 , 그 수가 무한대라는 것을 알 수 있습니다. 2 개의 유니버스를 추가하면 무한히 많은 요소와 모든 “단순한”데이터 유형이있는 자연수를 얻을 수 있습니다.

두 번째 제한은 계산 규칙입니다. CoC는 반복 만 지원합니다 . 즉, recusive 함수는 인수의 하위 용어에 액세스 할 수 없습니다. 이러한 이유로, 유도 성 유형을 기본 구성으로 추가하는 것이 더 편리하여 CIC를 발생시킵니다. 그러나 이제 또 다른 문제가 발생합니다. 가장 자연스러운 유도 규칙 ( 이 문맥에서 제거 라고 함 )은 제외 된 중간과 일치하지 않습니다! 유도 규칙을 유니버스가있는 예측 유형으로 제한하면 이러한 문제가 나타나지 않습니다.

결론적으로 CoC는 기본 시스템에서 원하는 표현력과 견고성에 일관성이 없습니다. 유니버스를 추가하면 이러한 많은 문제가 해결됩니다.


답변