Неліктен шексіз түрдегі иерархия?

Coq, Agda, and Idris have an infinite type hierarchy (Type 1 : Type 2 : Type 3 : ...). But why not do it instead like λC, the system in the lambda cube that's closest to the calculus of constructions, which has only two sorts, $*$ and $◽$, and these rules?

$$\frac {} {∅ ⊢ * : ◽}$$

$ \ frac {Γ ⊢ T _ 1: s _ 1 \ qquad Г, \: x: T _ 1 ⊢ t: T _ 2} {Γ ⊢ (λ \: x: T _1, \: t): (Π \: x: T _1, \: T _ 2)} $$

$ \ frac {Γ ⊢ T _ 1: s _ 1 \ qquad Г, \: x: T _ 1 ⊢ T _ 2: s _ 2} {Γ ⊢ (Π \: x: T _1, \: T _ 2): s _ 2} $$

Бұл оңайырақ. Бұл жүйенің маңызды шектеулері бар ма?

17

2 жауаптар

Шын мәнінде, КК-ның көзқарастары мағыналы болып табылады - ерікті импрентативті сандық бағалауға мүмкіндік береді. Мысалы, типі $ \ forall a. \; a \ to $ $ өзін $ (\ forall a. \ a \ to a) \ to (\ forall a. \ a \ to a) $ алу үшін жасауға болады, бұл ғаламдық иерархиямен мүмкін емес.

Кеңінен қолданылмайтын себебінен, импрентативті сандық бағалау классикалық логикамен үйлеспейді. Егер сізде бар болса, түрлер теориясы түрлерінің үлгісін бере алмайсыз, онда түрлері түрлілігімен түсіндіріледі --- қараңыз Джон Рейнолдстың танымал қағазы Полиморфизм - Set-теориялық емес .

Көптеген адамдар типтік теорияны қарапайым математикалық дәлелдерді машинаны тексеру әдісі ретінде пайдаланғысы келгендіктен, әдеттегі негіздермен үйлеспейтін типтік-теориялық ерекшеліктер туралы әдетте өз пікірлерін білмейді. Шын мәнінде, Coq бастапқыда қолайсыздықты қолдады, бірақ олар оны тұрақты түрде тастап кетті.

19
қосылды

Нелдің (әдеттегідей тамаша) жауаптарын, іс жүзінде неліктен деңгейлерді пайдалану туралы біраз түсініктеме беремін.

CoC-дің бірінші маңызды шектеуі - бұл тривиальды болып табылады! Бір қызығы байқау - бұл біреуден артық элемент бар екендігін дәлелдеуге мүмкіндік бермейтін ешқандай тип жоқ, олардың шексіз саны аз. Тек 2 ғаламды қосу сізге шексіз көп элементтері бар барлық табиғи нөмірлерді және барлық «қарапайым» деректер түрлерін береді.

Екінші шектеулер есептеу ережелері болып табылады: CoC тек итерацияны қолдайды, яғни қайтару функциялары олардың аргументтерінің қосалқы терминдеріне қол жеткізе алмайды. Осы себепті индукциялық типтерді қарабайыр құрылыс ретінде қосу оңайырақ. Бірақ қазір тағы бір мәселе туындайды: ең табиғи индукциялық ереже (бұл тұрғыда жою »деп аталады)« Болдырмау ортасы »-мен келіспейді! Егер сіз индукция ережесін ғаламдан тұратын предикативті түрлерге шектейтін болсаңыз, бұл мәселелер пайда болмайды.

Қорытындылай келе, CoC-тің негізгі жүйеде қалайтындығын білдірмейтіндігі де, сенімділігі де жоқ. Ғаламдарды қосу бұл мәселелердің көбісін шешеді.

9
қосылды
@ ŁukaszLew Бұл шын мәнінде, оңай дәлелденген «дәлелсіз қате» моделінің қарапайым салдары. Бұл үлгіде ешбір түрдің 1 элемент көп емес. 2 ғаламатқа ие болу осы модельдің бар болуына жол бермейді. Александр Микельдің диссертациясы 2 әмбебап элементтердің шексіз саны бар түрге сілтеме береді.
қосылды автор cody, көзі
Алғашқы шектеулерге кейбір сілтемелеріңіз бар ма? Егер жоқ болса, екінші аалам теңдеңізді (пропозматикалық мета?) Теңсіздікті дәлелдеуге қалай көмектеседі?
қосылды автор Philippe Gauthier, көзі