Методические указания для лабораторной работы «Ознакомление с языком Пролог и средой программирования Visual prolog.

Основы языка программирования Пролог.

Язык программирования Пролог (PROgramming LOGic) предполагает получение решения задачи при помощи логического вывода из ранее известных фактов. Программа на языке Пролог не является последовательностью действий – она представляет собой набор фактов и правил, обеспечивающих получение логических заключений из данных фактов. Поэтому Пролог считается декларативным языком программирования.

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

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

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

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

Программист на Прологе описывает объекты и отношения, а также правила, при которых эти отношения являются истинными.

Объекты рассуждения в Прологе называются термами–синтаксическими объектами одной из следующих категорий:

· константы,

· переменные,

· функции (составные термы или структуры), состоящие из имени функции и списка аргументов-термов, имена функций начинаются со строчной буквы.

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

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

Пролог не имеет оператора присваивания.

Использование дизъюнкции и отрицания.

Чистый Пролог разрешает применять в правилах и целях только конъюнкцию, однако, язык, используемый на практике, допускает применение дизъюнкции и отрицания в телах правил и целях. Для достижения цели, содержащей дизъюнкцию, Пролог–система сначала пытается удовлетворить левую часть дизъюнкции, а если это не удается, то переходит к поиску решения для правой части дизъюнкции. Аналогичные действия производятся при выполнении тела правил, содержащих дизъюнкцию. Для обозначения дизъюнкции используется символ « ; ».

В Прологе отрицание имеет имя «not» и для представления отрицания какого-либо предиката P используется запись not(P). Цель not(P) достижима тогда и только тогда, когда не удовлетворяется предикат (цель) P. При этом переменным значения не присваиваются. В самом деле, если достигается P, то не достигается not(P), значит надо стереть все присваивания, приводящие к данному результату. Наоборот, если P не достигается, то переменные не принимают никаких значений.

Управление поиском решения.

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

Пролог обеспечивает два встроенных предиката, которые дают возможность управлять механизмом поиска с возвратом: предикат fail – используется для инициализации поиска с возвратом и предикат отсечения ! – используется для запрета возврата.

Предикат fail всегда имеет ложное значение!

Пример 3: Использование предиката fail. Для примера 1 можно добавить правило для печати всех матерей, которые есть в БД:

печать_матерей:-мать(X,Y), write(X,” есть мать”,Y),nl,fail.

goal

печать_матерей.

В результате будет выдано 3 решения:

X=мария, Y= анна.

X=мария, Y= юлия.

X=анна, Y= петр.

Отсечение так же, как и fail помещается в тело правила. Однако, в отличие от fail предикат отсечения имеет всегда истинное значение.

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

Существует только два случая применения предиката отсечения:

1. Если заранее известно, что определенные посылки никогда не приведут к осмысленным решениям – это так называемое «зеленое отсечение».

2. Если отсечения требует сама логика программы для исключения альтернативных подцелей – это так называемое «красное отсечение».

Процедурность Пролога.

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

Тем не менее, рассмотрим Пролог с точки зрения процедурного программирования:

1. Факты и правила можно рассматривать как определения процедур.

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

3. В правиле может быть выполнено сравнение, как в условных операторах.

4. Отсечение можно считать аналогом go to.

5. Возврат вычисленного значения производится аналогично процедурам. В Прологе это делается путем связывания свободных переменных при сопоставлении цели с фактами и правилами.

Использование списков

Список – это упорядоченный набор объектов одного и того же типа. Элементами списка могут быть целые числа, действительные числа, символы, строки, символические имена и структуры. Порядок расположения элементов в списке играет важную роль: те же самые элементы списка, упорядоченные иным способом, представляют уже совсем другой список.

Совокупность элементов списка заключается в квадратные скобки ([]), элементы друг от друга отделяются запятыми. Список может содержать произвольное число элементов, единственным ограничением является объем оперативной памяти. Количество элементов в списке называется его длиной. Список может содержать один элемент и даже не содержать ни одного элемента. Список, не содержащий элементов, называется пустым или нулевым списком.

Непустой список можно рассматривать как список, состоящий из двух частей: головы – первого элемента списка; и хвоста – остальной части списка. Голова является элементом списка, хвост является списком. Голова списка – это неделимое значение, хвост представляет собой список, составленный из того, что осталось от исходного списка в результате «отделения головы». Этот новый список обычно можно делить и дальше. Если список состоит из одного элемента, то его можно разделить на голову, которой будет этот самый элемент, и хвост, являющийся пустым списком. Пустой список нельзя разделить на голову и хвост.

Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):

[Head | Tail].

Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка (для имен головы и хвоста списка пригодны любые допустимые Прологом имена). Данная операция также присоединяет элемент в начало списка, например, для того , чтобы присоединить X к списку S следует написать [X | S].

Отличительной особенностью описания списков является наличие звездочки (*) после имени домена элементов.

Пример 6: объявление списков, состоящих из элементов стандартных типов доменов или типа структуры.

domains

list1=integer*

list2=char*

list3=string*

list4=real*

list5=symbol*

personal_library = book (title, author, publisher, year)

list6= personal_library*

list7=list1*

list8=list5*

В первых пяти объявлениях списков в качестве элементов используются стандартные домены данных, в шестом типе списка в качестве элемента используется домен структуры personal_library, в седьмом и восьмом типе списка в качестве элемента используется ранее объявленный список.

Пример 7: демонстрация разделения списков на голову и хвост.

Список	Голова	Хвост
[1, 2, 3, 4, 5]	1	[2, 3, 4, 5]
[6.9, 4.3]	6.9	[4.3]
[cat, dog, horse]	Cat	[dog, horse]
[‘S’, ‘K’, ‘Y’]	‘S’	[‘K’, ‘Y’]
[«PIG»]	«PIG»	[]
[]	Не определена	Не определен

Поиск элемента в списке

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

Пример 8: поиск элемента в списке.

domains

list=integer*

predicates

member (integer, list)

clauses

member (Head, [Head |_ ]).

member (Head, [_ | Tail ]):- member (Head, Tail).

goal

member (3, [1, 4, 3, 2]).

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

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

member (Head, [Head |_ ]):- !.

Отсечение отменяет действие механизма возврата, поэтому поиск альтернативных успешных решений реализован не будет.

Объединение двух списков

Слияние двух списков и получение, таким образом, третьего списка принадлежит к числу наиболее полезных при работе со списками операций. Обозначим первый список L1, а второй список - L2. Пусть L1 = [1, 2, 3], а L2 = [4, 5]. Предикат append присоединяет L2 к L1 и создает выходной список L3, в который он должен переслать все элементы L1 и L2. Весь процесс можно представить следующим образом:

1. Список L3 вначале пуст.

2. Элементы списка L1 пересылаются в L3, теперь значением L3 будет [1, 2, 3].

3. Элементы списка L2 пересылаются в L3, в результате чего тот принимает значение [1, 2, 3, 4, 5].

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

Пример 9: объединение двух списков.

domains

list=integer*

predicates

аppend (list, list, list)

clauses

append ( [], L2, L2).

append ([H|T1], L2, [H|T3 ]):- append (T1, L2, T3).

goal

append ( [1, 2, 3], [4, 5], L3).

Основное использование предиката append состоит в объединении двух списков, что делается при помощи задания цели вида append ([1, 2, 3], [4, 5], L3). Поиск ответа на вопрос типа: append (L1, [3, 4, 5], [1, 2, 3, 4, 5]) – сводится к поиску такого списка L1=[1, 2], который при слиянии со списком L2 = [3, 4, 5] даст список L3 = [1, 2, 3, 4, 5]. При обработки цели append (L1, L2, [1, 2, 3, 4, 5]) ищутся такие списки L1 и L2, что их объединение даст список L3 = [1, 2, 3, 4, 5].

Сортировка списков

Сортировка представляет собой переупорядочение элементов списка определенным образом. Назначением сортировки является упрощение доступа к нужным элементам. Для сортировки списков обычно применяются три метода:

· метод перестановки,

· метод вставки,

· метод выборки.

Также можно использовать комбинации указанных методов.

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

Второй из методов, метод вставки, особенно удобен для реализации на Прологе.

Пример 10: сортировка списков методом вставки.

domains

list=integer*

predicates

insert_sort (list, list)

insert (integer, list, list)

asc_order (integer, integer)

clauses

insert_sort ( [], []).

insert_sort ([H1|T1], L2):- insert_sort (T1, T2),

insert(H1, T2, L2).

insert (X, [H1| T1], [H1| T2]) :- asc_order (X, H1), !,

insert (X, T1, T2).

insert (X, L1, [X| L1]).

asc_order (X, Y):- X>Y.

goal

insert_sort ([4, 7, 3, 9], L).

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

После того, как произошло успешное завершение первого правила, Пролог пытается выполнить второй предикат insert, вызов которого содержится в теле второго правила. Переменной H1 сначала присваивается первое взятое из стека значение 9, а предикат принимает вид insert (9, [], [9]).

Так как теперь удовлетворено все второе правило, то происходит возврат на один шаг рекурсии в предикате insert_sort. Из стека извлекается 3 и по третьему правилу вызывается предикат asc_order, то есть происходит попытка удовлетворения пятого правила asc_order (3, 9):- 3>9. Так как данное правило заканчивается неуспешно, то неуспешно заканчивается и третье правило, следовательно, удовлетворяетсячетвертое правило и 3 вставляется в выходной список слева от 9: insert (3, [9], [3, 9]).

Далее происходит возврат к предикату insert_sort, который принимает следующий вид: insert_sort ([3, 9], [3, 9]).

На следующем шаге рекурсиииз стека извлекается 7 и по третьему правилу вызывается предикат asc_order в виде asc_order (7, 3):- 7>3. Так как данное правило заканчивается успешно, то элемент 3 убирается в стек и insert вызвается рекурсивно еще раз, но уже с хвостом списка – [9]: insert (7, [9], _). Так как правило asc_order (7, 9):- 7>9 заканчивается неуспешно, то выполняется четвертое правило, происходит возврат на предыдущие шаги рекурсии сначала insert, затем insert_sort.

В результате 7 помещается в выходной список между элементами 3 и 9: insert (7, [3, 9], [3, 7, 9]).

При возврате еще на один шаг рекурсиииз стека извлекается 4 и по третьему правилу вызывается предикат asc_order в виде asc_order (4, 3):- 4>3. Так как данное правило заканчивается успешно, то элемент 3 убирается в стек и insert вызвается рекурсивно еще раз, но уже с хвостом списка – [7, 9]: insert (4, [7, 9], _). Так как правило asc_order (4, 7):- 4>7 заканчивается неуспешно, то выполняется четвертое правило, происходит возврат на предыдущие шаги рекурсии сначала insert, затем insert_sort.

В результате 4 помещается в выходной список между элементами 3 и 7:

insert (4, [3, 7, 9], [3, 4, 7, 9]).

insert_sort [4, 7, 3, 9], [3, 4, 7, 9]).

Компоновка данных в список

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

Findall (Var_, Predicate_, List_), где Var_ обозначает имя для терма предиката Predicate_, в соответствии с типом которого формируются элементы списка List_.

Пример 11: использование предиката findall.

domains

d=integer

predicates

decimal (d)

write_decimal

clauses

decimal (0)

decimal (1)

decimal (2)

decimal (3)

decimal (4)