Рекурсивные схемы
Киевский Национальный университет имени
Тараса Шевченко
Реферат
на
тему:
«Рекурсивные схемы»
студента 3-го курса,
группы ТП
Пушкаря Н.В.
Киев 1999
РЕКУРСИВНЫЕ СХЕМЫ
§ 1. Класс рекурсивных схем
1.1. Рекурсивное программирование.
Среди упомянутых вы-
ше
методов формализации понятия вычислимой функции метод
Тьюринга
Поста основан на уточнении понятия процесса вы-
числений,
для чего используются абстрактные «машины», опи-
санные
в точных математических терминах. Другой подход (ме-
тод
Черча — Клини) основан на понятии рекурсивной функции.
Рекурсивная
функция задается с помощью рекурсивных опреде-
лений.
Рекурсивное определение позволяет связать искомое зна-
чение
функции для заданных аргументов с известными значения-
ми
той же функции при некоторых других аргументах. Эта связь
устанавливается
с помощью универсального механизма рекурсии,
задающего
механическую процедуру поиска значений функции.
Двум
подходам к определению вычислимых функции соответст-
вуют
два метода программирования этих функций — операторное
и
рекурсивное программирование. При операторном методе про-
грамма
представляет собой явно выписанную последовательность
описаний
действий гипотетической вычислительной машины (по-
следовательность
операторов, команд и т. п.).
Язык
Фортран — типичный представитель
операторных
языков.
С другой стороны, рекурсивная программа — это сово-
купность
рекурсивных определений, задающих рекурсивную
функцию,
для которой аргументами служат начальные данные
программы,
а значением — результат выполнения программы.
Известный
язык рекурсивного программирования — язык Лисп —
предназначен
для обработки символьной информации. В других
языках
комбинируют оба метода программирования. Так, Пас-
каль
операторный язык с возможностью рекурсивного про-
граммирования,
предоставляемой механизмом рекурсивных про-
цедур
и функций.
Известным
примером рекурсивно определяемой функции яв-
ляется
факториальная функция FACT: NN, где N — мно-
жество
целых неотрицательных чисел:
FACT
(х) =
Эту
же функцию можно запрограммировать в некотором рекурси-вном языке, базирующемся
на механизме рекурсивных функций языка
Паскаль:
FACT
(a),
FACT
(х) = если х = 0 то 1 иначе х FACT (х — 1),
где
а — некоторое целое неотрицательное число.
Выполнение
этой программы для некоторого значения а (пусть
а
= 4) может быть осуществлено следующим образом. В обе час-
ти
рекурсивного определения вместо х подставляется 4, после чего
вычисляется
правая часть определения. Вычисление правой час-
ти
начинается с вычисления логического выражения. Если его
значение
1 (истина), то вычисляется левое функциональное выра-
жение
(стоящее после то), а если его значение 0 (ложь) — вы-
числяется
правое выражение (стоящее после иначе). Вычисление
функционального
выражения сводится к его упрощению, т. е.
выполнению
всех возможных вычислений. Если в упрощенном
выражении
остается вхождение символа определяемой функции
FACT,
то осуществляется переход к новому шагу выполнения
программы.
На этом шаге вхождение FACT(m), где m, — значение
внутри
скобок после упрощения, заменяется левым (m = 0) или
правым
(m > 0) функциональным выражением, в котором все
вхождения
х заменены на m. Упрощения продолжаются до тех
пор,
пока не будет получено выражение, не содержащее FACT
(в
пашем случае это выражение — число).
FACT
(4) = если 4 = 0 то 1 иначе 4FACT(4 — 1) =
= 4FACT (3) = 4 (если 3=0 то 1 иначе
3FACT (3 - 1)) = 4 3 FACT (2) =
= 12(если 2 = 0 то 1 иначе 2FACT(2 — 1)) =
= 122FACT(1) = 24(если 1 = 0 то 1
иначе
1FACT(1 - 1)) =
= 241FACT(0) = 24(если 0 =
= 0 то 1 иначе 0FACT(0 — 1)) = 24
Вычисление
рекурсивной программы может завершиться за ко-
нечное
число шагов с результатом, равным значению запрограм-
мированной
функции для заданных аргументов (начальных зна-
чений
переменных), но может и продолжаться бесконечно. В по-
следней
случае значение функции не определено.
Еще
один популярный пример — рекурсивная программа, вы-
числяющая
значения функции Аккермана А: :
А
(а, b),
А
(х, у) = если х =0 то у + 1 иначе
В (х, у),
В
(х,
у)
= если у =0 то А (х - 1, 1) иначе С (х, у),
C(x,y) = A(x-1,A(x,y-1)).
Эта
программа состоит из главного вызова А (а, b) и трех оп-
редeлений функций. Первое определение
описывает функцию Ак-
кeрмана А череа вспомогательную функцию В,
которая задана,
в
свою очередь, с помощью функций A
и С. Последняя также оп-
ределена
через функцию А. Здесь каждое определение, взятое
отдельно,
само на себя не ссылается, но имеет место взаимная ре-
курсия,
когда каждая из функций A,
В, С косвенно определена
через
саму себя.
Выполнение
этой программы для а = b
= 1 выглядит сле-
дующим
образом (некоторые мелкие упрощения не выписаны):
А
(1, 1) =
если
1 = 0 то 2 иначе В (1, 1) = В (1, 1) = если
1=0 то
A
(0,
1) иначе С (1, 1) = С
(1, 1) =
=A
(0, А (1, 0)) = А (0, (если 1 = 0 то 1 иначе
В
(1, 0))) = А (0, В (1, 0)) = А (0, (если
0 = 0 то
А
(0, 1) иначе С (1, 0)) = А ( 0, Л (0,1) ) =
=Л
(0, (если 0=0 то 2 иначе В(О, 1))) = А
(0, 2) =
=
если 0 = 0 то 2+4 = 1 иначе В(0, 2)
= 3.
Отметим,
что в этом примере функциональное выражение со-
держит
несколько вхождений символов определяемых функций
(например,
А (0, А (1, 0)) ). Использованное нами правило под-
становки
в этом случае требует, чтобы замещалось левое из самых
внутренних
вхождений (в случае упомянутого терма — вхожде-
ние
А (1,0)).
Операторный
и рекурсивный методы программирования имеют
свои
достоинства и недостатки, обсуждать которые — не наша
задача
(см. например, ставшую классической работу Дж. Бэку-
са,
обратившего внимание на преимущества функционального
стиля
программирования). Но чтобы подготовить почву для та-
кого
обсуждения, полезно формализовать оба метода. Стандарт-
ные
схемы являются моделями операторных программ. Сейчас
мы
введем рекурсивные схемы, которые служат абстракциями
рекурсивных
программ, а в последующих параграфах проведем
сравнение
этих моделей.
1.2. Определение рекурсивной схемы.
Так же, как и стан-
дартные
схемы, рекурсивные схемы определяются в некотором
базисе.
Полный базис рекурсивных схем, как и базис стандартных
схем,
включает четыре счетных множества символов: перемен-
ные,
функциональные символы, предикатные символы., специаль-
ные
символы.
Множества
переменных и предикатных символов ничем не
отличаются
от соответствующих множеств в базисе стандартных
схем.
Множество специальных символов — другое, а именно:
{если, то, иначе, ( , ) , }. Что касается множества функциональ-
ных
символов, то оно ииеет единственное, но существенное отли-
чие
от множества функциональных символов базиса стандартных
схем.
Отличие состоит в том, что это множество разбито на два
непересекающихся
подмножества: множество базовых функцио-
нальных
символов и множество определяемых функциональных
символов.
Чтобы отличать их, будем определяемые функциональ-
иые
символы обозначать прописными буквами, например, F(1),
G(2), Н(1),
. . . (Такие буквы уже использовались для обозначения
функций.
В рекурсивных схемах важно наглядно отделать базо-
вые
и определяемые символы, поэтому мы пошли на двусмыслен-
ное
использование прописных букв F, G, Н, . . ., надеясь, что
контекст
поможет восстановить смысл обозначения.)
В
базисе рекурсивных схем нет множества операторов, вместо
него
множество логических выражений и множество термов.
Простые
термы определяются точно так же, как определялись
термы-выражения
в стандартных схемах. Среди простых термов
выделим
базовые термы, которые не содержат определяемых функ-
циональных
символов, а также вызовы — термы вида F(n)
(т1,
. . .
.
. ., тn)
где т1
, .
. . , тn
простые термы, а F(n) — определяемый
функциональный
символ. Логическое выражение — слово вида
p(n)
(т1, . . .
,тn),
где p(n)
предикатный символ, т1, . . .
,тn
базовые
термы. Терм — это 1) простой терм, или 2) условный терм,
т.
е. слово вида
если p то т1 иначе тn,
где p — логическое выражение, т1 , тn — простые термы,
назы-
ваемые
левой и соответственно правой альтернативой.
если р(х, у) то h (h (а)) uначе F (х) — условный терм.
Наряду
с обычным представлением термов будем использо-
вать
бесскобочную форму;
если рху то hha иначе Fx.
Пусть
B
некоторый базис. Расширим множество специаль-
ных
символов дополнительным символом = .
Рекурсивным
уравнением, или определением функции F назо-
вем
слово вида
F(n)(x1 ,. . ., xn) = т (x1 ,. . ., xn).
где
F(n)
n-мeстный определяемый функциональный символ;
т
(x1
,.
. ., xn) — терм, содержащий переменные из
множества
переменных
{x1
,.
. ., xn},
называемых формальными парамет-
рами
(ФРП) функции F,
и никаких других переменных.
Рекурсивной
схемой называется пара (т, М), где т — терм,
называемый
главным-термом схемы (или ее входом), а М — такое
множество
рекурсивных уравиенвй, что все определяемые функ-
циональные
символы в левых частях уравнений различны ц вся-
кий
определяемый символ, встречающийся в правой части неко-
торого
уравнения или в главном терме схемы, входит в левую
часть
некоторого уравнения. Другими словами, в рекурсивной
схеме
имеется определение всякой вызываемой в ней функции,
причем
ровно одно.
1.3. Рекурсивная программа. Понятие
интерпретации базиса, полностью
переносится на базисы рекурсивных схем с одним лишь замечанием — определяемые
функциональные символы не интерпретируются. Определение свободной интерпретации
также остается в силе.
Пара
(S, I), где S — рекурсивная схема в базисе В, а I —
интерпретация
этого базиса, называется рекурсивной программой,
Понятие
выполнения рекурсивной программы определим с по-
мощью
протокола выполнения, который представляет собой ко-
нечную
или бесконечную последовательность конфигураций. Кон-
фигурации
определены с помощью понятия значения терма.
Так
как мы сейчас рассматриваем термы, допускающие неинтер-
претируемые
определяемые функциональные символы, необхо-
димо
обобщить понятие значения (базового) терма.
Пусть
т — терм, I
некоторая интерпретация, W — неко-
торое
состояние памяти, т. е. совокупность значений всех пере-
менных,
входящих а терм (или в схему, содержащую этот терм).
Значение
тI
(W) терма т при интерпретации I
и состоянии памяти
W определяется следующим образом:
1)
если т, — базовый терм, то тI
(W) — значение этого терма,
определенное
точно так, как это было сделано в п. 2.4;
2)
если т — терм вида F(n)(т1,.
. ., тn), то т1 (W) = F(n)(т1I(W),.
. ., тnI(W));
3)
если т — терм вида f(n)
(т1,. . ., тn) и хотя бы один из
тер-
мов
т1,. . ., тn содержит определяемый
функциональный символ, то
тI(W) = Ф(n)(т1I(W),.
. ., тnI(W))
где
Ф(n)
символ функции I(f(n)),
за которым в скобках сле-
дует
список значений термов т1I(W),. . ., тnI(W);
4)
если т — условный терм вида
если p(n)(т1,.
. ., тn) то
тl
иначе
тr, то
Таким
образом, в общем случае значения термов — это выра-
жения,
содержащие элементы из области интерпретации, опре-
деляемые
функциональные символы и символы конкретных функ-
ций.
Если
протокол конечен, то программа (S, I) останавливается
и
последняя конфигурация в протоколе считается результатом
программы,
если она представляет собой элемент из области ин-
терпретации.
Если же последняя конфигурация — выражение,
составленное
из символов функций и значений переменных, то
осуществляется
вычисление этого выражения, в результат вы-
числения
(элемент из области интерпретации) объявляется резуль-
татом
программы. Программа (S, I)
зацикливается, если протокол
бесконечен.
П р
и м е
р. Протокол выполнения программы (S,I), где
I — интерпретация, выглядит следующим
образом:
Порядковый Значение терма
номер
1 F(4)
2 4 x F (3)
3 4 x (3 x (F (2)))
4 4 х (3 х (2 x F (1)))
5 4 x (3 x (2 x (1 x F (0))))
6 4 x (3 x (2 x
(1 x 1))) = 24
Протокол
выполнения программы (S,Ih), где Ih — свободная
интерпретация
из п. 3.2:
Порядковый Значение терма
номер
1 Fx
2 gxFhx
3 gxghxFhhx
4 gxghxghhxFhhhx
5 gxghxghhxa
После
того как введено понятие выполнения рекурсивных
программ,
можно дать определения пустоты, тотальности н функ-
циональной эквивалентности
рекурсивных схем.
§ 2. Проблемы трансляции
2.1. О сравнении классов схем. Программы для
ЭВМ, будь
то
программы, записанные на операторном языке, или программы
на
рекурсивном языке, универсальны в том смысле, что любую
вычислимую
функцию можно запрограммировать и найти ее
значения
для заданных значений аргументов. При этом, как уже
указывалось,
не требуется богатого набора программных прими-
тивов
и базовых операций: достаточно тех средств, которые мо-
делируются
стандартными схемами, плюс одна интерпретирован-
ная
операция и один предикат. Это значит, что различные классы
программ
не имеет смысла сравнивать по мощности, понимаемой
как
способность реализовать различные алгоритмы,— все они
оказываются
универсальными. В то же время программисты знают,
что
одни программные примитивы являются «более выразитель-
ными»,
чем другие, что запись алгоритмов с привлечением рекур-
сии
короче, чем итерационное представление, но вычисления по
такой
программе могут истребовать больше времени, и т. д. При
переходе
к схемам программ возникает возможность поставить
и
исследовать проблему выражения одних наборов примитивов
через
другие в более чистом виде. Задачи такого типа образуют
сравнительную
схематологию, основу которой составляют теоре-
мы
о возможности или невозможности преобразования схем из
одного
класса в схемы другого. При этом наряду с основной за-
дачей
выяснением соотношений между различными средствами
программирования
решается и другая, внутренняя задача схе-
матологии.
Действительно, если мы умеем трансформировать один
класс
схем в другой, то сможем переносить результаты, получен-
ные
для некоторого класса схем, на другие классы.
В
этой главе рассматриваются рекурсивные схемы, но так
как
в следующей главе речь пойдет о других классах схем прог-
рамм,
имеет смысл ввести необходимые понятия сравнительной
схематологии
для произвольных классов схем программ.
Пусть
У— класс схем программ в некотором базисе B, У —
класс
схем программ в базисе У’.
Базис любого из рассматривае-
мых
классов схем включает множества: переменных, базовых
функциональных
символов, предикатных символов, другие мно-
жества,
специфичные для данного класса.
Мы
будем сравнивать классы схем, у которых базисы согла-
сованны
в том смысле, что первые три из перечисленных множеств
одинаковы
в данных базисах. Это дает возможность превращать
в
программы схемы из разных классов с помощью одной и той же
интерпретации
базисов. Например, полные базисы стандартных
и
рекурсивных схем согласованны, т. е. определение функцио-
дальней
эквивалентности может быть обобщено на схемы из раз-
ных
классов.
Схема
S1 нз класса У и схема S2, из класса У’ функционально
эквивалентны.,
если для любой интерпретации I
согласованных
базисов
классов У u
У’
программы (S1,
I),
(S2, I) или
обе
зацикливаются,
или обе останавливаются с одним и тем же резуль-
татом.
Говорят,
что класс схем У мощнее класса схем У’, или класс
У’ транслируем в класс У (обозначение: УУ’),
если для любой
схемы
из У’
существует эквивалентная ей схема в классе У.
Класс
У строго мощнее класса У’
(У > У’),
если У мощнее
У’ и в У существует схема, для которой нет
эквивалентной схемы
в
У’
(класс У’
не транслируем в класс У). Классы
У и У’
равномощны,
если У мощнее У’
и У’
мощнее У. Класс схем У
эффективно
транслируем в класс схем У’,
если существует алго-
ритм,
преобразующий любую схему из У в эквивалентную схему
из
У’.
Классы У и У’
эффективно равномощны, если У эффек-
тивно
транслируем в У’
и У’
эффективно транслируем в У.
Ниже,
когда устанавливается транслируемость одного класса
схем
в другой или их равномощность, фактически демонстрируется
эффективная
транслируемость или эффективная равномощность.
2.2. Трансляция стандартных схем в рекурсивные.
В рекур-
сивных
схемах результат поставляет ровно один терм, а в стан-
дартных
схемах заключительные оператор может содержать
любой
конечный набор термов и тогда результат программы —
не
один элемент из области интерпретации, а набор таких эле-
ментов.
Однако такое отличие не имеет принципиального значе-
ния
для транслируемости схем. Можно было бы определить ре-
курсивные
схемы, поставляющие в качестве результата наборы
термов,
например, используя интерпретированную функцию пе-
чать
(т1, . . ., тn).
Мы поступим проще — ограничим класс стан-
дартных
схем схемами над базисом, содержащим заключительные
операторы
только следующего вида: стоп(х), хХ.
Т
е о р е м а (Маккарти). Класс стандартных схем транс-
лируем
в класс рекурсивных схем.
Краткий обзор и комментарии
Теоретическое
изучение рекурсивного программирования бы-
ло
начато Маккарти в связи с его работами над языком
Лисп и одновременно в связи с попытками создать
основы
семантической
теории программирования. В дальнейшем рекур-
рентные
схемы и программы играли важную роль в развитии фор-
мальных
методов описания и исследования семантики программ
и
языков программирования, в теории правильности программ.
Схематологические
аспекты рекурсивного программированяя впер-
вые
были исследованы Де Баккером и Скоттом, Стронгом,
Патерсоном
и Хьюиттом.
Де
Баккер и Скотт предложили унарные рекурсивные схемы
как
обобщение схем Янова и инициировали изучение главных
проблем
для рекурсивных схем. Так как класс рекурсивных схем
строго
мощнее класса стандартных схем (см. теорему), Heразре-
шимость
всех глагвных проблем для рекурсивных схем можно
установить из их неразрешимости для стандартных
схем.
С
другой стороны, класс праволинейных унарных схем равномо-
щен
классу схем Янова (см. теорему), поэтому на этот класс
наносятся
все «положительные» результаты из теории схем Яно-
ва.
В настоящее время между этими двумя полюсами мало
мущественных
результатов. Гарлэнд и
Лакхэм показали
разрешимость
проблемы эквивалентности в классе линейных унар-
ныx
схем, и Сабельфельд построил полную систему
эквива-
лентных
преобразований для этого класса в духе системы преоб-
зования
Ершова для схем Янова. Наиболее полное исследова-
ние
класса унарных схем выполнено Ашкрофтом, Манна и Пнуе-
ли,
которые установили разрешимость проблем пустоты,
тотальности
и свободы в этом классе, а также разрешимость про-
блемы
эквивалентности в классе свободных унарных схем.
В
классической работе Гарлэнд и Лакхэм высказали ги-
потезу
о разрешимости функциональной эквивалентности в клас-
се
унарных линейных рекурсивных схем с засылками констант,
т.е.
схем, в которых разрешается использовать нульместные ба-
зовые
функциональные символы. Однако все попытки применения
«техники
следов» для построения распознающего алгоритма ока-
зались
неудачными. Лисовик разработал новый метод (назвав его
методом
жестких множеств), применением которого доказал
гипотезу
Гарлэнда-Лакхэма. Впрочем, другой
алгоритм реше-
ния
этой проблемы оказалось возможным извлечь из результатов
работ.
Понятие
унарной металинейной схемы отличается от унарной
линейной
только тем, что снимаются все ограничения, которые
накладывались
на главный терм схемы. Например,
F1 (F2(F3(а))),
F1 (х) = если р(х) тo х иначе g(F1(f (х))),
F2 (х) = если q(х) то f(F3(g
(х))) иначе F1(h
(x)),
F3 (х)
= если r(х)
то х иначе F3(g
(h
(х)))
металинейная схема. Лисовик показал, что проблема эк-
вивалентности
унарных металинейных рекурсивных схем с за-
сылками
констант алгоритмически разрешима. Этот результат
был
получен с помощью довольно длинной цепочки сведений,
в
конечном счете проблема была сведена к решению системы ли-
нейных
диофантовых уравнений.
Была
определена логико-термальная эквивалентность,
казавшаяся
корректным и разрешимым отношением эквивалент-
ности.
Характерная особенность лт-эквивалентпости состоит
в
том, что ее определение не использует понятия интерпретации.
Несмотря
на тот факт, что лт-эквивалентность существенно силь-
нее
функциональной эквивалентности, набор преобразований,
охраняющий
лт-эквивалентность, оказался довольно широким.
Естественно
попытаться ввести формальную эквивалентность,
не
использующую понятия интерпретации, и для рекурсивных
схем.
Такая эквивалентность, основанная на понятии дерева раз-
вертки
всех возможных выполнений схемы была введена
Розеном
под названием древесной эквивалентности (tree
equivalence).
Проблема
древесной эквивалентности иказалась равносильной
проблеме
эквивалентности детерминированных магазинных
автоматов,
известной открытой проблемме в теории формаль-
ных
языков. Что касается проблеммы древесной пустоты —
алгоритм
решения ее существует и описан. Разрешимой является
также
проблемма древесной эквивалентности в подклассе линей-
ных
(полиадических) рекурсивных схем.
Эквивалентные
преобразования для рекурсивных схем про-
грамм
также рассматривались в некоторых работах. Условия
применения
многих преобразований извлекаются при этом
с
помощью алгоритмов глобального анализа, обобщающих
алгоритмы
разметки.
Стронг,
Патерсон и Хьюитт исследовали задачу трансляции
рекурсивных
схем в стандартные. Их работы открыли новый
раздел
теории схем программ — сравнительную схематологию.
Задача
сравнительной схематологии — изучение выразительных
возможностей
различных средств (и методов) программирования,
изучение
возможности транслировать один класс схем в другой.
Стронг
показал, что класс рекурсивных схем не транслируется в
класс
стандартных схем (и даже в более общий класс счетчиковых
схем
, и
выделил некоторые подклассы
транслируемых
схем.
Одновременно Патерсон и Хьюитт предложили выразитель-
ный
пример рекурсивной схемы , для которой не существует
эквивалентной
стандартной схемы. Они же анонсировали
возможность трансляции линейных унарных схем,
алгоритм
трансляции был позднее предложен Гарлэндом и
Лакхэмом.
Стандартные и рекурсивные схемы программ Алгоритмы трансляции. Изучение рекурсивных алгоритмов в начальных классах. Схема упрощения выражения в программировании. Доказать что значение выр будет целое число. Рекурсивных уравнений Ленин Россия Ленине. Примеры рекурсивной функции на паскале. Рекурсивные методы в программировании. Рекурсивные функции решение программа. Общая схема рекурсивной программы. Определение рекурсивных функций. Блок схема рекурсивной функции. Рекурсивные функции в паскале. Схемы задач за первый класс. Реферат рекурсивный фильтр. Программа класса патерсона.
|
