Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

П вызов является самой последней подцелью предложения,

О ранее в предложении не было точек возврата

Ниже приводится удовлетворяющий обоим условиям пример

count (N) : -write(N), nl, NewN = N+l, count(NewN) .

Эта процедура является хвостовой рекурсией, которая вызывает себя без резервирования нового стекового фрейма, и поэтому не истощает запас памяти Как показывает программа ch06e04 pro (листинг 13 4), если вы дадите ей целевое утверждение

count (0) .

то предикат count будет печатать целые числа, начиная с 0, и никогда не остановится В конечном счете произойдет целочисленное переполнение, но остановки из-за истощения памяти не произойдет

Листинг 13.4. Программа ch06e04.pro

/* Программа с хвостовой рекурсией, которая не истощает память */ predicates count(ulong)

clauses

count(N):-

write('\r',N), NewN = N+l, count(NewN).

GOAL nl, count(0).

1. Определение списка

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

Список, содержащий числа 1, 2 и 3, записывается так:

[1, 2, 3]

Каждая составляющая списка называется элементом. Чтобы оформить списочную структуру данных, надо отделить элементы списка запятыми и заключить их в квадратные скобки. Вот несколько примеров:

[dog, cat, canary]

["valerie ann", "jennifer caitlin", "benjamin thomas"]

1. Объявление списков

Чтобы объявить домен для списка целых, надо использовать декларацию домена, такую как:

domains

integerlist = integer*

Символ (*) означает "список чего-либо"; таким образом, integer* означает "список целых".

Элементы списка могут быть любыми, включая другие списки. Однако все его элементы должны принадлежать одному домену. Декларация домена для элементов должна быть следующего вида:

domains

elementlist = elements*

elements = ....

Здесь elements имеют единый тип (например: integer, real или symbol) или являются набором отличных друг от друга элементов, отмеченных разными функторами. В Visual Prolog нельзя смешивать стандартные типы в списке. Например, следующая декларация неправильно определяет список, составленный из элементов, являющихся целыми и действительными числами или идентификаторами:

elementlist = elements*

elements = integer; real; symbol/* Неверно */

Чтобы объявить список, составленный из целых, действительных и идентификаторов, надо определить один тип, включающий все три типа с функторами, которые покажут, к какому типу относится тот или иной элемент. Например:

elementlist = elements*

elements = i(integer); r(real); s(symbol)% функторы здесь i,r и s

1. Головы и хвосты

Список является рекурсивным составным объектом. Он состоит из двух частей — головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка — всегда список, голова списка — всегда элемент. Например:

голова [а, b, с] есть а

хвост [а, b, с] есть [b, с]

Что происходит, когда вы доходите до одноэлементного списка? Ответ таков:

голова [с] есть с

хвост [с] есть []

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

В концептуальном плане это значит, что список имеет структуру дерева, как и другие составные объекты. Структура дерева [а, b, с, d] представлена на рис. 1.

Рис. 1. Структура дерева

Одноэлементный список, как, например [а], не то же самое, что элемент, который в него входит, потому что [а] на самом деле — это составная структура данных.

1. Работа со списками

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

[а, b, с] эквивалентно [а| [b, с]] и, продолжая процесс,

[а| [b, с] ] эквивалентно [а| [b| [с] ]], что эквивалентно [а| [b| [с| [] ] ] ]

Можно использовать оба вида разделителей в одном и том же списке при условии, что вертикальная черта есть последний разделитель. При желании можно набрать

[а, b, с, d] как [а, b|[с, d]].

В табл. 1. приведены несколько примеров на присвоение в списках.

Таблица 1. Присвоение в списках

Список 1	Список 2	Присвоение переменным
[X, Y, Z]	[эгберт, ест, мороженое]	Х=эгберг, У=ест, Z=мороженое
[7]	[X | Y]	Х=7, Y=[]
[1, 2, 3, 4]	[X, Y | Z]	X=l, Y=2, Z=[3,4]
[1, 2]	[3 | X]	fail% неудача

1. Использование списков

Список является рекурсивной составной структурой данных, поэтому нужны алгоритмы для его обработки. Главный способ обработки списка — это просмотр и обработка каждого его элемента, пока не будет достигнут конец.

Алгоритму этого типа обычно нужны два предложения. Первое из них говорит, что делать с обычным списком (списком, который можно разделить на голову и хвост), второе — что делать с пустым списком.

1. Печать списков

Если нужно напечатать элементы списка, это делается так, как показано в листинге 1.

Листинг 1. Программа ch07e01.pro;

domains

list = integer*% Или любой тип, какой вы хотите

predicates

write_a_list(list)

clauses

write_a_list([ ]),% Если список пустой — ничего не делать

write_a_list([Н|Т]):-% Присвоить Н-голова,Т-хвост, затем...

write(H),nl,

write_a_list(Т).

goal

write_a_list([1, 2, 3]).

Вот два целевых утверждения write_a_list, описанные на обычном языке:

Печатать пустой список — значит ничего не делать.

Иначе, печатать список — означает печатать его голову (которая является одним элементом), затем печатать его хвост (список) .

1. Подсчет элементов списка

Рассмотрим, как можно определить число элементов в списке. Что такое длина списка? Вот простое логическое определение:

Длина [] — 0.

Длина любого другого списка — 1 плюс длина его хвоста.

Можно ли применить это? В Прологе — да. Для этого нужны два предложения (листинг 2).

Листинг 2. Программа ch07e02.pro

domains

list = integer*

predicates

length_of(list,integer)

clauses

length_of ( [ ] , 0).

length_of ( [ _|T],L) :-

length_of(T,TailLength),

L = TailLength + 1.

Посмотрим сначала на второе предложение. Действительно, [_|T] можно сопоставить любому непустому списку, с присвоением т хвоста списка. Значение головы не важно, главное, что оно есть, и компьютер может посчитать его за один элемент.

Таким образом, целевое утверждение

length_of([1, 2, 3], L).

подходит второму предложению при T=[2, 3]. Следующим шагом будет подсчет длины T. Когда это будет сделано (не важно как), TailLength будет иметь значение 2, и компьютер добавит к нему 1 и затем присвоит L значение 3.

Итак, как компьютер выполнит промежуточный шаг? Это шаг, в котором определяется длина [2, 3] при выполнении целевого утверждения

length_of([2, 3], TailLength).

Другими словами, length_of вызывает сама себя рекурсивно.

1 Имеются и другие стандартные домены.

Характеристики

Список файлов книги