Методические рекомендации

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

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

Ты скажи: " Что сделать", а я разработаю "Как это сделать". Другими словами, в отличие от императивных языков программирования, на Прологе интерпретатор сам выбирает порядок исполнения операторов в программе.

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

На Прологе легко определить отношения, подобные отношению родитель(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) осуществляется поиск заключений (заголовков правил), соответствующих цели. Если такое заключение найдено, то в свою очередь должны быть доказаны цели, входящие в данное правило. В Прологе используется обратное рассуждение.

В Прологе поиск осуществляется в глубину. Алгоритм поиска показан на рисунке.

Здесь задействованы три списка. Первый, ПРЕДЛОЖЕНИЯ, содержит предложения. Во втором, ЦЕЛИ, находятся цели, подлежащие удовлетворению. Третий список, РЕШЕНИЯ, включает точки возврата и хранит следы предложений, применявшихся для достижения целей. Это своего рода трасса нахождения решения процедурой поиска.

Процедура ПОИСК просматривает список целей. Если он пуст, то, значит, не осталось ни одной цели, которую нужно доказать, и поиск считается успешным. В противном случае удаляется первая цель из списка ЦЕЛИ, и сканирование продолжается по списку ПРЕДЛОЖЕНИЯ в поисках подходящего предложения. Если таковое найдено, то указатель (в списке ПРЕДЛОЖЕНИЯ) на это предложение вместе с целью добавляется к списку РЕШЕНИЯ. Указатель отмечает, как далеко процедура ПОИСК продвинулась в списке ПРЕДЛОЖЕНИЯ перед нахождением нужного предложения. Затем проверяются цели выбранного предложения. Если хотя бы одна из них недостижима, указатель продвигается до следующего подходящего предложения в списке ПРЕДЛОЖЕНИЯ и его цели помещаются в список ЦЕЛИ. Такая реакция на неудачу называется возвратом. Этот новый указатель замещает прежний в списке РЕШЕНИЯ, и всякий раз, когда совершается возврат, продвигается далее по списку ПРЕДЛОЖЕНИЯ. Если указатель достигает конца списка ПРЕДЛОЖЕНИЯ, то, следовательно, в списке нет предложений, доказывающих искомые цели, и ПОИСК завершается неудачей.