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

Размещено на http://allbest.ru

1. Знакомство с языком логического программирования Visual Prolog

программирование пролог домен файловый

Цель работы

Изучить основные языковые конструкции языка Пролог и ознакомиться со средой Visual Prolog.

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

В этой работе Вы познакомитесь с языком логического программирования Пролог. Теоретической основой языка Пролога является раздел символьной логики, называемый исчислением предикатов. Название Пролог (Prolog) произошло от словосочетания «программирование при помощи логики» (PROgramming in LOGic).

Создание логического программирования можно приписать Роберту Ковальскому и Алэну Колмероэ. Р. Ковальский разработал процедурную интерпретацию хорновских дизъюнктов. В начале 70-х годов А. Колмероэ и его группа создали в Марсельском университете (Франция) специальную, написанную на Фортране программу, предназначенную для доказательства теорем. Программа доказательства теорем, названная Прологом, включала в себя интерпретатор Р. Ковальского. С тех пор было сделано несколько расширений и усовершенствований языка. Здесь можно отметить работу группы из Эдинбургского университета (Шотландия). Шотландский вариант получил название C&M Prolog в честь авторов классической работы «Программирование на языке Пролог» Уильяма Клоксина и Кристоффера Меллиша. Сегодняшней своей популярности Пролог во многом обязан эффективной реализации этого языка, полученной в Эдинбурге Дэвидом Уорреном и его коллегами в конце 70-х годов. Написанный ими компилятор (компилятор был почти полностью написан на Прологе) остается и поныне одной из лучших реализаций Пролога.

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

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

При выполнении лабораторных работ мы будем использовать визуальную среду программирования - VisualProlog. Существует реализация системы VisualProlog для таких платформ как: DOS, Windows 3.x, Windows 95/98, Windows NT, OS/2, SCO Unix, Linux. VisualProlog прекрасное средство для разработки клиент-серверных приложений. В настоящее время Visual Prolog также включает оболочку для разработки экспертных систем - ESTA.

Факты и правила

Программирование на языке Пролог состоит их 3-х этапов:

Определение фактов предметной области.

Факты могут описывать свойства объектов и отношения между объектами. Например, факт «нравится ellen tennis» можно записать так: likes(ellen, tennis).

Этот факт включает в себя два объекта, обозначенных словами ellen и tennis, и отношение, обозначенное словом likes (нравится). Обратите внимание, что каждый факт и каждое правило предметной области должны заканчиваться точкой. Имена объектов, список которых в каждом факте заключен в круглые скобки, называются аргументами. Имя отношения - называется предикатом. Таким образом, likes - предикат с двумя аргументами.

Определение правил.

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

Общий вид правила:

A: - B1, ..., Bn. (n>0)

Здесь A - заголовок правила, Bi - тело правила. Символ «:-» читается «если». Возможны два варианта прочтения данного правила:

декларативное прочтение - «A истинно, если истинны Bi»;

процедурное прочтение - «чтобы решить задачу A, сначала надо решить подзадачу B1, затем подзадачу B2, ..., затем подзадачу Bn». Таким образом, для выполнения цели в заголовке правила, необходимо вначале выполнить (согласовать) все подцели из тела правила. Например, правило «тому нравится футбол, если футбол является видом спорта» на Прологе можно записать следующим образом:

likes(tom, football):- sport(football)

Цель likes(tom, football) будет истинной в том случае, если выполняются все подцели из тела правила. В данном случае подцель sport(football).

Формулировка вопросов об объектах предметной области и отношениях между ними.

Имея некоторую совокупность фактов, мы можем обращаться к Прологу с вопросами о них.

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

likes(ellen, tennis).

likes(tom, football).

likes(tom, swimming).

Теперь мы можем задать системе вопрос «нравится ли тому футбол»:

likes(tom, football)

yes

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

Переменные

До сих пор мы рассматривали отношения, аргументами которых выступали конкретные объекты - константы, такие как, ellen, tennis, и т.д. Такие объекты называются атомами. Аргументами отношений могут выступать также абстрактные объекты - переменные. Переменные используются для задания общих правил и формулировки общих вопросов. Переменные должны начинаться с большой буквы. Например, правило «биллу нравится то же, что и тому» на Прологе можно записать так:

likes(bill, X):- likes(tom, X).

В этом правиле объект X - переменная, объекты bill и tom - константы (начинаются с маленькой буквы). Если Вы хотите, чтобы константа начиналась с большой буквы, необходимо заключить ее в двойные кавычки, например: «Bill».

Переменная может также встречаться в запросе. Если в запрос переменная не входит, то ответом будет либо да (yes), либо нет (no). Если же в запрос входит переменная, то Пролог найдет все значения этой переменной и вернет ответ. Например, вопрос «что нравится биллу» можно записать на Прологе.

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

What = football

What = swimming

Solutions

Иногда возникает необходимость в использовании переменной, имя которой не будет потом нигде употребляться. Например, если необходимо определить «нравится ли что-то тому» и при этом не важно, что именно, можно использовать анонимную переменную. Анонимная переменная обозначается одиночным знаком подчеркивания: «_». Например, вопрос «нравится ли что-то тому» на Прологе можно записать так:

likes(tom, _).

yes

Вопрос «нравится ли эллен теннис и нравится ли тому теннис» можно задать следующим образом:

likes(ellen, tennis), likes(tom, tennis).



Запятая между подцелями likes читается как «и». Пролог пытается согласовать каждую подцель по очереди. Сочетая возможности конъюнкции и использования переменных, можно строить достаточно содержательные вопросы. Например, вопрос «существует ли что-нибудь такое, что нравится обоим эллен и тому» на Прологе можно записать так:

likes(ellen, X), likes(tom, X).

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

Выполнение запроса

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

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

Свободная переменная сопоставляется с константой или с ранее связанной переменной (и становится связанной с соответствующим значением).

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

Механизм поиска с возвратом

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

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

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

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

Целевое утверждение считается согласованным, когда соответствующий факт найден для каждой оконечности (листа) целевого дерева.

Основные программные секции программ на VisualProlog

Обычно программа на VisualProlog состоит из 4-х программных секций. Каждой секции предшествует свое ключевое слово.

Секция доменов (domains) служит для объявления всех используемых нестандартных доменов. VisualProlog позволяет создавать свои собственные типы объектов из базисных типов доменов. Существует несколько встроенных стандартных доменов.

Пример описания нестандартных типов данных:

domains

person, thing = symbol

age = integer



Секция предикатов (predicates) используется для объявления всех используемых в программе нестандартных предикатов. Описание предиката состоит из имени предиката, за которым в круглых скобках через запятую перечисляются типы аргументов:

predicateName(argument_type1, argument_type2, ...,

argument_typeN)

Например, чтобы использовать предикат likes в программе, необходимо вначале его описать в разделе предикатов:

predicates

likes(symbol, symbol)



Это описание означает, что оба объекта предиката likes относятся к типу symbol. С учетом сделанного выше объявления в разделе domains предикат likes можно описать следующим образом:

likes(person, thing)

Следует отметить, что хоть типы person и thing описывают данные типа symbol, они являются разными типами. Это означает, что, например, данные типа person могут в утверждениях занимать только место первого аргумента предиката likes.

Секция утверждений (clauses) содержит описание фактов и правил.

Например:

clauses

likes(ellen, tennis).

likes(tom, tennis).

likes(bill, X):- likes(tom, X).

Секция целей (goal) используется для задания целевого утверждения (запроса).

Например, целевым утверждением может являться запрос «найти все, что нравится биллу»:

goal

likes(bill, What).

Секция целей ничем не отличается от тела правила: в ней также как и в теле правила перечисляются подцели. VisualProlog автоматически вычисляет подцели в разделе goal после запуска программы и выдает ответ в отдельном окне.

Кроме перечисленных, существуют и другие программные секции:

секция констант (constants) - можно объявить символьные константы, которые затем можно будет использовать в программе. Для объявления констант используется следующий синтаксис:

<constant_name> = <definition>

constants

two = 2

goal

X = two + two.

Пролог выдаст ответ:

X = 4

Solution

секция динамических баз данных (database или facts) - содержит определение предикатов динамической базы данных. Факты динамической базы данных можно добавлять и удалять непосредственно во время исполнения программы.

секция глобальных определений (global domains, global predicates, global database) - позволяет задать глобальные определения, видимые в других модулях.

Среда VisualProlog

Система VisualProlog включает: интерактивную визуальную среду разработки приложений, состоящую из текстового и разнообразных графических редакторов; инструменты генерации кода (Experts); расширение Пролога в форме VPI (Visual Programming Interface); компилятор с языка Пролог; различные библиотеки; компановщик; примеры программ и файлы помощи.

Для запуска VisualProlog выберите пункт Vip32 из меню Пуск > Программы > Visual Prolog 5.2 Personal Edition. После запуска системы на экране появятся два окна (Рис.): первое - главное окно приложения, второе - окно сообщений, в котором при работе с системой выводятся сообщения о компиляции программ, о сохранении компонент проекта и т. д. Главное окно приложения содержит главное меню и панель инструментов, содержащую кнопки для наиболее часто используемых команд меню:

Главное меню включает следующие пункты:

Для создания простых программ в среде VisualProlog не обязательно создавать проект, а достаточно выбрать из меню команду File > New. Созданная таким образом программа должна обязательно содержать секцию goal. Для тестирования созданной программы можно воспользоваться командой меню Project > Test Goal. На экране появится окно, содержащее результаты работы программы.

Для создания приложений, содержащих графический интерфейс пользователя, необходимо создать проект. Для создания нового проекта надо выбрать пункт меню Project > New project… На экране появится диалоговое окно Application Expert (Рис.), позволяющее задать информацию о проекте.

Минимальная информация о проекте, которую необходимо указать в окне Application Expert следующая: имя проекта и каталог, в котором он будет размещен. В таблице приведено описание основных параметров проекта.



После задания параметров проекта, для его создания необходимо нажать на кнопку create. На экране появится окно проекта, содержащее два модуля: VPITools.pro и имя_проекта.pro (Рис.).

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

Для выполнения созданного приложения необходимо выбрать команду меню Project > Run или нажать клавишу f9. Для отладки приложения с помощью программы VisualProlog Debugger нужно выбрать команду Project > Debug или нажать комбинацию клавиш shift+ctrl+f9.

Выполнение работы

Запустите VisualProlog, затем выберите из меню команду File > Open… В появившемся диалоговом окне укажите имя файла VIP\DOC\EXAMPLES\ch02e01.pro. Эта программа должна выглядеть следующим образом:

predicates

likes(symbol,symbol)

clauses

likes(ellen,tennis).

likes(tom,baseball).

likes(eric,swimming).

likes(tom, football).

likes(mark,tennis).

likes(bill,Activity):-likes(tom, Activity).

Как видно из приведенного листинга секция predicates содержит описание предиката likes, содержащего два аргумента типа symbol. В разделе clauses объявлено 5 фактов и одно правило.

Задайте в разделе goal следующее целевое утверждение:

goal

likes(tom, football).

Для выполнения целевого утверждения выберите из меню команду Project > Test Goal или нажмите комбинацию клавиш alt+g. В окне Messages появятся сообщения о компиляции программы, а затем на экране появится окно, содержащее полученный ответ - yes (так как целевое утверждение согласуется с базой данных).

Измените целевое утверждение следующим образом:

goal

likes(bill, X).

В результате выполнения этого целевого утверждения получим ответ:

X = baseball

X = football

2 Solutions



При сопоставлении этого целевого утверждения с базой данных Пролог выберет правило likes(bill,Activity):-likes(tom, Activity), поскольку первый аргумент исходного целевого утверждения - bill, совпадает с первым аргументом заголовка правила (первое правило унификации), а вторым аргументом целевого утверждения является свободная переменная X, которая связывается со свободной переменной из заголовка правила - Activity (третье правило унификации). Для доказательства утверждения likes(bill, Activity) необходимо вначале доказать (согласовать) все утверждения из тела правила. Таким образом, цель likes(tom, Activity) становится новой подцелью для доказательства. Пролог просматривает базу фактов и правил и пытается найти утверждение, согласующееся с целевым. Первый факт - likes(ellen, tennis) не подходит, поскольку первым аргументом нового целевого утверждения выступает константа tom. Первым аргументом следующего факта раздела clauses является константа tom, а вторым - константа baseball. Поскольку вторым аргументом целевого утверждения является свободная переменная Activity, то она сопоставляется с соответствующей константой (второе правило унификации) и получает значение baseball (подцель likes(tom, Activity) доказана). Далее Пролог возвращает найденное значение переменной Activity в правило likes(bill, Activity):- likes(tom, Activity). Правило доказано, поскольку доказаны все подцели, содержащиеся в его теле.

Перменная X связана с переменной Activity. Поскольку переменная Activity теперь конкретизирована значением baseball, то это же значение приобретает и переменная X. Найденное значение возвращается пользователю и появляется в соответствующем окне. Пролог пытается найти все решения. Вначале он пытается передоказать подцель likes(tom, Activity). Следуя правилам унификации, Пролог находит новое решение: Activity=football. Это значение возвращается в правило likes(bill, Activity) и переменная X получает новое значение: X = football, которое и возвращается пользователю. Пролог снова пытается передоказать подцель likes(tom, Activity), но подходящих утверждений в базе данных больше нет. Затем Пролог пытается передоказать целевое утверждение likes(bill, X). Поскольку больше подходящих утверждений в базе данных нет, в окно выводится сообщение: 2 Solutions.

К сожалению, в таком режиме (не создавая проект) невозможно выполнить отладку программы. Для использования отладчика VisualProlog Debugger необходимо создать проект и включить в основной модуль приведенный выше код.

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

Необходимо описать предметную область «родственные отношения». Для этого задайте в качестве фактов следующие отношения между объектами предметной области:

parents(X, Y) - X является родителем Y;

man(X) - X мужчина;

woman(X) -X женщина.

Например,

parents(tom, ellen).

man(tom).

woman(ellen).

Определите в качестве правил (используя отношения parents, man, woman) следующие отношения:

sister(X, Y) - X является сестрой Y;

brother(X, Y) - X является братом Y;

father(X, Y) - X является отцом Y;

mother(X, Y) - X является матерью Y;

grandfather(X, Y) - X является дедушкой Y.



2. Рекурсия и итерация в языке Пролог

Цель работы

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

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

Рекурсия и итерация

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

Управление поиском с возвратом

Для реализации повторных вычислений в традиционных языках существует ряд операторов (for, while, repeat). Однако в языке Пролог отсутствуют их аналоги. Пролог позволяет только два вида повторений: возврат, в котором осуществляется поиск нескольких решений в одном запросе и рекурсию, в которой процедура вызывает сама себя. Для управления поиском с возвратом используются два встроенных предиката:

fail (неудача) - осуществляет вынужденное неудачное завершение выполнение предиката и, таким образом, инициирует процесс возврата.

Cut или ! (отсечение) - используется для предотвращения поиска с возвратом.

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

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

Факт (первое утверждение) будет использоваться для выполнения всех подцелей программы. Таким образом, repeat - это рекурсивное правило, которое никогда не бывает неуспешным.

В качестве примера использования предиката repeat рассмотрим следующую программу:

predicates

repat

typewriter

clauses

repeat.

repat:- repeat.

typewriter:- repeat, readchar(C), write(C),

char_int(C, 13).

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

Выполнение работы

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

Каноническим примером рекурсивных функций является функция вычисления факториала числа. Число n! (n факториал) определяется как (n)*(n-1)*(n-2)* ... *(1). Факториал числа 0 равен 1. Заметьте также, что n! = (n)*(n-1)!.

Математическое определение факториала рекурсивно и его реализация через рекурсивную функцию совершенно естественна. Ниже приведена программная реализация функции вычисления факториала числа на языке Паскаль.

procedure Factorial(N:integer; var Y:integer);

var

NewN, NewY: integer;

begin

if N = 0 then Y:= 1

else

if N > 0 then

begin

NewN:= N - 1;

Factorial(NewN, NewY);

Y:= NewY * N

end

end;

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

factorial(0, 1).

factorial(N, Y):- N>0,

NewN = N -1,

factorial(NewN, NewY),

Y = NewY * N.

factorial(3, Y)

Y=6

При выполнении целевого утверждения factorial(3, Y) получим следующую последовательность рекурсивных вызовов:

factorial(3, Y)

...

factorial(2, NewY)

...

factorial(1, NewY')

...

factorial(0, NewY'') - (0!)= 1, NewY''= 1

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

Таким образом, факт (0!) = 1 не будет использоваться до тех пор, пока в ходе исполнения программы не будет порожден вызов, специально требующий вычисления значения 0!.

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

procedure factorial(N:integer; var Y:integer);

var

I, P: integer;

begin

I:=0; P:=1;

while I < N do

begin

I:= I+1;

P:= P*I

end;

Y:=P;

end;

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

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

Для выполнения оптимизации остатка рекурсии необходимо, чтобы соблюдались следующие условия:

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

Ранее в предложении не должно быть точек возврата.

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

factorial(N, Y):-factorial(0, 1, N, Y).

factorial(N, Y, N, Y):-!.

factorial(I, P, N, Y):-I<N,

NewI=I+1, NewP=P*NewI,

factorial(NewI, NewP, N, Y).

factorial(3, Y)

Y=6

Эта программа порождает вычисления методом снизу вверх - значение 1! вычисляется исходя из значения 0!, затем значение 2! исходя из 1! и т. д. В Прологе отсутствуют «локальные» переменные для удержания промежуточных результатов и их изменения в процессе вычисления. Поэтому для реализации итерационных алгоритмов, требующих сохранения промежуточных результатов, процедуры Пролога дополняются аргументами, называемыми накопителями. Накопители являются логическими переменными, а не ячейками памяти. В процессе итерации передается не адрес, а значение. Так как логические переменные обладают свойством «одноразовой записи», то измененное значение - новая логическая переменная - передается каждый раз. Поэтому для указания измененных значений в обозначениях переменных используется префикс New. Обычно промежуточное значение соответствует результату вычисления при завершении итерации. Это значение сопоставляется результирующей переменной с помощью единичного предложения процедуры. В приведенном примере промежуточное значение факториала числа сохраняется в переменной P. Как только значение счетчика I будет равно значению N, результат вычисления факториала копируется из переменной P в переменную Y и возвращается пользователю. При выполнении целевого утверждения factorial(3, Y) получим следующую последовательность рекурсивных вызовов:

factorial(3, Y)

factorial(0, 1, 3, Y)

...

factorial(1, 1, 3, Y)

...

factorial(2, 2, 3, Y)

...

factorial(3, 6, 3, Y)

Y:=6

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

Написать функцию, использующую метод Ньютона для вычисления квадратного корня. Метод Ньютона вычисления квадратного корня из числа x начинается с выбора начального приближения y. Это приближение считается достаточно точным, если | x - y² | <= err, где err - некоторая заранее определенная погрешность. В противном случае более точным приближением будет 1/2 *(y + x/y), которое можно вычислить и точно так же подвергнуть проверке на погрешность. Для получения абсолютной величины числа используйте функция abs: abs(-5) = 5.

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

Написать функции для вычисления N-го числа последовательности Фибоначчи. Каждое следующее число последовательности Фибоначчи вычисляется как сумма двух предыдущих. Два первых числа равны единице.

Контрольные вопросы

Треугольное число с индексом N - это сумма всех натуральных чисел до N включительно. Напишите рекурсивную и итерационную программы, задающую отношение triangle(N, T), истинное, если T - треугольное число с индексом N.

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

Определить процедуру between(N1, N2, X), которая порождает все целые числа X, отвечающие условию N1 X N2.

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

Например,

fact(3, S)

S=1*2*3

3. Рекурсивные структуры данных

Цель работы

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

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

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

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

Бинарные деревья

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



type TreeType = ^Tree;

Tree = record

Element: string;

Left, Right: TreeType;

end;

Здесь Element - элемент, находящийся в вершине, а Left и Right - соответственно левое и правое поддерево.

В языке Пролог бинарное дерево можно задать с помощью тернарного функтора tree(Element, Left, Right):

domains

treetype = tree(string, treetype, treetype);

empty()

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

tree(“1”,

tree(“2”,

tree(“4”, empty, empty),

tree(“5”, empty, empty)),

tree(“3”,

tree(“6”, empty, empty),

tree(“7”, empty, empty)))

Списки

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

В языке Пролог введена специальная форма для представления списка с головой X и хвостом Y. Такой список записывается как [X|Y], где для разделения X и Y используется вертикальная черта. При конкретизации структуры подобного вида X сопоставляется с головой списка, а Y - с хвостом списка. В приведенном выше примере при сопоставлении списка [1, 2, 3] со структурой [X|Y] переменная X примет значение 1, а переменная Y - [2, 3]. Представление списка в виде головы и хвоста было принято для удобной рекурсивной обработки элементов списка. В языке Паскаль объявить тип list, описывающий список целых чисел можно следующим образом:

type list = ^TElemList;

TElemList = record;

Inf: char;

Next: list;

end;

В языке Пролог списковый тип объявляется так:

domains

name_of_list_type = type_of_elements*



Здесь name_of_list_type является доменом списка элементов типа type_of_elements. Например, тип list, описывающий список целых чисел, можно объявить следующим образом:

domains

list = integer*

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

Например,

llist = l(list); s(symbol); i(integer); c(char)

list = llist*

Тогда список [a, 1, [b, c]] будет представлен следующим образом: [s(a), i(1), l([s(b), s(c)])].

Выполнение работы

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

Прохождение бинарных деревьев

Рассмотрим алгоритм обхода бинарного дерева в симметричном порядке. Этот алгоритм рекурсивен по своей природе и сводится к следующим шагам:

1. Пройти в симметричном порядке левое поддерево.

2. Попасть в корень.

3. Пройти в симметричном порядке правое поддерево.

На языке Паскаль этот алгоритм можно записать следующим образом:



type TPNode = ^Tree;

Tree = record

Element: string;

Left, Right: TPNode;

end;

procedure PBDSP (PTree: TPNode);

begin

if PTree <> Nil then

begin PBDSP (PTree^.Left);

Writeln (PTree^.Element);

PBDSP (PTree^.Right)

end

end;

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

traverse(empty).

traverse(

tree(Element, Left, Right)):-traverse(Left),

write(Element), nl,

traverse(Right).

Обработка списков

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

Элемент совпадает с головой списка.

Элемент принадлежит хвосту списка.

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

type TList = ^TElemList;

TElemList = record;

Inf: char;

Next: TList;.

end;

function Find(Elem:Сhar; List:TList):boolean;

begin

{Проверяется случай, когда список пуст}

if (List = Nil) then Find:=false

{Рассматривается случай, когда список не пуст}

else {искомый элемент совпадает с головой списка}

if List^.Inf = Elem then Find:= true

{иначе ищем элемент в хвосте списка}

else Find:= Find(Elem, List^.Next);

end;

Функция Find получает два аргумента: искомый элемент и список, в котором производится поиск.

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

domains

list = element*

element = symbol

predicates

find(element, list)

clauses

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

find(Elem, [Elem_]).

%иначе ищем элемент в хвосте списка

find(Elem, [_Tail]):-find(Elem, Tail).

find(“3”, [“1”', “3”, “4”])

Yes

При задании целевого утверждения Пролог попытается вначале применить первое правило. Если искомый элемент не совпадает с первым элементом списка (головой списка), то делается откат и Пролог пытается для доказательства целевого утверждения применить второе правило. Пролог унифицирует имеющиеся термы с заголовком второго правила find(Elem, [_Tail]). При этом первый элемент списка ставится в соответствие анонимной переменной. Так делается потому, что значение первого элемента списка не представляет для нас интереса (второе правило не было бы задействовано, если бы первый элемент списка совпадал с объектом поиска - первое правило). Теперь мы хотим присвоить переменной Tail хвост списка, чтобы Пролог попытался установить соответствие между объектом поиска и головой хвоста списка. Попытка согласовать подцель find(Elem, Tail) заставляет Пролог представить хвост текущего списка как новый самостоятельный список. Этот процесс повторяется до тех пор, пока либо выполнится первое правило (успешное завершение программы), либо пока не исчерпается весь список (неуспешное завершение программы). Так при выполнении целевого утверждения find(“3”, [“1”, “3”, “4”]) получим следующую последовательность рекурсивных вызовов.

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

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

Написать программу нахождения последнего элемента списка. Для нахождения последнего элемента списка используйте двунарный предикат last(type_of_elements, list). Первый аргумент этого предиката задает последний элемент списка, второй - список, в котором производится поиск последнего элемента, если элемент X является последним элементом списка L. Например:

last(3, [1, 2, 3])

Yes

last(X, [1, 2, 3])



Написать программу исключения первого вхождения элемента в список. Для исключения первого вхождения некоторого элемента в список используйте предикат exclude(type_of_elements, list, list). Цель exclude(X, Y, Z) исключает первое вхождение элемента X в список Y, формируя новый список Z.

Например:

exclude(2, [1, 2, 3, 2], Z)

Z=[1, 3, 2]

Написать программу обращения списка. Обращенный список можно получить путем присоединения головы этого списка к обращенному хвосту. Для решения задачи используйте двунарный предикат reverse(list, list). Первый аргумент этого предиката задает начальный список, второй - обращенный.

Например:

reverse([1, 2, 3], Y)

Y=[3, 2, 1]

Написать программу поиска минимального элемента списка и его порядкового номера в этом списке. Для решения задачи используйте тринарный предикат minimum(type_of_elements, integer, list). Первый аргумент в этом предикате задает минимальный элемент списка, второй - индекс этого элемента в списке, третий - список, в котором производится поиск минимального элемента. Т. о. цель minimum(X, N, L) согласуется с базой данных, если X является минимальным элементом списка L, а N - порядковый номер элемента X в этом списке.

Например:



minimum(1, 4, [2, 5, 3, 1, 7])

Yes

minimum(X, N, [2, 5, 3, 1, 7])

X=1, N=4

Написать программу сортировки элементов списка с помощью прямого включения. При сортировке включением каждый элемент списка рассматривается отдельно и включается в новый список на соответствующее место. Алгоритм этой сортировки следующий:

FOR i:= 2 TO n DO

x:= a[i];

включение x на соответствующее место среди

a[1] ... a[i]

END

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

Например:

insertion_sort([2, 5, 3, 1, 7], Y)

Y=[1, 2, 3, 5, 7]

Контрольные вопросы

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

В результате выполнения целевого утверждения find(X, [1, 2, 3]) переменная X примет следующие значения: X=1, X=2, X=3

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

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

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

Дан плоский замкнутый многоугольник {P₁, P₂, ..., P_n}. Требуется найти площадь ориентированного многоугольника. Площадь вычисляется с помощью линейного интеграла 1/2 xdy - ydx, где интегрирование производится по границе многоугольника. Решением данной задачи является приведенная ниже программа, задающая отношение area(Chain, Area). Chain является списком координат вершин. Значением переменной Area будет площадь многоугольника с данными вершинами.

area([Tuple], 0).

area([(X1, Y1), (X2, Y2)|XYs], Area):-

area([(X2, Y2)|XYs], Area1),

Area=(X1*Y2-Y1*X2)/2+Area1.

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

4. Представление и обработка списков

Изучение представлений списков и пролог программ поиска элемента в списке, разделения и объединения списков, сортировки списка, удаления дубликатов в списке. Разработка пролог-программ обработки списков.

Турбо-Пролог и списки

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

Список является набором объектов одного и того же доменного типа.

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

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

Пример.

[ 3, 8, 24, 38, 4, 2, 3, 3, 3 ]

[ 3.14, 3.62, 5.0, 3.14 ]

[ "RED", "BLUE", "GREEN" ]

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

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

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

- первый элемент списка - голова;

- остальная часть списка - хвост.

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

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



Применение списков в пролог - программе

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

описать домен и предикат списка.

Описание домена списка производится в разделе domains с указанием звездочки * после имени типа элемента списка.

domains

num = integer

num_list = num*

или:

domains

num_list = integer*

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

predicates

number(...,num_list,...).

Работа со списками основана на расщеплении их на голову и хвост.

Операция деления списка на голову и хвост обозначается при помощи вертикальной черты '|': [ H | T ] ([Голова|Хвост]).

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

Операция отсечения

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

Отсечение повлияет на вычисление цели А следующим образом. Перебор будет возможен в списке подцелей P, Q; однако, как только точка отсечения будет достигнута, найденные решения для подцелей P и Q фиксируются и все альтернативные решения для них не рассматриваются. Альтернативное предложение, входящее в процедуру: A:-R. также не будет учитываться. Тем не менее возврат (перебор) будет возможен в списке подцелей S, T.

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

без использования отсечения

f(X,Y):-X<1,Y=sin(X).

f(X,Y):-1<=X,X<3,Y=cos(X).

f(X,Y):-X>=3,Y=X*X.



с использованием отсечения

f(X,Y):-X<1,!,Y=sin(X).

f(X,Y):-X<3,!,Y:=cos(X).

f(X,Y):-Y=X*X.

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

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

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

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

member( 6, [ 3, 8, 6, 4, 2 ] ).

Для того, чтобы выяснить, является ли какой-либо элемент членом списка, необходимо установить, эквивалентен ли он голове списка, а если нет, то не является ли он членом хвоста списка, то есть для организации поиска необходима проверка двух условий:

- искомый элемент Х совпадает с головой списка

- элемент Х принадлежит хвосту этого списка.

Пример. Установить: cуществует ли в заданном списке символ 'А'.

domains

list = char*

predicates

member(list).

clauses

member(X,[X|_]).

member(X,[_|T]):- member(X,T).

goal

member('A',['C','D','T','A','G']).

Ответом будет 'yes'.

Разделение списка

Достаточно часто требуется разделить список на несколько частей.

В случае деления исходного списка L на список L1 (например, для которого элементы меньше значения M) и L2 (например, значение элементов больше или равно M), вводится следующий предикат:

del(M,L,L1,L2).

Организуется правило для разделения: очередной элемент извлекается из списка при помощи метода разделения списка на голову и хвост, а потом сравнивается с M.

Пример. Исходный список разделить на два списка по условию

L1, если X < M;

Х принадлежит

L2, если X >= M.

domains

list = integer*

predicates

del(integer,list,list,list).

clauses

del(M,[H|T],[H|L1],L2):- H < M,

del(M,T,L1,L2).

del(M,[H|T],L1,[H|L2]):- H >= M,

del(M,T,L1,L2).

del(_,[],[],[]).

goal

del(8,[1,2,13,4,5,12,18,2,12],L1,L2).

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

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

Пример. Объединить исходные списки L1 и L2 в выходной список L3.

domains

list = integer*

predicates

append(list,list,list).

clauses

append([],L,L).

append([N|L1],L2,[N|L3]):-append(L1,L2,L3).

goal

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

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

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

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

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

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

domains

number=integer

list=integer*

predicates

sort(list,list).

cord(number,number).

...