Prolog

конкретизация предложений,

        вариант предложения

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

вычисление целевого утверждения Литература

Clocksin W. F. and Mellish С. S. (1981). Programming in Prolog. Springer-Verlag. [Имеется перевод: Клоксин У., Меллиш К. Программирование на языке Пролог. - М.: Мир, 1987.]

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 = [лыжи, еда]