- •Часть 1
- •1. Введение
- •2. Теоретические основы логического программирования.
- •2.1 Основные определения логики предикатов первого порядка
- •2.2 Стандартные формы представления формул исчисления предикатов.
- •3. Синтаксис языка программирования Пролог.
- •3.1. Основные элементы языка Пролог.
- •3.2. Представление клауз Хорна на языке Пролог. Факты. Правила. Вопросы.
- •3.2.1. Представление фактов в Пролог—программах.
- •3.2.2. Вопросы.
- •3.2.3. Правила.
- •3.2.4. Подстановки и примеры утверждений.
- •3.2.5. Пример Прологпрограммы.
- •4. Семантика языка программирования Пролог.
- •4.1 Декларативная и процедурная семантика программ на языке Пролог.
- •4.2. Вычислительная модель логической программы.
- •4.2.1. Унификация термов.
- •4.2.2. Общая схема согласования целевых утверждений.
- •4.2.3 Механизм поиска с возвратом.
- •5. Рекурсивное программирование на языке Пролог.
- •5.1 Рекурсивные правила.
- •5.2 Схема поиска решений в рекурсивных программах.
- •5.3. Списки и их представление на Прологе.
- •Основные определения.
- •Унификация списков.
- •Предикат list.
- •Типовые процедуры обработки списков на языке Пролог.
- •Предикат length.
- •5.4.2. Предикат member.
- •Предикат first.
- •Предикат last.
- •Предикат next.
- •Предикат append.
- •Предикат add.
- •Предикаты revers1 и revers2.
- •Предикат delete.
- •5.4.10. Предикат number_list.
- •5.4.11. Предикат sumlist.
- •5.4.12. Предикат delrepeat.
- •5.5 Множества и их представление на языке Пролог. Простые программы обработки множеств.
- •Основные определения.
- •Предикат unionset.
- •Пересечение множеств.
- •Разность множеств.
- •Определение подмножества.
- •5.5.6. Декартово произведение множеств.
- •Прологпрограммы сортировки списков.
- •Метод прямого выбора.
- •Метод вставки.
- •5.6.3. Метод перестановок.
- •6. Стандартные предикаты языка Пролог.
- •Арифметические предикаты.
- •6.2. Предикаты сравнения арифметических выражений и символьных термов.
- •6.3. Предикаты определения типов термов.
- •6.4. Примеры программ с использованием арифметических предикатов.
- •6.5. Предикаты вводавывода термов и символов.
- •6.5.1. Ввод/вывод термов.
- •6.5.2. Ввод/вывод символов.
- •6.6. Стандартные предикаты управления логическим выводом.
- •6.7. Стандартные предикаты обработки списков.
- •6.8. Стандартные предикаты обработки строк.
- •7. Система программирования Arity Prolog 5.0.
- •Описание среды программирования Arity Prolog 5.0.
- •Методические указания по лабораторным работам.
- •7.2.1. Лабораторная работа № 1. Простейшая программа на языке Пролог.
- •7.2.2. Лабораторная работа № 2. Использование арифметических операций и унификации арифметических выражений.
- •7.2.3. Лабораторная работа 3.1. Создание базы данных “Cессия” и запросов к этой базе данных на языке Пролог с использованием стандартного предиката fail.
- •Приложение 2. Варианты заданий по лабораторной работе 4.
- •Приложение 3. Варианты заданий по лабораторной работе 5.
- •Список литературы.
4.2.3 Механизм поиска с возвратом.
Для того, чтобы представить работу механизма автоматического возврата удобно воспользоваться понятием маркера. Маркер отмечает текущее утверждение в программе, сопоставимое с целью. Для каждой цели в запросе Прологсистема создает свой собственный маркер, который будем обозначать значком “”. Маркеры могут передвигаться только вперед. Однако, когда цель начинает согласовываться сначала, соответствующий маркер устанавливается на первое утверждение, заголовок которого совпадает с именем предикатацели.
Рассмотрим этот процесс на примере. Пусть программа «Однокурсники» содержит следующие утверждения:
(1) student_course(X,Y):student(X,K1), student(Y,K2),X\=Y,K1=K2.
(2) student(‘Иванов’,1).
student(‘Петров’,4).
student(‘Сидоров’,2).
(5) student(‘Кузнецов’,4).
Пусть требуется согласовать запрос:
? student_course(X,Y).
Этот запрос сопоставим с первым утверждением, которое является правилом, поэтому производится редукция цели, и текущая резольвента примет вид:
ТР: student(X,K1), student(Y,K2),X\=Y,K1=K2.
Создадим маркер 1 для первой цели в резольвенте student(X,K1) и маркер 2 для второй цели в резольвенте student(Y,K2).
При просмотре фактов student в программе маркеры будут передвигаться следующим образом:
(2) student(‘Иванов’,1). 1 2 (no) 2 (no)
(3) student(‘Петров’,4). 2 (no) 1 2 (no)
(4) student(‘Сидоров’,2). 2 (no) 2 (no)
(5) student(‘Кузнецов’,4). 2 (no) 2 (yes)
возврат 1-й цели успешный
вывод
при подстановке {X=‘Петров’; Y=‘Кузнецов’}.
Таким образом, ответ на запрос будет выдан в следующем виде:
? student_course(X,Y).
X=‘Петров’
Y=‘Кузнецов’ >
Получив решение, Прологсистема предлагает пользователю решить, нужно ли искать другие решения. При нажатии клавиши «;» интерпретатор Пролога выполняет возврат на первую цель и переставляет маркер 1 на предложение 3 программы, а маркер 2 на первое предложение.
(2) student(‘Иванов’,1). 2 (no) 2 (no)
(3) student(‘Петров’,4). 2 (no) 2(yes) (4) student(‘Сидоров’,2). 1 2 (no)
(5) student(‘Кузнецов’,4). 2 (no) 1 возврат 1-й цели успешный
вывод
при подстановке {X=‘Петров’; Y=‘Кузнецов’}.
Не найдя второкурсников, кроме Сидорова система сама производит возврат и переставляет маркер 1 на предложение 4 программы, а маркер 2 на первое предложение.
Таким образом, ответ на запрос будет выдан в следующем виде:
? student_course(X,Y).
X=‘Кузнецов’
Y=‘Петров’
>;
Если отказаться от этого решения, то система должна будет переставить маркер 1 на предложение, следующее за пятым предложением программы, но поскольку все предложения программы исчерпаны, а маркер 1 может передвигаться только вперед, вычисление запроса завершается, сообщением “no”, которое означает, что больше решений нет.
5. Рекурсивное программирование на языке Пролог.
5.1 Рекурсивные правила.
Рекурсия в логическом программировании применяется в двух случаях:
если отношение описывается с помощью такого же отношения;
когда сложный объект (структура) сам является частью однотипного, сложного объекта.
Рассмотрим первый случай. Отношения на языке Пролог описываются с помощью правил. Правило, содержащее свой заголовок в качестве предиката в правой части этого правила, называется рекурсивным. Рекурсивное правило реализует повторяющиеся действия. Рекурсивные правила эффективны при программировании циклических задач, при формировании запросов к базам данных и при обработке списков.
Для того, чтобы рекурсивная процедура завершалась, необходимо, чтобы в процедуру было включено условие выхода, гарантирующее окончание работы процедуры. Правило, содержащее условие выхода из рекурсии, является нерекурсивным.
В общем случае рекурсивная процедура имеет следующий вид:
<заголовок рекурсивного правила>:<предикат условия выхода>, <предикаты>.
<заголовок рекурсивного правила >:<предикаты>,
<заголовок рекурсивного правила >,<предикаты>.
<заголовок рекурсивного правила >:<предикаты>,
<заголовок рекурсивного правила >,<предикаты>.
…………………………………………..
<заголовок рекурсивного правила >:<предикаты>,
<заголовок рекурсивного правила >,<предикаты>.
В языке Пролог при согласовании целей правила в процедуре выбираются в порядке их записи в программе. В рекурсивных программах порядок записи правил может оказаться весьма важным. Неудачное расположение правил может привести к бесконечным, рекурсивным вызовам, завершением которых является переполнение стека.
Чтобы обеспечить проверку условий завершения рекурсивных вызовов, рекомендуется нерекурсивное правило с условием выхода записывать перед рекурсивными правилами.
Рассмотрим примеры рекурсивных процедур.
Пример 1. Программа определения суммы ряда натуральных чисел.
sum_series(1,1).
sum_series(N,S):N>0,Next is N-1, sum_series(Next,S1),
S is N+S1.
? sum_series(6,S).
S=21.
YES
Пример 2. Программа генерации ряда натуральных чисел от N до 20.
write_number (20) :write(20).
write_number(N): N<20,write(N),nl,Next is N-1, write_number (Next).
? write_number(15).
15
16
17
18
19
20
YES