Очереди

Интересным применением разностных списков является организация очередей. Очередь – структура данных для хранения списков, используемая по принципу: «первым записан – первым считан». Голова разностного списка представляет начало очереди, хвост – ее конец, а объекты разностного списка – это элементы очереди. Очередь пуста, если пуст разностный список, т.е. голова и хвост тождественны.

Управление очередью отличается от управления описанным выше справочником. Рассмотрим отношение queue(S), предназначенное для обработки потока команд, представленных списком S. Существуют две основные операции с очередью – включение элемента в очередь и исключение элемента из очереди, представляемые структурами enqueue(X) и dequeue(X) соответственно, где Х –интересующий нас элемент.

В программе 15.11 эти операции реализуются абстрактно. Предикат queue (S) обращается к предикату queue (S,Q), где Q – первоначально пустая очередь. Предикат queue/2 является интерпретатором для потока команд включения и исключения. Он воспринимает каждую команду и соответственно изменяет состояние очереди. При включенииэлемента используется незаполненность хвоста очереди; производится конкретизацияего новым элементом и соответствующее обновление хвоста очереди. Понятно, что отношения enqueue и dequeue могут быть и неразвернутыми, что дает более выразительную и эффективную, однако более трудную для чтения программу.

queue(S) ¬

S – последовательность операций включения элементов в очередь и исключения элементов из очереди, представленных списком термов enqueue (Х) и dequeue(X).

queue(S) ¬ queue(S,Q\Q).

queue([enqueue(X)|Xs],Q) ¬

enqueue(X,Q,Q1),queue(Xs,Q1).

queue([dequeue(X)|Xs],Q) ¬

dequeue(X,Q,Ql),queue(Xs,Ql).

queuc([ ],Q).

enqueue(X.Qh\[X|Qt],Qh\Qt).

dequeue[X,[X | Qh]\Qt,Qh\Qt).

Программа 15.11. Выполнение операций над очередью.

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

queue([ ].Q) ¬ empty(Q).

Очередь пуста, если ее голова и хвост конкретизируются пустыми списками, выраженными фактом empty([ ] \[ ]). Логически для этого должно быть достаточно предложения empty (Х \ Х). однако из-за отсутствия в Прологе контроля на вхождение, рассмотренного в гл. 4, оно может быть удовлетворено ошибочно на непустой очереди, образующей некоторую циклическую структуру данных.

Продемонстрируем использование очередей для раскрытия списка в программе 15.12. Хотя этот пример до некоторой степени надуманный, он ясно показывает, как могут быть использованы очереди.

flatten (Xs,Ys) ¬

Ys – раскрытый список, содержащий элементы из списка Xs.

flatten(Xs,Ys) ¬ flatten_q(Xs,Qs\Qs,Ys).

flatten_q([X Xs],Ps\[Xs| Qs],Ys) ¬

flatten_q(X.Ps\Qs.Ys),flatten_q(X,[Q| Ps]\Qs,[X! Ys]) ¬

constant(X).X ¹ [ ],flatten_q(Q,Ps\Qs,Ys).

flatten._q([ ].[Q | Ps] \Qs,Ys) ¬

flatten q(Q.Ps\Qs,Ys).

flatten„q([ ].[ ]\[ ],[ ]).

Программа 15.12. Программа раскрытия списка с использованием очереди.

Основное отношение в программе flatten_q(Ls,Q,Xs), где Ls – список списков, подлежащий раскрытию, Q – очередь списков, ожидающих раскрытия, и Xs – список элементов в Ls. Первое предложение flatten/3 посредством отношения flatten/2 инициализирует пустую очередь. Базовой операцией являются включение в очередь хвоста списка и рекурсивное раскрытие головы списка:

flatten. q([X|Xs].Q,Ys) ¬enqueue(Xs,Q,Ql),flatten_q(X,Ql,Ys).

Явно pacкрывая отношение enqueue получим

flatten_q([X | Xs],Qh\ [Xs | Qt].Ans)¬

flatten_q(X.Qh\Qt,Ys).

Если элемент, подлежащий раскрытию, оказывается константой, он добавляется в выходную структуру, строящуюся сверху вниз, и некоторый элемент извлекается из очереди (при унификации с головой разностного списка) для последующего раскрытия в рекурсивном вызове отношения flatten_q:

flatten_q(X,[Q|Qh] \Qt,[X | Ys]) ¬ constant(X).X ¹ [ ],flatten_q(Q,Qh \,Qt,Ys).

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

flatten_q([ ].[Q | Qh],Qt,Ys) ¬ flatten_q(Q,Qh\Qt,Ys),

либо очередь оказывается пустой, и вычисления прекращаются.

Рассмотрим операционный смысл программы 15.11. В процессе предполагаемого использования очереди сообщения enqueue (X) передаются с определенными X, а deqiieue(X) – c неопределенными X. Пока в очередь включено больше элементов, чем из нее исключено, очередь ведет себя нормально; разность между головой очереди и ее хвостом дает элементы, содержащиеся в очереди. Однако, если число полученных команд исключения из очереди превышает число команд включения элементов в очередь, происходит интересное явление – содержимое очереди становится «отрицательным». Голова опережает хвост очереди, что приводит к появлению в очереди отрицательной последовательности неопределенных элементов.

Число таких элементов определяется числом избыточных операций исключения из очереди.

Интересно понаблюдать, как такое поведение согласуется с ассоциативностью присоединения разностных списков. Если очередь Qs \ [X1,X2,X3\ Qs], содержащая три неопределенных отрицательных элемента, присоединяется к очереди [а,b,c ,d,e\Xs]\Xs, состоящей из пяти элементов, то результатом присоединения будет очередь [d,e\Xs] \ Xs с двумя элементами, где отрицательные элементы Х1,Х2,ХЗ инфицируются с а,b,с.