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

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

• пуста , либо

• состоит из головы и хвоста , причем хвост должен быть сам списком.

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

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

в качестве символа, обозначающего пустой список, и атом

затем

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

:- 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) )

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

больше( X, Y)

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

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

Если же элементы списка — атомы, то отношение большеможет соответствовать алфавитному порядку между ними.

Пусть

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

обозначает отношение, в котором Спис — некоторый список, а УпорСпис — это список, составленный из тех же элементов, но упорядоченный по возрастанию в соответствия с отношением больше. Мы построим три определения этого отношения на Прологе, основанные на трех различных идеях о механизме сортировки. Вот первая идея:

Для того, чтобы упорядочить список Спис, необходимо:

• Найти в Списдва смежных элемента X и Y, таких, что больше( X, Y), и поменять X и Y местами, получив тем самым новый список Спис1; затем отсортировать Спис1.

• Если в Списнет ни одной пары смежных элементов X и Y, таких, что больше( X, Y), то считать, что Списуже отсортирован.

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