Лабораторная работа №1

Тема работы: Ознакомление с принципами организации и эксплуатации базовой Prolog-системы.

Цель работы: ознакомление с основными возможностями системы SWI-Prolog, правилами эксплуатации интерпретатора и заполнения информационной базы, составления элементарных и составных вопросов со стандартными системными предикатами и c составлением простейших правил для их накопления в Prolog-системе.

1. Ознакомление со средой разработки

   1. Установка среды разработки

Среду разработки SWI-Prolog можно бесплатно загрузить с официального сайта https://www.swi-prolog.org/. Среда разработки состоит из исполнительного модуля (SWI-Prolog - с ним можно работать отдельно через командную строку) и графического интерфейса разработчика (SWI-Prolog Editor), который является надстройкой над исполнительным модулем. Также для корректной работы Help необходимо скачать, разархивировать и поместить все файлы документации в папку “%ПАПКА_ИСПОЛНИТЕЛЬНОГО_МОДУЛЯ%\Manual\” (папку Manual необходимо создать). По умолчанию папка исполнительного модуля “C:\Program files”.

2. Основные возможности среды разработки

После установки окно SWI-Editor выглядит следующим образом (Рис. 1):

Рис. 1 Окно SWI-Editor

По умолчанию в программе выставлен английский язык, но его можно изменить на русский, с помощью Window->Configuration, где выбрать вкладку Option и в поле Language File указать путь к файлу russian.ini (обычно поставляется вместе с Prolog Editor и находится в той же папке, что и english.ini). Далее объяснения по интерфейсу редактора будут изложены с названиями пунктов на русском языке. Почти все пункты контекстного меню по умолчанию для удобства вынесены на верхнюю панель инструментов.

Для создания новой программы необходимо выбрать пункт Файл->Новый. После написания программы в окне редактора ее можно выполнить командой Старт->Запустить, или нажать F9. ВНИМАНИЕ: редактор не поддерживает кириллицу в пути к файлу, поэтому для успешного запуска программ необходимо чтоб в пути к файлу программы не было символов кириллицы.

В редакторе присутствует возможность отладки программ. Для этого необходимо расставить точки останова в программе. Точки останова можно поставить щелкнув два раза на цифре с номером строки, а также нажатием на кнопку «жучка» на левой панели инструментов (не путать с закладками, закладки – прямоугольные, точки останова – в виде жучков. Закладки ставятся просто для отметки строки также двойным щелчком, но слева от цифры с номером строки). Режим отладки включается и отключается пунктом Тест->Отладка (On/Off). Также возможно включение и отключение пошагового выполнения программы пунктом Тест->Трассировка (On/Off). В режиме пошагового выполнения для перемещения между командами используются кнопки «Следующий» (следующий функтор), «Шаг» (выполнение одного шага программы) и «Шаг наверх» (выполнение до выхода на уровень вверх по стеку вызова).

В командной строке отображаются все действия SWI Editor, которые касаются движка SWI Prolog. В действительности SWI Editor просто дает команды на выполнения через командную строку, то есть является надстройкой над консольной реализацией среды разработки SWI Prolog.

2. Теоретические сведения

   1. Общая информация

Язык Пролог, самый известный из представителей семейства языков логического программирования, вырос из работ Алана Колмерауэра (A. Colmerauer) по обработке естественного языка и независимых работ Роберта Ковалького (R. Kowalski) по приложениям логики к программированию. Дэвиду Уоррену (D. Warren) и его коллегам из Эдинбургского университета удалось осуществить достаточно эффективную реализацию Пролога. Имя Уоррена вошло в историю логического программирования. В его честь названа базовая техника реализации Пролога, получившая название абстрактной машины Уоррена. Программа на языке Пролог представляет собой набор фактов и (возможно) правил. Если программа содержит только факты, то ее называют база данных. Если она содержит еще и правила, то часто используют термин база знаний.

SWI-Prolog распространяется под лицензией GPL, что обеспечивает возможность его использования без нарушений чьих-либо коммерческих интересов. Эта версия языка Пролог доступна как пользователям ОС Linux, так и пользователям Windows.

2. Атомы, числа, переменные и составные термы

Программа на языке Пролог обычно описывает некую действительность. Объекты (элементы) описываемого мира представляются с помощью термов. Терм интуитивно означает объект. Существует 4 вида термов: атомы, числа, переменные и составные термы. Атомы и числа иногда группируют вместе и называют простейшими термами.

Атом - это отдельный объект, считающийся элементарным. В Прологе атом представляется последовательностью букв нижнего и верхнего регистра, цифр и символа подчеркивания '_', начинающейся со строчной буквы. Кроме того, любой набор допустимых символов, заключенный в апострофы, также является атомом. Наконец, комбинации специальных символов + - * = < > : & также являются атомами (следует отметить, что набор этих символов может отличаться в различных версиях Пролога). Пример

Представленные далее последовательности являются корректными атомами:

b, abcXYZ, x_123, efg_hij, коля, слесарь,

'Это также атом Пролога',

+, ::, <---->, ***

Числа в Прологе бывают целыми (Integer) и вещественными (Float). Синтаксис целых чисел прост, как это видно из следующих примеров: 1, 1313, 0, -97. Не все целые числа могут быть представлены в машине, их диапазон ограничен интервалом между некоторыми минимальным и максимальным значениями, определенными конкретной реализацией Пролога. SWI-Prolog допускает использование целых чисел в диапазоне от -2147483648 (-2³¹) до 2147483647 (2³¹-1). Синтаксис вещественных чисел также зависит от конкретной реализации. Мы будем придерживаться простых правил, понятных из следующих примеров: 3.14, -0.0035, 100.2. При обычном программировании на Прологе вещественные числа используются редко. Причина этого кроется в том, что Пролог - язык, предназначенный в первую очередь для обработки символьной, а не числовой информации. При символьной обработке часто используются целые числа, нужда же в вещественных числах невелика. Везде, где можно, Пролог старается привести число к целому виду.

Переменными в Прологе являются строки символов, цифр и символа подчеркивания, начинающиеся с заглавной буквы или символа подчеркивания:

X, _4711, X_1_2, Результат, _x23, Объект2, _

Последний пример (единственный символ подчеркивания) является особым случаем - анонимной переменной (переменной без имени). Анонимная переменная применяется, когда ее значение не используется в программе. Возможное неоднократное употребление безымянной переменной в одном выражении применяется для того, чтобы подчеркнуть наличие переменных при отсутствии их специфической значимости.

Составные термы (функции) состоят из имени функции (нечислового атома) и списка аргументов (термов Пролога, то есть атомов, чисел, переменных или других составных термов), заключенных в круглые скобки и разделенных запятыми. Группы составных термов используют для составления фраз Пролога. Нельзя помещать символ пробела между функтором (именем функции) и открывающей круглой скобкой. В других позициях, однако, пробелы могут быть полезны для создания более читаемых программ. Ниже приведены два составных терма:

итого(клиент(X,23,_), 71)

'Что случилось?'(ничего)

При задании имен термов предпочтительнее использовать мнемонические ("говорящие") имена, так как терм a(ж), например, гораздо менее информативен, чем терм aвтор(жюль_верн).

Еще одной важной структурой данных в Прологе является список. Мы познакомимся с ним позднее. Сейчас отметим только один из видов списков - список символов. Такие списки могут быть представлены в виде строк, например, первый аргумент составного терма возраст("Борис",10) - строка. При записи строки заключаются в кавычки.

3. Запросы, факты и правила

Запрос - это последовательность предикатов, разделенных запятыми и завершающаяся точкой. На естественном языке запятая соответствует союзу "и", а на языке математической логики обозначает конъюнкцию. С помощью запросов можно "спрашивать" базу данных о том, какие утверждения являются истинными. Предикат запроса называется целью. Простые вопросы, не содержащие никаких переменных, называют да-нет-вопросами. Они допускают лишь два возможных ответа: "Yes" означает наличие соответствующего факта в базе данных (первый запрос примера, приведенного ниже), "No" - его отсутствие (второй запрос). В случае ответа "Yes" говорят, что запрос завершился успехом, цель достигнута.
Пример

?- больше(слон, лошадь), больше(лошадь,осел).

Yes
?- больше(слон, собака).

No

Использование переменных в запросах позволяет задавать более сложные вопросы. Предположим, например, что мы хотим определить, какие животные больше осла? В следующем запросе переменная X обозначает искомый ответ:

?- больше(X, осел).

X = лошадь

Yes

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

Запросы с переменными могут иметь более одного решения. Первым всегда выводится то из решений, которое находится ближе к началу базы данных. Если нам достаточно только одного ответа, то можно нажать Enter и закончить поиск. В случае, если мы захотим получить очередной ответ, нужно нажать клавишу ; (точка с запятой), и Пролог начнет поиск других вариантов ответа на запрос. Сообщение "No" говорит об отсутствии очередного решения.

Факт - это утверждение о том, что соблюдается некоторое конкретное отношение. Он является безусловно верным. В разговорной речи под фактом понимается нечто вроде "Сегодня солнечно" или "Васе 10 лет". На Прологе это запишется в виде

'Сегодня солнечно'.

'Васе 10 лет'.

Если вы сохраните эти факты в файле и затем загрузите его, то можно задавать вопросы интерпретатору Пролога (напомним, что запрос вводится после приглашения Пролога, которое в большинстве версий имеет вид ?-) , например,

?- 'Сегодня солнечно'.

Yes
?- 'Васе 10 лет'.

Yes
?- 'Сегодня солнечно', 'Васе 10 лет'.

Yes

Запятая между фактами в последнем запросе означает операцию логического и (конъюнкцию).

Такая форма записи соответствует логике высказываний, возможности которой, как уже говорилось, достаточно ограничены. Мы не можем задать, например, вопрос о том, сколько лет Васе. Гораздо удобнее использовать параметризованные факты, работу с которыми поддерживает логика предикатов. На Прологе факт может быть записан в виде предиката, аргументы которого являются символьными или числовыми константами.

Правила.Пролог могут содержать правила, позволяющие получать дополнительные знания о том мире, который описывает программа. Правило задает новый предикат через определенные ранее. Правило состоит из головы (предиката) и тела (последовательности предикатов, разделенных запятыми). Голова и тело разделены знаком :- и, подобно каждой фразе Пролога, правило должно заканчиваться точкой. Запятая в теле правила означает конъюнкцию (&&, логическое и).

Знак :- есть схематическая запись стрелки (<-) и показывает, что из правой части следует левая. Этот знак читается как "если". Интуитивный смысл правила состоит в том, что цель, являющаяся головой, будет истинной, если Пролог сможет показать, что все выражения (подцели) в теле правила являются истинными.

Пример
Правило, определяющее отношение ребенок/2 через отношение отец/2, запишется следующим образом:

ребенок(X, Y) :- отец(Y, X).

Это означает, что если человек Y является для человека X отцом, то X является ребенком Y. Здесь X и Y - переменные. Напомним, что запись ребенок/2 показывает, что предикат ребенок является функцией от двух аргументов.

4. Предикаты

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

имя_предиката(аргументы).

Аргументы перечисляются через запятую и представляют собой какие-то объекты или свойства объектов, а имя предиката обозначает связь или отношение между аргументами. Предикат однозначно определяется парой: имя и количество аргументов. Два предиката с одинаковым именем, но различным количеством аргументов, считаются различными. Количество параметров предиката называется его арностью (arity). При описании предиката арность указывают после его имени, разделяя их символом '/' (слэш).

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

Пример
Факт "Коля работает слесарем" на Прологе запишется следующим образом:

профессия(коля, слесарь).

Здесь предикат профессия/2 имеет два аргумента: первый означает имя человека, а второй - профессию. Факт "Борису 10 лет" можно представить в виде:

возраст("Борис", 10).

Порядок аргументов предиката связан со смыслом факта и поэтому не изменяем. При записи фактов надо помнить, что:

имя факта начинается со строчной буквы;

запись каждого факта заканчивается точкой.

В приведенных выше примерах профессия/2 и возраст/2 - предикаты (составные термы), коля и слесарь - атомы, 10 - число, "Борис" - строка. Подробнее о видах термов Пролога рассказывается в следующем разделе.

База данных на Прологе - это совокупность фактов. В процессе работы в базу данных можно добавлять новые факты, удалять или изменять старые.
Пример
Составим базу данных из следующих фактов: "слон больше, чем лошадь", "лошадь больше, чем осел", "осел больше, чем собака" и "осел больше, чем обезьяна":

больше(слон, лошадь).

больше(лошадь, осел).

больше(осел, собака).

больше(осел, обезьяна).

Мы использовали предикат больше/2, имеющий два параметра.

Сохраним эту базу данных в текстовом файле и затем познакомим Пролог с ней. Теперь можно формулировать запросы к интерпретатору Пролога:

?- больше(слон, лошадь).

Yes
?- больше(лошадь, слон).

No

3. Задание на лабораторную работу

В ходе данной работы необходимо:

1. Построить базу знаний из любой предметной области.

2. Составить набор запросов к базе знаний из п.1.

Примеры предметных областей:

1. Отношения подчиненности в группе проектировщиков.

2. Отношения связей в комплексной программе, разрабатываемой группой программистов.

3. Иерархические отношения в организационной модели вуза.

4. Отношения, необходимые для начисления стипендии.

5. Отношения, проверяемые при выдаче диплома с отличием.

6. Отношения, контролируемые для выдачи направления в аспирантуру.

7. Отношения между курсами по учебным планам.

8. Отношения в организационной иерархии общежития.

4. Пример выполнения

Листинг программы:

% Строим базу знаний

% Факты, представленные в процедуре student

% устанавливают соответствие студентов и их средних баллов

% student(Name, SrBal)

student('Ivanov', 4.5).

student('Pupkin', 3.0).

student('Vetrov', 4.3).

student('Petrov', 3.2).

student('Levchenko', 4.6).

student('Sidorov', 5.0).
% Составляем правило "Стипендия"

% Name - имя студента

% Результат вызова этого правила:

% 1. если параметром передать конкретное имя Prolog-система даст ответ

% true если студент имеет стипендию или fail если не имеет.

% 2. если параметром передать переменную, то будет выведен список студентов,

% которые имеют стипендию

stipendiya(Name) :- student(Name, SrBal), SrBal > 4.

% Определим еще одну пролог-процедуру company

% Эта процедура будет определять минимальный средний балл,

% необходимый студенту для работы в данной компании

% company(Name, MinSrBal)

company('Microsoft', 5.0).

company('Apple', 4.9).

company('IBM', 4.5).

company('IT-west', 4.0).

company('Vasya and Co',3.0).
% Составим правило "может ли студент работать в компании"

% Здесь тоже можно вводить конкретные значения для ответа "да-нет"

% либо переменные для получения списка компаний или студентов.

isAbleToWork(NameStudent, NameCompany) :-

student(NameStudent,SrBalStudent),

company(NameCompany,SrBalCompany),

SrBalStudent>=SrBalCompany.

Запросы:

?- stipendiya('Levchenko').

true.
?- stipendiya('Pupkin').

false.
?- stipendiya(S).

S = 'Ivanov' ;

S = 'Vetrov' ;

S = 'Levchenko' ;

S = 'Sidorov'.

?- company('Microsoft',X).

X = 5.0.
?- isAbleToWork('Levchenko','Microsoft').

false.
?- isAbleToWork('Sidorov','Microsoft').

true.
?- isAbleToWork('Levchenko',X).

X = 'IBM' ;

X = 'IT-west' ;

X = 'Vasya and Co'.
?- isAbleToWork(X,'Microsoft').

X = 'Sidorov'.

?- isAbleToWork(X,'IBM').

X = 'Ivanov' ;

X = 'Levchenko' ;

X = 'Sidorov'.

?- isAbleToWork(X,Y).

X = 'Ivanov',

Y = 'IBM' ;

X = 'Ivanov',

Y = 'IT-west' ;

X = 'Ivanov',

Y = 'Vasya and Co' ;

X = 'Pupkin',

Y = 'Vasya and Co' ;

X = 'Vetrov',

Y = 'IT-west' ;

X = 'Vetrov',

Y = 'Vasya and Co' ;

X = 'Petrov',

Y = 'Vasya and Co' ;

X = 'Levchenko',

Y = 'IBM' ;

X = 'Levchenko',

Y = 'IT-west' ;

X = 'Levchenko',

Y = 'Vasya and Co' ;

X = 'Sidorov',

Y = 'Microsoft' ;

X = 'Sidorov',

Y = 'Apple' ;

X = 'Sidorov',

Y = 'IBM' ;

X = 'Sidorov',

Y = 'IT-west' ;

X = 'Sidorov',

Y = 'Vasya and Co'.