Funsplit и полярность Pi-типов

18

В недавнем потоке в списке рассылки Агда, вопрос - законов выскочил, в котором Питер Hancock сделал заставляющий думать замечание .η

Насколько я понимаю, законы приходят с отрицательными типами, т.е. связующие, правила введения которых обратимы. Чтобы отключить для функций, Хэнк предлагает использовать специальный элиминатор funsplit вместо обычного правила приложения. Я хотел бы понять замечание Хэнка с точки зрения полярности.ηη

Например, есть две презентации -types. Существует традиционный Martin-Löf сплит нейтрализатор, в позитивном стиле:Σ

Γf:(a:A)(b:Ba)C(a,b)Γp:Σa:A.BΓsplitfp:Cp

И есть отрицательная версия:

Γp:Σa:A.BΓπ0p:AΓp:Σa:A.BΓπ1p:B[π0p/a]

Последнее представление позволяет легко получить для пар, т.е. для любой пары (где == обозначает равенство определений). С точки зрения доказуемости это различие не имеет значения: интуитивистски можно реализовать проекции с разбивкой или наоборот.η(π0p,π1p)==pp

Теперь, -типы обычно (и неоспоримый, я считаю) негативно воспринят:Π

Γf:Πa:A.BΓs:AΓfs:B[s/a]

Что дает нам для функций: .ηλx.fx==f

Тем не менее, в этом письме Хэнк вспоминает элиминатор funsplit (Программирование в теории типов ML, [http://www.cse.chalmers.se/research/group/logic/book/], стр. 56). Это описывается в логической структуре:

fΠ(A,B)C(v)Set[vΠ(A,B)]d(y)C(λ(y))[y(x)B(x)[xA]]funsplit(f,d)C(f)

Интересно, что Nordstrom et al. мотивировать это определение, сказав, что «[эта] альтернативная неканоническая форма основана на принципе структурной индукции». Это утверждение сильно пахнет позитивом: функции будут «определены» их конструктором .λ

Тем не менее, я не могу достаточно точно описать это правило в естественной дедукции (или, что еще лучше, в последовательном исчислении). (Ab) использование логического каркаса для введения представляется здесь решающим.Y

Итак, является ли funsplit позитивным представлением -типов? Есть ли у нас что-то похожее в (независимом) исчислении секвенций? Как бы это выглядело?Π

Насколько распространено / любопытно это для теоретиков доказательства в этой области?

pedagand
источник

Ответы:

12

Представление функциональной элиминации с использованием определенно не является обычным явлением в большинстве методов теории типов. Однако я считаю, что эта форма действительно является «позитивным» представлением об устранении функциональных типов. Проблема здесь в том, что вам нужна форма соответствия шаблону высшего порядка, см., Например, Дейл Миллер .funsplit

Позвольте мне переформулировать ваше правило более понятным для меня способом:

Γf:Πx:A.BΓ,z:Πx:A.BC:SetΓ,[x:A]F(x):Be:C{λx:A.F(x)/z}match f with λx:A.F(x)e:C{f/z}

Там , где представляет собой мета-переменная типа в контексте .B x : AFBx:A

Правило переписывания становится:

match λx:A.t with λx:A.F(x)ee{t{u/x}/F(u)}

Это позволяет вам определить приложение как:

app(t,u)=match t with λx:A.F(x)F(u)

Помимо того факта, что для этого требуется действительная система типов «логический каркасный стиль», из-за проблем (и ограниченных потребностей) унификации более высокого порядка эта формулировка непопулярна.

Однако есть место, где в литературе присутствует положительное / отрицательное различие: формулировка предикатов логических отношений . Два возможных определения (в унарном случае)

[[Πx:A.B]]={tu[[A]],tu[[B]]xu}

и

[[Πx:A.B]]={ttλx.t,u[[A]],t{u/x}[[B]]xu}

Вторая версия менее распространена, но ее можно найти, например, в Dowek и Werner .

Коди
источник
1
Похоже, это связано с абстрактным синтаксисом высшего порядка, который широко используется в логической структуре. В частности, здесь кажется мета-функцией. F
день
13

Вот немного другой взгляд на ответ Фредрика. Как правило, случайные церковные кодировки типов удовлетворяют соответствующим законам , но не удовлетворяют законам .ηβη

Таким образом, это означает, что мы можем определить зависимую пару следующим образом:

л 1 л 1 : х : Х .

Икс:Икс,Y[Икс]α:*,(ΠИкс:Икс,Y[Икс]α)α
Теперь, обратите внимание , что легко определимы: Однако вы не можете определить вторую проекцию - попробуйте! Вы можете определить только слабый элиминатор для этого, поэтому я написал это с экзистенциальным.π1тг 2 : П р : ( х : Х .
π1:Икс:Икс,Y[Икс]Иксλп:(Икс:Икс,Y[Икс]),пИкс(λИксY,Икс)
π2:Πп:(Икс:Икс,Y[Икс]),Y[π1п]

Однако вторая проекция реализуема , и в параметрической модели вы можете показать, что она также имеет правильное поведение. (См. Мой недавний проект с Дереком Дрейером о параметричности в исчислении конструкций, чтобы узнать больше об этом.) Поэтому я думаю, что проекция фундаментально требует некоторых сильных свойств экстенсиональности, чтобы иметь смысл.π2

В терминах последовательного исчисления слабый элиминатор имеет правило, которое выглядит примерно так:

pΓCΓ,x:X,y:Y[x],

Γ,Икс:Икс,Y:Y[Икс],Γ'е':СΓ,п:Икс:Икс,Y[Икс],Γ'LеT(Икс,Y)знак равнопяNе':С
Здесь неявные условия правильной формы подразумевают, что не может быть свободным в или . Если мы ослабим это условие, мы получим правило разделения, которое имеет левое правило, которое выглядит как Эта замена очень напоминает мне правило исключения Жирара / Шредера-Хейстера для равенства. Я задала вопроспΓ'С
Γ,Икс:Икс,Y:Y[Икс],[(Икс,Y)/п]Γ'е':[(Икс,Y)/п]СΓ,п:Икс:Икс,Y[Икс],Γ'LеT(Икс,Y)знак равнопяNе':С
об этом правиле некоторое время назад, и Дэвид Баэлде и Гопалан Надатур дают современную версию в своей статье LICS 2012 « Объединение модуля вычета и логики определений с фиксированной точкой» . Я думаю, что Конор МакБрайд потратил некоторое время на размышления о связи между типом идентичности и равенством Шредера-Хейстера, так что вы можете захотеть увидеть, что он думает.
Нил Кришнасвами
источник
1
Я действительно наслаждаюсь всеми этими ответами! Я чувствую, что в ответе Фредрика есть некое понятие «самоанализа» (способность знать, что термин имеет значение), что является реальной проблемой с eta: параметричность подразумевает, что самоанализ подразумевает eta.
Коди
10

Ричард Гарнер написал хорошую статью о применении против funsplit, О силе зависимых продуктов в теории типов Мартина-Лёфа (APAL 160 (2009)), в которой также обсуждается природа высшего порядка правила funsplit (со ссылкой на Питер Шредер-Хейстер. Естественное продолжение естественного дедукции (JSL 49 (1984))).

Ричард показывает, что при наличии типов идентичности (а также правил формирования и введения для типов ) funsplit является взаимозависимым с правилом приложения выше + пропозициональная эта, то есть следующие два правила: Π

м:Π(A,В)η(м):яdΠ(A,В)(м,λИкс,мИкс)(Π-Prop-η)
Икс:Aе(Икс):В(Икс)η(λ(е))знак равнорееL(λ(е)):яdΠ(A,В)(λ(е),λ(е))(Π-Prop-η-comp)

То есть, если у вас есть funsplit, вы можете определить application и как указано выше, чтобы . Что еще интереснее, если у вас есть приложение и правила предложения, то вы можете определить funsplit.η(Π-Prop-η-comp)

Кроме того, funsplit строго сильнее приложения: правила пропационного эта не определимы в теории с единственным применением - следовательно, фунсплит не определим, так как тогда и правила пропа будут также. Интуитивно понятно, что это потому, что правила приложения дают вам немного больше времени: в отличие от funsplit (и т. Д.), Они не сообщают вам, что такое функции, а только то, что их можно применять к аргументам. Я считаю, что аргумент Ричарда можно повторить и для типов , чтобы показать тот же результат для против проекций.ΣsпLяT

Обратите внимание, что если бы у вас были определенные правила eta, вы бы наверняка использовали их и пропозиционально (с ). Таким образом, я думаю, что ваши утверждения «[...] которые дают нам для функций» и «[...] эта последняя презентация облегчает получение для пар» неверны. Agda, однако, реализует как для функций, так и для пар (если определена как запись), но это не следует только из приложения.η(м)знак равнорееL(м)ηηηΣ

Фредрик Нордвалл Форсберг
источник