Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Линейная зависимая теория типов

Как известно, в декартово-замкнутых категориях внутренним языком является лямбда-исчисление, а в моноидальных — линейная логика. В локально декартово-замкнутых категориях появляется возможность конструировать кроме типов X -> Y также зависимые типы (x : X) -> Y(x).

Какое же свойство является аналогом локальной замкнутости для моноидальных категорий? Вот тут (http://mathoverflow.net/questions/205902/what-is-the-monoidal-equivalent-of-a-locally-cartesian-closed-category) пишут, что это моноидальная замкнутость всех Comod-категорий данной категории.

То есть, для каждого кокоммутативного комоноида X из нашей категории, категория комодулей над ним должна быть моноидально замкнутой. Что такое кокоммутативные комоноиды? Да это "классические" (в смысле без ограничения линейности) типы, т.е. объекты, для которых клонирование и забывание элементов возможно и удовлетворяет всем естественным аксиомам. И вот для таких объектов X как раз должно быть возможно строить объекты вида (x : X) -> Y(x).

thedeemon: Звучит так, будто зависимые типы не должны быть линейными?

akuklev: Не совсем. Во всех публикациях по линейным зависимым типам именно такая фигня, кроме идеи МакБрайда про то, что не нужно чтобы в (x : X) -> Y(x) тип X был классическим, а нужно, чтобы терм Y(x) “не поглощал икса”, т.е. иксом можно только “параметризовать”, но нельзя икс элиминировать. Фактически это дополнительное требование к категории (дополнительное к моноидальной замкнутости всех комоноидных категорий), что для каждого типа X существует ещё тип Ghost(X), естественным образом наделённый структурой кокоммутативного комоноида и конструктором ⧘_⧙ : X -> Ghost(X), строго-инъективным в функториальном смысле (т.е. Id-типов), но без элиминаторов (как у вселенных, что обеспечивает параметричность).

Как такое свойство выразить категорно?
Subscribe

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 25 comments

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…