ВУЗ:
Составители:
Программирование. Процесс составления программы на Прологе в основном схо-
ден с процессом построения теории в логике предикатов.
•
•
•
•
Программист анализирует значимые сущности, функции и отношения из прикладной
области и выбирает обозначения для них.
Программист семантически определяет каждую значимую функцию и каждое значи-
мое отношение. Для отношений указывается, какие конкретные их реализации дают
истину, а какие - ложь.
Программист аксиоматически определяет каждое отношение при помощи правил и
фактов Пролога. Аксиоматическое определение отношения будет удачным, если оно
отразит смысл семантического определения. Множеством аксиоматических определе-
ний всех значимых для заданной предметной области отношений является программа,
моделирующая структуру этой области.
Для выполнения запросов к множеству правил и фактов программист или пользова-
тель применяет интерпретатор языка Пролог. Совокупность, состоящую из запроса,
множества правил и фактов программы и интерпретатора языка, можно рассматривать
как алгоритм решения задач из прикладной области. При этом запрос, правила и факты
программы представляют собой начальные формулы алгоритма, а интерпретатор со-
держит правила преобразования этих формул. Интерпретатор играет роль активной
силы, которая выполняет выводы из правил программы и тем самым реализует или
развертывает отношения определенные правилами программы.
Р. Ковальский описывает сущность логического программирования фразой:
Алгоритм = Логика + Управление.
Подобно тому, как Лисп скрыл от программиста устройство памяти компьютера, Пролог
позволил ему не заботиться (без необходимости) о потоке управления в программе.
7.3 Оценка языка Пролог
При написании данного пункта, мы следуем мнению Н. Н. Непейводы[6].
Язык Пролог рекламируется как язык логического программирования. Программа
состоит из множества хорновских дизъюнктов, записываемых в виде
Q(t) :– P
1
(t
1
), P
2
(t
2
), …, P
n
(t
n
).
(жирным шрифтом выделены кортежи: на самом деле предикаты могут иметь любое чис-
ло аргументов).
Кроме того, в программе имеется цель вида
?– R
1
, …, R
k
.
Каждый шаг программы состоит в преобразовании цели путем ее унификации с одним из
дизъюнктов. Программа считается успешно завершенной, если в некоторый момент из це-
ли исчезают все предикаты. Программа может зафиксировать неудачу, если один из пре-
дикатов цели ни с одним из дизъюнктов программы не унифицируется. Естественно, что
может быть и промежуточный, но гораздо чаще встречающийся случай: программа не
может зафиксировать неудачу, а просто зацикливается либо переполняется из-за неогра-
ниченного удлинения выражений.
Эта схема могла быть реализована многими способами. Поскольку Пролог появил-
ся в самом начале 70-ых годов, был выбран способ, тогда находившийся на уровне, но
сейчас уже безнадежно морально устаревший
1
. Выбирается всегда первый член целевого
дизъюнкта и первый из унифицируемых с ним дизъюнктов программы.
Здесь возникла сложность, которая была удачно разрешена и составила одно из
важнейших достижений Пролога. Взяв первого кандидата, мы можем через несколько ша-
гов зайти в тупик, а решение было совсем рядом: надо было взять следующего. Тут рабо-
тает механизм возвратов (backtracking). Если фиксируется неудача, мы возвращаемся к
1
Впрочем, уже тогда можно было бы чуть дальше глянуть на уже имевшиеся достижения информатики, но,
как правило, больше одного удачного нововведения ни в одной принципиально новой системе не делается.
45
Страницы
- « первая
- ‹ предыдущая
- …
- 43
- 44
- 45
- 46
- 47
- …
- следующая ›
- последняя »
