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

Логическое программирование — это технология, позволяющая довольно близко приблизиться к воплощению декларативного идеала, описанного в главе 7, согласно которому системы должны конструироваться путем представления знаний на некотором формальном языке, а задачи решаться путем применения процессов логического вывода к этим знаниям. Такой идеал выражен в следующем уравнении Роберта Ковальского: Алгоритм = Логика + Управление

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

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

criminal(X) :- american(X), weapon(Y), sells(X,Y,Z), hostile(Z).

Язык Prolog включает "синтаксические упрощения" (syntactic sugar) для обозначения списков и арифметических выражений. Например, ниже приведена программа Prolog для предиката append (X, Y, Z), которая выполняется успешно, если список Z представляет собой результат дополнения списка Y списком X.

append([] , Y, Y) .

append([А|Х],Y,[A|Z]) :- append(X,Y,Z).

На естественном языке эти выражения можно прочитать так: во-первых, дополнение списка Y пустым списком приводит к получению того же списка Y, и, во-вторых, [А | Z] — это результат дополнения списка Y списком [А | X], при условии, что Z — это результат дополнения списка Y списком X. Такое определение предиката append на первый взгляд кажется весьма подобным соответствующему определению на языке Lisp, но фактически является гораздо более мощным. Например, в систему можно ввести запрос append (А, В, [1,2] ) — какие два списка можно дополнить один другим, чтобы получить [1,2]? Система возвратит следующие решения:

А=[]       В=[1,2]

А=[1]     В=[2]

А=[1,2]  В=[]

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

  • В нем предусмотрено множество встроенных функций для выполнения арифметических операций. Литералы, в которых используются соответствующие функциональные символы, "доказываются" путем выполнения кода, а не осуществления дальнейшего логического вывода. Например, цель "X is 4+3" достигается успешно после связывания переменной X со значением 7. С другой стороны, попытка достижения цели 5 is X+Y" оканчивается неудачей, поскольку эти встроенные функции не обеспечивают решения произвольных уравнений.
  • В языке предусмотрены встроенные предикаты, вызывающие при их выполнении побочные эффекты. К ним относятся предикаты ввода-вывода и предикаты assert/retract для модификации базы знаний. Такие предикаты не имеют аналогов в логике и могут порождать некоторые эффекты, вызывающие путаницу, например, если факты подтверждаются (и вводятся в базу знаний) некоторой ветвью дерева доказательства, которая в конечном итоге оканчивается неудачей.
  • В языке Prolog допускается определенная форма отрицания — отрицание как недостижение цели. Отрицаемая цель not Р считается доказанной, если системе не удается доказать Р. Таким образом, следующее высказывание: alive(X) :- not dead(X). можно прочитать так: "Любого следует считать живым, если нельзя доказать,что он мертв".
  • В языке Prolog предусмотрен оператор равенства, "=", но он не обладает всей мощью логического равенства. Цель с оператором равенства достигается успешно, если в ней два терма являются унифицируемыми, а в противном случае попытка ее достижения оканчивается неудачей. Таким образом, цель X+Y=2+3 достигается успешно, после связывания переменной X со значением 2, a Y — со значением 3, а попытка достижения цели mornings tar=evenings tar оканчивается неудачей. (В классической логике последнее равенство может быть или не быть истинным.) Не могут быть подтверждены (введены в базу знаний) какие-либо факты или правила, касающиеся равенства.
  • Из алгоритма унификации Prolog исключена проверка вхождения. Это означает, что могут быть сделаны некоторые противоречивые логические выводы; такая проблема возникает редко, за исключением тех ситуаций, когда язык Prolog используется для доказательства математических теорем.

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