Ирина Эланс

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

Программирование на языке Prolog

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное учреждение

высшего профессионального образования

«Комсомольский-на-Амуре государственный

технический университет»

Факультет компьютерных технологий

Кафедра информационных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по дисциплине «Интеллектуальные информационные системы»

Программирование на языке Prolog

Студент группы 9-ПИ ______________ К.А. Страхова

подпись, дата

Руководитель проекта ______________ А.А. Сиротин

подпись, дата

Нормоконтролёр ______________ А.В. Еськова

подпись, дата

2013

Содержание

1 Структурное, функциональное и логическое программирование. 3

2 Основные конструкции языка 6

3 Ход работы 16

3.1Построение треугольника Паскаля 16

3.2 Работа со списками 24

3.3 Работа с внешними базами данных в Prolog 29

3.4 Задачи использующие структуру графа 34

3.5 Построение экспертной системы 39

3.6 Реализация головоломки о Ханоской башне 44

Список использованных источников 53

1 Структурное, функциональное и логическое программирование.

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

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

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

Недостатки алгоритмических языков:

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

Функциональное и логическое программирование похожи по способу реализации.

Функциональное программирование. Любую сложную программу можно рассматривать как функцию. Основной принцип - суперпозиция функций.

Пример 1

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

Н0(0;0) - начальное значение

НК(5;4) - конечное значение.

length (5,4)=sqrt(K,N), где K=mul(X,X), N=mul(Y,Y) - примитивные функции.

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

Достоинства:

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

Недостатки:

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

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

Создание логического программирования можно приписать Ковальскому и Колмэроэ.

Ковальский разработал процедурную интерпретацию хорновских дизъюнктов и показал, что аксиома A if B1and B2 and B3...and BN может рассматриваться и выполняться в качестве процедуры рекурсивного языка программирования.

В этом случае, А - заголовок процедуры, а BI - "тело".

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

В основе логического программирования лежит метод резолюций.

2 Основные конструкции языка

Существует единственная структура данных - логический терм. Термы могут быть простыми и составными.

Простой терм может быть константой или переменной. Константа - это атом или число. Атом начинается со строчной буквы, знака или резервного имени. Константы в Прологе могут быть шести типов: integer, real, char, symbol, string, file.

Рисунок 2 – Конструкция языка

Пример 2

Константы:

0, -l, 123.4, 0.23E-5, а, +, :, 'Фред Блогс'

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

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

анонимная переменная обозначается символом '_' и показывает, что конкретное значение данной переменной не представляет интереса;
явные переменные обозначаются любой последовательностью символов, начиная с заглавной буквы латинского алфавита (X, D1, Wer и т.д.).

Область действия переменных.

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

Единственным исключением из правила определения области действия переменных является анонимная переменная, например, “_” в цели любит(Х,_). Каждая анонимная переменная есть отдельная сущность. Она применяется тогда, когда конкретное значение переменной несущественно для данного утверждения. Таким образом, каждая анонимная переменная четко отличается от всех других анонимных переменных в утверждении.

Переменные, отличные от анонимных, называются именованными или связными, а не конкретизированные (переменные, которым не было присвоено значение) называются свободными.

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

Функтор задается именем (суть атом) и арностью (число аргументов).

Пример 3

Составные термы:

dog(“рекс”), parent(Х,У)./ рекс – собака, родителем Y является X

В данном примере структура dog имеет арность 1 (записывается как dog /1), а структура parent - арность 2 (parent /2). Заметим, что атом можно рассматривать как структуру арности 0. Для некоторых типов структур допустимо использование альтернативных форм синтаксиса. Это синтаксис операторов для структур арности 1 и 2, синтаксис списков для структур в форме списков и синтаксис строк для структур, являющихся списками кодов символов.

Утверждения

Программа на Прологе есть совокупность утверждений. Утверждения состоят из целей и хранятся в базе данных Пролога. Таким образом, база данных Пролога может рассматриваться как программа на Прологе. В конце утверждения ставится точка “.”. Иногда утверждение называется предложением. Утверждения бывают трех видов: факты, правила, вопросы.

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

Простые факты служат для констатации конкретных свойств и отношений.

Пример 4

like(jhon, apple) - Джон любит яблоки.

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

Пример 5

like(X, apple) - все любят яблоки.

Конечное множество фактов образует программу. Это простейший вид программы. Множество фактов, с другой стороны, составляет описание ситуации.

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

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

Пример 6

dog(X).

parent (Х,Y), dog (Y).

Поиск ответа на вопрос состоит в том, чтобы определить, является ли вопрос логическим следствием программы. Логические следствия выводятся путем применения правил. Простейшее правило вывода – совпадение: из Р выводимо Р.

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

Формальное определение синтаксиса Пролога, используя форму записи Бэкуса-Наура, иногда называемую бэкусовской нормальной формой (БНФ), выглядит так:

запрос ::- голова утверждения

правило ::– голова утверждения :- хвост утверждения

факт ::- голова утверждения

голова утверждения ::-атом | структура

хвост утверждения ::- атом структура,

термы ::-терм [,термы]

терм ::- число | переменная | атом | структура

структура ::-атом (термы)

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

Вопросы могут быть простыми, конъюктивными и экзистенциальными.

Простой вопрос состоит из одной цели. Процедура поиска ответа на простой вопрос осуществляется непосредственно. В программе ищется факт, предполагаемый в вопросе. Если факт, тождественный вопросу, найден, то ответ – да. Ответ нет дается в том случае, когда факт, тождественный вопросу, не найден, поскольку данный факт не является логическим следствием программы. Такой ответ не подвергает сомнению истинность вопроса, он просто показывает, что не удалось доказать истинность вопроса с помощью программы.

Пример 7

В Пролог-программе хранятся факты:

dog(jek). // jek - собака

dog(rex). // rex - собака

dog(holly). // holly – собака

Программе задается вопрос:

dog(jek).

Ответ утвердительный – yes, так как в программе существует тождественный факт.

При вопросе:

dog(mikky).

Ответ отрицательный – no, поскольку в программе не существует тождественного факта, хотя где-то и может существовать собака с такой кличкой.

Экзистенциальный вопрос в общем случае содержит переменные и может иметь несколько решений.

Пример 8

Программе, описанной в Примере 7, задается вопрос:

dog(X).

В качестве ответа будет получен результат:

X =jek

X= rex

X= holly

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

Конъюнктивный вопрос – это конъюнкция целей, поставленная в виде вопроса. Подцели отделяются друг от друга запятой.

Пример 9

dog(jek),dog(rex),dog(X).

Простой вопрос является частным случаем конъюнктивных вопросов с единственной целью. В простейшем конъюнктивном вопросе все подцели простые.

Правило - это утверждение вида A¬B₁, B₂,…,B_n, где n³0. A называется заголовком правила, а B₁, B₂,…,B_n - телом правила. Как A, так и B_i должны быть целями. Правило состоит из одной головной цели и одной или более хвостовых целей, которые истинны при некоторых условиях.

Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей. Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели.

Пример10

dog(X) :- parent(X,Y),dog(Y). // X является собакой, если у него есть родитель Y и Y - собака

homo(Х) :-men(Х). // X – человек, если X – мужчина

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

Так, правило:

dog(X) :- parent(X,Y),dog(Y). может быть задано как

:- dog(X)’,’ parent(X,Y)’,’dog(Y).

Запись верна, поскольку :- является оператором “при условии, что”, а ',' - это оператор конъюнкции. Однако удобнее записывать это как:

dog(X) :- parent(X,Y),dog(Y).

и читать следующим образом: “ Х - собака при условии, что родителем Х является Y и Y - собака”.

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

Пример 11

Родственное отношение «внук» можно описать так:

vnuk(X,Y):-fath(Y,Z),fath(Z,X). // X- внук Y, если Y – отец Z и Z – отец X

vnuk(X,Y):-moth(Y,Z),fath(Z,X). //X- внук Y, если Y –мать Z и Z – отец X

vnuk(X,Y):-fath(Y,Z),moth(Z,X). //X- внук Y, если Y –отец Z и Z – мать X

vnuk(X,Y):-moth(Y,Z),moth(Z,X). //X- внук Y, если –мать Z и Z –мать X

Однако, то же самое отношение можно записать компактнее, определив «промежуточное» отношение parent (родитель):

parent(X,Y):- fath(X,Y). //X – родительY, если X – отец Y

parent(X,Y):-moth(X,Y). //X – родительY, если X – мать Y

Тогда родственное отношение «внук» можно определить так:

vnuk(X,Y):- parent(Y,Z), parent(Z,X).

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

Простой абстрактный интерпретатор.

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

Абстрактный интерпретатор выполняет вычисления с ответами «да/нет». Он получает программу P и основной вопрос Q и дает ответ да, если Q выводимо из P, и ответ нет, в противном случае. Кроме того, если цель не выводима, интерпретатор может вообще не завершить работу. В этом случае не выдается никакого ответа. Работу интерпретатора схематично можно описать следующим образом:

Вход: Основной вопрос Q и программа P

Результат: да, если найден вывод Q из программы P,

нет – в противном случае

Алгоритм: Положить резольвенту равной Q.

Пока резольвента A1,A2,…,An не пуста –

начало цикла

Выбрать цель Ai, 1 £ i £ n, и такой основной пример

предложения A¬B1,B2,…,Bk, где k³0 в Р, что A=Ai

(если такого предложения нет - выйти из цикла);

положить резольвенту равной

A1,…,Ai-1, B1,…,Bk ,Ai+1,…,An

конец цикла

если резольвента пуста, то результат – да, иначе результат – нет.

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

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

Пример 12

Программа, определяющая родственное отношение «сын»:

fath(abram,isak).

fath(aran,lot).

men(abram).

men(lot).

men(isak).

sun(X,Y):-fath(Y,X),men(X).

Вопрос: sun(lot, aran)

Протокол интерпретатора:

Вход: sun(lot, aran) и программа

Резольвента не пуста

Выбор: sun(lot, aran) (единственный выбор)

Выбор: sun(lot, aran):- fath(aran,lot), men(lot). Новая резольвента: fath(aran,lot), men(lot).

Резольвента не пуста.

Выбор: fath(aran,lot) // первая подцель в новой резольвенте

Выбор: fath(aran,lot). //из двух фактов fath(abram,isak), fath(aran,lot) подходит последний

Резольвента не пуста.

Выбор: men(lot) // вторая подцель в новой резольвенте

Выбор: men(lot). //из трех фактов men(abram), men(isak),men(lot) подходит последний

Новая резольвента пуста.

Результат: да

3 Ход работы

3.1Построение треугольника Паскаля

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

Задание: Написать программу, которая выводит треугольник Паскаля до введенного пользователем уровня. В программе должна быть предусмотрена элементарная справка и защита от ошибок.

Числа, стоящие в одной строке, являются биномиальными коэффициентами соответствующей степени, которые можно найти следующим образом:

Ход выполнения:

Был создан проект под названием «ТреугольникПаскаля» (рисунок 3), состоящий из основного окна Task Window и трех диалоговых окон: AboutDialog, Help, MyDialog. В окне MyDialog пользователь будет вводить требуемый уровень треугольника и нажимать на кнопку OK для отображения соответствующего треугольника на экран. Для создания диалоговых окон необходимо нажать на кнопку Dialog в окне проекта, создать нужное диалоговое окно и разместить нужные элементы управления на нем (пример окна MyDialog на рисунок 4.

Двойным щелчком мыши на кнопке OK открывается окно атрибутов данной кнопки (рисунок 5), в котором можно установить соответствующие атрибуты, включая и идентификатор данного элемента (в нашем случае idc_ok). Именно для данного идентификатора будет прописан основной код программы. Идентификатор для поля ввода текста зададим idc_mydialog_1. Для перехода к написанию кода для данного объекта в окне проекта (рисунок 6) необходимо нажать кнопку Dialog, выбрать нужное диалоговое окно и нажать на кнопку CodeExpert в результе чего будет открыто окно Dialog and Window Expert (рисунок 7). Для перехода к написанию кода элемента управления необходимо в секции Dialog or Window Selection выбрать соответствующее окно (в нашем случае выбрано диалоговое окно MyDialog). В секции Place Source Code in… выбрать модуль проекта (в нашем случае выбран проект ТреугольникПаскаля.pro). В списке типа событий Event Type выбрать нужный тип (в нашем случае выбран Control – элементы управления), в списке Event or Item (событие или элемент) выбрать нужную позицию (в нашем случае выбран идентификатор кнопки OK – idc_ok). После указанных действий необходимо нажать на кнопку Edit Clause – редактировать правила (рисунок 7). Если правила для события или элемента еще не существовали, то кнопка Edit Clause первоначально называется Add Clause – добавить правила.

Рисунок 3 - Окно проекта

Рисунок 4 - Окно MyDialog

Рисунок 5 - Атрибуты кнопки Ок

Рисунок. 7 - Dialog and Window Expert

После нажатия на кнопку Edit Clause мы переходим к редактору кода соответствующего элемента (рисунок 8). Именно здесь прописывается программный код Prolog-приложения. Основной код нашей программы следующий (просим обратить внимание читателей, что представленный код не является панацеей и является не самым оптимальным с точки зрения затрат вычислительных ресурсов, код представлен в книге лишь в качестве примера prolog-программы, в которой присутствует все основные секции):

Рисунок 8 - Редактор кода

domains

r=real % задаем r типа real (действительные числа)

s=string % задаем s типа string (строки)

predicates

nondeterm calculate1(r,r)

nondeterm calculate2(r,r,r,r,r,r,r,r)

nondeterm proverka (s)

% определяем предикаты calculate1, calculate2, proverka. Ключевое слово nondeterm означает, что данные предикаты недетерминированные, т.е. для каждого из объявленных предикатов существует более одной альтернативы. Предикат calculate1(номер уровня введенный пользователем, номер уровня в «данный момент») отвечает за проверку достижимости требуемого уровня. Предикат calculate2(номер уровня введенный пользователем, номер уровня в данный момент, искомый элемент данного уровня, …вспомогательные переменные).

Clauses

% обработка нажатия кнопки Ok

dlg_mydialog_eh(_Win,e_Control(idc_ok,_CtrlType,_CtrlWin,_CtlInfo),0):-!,

EDIT_WIN=win_GetCtlHandle(_WIN,idc_mydialog_1), P=win_GetText(EDIT_WIN), proverka(P),!.

proverka (P):- str_real(P,P1),!,nl, write ("Треуголик Паскаля с уровнем равным ",P),calculate1(P1,1),!.

proverka(P):- dlg_MessageBox("Ошибка","Вы должны ввести ЧИСЛО большее 0 ",2,0,0,0).

calculate1(X,N):- X<=0,nl,write ("Ошибка!!!Введите положительное целое число, большее 0").

calculate1(X,N):- N<=X,nl,calculate2(X,N,1,0,1,N,1,0),!.

calculate2(X,N,X1,Y1,Z1,T1,F1,F3):- X1>0, write (X1," "), Y2=Y1+1,Z2=Z1*Y2,

T2=T1-F3,F2=F1*T2,X2=F2/Z2,F4=F3+1, !,calculate2(X,N,X2,Y2,Z2,T1,F2,F4).

calculate2(X,N,X1,_,_,_,_,_):- N1=N+1,calculate1(X,N1).

Работу программы можно описать следующим образом: в переменную Edit_WIN передаем управление компонентом mydialog_1 (поле ввода требуемого уровня), который имеет идентификатор idc_mydialog_1. В P мы записываем значение, введенное пользователем, используя встроенный предикат win_GetText. Далее вызываем предикат proverka, предназначенный для проверки корректности введенного пользователем значения. Для этого используется встроенный предикат str_real, который переводит переменные типа string в переменные типа real. В случае успеха в переменную P1 записывается значение пользователя, но уже в числовом виде и происходит вызов предиката calculate1, который совместно c предикатом calculate2 отвечают за нахождение элементов треугольника. В случае неудачи выдается соответствующее сообщение, извещающее пользователя о необходимости ввода только чисел. При вызове предиката calculate1 переменная X содержит значение введенного пользователем уровня, а переменная N содержит номер уровня на текущий момент поиска решения. При успешной проверке X<=N (то есть требуемый уровень еще не достигнут) происходит вызов предиката calculate2. Предисат calculate2 рекурсивно вычисляет элементы очередного уровня треугольника Паскаля. По окончании вычислений всех элементов очередного уровня вторая альтернатива предиката calculate2 вызывает предикат calculate1 с увеличенным на единицу значением уровня треугольника. Программа завершает свою работу по мере достижения требуемого уровня.

Основной код программы прописан, но он сработает только после нажатия на кнопку OK диалогового окна MyDialog, которое пользователю еще необходимо вызвать. В нашем проекте вызов диалогового окна будет производиться нажатием одного из пунктов меню. Для этого необходимо в окне проекта (рисунок 3) нажать на кнопку Menu, двойным щелчком открыть окно меню, в котором создать дополнительный пункт (рисунок 9.) при помощи кнопки New (в нашем проекте был создан пункт меню Paskal) и установить соответствующие атрибуты пункта меню, включая его идентификатор (в нашем случае id_paskal).

Рисунок 9 - Окно редактирования меню проекта

Для перехода к редактору кода данного пункта меню необходимо проделать операции аналогичные действиям описанным для перехода к коду кнопки OK, но при этомнеобходимо выбрать окно Task Window, выбрать в списке Event Type позицию Menu, в списке Event or Item выбрать идентификатор нужного пункта меню (в нашем проекте это id_paskal, рисунок 10) и нажать соответствующую кнопку для перехода к редактору кода.

Рисунок 10 - Dialog and Window Expert

В редакторе кода необходимо прописать вызов диалогового окна MyDialog:

task_win_eh(_Win,e_Menu(id_paskal,_ShiftCtlAlt),0):-!,

dlg_mydialog_Create(_Win),!.

Для запуска проекта необходимо нажать на клавиатуре кнопку F9 либо соответствующие кнопки в меню или на панели инструментов.

При запуске программы, пользователь вызывает окно MyDialog нажатием кнопки Paskal меню. В появившемся окне пользователь вводит требуемый уровень и нажимает на кнопку OK. В окне Messages выводится результат выполнения программы (рисунок 11).

Рисунок 11 - Результат работы Prolog-программы

Вывод:

В ходе выполнения работы я освоил основные секции prolog-программы и научился использовать рекурсию для поиска решений.

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

Задание: Объединить два списка, найти максимальный элемент и удалить его.

Ход выполнения:

В среде Visual Prolog 5.2 создан соответствующий проект.

Логика программы:

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