Лекция №17 Рекурсивные функции и лямбда-исчисление а.Черча

В основе функционального программирования лежит идея, что в результате каждого действия возникает значение. Значения становятся аргументами следующих действий, и конечный результат всей задачи выдается пользователю. Программа строится из логически расчлененных определений функций, которые состоят из организующих вычисления управляющих структур и из вложенных, часто вызывающих самих себя (рекурсивных) вызовов функций.

Основными средствами функционального программирования как раз и являются композиция и рекурсия. Ни ячеек памяти, ни операторов присваивания, ни циклов, ни, тем более, блок-схем, ни передач управления.

В основе функционального программирования лежит строгий математический аппарат лямбда-исчисления Чёрча и теория рекурсивных функций.

Введенное в 1931 году математиком Алонзо Черчем, лямбда-исчисление оперирует всего тремя типами элементов:

• символами, представляющими переменные и константы;

• скобками для группировки символов;

• обозначениями функций с использованием греческой буквы лямбда.

Лямбда-исчисление используется для синтаксического описания свойств математических функций и обработки их в качестве правил.

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

Вычисления начинаются с вызова некоторой функции, которая в свою очередь вызывает функции, входящие в состав ее определения и т. д. в соответствии с иерархией определений и структурой условных предложений. Функции могут прямо или опосредованно вызывать сами себя. Каждый вызов возвращает некоторое значение в вызвавшую его функцию, вычисление которой после этого продолжается. Процесс вычислений повторяется до тех пор, пока запустившая вычисления функция не вернет конечный результат пользователю. В функциональном программировании нет места присваиванию и передаче управления. Разветвление вычислений основано на механизме обработки аргументов условного предложения. При таком подходе к программированию рекурсия является единственным способом организации повторяющихся вычислений.

В функциональной программе не должно быть:

• присваиваний;

• глобальных переменных;

• обработки исключений;

• функций с побочными эффектами.

Этот перечень следует из основного свойства функционального программирования – прозрачности по ссылкам.

Прозрачность по ссылкам – необходимое условие функциональной программы

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

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

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

В функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путем декомпозиции и синтеза существующих объектов. О ненужных объектах позаботится встроенный в язык сборщик мусора (удаление ненужных объектов программы вынесено на уровень системы). Благодаря этому в функциональных языках все функции свободны от побочных эффектов.

Из отсутствия побочных эффектов следует еще одно преимущество – параллелизм вычислений. На интуитивном уровне понятно, что если все функции для вычислений используют только свои параметры, можно вычислять независимые функции в произвольном порядке или, скажем, параллельно, на результат вычислений это не повлияет. Причем параллелизм этот может быть организован как на уровне компилятора языка, так и на уровне архитектуры. В лямбда-исчислении доказывается теорема, которая подтверждает это интуитивное соображение на уровне математической теории.

Функциональным языкам присущи энергичный и ленивый виды вычислений.

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

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

В теории функционального программирования принято говорить о двух крайних видах вычисления: энергичном и ленивом. Эти варианты выделяются, так как представляют крайние случаи, хотя существуют и другие варианты.

Ленивое вычисление – стратегия планирования, при которой вычисления не выполняются до тех пор, пока не возникнет необходимость в их результатах.

Энергичное вычисление – стратегия, при которой вычисления выполняются, как только появляется возможность их выполнить. Принцип энергичного вычисления можно сформулировать следующим тезисом: «на каждом шаге вычисляется все, что может быть вычислено». Не важно, пригодится ли в конечном случае полученный результат. Таким образом, всегда существует вероятность выполнения лишних вычислений.

Принцип ленивого вычисления: «не вычислять ничего, что не требуется в данный момент». Можно провести некоторую аналогию энергичного вычисления в функциональных языках с механизмом вызова по значению в императивных языках, а ленивое вычисление с механизмом вызова по необходимости. Однако между ними не существует тождественного равенства, и точное соотношение между этими терминами будет ясно, после изучения гл. 9.

Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим (strict) языком программирования, в отличие от нестрогого (lazy) языка, с ленивой стратегией вычисления.