3.8. Хвостовая рекурсия и списки

В этом разделе методы хвостовой рекурсии будут использованы в программах, предназначенных для хранения и обработки данных о людях (см. гл. 2 и 3). Предположим, что необходимо хранить и уметь организовывать доступ к данным о людях, которые ежегодно оплачивают следующие счета: страховку за автомобиль, личную страховку, страховку за здание, лицензию на право пользования телевизором, налог на автомобиль и взносы за членство в клубе или какой-то профессиональной ассоциации. Любой человек может иметь счет по конкретной позиции, а может и не иметь. Нас будут интересовать месяц и число погашения счета и не будут - год и размер счета. Представляем все эти данные в виде табл. 3.3.

Таблица 3.3

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

Alan data ((2 ∅ 3) (9 6) (2 ∅ 3) ( ) ( ) ( ))

Colin data(( )()()() (22 11) (5 9))

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

1. Каковы имена людей, которые погасили все счета, и какова дата оплаты?
2. Какие счета погашены на текущий день?
3. Кто погасил счет данного типа и какова дата оплаты?
4. Кто не погасил счёт данного типа?
5. Кого необходимо предупредить о том, что счет по заданной позиции должен быть погашен в течение определенного числа дней?

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

X саг ins Y if

X data (Y|Z)

Идея еще одного метода заключается в помещении списка типов счетов в унарное отношение

Теперь необходимо связать тип счета с именем человека и датой оплаты. Это можно сделать, если удастся, в свою очередь, связать аргумент X списка счетов с аргументом списка данных определенной личности. Следующее отношение, использующее хвостовую рекурсию, позволяет связать аргументы, стоящие в списках на одних и тех же местах:

(X Y) match ((X|Z) (Y|х))

(X Y) match (x z)

Здесь первое нерекурсивное правило позволяет связать головы списков. Второе правило дает возможность связать между собой элементы списков, стоящие на одних и тех же местах. Определение отношения содержит хвостовую рекурсию, поскольку рекурсивное условие стоит последним в последнем правиле. С помощью отношения match (связать) можно получить множество упорядоченных пар аргументов; первым аргументом в каждой паре является член первого списка, вторым аргументом - связанный с членом первого списка член второго списка. Для проверки работы отношения используется следующий тест:

all (х у : Alan data z and bill X and (x y) match (z X))

[( ) (взнос за членство в клубе)]

В данном примере в виде упорядоченных пар печатаются даты оплат, произведенных Аланом, и связанные с ними названия счетов из списка счетов.

Упражнение 3.14

а. Составьте запрос, позволяющий определить имена вместе о названиями счетов и датами оплат.

б. Составьте запрос; аналогичный запросу, описанному в п. (а). Отличие заключается в том, что информация о счетах, по которым данный человек не платит, выводиться не должна.

Чтобы выполнить упражнение 3.14, а, можно использовать новое отношение pays (оплачивает):

X pays (Y on Z) if

(Y Z) match (x y)

и запрос

В ответ будет получено:

Alan (car ins) (20 3)

Alan (life ins) (20 3)

и т. д.

Если не надо печатать названий счетов, по которым данный человек не производит оплат, нужно следующим образом изменить отношение pays:

X pays (Y on Z) if

not(Y())match(x y)

т. е. в данном случае пустой список ( ) исключается из процесса сопоставления. Ниже приведен еще один вариант отношения, использование которого позволяет решить ту же задачу:

X pays (Y on Z) if

not Z EQ ()

В последнем варианте фигурирует отношение EQ. Напомним, что это отношение истинно в том случае, когда два аргумента, представляющие собой списки, полностью (включая порядок следования элементов) идентичны.

Упражнение 3.15

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

а) погашение которых произведено только что;

б) оплата по которым будет произведена в следующем месяце;

в) оплаты по которым будут произведены в оставшиеся дни текущего месяца.

Упражнение 3.16

Покажите, как отношение match можно использовать вместе-с отношением stat из разд. 3.3 для извлечения, во-первых, подсписков из основного списка и, во-вторых, информации из нужного подсписка. В данном случае дело облегчается тем, что каждый подсписок содержит три элемента. Предусмотрите случай, когда подсписки будут включать различное число элементов.

Прочитав эту главу, читатели должны понять, что список, или структура данных является довольно мощным средством программирования. Одно из достоинств Пролога заключается в том, что достаточно нескольких простых примеров для того, чтобы показать, как могут создаваться очень большие программы. Пролог-система позволяет добавлять столько дополнительных данных или дополнительных правил, сколько можно разместить в оперативной памяти. Кроме того, одну и ту же программу, написанную на Прологе, можно использовать для решения многих различных задач. Хотя уже было описано довольно много методов, позволяющих сопоставлять элементы, принадлежащие различным спискам, читателям не составит особого труда придумать свои собственные.

Долг программиста состоит в том, чтобы уметь создавать удобные для сопровождения хорошо документированные программы, легко поддающиеся расширению и удовлетворяющие требованиям гибкости. Кроме того, не надо забывать, что программист постоянно должен заботиться о быстроте работы программы и об экономном расходовании памяти. В связи с этим обратим внимание на использование оператора "/". Этот оператор позволяет за счет отсечения альтернативных вариантов эффективно управлять возвратом. Аналогично метод, основанный на применении хвостовой рекурсии при задании отношений, дает возможность ограничить рост стека. Настоятельно рекомендуем читателям использовать именно этот метод. В качестве образцов можно взять стандартные отношения микроПролога; для того чтобы посмотреть правила, определяющие, например, отношения ON и APPEND, достаточно ввести команды

LIST ON

LIST APPEND

Кроме того, можно распечатать тексты любых модулей, входящих в состав той или иной программной системы. Так, сервисная программа SIMPLE GOGTOUT из трех модулей: qtierry-mod, еrmess-mod, program-mod. Текст любого из них можно вывести на экран с помощью команды LIST. Напомним, что просмотр длинных программ можно приостановить нажатием клавиш SYMBOL SHIFT и А.