База-часть определений в которых не встречаются вызовы самого предиката.шаг-

Рекурсия – это второе средство для организации повторяющихся действий в Прологе. Рекурсивная процедура – это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некое условие, которое остановит рекурсию. Такое условие именуют граничным.

Примером рекурсивных вычислений есть узнаваемый метод вычисления факториала. Факториал числа N определяется в соответствии с методу:

  1. 1!=1
  2. N!=N*(N-1)!

Реализация этого метода на языке Пролог имеет таковой вид:
domains
N, F = real % Вещественный тип имеет больший диапазон
predicates
factorial( N, F )
clauses
factorial( 1, 1 ). % База рекурсии, ограничение вычислений
factorial( N, R ):– N 0, % Правило с рекурсией
N1 = N — 1,
factorial( N1, R1 ),
R = R1 * N.
goal
factorial( 8, F), write( F ). % Пример вычисления 8!

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

Вычисление частичных сумм последовательностей

Перечни в турбопрологе

Перечень — последовательность из произвольного числа элементов. Элементы перечня разделяются запятыми и заключаются в квадратные скобки. Любой перечень представляет собой:

  • или безлюдный перечень (атом []);
  • или непустой перечень — структуру, складывающуюся из двух

частей: первый элемент — голова (Head) перечня; второй

элемент — хвост (Tail) перечня.

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

[ Элемент1, Элемент2,…]

либо

[ Голова | Хвост ]

либо

[ Элемент1, Элемент2,… | Остальные].

Примерами перечней могут служить:

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

[3.2,4.6,1.1,2.64,100.2]

[День назад,Сейчас,на следующий день]

Количество элементов в перечне именуется его длиной. Перечень, не содержащий элементов, именуется безлюдным либо нулевым перечнем. Он обозначается так: []. Непустой перечень возможно разглядывать как складывающийся из двух частей: первый элемент перечня — его голова, и другая часть перечня — хвост. Голова есть элементом перечня, хвост имеется перечень сам по себе. Турбо-Пролог разрешает, например, делать над перечнями следующие операции: доступ к элементам перечня, диагностику на принадлежность к перечню, сортировку элементов перечня в порядке возрастания либо убывания.

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

domains

item = c (char); i (integer); s (string) /* c, i, s – функторыпредикатов */

item _list = item* /* домен перечней смешанного типа */

predicates

list (item _list)

clauses

list ([i (10), i (12), i (2000), s (“НГПУ – ИФМИЭО”), c (“N”)]).

Разглядим программу Птицыс применением перечней.

/* Программа: П т и ц ы. */

domains

bird_list = bird_name*

bird_name = symbol

predicates

birds(bird_list)

clauses

birds([ласточка,синица,чиж,воробей]).

Отличительной изюминкой описания перечня есть наличие звездочки (*) по окончании имени перечня элементов. Так запись bird_name* показывает на то, что это описание перечня, элементами кожный покров являются bird_name (птицы).

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

bird_list = bird_name*

bird_name = symbol

либокак

bird_list = symbol*

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

birds(bird_list)

Сам перечень присутствует в разделе утверждений clauses:

birds([ласточка,синица,чиж,воробей]).

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

birds(All).

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

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

В программе Птицы чтобы получить доступ к элементам перечней были использованы внешние целевые утверждения. Задание цели в виде birds(All) снабжало присваивание переменной All всего перечня в целом. Наоборот, цель birds([_,_,_,B]) разрешила извлечь из перечня только один элемент. В этом случае, требовалось правильное знание числа элементов перечня. Для работы со перечнями, протяженность которых заблаговременно малоизвестна, употребляется способ разделения перечня на хвост и голову. Этот способ трудится независимо от длины перечня, , пока перечень не будет исчерпан. Операция деления перечня на хвост и голову обозначается при помощи вертикальной черты (|):

[Head|Tail].

Head тут есть переменной для обозначения головы перечня, переменная Tail обозначает хвост перечня.

Программа Голова — хвост демонстрирует применение способа. Это — программа печати введенных пользователем символов целых и списков чисел.

Перечни в лиспе

Язык функционального программирования Лисп (Lisp) был создан во второй половине 50-ых годов двадцатого века Джоном МакКарти (JohnMcCarthy). Наименование Лисп (Lisp) происходит от Listprocessing(обработка перечней). Главным фундаментальным типом данных в языке LISP есть перечень. Наименование языка LISP образовано от LIStProcessing (обработка перечня).

Перечень рекурсивно определяется так:

Перечень ::= NIL | (S — выражение . Перечень)

В соответствии с этому определению любой непустой перечень есть точечной парой.

Приведем примеры перечней:

(LISP Functionallanguage)

(5 6 (8 (9)) 23 NIL)

Принципиально важно выделить понятие безлюдного перечня, что не содержит элементов, он обозначается () либо атомом NIL. К примеру, (NIL ()) — перечень, складывающийся из двух безлюдных перечней. Оперативная память компьютера, на котором трудится LISP, логически разбивается на мелкие области, каковые именуются списочными ячейками. Списочная ячейка складывается из полей с именами CAR и CDR, каждое из которых содержит указатель. Указатель может ссылаться на другую списочную ячейку либо на другой объект языка LISP, к примеру, на атом. Указатели между ячейками образуют как бы цепочку, по которой возможно из прошлой ячейки попасть в следующую и без того, наконец, до атомарных объектов. Любой атом, узнаваемый совокупности, записан в определенном месте памяти только один раз. Графически списочную ячейку будем воображать прямоугольником, поделённым на поля CAR и CDR. Указатель изображается в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении второй ячейки либо атоме, на что ссылается указатель.

Пример 1. Изобразим перечень (A B C D) в графической нотации:

Лекция 19: Логика предикатов. Кванторы


Также читать:

Понравилась статья? Поделиться с друзьями: