Вопрос о логике и переписке Карри-Говарда

Question

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

Answer 1

Переписка карри-Говарда не о логическом программировании, а функциональное программирование. Фундаментальный механик пролога оправдан в теории доказательства Джона Робинсона Техника разрешения, который показывает, как можно проверить, выражаются ли логические формулы, выраженные в качестве пункта рога Удовлетворенность, То есть, можете ли вы найти условия для подстановки для их логических переменных, которые делают их верными.

Таким образом, логическое программирование состоит в том, чтобы указывать программы в качестве логических формул, и расчет программы является некоторой формой достойного вывода, в прологе reolution, как я уже сказал. Напротив, корреспонденция Curry-Howard показывает, как доказательства в специальном формультере логики называются естественный вычет, соответствует программам в исчислении лямбда, с типом программы, соответствующей формуле, подтверждающую доказательство; Вычисление в исчислении лямбда соответствует важному феномену в теории доказательства, называемой нормализацией, которая преобразует доказательства в новые, более прямые доказательства. Таким образом, логическое программирование и функциональное программирование соответствуют разным уровням в этих логиках: логические программы соответствуют формулам логики, в то время как функциональные программы соответствуют доказательствам формул.

Есть еще одно отличие: используемые логики обычно различны. Логическое программирование обычно использует более простые логики - как я уже говорил, Prolog основан на главных пунктах, которые являются высокоограниченным классом формул, в которых это не вложилось, и не существует никаких разногласий, хотя пролог восстанавливает полную прочность классической логики с использованием Вырезать правило. Напротив, функциональные языки программирования, такие как Haskell, придерживаются тяжелых применений программ, типы которых вложили последствия и украшены всеми видами форм полиморфизма. Они также основаны на интуитурной логике, классу логики, которые запрещают использовать принцип исключенного середина, на котором вычисляется вычислительный механизм Робинсона.

Некоторые другие очки:

1. Можно базовое логическое программирование на более сложных логиках, чем роговые пункты; Например, лямбда-пролог основан на интуитуистической логике с различным механизмом вычислений, чем разрешение.
2. Дейл Миллер назвал кормовой парадигмой для логики. Доказательство поиска как программирование метафора, чтобы контрастировать с Доказательства как программы Метафора, которая является еще одним термином, используемой для корреспонденции Curry-Howard.

Answer 2

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

Таким образом, поиск доказательств в логическом программировании можно использовать для поиска доказательств, которые затем интерпретируются как функциональные программы.Кажется, это самая прямая связь между ними (как вы и просили).

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