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

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

К функциональным языкам программирования относят: 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++ и др.

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

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

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

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

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

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

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

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

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

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

• Перевод

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

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

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

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

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

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

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

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

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

Языки программирования, о которых не каждый знает

Я начал программировать еще в детстве, и годам к двадцати пяти мне казалось, что я все знаю и понимаю. Объектно ориентированное программирование стало частью моего мозга, все мыслимые книги о промышленном программировании были прочитаны. Но у меня оставалось такое ощущение, будто я что-то упустил, что-то очень тонкое и необыкновенно важное. Дело в том, что, как и многих в девяностые годы, в школе меня учили программировать на Pascal (о да, слава Turbo Pascal 5.5! - Прим. ред.), потом был C и C++. В университете Fortran и потом Java, как основной инструмент на работе. Я знал Python и еще несколько языков, но все это было не то. А серьезного образования в области Computer Science у меня не было. Однажды во время перелета через Атлантику я не мог заснуть, и мне захотелось что-то почитать. Каким-то волшебным образом у меня под рукой оказалась книга про язык программирования Haskell. Мне кажется, именно тогда я понял истинный смысл выражения «красота требует жертв».

Теперь, когда меня спрашивают, как я выучил Haskell, я так и говорю: в самолете. Этот эпизод изменил мое отношение к программированию вообще. Конечно, после первого знакомства многие вещи казались мне не вполне понятными. Пришлось напрячься и изучить вопрос более тщательно. И знаешь, прошло десять лет, многие функциональные элементы стали частью промышленных языков, лямбда-функции уже есть даже в Java, вывод типов - в С++, сопоставление с образцом - в Scala. Многие думают, что это какой-то прорыв. И в этой серии статей я расскажу тебе про приемы функционального программирования, используя разные языки и их особенности.

Интернетчики часто на потеху публике составляют всякие списки и топы. Например, «список книг, которые ты должен прочесть до тех пор, пока тебе не исполнилось тридцать». Если бы передо мной стояла задача сделать список книг по программированию, которые ты должен прочесть до тех пор, пока тебе сколько-то там не исполнилось, то первое место, безусловно, досталось бы книге Абельсона и Сассмана «Структура и интерпретация компьютерных программ» . Мне даже иногда кажется, что компилятор или интерпретатор любого языка должен останавливать каждого, кто не читал эту книгу.

Поэтому если и есть язык, с которого нужно начинать изучение функционального программирования, так это Lisp. Вообще, это целое семейство языков, куда входит довольно популярный сейчас язык для JVM под названием Clojure . Но в качестве первого функционального языка он не особо подходит. Для этого лучше использовать язык Scheme , который был разработан в MIT и до середины двухтысячных годов служил основным языком для обучения программированию. Хотя сейчас вводный курс с тем же названием, что упомянутая книга, был заменен на курс по Python, она все еще не потеряла своей актуальности.

Постараюсь кратко рассказать о языке Scheme и вообще об идее, стоящей за языками данной группы. Несмотря на то что Lisp очень старый (из всех языков высокого уровня старше только Fortran), именно в нем впервые стали доступны многие методы программирования, применяемые сейчас. Далее я буду использовать название Lisp, имея в виду конкретную реализацию - Scheme.

Синтаксис за две минуты

Синтаксис в языке Lisp, хм, слегка спорный. Дело в том, что идея, лежащая в основе синтаксиса, крайне проста и построена на основе так называемых S-выражений . Это префиксная запись, в которой привычное тебе выражение 2 + 3 записывается как (+ 2 3) . Это может показаться странным, но на практике дает некоторые дополнительные возможности. Кстати, (+ 2 10 (* 3.14 2)) тоже работает:). Таким образом, вся программа - это набор списков, в которых используется префиксная нотация. В случае языка Lisp сама программа и абстрактное синтаксическое дерево - «если вы понимаете, о чем я» 😉 - по сути, ничем не отличаются. Такая запись делает синтаксический анализ программ на Lisp очень простым.
Раз уж мы говорим о языке программирования, то следует сказать о том, как определять функции в этом языке.

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

Самый простой способ определить функцию - это написать следующий код. Начнем с неприлично простого:

(define (sq-roots a b c) (let ((D (- (* b b) (* 4 a c)))) (if (< D 0) (list) (let ((sqrtD (sqrt D))) (let ((x1 (/ (- (- b) sqrtD) (* 2.0 a))) (x2 (/ (+ (- b) sqrtD) (* 2.0 a)))) (list x1 x2))))))

Да, это именно то, что ты подумал, - решение квадратного уравнения на Scheme. Но этого более чем достаточно, чтобы разглядеть все особенности синтаксиса. Здесь sq-roots - это название функции от трех формальных параметров.

На первый взгляд в конструкции let , которая используется для определения локальных переменных, слишком много скобок. Но это не так, просто сначала мы определяем список переменных, а затем выражение, в котором эти переменные используются. Здесь (list) - это пустой список, который мы возвращаем, когда корней нет, а (list x1 x2) - это список из двух значений.

Теперь о выражениях. В нашей функции sq-roots мы использовали конструкцию if . Вот здесь-то и начинается функциональное программирование.

Дело в том, что в отличие от императивных языков, таких как C, в функциональных языках if - это выражение, а не оператор. На практике это означает, что у него не может отсутствовать ветка else. Потому что выражение всегда должно иметь значение.

Нельзя рассказать про синтаксис, не поговорив о синтаксическом сахаре . В языках программирования синтаксическим сахаром называют конструкции, которые не являются необходимыми, а лишь облегчают чтение и переиспользование кода. Для начала приведем классический пример из языка C. Многие знают, что массивы не обязательное средство выражения, так как есть указатели. Да, действительно, массивы реализованы через указатели, и a[i] для языка C - это то же самое, что и *(a + i) . Данный пример вообще довольно необычный, с ним связан забавный эффект: так как операция сложения остается коммутативной в случае указателей, то последнее выражение - это то же самое, что и *(i + a) , а это может быть получено при удалении синтаксического сахара из выражения i[a] ! Операция удаления синтаксического сахара в английском языке называется специальным словом desugaring .

Возвращаясь к языку Scheme, следует привести важный пример синтаксического сахара. Для определения переменных, как и в случае функций, используется ключевое слово (в Lisp и Scheme это называется специальной формой) define . К примеру, (define pi 3.14159) определяет переменную pi . Вообще говоря, точно так же можно и определять функции:

(define square (lambda (x) (* x x)))

это то же самое, что и

(define (square x) (* x x))

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

Если посмотреть на let с точки зрения лямбда-выражения, то легко заметить следующее соответствие:

(let ((x 5) (y 2)) (* x y)) (apply (lambda (x y) (* x y)) (list 5 2))

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

Функциональные языки бывают чистыми и нечистыми . Чистые функциональные языки сравнительно редки, к ним относятся в первую очередь Haskell и Clean . В чистых языках нет побочных эффектов. На практике это означает отсутствие присваивания и ввода-вывода в том виде, к которому мы привыкли. Это создает ряд трудностей, хотя в уже упомянутых языках это решено довольно хитроумно, и на этих языках пишут код с большим количеством ввода-вывода. Языки типа Lisp, OCaml или Scala допускают функции с побочными эффектами, и в этом смысле данные языки зачастую более практичны.

Наша задача - изучить основные приемы функционального программирования на Scheme. Поэтому мы будем писать чисто функциональный код, без использования генератора случайных чисел, ввода-вывода и функции set! , которая позволят менять значения переменных. Обо всем этом можно прочитать в книге SICP . Сейчас остановимся на самом существенном для нас.

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

Пускай у нас есть две функции - succ и prev . Первая возвращает число, на 1 большее, чем аргумент, а вторая - на 1 меньшее. Теперь попробуем определить операцию сложения, причем двумя способами:

(define (add x y) (if (eq? y 0) x (add (succ x) (prev y)))) (define (add-1 x y) (if (eq? y 0) x (succ (add-1 x (prev y)))))

В чем разница между первым и вторым случаем? Дело в том, что если рассмотреть способ вычисления для первого случая по шагам, то можно увидеть следующее:

(add 3 4) => (add 4 3) => (add 5 2) => (add 6 1) => (add 7 0) => 7

Во втором случае мы будем иметь примерно следующее:

(add-1 3 4) => (succ (add-1 3 3)) => (succ (succ (add-1 3 2))) => (succ (succ (succ (add-1 3 1)))) => (succ (succ (succ (succ (add-1 3 0))))) => (succ (succ (succ (succ 3)))) => (succ (succ (succ 4))) => (succ (succ 5)) => (succ 6) => 7

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

Списки

Один из важнейших элементов функционального программирования, наряду с рекурсией, - списки . Они обеспечивают основу для сложных структур данных. Как и в других функциональных языках, списки являются односвязными по принципу голова - хвост. Для создания списка используется функция cons , а для доступа к голове и хвосту списка - функции car и cdr соответственно. Так, список (list 1 2 3) - это не что иное, как (cons 1 (cons 2 (cons 3 "()))) . Здесь "() - пустой список. Таким образом, типичная функция обработки списка выглядит так:

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))

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

Функции высших порядков

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

(define (map f lst) (if (null? lst) lst (cons (f (car lst)) (map f (cdr lst)))))

Функция map применяет функцию f к каждому элементу списка. Как бы это странно ни выглядело, но теперь мы можем выразить функцию вычисления длины списка length через sum и map:

(define (length lst) (sum (map (lambda (x) 1) lst)))

Если ты вдруг сейчас решил, что все это как-то слишком просто, то давай подумаем вот над чем: как сделать реализацию списков, используя функции высших порядков?

То есть нужно реализовать функции cons , car и cdr так, чтобы они удовлетворяли следующему соотношению: для любого списка lst верно, что значение (cons (car lst) (cdr lst)) совпадает с lst . Это можно сделать следующим образом:

(define (cons x xs) (lambda (pick) (if (eq? pick 1) x xs))) (define (car f) (f 1)) (define (cdr f) (f 2))

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

Использование quote и метапрограммирование

Одна приятная особенность языка Lisp делает его необыкновенно удобным для написания программ, которые занимаются преобразованием других программ. Дело в том, что программа состоит из списков, а список - это основная структура данных в языке. Существует способ просто «закавычить» текст программы, чтобы она воспринималась как список атомов.

Атомы - это просто символьные выражения, к примеру ("hello "world) , что то же самое, что и "(hello world) , или в полной форме (quote (hello world)) . Несмотря на то что в большинстве диалектов Lisp есть строки, иногда можно обходиться quote . Что более важно, с помощью такого подхода можно упростить кодогенерацию и обработку программ.

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

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

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

(define (deriv exp var) (cond ((number? exp) 0) ((variable? exp) (if (same-variable? exp var) 1 0)) ((sum? exp) (make-sum (deriv (addend exp) var) (deriv (augend exp) var))) ((product? exp) (make-sum (make-product (multiplier exp) (deriv (multiplicand exp) var)) (make-product (deriv (multiplier exp) var) (multiplicand exp)))) (else (error "unknown expression type - DERIV" exp))))

Здесь функция deriv представляет собой реализацию алгоритма дифференцирования так, как его проходят в школе. Данная функция требует реализации функций number? , variable? и так далее, которые позволяют понять, какую природу имеет тот или иной элемент выражения. Также нужно реализовать дополнительные функции make-product и make-sum . Здесь используется пока неизвестная нам конструкция cond - это аналог оператора switch в таких языках программирования, как C и Java.

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

(define (variable? x) (symbol? x)) (define (same-variable? v1 v2) (and (variable? v1) (variable? v2) (eq? v1 v2))) (define (make-sum a1 a2) (list "+ a1 a2)) (define (make-product m1 m2) (list "* m1 m2)) (define (sum? x) (and (pair? x) (eq? (car x) "+))) (define (addend s) (cadr s)) (define (augend s) (caddr s)) (define (product? x) (and (pair? x) (eq? (car x) "*))) (define (multiplier p) (cadr p)) (define (multiplicand p) (caddr p))

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

Если воспользоваться интерактивным интерпретатором Scheme, то легко убедиться, что полученный код работает правильно, но без упрощения выражений:

(deriv "(+ x 3) "x) => (+ 1 0) (deriv "(* (* x y) (+ x 3)) "x) => (+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+ x 3)))

Для тривиальных случаев (например, умножение на 0) задача упрощения решается довольно легко. Этот вопрос остается читателю. Большинство примеров в этой статье взяты из книги SICP, поэтому в случае возникновения трудностей можно просто обратиться к источнику (книга находится в открытом доступе).

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

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

(define (desugar-define def) (let ((fn-args (cadr def)) (body (caddr def))) (let ((name (car fn-args)) (args (cdr fn-args))) (list "define name (list "lambda args body)))))

Эта функция прекрасно работает с правильно сформированными определениями функций:

(desugar-define "(define (succ x) (+ x 1))) => (define succ (lambda (x) (+ x 1)))

Однако это не работает для обычных определений, таких как (define x 5) .
Если мы хотим удалить синтаксический сахар в большой программе, содержащей множество различных определений, то мы должны реализовать дополнительную проверку:

(define (sugared? def) (and (eq? (car def) "define) (list? (cadr def))))

Такую проверку можно встроить прямо в функцию desugar-define , сделав так, чтобы в случае, если определение не нуждается в удалении синтаксического сахара, оно просто бы не менялось (данное тривиальное упражнение остается читателю). После чего можно обернуть всю программу в список и использовать map:

(map desugar-define prog)

Заключение

В данной статье я не ставил себе задачу рассказать про Scheme сколь-нибудь подробно. Мне прежде всего хотелось показать несколько интересных особенностей языка и привлечь читателя к изучению функционального программирования. Этот чудесный язык при всей его простоте имеет свое очарование и особенности, которые делают программирование на нем очень увлекательным. Что касается инструмента для работы со Scheme, то сильные духом могут замахнуться на MIT-Scheme , а остальные - пользуйтесь прекрасной учебной средой Dr. Racket . В одной из следующих статей я обязательно расскажу, как написать собственный интерпретатор Scheme.

Отложенные вычисления

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

Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим. На самом деле, в таких языках порядок вычисления строго определен. В качестве примера строгих языков можно привести Scheme, Standard ML и Caml.

Языки, использующие отложенные вычисления, называются нестрогими. Haskell - нестрогий язык, так же как, например, Gofer и Miranda. Нестрогие языки зачастую являются чистыми.

Очень часто строгие языки включают в себя средства поддержки некоторых полезных возможностей, присущих нестрогим языкам, например бесконечных списков. В поставке Standard ML присутствует специальный модуль для поддержки отложенных вычислений. А Objective Caml помимо этого поддерживает дополнительное зарезервированное слово lazy и конструкцию для списков значений, вычисляемых по необходимости.

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

§ Lisp (List processor). Считается первым функциональным языком программирования. Нетипизирован. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. Существует объектно-ориентированный диалект языка - CLOS.

§ ISWIM (If you See What I Mean). Функциональный язык-прототип. Разработан Ландиным в 60-х годах XX века для демонстрации того, каким может быть язык функционального программирования. Вместе с языком Ландин разработал и специальную виртуальную машину для исполнения программ на ISWIM’е. Эта виртуальная машина, основанная на вызове-по-значению, получила название SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.

§ Scheme . Диалект Lisp’а, предназначенный для научных исследований в области computer science. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем Common Lisp.

§ ML (Meta Language). Семейство строгих языков с развитой полиморфной системой типов и параметризуемыми модулями. ML преподается во многих западных университетах (в некоторых даже как первый язык программирования).

§ Standard ML . Один из первых типизированных языков функционального программирования. Содержит некоторые императивные свойства, такие как ссылки на изменяемые значения и поэтому не является чистым. При вычислениях использует вызов-по-значению. Очень интересная реализация модульности. Мощная полиморфная система типов. Последний стандарт языка - Standard ML-97, для которого существует формальные математические определения синтаксиса, а также статической и динамической семантик языка.

§ Caml Light и Objective Caml . Как и Standard ML принадлежит к семейству ML. Objective Caml отличается от Caml Light в основном поддержкой классического объектно-ориентированного программирования. Также как и Standard ML строгий, но имеет некоторую встроенную поддержку отложенных вычислений.

§ Miranda . Разработан Дэвидом Тернером, в качестве стандартного функционального языка, использовавшего отложенные вычисления. Имеет строгую полиморфную систему типов. Как и ML преподаётся во многих университетах. Оказал большое влияние на разработчиков языка Haskell.

§ Haskell . Один из самых распространённых нестрогих языков. Имеет очень развитую систему типизации. Несколько хуже разработана система модулей. Последний стандарт языка - Haskell-98.

§ Gofer (GOod For Equational Reasoning). Упрощённый диалект Haskell’а. Предназначен для обучения функциональному программированию.

§ Clean . Специально предназначен для параллельного и распределённого программирования. По синтаксису напоминает Haskell. Чистый. Использует отложенные вычисления. С компилятором поставляется набор библиотек (I/O libraries), позволяющих программировать графический пользовательский интерфейс под Win32 или MacOS.

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

Функциональный подход породил целое семейство языков, родоначальником которых, как уже отмечалось, стал язык программирования LISP. Позднее, в 70-х годах, был разработан первоначальный вариант языка ML, который впоследствии развился, в частности, в SML, а также ряд других языков. Из них, пожалуй, самым "молодым" является созданный уже совсем недавно, в 90-х годах, язык Haskell.

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

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

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

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

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

Часто к ним относят нелинейную структуру программы и относительно невысокую эффективность реализации. Однако первый недостаток достаточно субъективен, а второй успешно преодолен современными реализациями, в частности, рядом последних трансляторов языка SML, включая и компилятор для среды Microsoft .NET.

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

Заметим, что под термином "функция" в математической формализации и программной реализации имеются в виду различные понятия.

Так, математической функцией f с областью определения A и областью значений B называется множество упорядоченных пар

таких, что если

(a,b 1) f и (a,b 2) f,

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

Для формализации понятия "функция" была построена математическая теория, известная под названием лямбда-исчисления. Более точно это исчисление следует именовать исчислением лямбда-конверсий.

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

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

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

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

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

Развитием ранних языков программирования стали языки функционального программирования с сильной типизацией, характерным примером здесь является классический ML, и его прямой потомок SML. В языках с сильной типизацией каждая конструкция (или выражение) должна иметь тип.

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

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

На современном этапе развития возникли языки функционального программирования "нового поколения" со следующими расширенными возможностями: сопоставление с образцом (Scheme, SML, Miranda, Haskell), параметрический полиморфизм (SML) и так называемые "ленивые" (по мере необходимости) вычисления (Haskell, Miranda, SML).

Семейство языков функционального программирования довольно многочисленно. Об этом свидетельствует не столько значительный список языков, сколько тот факт, что многие языки дали начало целым направлениям в программировании. Напомним, что LISP дал начало целому семейству языков: Scheme, InterLisp, COMMON Lisp и др.

Не стал исключением и язык программирования SML, который был создан в форме языка ML Р. Милнером (Robin Milner) в MIT (Massachusetts Institute of Technology) и первоначально предназначен для логических выводов, в частности, доказательства теорем. Язык отличается строгой типизацией, в нем отсутствует параметрический полиморфизм.

Развитием "классического" ML стали сразу три современных языка с практически одинаковыми возможностями (параметрический полиморфизм, сопоставление с образцом, "ленивые" вычисления). Это язык SML, разработанный в Великобритании и США, CaML, созданный группой французских ученых института INRIA, SML/NJ – диалект SML из New Jersey, а также российская разработка – mosml ("московский" диалект ML).

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

1. простота тестирования и верификации программного кода на основе возможности построения строгого математического доказательства корректности программ;

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

3. безопасная типизация: недопустимые операции с данными исключены;

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

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

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

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

1. интеграция различных языков функционального программирования (при этом максимально используются преимущества каждого из языков, в частности, Scheme предоставляет механизм сопоставления с образцом, а SML – возможность вычисления по мере необходимости);

2. интеграция различных подходов к программированию на основе межъязыковой инфраструктуры Common Language Infrastructure, или CLI (в частности, возможно использование C# для обеспечения преимуществ объектно-ориентированного подхода и SML – функционального, как в настоящем курсе);

3. общая унифицированная система типизации Common Type System, CTS (единообразное и безопасное управление типами данных в программе);

4. многоступенчатая, гибкая система обеспечения безопасности программного кода (в частности, на основе механизма сборок).

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

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

Многие современные языки функционального программирования являются строго типизированными языками (строгая типизация). Строгая типизация обеспечивает большую безопасность. Многие ошибки могут быть исправлены на стадии компиляции, поэтому стадия отладки и общее время разработки программ сокращаются. Строгая типизация позволяет компилятору генерировать более эффективный код и тем самым ускорять выполнение программ. Наряду с этим, существуют функциональные языки с динамической типизацией. Тип данных в таких языках определяется во время выполнения программы (гл. 3). Иногда их называют «безтиповыми». К их, достоинствам следует отнести то, что программы, написанные на этих языках, обладают большей общностью. Недостатком можно считать отнесение многих ошибок на стадию выполнения программы и связанную с этим необходимость применения функций проверки типов и соответствующее сокращение общности программы. Типизированные языки способствуют генерации более «надежного» кода, а типизированные более «общего».

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

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

Common Lisp. Версия Лиспа, которая с 1970 г. может считаться стандартом языка, благодаря поддержке со стороны лаборатории искусственного интеллекта Массачусетского технологического института, безтиповый, энергичный, с большим набором императивных включений, допускающих присваивание, разрушение структур. Практический. Достаточно сказать, что на Лиспе был написан векторный графический редактор Автокад.

Scheme. Диалект Лиспа, предназначенный для научных исследований в области компьютерной науки и обучения функциональному программированию. Благодаря отсутствию императивных включений язык получился намного меньше, чем Common Lisp. Восходит к языку, разработанному Дж. Маккарти в 1962 г. Академический, безтиповый, энергичный, чистый.

Refal. Семейство языков, разработанных В. Ф. Турчиным. Старейший член этого семейства впервые реализован в 1968 году в России. Широко используется и поныне в академических кругах. Содержит элементы логического программирования (сопоставление с образцом). Поэтому язык Refal предлагается в данном учебном пособии в качестве языка для самостоятельного изучения.

Miranda. Строго типизированный, поддерживает типы данных пользователя и полиморфизм. Разработан Тернером на основе более ранних языков SALS и KRC. Имеет ленивую семантику. Без императивных включений.

Haskell. Развитие языка пришлось на конец прошлого века. Широко известен в академических кругах. В некоторых западных университетах используется в качестве основного языка для изучения студентами. Один из наиболее мощных функциональных языков. Ленивый язык. Чисто функциональный язык. Типизированный. Haskell – отличный инструмент для обучения и экспериментов со сложными функциональными типами данных. Программы, написанные на Haskell, имеют значительный размер объектного кода и невысокую скорость исполнения.

Clean. Диалект Haskell, приспособленный к нуждам практического программирования. Как и Haskell, является ленивым чисто функциональным языком, содержит классы типов. Но Clean также содержит интересные особенности, которые не имеют эквивалента в Haskell. Например, императивные возможности в Clean основаны на уникальных типах, идея которых заимствована из линейной логики (linear logic). Clean содержит механизмы, которые позволяют значительно улучшить эффективность программ. Сред этих механизмов явное подавление отложенных вычислений. Реализация Clean является коммерческим продуктом, но свободная версия доступна для исследовательских и образовательных целей.

ML(Meta Language). Разработан группой программистов во главе с Робертом Милиером в середине 70-х гг. в Эдинбурге (Edinburgh Logic for Computable Functions). Идея языка состояла в создании механизма для построения формальных доказательств в системе логики для вычислимых функций. В 1983 язык был пересмотрен дополнен такими концепциями, как модули. Стал называться стандартный ML. ML – это сильно типизированный язык со статическим контролем типов и аппликативным выполнением программ. Он завоевал большую популярность в исследовательских кругах и в области компьютерного образования.