Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Лекция №17

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 715; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.