Программирование на языке 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 Основные конструкции языка

 

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

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

 

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

 

Пример 2

Константы:

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

 

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

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

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

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

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

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

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

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

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

 

 

Пример 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, поскольку в программе не существует тождественного факта, хотя где-то и может существовать собака с такой кличкой.

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