Тема 4. Введение в функциональное программирование 1
План ближайших лекций по ФП
Введение в ФП (эта лекция)
-исчисление как базис ФП
Основы и идиомы ФП, язык Scheme Системы типов, побочные эффекты, язык Haskell Мультипарадигменные языки, язык Python Тема 4. Введение в функциональное программирование 2 Суть парадигмы ФП Использование чистых функций Отсутствие изменяемого состояния Элегантные небольшие функции, при этом выразительные Более короткие программы, активное использование абстракции Управление побочными эффектами функций Минимизация, управление или отказ от побочных эффектов Функциональное процедурное программирование Тема 4. Введение в функциональное программирование Функциональная чистота Функциональная чистота — отсутствие побочных эффектов Функции в математическом смысле как отображение множеств Побочные эффекты — всё, помимо преобразования входных данных в выходные Глобальное изменяемое состояние, ввод-вывод и т. п.
В императивных языках могут быть процедуры... -> void, вызывающиеся только ради побочных эффектов Пример с электронной таблицей Выражения в ячейках таблицы вычисляют значение из значений других ячеек Не используются операторы печати, работы с файлами и пр.
Тема 4. Введение в функциональное программирование Императивное vs. функциональное Ячейки памяти vs. неизменяемые значения Императивная программа исполняется инструкция за инструкцией, изменяя значения ячеек памяти Функциональная программа вычисляет значения на основе других значений Терм x в ИП — имя позиции в памяти, а в ФП — имя значения, которое не меняется в области видимости Возможно программирование без изменяемого состояния Можно ли написать хоть что-то полезное без оператора присваивания?
Тезис Чёрча-Тьюринга об эквивалентности императивных и функциональных программ Рекурсия заменяет итерацию Итерация проходит по одинаковым ячейкам с разными значениями В ФП нет изменяемых значений. Рекурсия с передачей новых аргументов Для получения такой же оценки сложности алгоритмов используется оптимизация хвостовых вызовов Тема 4. Введение в функциональное программирование История функциональных языков (1) 1958, Lisp Один из первых языков. Создан Джоном Маккарти Работа с символьными данными и списками для задач ИИ Породил целое семейство Lisp в лабораториях ИИ 1973, ML Создан Робином Милнером Для доказательства теорем Вывод типов по Хиндли-Милнеру, полиморфизм, важность -исчисления Создано много языков на основе ML 1975, Scheme Создан Стилом и Сассманом Для исследований языков, обучения. Продолжает развиваться Тема 4. Введение в функциональное программирование История функциональных языков (2) 1980-е Стандартизация Common Lisp Очередное свёртывание исследований ИИ и применения Lisp Общий ленивый функционально чистый язык, частично на основе ML Функциональные расширения языков сценариев Объектный диалект ML. Мультипарадигменный, эффективные программы F#, диалект OCaml под влиянием C# и Haskell для платформы.NET Clojure, диалект Lisp под влиянием Haskell, Erlang. Подход к параллельности Haskell, OCaml, Common Lisp, Scheme, Erlang, Clojure, XSLT и др.
Модель вычислений функциональных языков Механизм исполнения программ ФП На его основе строится исполнение, аналогично машинным инструкциями в На практике используются только элементы исчисления, программы Очень компактная формальная система 4 синтаксических формы: переменные, константы, -абстракции и применения Функции — полноправные значения Могут передаваться как аргументы, возвращаться как значения, именоваться Некоторые из этих свойств есть и в императивных языках (делегаты, указатели Абстракция шаблонов вычислений Выполнение преобразования над каждым элементом списка: удвоение, преобразование в строку и пр. Передача функции преобразования как аргумента Фильтрация списка. Передача в качестве аргумента функции-предиката из типа Требуются только функции одного аргумента Проще понимать и рассуждать о программе На результат влияют только аргументы и значения из области видимости Интерфейс функции это её тип. Легче выявлять, на что влияют изменения в коде Не требуется моделирование внешнего окружения, mock-объектов и пр.
В ИП общее изменяемое состояние потоков через блокировки, сложная В ФП нет изменяемого состояния и блокировок, сложно допустить ошибку Но автоматическая параллелизация по-прежнему не столь проста Очень часто создаются пользовательские типы данных Большое количество исследований систем типов в ФП Используются развитые системы типов Тема 4. Введение в функциональное программирование Подход Lisp. Фактически в языке смешиваются парадигмы ФП и ИП. Уменьшаются Подход раннего Haskell. Программа всего лишь преобразует строку в строку.
Сложно создавать практические программы Подход Haskell, Clean. Система типов разделяет чисто функциональную часть и часть с эффектами. Используются монады, уникальные типы Код программ обычно намного короче Можно сделать программу очень короткой, но запутанной Большие возможности абстракции Можно создавать код на уровне абстракции приложения Внутренние предметно-ориентированные языки DSL, например, для парсинга можно создать BNF-подобный язык внутри языка ФП Могут возникать проблемы с производительностью Раньше код на языках ФП был значительно медленнее, чем ИП. Сейчас Не всегда очевидная реализация алгоритма будет эффективной Simon Peyton Jones on Functional Programming and Haskell [Electronic Resource] / M. Vlter // Software Engineering Radio. — 2008. — No.
108. — http://se-radio.net/podcast/2008-08/episode-108-simon-peytonjones-functional-programming-and-haskell Аудиозапись интервью с одним из разработчиков Haskell Себеста Р. У. Основные концепции языков программирования. — Вильямс, 2001. — urn:isbn:5-8459-0192- Гл. 14. Функциональные языки программирования
[ 
«