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

Лекция №17

История функционального программирования

Как известно, теоретические основы императивного программирования были заложены ещё в 30-х годах XX века Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, также родилась в 20-х — 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать Мозеса Шёнфинкеля (Германия и Россия) и Хаскелла Карри (Англия), разработавших комбинаторную логику, а также Алонзо Чёрча (США), создателя l-исчисления.

Теория так и оставалась теорией, пока в начале 50-х прошлого века Джон МакКарти не разработал язык Lisp, который стал первым почти функциональным языком программирования и на протяжении многих лет оставался единственным таковым. Хотя Lisp всё ещё используется (как, например, и FORTRAN), он уже не удовлетворяет некоторым современным запросам, которые заставляют разработчиков программ взваливать как можно большую ношу на компилятор, облегчив тем самым свой непосильный труд. Необходимость в этом, конечно же, возникла из-за всё более возрастающей сложности программного обеспечения.

В связи с этим обстоятельством всё большую роль начинает играть типизация. В конце 70-х — начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм. Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число диалектов.

В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многочисленные более мелкие проблемы. Чтобы исправить ситуацию, объединенная группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов. В настоящее время действителен стандарт Haskell-98.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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