|
p align="left">предок( X, Z) :- родитель( X, Y), родитель( Y, Z). предок( X, Z) :- родитель( X, Y1), родитель( Y1, Y2), родитель( Y2, Z). предок (X, Z) :- родитель( X, Y1), родитель( Y1, Y2), родитель( Y2, Y3), родитель( Y3, Z). Пары предок-потомок, разделенных разным числом поколений. Эта программа длинна и, что более важно, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку длина цепочки людей между предком и потомком ограничена длиной наших предложений в определении отношения. Существует, однако, корректная и элегантная формулировка отношения предок - корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь - определить отношение предок через него самого. Рис. 3 иллюстрирует эту идею: Для всех X и Z, X - предок Z, если существует Y, такой, что (1) X - родитель Y и (2) Y - предок Z. Предложение Пролога, имеющее тот же смысл, записывается так: предок( X, Z) :- родитель ( X, Y), предок( Y, Z). Теперь мы построили полную программу для отношения предок, содержащую два правила: одно для ближайших предков и другое для отдаленных предков. Здесь приводятся они оба вместе: предок( X, Z) :- родитель( X, Z). предок( X, Z) :- родитель( X, Y), предок( Y, Z). Рекурсивная формулировка отношения предок. Ключевым моментом в данной формулировке было использование самого отношения предок в его определении. Такие определения называются рекурсивными. Логически они совершенно корректны и понятны. Рекурсия - один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности. Оптимизация хвостовой рекурсииУ рекурсии есть один большой недостаток -- она «съедает» память. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура) могла, после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась. Это означает, что если процедура вызывает себя 100 раз, то 100 различных состояний должно быть записано одновременно (состояния выполнения решения сохраняются в стековом фрейме). Максимальный размер стека у 16-битных платформ, таких как IBM PC, работающая под DOS, составляет 64 Кбайт, что позволяет разместить максимум 3000 или 4000 стековых фреймов. На 32-битных платформах стек теоретически может возрасти до нескольких гигабайт; но здесь проявятся другие системные ограничения, прежде чем стек переполнится. Что же можно сделать, чтобы избежать использования столь большого стекового пространства?Рассмотрим специальный случай, когда процедура может вызвать себя без сохранения информации о своем состоянии. Что, если вызывающая процедура не собирается возобновлять свое выполнение после завершения вызванной процедуры?Предположим, что процедура вызывается последний раз, т. е. когда вызванная процедура завершит работу, вызывающая процедура не возобновит свое выполнение. Это значит, что вызывающей процедуре не нужно сохранять свое состояние, потому что эта информация уже не понадобится. Как только вызванная процедура завершится, работа процессора должна идти в направлении, указанном для вызывающей процедуры после ее выполнения.Например, допустим, что процедура А вызывает процедуру В, а В -- С в качестве своего последнего шага. Когда В вызывает С, В не должна больше ничего делать. Поэтому, вместо того чтобы сохранить в стеке процедуры В информацию о текущем состоянии С, мы можем переписать старую сохраненную информацию о состоянии В (которая больше не нужна) на текущую информацию о С, сделав соответствующие изменения в хранимой информации. Когда С закончит выполнение, она будет считать, что она вызвана непосредственно процедурой А.Предположим, что на последнем шаге выполнения процедура В вместо процедуры С вызывает себя. Получается, что когда В вызывает В, стек (состояние) для вызывающей в должен быть заменен стеком для вызванной В. Это очень простая операция, просто аргументам присваиваются новые значения и затем выполнение процесса возвращается на начало процедуры В. Поэтому, с процедурной точки зрения, происходящее очень похоже на всего лишь обновление управляющих переменных в циклеЭта операция называется оптимизацией хвостовой рекурсии (tail recursion optimization) или оптимизацией последнего вызова (last-call optimization) Обратите внимание, что по техническим причинам оптимизация последнего вызова неприменима к рекурсивным функциям.Как задать хвостовую рекурсиюЧто означает фраза "одна процедура вызывает другую, выполняя свои самый последний шаг"? На языке Пролог это значит.П вызов является самой последней подцелью предложения,О ранее в предложении не было точек возвратаНиже приводится удовлетворяющий обоим условиям пример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)clausescount(N):-write('\r',N), NewN = N+l, count(NewN).GOAL nl, count(0).13. Определение спискаВ Прологе список -- это объект, который содержит конечное число других объектов. Списки можно грубо сравнить с массивами в других языках, но, в отличие от массивов, для списков нет необходимости заранее объявлять их размер.Список, содержащий числа 1, 2 и 3, записывается так:[1, 2, 3] Каждая составляющая списка называется элементом. Чтобы оформить списочную структуру данных, надо отделить элементы списка запятыми и заключить их в квадратные скобки. Вот несколько примеров: [dog, cat, canary] ["valerie ann", "jennifer caitlin", "benjamin thomas"] 14. Объявление списковЧтобы объявить домен для списка целых, надо использовать декларацию домена, такую как: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 15. Головы и хвостыСписок является рекурсивным составным объектом. Он состоит из двух частей -- головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка -- всегда список, голова списка -- всегда элемент. Например:голова [а, b, с] есть ахвост [а, b, с] есть [b, с]Что происходит, когда вы доходите до одноэлементного списка? Ответ таков:голова [с] есть схвост [с] есть []Если выбирать первый элемент списка достаточное количество раз, вы обязательно дойдете до пустого списка []. Пустой список нельзя разделить на голову и хвост.В концептуальном плане это значит, что список имеет структуру дерева, как и другие составные объекты. Структура дерева [а, b, с, d] представлена на рис. 1.Рис. 1. Структура дереваОдноэлементный список, как, например [а], не то же самое, что элемент, который в него входит, потому что [а] на самом деле -- это составная структура данных.16. Работа со спискамиВ Прологе есть способ явно отделить голову от хвоста. Вместо разделения элементов запятыми, это можно сделать вертикальной чертой "|". Например:[а, 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% неудача | | |
17. Использование списковСписок является рекурсивной составной структурой данных, поэтому нужны алгоритмы для его обработки. Главный способ обработки списка -- это просмотр и обработка каждого его элемента, пока не будет достигнут конец.Алгоритму этого типа обычно нужны два предложения. Первое из них говорит, что делать с обычным списком (списком, который можно разделить на голову и хвост), второе -- что делать с пустым списком.18. Печать списковЕсли нужно напечатать элементы списка, это делается так, как показано в листинге 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, описанные на обычном языке: Печатать пустой список -- значит ничего не делать. Иначе, печатать список -- означает печатать его голову (которая является одним элементом), затем печатать его хвост (список) . 19. Подсчет элементов спискаРассмотрим, как можно определить число элементов в списке. Что такое длина списка? Вот простое логическое определение:Длина [] -- 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, 2, 3, 4, 5, 6, 7
|
