Списки и процедуры их обработки (лекция)
ГБПОУ «Шадринский политехнический колледж»
Машиностроительное отделение
Списки и процедуры их обработки
(статья)
Подготовила Волосникова Лариса Владимировна,
преподаватель машиностроительного отделения ШПК
Шадринск 2014
Списки и процедуры их обработки.
Цель лекции:
1. Знакомство с использованием списков в Пролог-программах.
Задачи, необходимые для достижения цели:
1. Изучение рекурсивных процедур обработки списков.
2. Получение навыков работы по обработке списков.
3. Знакомство с преобразованием набора фактов в списки.
Литература:
1. Коуров В.Г. Интеллектуальные информационные системы и
программирование на языке «Prolog».-Шадринск, ШфМГОПУ, 2005.
2. Братко И. Программирование на языке Пролог для искусственного
интеллекта. Пер. с англ. – М.: Мир, 1990. – 560 с.
3. Стерлинг Л. Искусство программирования на языке Пролог. Пер. с
англ. / Л. Стерлинг, Э. Шапиро / – М.: Мир, 1990. – 225 с.
4. Ин Ц. Использование Турбо-Пролога. Пер. с англ. / Ц. Ин, Д. Соломин.
– М.: Мир, 1993. – 608 с.
П.1 Списки как рекурсивные структуры данных
Список - широко используемая структура данных, которую удобно
применять при рекурсивной обработке информации, состав и количество
которой изменяется в ходе процесса обработки.
Список - упорядоченная последовательность элементов, которая может
иметь произвольную длину. Элементами списка могут быть любые термы:
- константы
- переменные
- структуры, которые могут включать и другие списки.
Списки широко используются при создании баз данных и знаний,
экспертных систем, карт городов, программ на ЭВМ и математических
объектов (графы, формулы, функции).
Список - это либо пустой список (записывается в квадратных скобках []),
не содержащий ни одного элемента, либо структура, имеющая в своем
составе две компоненты: "голову" и "хвост" списка.
"Голова" и "хвост" списка являются компонентами функтора,
обозначаемого точкой. Например, список, состоящий из одного символьного
элемента "а" может быть записан в виде. ( а, [] ) и его представление в виде
дерева имеет следующую структуру:
Запись сложных списков с помощью функтора не удобна, поэтому в
Прологе используется иная форма записи, при которой элементы списка
заключаются в квадратные скобки и разделяются запятыми. Так для
рассмотренных примеров запись списков с использованием скобочной
формы записи будет иметь вид: [а] и [а, b, с], соответственно.
Непустой список можно рассматривать как состоящий из двух частей:
- первого элемента списка - головы списка,
- оставшейся части списка - хвоста списка.
Голова является элементом списка и это неделимое значение. Хвост - это
есть список, состоящий из всех элементов исходного списка, за исключением
первого элемента. Хвост может быть поделен и дальше на голову и хвост.
Выполняя аналогичные операции, этот процесс можно продолжать, пока
список не станет пустым. Из этого следует очевидный вывод, что список
является рекурсивной структурой данных.
В Прологе введена специальная форма для представления списка с
"головой" Х и "хвостом" Y, где для разделения Х и Y используется символ
вертикальной черты, т.е. [ Х |Y ].
Используя данный подход, список [а, b, с] можно записать как [a | [b, с]].
Здесь "а" - голова списка, первый его элемент, а [b, с] - '"хвост" списка, часть
списка, начинающаяся со второго элемента.
Итак, рассмотрев понятие списка, давайте сравним его с какой-либо
структурой языка Паскаль:
Множества, но порядок элементов в списке существенен и элементы
списка могут сколько угодно раз повторяться;
Массивы, но для списков нет необходимости заранее объявлять их
размер
П.2 Использование списков в Пролог-программах
Для использования списков в Пролог-программе необходимо следующее:
1. В разделе domains описать домен списка. Домен списка задается в
формате: <ИМЯ ДОМЕНА> = <ДОМЕН ЭЛЕМЕНТА>*
Например, домен списка, элементами которого являются целые числа,
описывается следующим образом:
domains
list_num=integer*
или
list_num=elem*
elem=integer
2. Описать работающий со списком предикат в разделе predicates, например:
predicates
num(list_num)
3. Ввести или создать в программе собственно список, т.е. задать список в
разделах goal или clauses.
Например: Напишем программу, которая содержит список времен года.
Наименование сезонов является данным строкового типа и представляет
собой домен элементов списка.
domains
list_sеason=string*
predicates
year(list_season)
clauses
year(["зима", "весна", "лето", "осень"]).
Рассмотрим запросы к предикатам, содержащим списковые структуры,
Для изучения правил формирования запросов к списковым структурам, а
также с целью изучения правил унификации переменных элементами списка
выполним ряд внешних запросов к программе:
1) "Каков весь список сезонов в году?" - year(X)
2) "Какой второй сезон в году?" - year([_,Х,_,_])
3) "Какие сезоны составляют вторую половину года?" - year([_,_|X])
или year([_ | [_|X]])
4) "Какой Вы надеетесь получить результат от запроса - year([X|Y])?
Итак, в задании 1 внешняя цель year(X) обеспечивала присвоение
переменной Х всего списка в целом. Напротив, цель year(_,Х,_,_) позволяла
извлечь из списка всего лишь один элемент. Однако, в этом случае,
требовалось точное знание числа элементов в списке. Если задать цель в виде
year([Х,Y]), то она не будет удовлетворена в виду несоответствия количества
элементов в списке и целевом утверждении.
Вместе с тем, возможность отделения от списка первого элемента
позволяет обрабатывать его отдельно вне зависимости от длины списка.
Причем, оставшийся хвост можно снова рассматривать как список, в котором
можно выделить первый элемент. Аналогичные отделения первого элемента
можно проводить до тех пор, пока весь список не будет исчерпан. Этот
рекурсивный подход составляет основу построения процедур обработки
списковых структур.
П.3 Простейшие процедуры работы со списками
Процедура в прологе - это совокупность предложений с головами,
представленными одинаковыми термами. Для обработки списков
используются типовые процедуры (которые мы рассмотрим далее на
примерах)
Для выполнения большинства операций над списками, таких как вывод
на печать элементов списка, определение принадлежности элемента списку,
деление списка на два, соединение списков и т.д., используется разделение
списка на хвост и голову. Для соответствующего предиката, как правило,
имеются два утверждения, одно из которых является рекурсивным правилом
обработки списка, а другое – граничное условие для завершения рекурсивной
обработки списков. Для пояснения методов обработки списков рассмотрим
несколько примеров.
1) Рассмотрим программу распечатки содержимого списка,
элементы которого могут быть целыми числами или
символьными строками:
domains
list1=integer*
list2=symbol*
predicates
print_list(list1)
print_list(list2)
clauses
print_list([]).
print_list([Head|Tail]):–write(Head), nl,
print_list(Tail).
goal
print_list([1,2,3,4]).
В данной программе предикат списка print_list() описан для двух типов
доменов, поэтому с его помощью могут обрабатываться списки, элементами
которых являются как целые числа, так и символьные строки. В программе
реализован рекурсивный метод обработки.
Первое правило программы print_list([]) описывает тот факт, что пустой
список не нужно печатать, оно же является условием выхода из рекурсии,
используемым во втором правиле – печать списка завершается тогда, когда
список пуст. Опишем работу программы.
Первоначально аргумент целевого внутреннего запроса
print_list([1,2,3,4]) сопоставляется с первым вариантом правила;
сопоставление терпит неуспех, так как [1,2,3,4]¹[]. Затем выбирается второй
вариант правила, здесь сопоставление завершается успехом и выполняется
операция – разделения целевого списка на голову и хвост. Результатом ее
является сопоставление Head=1 и Tail=[2,3,4]. Далее начинают
последовательно выполняться предикаты тела правила.
Первым в теле стоит стандартный предикат write(Head), который
выводит на экран значение переменной Head, в данном случае 1, затем
выполняется предикат nl – перевод строки и формируется рекурсивный
вызов print_list([2,3,4]). Снова обращение к первому варианту правила и
снова неуспех — [2,3,4]¹[], и снова успешное сопоставление со вторым
вариантом и т. д. В конечном итоге переменная Head становится равной 4, а
Tail=[], и теперь после рекурсивного вызова print_list([]) сопоставление для
первого варианта правила завершится успехом – []=[], этот вариант правила
не имеет рекурсии – он является фактом и интерпретируется Прологом как
цель достигнута и целевой запрос считается удовлетворенным.
2) Можно, используя рекурсивный вызов, легко посчитать длину
списка:
length([], 0).
length([X|L], N):-length(L, M), N = M+1.
1) Проверяет принадлежность элемента списку member(X, L). Если
X принадлежит L, то истина и ложь в противном случае.
С точки зрения декларативного смысла:
X принадлежит списку, если X совпадает с головой списка.
X принадлежит списку, если X принадлежит хвосту списка.
Можно записать:
member(X, [X|T]).
member(X, [H|T]) :-member(X, T).
С точки зрения процедурного смысла - это рекурсивная процедура.
Первое предложение терминальное условие. Когда хвост будет равен []
проверка остановиться. Второе предложение рекурсивное. Сокращение
списка происходит за счет взятия хвоста (хвостовая рекурсия).
2) Соединение двух списков: append (L1, L2, L3), где L1 и L2 -
списки, а L3 - их соединение.
Для определения процедуры append используем два предложения:
Если присоединить пустой список [] к списку L, то получим список L.
append([], L, L).
append([X|L1], L2, [X|L3]):- append(L1, L2, L3). Если присоединить не
пустой список [X|L1] к списку L2, то результатом будет список [X|L3],
где L3 получаeтся соединением L1 к L2 : |X| L1 | L2 |
С точки зрения процедурной семантики
первое предложение - терминальное условие,
второе - рекурсивное с хвостовой рекурсией.
Рассмотрим примеры применения
?-append([a], [b, c], L). L=[a, b, c]
?-append([a], L, [a, b, c]). L=[b, c]
?-append(L, [b, c], [a, b, c]). L=[a]
Можно использовать для разбиения
?-append(L1, L2, [a, b, c]). L1=[] L2=[a, b, c];
L1=[a] L2=[b, c];
L1=[a, b] L2=[c];
L1=[a, b, c] L2=[]
Можно использовать для поиска комбинаций элементов.
Например можно выделить списки слева и справа от элемента
?-append(L, [3|R], [1, 2, 3, 4, 5]). L=[1, 2] R=[4, 5]
Можно удалить все, что следует за данным элементом и этот
элемент тоже:
?L1=[a, b, c, d, e], append(L2, [c|_], L1). L1=[a, b, c, d, e] L2=[a, b]
Можно определить процедуру, выделяющую последний элемент в
списке:
last(X, L):-append(_, [X], L).
3) Процедура reverse обращает список.
Пустой список после обращения - пустой. reverse([], []).
Обратить список [X|L1] и получить список L2 можно, если обратить
список L1 в L3 и в хвост ему добавить X
reverse([X|L1], L2):-reverse(L1, L3),
append( L3, [X], L2).
П.4 Компоновка данных в список
Часто при работе с базами данных встает задача преобразования
структур исходных отношений для выполнения тех или иных операции над
ними. Одной из таких задач является выбор данные ж базы в список для
последующей обработки.
В составе Турбо-Пролога для этих целей предусмотрен
стандартный предикат findall (найти_все). Данный предикат вычисляет все
ответы на запрос и возвращает их в виде списка. Синтаксис этого предиката
имеет вид:
findall( Var, Predicat, List_name) ,
где List_name - имя переменной выходного списка ответов на запрос,
Predicat - запрос с переменными, записанным в виде некоторого
предикатного выражения
Var - объект предикатного выражения Predicat_expression,
определяющий структуру элемента списка List_name.
Для пояснения использования данного предиката для преобразования
структур данных рассмотрим пример: имеем базу данных work(),
описанную соответствующим предикатом и заданную набором фактов:
фамилия сотрудника, отдел и премия. Требуется сформировать список
фамилий сотрудников 101 отдела.
domains
otdel, premia=integer
name=string
list_worker=name*
predicates
work(name, otdel, premia)
clauses
work( "Петров", 101, 500 ).
work( "Павлов", 211,400 ).
work("Сидоров",101,300).
work( "Иванов". 101,200).
Так как обработка фактов производится всегда в том порядке, как
они заданы в программе, то могут возникнуть неудобства, если нужно будет
сортировать, упорядочивать и т.д. фамилии сотрудников. Для этих целей
удобнее использовать списковые структуры организации данных.
Для этого требуется описать структуру этого списка в секции domains и
использовать предикат findall в следующем виде:
findall( Name, work(Name,101,_), List_Name), здесь Name является
свободной переменной для значений фамилий, которые удовлетворяют
запросу в виде предикатного выражения work(Name,101,_). Кроме того,
переменная Name определяет, что элементами списка List_Name будут
фамилии. В результате выполнение предиката findall список List_Name будет
содержать фамилии всех служащих 101 отдела.
