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

Методология логического программирования.

Методология логического программирования - подход, согласно которому программа содержит описание проблемы в терминах фактов и логических формул, а решение проблемы система выполняет с помощью механизмов логического вывода.

Логическое программирование начинает свой отсчет времени с конца 60-х годов XX века, когда Корделл Грин предложил использовать резолюцию как основу логического программирования. Алан Колмеро создал язык логического программирования Prolog в 1971 году. Логическое программирование пережило пик популярности в середине 80-х годов XX века, когда оно было положено в основу проекта разработки программного и аппаратного обеспечения вычислительных систем пятого поколения.

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

Одним из недостатков логического подхода в концептуальном плане является специфичность класса решаемых задач.

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

Нелинейность структуры программы является особенностью декларативного подхода и, строго говоря, представляет собой оригинальную особенность, а не объективный недостаток.

в качестве примеров языков логического программирования можно привести Prolog (название возникло от слов PROgramming in LOGic) и Mercury.

Методы и концепции.

Метод единообразия заключается в одинаковом применении механизма логического доказательства ко всей программе.

Метод унификации - это механизм сопоставления с образцом для создания и декомпозиции структур данных.

Общие сведения о языке Prolog, связь с исчислением предикатов.

ПРОЛОГ является языком исчисления предикатов. Предикат – это логическая формула от одного или нескольких аргументов. Можно ска- зать, что предикат – это функция, отображающая множество произволь- ной природы в множество {ложно, истинно}.

Обозначаются предикаты F(x), F(x, y), F(x, y, z) и т. д..

Одноместный предикат F(x), определенный на предметной области M, является истинным, если у объекта x есть свойство F, и ложным – если этого свойства нет.

Двухместный предикат F(x, y) является истинным, если объекты x и y находятся в отношении F.

Многоместный предикат F(x1 , x2 , x3 ,..., xN ) задает отношение меж- ду элементами x1 , x2 , ..., xN и интерпретируется как обозначение высказывания: “Элементы x1 , x2, x N находятся между собой в отношении F”.

При разработке логических программ предикаты получают обычно названия, соответствующие семантике описываемой предметной области.

Примеры предикатов:

хищник (Х)

супруги (X,Y)

фио (X,Y,Z)

Предикаты, которые нельзя разбить на отдельные компоненты, на- зывают атомарными. Сложные формулы строятся путем комбинирова- ния атомарных предикатов логическими соединителями И, ИЛИ и НЕ.

Пролог (Prolog) - это программирование на языке логики.

Этот язык используется для задач, которые сводятся к объектам и отношениям между ними.

Пролог является реляционным языком.

Пользоваиель должен установить какие формальные отношения и объекты существуют в решаемой задаче и установить какие отношения справедливы для поиска решения.

Пролог - это декларативный язык. Он отличается от процедурных (императивных) языков:

• императивный - как делать

• декларативный - что делать

Порядок выполнения Пролог программы определяется:

• семантикой языка

• новыми фактами, которые Пролог выводит из имеющихся

• отчасти той управляющей информацией, которую задает программист

Пролог - это логический язык, в котором реализована логика предикатов 1-го порядка.

В самом языке предусмотрены элементы интеллектуальности:

• сопоставление с образцом

• поиск с возвратом

• недетерменизм

Модель вычислений

• Система реализующая логический вывод в исчислении предикатов 1-го порядка

• Хорнова модель вычислений: доказательство некоторых формул исчисления как вычисление

• "Выражение Хорна" (дизъюнкты,клаузы) + принцип резолюции (как логический вывод)

1. A(t₁,t₂...t_n) - факт

A - формула

t₁,t₂...t_n - термы

2. ~A₁V~A₂V...~A_nVA_m

(тут используют только имена формул, скобки и термы опущены)

3. Правило преобразования дизъюнкции в конъюнкции:

A₁&A₂&...&A_n-->A_m

"Из A₁ и ... A_n следует A_m"

• В качестве механизма логического вывода используется метод резолюции с формулами: A₁VA₂...VA_n

Это регулярная процедура последовательного сопоставления с образцом (алгоритм унификации)

A₁&A₂&...&A_n-->A_m

A₁,A₂,...,A_n - подцели

A_m - цель

Доказательство правила выполняется от подцели к цели.

Этапы программирования на Прологе

• объявление фактов об объектах и отношениях

• определение правил

• формировки вопросов

Пример 1:

Факты	Объекты	Отношение
"Иван - отец Алексея"	"Иван","Алексей"	отец
"Серебро - ценное"	серебро	ценное
"Петр дает книгу Ольге"	"Петр",книга,"Ольга"	дает

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

Отношение:  отец("Иван","Алексей").  ценное(серебро).  дает("Петр","Ольга",книга).

? - отец("Иван",Y).  Y - переменная

Концепция резолюции в языке Prolog.

Логическое программирование основывается на логическом выводе и доказательстве теорем, которые позволяет осуществлять исчисление предикатов. Одним из используемых для этого методов является резолюция — правило логического вывода, позволяющее получать одни высказывания из других. Для использования принципа резолюции логические высказывания должны быть приведены к дизъюнктивной форме, имеющей следующий общий вид: A₁ÙA₂Ù…ÙA_m®B₁ÚB₂Ú…ÚB_n или, сокращенно, A®B, где A_i и B_j — термы. Ограниченный вид дизъюнктивных форм, называемый хорновскими дизъюнктами илидизъюнктами Хорна, позволяет упростить процесс логического вывода на основе резолюции. В хорновском дизъюнкте заключение либо отсутствует (дизъюнкт без головы), либо содержит единственный терм (дизъюнкт с головой). Концепция резолюции заключается в следующем. Предположим, что заданы два следующих высказывания: A®B и B®C. Логически из этого следует, что A®C. Процесс вывода этого высказывания представляет собой резолюцию и в упрощенном виде выглядит следующим образом. Образуется новое высказывание, левая часть которого есть конъюнкция левых частей исходных высказываний, а правая часть — конъюнкция их правых частей, т.е. (AÙB)®(BÙC). Затем термы, появляющиеся в обеих частях нового высказывания, удаляются из него, в результате чего получается выводимое высказывание. Наличие переменных в высказываниях приводит к необходимости выполнять в процессе резолюции поиск их значений, позволяющих установить соответствие между термами. Алгоритм определения необходимых подстановок значений переменных с целью приведения в соответствие двух выражений исчисления предикатов называетсяунификацией. Временное присваивание значений переменным с целью унификации называется конкретизацией. Обычно во время резолюции переменная конкретизируется неким значением, не полностью удовлетворяющим требуемому соответствию. В этом случае надо конкретизировать эту переменную новым значением. Процесс возврата к предыдущему состоянию называетсябектрекингом (backtracking).

Предикаты (факты), правила, цели.

Все операторы в языке Prolog образуются из термов. Терм может быть константой, переменной или структурой, составленной из других термов. Константа — это атом или целое число. Переменная — это любая строка букв, цифр и символов подчеркивания, начинающаяся с прописной буквы. Связывание переменной со значением и типом называется конкретизацией и происходит только в процессе резолюции. Конкретизации осуществляются только для того, чтобы удовлетворить некую цель, представляющую собой доказательство или опровержение некоторого высказывания. Структура соответствует атомарному высказыванию исчисления предикатов и имеет ту же форму: функтор(терм₁, …, терм_n). Функтор может быть любым атомом и служит для идентификации структуры. В языке Prolog структуры используются для формулирования фактов и правил. Структура устанавливает некоторое отношение между соответствующими термами. В то же время, когда структура рассматривается как запрос, она представляет собой предикат. Программа на языке Prolog состоит из набора фактов и правил, образующих базу данных, на основе которой логически может быть выведена новая информация. Простейшая форма хорновского дизъюнкта без головы в языке Prolog представляет собой отдельную структуру, интерпретируемую как факт, то есть высказывание, которое предполагается истинным. Оператор языка Prolog, соответствующий хорновскому дизъюнкту с головой и называемый правилом, имеет следующий общий вид: <структура₀> :- <структура₁>, …, <структура_n> где <структура₀> представляет собой заключение, а <структура₁>, …, <структура_n> — предпосылки. Разделяющая предпосылки запятая соответствует оператору конъюнкции. Если высказывания содержат переменные, то подразумевается, что переменные неявно связаны с квантором всеобщности. Данный оператор интерпретируется как правило «если то», а именно: если предпосылка является истинной или она может быть сделана истинной путем некоторой конкретизации её переменных, то следствие считается истинным. Факты и правила представляют сведения, необходимые для решения задачи. Для описания того, что требуется получить, служат высказывания, называемые целямиили запросами. В языке Prolog цель имеет синтаксическую форму, эквивалентную форме хорновского дизъюнкта без головы. Определение цели соответствует формулировке теоремы, которую система должна доказать или опровергнуть на основе заданных фактов и правил. На любой корректный запрос система реализации языка Prolog должна дать ответ “yes” или “no”. Ответ “yes” означает, что система доказала, что цель была истинной при заданных фактах и правилах. Ответ “no” указывает, что либо было доказано, что цель ложна, либо система неспособна ни доказать, ни опровергнуть её на основе имеющихся сведений. В качестве целей могут выступать высказывания в форме конъюнкции и высказывания, включающие переменные. Если цель включает в себя конъюнкцию фактов или структур, то они называются подцелями. При наличии переменных система пытается найти их конкретизации, делающие цель истинной.

Организация повторов в языке Prolog.

В Прологе для этого используются процедура поиска с возвратом (откат) и рекурсия. Откат дает возможность получить много решений в одном запросе к программе, а рекурсия позволяет использовать в процессе определения предиката его самого.

БАЗИС РЕКУРСИИ - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии.

ШАГ РЕКУРСИИ - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле.

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

НЕДОСТАТОК: может не хватать для работы стека. При каждом рекурсивном вызове предиката в специальном стековом фрейме запоминаются все промежуточные переменные, которые могут понадобиться. Максимальный размер стека при работе под управлением операционной системы MS DOS всего 64 Кб. Этого достаточно для размещения около трех-четырех тысяч стековых фреймов (в зависимости от количества и размера промежуточных переменных). При больших входных значениях стека может не хватить.

Есть, правда, один вариант рекурсии, который использует практически столько же оперативной памяти, сколько итерация в императивных языках программирования. Это так называемая хвостовая или правая рекурсия. Для ее осуществления рекурсивный вызов определяемого предиката должен быть последней подцелью в теле рекурсивного правила и к моменту рекурсивного вызова не должно остаться точек возврата (непроверенных альтернатив). То есть у подцелей, расположенных левее рекурсивного вызова определяемого предиката, не должно оставаться каких-то непроверенных вариантов и у процедуры не должно быть предложений, расположенных ниже рекурсивного правила.

Литература: [1], [5].

ПРОЕКТИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ В ОБРАЗОВАНИИ