Почему Агда и Кок не соглашаются в строгой позитивности?

24

Я наткнулся на противоречивое разногласие между Агдой и Коком, которое, очевидно, не связано с наиболее известными различиями между их теориями типов (например, (im) предсказуемость, индукция-рекурсия и т. Д.).

В частности, Агда принимает следующее определение:

  data Ty : Set0 -> Set0 where
    c1 : Ty ℕ
    c2 : Ty (Ty ℕ)

в то время как эквивалентное определение Coq отклонено, поскольку появление [Ty _] в качестве индекса самого себя в c2 считается нарушением строгой положительности.

  Inductive Ty : Set -> Set :=
    | c1 : Ty nat
    | c2 : Ty (Ty nat).

Фактически, этот случай является почти дословным примером из раздела 14.1.2.1 Coq'Art о нарушении строгой позитивности:

  Inductive T : Set -> Set := c : (T (T nat)).

Но я не вижу причин такого различия между теориями типов. Мне понятен классический пример доказательства того, что False использует отрицательное вхождение типа в аргументе конструктора, но я не могу понять, как можно извлечь противоречие из этого стиля индексации (независимо от других строго положительных аргументов конструктора).

Обращаясь к литературе, в ранней статье «Индуктивные семьи» Дайбжера делается необоснованный комментарий о том, что решение Полина-Моринга в статье CID имеет несколько иные ограничения, и смутно предполагает, что различия могут быть связаны с непредсказуемостью, но не будем подробно останавливаться на этом. Бумага Дайберса, кажется, позволяет это, в то время как бумага Полина-Моринга явно запрещает это.

Очевидно, я не первый, кто заметил эту разницу во мнениях, и некоторые считают, что это определение не должно быть разрешено ни в одной из систем ( https://lists.chalmers.se/pipermail/agda/2012/004249.html ), но Я не нашел никаких объяснений того, почему это звучит в одной системе, а не в другой, или просто нет различий во мнениях.

Итак, я полагаю, у меня есть несколько вопросов:

  1. Это пример монотонного, но не строго положительного типа? (В Coq; явно Агда считает это строго положительным)
  2. Почему Agda разрешает это, в то время как Coq отклоняет это? Это просто своеобразное различие в интерпретации «строго положительного», есть ли тонкая разница между Coq и Agda, которая делает его звучащим в Agda, и несостоятельным в Coq, или это вопрос вкуса, обусловленный конкретными теоретическими предпочтениями?
  3. Есть ли существенная разница между первым определением выше и эквивалентным индуктивно-рекурсивным определением ниже?

Индуктивно-рекурсивное определение:

  mutual
    data U : Set0 -> Set0 where
      c : (i : Fin 2) -> U (T i)
    T : Fin 2 -> Set0
    T zero = ℕ
    T (suc zero) = U ℕ

Я счастлив иметь указатели на соответствующую литературу.

Заранее спасибо.

Колин Гордон
источник
1
Насколько я знаю, Coq является более строгим, чем это допускает основополагающая теория, потому что это было легче реализовать и достаточно полезно на практике. Насколько я понимаю, этот ответ о другом, но связанном деле .
Жиль "ТАК - перестань быть злым"
1
Это определение не принимается текущей версией разработчика Agda:Ty is not strictly positive, because it occurs in an index of the target type of the constructor c2 in the definition of Ty.
gallais
2
Да, вы правы, кто-то еще указал мне на это прошлой ночью. Я использовал пакет Debian 2.3.0.1, но 2.3.2.1 от Cabal отклоняет как прямое, так и определение IR. Похоже, что, казалось бы, не связанная с этим ошибка сделала проверку позитивности на индексы более строгой: code.google.com/p/agda/issues/detail?id=690 Так как она обсуждалась в списке без явной пометки проблемы со звуком , я все еще интересно, является ли сам тип звука.
Колин Гордон

Ответы:

10

Похоже, проблема заключается в путанице, вызванной слиянием двух факторов:

  1. Я использовал устаревшую версию Agda (2.3.0.1). Похоже, что до 2.3.2 Agda просто не проверяла строгую положительность индексов результатов конструктора (см. Ошибку, которую я связал в другом месте в потоке).
  2. Более внимательное прочтение статьи об индуктивных семьях Дайбжера предполагает, что он, возможно, предполагал, что определяемый индуктивный тип не будет связан при наборе индексов результата конструктора . В разделе 3.2.1 приведена схема для индуктивных конструкторов в прозе, и, по-видимому, я неверно истолковал язык, описывающий связывающие среды каждой части схемы.

Это более близкое прочтение, конечно, согласуется с проверкой, которую выполняют Coq и (последние версии) Agda, которые запрещают любое появление T в его собственных индексах.

Колин Гордон
источник
4

Как подсказывают ваши собственные замечания, возможной причиной такой разницы является непредсказуемость. Исторически у Coq был непредсказуемый набор (все еще доступный как флаг, я верю!)

Цитирую книгу Адама Члипалы http://adam.chlipala.net/cpdt/html/Universes.html

Инструменты Coq поддерживают флаг командной строки -impredicative-set, который модифицирует Gallina более фундаментальным образом, делая Set непредсказуемым. Термин, аналогичный T: Set, T имеет тип Set, а индуктивные определения в Set могут иметь конструкторы, которые количественно определяют аргументы любых типов. Чтобы поддерживать согласованность, должно быть наложено ограничение исключения, аналогично ограничению для Prop. Ограничение применяется только к большим индуктивным типам, где некоторые конструкторы определяют количество по типу Type. В таких случаях значение в этом индуктивном типе может быть сопоставлено только с шаблоном, чтобы получить тип результата с типом Set или Prop. Это правило контрастирует с правилом для Prop, где ограничение применяется даже к небольшим индуктивным типам, и где у типа результата может быть только тип Prop. В старых версиях Coq, Set был непредсказуемым по умолчанию. Более поздние версии делают Set предикативным, чтобы избежать несоответствия с некоторыми классическими аксиомами. В частности, следует остерегаться при использовании непредсказуемого набора с аксиомами выбора. В сочетании с исключенным средним значением или расширением предиката может возникнуть несогласованность. Impredicative Set может быть полезен для моделирования изначально непредсказуемых математических концепций, но почти все разработки Coq обходятся без него.

Картер Тацио Шонвальд
источник
Из звука исправления ошибки, который я обнаружил выше, похоже, что Agda просто не проверяла положительность индексов для результатов конструктора. Который фактически не указывает, является ли мой предложенный тип монотонным, но предполагает, что это не связано с непредсказуемостью.
Колин Гордон
2
И да, -impredicative-set делает Set невидимым в Coq.
Колин Гордон