Приведение рекурсивной формы к итеративной форме

Повысить эфф программы можно приведением ее к итеративному виду.

Т.е. к виду, в котором рекурсивные вызовы можно заменить на циклы.

Если рекур вызов вып в конце функции то и запоминать состояние не надо, надо сделать только переход, иначе запоминать с теке…

Говорят что множество определений F = {f1,f2,..,fn} находится в итеративной форме если для каждого определения fj функции с параметрами x1..xn, и с телом =ej , 1<=j<=N, и требование к ej (телу функции) должно быть следующим:

1 либо оно совсем не содержит вызовов функций f принадлежащих F

2 либо имеет форму fk e1..el и здесь e1,…el не содержат вызовов функций f из множества F. Вызов может быть атким что он составляет все тело функции, только вопрос в параметрах, они не должны иметь рекурсивных признаков

3 либо оно, тело, условное выражение с ветвями, имеющими одну из вышеперечисленных форм. Тело функции может быть формой if…

если такие условия выполняются то такие рекурсивные функции можно запрограммировать в императивном стиле, при этом имена функций будут служить метками, по которым будет передаваться управление программе.

*каждая функция это начало кода со своей меткой.

Мы рассмотрим оч простой пример, возьмем функцию выч факториал.

Рекурсивное определение

Fact 0 = 1

Fact (n+1) = (n+1) * (fact n)

Введем новую функцию f, в которой u обобщает (n+1)

3 f n u= u * (fact n)

Конкретизируем и раскроем по 1 и 2 это определение

4 f 0 u = u

5 f (n+1) u = u * ((n+1)*(fact n))

Учитывая ассоциативность умножения, свернем по 3

= f n u * (n+1)

Вырази fact через f, свернув по 2 и 3

6 fact (n+1) = f n (n+1)

Определения 1,6,4,5 – это итеративная реализация функии факториала.

Введение в лямбда исчисление

Будем говорит о теоритеч основах…

Лямбда исчисление была предложено в 1934 году Алонзом Чёрчем.

Парадоксы… и надо было исп другой стиль представления функкий…. Черч предложил опр функции как правило преобразующее свой аргумент в результат. Благодаря лямбда исчислению теория множеств получилась свободная от парадоксов. Потом ученые выяснили что лямбда исч можно исп как язык программирование, так и формальную основу для описания семантики языков программирования.

Синтаксис лямбда исчисления

Термы(выражения) лямбда-исчисления (будем обозначать их L,M,N…) строятся индуктивно из заданного множества переменных x,y,z… след образом

1 х – переменная явл термом

2 (лямбда х. М) – абстракция явл термом (как \x->e)

3 (M N) – применение функции явл термом

Запись M ΞN обозначает что M и N идентичны.

Метасимволы L,M,N метаязык а не язык лямбда исчисления.

Мы будем определять равенство M=N, но надо рассмотреть семантику исчисления.

Множество связанных переменных

(как глобальные и локальные переменные)

Свободные переменные – глобальные

Связанные переменные – локальные

(Lambda x.(lamday.(x z)))

Z – свободна, x - связана

BV – функция, которая строит связанные переменные. Bound value. Множеств переменных для которых есть лямбда абстракция. Надо терм рекурсивно разобрать, а вариантов будет только 3…(3 вида термов).

BV(x)=O (пустое множество)

BV(lambda x.M) = BV(M) u {x}

BV(M N) = BV(M) u BV(N)

Х – связанная здесь переменная…