Теория вычислительных процессов |
Лекция 4 |
Лекция 4
1.5. Рекурсивные схемы
1.5.1. Рекурсивное программирование
Среди упомянутых выше методов формализации понятия вычислимой функции метод Тьюринга - Поста основан на уточнении понятия процесса вычислений, для чего используются абстрактные “машины”, описанные в точных математических терминах. Другой подход (метод Черча - Клини) основан на понятии рекурсивной функции. Рекурсивная функция задается с помощью рекурсивных определений. Рекурсивное определение позволяет связать искомое значение функции для заданных аргументов с известными значениями той же функции при некоторых других аргументах. Эта связь устанавливается с помощью универсального механизма рекурсии, дающего механическую процедуру поиска значений функции. Двум подходам к определению вычислимых функций соответствуют два метода программирования этих функций - операторное и рекурсивное программирование. При операторном методе программа представляет собой явно выписанную последовательность, описаний действий гипотетической вычислительной машины (последовательность операторов, команд и т. п.). Язык Фортран - типичный представитель операторных языков. С другой стороны, рекурсивная программа - это совокупность рекурсивных определений, задающих рекурсивную функцию, для которой аргументами служат начальные данные программы, а значением – результат выполнения программы. Известный язык рекурсивного программирования - язык Лисп - предназначен для обработки символьной информации. В других языках комбинируют оба метода программирования. Так, Паскаль - операторный язык с возможностью рекурсивного программирования, предоставляемой механизмом рекурсивных процедур и функций.
Примером рекурсивно определяемой функции является факториалъная функция FАСТ: Nat Nat:
FАСТ(х) = 1,если х =0, FАСТ(х) = х FАСТ(х - 1), если х> 0.
Операторные программы, вычисляющие значения этой функции, приведены в п. 1.1.3. Эту же функцию можно запрограммировать в некотором рекурсивном языке, базирующемся на механизме рекурсивных функций языка Паскаль:
FACT(a),
FACT(x) = if х=0 then 1 else х FACT(x - 1),
где а - некоторое целое неотрицательное число.
Выполнение этой программы для некоторого значения а (пусть а = 4) может быть осуществлено следующим образом. В обе части рекурсивного определения вместо х подставляется 4, после чего вычисляется правая часть определения. Вычисление правой части начинается с вычисления логического выражения. Если его значение 1 (истина), то вычисляется левое функциональное выражение (стоящее после then), а если его значение 0 (ложь) – вычисляется правое выражение (стоящее после else). Вычисление функционального выражения сводится к его упрощению, т. е. выполнению всех возможных вычислений. Если в упрощенном выражении остается вхождение символа определяемой функции FАСТ, то осуществляется переход к новому шагу выполнения программы. На этом шаге вхождение FACT(m), где m - значение внутри скобок после упрощения, заменяется левым (т = 0) или правым (m>0) функционалъным выражением, в котором все вхождения х заменены на m. Упрощения продолжаются до тех пор, пока не будет получено выражение, не содержащее FАСТ (в нашем случае это выражение - число).
Вычисление рекурсивной программы может завершиться за конечное число шагов с результатом, равным значению запрограммированной функции для заданных аргументов (начальных значений переменных), но может и продолжаться бесконечно. В последнем случае значение функции не определено.
1.5.2. Определение рекурсивной схемы
Рекурсивная схема (РС) так же, как ССП определяется в некотором базисе.
Полный базис РС, как и базис ССП, включает четыре счетных множества символов: переменные, функциональные символы, предикатные символы, специальные символы.
Множества переменных и предикатных символов ничем не отличаются от ССП. Множество специальных символов - другое, а именно: {if, then, else, (,), ,}. Отличие множества функциональных символов состоит в том, что оно разбито на два непересекающихся подмножества: множество базовых функциональных символов и множество определяемых функциональных символов (обозначаются для отличия прописными буквами, например, F(1),G(2), и т.д.).
В базисе РС нет множества операторов, вместо него - множество логических выражений и множество термов.
Простые термы определяются так же, как термы-выражения в СПП. Среди простых термов выделим базовые термы, которые не содержат определяемых функциональных символов, а также вызовы-термы вида F(n)(1,
2,…,
n), где
1,
2,…,
n-простые термы, F(n) – определяемый фунциональный символ.
Логическое выражение - слово вида
p(n)(1,
2,…,
n),
где p - предикатный символ, а 1,
2,…,
n -базовые термы.
Терм - это простой терм, или условный терм, т.е. слово вида
if then
1 else
2,
где - логическое выражение,
1,
2 - простые термы, называемые левой и соответственно правой альтернативой.
Примеры термов:
- f(x, g(x, у)); h(h(a)) - базовые термы;
- f(F(x), g(x, F(y))); Н(Н(а)) - простые термы;
- F(x); Н(Н(а)) - вызовы;
- if p(х, у) then h(h(a)) eIse F(x) - условный терм.
Используется бесскобочная форма представления:
if рху then hha else Fx - условный терм.
Расширим в базисе В множество специальных символов символом "=".
Рекурсивным уравнением, или определением функции F назовем слово вида
F(n)(x1,x2,…,xn)=(x1,x2,…,xn),
где (x1,x2,…,xn) - терм, содержащий переменные, называемые формальными параметрами функции F.
Рекурсивной схемой называется пара (, М), где
- терм, называемый главным термом схемы (или ее входом). М - такое множество рекурсивных уравнений, что все определяемые функциональные символы в левых частях уравнений различны и всякий определяемый символ, встречающийся в правой части некоторого уравнения или в главном терме схемы, входит в левую часть некоторого уравнения. Другими словами, в РС имеется определение всякой вызываемой в ней функции, причем ровно одно.
Примеры РС:
Rs1: F(x); F(x) = if р(х) then а eIse g(x, F(h(x))).
Rs2: А(b, с); А(х, у) = if р(х) then f(x) else В(х, у);
В(х, у) = if р(у) then A(g(x), а) else С(х, у);
С(х, у) = A(g(x), А(х, g(y)).
Rs3: F(x); F(x) = if р(х) then х else f(F(g(x)), F(h(x))).
Пара (Rs, I), где Rs - РС в базисе В, а I - интерпретация этого базиса, называется рекурсивной программой. При этом заметим, что определяемые функциональные символы не интерпретируются.
Протоколы выполнения программы (Rs1, I1) И (Rs2 ,I2), где I1 и I2 - интерпретации из п. 1.2.3 (рисунок 1.3, б, в), выглядят следующим образом:
№ п/п |
Значения терма для (Rs1,I1) |
Значения терма для (Rs2,I2) |
1 |
F(4) |
F(a,b,c) |
2 |
4*F(3) |
CONSCAR(abc,F(b,c)) |
3 |
4*(3*F(2)) |
CONSCAR(abc,CONSCAR(bc,F(c))) |
4 |
4*(3*(2*F(1))) |
CONSCAR(abc,CONSCAR(bc,CONSCAR(c,F(e)))) |
5 |
4*(3*(2*(1*F(0)))) |
CONSCAR(abc,CONSCAR(bc,CONSCAR(c,e)))=abc |
6 |
4*(3*(2*(1*1)))=24 |
1.6.1. О сравнении классов схем
Программы для ЭВМ, будь-то программы, записанные на операторном языке, или программы на рекурсивном языке, универсальны в том смысле, что любую вычислимую функцию можно запрограммировать и найти ее значения для заданных значений apryмeнтов. При этом не требуется богатого набора программных примитивов и базовых операций: достаточно тех средств, которые моделируются стандартными схемами. Это значит, что различные классы программ не имеет смысла сравнивать по способности реализовать различные алгoритмы,- все они оказываются универсальными. В то же время программисты знают, что одни программные примитивы являются “более выразительными”, чем другие, что запись алгоритмов с привлечением рекурсии короче, чем итерационное представление. Но вычисления по такой программе могут потребовать больше времени, и т. д. При переходе к схемам программ возникает возможность поставить и исследовать проблему выражения одних наборов примитивов через другие в более чистом виде. Задачи такого типа образуют сравнительную схематологию, основу которой составляют теоремы о возможности или невозможности преобразования схем из одного класса в схемы другого. При этом наряду с основной задачей, выяснением соотношений между различными средствами программирования, решается и другая, внутренняя задача схематологии. Действительно, если мы умеем трансформировать один класс схем в другой, то сможем переносить результаты, полученные для некоторого класса схем, на другие классы.
Мы будем сравнивать классы схем, у которых базисы согласованы в том смысле, что множества переменных, базовых функциональных символов и предикатных символов одинаковы в данных базисах. Это дает возможность превращать в программы схемы из разных классов с помощью одной и той же интерпретации базисов. Например, полные базисы стандартных и рекурсивных схем согласованны, т. е. определение функциональной эквивалентности может быть обобщено на схемы из разных классов.
Схема S1 из класса W и схема S2 из класса W' функционально эквивалентны, если для любой интерпретации I согласованных базисов классов W и W' программы (S1, I), (S2, I) или обе зацикливаются, или обе останавливаются с одним и тем же результатом.
Класс схем W мощнее класса схем W', или класс W' транслируем в класс W, если для любой схемы из W' существует эквивалентная ей схема в классе W. Классы W и W' равномощны, если W' мощнее W и W мощнее W'.
Доказано, что класс ССП транслируем в класс РС и класс РС не транслируем в класс ССП.
Рассмотренные примеры подтверждают первое утверждение для одинаковых интерпретаций I базисов. В этом случае РС Rs1 эквивалентна ССП S1. При разных интерпретациях ССП и РС результаты будут различаться и, следовательно, программы (Rs1, I1) и (S1, I2) будут различны.
Второе утверждение подкрепляется РС Rs3. Причина не транслируемости этой схемы обусловлена тем, что при варьировании интерпретаций возникает необходимость запомнить сколь угодно большое число промежуточных значений, в то время как память любой стандартной схемы ограничена.
Существуют некоторые классы РС, транслируемые в ССП. К ним относится класс линейных унарных РС, имеющих базис с единственной переменной х и одноместными функциональными и предикатными символами. Например:
Rs4: F(x); F(x)=if р(х) then х else f(x, F(g(x”) транслируема в ССП.
Схемы с процедурами строятся в объединенном базисе классов стандартных и рекурсивных схем. Она состоит из двух частей - главной схемы и множества схем процедур. Главная схема - это стандартная схема, в которой имеются операторы присваивания специального вида х:= F(n)(y1,y2,...,yn), называемые операторами вызова процедур. Схема процедуры состоит из заголовка и тела процедуры, разделенных символом равенства. Заголовок имеет тот же вид, что и левая часть рекурсивных уравнений. Тело процедуры - это стандартная схема того же вида, что и главная схема. 3аключительный оператор тела процедуры всегда одноместен (stop(x)). Ниже приведен пример схемы с процедурами.
Главная схема |
Множество схем процедур |
(staгt(x), |
F(y, v, w) = start, |
1: z:=x, |
1: if р(у) then 2 else 4, |
2: u:=а, |
2: y:=h(y), |
3: x:=F(x, z, u), |
3: v:=G(v, w) goto 1, |
4: u:=Ь, |
4: if q(w) then 5 else 6, |
5: z:=F(z,.x, u) |
5: y:=v, |
6: stop(z) |
6: stop(y)) |
G(t, r) = (staгt, |
|
1: if q(r) then 2 else 3, |
|
2: t:= f(t), |
|
3: stop(t); |
Доказано, что класс РС транслируем в класс схем с процедурами и наоборот.
назад | содержание | вперед