Главная arrow Логика arrow Логическое программирование
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

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

Логическое программирование — это технология, позволяющая довольно близко приблизиться к воплощению декларативного идеала, описанного в главе 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).