Вопрос по haskell, types – Как работает Джинн?

38

Хорошо, я понимаю, что, вероятно, пожалею об этом до конца своей жизни, но ... Как Джинн на самом деле работает?

В документации сказано, что он использует алгоритм, который является «расширением ЖЖ». и указывает на длинную путаницу о LJT. Насколько я могу судить, это большая сложная система сильно формализованных правил для определения того, какие логические утверждения являются истинными или ложными. Но это даже неbegin объяснить, как вы превращаете сигнатуру типа в исполняемое выражение. Предположительно все сложные формальные рассужденияinvolved как-то, но картина принципиально неполная.


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

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

Я подозреваю, что то, что делает Джинн, в основном просто, но я упускаю некоторые важные детали, которые объясняют, как вся эта сложная логическая гимнастика связана с исходным кодом Haskell ...

@DonStewart: я могу видеть, как тип является теоремой, а программа - доказательством. Я могу как-то увидеть, как вы можете сравнить доказательство с ЖЖ, чтобы увидеть, является ли доказательство действительным. Я не понимаю, как тыsearch для доказательства, если у вас его еще нет, то есть, как вы можете создать доказательство из ничего. MathematicalOrchid
Он находит доказательства для теорем, которые представляют типы. Любая программа с правильным типом является примером. Таким образом, благодаря Curry-Howard, вы можете перенять доказательную тактику поиска из теоремы, доказывающей вместо этого поиск программ данного типа. Don Stewart

Ваш Ответ

3   ответа
22

согласно изоморфизму Карри-Говарда, существует соответствие между типами и предложениями, а также значениями и доказательствами. Джинн использует эту переписку.

Будьте более конкретны, скажите, что вы хотите найти термин типа Haskell(a, b) -> (b, a), Сначала вы переводите тип в оператор в логике (Джинн использует пропозициональную логику, то есть без квантификаторов). Логическое утверждение идет(A and B) is true implies (B and A) is true, Следующий шаг - доказать это. Для логики высказываний всегда можно механически доказать или опровергнуть утверждение. Если мы можем опровергнуть это, то это означает, что не может быть соответствующего термина в (завершающем) Haskell. Если мы можем доказать это, то есть член Хаскелла такого типа, и, кроме того, член Хаскелла имеет точно такую же структуру, что и доказательство.

Последнее утверждение должно быть квалифицированным. Существуют различные наборы аксиом и правил вывода, которые вы можете использовать, чтобы доказать утверждение. Существует только соответствие между доказательством и термином Хаскелла, если вы выберете конструктивную логику. «Нормальная», то есть классическая логика имеет такие вещи, какA or (not A) как аксиома. Это будет соответствовать типу HaskellEither a (a -> Void), но в нем нет термина Хаскеля, поэтому мы не можем использовать классическую логику. Все еще верно то, что любое высказывание высказывания может быть доказано или опровергнуто в конструктивной логике высказываний, но это значительно более сложно, чем в классической логике.

Напомним, что Джинн переводит тип в пропозицию в логике, затем использует процедуру принятия решения для конструктивной логики, чтобы доказать предложение (если это возможно), и, наконец, доказательство переводится обратно в термин Хаскелла.

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

В качестве заключительного комментария для вас, чтобы задуматься:Either a (a -> Void) может быть реализовано, если у вас есть Схемыcall/cc, Выберите более конкретный тип, какEither a (a -> Int) и выяснить как.

@sanjoyd,plato.stanford.edu/archives/spr2004/entries/… кажется, есть несколько хороших ссылок.
& quot; В качестве заключительного комментария вы должны подумать: либо (a -> Void) может быть реализовано, если у вас есть вызов схемы / cc. Выберите более конкретный тип, такой как Either a (& gt; Int) и выясните, как. & Quot; Потому что Пирс эквивалентен ЛЕМ?
Мета-теорема о том, что любое пропозициональное утверждение разрешима, давно доказана логиками. Извините, у меня нет ссылки сейчас.
Во-вторых, как вы показываете, что «любое высказывание высказываний может быть доказано или опровергнуто в конструктивной логике высказываний»?
Да, закон Пирса эквивалентен LEM, но конструктивное доказательство этого также интересно.
32

какое отношение доказательство теорем имеет к программированию?

Строго типизированное программирование очень тесно связано с логикой. В частности, традиционные функциональные языки в традиции ОД тесно связаны синтуициониста Логика высказываний.

Слоган «Программы - это доказательства», предположение, что программа доказывает, - это ее тип.
В общем, вы можете думать о

 foo :: Foo

как сказать, чтоfoo является доказательством формулыFoo, Например тип

 a -> b  

соответствует функциям изa вbтак что если у вас есть доказательствоa и доказательствоa -> b у тебя есть доказательствоb, Итак, функции прекрасно соответствуют импликации в логике. так же

(a,b)

Соответствует соединению (логика и). Так что логика тавтологииa -> b -> a & b соответствует типу Haskella -> b -> (a,b) и имеет доказательство:

\a b -> (a,b)

это и есть «правило введения»; В то время как,fst :: (a,b) -> a а такжеsnd :: (a,b) -> b соответствуют 2 «правилам исключения»

так же,a OR b соответствует типу HaskellEither a b.

Это соответствие иногда называют «изоморфизмом Карри-Ховарда»; или & quot;Переписка Карри-Ховарда& Quot; послеХаскель Карри а такжеУильям Элвин Ховард

Эта история осложняется не тотальностью в Haskell.

Джинн "просто" доказательство теоремы.

Если вы заинтересованы в попытке написать клон, первая страница Google приводит результаты для & quot; Простая проверка теоремы & quot; имеетэтот статья, которая описывает написание теоремы для LK, которая написана на SML.

Редактировать: что касается «как доказательство теоремы возможно»? Ответ в том, что в некотором смысле это не сложно. Это просто проблема поиска:

Рассмотрим проблему, сформулированную так: у нас есть ряд предложений, которые мы знаем, как доказать S, и предложение, которое мы хотим доказать P. Что мы делаем? Прежде всего, мы спрашиваем: у нас уже есть доказательство P в S? Если это так, мы можем использовать это, если не мы можемpattern match на стр

case P of
   (a -> b) -> add a to S, and prove b (-> introduction)
   (a ^ b)  -> prove a, then prove b (and introduction)
   (a v b)  -> try to prove a, if that doesn't work prove b (or introduction)

если ни одна из этих работ

for each conjunction `a ^ b` in S, add a and b to S (and elimination)
for each disjunction `a v b` in S, try proving `(a -> P) ^ (b -> P)` (or elimination)
for each implication `a -> P` is S, try proving `a` (-> elimination)

Реальные доказатели теорем имеют некоторые хитрости, но идея та же. Область исследований «Процедуры принятия решений»; исследует стратегию поиска доказательств для определенных формул, которые гарантированно работают. С другой стороны, «Тактика» Рассматривает, как оптимально упорядочить поиск доказательства.

Относительно: «Как можно перевести доказательства в Haskell?»

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

Смысл введения:

\s -> ?

Или введение

Left
Right

И введение

\a b -> (a,b)

И устранение

fst
snd

так далее

В своем ответе augustss говорит, что то, как он реализовал это в Джинне, немного утомительно для такого ответа. Бьюсь об заклад, что вы можете понять, как реализовать это самостоятельно.

@MateticOrchid, но, по мнению ОМС, цепочка рассужденийis исполняемый код!
Документ не полностью ответил на вопрос, но он дал мне некоторые ключевые идеи, поэтому я принимаю этот ответ. MathematicalOrchid
Я вроде как понимаю ОМС. Мой реальный вопрос: «Если у меня есть цепочка рассуждений, подтверждающая мою теорему о типе, как мне перевести это в исполняемый код?» А также "как автоматическая теорема оказывается физически возможной?" Возможно, упомянутая вами статья объяснит последнее ... Я вернусь к вам, когда прочитаю. MathematicalOrchid
+1 за интересную статью, даже если она еще не ответила на мой главный вопрос. MathematicalOrchid
3

я смотрю на все это неправильно. , все эти формальные логические вещи просто отвлекают. Вместо того, чтобы смотреть на правила удержания для LJT или что-то еще, может быть, вещь, которую яshould делать - значит смотреть на Хаскелла.

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

Это даже не похоже на то, что вы должны генерировать все возможные выражения в поиске методом грубой силы. Если ни один из ваших аргументов не имеет типов функций, нет смысла пробовать приложения функций. Если все ваши аргументы являются переменными полиморфного типа,case Выражения не помогут вам. И так далее. Доступные типы сообщают вам, какие выражения могут работать.

Все становится немного интереснее, если вы позволяете своему коду вызывать существующие функции верхнего уровня. Помимо забавных проблем с областями видимости с полиморфными типами, существует вопрос выяснения того, какие функции вам помогут или не помогут.

Очевидно, мне придется уйти и немного подумать об этом ...

Вы, конечно, можете сделать это таким образом. Вы должны быть немного осторожны, если хотите убедиться, что поиск прекращается. Как для случая, когда есть термин, так и для случая, когда его нет. Например(a->a)->a->a имеет бесконечно много (разных) способов построения термина с этим типом.
Да, ясно, что некоторые типы не имеют реализации, а другие имеют бесконечность. Я хотел бы каким-то образом контролировать объем поиска. (Хотя я еще не выяснил, откуда вступают выборы ... Я уверен, что буду.) MathematicalOrchid
И делать это таким образом ничем не отличается от доказательства теорем. Причина, по которой я использовал средство доказательства теорем в Джинне, заключалась в том, что я знал, что для конструктивной логики существуют надежные и полные средства доказательства теорем, поэтому мне не пришлось изобретать новое.

Похожие вопросы