Перекрывающаяся черта теории типов и систем типов.
Я заинтересован в том, чтобы получить действительно твердое представление о зависимой типизации. Я прочитал большую часть TaPL и прочитал (если не полностью поглощен) «Зависимые типы» в ATTaPL . Я также прочитал и просмотрел кучу статей о зависимой типизации. Многие дискуссии по теории типов,...
Coq имеет тип Prop несущественных доказательств, которые отбрасываются при извлечении. Какова причина этого, если мы используем Coq только для доказательств? Prop является непредсказуемым, поэтому Prop: Prop, однако, Coq автоматически выводит индексы юниверса, и мы можем использовать Type (i)...
Я читал несколько статей о зависимых типах и контрактах программирования. Из большей части того, что я прочитал, кажется, что контракты - это динамически проверяемые ограничения, а зависимые типы проверяются статически. Были некоторые бумаги, которые заставили меня думать, что возможно иметь...
Coq, Agda и Idris имеют бесконечную иерархию типов (Тип 1: Тип 2: Тип 3: ...). Но почему бы не сделать это, как λC, систему в лямбда-кубе, которая ближе всего к исчислению конструкций и имеет только два , ∗** и , и эти правила?◽◽◽ ∅⊢∗:◽∅⊢∗:◽\frac {} {∅ ⊢ * : ◽}...
Представьте себе, мы определили натуральные числа в лямбда-исчислении с зависимой типизацией как церковные цифры. Они могут быть определены следующим образом: SimpleNat = (R : Set) → R → (R → R) → R zero : SimpleNat zero = λ R z _ → z suc : SimpleNat → SimpleNat suc sn = λ R z s → s (sn R z s)...
π 1 : A × B → A π 2 : A × B → BA×B≜∀α.(A→B→α)→αA×B≜∀α.(A→B→α)→α A \times B \triangleq \forall\alpha.\; (A \to B \to \alpha) \to \alpha π1:A×B→Aπ1:A×B→A\pi_1 : A \times B \to Aπ2:A×B→Bπ2:A×B→B\pi_2 : A \times B \to B Это не так удивительно, хотя естественное чтение типа F - это пара с исключением в...
Для систем без зависимых типов, таких как система типов Хиндли-Милнера, типы соответствуют формулам интуиционистской логики. Там мы знаем, что ее модели являются гейтинговыми алгебрами, и, в частности, чтобы опровергнуть формулу, мы можем ограничиться одной гейтинговой алгеброй, где каждая формула...
В главе 1 и Приложении A к книге Hott представлены несколько семейств примитивных типов (типы юниверсов, зависимые типы функций, типы зависимых пар, типы копроизведения, пустой тип, тип блока, тип натурального числа и типы идентификаторов), образующие основу для теории гомотопического типа. Однако...
Я заинтересован в моделировании объектов, от объектно-ориентированного программирования, в теории зависимых типов. В качестве возможного приложения я хотел бы иметь модель, в которой я могу описать различные функции императивных языков программирования. Я мог найти только одну статью о...
Правда ли, что добавление аксиом в CIC может оказать негативное влияние на вычислительное содержание определений и теорем? Я понимаю , что в нормальном поведении теории, любой замкнутый терм сведет к канонической нормальной форме, например , если верно, то п должен сводиться к слагаемому виду ( S у...
Хорошо известно, что свойство Чёрча-Россера верно для редуцирования в простом типе лямбда-исчисления. Это означает , что исчисление соответствует, в том смысле , что не все уравнения с участием Х -терминов являются выводимыми: например, K ≠ I , так как они не разделяют ту же нормальную...
Я изучил кое-что о реализации зависимых типов, как этот учебник , но большинство из них - реализация интерпретаторов. Мой вопрос, кажется, что реализация компилятора для зависимого типа намного сложнее, чем компилятор, потому что вы действительно можете оценить аргументы зависимого типа для...
Я экспериментирую с системами чистого типа в лямбда-кубе Барендрегта, особенно с наиболее мощным, исчислением конструкций. Эта система имеет сорта *и BOX. Для справки ниже я использую конкретный синтаксис Morteинструмента https://github.com/Gabriel439/Haskell-Morte-Library, который близок к...
Мне интересно, может ли кто-нибудь подсказать мне, почему строгая положительность индуктивных типов данных гарантирует строгую нормализацию. Чтобы было ясно, я вижу, как наличие отрицательных явлений приводит к расхождению, то есть путем определения: data X where Intro : (X->X) -> X мы можем...
Я нахожусь в ситуации, когда мне нужно показать, что проверка типов решаема для исчисления с зависимым типом, над которым я работаю. До сих пор я был в состоянии доказать, что система сильно нормализуется, и, таким образом, равенство определений разрешимо. Во многих ссылках, которые я читал,...
Это довольно известный факт, что для получения противоречия из неравенства (например, ) в теории типов Мартина-Лоэфа требуется вселенная.( 0 =1 ) → ⊥(0=1)→⊥(0=1) \to \bot Доказательство также довольно простое - в отсутствие юниверсов мы можем стереть зависимости из любого зависимого типа, чтобы...
Скажем, я работаю в теории гомотопического типа, и мои единственные объекты изучения - это условные категории. Эквивалентности здесь даны функторами F:D⟶CF:D⟶CF:{\bf D}\longrightarrow{\bf C} а также G:C⟶DG:C⟶DG:{\bf C}\longrightarrow{\bf D}которые обеспечивают эквивалентность категорий C≃DC≃D{\bf...
Большинство помощников по доказательству имеют формализацию понятия «конечное множество». Эти формализации, однако, сильно отличаются (хотя можно надеяться, что все они по существу эквивалентны!). Что я не понимаю на данном этапе, так это пространство проектирования и каковы плюсы и минусы каждой...
Большинство зависимых типизированных систем имеют строгие условия положительности для индуктивных типов. Кто-нибудь знает пример, когда нарушение условия приводит к несогласованности в...
Итак, я читаю немного о разработке, в частности, алгоритмах, основанных на двухцветном исчислении конструкции, и я немного запутался. Я не понимаю, какова цель . Кажется, он идентичен за исключением того, что существует различие между неявными и явными аргументами для функций. В частности, я не...