Анализ структуры термов
Все реализации Пролога содержат некоторое число системных предикатов, связанных со структурой термов.
Типовые предикаты – это унарные отношения, связанные с типом терма. Такие предикаты проверяют, является ли данный терм константой или структурой. Можно уточнить вид константы – является ли она целым числом или атомом. Рассмотрим четыре типовых предиката: integer/1, atom/1, constant/1 и compound/1. Список этих предикатов вместе с описанием приведен на рис. 9.1.
integer (X) ¬ Х – целое число.
atom(X) ¬Х – атом.
constant(X) ¬ Х – константа (целое число или атом).
compound(X) ¬Х – основной терм.
Рис. 9.1. Системные типовые предикаты.
Можно считать, что каждый типовый предикат, описанный на рис. 9.1, как бы определен бесконечной таблицей фактов: таблицей целых чисел – integer(0), integer(1), integer(-1),...; таблицей атомов в программе – atom(foo), atom(bar),...; таблицей функциональных символов в программе с переменными аргументами compound(отец (X,Y)), compound(сын(X,Y)),... Отношение constant определяется таблицей, являющейся объединением таблицы целых чисел и таблицы атомов. Это выражается двумя правилами:
|
|
constant(X) ¬ integer(X).
constant(X) ¬ atom(X).
Хотя в разных версиях Пролога предикаты реализуются по-разному, мы полагаем, что вычисления происходят так, будто предикаты заданы таблицами. Однако данные предикаты могут быть использованы лишь целями, имеющими конечное число решений. Если подобный предикат использовать в цели, имеющей бесконечное число решений, то возникнет сообщение об ошибке. Рассмотрим цель integer(Х)?. Если Х – целое число, то цель решится успешно; если Х – атом или структура, то решение цели безуспешно. Если X – переменная, то появится сообщение об ошибке. Эта ситуация аналогична вычислению арифметического выражения, содержащего переменную. Отметим, что большинство реализаций Пролога не учитывают ошибочные ситуации, и цель integer (X), где Х – переменная, приводит к безуспешным вычислениям.
Заманчиво использовать вопрос вида atom(X)? для получения списка всех атомов с помощью механизма возврата в системе. Однако подобный способ использования предиката atom недопустим.
Единственные термы не,рассматриваемые в наборе предикатов на рис. 9.1 переменные. Пролог содержит системные предикаты, связанные с переменными. Но способ использования таких предикатов существенно отличается от способа использования системных предикатов, описываемых в данной главе. Металогические предикаты (таково формальное название подобных предикатов) являются предметом рассмотрения следующей лекции.
Приведем пример применения типовых предикатов в программе, раскрывающей список списков. Отношение flatten(Xs,Ys) истинно, если Ys – список элементов, встречающихся в списке списков Xs. Элементы списка Xs сами могут быть элементами или списками, так что элементы могут находиться на любой глубине вложенности. Пример цели, принадлежащей значению программы flatten, – flatten([[a],[b,[c,d]],e][a,b,c,d,e]).
|
|
Простейший вариант программы flatten использует двойную рекурсию. Для раскрытия произвольного списка [X | Хs], где Х само может быть списком, раскрывается голова списка X, раскрывается хвост списка Xs и результаты соединяются:
flatten([X | Xs],Ys)¬
flatten(X,Ysl),flatten(Xs,Ys2),append(Ys1,Ys2,Ys).
Что является исходным случаем? Раскрытие пустого списка приводит к пустому списку. Для другого исходного случая следует использовать типовый предикат. Результат раскрытия константы приводит к списку, состоящему из константы
flatten (X,[X]) ¬ constant(X), Х ¹ [ ].
Условие constant(X) необходимо для того, чтобы данное правило не применялось в случае, когда Х – список. Полной программой flatten является программа 9.1 а.
flatten(Xs, Ys) ¬
Ys – список элементов, содержащихся в Xs.
flatten([X | Xs],Ys)¬
flatten(X,Ysl), flatten (Xs,Ys2),append(Ysl,Ys2,Ys).
flatten(X,[X]) ¬
constant (X),X ¹ [ ].
flatten([ ],[ ]).
Программа 9.1а. Раскрытие списка с помощью двойной рекурсии.
Хотя декларативный смысл программы 9.1а очевиден, она реализует не самый эффективный способ раскрытия списков. В худшем случае, которым является левое линейное дерево, число редукций, используемых в программе, квадратично зависит от числа элементов в результирующем списке.
Программа flatten, строящая результирующий список сверху вниз, несколько сложнее программы с двойной рекурсией. В ней используется вспомогательный предикат flatten(Xs,Stack,Ys). где Ys -раскрытый список, содержащий элементы из Xs, а стек Stack содержит списки, подлежащие раскрытию. Стек представляется списком,
При обращении к процедуре flatten/3 в процедуре flatten/2 устанавливается начальное значение стека – пустой список. Перечислим случаи, рассматриваемые в процедуре flatten/3. Общий случай раскрытие списка [Х | Xs], где Х - список. В этом случае список Xs помещается в стек и список Х раскрывается рекурсивно. Для распознавания списка используется предикат list(X), определяемый фактом list([X | Xs]):
flatten([X | Xs],S,Ys) ¬ list(X), flatten (X,[Xs | S),Ys).
Если голова списка является константой, отличной от пустого списка, то она добавляется к результирующему списку и рекурсивно раскрывается хвост списка:
flatten([X | Xs],S,[X | Ys])¬ constant(X), X ¹ [ ], flatten(Xs,S,Ys).
При достижении конца списка возможны две ситуации, зависящие от состояния стека. Если стек не пуст, то считывается элемент из вершины стека и вычисления продолжаются:
flatten([ ],[X | S],Ys) ¬ flatten (X.S.Ys).
Если стек пуст, то вычисления завершаются:
flatten([ ],[],[ ]).
Полностью программа представлена как программа 9.1б.
flatten (Xs.Ys) ¬
Ys - список элементов, содержащихся в Xs.
flatten(Xs,Ys)¬flatten(Xs,[ ],Ys).
flatten([X | Xs],S,Ys)¬
list(X),flatten(X,[Xs | S],Ys).
flatten([X | Xs],S, [X | Ys]) ¬
constant (X), X ¹ [ ],flatten(Xs,S,Ys).
flatten([ ],[X | S],Ys)¬
flatten(X,S,Ys).
flatten([ ],[ ],[ ]).
list([X | Xs]).
Программа 9.1б. Раскрытие списка с помощью стека.
Программа 9.16 демонстрирует основные приемы работы со стеком. Стеком управляет унификация. Объекты помещаются в стек при рекурсивных обращениях к рассматриваемому списку и извлекаются из стека при унификации с головой списка и рекурсивных обращениях к хвосту списка. Другое применение стеков описано в программах 14.13 и 14.15, моделирующих магазинный автомат. Заметим, что параметр стека является примером накопителя. Читатель может убедиться, что число редукций в данном варианте программы линейно зависит от размера результирующего списка.