Язык программирования Пролог базируется на ограниченном наборе механизмов, включающих в себя сопоставление образцов, древовидное представление структур данных и автоматический возврат. Этот небольшой набор образует удивительно мощный и гибкий программный аппарат.
Программирование на Прологе – программирование в терминах логики. Программы на Прологе записываются в декларативном стиле, это означает что выполнение программ Пролог - машиной происходит по принципу:
Ты скажи: " Что сделать", а я разработаю "Как это сделать". Другими словами, в отличие от императивных языков программирования, на Прологе интерпретатор сам выбирает порядок исполнения операторов в программе.
Особенно хорошо Пролог приспособлен для решения задач, в которых фигурируют объекты и отношения между ними. Примером такой задачи может служить задача, описывающая родственные отношения в семье.
На Прологе легко определить отношения, подобные отношению родитель(X,Y), что означает ИСТИНА если X является родителем Y, и ЛОЖЬ в противном случае.
|
|
Программа на языке Пролог состоит из предложений. Каждое предложение заканчивается точкой.
Аргументами отношений могут быть атомы (константные объекты) или переменные. В тексте программы названия переменных начинаются с большой буквы, а названия констант – с маленькой.
На Прологе отношения могут быть записаны в виде фактов и правил. В виде фактов записываются простейшие отношения.
Например:
human(oleg).
fruit(orange).
Правила нужны для получения новых отношений из уже известных.
Например:
ather(X,Y):-parent(X,Y),man(X).
Что означает: X является отцом Y, ЕСЛИ X родитель Y И X является
мужчиной.
Вопрос к системе формируется в виде цели, которая может содержать переменные. В этом случае Пролог-машина проверит все возможно допустимые состояния переменных и найдет те из них, при которых цель достижима.
Повторяющееся применение фактов к правилам, приводящее к новым фактам, называется прямым рассуждением (forward chaining). При обратном рассуждении (backward chaining) осуществляется поиск заключений (заголовков правил), соответствующих цели. Если такое заключение найдено, то в свою очередь должны быть доказаны цели, входящие в данное правило. В Прологе используется обратное рассуждение.
В Прологе поиск осуществляется в глубину. Алгоритм поиска показан на рисунке.
Здесь задействованы три списка. Первый, ПРЕДЛОЖЕНИЯ, содержит предложения. Во втором, ЦЕЛИ, находятся цели, подлежащие удовлетворению. Третий список, РЕШЕНИЯ, включает точки возврата и хранит следы предложений, применявшихся для достижения целей. Это своего рода трасса нахождения решения процедурой поиска.
|
|
Процедура ПОИСК просматривает список целей. Если он пуст, то, значит, не осталось ни одной цели, которую нужно доказать, и поиск считается успешным. В противном случае удаляется первая цель из списка ЦЕЛИ, и сканирование продолжается по списку ПРЕДЛОЖЕНИЯ в поисках подходящего предложения. Если таковое найдено, то указатель (в списке ПРЕДЛОЖЕНИЯ) на это предложение вместе с целью добавляется к списку РЕШЕНИЯ. Указатель отмечает, как далеко процедура ПОИСК продвинулась в списке ПРЕДЛОЖЕНИЯ перед нахождением нужного предложения. Затем проверяются цели выбранного предложения. Если хотя бы одна из них недостижима, указатель продвигается до следующего подходящего предложения в списке ПРЕДЛОЖЕНИЯ и его цели помещаются в список ЦЕЛИ. Такая реакция на неудачу называется возвратом. Этот новый указатель замещает прежний в списке РЕШЕНИЯ, и всякий раз, когда совершается возврат, продвигается далее по списку ПРЕДЛОЖЕНИЯ. Если указатель достигает конца списка ПРЕДЛОЖЕНИЯ, то, следовательно, в списке нет предложений, доказывающих искомые цели, и ПОИСК завершается неудачей.
Контрольный пример
Простейшая программа на языке Пролог.
man(nikolay).
man(stepan).
woman(lida).
parent(lida, stepan).
parent(nikolay, stepan).
mother(X,Y):-parent(X,Y),woman(X).
Задание к работе
1. Изобразить граф, иллюстрирующий описываемые родственные отношения.
2. Составить программу, которая описывает родственные отношения.
В качестве фактов описать унарные отношения: мужчина, женщина; и бинарные: состоят_в_браке, родитель_ребенок.
Записать правила, которые определяют следующие отношения: муж, жена, родитель, ребенок, сын, дочь, брат, сестра, дядя, тетя, бабушка, дедушка.
3. Подобрать тестовые данные, проверяющие все полученные отношения. Тестовые данные должны содержать операции «И», «ИЛИ», «НЕ».
4. Оформить отчет о проделанной работе.
Содержание отчета
1. Описание родственных отношений, представленных в лабораторной работе, в виде графа.
2. Исходные тексты программ на языке Пролог.
3. Наборы тестовых данных и результаты работы программ.
4. Перечень и анализ ошибок, допущенных при решении задачи.
5. Выводы по работе.