8. Подходы к программированию на языке Пролог.

Возможны три точки зрения на Пролог-программу:

реляционный подход -

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

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

поведенческий (бихевиористический) подход к программе ,

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

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

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

• анализ значимых сущностей и отношений в предметной области;

• выбор обозначений для представления этих сущностей и отношений,

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

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

отец(О,Р):- отец(О,Р), !. (на каждый запрос к правилу «отец» будет найдено не более одного ответа).

Встроенный предикат “сократить”: !

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

1) предикат “сократить” является одной из подцелей составного запроса, напр.

?- a(X), b(Y), ! , c(X, Y, Z).

При выполнении этого запроса, если подцели a(X) и b(Y) окажутся успешными, интерпретатор пройдет через предикат !. После этого интерпретатор не сможет возвратиться назад к подцелям, стоящим перед !, и обязан использовать при выполнении подцели c(X,Y,Z) те значения X и Y, которые они получили при конкретизации. Если подцель c(X,Y,Z) окажется неуспешной при данных конкретизациях X и Y, то и весь запрос потерпит неудачу. Если предикат ! будет последней подцелью составного запроса, то это гарантирует получение только одного ответа на запрос;

2) предикат ! является подцелью правила. Тогда, если интерпретатор дойдет до этого предиката, то он не сможет вернуться назад для рассмотрения остальных фраз программы.

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

В соответствии с подходом к программе с позиций потока данных, множество ответов (выходной поток данных) вырабатывается в соответствии с внутренней структурой программы в результате выполнения запроса (аргументы запроса являются входным потоком). Назначение программы состоит именно в генерировании заданного множества ответов, а то, каким образом это достигается – не имеет значения. Рассмотрим тривиальный пример. Пусть спецификация множества ответов заключается в следующем: если номер отдела 100, то программа должна выдать имена служащих – Иванов, Петров. Простейшая программа, удовлетворяющая этой спецификации, будет состоять из фактов «служащий», имеющих своими аргументами фамилию и номер отдела. Тогда запрос «служащий(Х, 100)» приведет к генерированию требуемого множества ответов – фамилий служащих из этого отдела.

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

Еще один пример.

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

free(аргумент) – успешен, если аргументом является неконкретизированная переменная;

bound( аргумент) - успешен, если аргументом не является неконкретизированная переменная;

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

путешествие(москва, ленинград, поезд).

можно запрашивать(путешествие(X, Y, V),’введите вид транспорта: ’, V) :-

bound(X), bound(X).

найти или спросить(Zapros) :-

Zapros.

найти или спросить(Zapros) :-

можно запрашивать( Zapros, Podsk, Znach),

free(Znach),

write(Zapros), nl,

write(Podsk), read(Znach), assert(Zapros).

?- найти или спросить(путешествие(москва, ленинград, Т))

Т=поезд

?- найти или спросить(путешествие(москва, вашингтон, Т))

путешествие(москва, вашингтон, _0)

введите вид транспорта: самолет

Т=самолет

?- найти или спросить(путешествие(москва, вашингтон, Т))

Т=самолет

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

Работа с файловой системой.

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

Здесь F – имя файла в операционной системе MS DOS, N – внутреннее имя, выбранное программистом, которое будет использоваться при обращении к открытому файлу.

openread(N,F) – открывает файл для чтения;

openwrite(N,F) – открывает файл для записи;

openappend(N,F) – открывает файл для добавления записей в конец файла;

openmodify(N,F) – открывает файл и для чтения, и для записи.

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

filepos()

writedevice(N) – N – внутреннее имя файла, открытого при помощи одного из встроенных предикатов openwrite, openappend, openappend. Этот предикат соотносит файл с текущим устройством вывода, так что выходная информация, вырабатываемая при вызовах встроенных предикатов write или writef, пойдет в этот файл.

readdevice(N) - N – внутреннее имя файла, открытого при помощи встроенного предиката openread. Этот предикат соотносит файл с текущим входным устройством, так что информация, вводимая при любых обращениях к встроенным предикатам readchar, readln, readint, readreal, readterm будет поступать из этого файла.

closefile(N) - N – внутреннее имя открытого файла. Данный предикат закрывает файл.

deletefile(F)

existfile(F)

renamefile(F1,F2)

eof(N).

Представление знаний при помощи Пролога.

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

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

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

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

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

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

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

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

Семантические сети.

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

является(канарейка, птица).

является(кеша, канарейка).

летает(птица).

летает(Х):-

является(Х, У), летает(У).

цвет(канарейка, желтый).

цвет(Х, У):-

является(Х, Z), цвет(Z, У).

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

Фреймы.

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

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

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

trace включается отладчик (по желанию)( использовать <F10>)

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

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

include другой исходный файл

domains новые типы областей значений

лицо=symbol

смена= symbol

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

работает(лицо, смена)

predicates обязательно объявляет область каждого аргумента

знает(лицо,лицо)

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

знает(А, В).

clauses текст программы

работает(X, S),

работает(Y, S),

X<>Y.

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

char integer real string symbol file

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

domains

имя=symbol

сумма=integer

структура_клиент=клиент(имя, сумма, integer)

структура_дата=дата(integer, integer, integer)

predicates

сделка(структура_клиент, структура_дата)

clauses

сделка(клиент(смит,29,4), дата(87,4,22)).

Литература

1. Филд А., Харрисон П. Функциональное программирование. М., Мир, 1993.

1. Хендерсон П. Функциональное программирование. Применение и реализация. М., Мир, 1983.

2. Маурер У. Введение в программирование на языке Лисп. - М.: Мир, 1976.

3. Лавров С., Силагадзе Г. Автоматическая обработка данных. Язык Лисп и его реализация. - М.: Наука, 1978.

4. Хювенен Э., Сеппянен Й. Мир Лиспа. В 2-х т. - М.: Мир, 1990.

5. Морозов М.Н. Функциональное программирование - курс лекций (700Kzip).

2. Abelson H., Sussman G. Structure and Interpretation of Computer Programs. - MIT Press, Boston, 1986.

3. Дехтяренко И.А. Программирование в повествовательном наклонении.2003 http://www.softcraft.ru/paradigm/dp/dp01.shtml