Лебедева Н.С. Методическое пособие по программированию на Turbo Prolog
Подождите немного. Документ загружается.
11
Пример правила:
mother(X, Y): parent(X, Y), female(X).
Данное правило будет истинно, если:
1. Х является родителем Y
2. Х – женщина
В Турбо-Прологе факты и правила называются утверждениями.
Программа может содержать достаточно много правил, выраба-
тывающих различные заключения. Эффект введения правил точно такой
же, как если бы программа содержала больше фактов. Возможность
Турбо-Пролога выбирать нужные правила делает программу более
гибкой и мощной.
1.5. Цели
Вопрос – это средство извлечения информации из программы. С
помощью вопроса выясняется, выполнено ли некоторое отношение между
объектами. Вопрос к программе состоит из одного или более целевых
утверждений (целей). Если цель является фактом, таким как parent (tanja,
olja), то Турбо-Пролог отвечает True (истина) или False (ложь).
Если цель содержит переменные, то система либо выдает те
их значения, которые приводят к решению, если оно существует,
или сообщение No solutions (нет решений). Цель используется для
запуска процесса выполнения программы. Цель может состоять из
нескольких подцелей, разделенных запятыми (конъюнкция целей) или
точкой с запятой (дизъюнкция целей).
Например, А: – В, С
А – истина, если В – истина и С – истина
А: – В ; С
А – истина, если В – истина или С – истина
Конъюнкция связывает подцели сильнее, чем дизъюнкция. Турбо-
Пролог обрабатывает подцели слева направо, пытаясь сопоставить
подцели с фактами и правилами программы. Система совершает возврат
для повторного согласования некоторых подцелей, если последующая
подцель получает отказ. Пытаясь согласовать цель повторно, Турбо-
Пролог возобновляет поиск, начиная просмотр базы данных с утверж-
дения, непосредственно следующего за тем, которое обеспечивало
согласование цели ранее. Турбо-Пролог имеет внутренние
подпрограммы для выполнения сопоставления и связанных с ним
процессов, которые называются унификационными. Если одна из
подцелей несопоставима, то вся цель является неуспешной. Если все
подцели сопоставимы, то вся цель является успешной.
12
Цели бывают внутренние, которые являются кодом программы и
внешние, которые вводятся с клавиатуры. Внешняя цель программы
находит все решения для заданной задачи, внутренняя цель только
первое решение. Программы Турбо-Пролога с внешней целью называ-
ются интерактивными. После того как программа запущена, не
выполнится ничего полезного до тех пор, пока система не встретит цель
в программе, а при внешней цели приглашение goal: (цель)
1.6. Переменные
Логические переменные в программах Турбо-Пролога использу-
ются для обозначения неопределенных объектов. Переменные – это
цепочки, состоящие из букв, цифр и символов подчеркивания. Они
начинаются с прописной буквы или знака подчеркивания.
Если переменная встречается в предложении только один раз, то
нет необходимости давать ей имя. Можно использовать так называемую
“анонимную переменную”, которая обозначается “–”. Анонимная пере-
менная – переменная, используемая вместо поименованной переменной
в тех случаях, когда значение переменной не представляет интерес.
Если анонимная переменная встречается в цели программы, то ее
значение не выводится при ответе системы на поставленную цель.
Например:
parent(X, _).
В данной цели содержится вопрос об именах родителей, имена
детей обозначены через анонимную переменную.
Использование переменных в программах, написанных на Турбо-
Прологе отличается от использования переменных в традиционных
языках программирования. В этих программах переменная обозначает
неопределенный, но единственный объект, а не некоторую область
памяти. Лексический диапазон имени переменной – одно предложение.
Например, если имя переменной Х встречается в двух предложениях,
то оно обозначает две разные переменные.
Если переменная не имеет значения, то она неозначена или
неинициализирована (свободная). Неозначенная переменная не равна
нулю, или пробелу, не имеет значений равных “мусору” (какой бы мусор
не оказался в памяти, отведенной для переменной). Всякий раз, когда
переменная сопоставляется с константой, то получается значение этой
константы. Переменная вновь становится свободной, когда сопоста-
вление оказывается неуспешным или цель успешно вычислена.
13
2. Основы программирования на Турбо-Прологе
2.1. Структура программ на Турбо- Прологе
Программа, написанная на Турбо-Прологе может состоять из
следующих разделов:
domains
global domains
database
predicates
global predicates
goal
clauses
Каждый раздел имеет свое ключевое слово.
Раздел domains содержит описание пользовательских доменов,
которые описывают различные классы объектов, используемые в
программе.
Раздел global domains содержит описание пользовательских
доменов, которые используются при написании модульных программ в
нескольких модулях.
Раздел database содержит описание предикатов динамической
базы данных, которая используется в программе.
Раздел predicates содержит описание используемых
программой предикатов.
Раздел global predicates содержит описание предикатов,
которые используются в нескольких модулях.
Раздел goal содержит цель, которая может состоять из нескольких
подцелей. Программа должна содержать только одну цель.
Раздел clauses содержит факты и правила необходимые для
работы программы.
Если в программе отсутствуют глобальные домены и предикаты,
динамическая база данных, то отсутствуют в программе и
соответствующие разделы. Если не задать раздел goal, то система
будет каждый раз запрашивать цель. В любом месте программы можно
помещать комментарии, заключенные символами / * и * /.
14
2.2. Описание доменов
Турбо-Пролог имеет шесть встроенных типов доменов:
char – отдельный символ;
symbol – символьное имя, последовательность букв, цифр и знаков
подчеркивания, которая начинается со строчной буквы или
заключена в кавычки;
string – строки, последовательность символов, заключенная в кавычки;
integer – целое число в диапазоне от –32768 до 32767;
real – действительные числа в диапазоне от +1Е-307 до +1Е308;
file – имя файла.
Домены типа symbol хранятся в специально организованной
таблице в оперативной памяти для быстрого поиска, но это расходует
дополнительную память и требует дополнительное время.
Турбо-Пролог позволяет конструировать свои собственные типы
объектов из встроенных типов доменов.
Описание доменов происходит в разделе доменов по следующему
формату:
<имя домена> = <имя встроенного типа домена>
Например:
domains
title = symbol
author = symbol
year = integer
или
domains
title, author = symbol
year = integer
2.3. Описание предикатов
Предикаты описываются в разделе предикатов по следующему
формату:
<имя предиката> (<имя встроенного домена>,
<имя пользовательского домена>)
В скобках перечисляются домены аргументов предиката. Предикат
может не иметь аргументов и его описание будет состоять только из
имени. Допустимо повторное описание предиката с другими доменами
аргументов.
15
Например, два способа описания предиката book:
1.
predicates
book (symbol, symbol, integer)
2.
domains
title, author = symbol
year = integer
predicates
book (title, author, year)
Если программа состоит из нескольких модулей или использует
внешние процедуры, то необходимо организовать связи. Межмодульные
связи устанавливаются объявлением нужных предикатов и доменов
глобальными. Все аргументы глобальных предикатов должны быть
глобальными доменами или принадлежать стандартным типам доменов.
Имя предиката должно начинаться со строчной латинской буквы и
должно иметь не более 250 символов. Не допускаются пробелы в имени
предиката.
2.4. Сопоставимость термов
Одной из важных операций над термами является сопоставление.
Сопоставление в Турбо-Прологе соответствует некоторому действию в
логике, называемому унификацией (отождествлением). Сопоставление –
это процесс на вход которого подаются два терма, а он проверяет,
соответствуют ли эти термы друг другу. Если термы не
сопоставимы, то этот процесс имеет неуспех. Если же они сопоставимы,
то процесс находит конкретизацию переменных, делающую эти термы
тождественными, и завершается успешно.
Правило сопоставления термов
Даны два терма А и В:
1) если А и В – константы, то А и В сопоставимы только, если они
являются одним и тем же объектом;
2) если А – переменная, а В – произвольный объект, то они
сопоставимы, и А приписывается значение В. Наоборот, если В
– переменная, а А – произвольный объект, то В приписывается
значение А;
3) если А и В – структуры, то они сопоставимы, только если:
a) А и В имеют одинаковый главный функтор;
b) все их соответствующие компоненты сопоставимы.
16
2.5. Встроенные предикаты
Встроенные предикаты – предикаты исходно определенные в
Турбо-Прологе и обычно выполняют функции не связанные с
логическим выводом.
Предикаты ввода – вывода информации:
readint(X) – читает целое число с текущего устройства ввода;
readchar(X) – читает символьную переменную с текущего устройства
ввода;
readlln(X) – читает строку с текущего устройства ввода;
readchar(_) –ожидание нажатия произвольной клавиши;
write(X) – запись аргумента на текущее устройство вывода;
nl – перевод строки.
Например,
pr1: – readint(Х), nl, write(‘X=’,X).
Правило pr1 выполняет следующие действия: читает значение Х,
переводит строку, печатает 'X=' и значение Х
Арифметические предикаты:
+ – сложение;
– – вычитание;
* – умножение;
/ – деление;
mod – остаток от деления целых чисел;
div – целочисленное деление.
Математические функции:
sin(X) – синус;
cos(X) – косинус;
tan(X) – тангенс;
arctan(X) – арктангенс;
abs(X) – абсолютная величина;
exp(X) – экспонента;
ln(X) – натуральный логарифм;
log(X) – десятичный логарифм;
sqrt(X) – квадратный корень.
Примечание: в тригонометрических функциях угол задается в
градусах.
17
2.6. Предикат отрицания
Программа на Турбо-Прологе является совокупностью правил и
фактов, описывающих истинные утверждения. Ложные факты явно не
указываются, они просто опускаются, но используя предикат отрицания
можно иметь отрицательную информацию в программе.
not – предикат отрицания.
not(goal) – это выражение будет успешно, если не успешна цель и
наоборот, выражение неуспешно, если цель успешна.
Отрицание удобно для логического вывода некоторых фактов из
уже имеющихся в базе данных. Использование предиката not в
конструкции правила дает возможность ввести в программу элементы
логики.
Пример. Имеем перечень фруктов, написать правило, что Катя
любит все фрукты, кроме яблок.
fruits(apples).
fruits(banana).
fruits(oranges).
…
likes('Katja', X):=fruits(X), not(fruits(apples)).
Можно использовать предикат not для определения отношения
“различны” для переменных X и Y:
different(X, Y):– not(X=Y).
2.7. Операция ''=''
В Турбо-Прологе операция ''='' выполняет две функции:
1) сравнение двух термов;
2) сопоставление двух термов с конкретизацией переменных.
Какую из выше перечисленных функций выполняет операция ''='',
определяется в зависимости от того, являются ли значения термов
свободными или означенными.
Например, имеем выражение
oranges = oranges.
Это выражение может быть подцелью какого-нибудь правила. В данном
случае операция ''='' выполняет функцию сравнения, так как оба терма
известны и совпадают. Все выражение истинно и является успешным.
Рассмотрим следующее выражение
oranges = appels.
18
Это выражение ложно, так как термы имеют различные значения.
Рассмотрим подцель, которая содержит следующее выражение
X = oranges.
В данном случае операция ''='' выполняет функцию сопоставления
двух термов. Эта подцель присваивает переменной Х значение oranges
только в том случае, если переменная Х еще не была означена.
Для Турбо-Пролога не существенно, известно ли значение справа
или слева от ''=''; в любом случае переменная Х получает значение
oranges. Можно записать и
oranges = X.
В случае, если Х уже имеет значение, то это значение сравнивается
с константой appels. Если эти два значения одинаковы, то подцель
успешна; если они различны, то подцель неуспешна.
Работа операции ''='' проходит также как работа внутренних
унификационных подпрограмм при сопоставлении целей и подцелей с
фактами или правилами программы.
Рассмотрим пример, в котором переменная Count означена и
имеет значение 1. Тогда выражение
Count = Count + 1
будет ложно. Если необходимо использовать переменную в качестве
“счетчика”, надо ввести дополнительную неозначенную переменную
Count1:
Count1 = Count + 1.
Данное выражение, которое может быть подцелью, сгенериро-
ванной внутри Турбо-Пролога, является успешным.
2.8. Декларативный и процедурный смысл
программ
Различают два уровня смысла программы на Турбо-Прологе:
1) декларативный;
2) процедурный.
Декларативный смысл определяет, что должно быть
результатом работы программы.
Процедурный смысл определяет еще и как этот результат был
получен, т. е. как отношения реально обрабатываются системой.
Способность системы прорабатывать многие процедурные детали
самостоятельно считается одним из специфических преимуществ Турбо-
19
Пролога. Результаты работы программы определяются ее
декларативным смыслом.
Рассмотрим предложение
А: – В, С.
где А, В, С имеют синтаксис термов.
Декларативный смысл данного предложения:
А – истинно, если В и С истинны, или из В и С следует А.
Процедурный смысл данного предложения: чтобы решить задачу А,
сначала решить подзадачу В, а затем – подзадачу С, или чтобы достичь
А, сначала достичь В, затем С.
Таким образом, декларативный смысл программы определяет,
является ли данная цель истинной, и если – да, то при каких значениях
переменных она достигается.
Различие между декларативным и процедурным смыслом заклю-
чается в том, что процедурный смысл определяет не только логические
связи между головой предложения и целями в его теле, но еще и
порядок, в котором эти цели обрабатываются.
Декларативность позволяет понимать программу, не отслеживая
динамику ее выполнения, и является уникальной особенностью Турбо-
Пролога.
2.9. Структуры
Объект, представляющий другой объект или совокупность
объектов называется составным объектом или структурой.
Если объекты структуры относятся к одному и тому же типу
доменов, то такая структура называется однодоменной. Если объекты
структуры относятся к разным типам доменов – многодоменная.
Объекты могут быть константами, переменными или структурами.
Для того, чтобы объединить объекты в структуры, надо выбрать
функтор. Каждый функтор определяется двумя параметрами:
1) именем, синтаксис которого совпадает с именем предиката;
2) арностью – т. е. числом аргументов.
Например, рассмотрим структуру date
date(1, september, 2002),
где date – функтор, все аргументы данной многодоменной структуры
являются константами.
20
date(Day, september, 2002),
в данной структуре аргументами являются переменная и константы.
likes(
'
Katja
'
, fruits(banana, apples, oranges)),
likes – главный функтор, аргументы данной многодоменной структуры –
константа и структура.
Рассмотренную структуру в программе можно описать следующим
образом:
domains
personal_liking = fruits(type1, type2, type3)
type1, type2, type3 = symbol
predicates
likes(symbol, personal_liking)
Чтобы легче понять структуры, их обычно представляют в виде
дерева, в котором каждому функтору соответствует вершина, а компо-
нентам соответствуют ветви дерева. Каждая ветвь может указывать на
другую структуру, так что можем иметь структуры внутри структур.
Следующие примеры показывают, как можно использовать
структуры для представления геометрических объектов.
point(1,1)
segment(point(1,1), point(3,2))
tringle(point(3,1), point(5,3), point(5,1))
date
1
september
2002
likes
Katja
fruits
banana
apples orange
Рис. 2.1
Рис. 2.2
0 1 2 3 4 5
5
4
3
2
1
А
В
С
D
Е