Каковы наиболее интересные эквивалентности, возникающие из изоморфизма Карри-Говарда?

https://stackoverflow.com/questions/2969140

24-10-2019
|

Вопрос

Я наткнулся на Изоморфизм Карри-Говарда относительно поздно в моей жизни программирования, и, возможно, это способствует тому, что я полностью очарован этим.Это означает, что для каждой концепции программирования существует точный аналог в формальной логике, и наоборот.Вот «основной» список таких аналогий, который пришел мне в голову:

program/definition        | proof
type/declaration          | proposition
inhabited type            | theorem/lemma
function                  | implication
function argument         | hypothesis/antecedent
function result           | conclusion/consequent
function application      | modus ponens
recursion                 | induction
identity function         | tautology
non-terminating function  | absurdity/contradiction
tuple                     | conjunction (and)
disjoint union            | disjunction (or)          -- corrected by Antal S-Z
parametric polymorphism   | universal quantification

Итак, на мой вопрос: каковы наиболее интересные/неясные следствия этого изоморфизма? Я не логик, поэтому уверен, что этим списком я лишь прикоснулся к поверхности.

Например, вот некоторые понятия программирования, для которых я не знаю содержательных названий в логике:

currying                  | "((a & b) => c) iff (a => (b => c))"
scope                     | "known theory + hypotheses"

И вот некоторые логические концепции, которые я не совсем сформулировал в терминах программирования:

primitive type?           | axiom
set of valid programs?    | theory

Редактировать:

Вот еще несколько эквивалентов, полученных из ответов:

function composition      | syllogism                -- from Apocalisp
continuation-passing      | double negation          -- from camccann

Решение

Поскольку вы явно спросили о самом интересном и непонятном:

Вы можете расширить CH на множество интересных логик и формулировок логик, чтобы получить действительно большое разнообразие соответствий.Здесь я постарался сосредоточиться на некоторых наиболее интересных, а не на малоизвестных, а также на паре фундаментальных, которые еще не возникли.

evaluation             | proof normalisation/cut-elimination
variable               | assumption
S K combinators        | axiomatic formulation of logic   
pattern matching       | left-sequent rules 
subtyping              | implicit entailment (not reflected in expressions)
intersection types     | implicit conjunction
union types            | implicit disjunction
open code              | temporal next
closed code            | necessity
effects                | possibility
reachable state        | possible world
monadic metalanguage   | lax logic
non-termination        | truth in an unobservable possible world
distributed programs   | modal logic S5/Hybrid logic
meta variables         | modal assumptions
explicit substitutions | contextual modal necessity
pi-calculus            | linear logic

РЕДАКТИРОВАТЬ:Справочник, который я бы порекомендовал всем, кто хочет узнать больше о расширениях CH:

«Осуждающая реконструкция модальной логики» http://www.cs.cmu.edu/~fp/papers/mscs00.pdf - это отличное место для начала, потому что оно начинается с первых принципов, и большая часть его предназначена для того, чтобы быть доступной для нелогиков/теоретиков языка.(Хотя я второй автор, поэтому я предвзят.)

Другие советы

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

Неурочение представляет противоречие-непоследовательная логика. Несовместимая логика, конечно Позвольте вам доказать что-либо, в том числе ложность, однако.

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

Основной особенностью конструктивистского вкуса является то, что двойное отрицание не эквивалентен не подложанию. Фактически, отрицание редко является примитивом в системе типа, поэтому вместо этого мы можем представлять его как подразумевающую ложь, например, not P становится P -> Falsity. Анкет Таким образом, двойное отрицание будет функцией с типом (P -> Falsity) -> Falsity, что явно не эквивалентно чему -то просто типу P.

Тем не менее, есть интересный поворот в этом! На языке с параметрическим полиморфизмом переменные типа диапазон по всем возможным типам, включая необитаемые, поэтому полностью полиморфный тип, такой как ∀a. a в каком-то смысле почти нередит. Так что, если мы пишем двойное практически отрицательное, используя полиморфизм? Мы получаем тип, который выглядит так: ∀a. (P -> a) -> a. Анкет Это эквивалентно чему -то типу P? Это действительно так, просто применить это к функции идентификации.

Но в чем смысл? Зачем писать такой тип? Имеет ли это иметь в виду Что -нибудь с точки зрения программирования? Ну, вы можете думать об этом как о функции, которая уже имеет что -то типа P где -то, и вам нужно, чтобы вы дали ей функцию, которая принимает P В качестве аргумента, поскольку все это полиморфно в конечном типе результата. В некотором смысле это представляет собой Приостановленные вычисления, ожидая, чтобы остальные были предоставлены. В этом смысле эти приостановленные вычисления могут быть составлены вместе, переданы, вызов, что угодно. Это должно начать звучать знакомо для поклонников некоторых языков, таких как схема или рубина-потому что это значит, что это то, что двойное отстранение соответствует Стиль продолжения продолжения, и на самом деле тип, который я дал выше, является именно той продолжением Монады в Хаскелле.

Ваша диаграмма не совсем правильно; Во многих случаях вы сбили с толку типы с терминами.

function type              implication
function                   proof of implication
function argument          proof of hypothesis
function result            proof of conclusion
function application RULE  modus ponens
recursion                  n/a [1]
structural induction       fold (foldr for lists)
mathematical induction     fold for naturals (data N = Z | S N)
identity function          proof of A -> A, for all A
non-terminating function   n/a [2]
tuple                      normal proof of conjunction
sum                        disjunction
n/a [3]                    first-order universal quantification
parametric polymorphism    second-order universal quantification
currying                   (A,B) -> C -||- A -> (B -> C), for all A,B,C
primitive type             axiom
types of typeable terms    theory
function composition       syllogism
substitution               cut rule
value                      normal proof

1] Логика для функционального языка, завершенного Тьюрингом, противоречивая. Рекурсия не имеет соответствия в последовательных теориях. В непоследовательной теории логики/неопровержимых доказательств вы можете назвать это правилом, которое вызывает несоответствие/неосвязность.

2] Опять же, это следствие полноты. Это было бы доказательством анти-теории, если бы логика была последовательной-таким образом, она не может существовать.

3] не существует на функциональных языках, поскольку они выдвигают логические особенности первого порядка: все количественное определение и параметризация выполняются по формулам. Если бы у вас были функции первого порядка, было бы непременно, кроме *, * -> *, так далее.; вид элементов области дискурса. Например, в Father(X,Y) :- Parent(X,Y), Male(X), X а также Y диапазон над доменом дискурса (называйте это Dom), а также Male :: Dom -> *.

function composition      | syllogism

Мне очень нравится этот вопрос. Я не знаю много, но у меня есть несколько вещей (помогая Статья Википедии, который имеет несколько аккуратных таблиц и такого самого):

Я думаю, что типы сумм/типы союза (например data Either a b = Left a | Right b) эквивалентны включительно дизъюнкция. И, хотя я не очень хорошо знаком с Карри-Ховардом, я думаю, что это демонстрирует это. Рассмотрим следующую функцию:
```
andImpliesOr :: (a,b) -> Either a b
andImpliesOr (a,_) = Left a
```
Если я правильно понимаю, тип говорит это (а ∧ беременный) → (а ★ беременный), и определение говорит, что это правда, где ★ либо инклюзивный, либо исключительный или, в зависимости от того, что Either представляет собой. У вас есть Either представляя эксклюзивную или, ⊕; Однако, (а ∧ беременный) ↛ (а ⊕ беременный) Например, ⊤ ∧ ⊤ ≡ ⊤, но ⊤ ⊕ ⊥ ≡ ⊥ и ⊤ ↛ ⊥. Другими словами, если оба а а также беременный это правда, тогда гипотеза истина, но заключение является ложным, и поэтому это значение должно быть ложным. Однако ясно, ((а ∧ беременный) → (а ∨ беременный), так как если оба а а также беременный верны, тогда по крайней мере один правда. Таким образом, если дискриминационные профсоюзы являются какой -то формой дизъюнкции, они должны быть инклюзивным разнообразием. Я думаю, что это считается доказательством, но вы не можете свободно отказаться от меня от этого понятия.
Точно так же ваши определения тавтологии и абсурда как функции идентификации и неконцентирующих функций, соответственно, немного выключены. Истинная формула представлена тип блока, это тот тип, который имеет только один элемент (data ⊤ = ⊤; часто пишется () и/или Unit в языках функционального программирования). Это имеет смысл: так как этот тип гарантированно Чтобы быть обитаемым, и, поскольку есть только один возможный житель, это должно быть правдой. Функция идентификации просто представляет собой конкретную тавтологию, которая а → а.

Ваш комментарий о неконтролирующих функциях в зависимости от того, что именно вы имели в виду, больше. Карри-ховард функционирует в системе типов, но не кодируется там. Согласно с Википедия, иметь дело с неверно, является проблемой, так как добавление его создает непоследовательную логику (например, Я могу определить wrong :: a -> b по wrong x = wrong x, и, таким образом, «доказать», что а → беременный для любого а а также беременный) Если это то, что вы имели в виду под «абсурдом», то вы совершенно правы. Если вместо этого вы имели в виду ложное утверждение, то вместо этого вы хотите какой -нибудь необитаемый тип, например что -то определено data ⊥- То есть тип данных без какого -либо способа его построения. Это гарантирует, что он вообще не имеет ценностей, и поэтому он должен быть необитаемым, что эквивалентно ложным. Я думаю, вы, вероятно, также могли бы использовать a -> b, Поскольку, если мы запрещаем неконтролирующие функции, это также необитаемо, но я не уверен на 100%.
Википедия говорит, что аксиомы кодируются двумя разными способами, в зависимости от того, как вы интерпретируете карри-ховард: либо в комбинаторах, либо в переменных. Я думаю, что представление комбинатора означает, что примитивные функции, которые мы даем, кодируют вещи, которые мы можем сказать по умолчанию (аналогично тому, как Modus Ponens является аксиомой, поскольку функциональное приложение является примитивным). И я считать То, что вид переменной может на самом деле означать одно и то же - в конце концов, комбинаторы являются просто глобальными переменными, которые являются конкретными функциями. Что касается примитивных типов: если я правильно думаю об этом, то я думаю, что примитивные типы - это сущности - примитивные объекты, о которых мы пытаемся доказать что -то.
Согласно моей логике и классам семантики, тот факт, что (а ∧ беременный) → в ≡ а → (беременный → в) (а также это беременный → (а → в)) называется законом эквивалентности экспорта, по крайней мере, в естественных доказательствах вычета. В то время я не заметил, что это было просто карри, я хотел бы, чтобы это было, потому что это круто!
Пока у нас теперь есть способ представить включительно Разнообразие, у нас нет способа представить эксклюзивное разнообразие. Мы должны быть в состоянии использовать определение исключительной дизъюнкции для представления его: а ⊕ беременный ≡ (а ∨ беременный) ∧ ¬(а ∧ беременный) Я не знаю, как написать отрицание, но я знаю, чтоп ≡ п→ ⊥, и как значение, так и ложь просты. Таким образом, мы должны представлять исключительную дизъюнкцию по:
```
data ⊥
data Xor a b = Xor (Either a b) ((a,b) -> ⊥)
```
Это определяет ⊥ быть пустым типом без значений, что соответствует ложению; Xor затем определяется, чтобы содержать оба (а также) Either атмосфера а или беременный (или же) и функция (значение) из (а, б) (а также) до нижнего типа (ЛОЖЬ). ~~Однако я понятия не имею, что это означает.~~ (РЕДАКТИРОВАТЬ 1: Теперь я это делаю, посмотри на следующий абзац!) Поскольку нет значений типа (a,b) -> ⊥ (Есть ли?), Я не могу понять, что это будет означать в программе. Кто -нибудь знает лучший способ подумать либо об этом определении, либо о другом? (РЕДАКТИРОВАТЬ 1: Да, Camccann.)

РЕДАКТИРОВАТЬ 1: Благодаря Ответ Камкканна (В частности, комментарии, которые он оставил на нем, чтобы помочь мне), я думаю, что вижу, что здесь происходит. Построить значение типа Xor a b, вам нужно предоставить две вещи. Во -первых, свидетель существования элемента любого a или же b как первый аргумент; это Left a или Right b. Анкет И во -вторых, доказательство того, что нет элементов обоих типов a а также b- Другими словами, доказательство того, что (a,b) необитаемо - как второй аргумент. Поскольку вы сможете написать только функцию из (a,b) -> ⊥ если (a,b) Является ли необитаемо, что значит для этого? Это будет означать, что какая -то часть объекта типа (a,b) не мог быть построен; другими словами, это по крайней мере один, и, возможно, оба, из a а также b также необитаемы! В этом случае, если мы думаем о сопоставлении рисунков, вы не могли бы матч с шаблонами на такой кортеже: предположить, что это b Является ли необитаемо, что бы мы написали, что могло бы соответствовать второй части этого кортежа? Таким образом, мы не можем обращать внимание против этого, что может помочь вам понять, почему это делает его необитаемой. Теперь единственный способ выполнить полную функцию, которая не принимает аргументов (как это должно (a,b) необитаемо), чтобы результат также был необитаемым типом-если мы думаем об этом с точки зрения соответствия моделям, это означает, что, хотя функция не имеет случая, нет никаких возможных тело Это могло бы иметь тоже, и поэтому все в порядке.

Многое из этого я думаю о вслух/доказывающем (надеюсь) вещах на лету, но я надеюсь, что это полезно. Я действительно рекомендую Статья Википедии; Я не читал его в каких -либо деталях, но его столы - действительно хорошее резюме, и это очень тщательно.

Вот слегка неясная, которую я удивлен, не был поднят ранее: «Классическое» функциональное реактивное программирование соответствует временной логике.

Конечно, если вы не философ, математик или навязчивый функциональный программист, это, вероятно, поднимает еще несколько вопросов.

Итак, во -первых: что такое функциональное реактивное программирование? Это декларативный способ работать с изменяющиеся во времени значения. Анкет Это полезно для написания таких вещей, как пользовательские интерфейсы, потому что входные данные пользователя - это значения, которые различаются со временем. «Классический» FRP имеет два основных типа данных: события и поведение.

События представляют значения, которые существуют только в дискретные времена. Ключи - отличный пример: вы можете придумать входные данные с клавиатуры как персонажа в данный момент времени. Каждый Keypress - это просто пара с символом клавиши и временем, которое он был нажат.

Поведение - это ценности, которые существуют постоянно, но могут постоянно меняться. Положение мыши является отличным примером: это просто поведение координат x, y. В конце концов, мышь всегда имеет позицию и, концептуально, эта позиция меняется постоянно Когда вы двигаете мышь. В конце концов, перемещение мыши - это единственное длительное действие, а не куча дискретных шагов.

А что такое временная логика? Соответственно, это набор логических правил для борьбы с количественными предложениями с течением времени. По сути, он расширяет нормальную логику первого порядка с двумя кванторами: □ и ◇. Первый означает «всегда»: читать □ φ как «φ всегда держит». Второе - «в конце концов»: ◇ φ означает, что «φ в конечном итоге будет держаться». Это особый вид модальная логика. Анкет Следующие два закона связывают квантификаторы:

□φ ⇔ ¬◇¬φ
◇φ ⇔ ¬□¬φ

Итак □ и ◇ двойные друг к другу так же, как ∀ и ∃.

Эти два квантификатора соответствуют двум типам в FRP. В частности, □ соответствует поведению и ◇ соответствует событиям. Если мы думаем о том, как эти типы населены, это должно иметь смысл: поведение населено в каждый Возможное время, в то время как событие происходит только один раз.

Относительно взаимосвязи между продолжениями и двойным отрицанием тип вызова/CC является законом Peirce http://en.wikipedia.org/wiki/call-with-current-continuation

CH обычно заявляется как соответствие между интуиционистской логикой и программами. Однако, если мы добавим оператор Call-with-current-continuation (CALLCC) (тип которого соответствует закону Пирса), мы получаем переписку между Классическая логика и программы с CallCC.

Хотя это не простой изоморфизм, это обсуждение конструктивного LEM очень интересный результат. В частности, в разделе «Заключение» Олег Киселев обсуждает, как использование монад для получения двойного отрицания устранения в конструктивной логике аналогично различению вычислительно уточнительных предложений (для которых LEM действителен в конструктивной обстановке) от всех предложений. Представление о том, что Monads захватывает вычислительные эффекты, является старым, но этот экземпляр карри-изоморфизм Howard помогает представить его в перспективе и помогает понять, что на самом деле двойное отстранение означает «означает« ».

Первоклассная поддержка продолжения позволяет выразить $ p lor neg p $. Хитрость основано на том факте, что не называть продолжение и выход с некоторым выражением, эквивалентно вызову продолжения с тем же выражением.

Для получения более подробного просмотра см.: http://www.cs.cmu.edu/~rwh/courses/logic/www handouts/callcc.pdf

2-continuation           | Sheffer stoke
n-continuation language  | Existential graph
Recursion                | Mathematical Induction

Одна вещь, которая важна, но еще не исследуется,-это связь 2-согласно Шеффер инсульт. Анкет В классической логике Sheffer Stroke может само по себе сформировать полную логическую систему (плюс некоторые концепции не оператора). Что означает знакомый and, or, not может быть реализован с использованием только Sheffer Stoke или nand.

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

Тип подписи 2-концентрации (a,b) -> Void. Анкет По этой реализации мы можем определить 1-концентрацию (нормальные продолжения) как (a,a) -> void, тип продукта как ((a,b)->Void,(a,b)->Void)->Void, тип суммы как ((a,a)->Void,(b,b)->Void)->Void. Анкет Это дает нам впечатляющую силу выразительности.

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow