Лабораторная, работа 6
Списки и процедуры их обработки
Цель работы:
- Знакомство с использованием списков в Пролог-программах.
- Изучение рекурсивных процедур обработки списков.
- Получение навыков работы по обработке списков.
- Знакомство с преобразованием набора фактов в списки.
1. Списки как рекурсивные структуры данных
Список - широко используемая структура данных, которую удобно применять при рекурсивной обработке информации, состав и количество которой изменяется в ходе процесса обработки.
Список - упорядоченная последовательность элементов, которая может иметь произвольную длину. Элементами списка могут быть любые термы:
- константы
- переменные
- структуры, которые могут включать и другие списки.
Списки широко используются при создании баз данных и знаний, экспертных систем, карт городов, программ на ЭВМ и математических объектов (графы, формулы, функции).
Список - это либо пустой список (записывается в квадратных скобках [] ), не содержащий ни одного элемента, либо структура, имеющая в своем составе две компоненты: "голову" и "хвост" списка.
"Голова" и "хвост" списка являются компонентами функтора, обозначаемого точкой. Например, список, состоящий из одного символьного элемента "а" может быть записан в виде. ( а, [] ) и его представление в виде дерева имеет следующую структуру:
Рассмотрим еще один пример. Пусть имеется список, состоящий из трех символьных данных 'а', 'b', и 'с', который можно записать в виде: ( а, . ( b, . (с, []) ) ) или представить в виде бинарного дерева, структура которого приведена справа:
(функтор) /\
/ | / \
/ | a / \
/ | / \
a [] b / \
(голова) (хвост) c []
Запись сложных списков с помощью функтора не удобна, поэтому в Прологе используется иная форма записи, при которой элементы списка заключаются в квадратные скобки и разделяются запятыми. Так для рассмотренных примеров запись списков с использованием скобочной формы записи будет иметь вид: [а] и [а, b, с], соответственно.
Непустой список можно рассматривать как состоящий из двух частей:
- первого элемента списка - головы списка,
- оставшейся части списка - хвоста списка.
Голова является элементом списка и это неделимое значение. Хвост - это есть список, состоящий из всех элементов исходного списка, за исключением первого элемента. Хвост может быть поделен и дальше на голову и хвост.
Выполняя аналогичные операции, этот процесс можно продолжать, пока список не станет пустым. Из этого следует очевидный вывод, что список является рекурсивной структурой данных.
В Прологе введена специальная форма для представления списка с "головой" Х и "хвостом" Y, где для разделения Х и Y используется символ вертикальной черты, т.е. [ Х фY ].
Используя данный подход, список [а, b, с] можно записать как [a ф [b, с]]. Здесь "а" - голова списка, первый его элемент, а [b, с] - '"хвост" списка, часть списка, начинающаяся со второго элемента.
2. Использование списков c Пролог-программах
Применение списков в программе отражается на трех ее разделах. Домен списка должен быть описан в секции domains, а работающий со списком предикат - в секции predicates. Наконец, нужно задать сам список в секции clauses или goal. Рассмотрим пример простой программы, использующей в своем составе список.
/* программа 13_1 */
- domains
- list_sеason=season*
- season=string
- predicates
- year(list_season)
- clauses
- year(["зима", "весна", "лето", "осень"])
Эта программа содержит список времен года. Наименование сезонов является данным символьного типа и представляет собой домен элементов списка. Отличительной чертой в описании списка является наличие символа звездочки (*) после имени домена элементов
Описание предиката ничем не отличается от обычного, когда в скобках после его имени указывается набор аргументов. Запросы к предикатам, содержащим списковые структуры, могут быть как внешними, так и внутренними. Для изучения правил формирования запросов к списковым структурам, а также с целью изучения правил унификации переменных элементами списка выполним ряд внешних запросов к программе.
Задание 1.
Загрузите программу 13_1 и введите ряд запросов, анализируя получаемый результат:
"Каков весь список сезонов в году?" - year(All)
"Какой второй сезон в году?" - year([_,Х,_,_]) или year([_,Xф_])
"Какие сезоны составляют вторую половину года?" - year([_,фX]) или year([_ ф [_фX]])
"Какой Вы надеетесь получить результат от запроса - year([XфY])?
Придумайте еще несколько запросов, введите их в программу. Результаты диалога с ЭВМ привести в отчете по работе.
Рассмотрим еще три примера программ. Программа 13_2 покалывает возможность использования в предикатах списковых структур совместно с другими доменными структурами (предикат office содержит целочисленный и списковый домены).
/* программа 13_2 */
- domains
- number=integer
worker=string
list_worker=worker*
- predicates
- office(number,list_worker)
- clauses
- office(101,["Петров", "Сидоров", "Иванов"]).
office(211,[ "Павлов" ]).
/* программа 13_3 */
- domains
- number,salary=integer
name=string
member=worker(name,salary)
list_worker=member*
- predicates
- office(number,list_worker)
- clauses
- office(101,[ worker("Петров", 500), worker( "Сидоров",300), worker("Иванов", 200) ]).
office(211,[ worker("Павлов", 400) ]).
/* программа 13_4 */
- domains
- name = string
list_worker = name*
number = integer
office == office( number , list_worker )
list_office = office*
- predicates
- all_office( list_offlce )
- clauses
- all_office( [office(101,["Петров","Сидоров","Иванов"] ), office(211,["Павлов"]) ]).
Программа 13_3 иллюстрирует тот факт, что элементами списка могут быть не только стандартные домены, но и любые, определяемые пользователем составные структуры. Так, например, в данной программе элементами списка list_worker являются экземпляры структуры worker(name,salary).
Наконец программа 13_4 демонстрирует, что элементами списковых структур могут являться и сами списки. Так, элементом списка list_office является структура office(number , list_worker), одним из аргументов которой является список.
Следует особо отметить, что вес три программы служат для описания и хранения баз данных одной и той же предметной области. При этом логические структуры храпения информации существенно различаются. Использование списковых и составных структур существенно расширяет возможности проектирования и использования логических моделей данных.
Задание 2.
Тщательно разберитесь со структурной организацией каждой из программ, загрузите их в ЭВМ и введите ряд запросов.
По программе 13_2:
"Кто работает в 101 отделе?" - office(101,All)
"Кто начальник (первый по списку) 101 отдела?" - office(101,[Nп_])
"Какие есть отделы в фирме?" - office(X,_)
"Каков состав всей фирмы?" - office(_.L)
По программе 13_3:
"Кто зам. (2-ой по списку) 101 отдела?" - office(101,[_,worker(X,_)п_])
"Какие оклады у начальников отделов?" - office(_,[worker(X,Y)п_])
По программе 13_4:
"Кто входит в совет директоров (первое подразделение в составе фирмы)?" - all_office([office(_,X)п_])
Придумайте еще несколько запросов, введите их в программу. Результаты диалога с ЭВМ привести в отчете по работе. Попробуйте графически изобразить схемы логических моделей предметной области для каждого из вариантов программы.
3. Простейшие процедуры работы со списками
В задании 1 внешняя цель year(All) обеспечивала присвоение переменной All всего списка в целом. Напротив, цель year(_,Х,_,_) позволяла извлечь из списка всего лишь один элемент. Однако, в этом случае требовалось точное знание числа элементов в списке. Если задать цель в виде year([Х,Y]), то она не будет удовлетворена в виду несоответствия количества элементов в списке и целевом утверждении.
Вместе с тем, возможность отделения от списка первого элемента позволяет обрабатывать его отдельно вне зависимости от длины списка. Причем, оставшийся хвост можно снова рассматривать как список, в котором можно выделить первый элемент. Аналогичные отделения первого элемента можно проводить до тех пор, пока весь список не будет исчерпан. Этот рекурсивный подход составляет основу построения процедур обработки списковых структур.
Рассмотрим одну из простейших процедур обработки списков, обеспечивающую последовательный доступ к элементам списка и вывод их на экран дисплея. Пример ее описания и применения приведен в программе 14_1.
Процедура print_Iist() включает два правила. Первое - это факт, определяющий граничное условие рекурсивной процедуры, т.е. конец вывода элементов списка, если он пуст.
Второе правило обеспечивает разделение списка на голову и хвост, вывод первого элемента
/* программа 14_1 */
- domains
- list_season=season*
season=string
- predicates
- year(list_season)
print_list(list_season)
- goal
- year(L), print_list(L).
- clauses
- уеаг(["зима", "весна", "лето", "осень"]).
print_list([]).
print_list([XпY]):- write(X), nl, print_list(Y).
списка на экран дисплея, перевод курсора на новую строку и рекурсивный вызов этого же правила, но уже применительно к хвостовой части списка. В общем случае это правило записывается следующим образом
print_list([]):- L=[XпY], write(X), nl, print_list(Y).
но принимая во внимание тот факт, что Пролог сопоставляет с целью заголовок правила прежде, чем пытается согласовать его тело, возможна более короткая запись этого правила, приведенная в программе 14_1.
В программе 14_1 используется внутренняя цель, состоящая из двух подцелей. Первая из них обеспечивает формирование списка наименований времен года на основе имеющейся в БД информации. Вторая обеспечивает вывод сформированного списка на экран дисплея. __
/* программа 14_2 */
- domains
- number,salary=integer
name=string
member=worker(name,salary)
list_worker=member*
- predicates
- office(number,list_worker)
print_list(list_worker)
show_workcr
- clauses
- show_worker:- makewindow(l,7,15,"Служащие",5,10,12,30), cursor(2,l), write(" Введи номер отдела -> "), readint(Otd), office(Otd,L), print_list(L), readchar(_).
office(101,[worker("Петров", 500), worker("Сидоров" ,300), worker("Иванов", 200) ]).
office(211,worker("Павлов", 400) ]).
print_list([]).
print_list([XпY]):- write(X),nl, print_list(Y).
Задание 3.
Доработайте программу 13_1 до 14_1 и запустите на выполнение. Используя trace print_list(), познакомьтесь с процессом деления списка в процессе выполнения рекурсии.
Однако, внутренняя цель программы ограничивает возможные действия по модификации данных в базе: добавлению, поиску, исключению и т.д.
В этих условиях, для вывода элементов списка на экран предпочтительнее ввести новый предикат и определить для него правила, в соответствии с которыми осуществляется поиск и вывод требуемых данных из базы.
Пример такого подхода реализован в программе 14_1, с использованием предиката show_worker.
Задание 4.
Доработайте программу 13_3 до 14_2, разберитесь в ней и запустеть на выполнение.
4. Процедуры обработки списков
Списки можно применять для представления множеств, хотя и есть некоторое различие между этими понятиями. Порядок элементов множества не существенен, в то время как для списка этот порядок имеет значение. Кроме того, один и тот же объект R списке может встретиться несколько раз. Однако, наиболее используемые операции над списками аналогичны операциям над множествами. Это проверка объекта на принадлежность множеству, объединение двух множеств, удаление из множества некоторого объекта.
Принадлежность к списку. Представим отношение принадлежи гости о виде member(R.L), где R - терм, a L - список. Цель member(R,L) истинна, если терм R встречается в L. Задача проверки вхождения терма в список формулируется в виде:
Граничное условие: Терм R содержится в списке, если R есть голова списка L.
Рекурсивное условие: Терм R содержится в списке, если R принадлежит хвосту L.
Один из вариантов Пролог-процедуры можно представить в следующем виде:
member(R,L):-L=[HпT], H=R.
member(R,L):- L=[HпT], member(R,T).
Цель L==[HпT] в теле обоих правил служит для того, чтобы разделить список L на голову и хвост. Можно улучшить процедуру, если учесть тот факт, что Пролог сначала сопоставляет с целью заголовок правила, а затем пытается согласовать его тело. Тогда улучшенный вариант этой же процедуры может быть записан в виде:
member R, [R п_]),
member R,[_ п Т ]) :- member(R, Т).
Использование анонимных переменных (_) вызвано тем, что при применении первого правила нас не интересует хвост списка, а при применении второго - голова списка.
В качестве примера рассмотрим работу процедуры при выполнении цели:
member(d,[a,b,d,c]).
Цель начинает сопоставляться с первого правила, но так как d не сопоставимо с а, то происходит откат ко второму правилу.
Переменная Т получает значение [b.d.c], и порождается цель: member(d,[b,d,c]). Так как первое правило не сопоставимо, происходит повторное сопоставление второго правила и выделение нового хвоста списка.
Текущей целью становится member(d,[d,c]). Использование первого правила приводит к тому, что проверяемый элемент d сопоставляется с головой списка. [d,c]. Первое правило становится истинным, т.е. цель достигнута.
Если исходная цель member(d,[a,b,c,e]), то процесс сопоставления со вторым правилом будет рекурсивно повторяться до тех пор, пока не будет достигнута цель member(d,[]). Ни одно из правил не сопоставимо с этой целью и, поэтому исходная цель оказывается ложной.
Соединение двух списков. Для соединения двух списков определим отношение append(L1,L2,L3), где L1 - исходный список, L2 - присоединяемый (добавляемый) список, a L3 - список, получаемый при их соединении. Задача соединения списков формулируется следующим образом:
Граничное условие: Присоединение списка L2 к [] дает тот же список L2.
Рекурсивное условие: Список L2 присоединяется к хвосту L1, а затем спереди добавляется голова L1.
Тогда непосредственно из постановки задачи можно написать процедуру вида: append([],L2,L3).
Однако, как и в предыдущем случае, append(L1,L2,L3):- L1=[HпT], воспользуемся тем, что Пролог сначала append(T,L2,X), сопоставляет с целью заголовок правила, а L3=[HпX]. затем пытается согласовать его тело. Тогда усовершенствованный вариант этой же процедуры будет записан в виде:
append( [ ], L2, L2 ).
append( [Н п L1 ], L2, [Н п L3]) :- append(L1, L2, L3).
На запрос append([a,b,c],[d,e],L) будет получен ответ L=[a,b,c.d,e], а на запрос append([a,b],[c],[a,c,d]) ответом будет "нет".
Данную процедуру можно также использовать для поиска в списке комбинации элементов, отвечающей некоторому условию, задаваемому в виде шаблона. Например, можно найти все месяцы, предшествующие данному, и все, следующие за ним, сформулировав такую цель:
Goal: append(X,["anp"пY],["янв","фев","март","апр","май","июнь"])
X=["янв","фев","март","апр"]
Y=["май","июнь"]
Удаление элемента. Для удаления элемента Х из списка L введем отношение delete(X,L,L1), где L1 - сокращенный список. Задача будет сформулирована в виде:
Граничное условие: Если Х - голова, то результатом удаления будет хвост списка.
Рекурсивное условие: Если Х находится в хвосте списка, тогда его следует удалить из хвоста списка.
delete( X, [X п Т], Т ).
delete(X,[YпТ],[Y,T1]):-delete(X, T, T1).
Получение п-ого терма из списка. Задача доступа к заданному номером элементу списка формулируется следующим образом:
Граничное условие: Первый терм в списке (HпT] есть Н.
Рекурсивное условие: N-й терм в списке [HпT] является (N-I)- Ым термом в списке Т.
term_in_list( [Н п _],1,Н ).
term_in_list([_пT], N, X ) :- M=N-1. term_in_list(T, M, X).
Определение длины списка" Задача формулируется следующим образом:
Граничное условие: Длина пустого списка равна нулю.
Рекурсивное условие: Длина списка [HпT] на единицу больше длины списка Т.
В предикате list_len второй аргумент принимает
list_len([],0).
list_len([_пT],Len):- list_len(T,Len1), Len = Len1+1.
значение равное длине списка. Если второй аргумент является связанной переменной, то идет проверка на ее совпадение с длиной списка.
Задание 5.
Используя любую из моделей описания предметной области списковыми структурами, разработать программу, позволяющую выполнять над списками все элементарные действия, процедуры которых приведены выше.
5. Компоновка данных в список
Часто при работе с базами данных встает задача преобразования структур исходных отношений для выполнения тех или иных операции над ними. Одной из таких задач является выбор данные ж базы в список для последующей обработки.
В составе Турбо-Пролога для этих целей предусмотрен стандартный предикат findall (найти_все). Данный предикат вычисляет все ответы на запрос и возвращает их в виде списка. Синтаксис этого предиката имеет вид:
findall( Variable, Predicat_expression, List_name) ,
где List_name - имя переменной выходного списка ответов на запрос,
Predicat_expression - запрос с переменными, записанным в виде некоторого предикатного выражения
Variable - объект предикатного выражения Predicat_expression, определяющий структуру элемента списка List_name
Для пояснения использования данного предиката для преобразования структур данных рассмотрим пример (программа 15_1).
/* программа 15_1 */
- domains
- number, salary=integer
name=string
list_worker=name*
- predicates
- work(name,number,salary)
- clauses
- work( "Петров", 101. 500 ).
work( "Павлов", 211,400 ).
work("Сидоров",101,300).
work( "Иванов". 101,200).
Имеем базу данных work(), описанную соответствующим предикатом и заданную набором фактов. Так как обработка фактов производится всегда в том порядке, как они заданы в программе, то могут возникнуть неудобства, если нужно будет сортировать, упорядочивать и т.л. фамилии сотрудников.
Для этих целей удобнее использовать списковые структуры организации данных.
Пусть для нашего примера требуется сформировать список фамилий сотрудников определенного отдела.
Для этого требуется описать структуру этого списка в секции domains и использовать предикат findall в следующем виде:
findall( Name, work(Name,101,_), List_Name),
Здесь Name является свободной переменной для значений фамилий, которые удовлетворяют запросу в виде предикатного выражения work(Name,101,_). Кроме того, переменная Name определяет, что элементами списка List_Name будут фамилии. В результате выполнение предиката findall список List_Name будет содержать фамилии всех служащих 101 отдела.
Задание 6.
Для программы 15_1 выполните внешний запрос по формированию списка сотрудников заданного отдела. Задайте запрос на формирование списка окладов некоторого отдела.
Приведенный пример показывает, что предикат findall обеспечивает фильтрацию, поиск и формирование списка данных, которые удовлетворяют условию поиска в БД. Однако, данный пример иллюстрировал только сам процесс поиска и преобразования данных, не связывая его с процессом обработки.
Рассмотрим еще один пример, который должен иллюстрировать тот случай, когда задача обработки данных определяет необходимость в преобразовании их структур.
/* программа 15_2 */
- domains
- number,salary=integer
name=string
list_salary=salary*
- predicates
- work(name,number,salary)
sum_list(list_salary,salary,integer)
show_sum
find_sum( number)
- clauses
- show_sum:-makewindow( 1,7.15, "Зарплата:",5, 10,12,30), cursor(2,1), write( "Введи номер отдела -> "), readint(Otd), find_sum(0td), readchar(_).
find_sum(0td):- findall(Many,work(_,Otd,Many),Lmany), sum_list(Lmany,Sum,Member), write("общий фонд : ",Sum),nl, write(" служащих : ",Member),nl, Ave=Sum/Member, write( "средняя з/п: ",Ave).nl.
sum_list([],0,0).
sum_list([HпT],Sum,Num):- sum_list(T,S,N), Sum=H+S, Num=N+l.
work("Петров",101,500). work("Павлов",211,400). work("Сидоров",101.300). work("Иванов", 101,200).
Пусть требуется на основе базы данных work() найти общий фонд зарплаты и среднюю зарплату каждого из отделов. Программа 15_2 решает эту задачу.
Предикат show_sum дает возможность ввести номер нужного отдела и обеспечить нужный расчет, обратившись к предикату find_sum().
Предикат find_sum() па основе фактов базы work() формирует список окладов сотрудников отдела - Lmany, вычисляет сумму элементов списка и их количество, выводит полученные данные вместе с вычисленным средним значением на экран.
Сумму элементов списка находит предикат sum_list. Он же подсчитывает число элементов в списке.
В предикате sum_list реализована рекурсивная процедура, аналогичная той, что была использована при описании процедуры поиска длины списка.
Задание 7.
Доработайте программу 15_2 так, чтобы до вывода итоговых данных по отделу R целом в окне экрана дисплея выводился список всех фамилий для сотрудников этого отдела.
6. Содержание отчета по лабораторной работе
Отчет по лабораторной работе должен содержать:
- Программы для заданий 1 и 2, запросы к ним и результаты их обработки.
- Текст программы обработки списков по заданию 5. Рекомендуется описание типовых процедур обработки списков организовать в виде отдельного программного файла, который мог бы подключаться к любой программе, работающей со списками.
- Полный текст доработанной программы 15_2 в соответствии с заданием 7.
- Результаты выполнения заданий 3, 4 и 6.