Логическое программирование
Логическое программирование — это технология, позволяющая довольно близко приблизиться к воплощению декларативного идеала, описанного в главе 7, согласно которому системы должны конструироваться путем представления знаний на некотором формальном языке, а задачи решаться путем применения процессов логического вывода к этим знаниям. Такой идеал выражен в следующем уравнении Роберта Ковальского:
Алгоритм - Логика + Управление
Одним из языков логического программирования, намного превосходящим все прочие по своей распространенности, является Prolog. Количество его пользователей насчитывает сотни тысяч. Он используется в основном в качестве языка быстрой разработки прототипов, а также служит для решения задач символических манипуляций, таких как написание компиляторов [1536] и синтаксический анализ текстов на естественном языке [1208]. На языке Prolog было написано много экспертных систем для юридических, медицинских, финансовых и других проблемных областей.
Программы Prolog представляют собой множества определенных выражений, записанных в системе обозначений, немного отличающейся от используемой стандартной логики первого порядка. В языке Prolog прописные буквы применяются для обозначения переменных, а строчные — для обозначения констант. Выражения записываются с головой, предшествующей телу; символ : - служит для обозначения импликации, направленной влево, запятые разделяют литералы в теле, а точка обозначает конец высказывания, как показано ниже.
criminal(X) :- american(X), weapon(Y), sells(X,Y,Z), hostile(Z).
Язык Prolog включает "синтаксические упрощения" (syntactic sugar) для обозначения списков и арифметических выражений. Например, ниже приведена программа Prolog для предиката append (х, Y, Z), которая выполняется успешно, если список Z представляет собой результат дополнения списка Y списком х.
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" оканчивается неудачей, поскольку эти встроенные функции не обеспечивают решения произвольных уравнений5.
• В языке предусмотрены встроенные предикаты, вызывающие при их выполнении побочные эффекты. К ним относятся предикаты ввода-вывода и предикаты 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). Мы вернемся к этой теме после рассмотрения того, как реализована система Prolog.