Логическое программирование

Логика и программирование долгое время были непересекающимися областями исследований. Еще в 1936 г. Тьюринг показал, что любая вычислимая функция может быть вычислена посредством дедукции (вывода) в исчислении предикатов первого порядка, существующий вариант которого построен Г.Фреге в 1879 г. Однако этот результат не нашел практического применения, так как не был известен алгоритм установления общезначимости (истинности во всех интерпретациях) логической формулы. К тому же было показано, что эта проблема алгоритмически неразрешима. В 1930 г. Френч и Эрбран независимо доказали фундаментальную теорему, предоставляющую алгоритм, который способен установить общезначимость логической формулы, если она является таковой. В противном случае этот алгоритм зацикливается. Поэтому проблему установления общезначимости в исчислении предикатов первого порядка стали считать полуразрешимой. Разработанный алгоритм также не нашел практического применения вследствие большой трудоемкости. В 1962 г. Робинсон предложил метод резолюции, который обладает существенно меньшей трудоемкостью, чем алгоритм Эрбрана, однако все еще не решает проблему комбинаторного взрыва. В этом методе используется единственное мощное правило вывода вместо множества правил, предложенных логиками. Метод резолюции стал применяться в автоматическом доказательстве теорем. Одновременно предпринимались усиленные попытки поиска стратегий вывода, сокращающих пространство поиска. На этом пути были достигнуты заметные успехи.

Основываясь на полученных к тому времени результатах, французский ученый А.Кольмероэ создал язык PROLOG (PROgramming in LOGic - программирование в терминах логики), первоначально предназначенный для работы с естественными языками, и опубликовал его описание в 1973 г. Значительного сужения пространства удалось достичь за счет использования логической системы Хорна, являющейся частью исчисления предикатов, и линейной по входу стратегии резолюции. Но даже при таких ограничениях оказалось возможным представлять любую вычислимую функцию. (Заметим, что логика Хорна шире теории реляционных баз данных.) Большое значение в становлении, развитии и осмыслении PROLOG'а имели работы Р.Ковальского. Появление PROLOG'а открыло новую область исследований - логическое, или реляционное, программирование, где практические результаты зачастую предшествует их теоретическому осмыслению и обоснованию.

Центральным понятием в логическом программировании является отношение. Программа представляет собой совокупность определений отношений между объектами (в терминах условий, или ограничений) и цели (запроса). Процесс выполнения программы трактуется как процесс установления общезначимости логической формулы, построенной из программы по правилам, установленным семантикой того или иного языка. Результат вычисления является побочным продуктом этого процесса. В реляционном программировании нужно только специфицировать факты, на которых алгоритм основывается, а не определять последовательность шагов, которые требуется выполнить. Это свидетельствует о декларативности языков логического программирования. Она метко выражена в формуле Р.Ковальского: "алгоритм = логика + управление". В настоящее время известны и другие языки логического программирования.

Языки логического программирования характеризуются:

- сверхвысоким уровнем;

- жесткой ориентацией на символьные вычисления (числовая обработка затруднена);

- возможностью инверсных вычислений (переменные в вызовах "процедур" не делятся на входные и выходные), что является уникальной чертой реляционного программирования, хотя недавно разработан аналогичный подход и для функциональных языков;

- зачастую логической неполнотой в двух аспектах: невозможностью выразить в программе определенные логические конструкции, а также невозможностью получить из программы все правильные выводы.

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

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

В настоящее время существует примерно полтора десятка реализаций PROLOG'а, такие как Arity/Prolog и Turbo Prolog, оформленные в виде интегрированных сред. Наиболее удачным вариантом считается VISUAL PROLOG, работающий как Windows-приложение и поддерживающий технологию визуального программирования.