Программирование на языке Пролог для искусственного интеллекта

Братко Иван

в качестве инфиксного оператора для построения списка по заданным голове и хвосту. Этот оператор мы можем объявить в программе, например, так:

:- op( 500, xfy, затем).

Список

[ войти, сесть, поужинать]

можно было бы тогда записать как

войти затем сесть затем поужинать

 затем ничего_не_делать

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

операции над списками, такие как

принадлежит ( X, L)

конк( L1, L2, L3)

удалить( X, L1, L2)

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

конк

транслируется на язык "затем — ничего_не_делать" следующим образом. Определение, которое мы использовали до сих пор, имеет вид

конк( [], L, L).

конк( [X | L1], L2, [X | L3] ) :-

 конк( L1, L2, L3).

В новой системе обозначений оно превращается в

конк( ничего_не_делать, L, L).

конк( X затем L1, L2, X затем L3) :-

 конк(L1, L2, L3).

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

• 

истина

соответствует пустому списку,

• 

&

 — оператор для соединения головы с хвостом, определяемый, например, как

:- op( 300, xfy, &)

Конъюнкция членов а, b, и с выглядела бы тогда как

а & b & с & истина

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

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

Упражнения

9.1. Определите отношение

список( Объект)

для распознавания случаев, когда

Объект

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

9.2. Определите отношение принадлежности к списку, используя систему обозначений, введенную в этой разделе: "затем — ничего_не_делать".

9.3. Определите отношение

преобр(

СтандСпис, Спис)

для преобразования списков из стандартного представления в систему "затем — ничего_не_делать". Например:

преобр( [а, b], а затем b затем ничего_не_делать)

ответ

9.4. Обобщите отношение

преобр

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

преобр

придется добавить два новых аргумента:

преобр( СтандСпис, Спис, Функтор, ПустСпис)

Примеры применения этого отношения:

?- пpeoбp( [а, b], L, затем, ничего_не_делать).

L = а затем b затем ничего_не_делать

?- преобр( [а, b, с], L, +, 0).

L = а+(b+(с+0) )

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

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

больше( X, Y)

означающее, что X больше, чем Y, независимо от того, что мы в действительности понимаем под "больше, чем". Если элементами списка являются числа, то отношение

больше

будет, вероятно, определено как

больше( X, Y) :- X > Y.

Если же элементы списка — атомы, то отношение

больше

может соответствовать алфавитному порядку между ними.

Пусть

сорт( Спис, УпорСпис)

обозначает отношение, в котором

Спис

 — некоторый список, а

УпорСпис

 — это список, составленный из тех же элементов, но упорядоченный по возрастанию в соответствия с отношением

больше

. Мы построим три определения этого отношения на Прологе, основанные на трех различных идеях о механизме сортировки. Вот первая идея:

Для того, чтобы упорядочить список

Спис

, необходимо:

• Найти в

Спис

два смежных элемента X и Y, таких, что

больше( X, Y)

, и поменять X и Y местами, получив тем самым новый список

Спис1

; затем отсортировать

Спис1

.

• Если в

Спис

нет ни одной пары смежных элементов X и Y, таких, что

больше( X, Y)

, то считать, что

Спис

уже отсортирован.

Мы переставили местами 2 элемента X и Y, расположенные в списке "не в том порядке", с целью приблизить список к своему упорядоченному состоянию. Имеется в виду, что после достаточно большого числа перестановок все элементы списка будут расположены в правильном порядке. Описанный принцип сортировки принято называть методом пузырька, поэтому соответствующая прологовская процедура будет называться

пузырек

.

пузырек( Спис, УпорСпис) :-

 перест( Спис, Спис1), !, % Полезная перестановка?