Как я могу интерпретировать правила набора текста на этой бумаге?

Эти правила ввода присутствуют на "О выразительности элементарной линейной логики: характеризующей Ptime и экспоненциальную иерархию времени" :

правила ввода

Из "Какую часть Милнера-Хиндли вы не понимаете?" Вопрос "Переполнение стека", я могу прочитать некоторые из них на английском языке, но все еще сложно чтобы выяснить, как сделать контролер типа из этого. Это моя попытка прочитать первые 4 правила:

  • Ax: как аксиома, если x имеет тип A, то x имеет тип A. (Это не очевидно?)

  • Вырезать. Если контекст Γ доказывает t has type A, а другой контекст ∆, расширенный с помощью утверждения x has type A, доказывает u has type B, то эти два контекста вместе, докажите, что замена всех вхождений x на t в u имеет тип B. (Что это значит, однако? Почему существуют два контекста, из которых возникает дополнительный, также как правило для замены, но как, если подстановка не является термином, а является ли операция? Классический Milner- У Хиндли нет ничего подобного: у него просто очень простое правило для приложения.)

  • Слабый. Если контекст доказывает t has type A, то этот контекст, расширенный с помощью выражения x has type B, все еще доказывает t has type A. (Опять же, это не так очевидно?)

  • Contr: если контекст, расширенный с помощью x1 has type !A и x2 has type !A proves t has type B, то этот контекст, расширенный с помощью x has type !A, доказывает замену всех вхождений x1 и x2 на x в t имеет тип B. (Еще одно правило для подстановки, похоже? Но почему есть два термина выше, один термин ниже? Кроме того, почему те ! s? Где все это будет отображаться на контроле типа?)

Я вполне понимаю, что эти правила хотят сказать, но я что-то пропустил, прежде чем он действительно щелкнет, и я смогу реализовать соответствующий тип проверки. Как я могу подойти к пониманию этих правил?

Ответы

Ответ 1

Это немного слишком широко, но из ваших комментариев я предполагаю, что вам не хватает базовых систем линейного типа. Эта система ослабевает (обычно не допускается в линейной логике), поэтому она фактически соответствует аффинной интуиционистской логике.

Основная идея: вы можете использовать каждое значение, которое у вас есть (например, переменные) не более одного раза.

Тип A (x) B (тензорный продукт) примерно соответствует типу значений пары, из которого вы можете проецировать как значение A, так и значение B.

Тип A -o B обозначает линейную функцию, которая потребляет значение A (помните: не более одного использования!) и выдает один B.

У вас может быть, например, \x.x : A -o A, но вы не можете иметь какой-либо термин : A -o (A (x) A), поскольку для этого потребуется дважды использовать аргумент.

Тип !A ( ", конечно, A!" ) означает значения типа A, которые можно дублировать, как и будет, - как это обычно бывает в нелинейных лямбда-исчислениях. Это выполняется по правилу сокращения.

Например, !A -o !B представляет собой обычную функцию: она требует значения (в неограниченном количестве копий) и создает значение (в неограниченном количестве копий). Вы можете написать функцию !A -o (!A (x) !A) следующим образом:

\a. (a (x) a)

Обратите внимание, что каждое правило линейного типирования с несколькими помещениями должно разбивать переменные среды между помещениями (например, один получает Gamma, другая Delta), без перекрытия. В противном случае вы можете дублировать линейные переменные. Из-за этого у Сократа есть два контекста. Нелинейным разрезом будет:

G |- t: A        G, x:A |- u: B
--------------------------------
  G |- u[t/x]: B

но здесь оба термина t и u могут использовать переменные в G, поэтому u[t/x] может использовать переменные дважды - нехорошо. Вместо этого линейный разрез

G1 |- t: A        G2, x:A |- u: B
--------------------------------
  G1,G2 |- u[t/x]: B

заставляет вас разделять переменные между двумя помещениями: то, что вы используете в t, недоступно для u.