Лекции. Логическое программирование

Подождите немного. Документ загружается.

Логическое программирование

Особенности языка Пролог

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

которых действуют объекты и отношения между этими объектами.

Ориентация Пролога – «нетрадиционные» применения вычислительной техники:

понимание естественного языка, базы знаний, экспертные системы и другие задачи.

Его принципиальное отличие от традиционных языков программирования заключается в

подходе к описанию способа решения задачи: программа на Прологе описывает не

процедуру решения задачи, а логическую модель предметной области – некоторые факты

относительно свойств предметной области и отношений между этими свойствами, а также

правила вывода новых свойств и отношений из уже заданных.

Программа на прологе состоит из предложений, которые могут быть фактами, правилами

или вопросами.

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

Терм – элемент Пролог-программы – либо константа, либо переменная, либо структура.

Терм записывается как последовательность литер, которые делятся на 4 категории: {A..Z},

{a..z}, {0..9},{+ - * / ^ < > ~ : . ? @ # $ &}.

Наиболее важная операция над термами – сопоставление. Сопоставление – процесс

проверки сопоставимости термов.

Два терма сопоставимы, если:

- они идентичны,

- переменным в обоих термах можно присвоить в качестве значений объекты таким

образом, что после подстановки они станут идентичными.

Например, date(Day,июнь,1999) и date(Day1,июнь,1999) сопоставимы, поскольку

переменным Day и Day1 можно присвоить одинаковые значения от 1 до 31.

Общие принципы поиска ответов на вопросы системой Пролог

Вопрос в системе Пролог представляет собой последовательность 1 или нескольких целей.

Чтобы ответить на вопрос, Пролог пытается достичь всех целей. Достичь цели – это

значит продемонстрировать, что цель является истиной, при условии, что отношения в

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

фактов и правил, заданных в программе. Если вопрос содержит переменные, то система

Пролог должна найти конкретные объекты, при использовании которых цели

достигаются.

Объекты данных

Объекты данных в Прологе могут быть простыми данными и структурами. Простые

данные могут быть константами и переменными. Константы могут быть атомами,

числами и строками.

Пролог-система распознает тип объекта по его синтаксической форме в тексте

программы.

Атом – комбинация букв, цифр и знака подчеркивания, начинающаяся со строчной

буквы. Примеры: a, "это_атом", "this_is_atom".

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

буквы. Примеры: V, Это_переменная25.

Структурированные объекты

Cтруктурные объекты (или просто структуры) - это объекты, которые состоят из

нескольких компонент. Эти компоненты, в свою очередь, могут быть структурами.

Основной характеристикой структуры является ее размерность (или арность) - число

термов в списке.

Структуры в программе ведут себя как единые объекты. Для того, чтобы объединить

компоненты в структуру, требуется выбрать функтор (имя отношения, образующегося

между элементами структуры) .

Например, дату можно рассматривать как структуру, состоящую из трех компонент: день,

месяц и год: дата( 1, май, 2000 ) .

Структура программы

Программа на Турбо Прологе состоит из следующих семи разделов:

 директивы компилятора - дополнительные инструкции по обработке программы;

 CONSTANTS - раздел описания констант;

 DOMAINS - раздел описания доменов;

 DATABASE - раздел описания предикатов внутренней базы данных;

 PREDICATES - раздел описания предикатов;

 CLAUSES - раздел описания предложений;

 GOAL - раздел описания внутренней цели.

Директива trace применяется при отладке программы для трассировки.

В программе не обязательно должны быть все эти разделы. Так, например, она может

состоять из одного описания цели:

GOAL

write("hello"),readchar(_).

Как правило, программа содержит, по меньшей мере, разделы PREDICATES и CLAUSES.

Если программа запускается в среде разработки Турбо Пролога, то раздел GOAL

необязателен. При написании же программы, не зависящей от среды разработки, в ней

необходимо указать внутреннюю цель.

В программе может быть несколько разделов описаний DOMAINS, PREDICATES,

DATABASE и CLAUSES. Однако разделов GOAL не может быть в программе более

одного.

Порядок разделов может быть произвольным, но при этом константы, домены и

предикаты должны быть определены до их использования. Однако в разделе DOMAINS

можно ссылаться на домены, которые будут объявлены позже.

Арифметические выражения

Пролог не предназначен для программирования задач с большим количеством

арифметических операций. Для этого используются процедурные языки

программирования. Однако в любую Пролог-систему включаются все обычные

арифметические операторы:

+ сложение,

— вычитание,

* умножение,

/ деление,

mod остаток от деления целых чисел,

div целочисленное деление.

Если Х - арифметическое выражение, то список [X ] также является арифметическим вы-

ражением, например [1,2,3]. Первый элемент списка используется как операнд в

выражении: X is ([l,2,3]+5) имеет значение 6.

Сравнение результатов арифметических выражений

Системные предикаты =:=, =\=, >, <, >= и <= определены как инфиксные операторы и

применяются для сравнения результатов двух арифметических выражений.

Для предиката @ доказательство целевого утверждения X@Y заканчивается успехом,

если результаты вычисления арифметических выражений Х и Y находятся в таком

отношении друг к другу, которое задается предикатом @.

Такое целевое утверждение не имеет побочных эффектов и не может быть согласовано

вновь. Если Х или Y - не арифметические выражения, возникает ошибка.

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

Х =:= Y Х равно Y

Х =\= Y Х не равно Y

Х < Y Х меньше Y

Х > Y Х больше Y

Х <= Y Х меньше или равно Y

Х >= Y Х больше или равно Y

Работа с файлами

file = <символическое имя файла1>;...;

<символическое имя файлаN>

Доступ к файлу может осуществляться в двух режимах - бинарном и текстовом.

filemode(SymbolicFileName,Mode) - специальный предикат для определения вида доступа

к файлу (параметр Mode принимает одно из двух значений:

0 - Binary Mode,

1 - Text Mode).

Дальнейшее изложение имеет отношение только к работе с файлами в текстовой режиме.

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

Открыть файл можно для чтения, записи, модификации. Открыть можно практически

неограниченное количество файлов, столько, сколько позволяют установки операционной

системы.

Предикат openread(SimbolicFileName,OSFileName) открывает файл только для чтения.

Если файл с указанным внешним именем не будет обнаружен, предикат терпит неудачу и

выводит соответствующее сообщение об ошибке.

Предикат openwrite(SimbolicFileName,OSFileName) открывает файл только для записи.

Этот предикат создает на диске новый файл. Если файл с указанным внешним именем уже

существует, он будет стерт. Если по какой-то причине файл не может быть создан,

предикат терпит неудачу и выводит соответствующее сообщение об ошибке.

Предикат openappend(SimbolicFileName,OSFileName) открывает файл только для

дозаписи в конец файла. Если файл с указанным именем не будет обнаружен, предикат

выводит соответствующее сообщение об ошибке.

Предикат openmodify(SimbolicFileName,OSFileName) открывает файл для чтения и

записи одновременно. Если файл с указанным именем не будет обнаружен, предикат

выводит соответствующее сообщение об ошибке.

Для того чтобы проверить, существует ли файл с указанным именем в указанном месте,

используется предикат existfile(OSFileName). Этот предикат имеет один аргумент.

Предикат истинен, если файл с именем, указанным в качестве его единственного

параметра, существует, и ложен — в противном случае.

Эти предикаты, связывают символическое имя файла с физическим именем открываемого

файла.

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

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

обратного слеша два ("\\"). Например, чтобы указать путь "C:\Prolog\BIN", нужно записать

строку "C:\\Prolog\\BIN".

Для того чтобы корректно закрыть открытый файл, используется предикат closefile. В

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

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

файлом можно работать только целиком.

Предикат deletefile(OSFileName) удаляет файл, указанный в качестве его единственного

параметра. Если по какой-то причине удалить файл не получается, этот предикат выдает

сообщение об ошибке.

Предикат renamefile(OldOSFileName, NewOSFileName) изменяет имя файла, указанного

в качестве его первого параметра, на имя, указанное в качестве его второго параметра.

Если не существует файла, чье имя указано в первом параметре, или существует файл, чье

имя указано во втором параметре, предикат выдаст сообщение об ошибке.

Предикат eof(SymbolicFileName) (сокращение от End Of File — "конец файла") успешен,

если достигнут конец файла, в противном случае он неуспешен. В качестве его

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

используется при организации рекурсивного считывания всех компонентов файла. Если

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

ошибке.

Предикат file_str(SymbolicFileName,String) целиком читает символы файла в строку или,

наоборот, записывает содержимое строки в файл, в зависимости от того, свободен ли

второй параметр этого предиката. Первым входным параметром этого предиката является

символическое имя файла, а вторым — строка, в которую считывается содержимое файла

или из которой записывается информация в него.

Предикат flush(SimbolicFileName) используется для принудительной записи в файл

содержимого внутреннего буфера, выделенного для файла, указанного в его единственном

параметре. Обычно он используется при работе с принтером.

Списки

Список задается перечислением элементов списка через запятую в квадратных скобках.

Элементы списка могут быть любыми, в том числе и составными объектами. В частности,

элементы списка сами могут быть списками.

В разделе описания доменов списки описываются следующим образом:

DOMAINS

<имя спискового домена>=<имя домена элементов списка>*

Звездочка после имени домена указывает на то, что мы описываем список, состоящий из

объектов соответствующего типа.

[monday, tuesday, wednesday, thursday, friday, saturday, sunday] — список,

элементами которого являются английские названия дней недели;

["понедельник", "вторник", "среда", "четверг", "пятница", "суббота",

"воскресенье"] — список, элементами которого являются русские названия дней недели;

[1, 2, 3, 4, 5, 6, 7] — список, элементами которого являются номера дней недели;

['п', 'в', 'с', 'ч', 'п', 'с', 'в'] — список, элементами которого являются

первые символы русских названий дней недели;

[] — пустой список, т.е. список, не содержащий элементов (в языке функционального

программирования Лисп он обозначается nil).

Рекурсивное определение списка.

Список — это структура данных, определяемая следующим образом:

1. пустой список ([ ]) является списком;

2. структура вида [H|T] является списком, если H — первый элемент списка (или

несколько первых элементов списка, перечисленных через запятую), а T — список,

состоящий из оставшихся элементов исходного списка.

Данное определение позволяет организовывать рекурсивную обработку списков, разделяя

непустой список на голову и хвост.

Работа со списками.

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

length([], 0). /* в пустом списке элементов нет */

length([_|T], L) :–

length(T, L_T), /* L_T — количество

элементов в хвосте */

L = L_T + 1. /* L — количество элементов

исходного списка */

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

— искомое значение, второй — список, в котором производится поиск).

member(X,[X|_]). /* X — первый элемент списка */

member(X,[_|T]) :–

member(X,T). /* X принадлежит хвосту T*/

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

будут представлять соединяемые списки, а третий — результат соединения.

conc([ ], L, L). /* при присоединении пустого списка

к списку L получим список L */

conc([H|T], L, [H|T1]) :–

conc(T,L,T1). /* соединяем хвост и список L, получаем

хвост результата */

Этот предикат можно применять для решения нескольких задач:

1. для соединения списков:

?-conc([1, 2, 3], [4, 5], X)  X= [1, 2, 3, 4, 5]

2. для того, чтобы проверить, получится ли при объединении двух списков третий:

?-conc([1, 2, 3], [4, 5], [1, 2, 5])  No

3. для разбиения списка на подсписки:

?-conc([1, 2], Y, [1, 2, 3])  Y=[3]

?-conc(X, [3], [1, 2, 3])  X=[1, 2]

4. можно использовать этот предикат для поиска элементов, находящихся левее и

правее заданного элемента:

?-conc(L, [2|R], [1, 2, 3, 2, 4])  L=[1], R=[3, 2, 4]

L=[1, 2, 3], R=[4]

5. на основе данного предиката conc можно создать предикат, находящий последний

элемент списка:

last(L,X):–

conc(_,[X],L).

Или задать его непосредственно:

last2([X],X). /* последний элемент одноэлементного

списка — этот элемент */

last2([_|L],X):–

last2(L,X). /* последний элемент списка совпадает

с последним элементом хвоста */

Предикат, позволяющий записать элементы списка в обратном порядке (первый

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

элементов первого аргумента в обратном порядке).

reverse([ ],[ ]). /* обращение пустого списка дает пустой

список*/

reverse([X|T],Z):–

reverse(T,S), conc(S,[X],Z).

/* обращаем хвост и приписываем к нему

справа первый элемент исходного

списка*/

Другой способ реверса:

rev([H|T],L1,L2):–

rev(T,[H|L1],L2). /* голову первого

аргумента дописываем ко

второму аргументу*/

rev([ ],L,L). /* если исходный список закончился,

то второй аргумент — передаем в третий

аргумент в качестве результата*/

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

исходный список, второй аргумент — номер элемента и третий — элемент списка,

указанного в качестве первого аргумента предиката, имеющий номер, указанный в

качестве второго аргумента).

n_element([X|_],1,X).

n_element([_|L],N,Y):–

N1=N–1,

n_element(L,N1,Y).

Предикат, проверяющий является ли элемент списком.

is_list([_|_]).

Предикат, преобразующий список в одноуровневый(первый аргумент - исходный

список, второй - результат).

simple_list([],[]).

simple_list([H|List],List1):-

is_list(H), /*если голова списка – список,*/

simple_list(H,List1). /*то рекурсивно вызываем

предикат simple_list и передаем ему

ее в качестве входного параметра*/

simple_list([H|List],[H|List1]):-

not is_list(H), /*если голова списка – простой элемент,*/

simple_list(List,List1). /*то рекурсивно вызываем

предикат simple_list и записываем ее

в список - результат*/

Предикат, удаляющий все вхождения заданного значения из списка (первый параметр

соответствует удаляемому списку, второй — исходному значению, а третий — результату

удаления из первого параметра всех вхождений второго параметра).

delete_all(_,[],[]).

delete_all(X,[X|L],L1):–

delete_all (X,L,L1).

delete_all (X,[Y|L],[Y|L1]):–

X<>Y,

delete_all (X,L,L1).

Если нужно удалить не все вхождения определенного значения в список, а только

первое, то :

delete_one(_,[],[]).

delete_one(X,[X|L],L):–!.

delete_one(X,[Y|L],[Y|L1]):–

delete_one(X,L,L1).

Предикат, добавляющий элемент в список (первый параметр – вставляемый элемент,

второй — исходный список, а третий — результат).

add(X, L, [X|L]).

Но если возникает необходимость добавлять только, если элемент отсутствует, то

можно использовать правило:

add(X, L, L):-member(X, L), !. add(X, L, [X|L]).

Проверка типов термов

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

atom(X) -истина, если X-атом.

integer(X) - истина, X-целое.

float(X) – истина, если Х – действительное число.

compound(X) – истина, если Х – составной терм.

atomic(X) - истина, если X-целое или атом.

var(X) - истина, если X-не конкретизированная переменная.

nonvar(X) - истина, если X- терм, отличный от переменной, или уже конкретизированная

переменная.

ground(Х)- истина, если Х не содержит свободных переменных.

number(Х) - истина, если Х – число.

string(Х) – истина, если Х – строка.

Операции с базами данных

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

некоторого множества отношений.

Описание отношений присутствует либо в явном виде (факты), либо в неявном виде

(правила).

Встроенные предикаты :

assert(d) всегда успешен и добавляет факт d к базе данных;

retract(d) удаляет факт, сопоставимый с d;

asserta(d) - обеспечивает запись в начало базы данных нового факта для заданного

отношения;

assertz(d) - обеспечивает запись в конец базы данных нового факта для заданного

отношения.

Объявление динамической базы данных осуществляется с помощью ключевого слова

database.