Работы с использованием пакета Turbo-Prolog - 6 часов Лабораторная работа № 2а. Знакомство с пакетом: диалог со справочной системой на естественном (усеченном) английском языке.

Пакет Turbo-Prolog версии 2.0 является одной из DOS-версий реализации языка логического программирования (Пролог). Пакет прост в обращении и содержит немало примеров программ, имеющих отношение к искусственному интеллекту и экспертным системам. Среди таких примеров - программа geobase.pro, представляющая собой справочную систему по географии США и отвечающая на вопросы пользователя, задаваемые на естественном (впрочем, весьма ограниченном, но расширяемом) английском языке. В программу лабораторных работ включена как повод для первого закомства с пакетом и как редкий пример интерфейса на естественном языке.

Для запуска программы откройте папку Prolog на диске С: и запустите программу prolog.exe. Заставка пакета убирается нажатием клавиши "пробел". В открывшемся окне следует выбрать опцию Files и трижды нажать клавишу Enter. В открывшемся списке программ следует выбрать и запустить нажатием Enter программу geobase.pro. В результате этих действий вы оказываетесь в редакторе. Для выхода из редактора следует воспользоваться клавишей Escape. Выбрав опцию Run и нажав клавишу Enter и "пробел" (чтобы убрать сообщение о значениях переменных), вы попадаете в главное меню.

Для выполнения лабораторной работы следует сначала выбрать в нем опцию Tutorial и внимально изучить инструкцию по пользованию справочной системой (возврат в главное меню - через нажатие клавиши Escape). После изучения инструкции можно обратиться к опции Query the database. Вы должны задать и получить ответы не менее, чем на 20 вопросов. Ваша цель должна состоять не только в получении интересующей вас информации о США, но и в выяснении интеллектуальных возможностей этой системы.

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

Структура программы на языке Турбо-Пролог. В общем случае программа на Турбо-Прологе состоит из разделов: domains, database, predicates, goal, clauses. Раздел domains содержит определения доменов (классов объектов, используемых в программе). Раздел database включает описание предикатов, фигурирующих в динамических базах данных, используемых в программе. Раздел predicates представляет собой описание предикатов, употребляемых непосредственно в самой программе. Раздел goal формулирует назначение программы (описание искомого решения задачи). Раздел clauses представляет собой перечень фактов и правил, используемых в процессе поиска решения задачи (осуществления цели).

Большинство программ содержит не все перечисленные разделы. Так раздел domains необходим, если встроенных в Турбо-Пролог доменов (char, integer, real, string, file, symbol) для построения программы недостаточно. Домены - это по сути аналог типов данных, определяемых пользователем в процедурных языках. Раздел database необходим в том случае, если программа предназначена для работы с большими объемами меняющихся со временем данных. Раздел goal также не всегда используется. Если цель (goal) задана, база знаний функционирует как программа, вычисляющая эту цель с учетом поступивших в базу данных и содержащихся в разделе clauses фактов. Если же цель (goal) не задана, Турбо-Пролог при каждом запуске запрашивает ее как внешнюю, задаваемую пользователем цель, т.е. работает как база знаний, отвечающая на запросы пользователя. Необходимыми для работы любой программы являются лишь разделы predicates и clauses, так как в этих разделах сосредоточено описание предикатов, фактов и правил вычисления ответов на запросы пользователя.

Программирование в логических языках состоит в построении модели предметной области (ПО) в терминах объектов, их свойств и отношений. Свойства и отношения объектов задаются с помощью предикатов. Операции тоже задаются предикатами (например, предикат sum(X,Y,Z). выполнен, если X+Y=Z). Простейшая программа состоит из одного или нескольких фактов (утверждений). Ниже приведена такая программа. Она содержит утверждения о ролях в учебном процессе четырех преподавателей. Запустите prolog.exe. Выбрав опцию edit, войдите в редактор и наберите приведенный ниже текст (примечание: для работы набранную программу сохранять не требуется и не следует).

/* Программа teachers.pro */

predicates

lecturer(symbol)

assistant(symbol)

clauses

lecturer("Иванов").

lecturer("Семенов").

assistant("Петров").

assistant("Сидоров").

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

Goal: lecturer("Петров").

Goal: lecturer("Иванов").

Goal: assistant("Петров").

Goal: assistant("Иванов").

Дайте объяснение полученным ответам.

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

Если вместо конкретного объекта (в данной программе - фамилии-константы) в качестве аргумента предиката указана переменная, программа ищет все возможные варианты выполнения данного предиката. Убедитесь в этом, набрав запросы:

Goal: lecturer(Х).

Goal: assistant(Х).

Усложним нашу программу, дополнив раздел predicates предикатами:

subject(symbol,symbol)

worker(symbol,symbol)

Дополним также раздел clauses фактами, использующими введенные предикаты:

subject("Иванов","ИИС").

subject("Петров","ИИС").

subject("Сидоров","ДМ").

subject("Семенов","ДМ").

worker("Иванов","ОСУ").

worker("Петров","ОСУ").

worker("Сидоров","ПМ").

worker("Семенов","ПМ").

worker("Смирнов","ПМ").

worker("Федоров","ИДО").

Теперь мы можем построить более сложные запросы. Например, можно спросить, кто является лектором по дисциплине "ИИС" ("Интеллектуальные информационные системы") и на какой кафедре он работает:

Goal: subject(X,"ИИС"), lecturer(X), worker(X,Y).

Задание: сформулируйте и проверьте следующие запросы:

Кто работает на кафедре прикладной математики ("ПМ")?

Кто лектор из работающих на кафедре "ПМ" и какую дисциплину он читает?

Кто ассистент из преподающих дискретную математику ("ДМ")и где он работает?

Придумайте и проверьте собственные запросы.

Возврат

Лабораторная работа № 3а. Использование правил и статических баз данных.

До сих пор наша программа teachers.pro содержала различные факты, а всё, что нам было нужно извлечь из знания этих фактов, мы определяли, формулируя различные запросы. Введем в программу новую конструкцию, называемую правилом.

Правило обычно имеет вид: А:-В1,В2,…,Вn. Левая часть правила (А) называется заголовком и представляет собой атомарную формулу. Правая часть (В1,В2,…,Вn) называется телом правила и представляет собой множество (возможно пустое) подцелей, выполнение которых необходимо для выполнения А. Знак :- читается как "если". Значит, запись А:-В1,В2,…,Вn читается так: "А имеет место, если имеют место В1 и В2 и…и Вn", т.е. запятая в записи правила играет роль логической связки "и" (вместо запятой можно также писать AND).

Дополним раздел predicates нашей программы еще парой предикатов:

teacher(symbol)

teacher_chair(symbol,symbol)

Кроме того, в раздел clauses введем три правила:

teacher(X):-lecturer(X).

teacher(X):-assistant(X).

teacher_chair(X,Y):-teacher(X),worker(X,Y).

Первые два правила вводят более общее понятие teacher (преподаватель), объединяя в нем и лектора, и ассистента, а третье правило, напротив, конкретизирует это обобщение до понятия teacher_chair (преподаватель_кафедры). Теперь с помощью запросов

teacher(X).

teacher_chair(X,Y).

teacher_chair(X,"ОСУ").

teacher_chair(X,"ПМ").

teacher_chair("Иванов",Y).

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

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

teacher(X):-lecturer(X); assistant(X).

teacher_chair(X,Y):-teacher(X),worker(X,Y).

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

Наконец, все эти сведения мы можем свести в единую базу данных, использовав предикат staff (штат) с необходимым числом аргументов. Для удобства для разных аргументов этого предиката введем разные обозначения типов объектов, что потребует использования раздела domains. Таким образом, наша новая программа примет вид:

/* Программа staff.pro */

domains

chair,subject,status,name =symbol

age=integer

predicates

staff(chair,subject,status,name,age)

clauses

staff("ОСУ","ЭС","лектор","Иванов",30).

staff("ОСУ","ЭС","ассистент","Петров",23).

Задание: Заполните базу данных остальными фактами, использованными в данной лабораторной работе и придуманными вами, и сформируйте следующие запросы:

Кто работает на кафедре "ОСУ"?

Кто на кафедре "ОСУ" имеет возраст меньше 30?

Какая кафедра и какие преподаватели обеспечивают дисциплину "ЭС"?

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

Внимание: в предикате запроса ставится подчерк _ в том его аргументе, сведения по которому вам не требуются.

Лабораторная работа № 3б. Использование повторения.

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

Вид правила, выполняющего повторение, следующий:

repetitive_rule:- /* правило повторения */

<предикаты и правила>

fail. /* неудача */

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

Вид правила, выполняющего рекурсию, следующий:

recursive_rule:- /* правило рекурсии */

<предикаты и правила>,

recursive_rule.

Обратите внимание,что последним правилом в теле данного правила является само правило (recursive_rule).

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

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

/* Программа staff1.pro */

domains

chair,subject,status,name =symbol

age=integer

predicates

staff(chair,subject,status,name,age)

show_staff

goal

show_staff.

clauses

staff("ОСУ","ИИС","лектор","Иванов",30).

staff("ОСУ","ИИС","ассистент","Петров",23).

show_staff:- staff(Chair,Subject,Status,Name,Age),

write(Chair,Subject,Status,Name,Age), nl,

fail.

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

Задание:

1.Создайте файл staff1.pro с текстом данной программы и убедитесь в ее работоспособности; отредактируйте ее так, чтобы данные на экране были удобочитаемы.

2.Удалите из правила предикат fail (вместе с предшествующей ему запятой). Чем отличается работа программы в этой редации от предыдущей?

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

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

Возврат

Лабораторная работа № 4а. Использование рекурсии в Turbo-Prolog.

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

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

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

Рассмотрим, для примера, программу проверки связности в ориентированном графе (орграфе). Орграф можно задать с помощью набора фактов следующего вида:

edge(a, b).

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

edge (a,d). edge (b, a). edge (d, e). edge (e,f).

edge (a, c). edge (b, e). edge (f, b).

Две вершины в орграфе связаны, если существует последовательность ребер, ведущая из первой вершины во вторую. Таким образом, предикат сonnected(B1,В2.) истинен, если В1 и В2 связаны. Тогда процедура, описывающая связность, будет иметь следующий вид:

сonneсted(B 1, В2):- edge(В1, В2).

connected(В1,В2):-edge(Вl, X), connected(Х, В2).

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

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

Goal: сonneсted(a,f).

ответ будет "да" (yes).

Задание:

1.Нарисуйте граф, представленный выше в виде фактов о связи вершин.

2.Напишите и отладьте программу connect.pro, использующую данные выше правила.

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