Какова интуиция за линейной логикой?

Я пытаюсь понять линейную логику, чтобы лучше понять системы линейного типа. Однако, когда я прочитал правила, я не в состоянии получить интуицию позади него , как я сделал в модальной логике - $\Box A$ означает требуются , как в Крипке кадров требуются для каждого достижимого мира [ является возможно с учетом необходимыми изменения]. Но я не могу найти какое-либо интуитивное объяснение двойственности и того, какая из пар соединения / дизъюнкции (если есть) соответствует и . $A$ $A$ $\Diamond A$ $A$ $\land$ $\lor$

lo.logic type-theory linear-logic Мацей Печотка
источник

Оригинальная статья Жирара - это то место, куда вы должны обратить внимание, если хотите понять интуицию, стоящую за ними. Вопрос как таковой является слишком общим imo, и ответ будет состоять в том, чтобы взглянуть на страницу Википедии для линейной логики.

Каве

Я согласен, что это слишком сложный вопрос и, безусловно, не уровень исследований, возможно, вам следует задать вопрос по CS Stack Exchange. Тем не менее, я бы не рекомендовал использовать оригинальную статью Жирара в качестве отправной точки для линейной логики. Может быть, Wikipedia - лучшее место для начала.

Дамиано

Это довольно широко. Возможно, предложение может начать рассматривать формулы как «валюту», которую можно тратить, вместо утверждений правды. Затем соединение может быть

означает , что мы можем проводить как в

монету и

монету. Другим видом соединения может быть

, что означает, что мы можем выбирать между расходами

и расходами

(но не обоими!). Вы можете найти несколько примеров в Википедии, как предложил Дамиано.

a \otimes b

$a \otimes b$

a

$a$

b

$b$

a & b

$a \& b$

a

$a$

b

$b$

Чи

@chi Я не уверен, что «интерпретация ресурсов» - лучший способ понять дуальность в LL. Процесс интерпретации гораздо более понятен.

Мартин Бергер

Я не уверен, что этот вопрос идеально подходит для CSTheory, но, учитывая, что он уже собирает голоса, вот ответ, который кто-то мог бы дать, если бы этот вопрос был размещен на cs.stackexchange .

Чтобы понять понятие дуальности линейной логики , которое разделяет конъюнкцию и дизъюнкцию гораздо дальше, чем мы привыкли в обычной логике, я рекомендую не рассматривать линейную логику с точки зрения ресурсов (хотя это важное чтение ). Вместо этого думайте о линейных логических формулах как о процессах, которые взаимодействуют в порту / имени / канале. Насколько мне известно, эта интерпретация была впервые изложена в (1), но уже упоминалась в оригинальной работе Жирара. Как изображение: $(\cdot)^{\bot}$ $A$

(Я не знаю , как правильно центр изображений здесь.) Линейное соединение интерпретируются как запущенные процессы и в параллели . Процесс передает пары на своем порте, где происходит от и является связи «с. $A \otimes B$ $A$ $B$ $A \otimes B$ $(a, b)$ $a$ $A$ $b$ $B$

Дуализация (что является отрицанием линейной логики) переключает вход и выход. Следовательно, сопряженное является $(.)^{\bot}$ $A \otimes B$

(A \otimes В)^{⊥} знак равно A^{⊥} ⅋ В^{⊥}

$(A \otimes B)^{\bot} \quad = \quad A^{\bot} ⅋ B^{\bot}$

В этом чтение представляет собой процесс , который взаимодействует с . $A^{\bot} ⅋ B^{\bot}$ $A \otimes B$

Линейный логический эквивалент дизъюнкции может быть дан аналогично теоретико-процессуальному чтению. Формула

A & В

$A\ \&\ B$

также следует рассматривать как два процесса и параллельно, но вместо того, чтобы активно отправлять сообщения, они ждут, когда среда решит, какой запускать. Так сидит там, ожидая ее русло немного информации , которая принимает решения , если должны работать как или . Это «параллельная» версия на языках последовательного программирования. Двойной $A$ $B$ $A \& B$ $A \& B$ $A$ $B$ $if/then/else$ $(A \& B)^{\bot}$ из является $A \& B$

(A & В)^{⊥} знак равно A^{⊥} \oplus В^{⊥}

$(A \& B)^{\bot} \quad = \quad A^{\bot} \oplus B^{\bot}$

может рассматриваться как процесс отправки 1 бита информации в , а именно: «продолжить как » или «продолжить как ». Это похоже на в , вычисляемые , а , вычисляемая , за исключением того, что при выборе между $A \& B$ $A$ $B$ $if\ true\ then\ P\ else\ Q$ $P$ $if\ false\ then\ P\ else\ Q$ $Q$ и теперь сделаны окружающей средой. $A$ $B$

Оператор! Также имеет теоретико-процессную интерпретацию: если

читается как процесс, то

можно читать как выполняющий бесконечно много процессов

параллельно.

A

$A$

! A

$!A$

A

$A$

При этом чтении аксиом линейных логики становится простыми проводами «» , которые пересылают сообщения от процессов к процессам . Эта интерпретация аксиом уже есть в сетках доказательства Жирара (3). $A \vdash A$ $A^{\bot}$ $A$

Эта теоретико-процессуальная интерпретация оказала влияние и породила много последующей работы, такой как, например, (2) для типов сеансов. Тем не менее, есть некоторые крайние случаи, которые делают его немного неловким, и, насколько мне известно, он не был создан для идеальной работы для полной линейной логики даже в 2017 году.

_{1. Абрамский С. Вычислительные интерпретации линейной логики .

2. П. Вадлер, Предложения как сеансы .

3. Википедия, Сеть доказательств .}

Мартин Бергер
источник

Какова интуиция за линейной логикой?

Ответы: