Где исследуется реляционная параметричность в моделях гипердоктрины или топоса?

9

Рейнольдс первоначально предложил реляционную семантику для полиморфного лямбда-исчисления второго порядка [1]. Однако позднее он показал [2], что этот подход не согласуется с классической теорией множеств. Питтс описал структуру гипердоктринных моделей и топос-моделей [3], которые согласуются с конструктивной логикой.

Предположительно, тогда были разработаны реляционные модели гипердоктрина и топоса. Где я могу прочитать о них?

  • [1] Типы, абстракция и параметрический полиморфизм
  • [2] Полиморфизм не является теоретико-множественным
  • [3] Полиморфизм задан теоретически, конструктивно
Том Эллис
источник

Ответы:

10
  • По техническим причинам не было большой работы над параметрическими топографическими моделями. Внутренняя логика топоса является формой теории множеств, и непредсказуемое индексирование в стиле F и аксиома powerset несовместимы. Посмотрите, что нетривиальные типы власти Энди Питтса не могут быть подтипами полиморфных типов :

    Эта статья устанавливает новую, ограничивающую связь между полиморфным лямбда-исчислением и разновидностью теории типов высшего порядка, которая воплощена в логике топосов. Показано, что любое вложение в топос декартовой замкнутой категории (закрытых) типов модели полиморфного лямбда-исчисления должно располагать полиморфные типы достаточно далеко от степенных типов P (X) топосов в том смысле, что что P (X) является подтипом полиморфного типа только в том случае, если X пусто (и, следовательно, P (X) является терминальным). В качестве следствия получаем усиление результата Рейнольдса о несуществовании теоретико-множественных моделей полиморфизма.

    В результате, даже если вы можете дать юниверсу интерпретацию типов F в топос-логике, вы не можете позволить ему интересным образом взаимодействовать с полной вселенной множеств. Однако еще не все потеряно!

    1. Тот факт, что (непараметрическая) вселенная множеств, интерпретирующая Систему F, означает, что вы можете дать параметрическую модель Системы F во внутренней логике топоса, гораздо проще, чем в обычной теории множеств. По сути, вам не нужно возиться с PER, поскольку вы можете просто предположить, что у вас есть подходящая коллекция наборов. Боб Атки использовал эту идею в своей работе « Реляционная параметричность для высших видов» , где он разработал параметричность дляFω работая в нечетком исчислении конструкций.

    2. Другой реакцией на результат Питтса является не работа с теорией множеств, а теория зависимых типов. Поскольку в теории зависимых типов нет формирователя типа мощности, вам не нужно беспокоиться о взаимодействии типов мощности и полиморфизма. См. Атки, Гани и Иоганна. Реляционно-параметрическая модель теории зависимых типов .

  • Однако нет таких препятствий для построения моделей гипердоктрины, где члены Системы F являются объектами логики. Исследования в этом направлении, вероятно, были начаты Абади и Плоткиным в их основополагающей статье «Логика параметрического полиморфизма» . Ларс Биркедал и его сотрудники интенсивно работали над созданием категориальных моделей для этой и подобных логик - см., В частности, Теоретико-категориальные модели Биркедала, Могелберга и Петерсена для линейной логики Абади и Плоткина , которая дает логику для рассуждений о линейной системе F плюс доказательство того, что оно обоснованно и полно по отношению к определенному классу категориальных моделей.

Нил Кришнасвами
источник