Список - это упорядоченный набор объектов - элементов списка, следующих друг за другом. Элементы списка в языке Турбо-Пролог должны принадлежать одному и тому же доменному типу. Объектами списка могут быть: целые числа, действительные числа, символы, символьные строки, структуры.
Совокупность элементов списка заключается в квадратные скобки, а элементы друг от друга отделяются запятыми. Примерами списков являются:
[10,24,1,8,385,0,8]
[0.4,67.43,986.01,914.5]
["ПЕТРОВ П.Р.","ИВАНОВ Б.О.","СИДОРОВ Т.К."]
Список может содержать произвольное число элементов (ограничением является объем доступной оперативной памяти). Список, не содержащий элементов, называется пустым списком и обозначается []. Обработка списков в Турбо-Прологе базируется на разбиении списка на голову - первый элемент в списке и хвост - остальную часть списка. Например, как показано в следующей таблице:
Список
Голова
Хвост
[1,2,3,4]
1
[2,3,4]
['а'.'b'.'с']
'а'
['bYc'l
["Курсант"]
"Курсант"
[ ]
[]
не определено
не определено
Наглядным представлением процесса разбиения списка на голову и хвост является графическое представление в виде бинарного (двоичного) дерева. Для списка [1,2,3,4] таким деревом будет следующее:
Для использования списков в Пролог-программе необходимо:
1) В разделе domains описать домен списка. Домен списка задается в формате:
= *
319
Например, домен списка, элементами которого являются целые числа, описывается следующим образом:
domains
list_num=integer*
или
list_num=elem*
elem= Integer
2) Описать работающий со списком предикат в разделе predicates, например:
predicates
num(list_num)
3) Ввести или создать в программе собственно список, т.е. задать список в разделах
Ниже приведены примеры внешних запросов к программе и получаемые при этом результаты:
Запрос
Результат
nате(Х)
Х= ["Петров П. Р.", "Иванов Б. О.", "Сидоров Т. К."].
name([_, Y, _])
Y="Иванов Б. О."
score([A,B,_,_,C])
A=1,B=3,C=9
При использовании в Пролог-программе списков с произвольным числом элементов используется метод разделения списка на голову и хвост. Этот метод обеспечивает рекурсивную обработку списка. Операция разделения списка на голову и хвост в языке Турбо-Пролог обозначается вертикальной чертой (|) и записывается в виде:
[Head | Tail]
Здесь: Head - переменная для обозначения головы списка; Tail - переменная для обозначения хвоста списка.
Пример 1. Рассмотрим программу распечатки содержимого списка, элементы которого могут быть целыми числами или символьными строками:
domains
Iist1=integer*
320
Iist2=symbol*
predicates
printjist(listl)
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([]) описывает тот факт, что пустой список не нужно печатать, оно же является условием выхода из рекурсии, используемым во втором правиле - печать списка завершается тогда, когда список пуст. Опишем работу программы.
Первоначально аргумент целевого внутреннего запроса printjist([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, a Tail=[], и теперь после рекурсивного вызова printjist([]) сопоставление для первого варианта правила завершится успехом - []=[], этот вариант правила не имеет рекурсии - он является фактом и интерпретируется Прологом как цель достигнута и целевой запрос считается удовлетворенным.
Пример 2. Рассмотрим Пролог-программу подсчета суммы произведений элементов двух векторов X и Y, представленных списками Х=[х1 ,х2,.. .хn] и Y=[y1 ,у2 ,.. ,уn]:
domains
vector=integer*
predicates
prod(vector, vector, integer)
clauses
prod([],[],0).
prod([X|Xs],[Y|Ys],S):-prod(Xs,Ys,Sp),
321
S=X*Y+Sp.
goal
prod([1,2,3],[7,8,9],Rest),white("Rest=",Res).
Предикат prod (...) является трехместным: первый аргумент - список X, второй - список Y и третий - сумма произведений списков. В разделе clauses описаны два варианта правила для этого предиката.
Первый вариант - утверждение о том, что сумма произведений элементов пустых списков равна 0. Второй вариант правила реализован с использованием хвостовой рекурсии. Выражение S=X*Y+Sp означает, что текущая сумма равна сумме произведений текущих элементов вектора и частичной суммы, полученной на предыдущих шагах вычислений.
Схематично действия при выполнении программы представлены в табл. 24.2. Рекурсивное правило описывает отсроченные вычисления - после рекурсивного вызова остается не выполненным хвост правила, копии которого помещаются в стек до тех пор, пока не произойдет сопоставление с первым вариантом правила. И после того, как это произойдет, частичная сумма Sp" получит значение 0 и все накопленные в стеке хвостовые вычисления будут выполнены в обратном порядке.
Таблица 24.2
Действия при выполнении программы
Вызов предиката
Подстановки
Хвостовые вычисления
Результаты вычислений
Prod([1, 2,3], [7,8,9], Res)
X=1, Y=7, Xs=[2,3], Ys=[8,9], Res=S
S=X*Y+Sp
S=1*7+43=50
Prod([2,3],[8,9],Sp)
X'=2, Y'=8, Xs'=[3], Ys'=[9], S=Sp
Sp=X'*Y'+Sp'
Sp=2*8+27=43
Prod([3],[9],Sp')
X"=3, Y"=9, Xs"=[], Ys"=[], Sp=Sp'
Sp'=X"*Y"+Sp"
Sp'=3*9+0=27
Prod([],[],Sp")
Xs"=[],Ys"=[], Sp"=0
Sp"=0
Ниже приведен текст Пролог-программы, в которой реализованы основные операции над списками целых чисел: создание списка, добавление элементов в список, распечатка содержимого списка, удаление элемента из списка, упорядочивание элементов в списке. В программе реализован оконный интерфейс и используется модель общения типа выбора из меню.