- •Введение
- •1. Организация вычислительного процесса
- •2. Основные элементы языка
- •2.1. Имена
- •2.2. Типы данных
- •2.3. Константы и переменные
- •2.4. Программные секции Пролога
- •2.4.1. Секция Domains
- •2.4.2. Секция Ppredicates
- •2.4.3. Секция Database
- •2.4.4. Секция Clauses
- •2.4.5. Секция Goal
- •3. Примеры программ
- •3.1. Программы с фактами и простыми правилами
- •3.2. Рекурсии
- •3.3. Программирование циклов
- •3.4. Работа со списками
- •3.5. Нахождение пути на графе
- •3.6. Использование структур
- •Vife(X):–family(_,X,_). % X – жена
- •3.7. Динамическая база данных
- •It_is("хищник"),
- •Xpositive(X, y), !. % в базе данных
- •3.8. Обработка текстов
- •Verb( string ) % Глагол
- •4. Стандартные предикаты
- •4.1. Ввод/вывод
- •4.2. Управление экраном и оконная система
- •4.3. Обработка строк
- •4.4. Преобразование типов
- •4.5. Работа с базой данных
- •4.6. Управляющие предикаты
- •4.7. Прочие стандартные предикаты
- •4.8. Арифметические и логические предикаты
- •5. Использование языка Пролог для построения экспертных систем
- •5.1. Оболочка экспертной системыGeni
- •5.2. Оболочка экспертной системы pexpert
- •5.2.1. Синтаксис правил
- •5.2.2. Функции
- •5.2.3. Взгляд на работу программы
- •5.2.4. Команды верхнего уровня
- •5.2.5. Команды оценки правил
- •5.2.6. Команды, действующие во время ввода данных
- •Рекомендуемая литература
- •Приложение. Варианты лабораторных работ Лабораторная работа 1. Работа с простой базой данных
- •Лабораторная работа 2. Программа “Родственные отношения”
- •Лабораторная работа 3. Построение простой вопросно-ответной системы
- •Лабораторная работа 4. Работа со списками
- •Лабораторная работа 5. Нахождение пути на графе
- •Лабораторная работа 6. Работа с базой данных с использованием структур
- •Лабораторная работа 7. Построение экспертной системы
- •Лабораторная работа 8. Построение синтаксического анализатора
3.2. Рекурсии
В Прологе заложено мощное средство, позволяющее определять некоторые отношения, используя эти же отношения, и называемое рекурсией. Подробнее, правило является рекурсивным, если оно вызывает само себя в виде подцели, содержащейся в теле по крайней мере одного из ее утверждений.
6. Примером рекурсивных вычислений является известный алгоритм вычисления факториала. Hа Прологе эта программа может иметь такой вид:
Domains
N, F=real
Predicates
factorial(N,F)
Clauses
factorial(1,1). % база рекурсии, ограничение вычислений
factorial(N,R):– N>0, N1=N-1,
factorial(N1,R1), R=R1*N.
Goal
factorial(8,F),write(F).
При каждом вызове дизъюнкта factorialгенерируются новые переменные, которые действуют всегда только на своем уровне вложенности, пока не встретится условие прекращения вычислений. Только после этого на обратном пути прохождения рекурсии определяются результаты, которые передаются вверх.
Любое рекурсивное определение содержит по крайней мере одно нерекурсивное правило и одно или несколько правил с рекурсией. В большинстве случаев имеется по одному правилу каждого типа. Считается, что используется хвостовая рекурсия, если последнее условие в последнем правиле является рекурсивным. Такая рекурсия имеет преимущество перед нехвостовой рекурсией, так как позволяет ограничить рост стека и строго контролировать процесс возврата. Это происходит благодаря очистке стека после успешного сопоставления условия, содержащего рекурсию.
3.3. Программирование циклов
На языке Пролог могут быть реализованы различные алгоритмические методы, позволяющие добиться того же эффекта, что и итеративные циклы в процедурных языках. Выбор алгоритма зависит от того, как представлены данные, которые требуется обрабатывать. Если данные представлены в виде списка (или рекурсивной структуры иного вида), то оптимальным является применение рекурсивного алгоритма. Если же имеется информация в виде базы данных, содержащей факты, то потребуется использовать алгоритм поиска с возвратом (бэктрекинг). И тот, и другой тип цикла можно реализовать с заданным числом повторений или потенциально бесконечным.
7. Рекурсивный цикл со счетчиком. Цикл выполнится 10 раз.
for(10).
for(N):– N<10,
prosess,
N1=N+1,
for(N1).
Goal for(0).
8. Бесконечный рекурсивный цикл. Выполняется ввод и печать символов. Процесс повторяется до нажатия клавиши ENTER, имеющей кодовое число 13.
typewr('\13').
typewr(Char):–write(Char),
readchar(C),
typewr(C).
Goal readchar(Char), typewr(Char).
9. Использование бэктрекинга для перебора всех вариантов. Пусть есть фрагмент программы
fact(f1).
fact(f2).
fact(f3).
print_fact:– fact(X), write(X), fail.
print_fact.
Наличие второго клоза предиката print_factпозволяет всей программе завершиться успешно после печати всех фактов.
10. Большую группу примеров циклов можно продемонстрировать с использованием предиката repeat. Этот предикат программируется следующим образом:
repeat.
repeat:–repeat.
Repeat– это цель, которая всегда успешна. Она недетерминирована, это означает: что всякий раз, когда до нее доходит перебор, порождается новая ветвь вычислений.
Пример цикла с сочетанием repeatиfail.
run:– repeat,
readln(X),
prosess(X,Y),
write(Y),
fail.
Предикат failзаставляет систему осуществлять возврат кrepeatиprosessв случае успешного завершения.
Можно также использовать сочетание repeatи стандартного предикатаkeypressed(вместоrepeat–fail) или сочетаниеnot(keypressed) и рекурсии:
run:– repeat, prosess,
keypråssed.
run:– not(keypressed),
prosess, run.
С использованием предиката repeatможно также организовать любое подходящее условие окончания работы цикла:
run:– repeat,
prosess,
write("Будет еще ввод?(y/n)" ),
readchar(Ans), Ans = 'n'.