Элементы функционального программирования. Принципы функционального программирования: почему это важно

Язык функционального программирования

В качестве основных свойств функциональных языков программирования обычно рассматриваются [кем? ] следующие:

• краткость и простота;

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

QuickSort () =
quickSort () = quickSort (n | n t, n <= h) + [h] + quickSort (n | n t, n > h)

• строгая типизация;

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

• модульность;

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

• функции - объекты вычисления;

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

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

• отложенные (ленивые) вычисления.

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

Некоторые языки функционального программирования

Классификация функциональных языков

В качестве примера чистого функционального языка можно привести Haskell . Однако большинство функциональных языков являются гибридными и содержат свойства как функциональных, так и императивных языков. Яркие примеры - языки Scala и Nemerle. В них органично сочетаются характеристики как объектно-ориентированных языков, так и функциональных. Реализована хвостовая рекурсия и её оптимизация, функция является полноправным объектом, то есть может быть сохранена в переменной, передана в качестве аргумента в другую функцию или возвращена из функции.

Также функциональные языки делят на строгие и нестрогие . К нестрогим языкам относят те, которые поддерживают отложенные вычисления (F#), то есть аргументы функции вычисляются только тогда, когда они действительно понадобятся при вычислении функции. Ярким примером нестрогого языка является Haskell. В качестве примера строгого языка можно привести Standard ML .

Некоторые функциональные языки реализованы поверх платформообразующих виртуальных машин (JVM, .NET), то есть приложения на этих языках могут работать в среде времени исполнения (JRE, CLR) и использовать встроенные классы. К ним относятся Scala, Clojure (JVM), F#, Nemerle, SML.NET (.NET).

Ссылки

• http://fprog.ru/ - Журнал «Практика функционального программирования»
• http://www.intuit.ru/department/pl/funcpl/1/ - Основы функционального программирования. Л. В. Городняя
• http://roman-dushkin.narod.ru/fp.html - Курс лекций по функциональному программированию , читаемый в МИФИ с 2001 года;
• http://alexott.net/ru/fp/books/ - Обзор литературы о функциональном программировании . Рассматриваются книги как на русском, так и на английском языке.

Wikimedia Foundation . 2010 .

Смотреть что такое "Язык функционального программирования" в других словарях:

язык прграммирования Лисп - Язык функционального программирования. Тематики информационные технологии в целом EN Lisp … Справочник технического переводчика

Универсальный язык программирования высокого уровня. Язык Лисп: относится к декларативным языкам функционального типа; предназначен для обработки символьных данных, представленных в виде списков. Основой языка являются функции и рекурсивные… … Финансовый словарь

У этого термина существуют и другие значения, см. Alice. Alice Семантика: функциональный Тип исполнения: компиляция в байткод для виртуальной машины Появился в: 2002 … Википедия

У этого термина существуют и другие значения, см. Scala. Scala Класс языка: Мультипарадигмальный: функ … Википедия

Oz Семантика: функциональный, процедурный, декларативный, объектно ориентированный, вычисления с ограничениями, Н модели, параллельные вычисления Тип исполнения: компилируемый Появился в: 1991 Автор(ы): Gert Smolka his students Релиз … Википедия

AWL (Alternative Web Language) Класс языка: мультипарадигмальный: функциональный, процедурный, объектно ориентированный Тип исполнения: интерпретируемый Появился в: 2005 г. Типизация данных: динамическая … Википедия

У этого термина существуют и другие значения, см. Леда (значения). Леда (Leda) мультипарадигмальный язык программирования, спроектированный Тимоти Баддом. Язык Leda исходно создавался с целью совмещения императивного программирования, объектно… … Википедия

Erlang Файл:Erlang logo.png Семантика: мультипарадигмальный: конкурентное, функциональное программирование Появился в: 1987 г. Автор(ы): Типизация данных: строгая, динамическая Основные реализации: E … Википедия

В языках функционального программирования основным конструктивным элементом является математическое понятие функции. Существует различия в понимании функции в математике и функции в программировании, в следствии чего нельзя отнести Си подобные… … Википедия

Python был задуман в 1980 х годах, а его создание началось в декабре 1989 года Гвидо ван Россумом в составе центра математики и информатики в Нидерландах. Язык Python был задуман как потомок языка программирования ABC, способный к обработке… … Википедия

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

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

К функциональным языкам программирования относят: Lisp, Miranda, Gofel, ML, Standard ML, Objective CAML, F#, Scala, Пифагор и др.

Процедурные языки программирования

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

Процедурные языки программирования: Ada, Basic, Си, КОБОЛ, Pascal, ПЛ/1, Рапира и др.

Стековые языки программирования

Стековый язык программирования − это язык программирования, в котором для передачи параметров используется машинная модель стека. Стековые языки программирования: Forth, PostScript, Java, C# и др. При использовании стека, в качестве основного канала передачи параметров между словами, элементы языка, естественным образом, образуют фразы (последовательное сцепление). Это свойство сближает данные языки с естественными языками.

Аспектно-ориентированные языки программирования 5) Декларативные языки программирования 6) Динамические языки программирования 7) Учебные языки программирования 8) Языки описания интерфейсов 9) Языки прототипного программирования 10) Объектно-ориентированные языки программирования 11) Логические языки программирования 12) Сценарные языки программирования 13) Эзотерические языки программирования

Стандартизация языков программирования. Парадигма программирования

Концепция языка программирования неотрывно связана с его реализацией. Для того чтобы компиляция одной и той же программы различными компиляторами всегда давала одинаковый результат, разрабатываются стандарты языков программирования. Организации, занимающиеся вопросами стандартизации: Американский национальный институт стандартов ANSI, Институт инженеров по электротехнике и электронике IEEE, Организация международных стандартов ISO.

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

Парадигмы программирования

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

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

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

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

Программирование – процесс создания компьютерных программ. В более широком смысле: спектр деят-сти, связ-ый с созданием и поддержанием в раб. состоянии программ - ПО ЭВМ.

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

Технология программир-я представляет собой набор технологических инструкций, включающих:

· указание последоват-сти выполнения технологич-х операций;

· перечисление условий, при кот-х выполняется та или иная операция;

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

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

Важным этапом создания прогр-го продукта явл. тестирование и отладка.

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

Тестирование − это процесс выполнения его программ на некотором наборе данных, для которого заранее известен результат применения или известны правила поведения этих программ.

Существуют следующие методы тестирования ПС:

1) Статическое тестирование – ручная проверка программы за столом.

2) Детерминированное тестир-е – при разл-х комбинациях исх-х данных.

3) Стохастическое – исх. данные выбир-ся произвольно, на выходе определяется качеств-е совпадение результатов или примерная оценка.

Стили программирования.

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

Существует несколько стилей программирования:

1. Процедурное программирование – это программирование, при котором программа представляет собой последовательность операторов. Используется в языках высокого уровня Basic, Fortran и др.
2. Функциональное программирование – это программирование, при котором программа представляет собой последовательность вызовов функций. Используется в языках Lisp и др.
3. Логическоепрограммирование – это программирование, при котором программа представляет собой совокупность определения соотношений между объектами. Используется в языках Prolog и др.

Объектно-ориентированноепрограммирование – это программирование, при котором основой программы является объект представляющий собой совокупность данных и правил их преобразования. Используется в языках Turbo-Pascal, C++ и др.

Функциональное программирование

1 Введение

Программы на традиционных языках программирования, таких как Си, Паскаль, Java и т.п. состоят их последовательности модификаций значений некоторого набора переменных, который называется состоянием . Если не рассматривать операции ввода-вывода, а также не учитывать того факта, что программа может работать непрерывно (т.е. без остановок, как в случае серверных программ), можно сделать следующую абстракцию. До начала выполнения программы состояние имеет некоторое начальное значение σ0 , в котором представлены входные значения программы. После завершения программы состояние имеет новое значение σ0 , включающее в себя то, что можно рассматривать как «результат» работы программы. Во время исполнения каждая команда изменяет состояние; следовательно, состояние проходит через некоторую конечную последовательность значений:

σ = σ0 → σ1 → σ2 → · · · → σn = σ0

Состояние модифицируется с помощью команд присваивания , записываемых в виде v=E или v:=E, где v - переменная, а E - некоторое выражение. Эти команды следуют одна за другой; операторы, такие как if и while, позволяют изменить порядок выполнения этих команд в зависимости от текущего значения состояния. Такой стиль программирования называютимперативным илипроцедурным .

Функциональное программирование представляет парадигму, в корне отличную от представленной выше модели. Функциональная программа представляет собой некоторое выражение (в математическом смысле); выполнение программы означает вычисление значения этого выражения.1 С учетом приведенных выше обозначений, считая что результат работы

1 Употребление термина «вычисление» не означает, что программа может оперировать только с числами; результатом вычисления могут оказаться строки, списки и вообще, любые допустимые в языке структуры данных.

императивной программы полностью и однозначно определен ее входом, можно сказать, что финальное состояние (или любое промежуточное) представляет собой некоторую функцию (в математическом смысле) от начального состояния, т.е. σ0 = f(σ). В функционально программировании используется именно эта точка зрения: программа представляет собой выражение, соответствующее функции f. Функциональные языки программирования поддерживают построение таких выражений, предоставляю широкий выбор соответствующих языковых конструкций.

При сравнении функционального и императивного подхода к программированию можно заметить следующие свойства функциональных программ:

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

Как следствие из предыдущего пункта, в функциональных программах нет циклов.

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

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

Вместо циклов функциональные программы широко используют рекурсивные функции.

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

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

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

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

Например, рассмотрим следующую программу на языке Haskell:

factorial n = if n == 0 then 1 else n * factorial (n - 1)

Практически сразу видно, что эта программа соответствует следующей частичной функции:

f(n) = n! n ≥ 0

(Здесь символ означает неопределенность функции, поскольку при отрицательных значениях аргумента программа не завершается.) Однако для программы на языке Си это соответствие не очевидно:

int x = 1; while (n > 0)

x = x * n; n = n - 1;

Следует также сделать замечание относительно употребления термина «функция» в таких языках как Си, Java и т.п. В математическом смысле «функции» языка Си не являются функциями, поскольку:

Их значение может зависеть не только от аргументов;

Результатом их выполнения могут быть разнообразные побочные эффекты (например, изменение значений глобальных переменных)

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

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

2 Основы лямбда-исчисления

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

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

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

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

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

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

Функциональные языки являются в основном удобной формой синтаксической записи для конструкций различных вариантов лямбдаисчисления. Некоторые современные языки (Haskell, Clean) имеют

100% соответствие своей семантики с семантикой подразумеваемых конструкций лямбда-исчисления.

В математике, когда необходимо говорить о какой-либо функции, принято давать этой функции некоторое имя и впоследствии использовать его, как, например, в следующем утверждении:

Пусть f: R → R определяется следующим выражением:

Тогда f0 (x) не интегрируема на интервале .

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

Пусть x = 2 и y = 4. Тогда xx = y.

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

где E - некоторое выражение, возможно, использующее переменную x.

Пример. λx.x2 представляет собой функцию, возводящую свой аргумент в квадрат.

Использование лямбда-нотации позволяет четко разделить случаи, когда под выражением вида f(x) мы понимаем саму функцию f и ее значение в точке x. Кроме того, лямбда-нотация позволяет формализовать практически все виды математической нотации. Если начать с констант и переменных и строить выражения только с помощью лямбда-выраже- ний и применений функции к аргументам, то можно представить очень сложные математические выражения.

Применение функции f к аргументу x мы будем обозначать как f x, т.е., в отличие от того, как это принято в математике, не будем использовать скобки2 . По причинам, которые станут ясны позднее, будем считать, что применение функции к аргументу ассоциативно влево, т.е. f x y

2 Заметим, что и в математике такие выражения, как sin x записываются без скобок.

означает (f(x))(y). В качестве сокращения для выражений вида λx.λy.E будем использовать запись λx y.E (аналогично для большего числа аргументов). Также будем считать, что «область действия» лямбда-выра- жения простирается вправо насколько возможно, т.е., например, λx.x y означает λx.(x y), а не (λx.x)y.

На первый взгляд кажется, что нам необходимо ввести специальное обозначение для функций нескольких аргументов. Однако существует операция каррирования 3 , позволяющая записать такие функции в обычной лямбда-нотации. Идея заключается в том, чтобы использовать выражения вида λx y.x + y. Такое выражение можно рассматривать как функцию R → (R → R), т.е. если его применить к одному аргументу, результатом будет функция, которая затем принимает другой аргумент. Таким образом:

(λx y.x + y) 1 2 = (λy.1 + y) 2 = 1 + 2.

Переменные в лямбда-выражениях могут бытьсвободными исвязанными . В выражении вида x2 + x переменная x является свободной; его значение зависит от значения переменной x и в общем случае ее нельзя

вать обозначение j, значение выражения не изменится.

Следует понимать, что в каком-либо подвыражении переменная может быть свободной (как в выражении под интегралом), однако во всем выражении она связана какой-либо операцией связывания переменной , такой как операция суммирования. Та часть выражения, которая находится «внутри» операции связывания, называетсяобластью видимости переменной.

В лямбда исчислении выражения λx.E[x] и λy.E[y] считаются эквивалентными (это называется α-эквивалентностью, и процесс преобразования между такими парами называют α-преобразованием). Разумеется, необходимо наложить условие, что y не является свободной переменной в E[x].

3 от фамилии известного логика Хаскелла Карри, в честь которого назван язык программирования Haskell

3 Лямбда-исчисление как формальная система

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

1. Переменные: обозначаются произвольными строками, составленными из букв и цифр.

2. Константы: также обозначаются строками; отличие от переменных будем определять из контекста.

3. Комбинации: , т.е. применения функции S к аргументу T ; и S и T могут быть произвольными лямбда-термами. Комбинация записывается как S T .

4. Абстракции произвольного лямбда-терма S по переменной x, обозначаемые как λx.S.

Таким образом, лямбда-терм определяется рекурсивно и его грамматику можно определить в виде следующей формы Бэкуса-Наура:

Exp = Var| Const| Exp Exp| λ Var . Exp

В соответствие с этой грамматикой лямбда-термы представляются в виде синтаксических деревьев, а не в виде последовательности символов. Отсюда следует, что соглашения об ассоциативности операции применения функции, эквивалентность выражений вида λx y.S и λx.λy.S, неоднозначность в именах констант и переменных проистекают только из необходимости представления лямбда-термов в удобном человеку виде, и не являются частью формальной системы.

3.1 Свободные и связанные переменные

В данном разделе мы формализуем данное ранее интуитивное представление о свободных и связанных переменных. Множество свободных

переменных F V (S) лямбда-терма S можно определить рекурсивно следующим образом:

Аналогично множество связанных переменных BV (S) определяется следующими формулами:

BV (x) =

BV (c) =

BV (S T) = BV (S) BV (T)

BV (λx.S) = BV (S) {x}

Здесь предполагается, что c - некоторая константа.

Пример. Для терма S = (λx y.x) (λx.z x) можно показать, что F V (S) = {z} и

BV (S) = {x, y}.

3.2 Подстановки

Интуитивно ясно, что применение терма λx.S как функции к аргументу T дает в результате терм S, в котором все свободные вхождения переменной x заменены на T . Как ни странно, формализовать это интуитивное представление оказывается нелегко.

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

3.3 Конверсия

Лямбда-исчисление основано на трех операциях конверсии, которые позволяют переходить от одного терма к другому, эквивалентному ему. По сложившейся традиции эти конверсии обозначают греческими буквами α, β и η. Они определяются следующим образом:

α-конверсия: λx.S −→ λy.S при условии, что y / F V (S).

Например, λu.u v −→ λw.w u.

β-конверсия: (λx.S) T −→ S.

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

3.4 Равенство лямбда-термов

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

под ней»:

Следует отличать понятие равенства, определяемое этими формулами, от понятия синтаксической эквивалентности, которую мы будем обозначать специальным символом ≡. Например, λx.x 6≡λy.y, но λx.x = λy.y. Часто можно рассматривать синтаксическую эквивалентность термов с точностью до α-конверсий. Такую эквивалентность будем обозначать символом ≡α . Это отношение определяется так же, как равенство лямбда-термов, за тем исключением, что из всех конверсий допустимы только α-конверсии. Таким образом, λx.x ≡α λy.y.

3.5 Экстенсиональность

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

• Перевод

- ООП не сможет больше спасать нас от «Облачных монстров».

Примечание переводчика: Есть два понятия - параллельность (выполнение одновременно, независимо) и конкурентность (выполнение по шагам, поочерёдно, но одновременно несколько задач) и как всегда, мне пришлось поломать голову подобрая правильные термины.

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

Возможно вы уже слышали такое выражение, вроде: “Clojure”, “Scala”, “Erlang” или даже “Java теперь имеет лямбды”. И вы имеете хоть и отдалённое представление о «Функциональном программировании». Если вы участник какого-либа программисткого сообщества, тогда эта тема могла уже вами обсуждаться.

Если вы поищите в Google по словосочетанию «Функциональное программирование», вы не увидите что-то нового. Второй язык из созданных ранее уже охватывает эту тему, он был создан в 50-ых и называется Lisp. Тогда, какого чёрта, эта тема стала популярна только сейчас? Всего то 60 лет спустя?

В начале, компьютеры были очень медленными

Верите вы этому или нет, но компьютеры были нааамного медленнее чем DOM. Нет, действительно. И в то-же время были 2 основные идеи в соглашении по дизайну и реализации языков программирования:

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

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

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

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

Что такое функциональное программирование?

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

Как отмечает Дэвид Мертц (David Mertz) в своей статье о функциональном программировании на Python , "функциональное программирование - программирование на функциональных языках ( LISP , ML, OCAML, Haskell, ...)", основными атрибутами которых являются:

• "Наличие функций первого класса" (функции наравне с другими объектами можно передавать внутрь функций).
• Рекурсия является основной управляющей структурой в программе.
• Обработка списков (последовательностей).
• Запрещение побочных эффектов у функций, что в первую очередь означает отсутствие присваивания (в "чистых" функциональных языках)
• Запрещение операторов, основной упор делается на выражения. Вместо операторов вся программа в идеале - одно выражение с сопутствующими определениями.
• Ключевой вопрос: что нужно вычислить, а не как .
• Использование функций более высоких порядков (функции над функциями над функциями).

Функциональная программа

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

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