Логическое программирование. Основы языка Пролог
Логическое программирование базируется на убеждении, что не человека следует обучать мышлению в терминах операций компьютера, а компьютер должен выполнять инструкции, свойственные человеку. В чистом виде логическое программирование предполагает, что инструкции даже не задаются, а сведения о задаче формулируются в виде логических аксиом. Такое множество аксиом является альтернативой обычной программе. Подобная программа может выполняться при постановке задачи, формализованной в виде логического утверждения, подлежащего доказательству (целевого утверждения).
Идея использования логики исчисления предикатов I порядка в качестве основы языка программирования возникла в 60-е годы, когда создавались многочисленные системы автоматического доказательства теорем и вопросно-ответные системы. В 1965 г. Робинсон предложил принцип резолюции, который в настоящее время лежит в основе большинства систем поиска логического вывода. Метод резолюций был использован в системе GPS (general problem solver). В нашей стране была разработана система ПРИЗ, которая может доказать любую теорему из школьного учебника геометрии.
Язык программирования PROLOG (programming in logic) был разработан и впервые реализован в 1972 г. группой сотрудников Марсельского университета во главе с Колмероэ. Группа занималась проблемой автоматического перевода с одного языка на другой. Основа этого языка — исчисления предикатов I порядка и метод резолюций.
При программировании на Прологе усилия программиста должны быть направлены на описание логической модели фрагмента предметной области решаемой задачи в терминах объектов предметной области, их свойств и отношений между собой, а не деталей программной реализации. Фактически Пролог представляет собой не столько язык для программирования, сколько язык для описания данных и логики их обработки. Программа на Прологе не является таковой в классическом понимании, поскольку не содержит явных управляющих конструкций типа условных операторов, операторов цикла и т. д. Она представляет собой модель фрагмента предметной области, о котором идет речь в задаче. И решение задачи записывается не в терминах компьютера, а в терминах предметной области решаемой задачи, в духе модного сейчас объектно-ориентированного программирования.
Суть Пролога – программирование в терминах целей. Программист описывает условие задачи, пользуясь понятиями объектов различных типов и отношений между ними, и формулирует вопрос. PROLOG-система обеспечивает ответ на вопрос, находя автоматически последовательность вычисления решения, используя встроенную процедуру поиска. До 1981 г. число исследователей, занимавшихся логическим программированием, составляло около сотни во всем мире. В 1981 году PROLOG был выбран в качестве базового языка компьютеров пятого поколения, и количество исследователей логического программирования резко возросло. Одной из наиболее интересных тем исследований является связь логического программирования с параллелизмом.
Где же используется Пролог в настоящее время? Это область автоматического доказательства теорем, построение экспертных систем, машинные игры с эвристиками (например, шахматы), автоматический перевод с одного языка на другой.
В настоящее время создано достаточно много реализаций языка Пролог: Wisdom Prolog, SWI Prolog, Turbo Prolog, Visual Prolog, Arity Prolog и т.д.
В нашем курсе будем использовать SWI Prolog. SWI-Prolog развивается с 1987 года. Его создателем и основным разработчиком является Ян Вьелемакер (Jan Wielemaker). Название SWI происходит от Sociaal-Wetenschappelijke Informatica (гол. социально-научная информатика), первоначального названия группы в Амстердамском университете, где работает Вьелемакер.
SWI-Prolog позволяет разрабатывать приложения любой направленности, включая Web-приложения и параллельные вычисления, но основным направлением использования является разработка экспертных систем, программ обработки естественного языка, обучающих программ, интеллектуальных игр и т.п. Это интерпретатор. Файлы, содержащие программы, написанные на языке SWI Prolog, имеют расширение pl.
SWI-Prolog-Editor является средой программирования для языка SWI-Prolog, включающую редактор программ с подсветкой синтаксиса, интерпретатор и отладчик программ. Основным назначением среды является обучение логическому программированию на языке Prolog.
Сначала устанавливаем SWI Prolog, затем — SWI Prolog Editor. Для запуска редактора SWI Prolog Editor необходимо запустить файл SwiplEdit.exe. Для настройки работы интерпретатора в специальном окне редактора, следует установить путь к интерпретатору, выполнив в редакторе команду Окно-Конфигурация на закладке Программы установить в строке Папка Пролога путь к интерпретатору. Там же, на закладке Настройки необходимо установить поле Codepage равным cp1251. Настройка кодовой страницы необходима для правильного сопоставления строковых констант, набранных русским алфавитом, между текстом программы в среде SWI-Prolog-Editor и языком SWI-Prolog. Для запуска программы из панели редактирования программ ее следует сохранить и нажать функциональную клавишу F9 или соответствующий значок на панели инструментов. В случае успешной загрузки на панели запросов появится:
Загрузить файл можно так же с помощью команды: [].
После любой модификации программу требуется заново загрузить в память. Перезапуск интерпретатора Пролога осуществляется нажатием Ctrl+F9 или соответствующего значка на панели инструментов.
Для выхода из интерпретатора Пролога используется команда: halt.
Как уже отмечалось Пролог использует исчисление предикатов первого порядка. Предикаты определяют отношения между объектами. Рассмотрим дерево родственных отношений:
Рисунок 10 — Дерево родственных отношений
Пример 1: Это дерево можно описать следующей Пролог-программой.
У нас имеется отношение родитель между двумя объектами. Описаны 6 фактов наличия отношений между конкретными объектами. Имена объектов начинаются с маленьких букв (они являются константами). В Прологе принято соглашение, что константы начинаются с маленькой буквы, а переменные – с большой. После набора такой Пролог-программы в редакторе можно загрузить программу в Пролог и задавать вопросы, касающиеся отношения родитель.
Запрос к программе набирается после приглашения ?- и должен заканчиваться точкой. Для выполнения набранного запроса необходимо нажать Enter. Ответ будет выдан под запросом. Запрос может быть набран в несколько строк — для перехода на новую строку используется клавиша Enter. В том случае, если строка будет заканчиваться точкой и будет нажата клавиша Enter SWI-Prolog начнет выполнение запроса. Если возможны несколько вариантов ответа на запрос, то для получения каждого следующего используется клавиша Enter. Варианты ответов SWI-Prolog отделяет друг от друга точкой с запятой. Прекратить выполнение программы (выдачу альтернативных ответов) можно нажав клавишу «a».
Вопросы могут быть простые и сложные (в качестве связки «и» при составлении сложного вопроса используется запятая). Ответы Пролог-системы выводятся сразу после вопроса. Могут быть следующие варианты ответов:
- Yes (да);
- No (соответствует нет или не найдены значения переменных в вопросе);
- Перечисляются возможные значения переменных в вопросе. При этом при нажатии клавиши «a» поиск решений прекращается, а при нажатии клавиши Enter, продолжается поиск новых решений до тех пор, пока не будут найдены все. Альтернативные решения разделяются точкой с запятой. Вывод завершается словом Yes, если не все решения были найдены и No, если других решений не осталось.