Основы программирования на языке Turbo Prolog

Эта цель сопоставляется с рекурсивным правилом

culc_point(C1,C2,C3,Sum1,Sum2,Sum3), которое

1) запрашивает  точку;

2) вызывает pos_point(C1,C2,C3,X,Y,S1,S2,S3), возвращающую новые значения счетчиков S1, S2, S3;

3) вызывает  само себя с новыми текущими значениями счетчиков.

На протяжении всех этих вызовов последние три аргумента Sum1, Sum2, Sum3 остаются свободными переменными. Так продолжается до тех пор, пока не вводится точка (0,0).

Правило pos_point(_,_,_,0,0,_,_,_) дает отказ без возможности перехода на другое правило pos_point (комбинация !,fail), и рекурсивное правило culc_point дает отказ. Затем происходит переход на граничное условие culc_point(C1,C2,C3,C1,C2,C3).

Аргументы, предназначенные для конечных значений счетчиков, наконец, перестают быть свободными, — в них копируются текущие значения. После этого цель culc_point(0,0,0,Sum1,Sum2,Sum3) успешно согласуется, происходит печать ответов и выход из программы.

Упражнение 5.3.

Напечатать сумму ряда , вычисленную с заданной точностью eps при фиксированном значении x (сумму вычислить и восходящей, и нисходящей рекурсией).

ГЛАВА 6. СПИСКИ

1. ОСНОВНЫЕ ПОНЯТИЯ

СПИСОК — это простая структура данных, широко используемая в нечисловом программировании.

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

Турбо-Пролог позволяет выполнять со списком целый ряд операций. Их перечень включает:

— доступ к объектам списка,

— проверка на принадлежность к списку,

— добавление и удаление элемента,

— выделение подсписка,

— слияние двух списков,

— разделение списка на два,

— сортировку элементов списка.

Списки бывают удобны при создании баз знаний (баз данных), экспертных систем, словарей.

2. СПИСКИ И ТУРБО-ПРОЛОГ

Список является набором объектов ОДНОГО И ТОГО ЖЕ ДОМЕННОГО ТИПА. Объектами списка могут быть целые числа, действительные числа, символы, символьные строки и структуры.

Порядок расположения элементов является отличительной чертой списка; те же самые элементы, упорядоченные иным способом, представлеют уже совсем другой список. Порядок играет важную роль в процессе сопоставления.

Турбо-Пролог допускает списки, ЭЛЕМЕНТАМИ КОТОРЫХ ЯВЛЯЮТСЯ СТРУКТУРЫ. Если структуры принадлежат к альтернативному домену, элементы списка могут иметь разный тип. Такие списки используются для специальных целей, и их мы пока рассматривать не будем.

Совокупность элементов списка заключается в квадратные скобки ([]), а друг от друга элементы отделяются запятыми.

Примерами списков могут служить:

[1,2,3,6,9,3,4]

["YESTERDAY","TODAY","TOMORROW"]

Элементами первого списка являются целые числа, элементами третьего — символьные строки.

3. АТРИБУТЫ СПИСКА

Объекты списка называются элементами списка. Список может содержать произвольное число элементов, единственным ограничением является лишь объем оперативной памяти.

Количество элементов в списке называется его длиной.

Список может содержать всего один элемент и даже не содержать элементов вовсе:

["summer"]    []

Список, не содержащий элементов, называется ПУСТЫМ или нулевым списком.

Непустой список можно рассматривать как состоящий из двух частей:

(1) первый элемент списка — его ГОЛОВА,

(2) остальная часть списка — ХВОСТ.

Голова является элементом списка, хвост есть список сам по себе. Голова — это отдельное неделимое значение. Наоборот, хвост представляет собой список, составленный из того, что осталось от исходного списка в результате «усекновения головы».

В списке [4,3,6,100], например, головой является значение 4, а хвостом — список [3,6,100].

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

У пустого списка голова и хвост не определены.

4. ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ

Рассмотрим следующее утверждение:

number([66,84,12,32]).

Объектом предиката number является четырехэлементный список. Голова этого списка есть число 66, хвост — список [84,12,32]. Нумерация списка начинается с головы и заканчивается на его последнем элементе, числе 32.

Внутренним Турбо-Прологовским представлением этого списка является бинарное дерево (рис 6.1).

рис. 6.1

Функтор списка, number, является корнем этого дерева. От корня отходят две ветви. Левая заканчивается листом со значением 66. Правая ветвь кончается узлом, из которого расходятся еще две ветви. Левая кончается значением 84, правая опять разветвляется на две ветви. На левой из них располагается лист со значением 12, правая ветвится еще раз. Левая из этих ветвей ведет к листу со значением 32, правая заканчивается пустым списком.

Очередность, в которой элементы связаны друг с другом, начинается с корня дерева. Лист самой левой ветви дает первый элемент списка. Затем очередность при посредстве узла правой ветви переходит на следующую левую ветвь, на ее листе находится второй элемент списка, 84. Аналогично нумеруются и все остальные элементы вплоть до последнего, 32. Так как больше неупорядоченных элементов не остается, то дерево оканчивается ветвью с пустым списком.

Изображение в виде бинарного дерева бывает особенно полезным для нагядной интерпретации процесса возврата в виде направленного перебора ветвей дерева.

Упражнение 6.1.

1. Различаются  ли с точки зрения Турбо-Пролога  два таких списка:

[63,29,24,27,86]

[63,24,29,27,86]

2. Можно  ли назвать корректным следующий список:

student([”МГМА”,"Смирнов",”2204”,1995])

5. ПРИМЕНЕНИЕ СПИСКОВ В ПРОГРАММЕ

Для того чтобы использовать в программе список, необходимо описать предикат списка. Ниже приведены примеры таких предикатов:

num([1,2,3,6,9,3,4])

time(["YESTERDAY","TODAY","TOMORROW"])

В этих выражениях num и time представляют предикаты списков. Предикатам списков обычно присваиваются имена, которые характеризуют либо тип элемента (num), либо сами данные (time).

Введение списков в программу с необходимостью отражается на трех ее разделах. Домен списка должен быть описан в разделе domains, а работающий со списком предикат — в разделе predicates. Наконец, нужно ввести сам список; то есть, другими словами, его нужно задать где-то в программе: либо в разделе clauses, либо в разделе goal.

Покажем, как можно создавать в программе списки и как их использовать.

animals(["monkey","piton","lion","white eagle"])

Если этот список необходимо использовать в программе, то следует описать домен элемента списка; ему логично присвоить имя подобное name_animals.

Отличительной особенностью описания списка является наличие звездочки (*) после имени домена элементов. Так запись

name_animals *

следует понимать как список, состоящий из элементов домена name_animals.

Описание в разделе domains, следовательно, может выглядеть либо как

animals_list = name_animals *

name_animals = symbol

либо как

animals_list = symbol *

Домен animals_list является доменом списка элементов типа symbol.

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

animals(animals_list)

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

clauses

animals(["monkey","piton","lion","white eagle"]).

Пример использования списков приведен в программе 6.1 «Списки», в которую дополнительно включены два списка из целых чисел (домен integer*) и предикат num.

/* Программа 6.1 «Списки». Назначение:    */

/* демонстрация работы со списками.   */

domains

 

   animals_list = name_animals *

   name_animals = symbol

 

predicates

 

   animals(animals_list)       

   num(integer *)

 

goal

   L=[6,7,8],write(L),nl,

   animals(L1),write(L1),nl,

   num(L2),write(L2).

 

clauses

 

animals(["monkey","piton","lion","white eagle"]).

 

num[1,2,3,4]).

/*     Конец программы              */

Упражнение 6.1.

Адресуйте программе следующие внешние запросы:

animals(All).

animals([_,_,B,_]).

animals([B1,B2,_,_]).

num(All).

num([F,S,T,A]).

Поясним теперь работу программы при задании каждой из этих целей, это прояснит способ работы со списками в программах на Турбо-Прологе.

Заметим, что свободная переменная All представляет весь список в целом. Он рассматривается при этом как некое целое, элементы играют роль частей этого целого.

Что касается второй цели, animals([_,_,B,_]), то процесс сопоставления начинается с первого элемента. Первые три переменные в целевом утверждении являются анонимными,переменной B присваивается значение lion.

Третья цель, animals([B1,B2,_,_]), запрашивает первые два элемента списка. На выходе можно будет увидеть B1=monkey, B2=piton, т.е. значения первого и второго элементов списка.

6. МЕТОД РАЗДЕЛЕНИЯ СПИСКА НА  ГОЛОВУ И ХВОСТ

В программе 6.1 «Списки» для получения доступа к элементам списков были использованы внешние целевые утверждения. Задание цели в виде animals(All) обеспечивало присваивание переменной All всего списка в целом. Напротив, цель animals([_,_,B,_]) позволила извлечь из списка лишь один элемент. В этом случае, однако, требовалось точное знание числа элементов списка.

Турбо-Пролог, однако, позволяет отделять от списка первый элемент и обрабатывать его отдельно. Данный метод работает вне зависимости от длины списка, до тех пор, пока список не будет исчерпан. Этот метод доступа к голове списка называется

МЕТОДОМ РАЗДЕЛЕНИЯ СПИСКА НА ГОЛОВУ И ХВОСТ.

Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):

[Head|Tail]

Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка. (Для имен головы и хвоста списка пригодны любые допустимые Турбо-Прологом имена.)

Программа 6.2 демонстрирует использования метода разделения списка. Два списка описаны в ней: список целых чисел (имя домена — integer*) и список символических имен (домен animals_list). Правило print_list применяется для доступа к элементам обоих списков.

/* Программа 6.2 «Голова-хвост». Назначение:   */

/* разделение  списка на голову и хвост         */

domains

   animals_list = symbol *

 

predicates

 

   print_list(integer *)

   print_list(animal_list)

 

clauses

 

   print_list([]).

   print_list([Head|Tail]) :-

  write(Head),nl,

  print_list(Tail).

/*   Конец программы                 */

Программа 6.2 использует правило print_list для доступа к элементам списков. Так как предикат print_list определен для объектов обоих доменов, то это правило используется для работы как со списком number_list, так и списком animal_list.

Когда правило пытается удовлетворить внешнюю цель

print_list([4,-9,5,3])

то первый вариант правила, print_list[], дает неуспех, так как его объект является пустым списком. Напротив, введенный список соответствует объекту второго варианта предиката print_list([Head|Tail]). Переменной Head, следовательно, присваивается значение первого элемента в списке, 4, в то время как переменной Tail ставится в соответствие оставшаяся часть списка,  
[-9,5,3].

Теперь, когда выделен первый элемент списка, с ним можно обращаться так же, как и с любым простым объектом:

write(Head),nl

Так как хвост списка есть список сам по себе, значение переменной Tail может быть использовано в качестве объекта рекурсивного вызова:

print_list(Tail)

Процесс повторяется до тех пор, пока переменная Head не примет значение 3, а переменная Tail присвоится пустой список. Теперь при рекурсивном вызове print_list(Tail) значение Tail соответствует объекту правила

print_list([])

Этот вариант является граничным условием рекурсии, и цель считается удовлетворенной.

Рекурсивные правила для работы со списками просты, но вместе с тем и очень важны, ввиду их применимости в большинстве программ.

7. ПОИСК ЭЛЕМЕНТА В СПИСКЕ

Поиск элемента в списке является очень распространенной операцией. Поиск представляет собой просмотр списка на предмет выявления соответствия между элементом данных (объектом поиска) и элементом просматриваемого списка. Если такое соответствие найдено, то поиск заканчивается успехом. В противном случае поиск заканчивается неуспехом. Для сопоставления объекта поиска с элементами просматриваемого списка необходим предикат, объектами которого и явлются эти объект поиска и список:

member(3, [1,2,3,4,5])

Первый из объектов утверждения, 3, есть объект поиска. Второй — это список [1,2,3,4,5].

Для выделения элемента из списка и сравнения его с объектом поиска можно применить метод разделения списка на голову и хвост. Стратегия поиска при этом будет состоять в рекурсивном выделении головы списка и сравнении ее с элементом поиска.

Так же, как в программе «Голова-хвост», при рекурсии хвостом каждый раз становится новый список, голова которого присваивается переменной, сравниваемой с объектом поиска.

member(Head,[Head|_])

Этот вариант правила соответствует случаю, когда объект поиска совпадает с головой списка. Отметим, что хвост списка при этом присваивается анонимной переменной. Если объект поиска и голова списка действительно соответствуют друг другу, то результатом сравнения явится успех.

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

member(Head, [_,Tail]) :-

   member(Head, Tail).

При этом уже проверенный первый элемент списка ставится в соответствие анонимной переменной. Попытка удовлетворить рекурсивное правило member(Head,Tail) заставляет Турбо-Пролог представить хвост текущего, как новый самостоятельный список.