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

Братко Иван

Lloyd J. W. (1984). Foundations of Logic Programming. Springer-Verlag.

Nilsson N. J. (1981). Principies of Artificial Intelligence. Tioga; Springer-Verlag.

Robinson A. J. (1965). A machine-oriented logic based on the resolution principle. JACM 12: 23-41. [Имеется перевод: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции. — В кн. Кибернетический сборник, вып. 7, 1970, с. 194–218.] 

Глава 3

Списки, операторы, арифметика

В этой главе мы будем изучать специальные способы представления списков. Список -

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

3.1. Представление списков

Список — это простая структура данных, широко используемая в нечисловом программировании. Список — это последовательность, составленная из произвольного числа элементов, например

энн

,

теннис

,

том

,

лыжи

. На Прологе это записывается так:

[ энн, теннис, том, лыжи ]

Однако таково лишь внешнее представление списков. Как мы уже видели в гл. 2, все структурные объекты Пролога — это деревья. Списки не являются исключением из этого правила.

Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом

[]

. Во втором случае список следует рассматривать как структуру состоящую из двух частей:

(1) первый элемент, называемый головой списка;

(2) остальная часть списка, называемая хвостом.

Например, для списка

[ энн, теннис, том, лыжи ]

энн

 — это голова, а хвостом является список

[ теннис, том, лыжи ]

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

.( Голова, Хвост)

Поскольку

Хвост

 — это список, он либо пуст, либо имеет свои собственную голову и хвост. Таким образом, выбранного способа представления списков достаточно для представления списков любой длины. Наш список представляется следующим образом:

.( энн, .( теннис, .( том, .( лыжи, [] ) ) ) )

На рис. 3.1 изображена соответствующая древовидная структура. Заметим, что показанный выше пример содержит пустой список

[]

. Дело в том, что самый последний хвост является одноэлементным списком:

[ лыжи ]

Хвост этого списка пуст

[ лыжи ] = .( лыжи, [] )

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

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

?- Список1 = [а, b, с],

 Список2 = (a, .(b, .(c,[]) ) ).

Список1 = [а, b, с]

Список2 = [а, b, с]

?- Увлечения1 = .( теннис, .(музыка, [] ) ),

 Увлечения2 = [лыжи, еда],

 L = [энн, Увлечения1, том, Увлечения2].

Увлечения1 = [теннис, музыка]

Увлечения2 = [лыжи, еда]

L = [энн, [теннис, музыка], том, [лыжи, еда]]

Рис. 3.1. Представление списка

[энн, теннис, том, лыжи]

в виде дерева.

Приведенный пример также напоминает вам о том, что элементами списка могут быть любые объекты, в частности тоже списки.

На практике часто бывает удобным трактовать хвост списка как самостоятельный объект. Например, пусть

L = [а, b, с]

Тогда можно написать:

Хвост = [b, с]

и

L = .(а, Хвост)

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

L = [а | Хвост]

На самом деле вертикальная черта имеет более общий смысл: мы можем перечислить любое количество элементов списка, затем поставить символ "

|

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

[а, b, с] = [а | [b, с]] = [a, b | [c]] = [a, b, c | [ ]]

Подытожим:

• Список — это структура данных, которая либо пуста, либо состоит из двух частей: головы и хвоста. Хвост в свою очередь сам является списком.

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

[ Элемент1, Элемент2, ... ]

или

[ Голова | Хвост ]

или

[ Элемент1, Элемент2, ... | Остальные]

3.2. Некоторые операции над списками

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