70 ресурсов по функциональному программированию


Оглавление (нажмите, чтобы открыть):

Лекции по функциональному программированию

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

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

Однако даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться обыкновенные люди, т.к. мнемокоды все еще оставались слишком сложными, тем более что всякий ассемблер был жёстко связан с архитектурой, на которой он исполнялся. Таким образом, следующим шагом после ассемблера стали так называемые императивные языки высокого уровня (BASIC, Pascal, C, Ada и прочие, включая объектно-ориентированные). Императивными такие языки были названы по той простой причине, что главным их свойством является ориентированность, в первую очередь, на последовательное исполнение инструкций оперирующих с памятью (т.е. присваиваний) и итеративные циклы. Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности (предписания).

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

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

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

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

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

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

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

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

В первую очередь большинство функциональных языков программирования реализуются как интерпретаторы, следуя традициям Lisp’а. Интерпретаторы удобны для быстрой отладки программ, исключая длительную фазу компиляции, тем самым укорачивая обычный цикл разработки. Однако с другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения в несколько раз. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, Objective Caml) или код на C/C++ (например, Glasgow Haskell Compiler). Что показательно, практически каждый компилятор с функционального языка реализован на этом же самом языке.

В этом курсе для описания примеров функционального программирования будет использоваться либо некий абстрактный функциональный язык, приближенный к математической нотации, либо Haskell, бесплатные компиляторы которого можно скачать с сайта www.haskell.org.

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

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

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

Краткость и простота

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

Пример 1. Быстрая сортировка Хоара на C.

Пример 2. Быстрая сортировка Хоара на абстрактном функциональном языке.

Пример 2 следует читать так:

1. Если список пуст, то результатом также будет пустой список.

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

Пример 3. Быстрая сортировка Хоара на языке Haskell.

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

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

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

Пример 4. Определение N-ого числа Фибоначчи.

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

Строгая типизация

Практически все современные языки программирования являются строго типизированными языками (возможно, за исключением JavaScript и его диалектов, не существует императивных языков без понятия «тип»). Строгая типизация обеспечивает безопасность. Программа, прошедшая проверку типов просто не может выпасть в операционную систему с сообщением, подобным «access violation», особенно это касается таких языков, как C/C++ и Object Pascal, где применение указателей является типичным способом использования языка. В функциональных языках большая часть ошибок может быть исправлена на стадии компиляции, поэтому стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерировать более эффективный код и тем самым ускорять выполнение программ.

Рассматривая пример с быстрой сортировкой Хоара, можно увидеть, что помимо уже упомянутых отличий между вариантом на языке C и вариантом на абстрактном функциональном языке, есть ещё одно важное отличие: функция на C сортирует список значений типа int (целых чисел), а функция на абстрактном функциональном языке — список значений любого типа, который принадлежит к классу упорядоченных величин. Поэтому последняя функция может сортировать и список целых чисел, и список чисел с плавающей точкой, и список строк. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать quickSort и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным полиморфизмом, и поддерживается большинством функциональных языков.

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

В языке C++ имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные quickSort. В стандартную библиотеку C++ STL входит такая функция и множество других полиморфных функций. Но шаблоны C++, как и родовые функции Ada, на самом деле порождают множество перегруженных функций, которые, кстати, компилятор должен каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция quickSort — это одна единственная функция.

В некоторых языках, например в Ada, строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Чтобы избежать этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста. Этот механизм называется механизмом вывода типов. Известно несколько таких механизмов, однако большинство из них являются разновидностями модели типизации Хиндли-Милнера, разработанной в начале 80-х годов XX века. Таким образом, в большинстве случаев можно не указывать типы функций.

Модульность

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

Функции — это значения

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

Можно воспользоваться функцией map для возведения в квадрат всех элементов некоторого списка:

Результатом выполнения этой инструкции будет список [1, 4, 9, 16].

Чистота (отсутствие побочных эффектов)

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

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

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

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

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

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

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

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

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

Решаемые задачи

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

1. Получение остаточной процедуры.

Если даны следующие объекты:

x3, . xn — неизвестные значения параметров.

Требуется получить остаточную процедуру P1 (x3, . xn). Эта задача решается только на узком классе программ.

2. Построение математического описания функций.

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

3. Определение формальной семантики языка программирования.

4. Описание динамических структур данных.

5. Автоматическое построение «значительной» части программы по описанию структур данных, которые обрабатываются создаваемой программой.

6. Доказательство наличия некоторого свойства программы.

7. Эквивалентная трансформация программ.

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

Справочный материал

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

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

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.

Internet-ресурсы по функциональному программированию

www.haskell.org — очень насыщенный сайт, посвящённый функциональному программированию в общем и языку Haskell в частности. Содержит различные справочные материалы, список интерпретаторов и компиляторов Haskell’а (в настоящий момент все интерпретаторы и компиляторы бесплатны). Кроме того, имеется обширный список интересных ссылок на ресурсы по теории функционального программирования и другим языкам (Standard ML, Clean).

cm.bell-labs.com/cm/cs/what/smlnj — Standard ML of New Jersey. Очень хороший компилятор. В бесплатный дистрибутив помимо компилятора входят утилиты MLYacc и MLLex и библиотека Standard ML Basis Library. Отдельно можно взять документацию по компилятору и библиотеке.

www.harlequin.com/products/ads/ml/ — Harlequin MLWorks, коммерческий компилятор Standard ML. Однако в некоммерческих целях можно бесплатно пользоваться версией с несколько ограниченными возможностями.

caml.inria.fr — институт INRIA. Домашний сайт команды разработчиков языков Caml Light и Objective Caml. Можно бесплатно скачать дистрибутив Objective Caml, содержащий интерпретатор, компиляторы байт-кода и машинного кода, Yacc и Lex для Caml, отладчик и профайлер, документацию, примеры. Качество компилированного кода у этого компилятора очень хорошее, по скорости опережает даже Standard ML of New Jersey.

clean/ — содержит дистрибутив компилятора с языка Clean. Компилятор коммерческий, но допускается бесплатное использование в некоммерческих целях. Из того, что компилятор коммерческий, следует его качество (очень быстр), наличие среды разработчика, хорошей документации и стандартной библиотеки.

Список литературы

1. Хювёнен Э., Сеппенен И. Мир Lisp’а. В 2-х томах. М.: Мир, 1990.

2. Бердж В. Методы рекурсивного программирования. М.: Машиностроение, 1983.

3. Филд А., Харрисон П. Функциональное программирование. М.: Мир, 1993.

4. Хендерсон П. Функциональное программирование. Применение и реализация. М.: Мир, 1983.

5. Джонс С., Лестер Д. Реализация функциональных языков. М.: Мир, 1991.

6. Henson M. Elements of functional languages. Dept. of CS. University of Sassex, 1990.

7. Fokker J. Functional programming. Dept. of CS. Utrecht University, 1995.

8. Thompson S. Haskell: The Craft of Functional Programming. 2-nd edition, Addison-Wesley, 1999.

9. Bird R. Introduction to Functional Programming using Haskell. 2-nd edition, Prentice Hall Press, 1998.

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

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

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


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

Технология программирования и основные этапы ее развития

Тема 1. Технология программирования. Основные понятия и подходы

Лекция 1

Приведите пример и прокомментируйте структурные схемы САР непосредственного цифрового управления.

Приведите пример и прокомментируйте самонастраивающуюся схемы САР со стабилизацией динамической характеристики.

Приведите пример и прокомментируйте самонастраивающуюся схемы САР со стабилизацией частотной характеристики.

Приведите пример и прокомментируйте самонастраивающуюся схемы САР с анализом отклонения показателя качества.

Приведите пример и прокомментируйте самонастраивающуюся схемы САР с подстраиваемой моделью.

Приведите пример и прокомментируйте самонастраивающуюся схемы САР с контролем временной характеристики.

Приведите пример и прокомментируйте самонастраивающуюся схемы САР с контролем АЧХ.

Приведите пример экстремального регулирования сжигания топлива в термической печи.

6. Приведите пример и прокомментируйте самонастраивающуюся схемы САР с обобщённым настраивым объектом.

Литература по лекции 7.

1.Ульянов В,А., Леушин И.О., Гущин В,Н. Технологические измерения, автоматика и управление в технических системах. Ч.1. Н.Новгород: НГТУ, 2000. –С.7-77.

2.Майзель М.М. Автоматика и системы управления производственными процессами. М.: Высшая школа,1972. С.85-264.

3.Глинков Г.М., Косырев А.И., Шевцов Е.К. Контроль и автоматизация металлургических процессов. М.: Металлургия, 1989. С.94-143.

4.Воронов А.А., Титов В.К., Новогранов Б.Н. Основы теории автоматического регулирования и управления. М.: Высшая школа, 1977. С.154-356.

5.Коганов В.Ю., Блинов О.М., Беленький А.М. Автоматизация управления металлургическими процессами. М.: Металлургия, !974. С.17-80.

6.Дорф Р., Бишоп Р. Современные системы управления. М.: Лаборатория Базовых Знаний, 2002. С.243-564.

7.Филипс Ч., Харбор Р. Системы управления с обратной связью. М.: Лаборатория Базовых знаний, 2001. С.113-326.

8.Методы классической и современной теории автоматического управления. Т.1 /Под ред. К.А. Пупкова. М.: МГТУ, 2004. С.150-179.

9.Никулин Е.А. Основы теории автоматического управления. Частотные методы анализа и синтеза систем. СПб.: БХВ-Петербург, 2004.

Технология программирования (ТП) – это совокупность методов и средств, используемых в процессе разработки программного обеспечения (ПО). Как любая технология, ТП представляет собой набор технологических инструкций, включающих:

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

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

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

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

Различают два вида ТП:

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

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

Рассмотрим основные этапы развития программирования вообще и ТП в частности.

Первый этап – «стихийное» программирование.Этот этап охватывает период от момента появления первых ЭВМ до середины 60-х годов ХХ вв. В этот период практически отсутствовали сформулированные технологии, и программирование фактически было искусством. Первые программы имели простейшую структуру. Они состояли из программы на машинном языке и обрабатываемых ею данных. Появление ассемблеров позволило вместо двоичных или 16-ричных кодов использовать символические имена данных и кодов операций. В результате программы стали более «читаемыми».

Создание языков программирования высокого уровня (FORTRAN,ALGOL) существенно упростило программирование вычислений, снизив уровень детализации операций, что позволило увеличить сложность программ.

В начале 60-х годов ХХ в. разразился «кризис» программирования. Анализ причин возникновения большинства ошибок позволил сформулировать структурный подход к программированию.

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

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

Поддержка принципов структурного программирования была заложена в основу процедурных языков программирования. Такие языки обычно содержат операторы передачи управления, поддерживают вложение подпрограмм, локализацию и ограничение области «видимости» данных (PL/1, ALGOL-68, Pascal, C).

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

Модульное программирование предполагает выделение групп подпрограмм, использующих одни и те же глобальные данные в отдельно компилируемые модули (библиотеки подпрограмм). Например, модуль графических ресурсов, модуль подпрограмм вывода на принтер и др. Связи между модулями при использовании данной технологии осуществляются через специальный интерфейс, а доступ к реализации модуля (телам подпрограмм и некоторым «внутренним» переменным) запрещен. Эту технологию поддерживают современные версии языков Pascal, С++,новые языки Ada, Modula.

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

Третий этап – объектный подход к программированию (середина 80-х – конец 90-х годов ХХ в.). Объектно-ориентированное программирование (ООП) – это технология создания сложного ПО, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного типа (класса), а классы образуют иерархию с наследованием свойств и методов. (Взаимодействие программных объектов в такой систем осуществляется путем передачи сообщений.) Примеры ООЯ: ObjectPascal (Delphi), C++, Modula, Java.

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

Использование объектного подхода имеет много преимуществ, однако его конкретная реализация в ООЯ программирования (Object Pascal, C++)имеет и ряд недостатков. Сохраняется зависимость модулей ПО от адресов экспортируемых полей и методов, а также структур и форматов данных. Эта зависимость объективна, т.к. модули должны взаимодействовать друг с другом, обращаясь к ресурсам друг друга. Связи модулей нельзя разорвать, но можно попробовать стандартизовать их взаимодействие, на чем и основан компонентный подход к программированию.

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

КП лежит в основе технологий, разработанных на базе COM(Component Object Model– компонентная модель объектов), и технологии создания распределенных приложений CORBA (Common Object Request Broker Architecture– общая архитектура с посредником обработки запросов объектов). Эти технологии используют сходные принципы и различаются лишь особенностями реализации.

Технология COM фирмы Microsoftявляется развитием технологии OLE (Object Linking and Embedding– связывание и внедрение объектов), которая использовалась в ранних версиях Windowsдля создания составных документов. Технология COM определяет общие принципы взаимодействия программ любых типов:библиотек, приложений, операционной системы, т.е. позволяет одной части ПО использовать функции (службы), предоставляемые другой, независимо от того, функционируют ли эти части в пределах одного процесса, в разных процессах на одном ПК или на разных ПК. Модификация COM, обеспечивающая передачу вызовов между компьютерами, называется DCOM(Distributed COM– распределенная COM). На базе технологии COMи DCOMразработаны компонентные технологии, решающие различные задачи разработки ПО:

1. OLE – automation или просто Automation (автоматизация) – технология создания программируемых приложений, обеспечивающая программируемый доступ к внутренним службам этих приложений. Вводит понятие диспинтерфейса (dispinterface) – специального интерфейса, облегчающего вызов функций объекта. Эту технологию поддерживает, например, Microsoft Excel, предоставляя другим приложениям свои службы.

2. ActiveX – технология, построенная на базе OLE — automation, предназначенная для создания ПО как установленного на одном ПК, так и распределенного в сети. Предполагает использование визуального программирования для создания компонентов – элементов управленияActiveX. Полученные таким образом элементы управления можно устанавливать на компьютер дистанционно с удаленного сервера, причем устанавливаемый код не зависит от используемой ОС. Это позволяет применять элементы управления ActiveXв клиентских частях приложений Интернет. Основные преимущества технологии ActiveX:

o быстрое написание программного кода (поскольку все действия, связанные с организацией взаимодействия сервера и клиента, берет на себя ПО COM, программирование сетевых приложений становится похожим на программирование для отдельного компьютера);

o открытость и мобильность (спецификации технологии недавно были переданы в Open Group как основа открытого стандарта);

o возможность написания приложений с использованием знакомых средсв разработки (Visual Basic, Visual C++, Borland Delphi, Borland C++ и любых средств разработки на Java);

o большое количество уже существующих бесплатных программных элементов ActiveX ;

o стандартность (технология ActiveX основана на широко используемых стандартах Интернет(TCP/IP, HTML, Java ) и стандартах COM, OLE ).

3. MTS (Microsoft Transaction Server – сервер управления транзакциями) – технология, обеспечивающая безопасность и стабильную работу распределенных приложений при больших объемах передаваемых данных.

4.MIDAS (Multitier Distributed Application Server – сервер многозвенных распределенных приложений) – технология, организующая доступ к данным разных компьютеров с учетом балансировки нагрузки сети.

Все указанные технологии реализуют компонентный подход, заложенный в COM.

Технология CORBA, разработанная группой компаний OMG (Object Management Group – группа внедрения объектной технологии программирования), реализует подход, аналогичный COM, на базе объектов и интерфейсов CORBA. Программное ядро CORBAреализовано для всех основных аппаратных и программных платформ и поэтому технологию можно использовать для создания распределенного ПО в гетерогенной (разнородной) вычислительной среде. Организация взаимодействия между объектами клиента и сервера в CORBAосуществляется с помощью специального посредника VisiBrokerи др. специализированного ПО.

Отличительной особенностью современного этапа развития ТП, кроме изменения подхода, является создание и внедрение автоматизированных технологий разработки и сопровождения ПО, которые называются CASE-технологии (Computer-Aided Software/System Engineering – разработка ПО/ПС с использованием компьютерной поддержки). На сегодняшний день существуютCASE-технологии, поддерживающие как структурный, так и объектный (в том числе и компонентный) подходы к программированию.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Основы функционального программирования/Вводная лекция

Содержание

Общие слова [ править ]

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

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

Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, а всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Шагом после ассемблера стали так называемые императивные языки высокого уровня: Бейсик, Паскаль, Си, Ада и прочие, включая объектно-ориентированные. Императивными («предписывающими») такие языки названы потому, что ориентированы на последовательное исполнение инструкций, работающих с памятью (то есть присваиваний), и итеративные циклы. Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности.

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

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

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

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

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

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

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

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

Большинство функциональных языков программирования реализуются как интерпретируемые, следуя традициям Лиспа (примечание: большая часть современных реализаций Лиспа содержат компиляторы в машинный код). Таковые удобны для быстрой отладки программ, исключая длительную фазу компиляции, укорачивая обычный цикл разработки. С другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, Objective Caml) или код на Си/Си++ (например, Glasgow Haskell Compiler). Что показательно, практически каждый компилятор с функционального языка реализован на этом же са́мом языке. Это же характерно и для современных реализаций Лиспа, кроме того среда разработки Лиспа позволяет выполнять компиляцию отдельных частей программы без остановки программы (вплоть до добавления методов и изменения определений классов).

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

Свойства функциональных языков [ править ]

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

Краткость и простота [ править ]

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

Пример 1. Быстрая сортировка Хоара на Си

Пример 2. Быстрая сортировка Хоара на абстрактном функциональном языке

quickSort ⁡ ( [ x : x s ] ) = quickSort ⁡ ( [ y ∣ y ∈ x s , y x ] ) + [ x ] + quickSort ⁡ ( [ y ∣ y ∈ x s , y ≥ x ] ) <\displaystyle \operatorname ([x:xs])=\operatorname ([y\mid y\in xs,\,y

Это читается так:

  1. Если список пуст, то результатом также будет пустой список.
  2. Иначе выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет конкатенация (сращивание) отсортированного списка из всех элементов хвоста меньших головы, списка из самой головы и списка из всех элементов хвоста бо́льших либо равных голове.

Пример 3. Быстрая сортировка Хоара на языке Haskell

Как видно на этом примере, функциональная формулировка алгоритма короче и яснее чем императивная, хоть последняя в данном случае и выигрывает в эффективности исполнения, сортируя массив «на месте», внутри себя, в то время как версия на Хаскеле создает новые списки в ходе работы.

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

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

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

Строгая типизация [ править ]

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

Мастер Йода рекомендует:  Какой он, хороший код по мнению Линуса Торвальдса

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

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

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


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

Модульность [ править ]

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

Функции суть значения [ править ]

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

Можно воспользоваться функцией map для возведения в квадрат всех элементов некоторого списка:

Результатом будет список [1, 4, 9, 16].

Чистота [ править ]

(отсутствие побочных эффектов)

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

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

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

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

Отложенные вычисления [ править ]

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

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

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

Решаемые задачи [ править ]

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

1. Получение остаточной процедуры.

Если даны следующие объекты:

2. Построение математического описания функций.

3. Определение формальной семантики языка программирования.

4. Описание динамических структур данных.

5. Автоматическое построение «значительной» части программы по описанию структур данных, которые обрабатываются создаваемой программой.

6. Доказательство наличия некоторого свойства программы.

7. Эквивалентная трансформация программ.

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

Справочный материал [ править ]

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

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

  1. Лисп (List processor). Считается первым функциональным языком программирования. Поддерживает динамическую и факультативно статическую типизацию. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. В стандарт Common Lisp входит Common Lisp Object System (CLOS) — объектная система Common Lisp, которая по многим параметрам превосходит объектные системы в других языках (поддерживает метаобъектный протокол, мультиметоды и т. д.).
  2. ISWIM (If you See What I Mean). Функциональный язык-прототип. Разработан Питером Ландиным в 60-х годах XX ве́ка для демонстрации того, каким может быть язык функционального программирования. Вместе с языком П. Ландин разработал и специальную виртуальную машину для исполнения программ на ISWIM’е. Эта виртуальная машина, основанная на вызове-по-значению, получила название SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.
  3. Scheme. Диалект Lisp’а, предназначенный для научных исследований в области computer science. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем Common Lisp.
  4. ML (Meta Language). Семейство строгих языков с развитой полиморфной системой типов и параметризуемыми модулями. ML преподаётся во многих западных университетах (в некоторых даже как первый язык программирования).
  5. Standard ML. Один из первых типизированных языков функционального программирования. Содержит некоторые императивные свойства, такие как ссылки на изменяемые значения и поэтому не является чистым. При вычислениях использует вызов-по-значению. Очень интересная реализация модульности. Мощная полиморфная система типов. Последний стандарт языка — Standard ML-97, для которого существует формальные математические определения синтаксиса, а также статической и динамической семантик языка.
  6. Caml Light и Objective Caml. Как и Standard ML принадлежит к семейству ML. Objective Caml отличается от Caml Light в основном поддержкой классического объектно-ориентированного программирования. Также как и Standard ML строгий, но имеет некоторую встроенную поддержку отложенных вычислений.
  7. Miranda. Разработан Дэвидом Тёрнером, в качестве стандартного функционального языка, использовавшего отложенные вычисления. Имеет строгую полиморфную систему типов. Как и ML преподаётся во многих университетах. Оказал большое влияние на разработчиков языка Haskell.
  8. Haskell. Один из самых распространённых не строгих языков. Имеет очень развитую систему типизации. Несколько хуже разработана система модулей. Последний стандарт языка — Haskell-98.
  9. Gofer (GOod For Equational Reasoning). Упрощённый диалект Haskell’а. Предназначен для обучения функциональному программированию.
  10. Clean. Специально предназначен для параллельного и распределённого программирования. По синтаксису напоминает Haskell. Чистый. Использует отложенные вычисления. С компилятором поставляется набор библиотек (I/O libraries), позволяющих программировать графический пользовательский интерфейс под Win32 или Mac OS.

Сайты о функциональном программировании [ править ]

  1. http://www.haskell.org/ — очень насыщенный сайт, посвящённый функциональному программированию в общем и языку Haskell в частности. Содержит различные справочные материалы, список интерпретаторов и компиляторов Haskell’а (в настоящий момент все интерпретаторы и компиляторы бесплатны). Кроме того, имеется обширный список интересных ссылок на ресурсы по теории функционального программирования и другим языкам (Standard ML, Clean).
  2. http://cm.bell-labs.com/cm/cs/what/smlnj/ — Standard ML of New Jersey. Очень хороший компилятор. В бесплатный дистрибутив помимо компилятора входят утилиты MLYacc и MLLex и библиотека Standard ML Basis Library. Отдельно можно взять документацию по компилятору и библиотеке.
  3. http://www.harlequin.com/products/ads/ml/(dead link) — Harlequin MLWorks, коммерческий компилятор Standard ML. Однако в некоммерческих целях можно бесплатно пользоваться версией с несколько ограниченными возможностями.
  4. http://caml.inria.fr/ — институт INRIA. Домашний сайт команды разработчиков языков Caml Light и Objective Caml. Можно бесплатно скачать дистрибутив Objective Caml, содержащий интерпретатор, компиляторы байт-кода и машинного кода, Yacc и Lex для Caml, отладчик и профайлер, документацию, примеры. Качество компилированного кода у этого компилятора очень хорошее, по скорости опережает даже Standard ML of New Jersey.
  5. http://www.cs.kun.nl/

clean/ — содержит дистрибутив компилятора с языка Clean. Компилятор коммерческий, но допускается бесплатное использование в некоммерческих целях. Качественный (очень быстр), в наличии среда разработчика, хорошая документация и стандартная библиотека.

Литература [ править ]

  1. Хювёнен Э., Сеппенен И. Мир Lisp’а. В 2-х томах. М.: Мир, 1990.
  2. Бёрдж В. Методы рекурсивного программирования. М.: Машиностроение, 1983.
  3. Филд А., Харрисон П. Функциональное программирование. М.: Мир, 1993.
  4. Хендерсон П. Функциональное программирование. Применение и реализация. М.: Мир, 1983.
  5. Джонс С., Лестер Д. Реализация функциональных языков. М.: Мир, 1991.
  6. Henson M. Elements of functional languages. Dept. of CS. University of Sassex, 1990.
  7. Fokker J. Functional programming. Dept. of CS. Utrecht University, 1995.
  8. Thompson S. Haskell: The Craft of Functional Programming. 2-nd edition, Addison-Wesley, 1999.
  9. Bird R. Introduction to Functional Programming using Haskell. 2-nd edition, Prentice Hall Press, 1998.

Благодарности [ править ]

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

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

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

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

Если вы будете заказывать что-то из перечисленных тут книг, то просьба пользоваться соответствующими ссылками — это помогает мне покупать новые книги и пополнять обзор литературы (Предупреждение: иногда цены на ozon.ru сильно отличаются от цен в других магазинах, поэтому можете сравнить цены с помощью http://findbook.ru/, или заглянуть на сайт издательства).

Введение

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

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

Литература на русском языке

В 70-80-е гг. в СССР было выпущено достаточно большое количество литературы, касающейся функционального и декларативного программирования. Список книг включает не только переводные книги, но и книги и учебники отечественных авторов, работавших в данных областях. В 90-е годы издание такой литературы практически сошло на нет, но в последние годы эта ситуация стала исправляться — появились переводы хороших зарубежных книг 1 , а также вышло несколько книг русскоязычных авторов, в том числе и учебники, разработанные специально для вузов 2 , описанных ниже.

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

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

Общие вопросы ФП

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

«Функциональное программирование» (Харрисон/Филд)

В 1993 году издательство «Мир» выпустило перевод достаточно известной книги Functional Programming, написанной Петером Харрисоном (Peter G. Harrison) и Антони Филдом (Anthony J. Field) в 1988 году. На русском языке она называется «Функциональное программирование» (ISBN 5-03-001870-0).

Данная книга начинается с рассмотрения функций как таковых и использования функций высшего порядка, а также рассматривает виды вычислений, используемые при функциональном стиле программирования. Для демонстрации приемов программирования в книге вводится язык Hope. Помимо Hope, кратко описываются и другие языки программирования: Lisp, Miranda, FP.

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

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

«Введение в функциональное программирование» (Харрисон)

Данный проект является переводом курса Introduction to Functional Programming Джона Харрисона (John Harrison). Этот курс может использоваться для быстрого ознакомления с основами ФП и семейством языков ML. Он содержит в себе как описание теоретических основ ФП (от лямбда-исчисления до систем типов), так и примеры применения парадигм ФП для решения конкретных задач.

В данном курсе используется язык программирования Caml Light 3 , входящий в семейство языков ML. По мере прохождения данного курса читатель получает набор знаний, необходимый для освоения данного языка и написания на нем достаточно сложных программ.

Перевод может использоваться как основа курса лекций по ФП — помимо конспектов лекций (lecture notes) в нем содержатся переводы всех сопутствующих слайдов. Последняя версия перевода может быть загружена с сайта проекта.

«Структура и интерпретация компьютерных программ»

В 2006 году был выпущен перевод на русский язык классического учебника MIT по основам программирования «Структура и интерпретация компьютерных программ» (Structure & Interpretation of Computer Programs, SICP). Перевод был выполнен Георгием Бронниковым.

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

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

Качество перевода книги очень высокое, однако имеются недостатки, связанные с изданием самой книги: она вышла в мягком переплете, и ее не очень удобно читать, имеются проблемы верстки и опечатки, а главное — малый тираж (всего 1000 экземпляров), в связи с чем книгу уже тяжело найти в магазинах. В то же время, ее можно найти в электронном виде.

Учебные курсы проекта «Интуит»

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

В настоящее время опубликованы следующие курсы (материалы некоторых курсов доступны также в печатном виде — книги можно заказать с сайта проекта):

  • «Стили и методы программирования» (Н. Н. Непейвода) — учебный курс, в котором систематически излагаются сведения о стилях программирования и их методах, а также обсуждаются вопросы сочетаемости различных методов в разработке программ.
  • «Язык и библиотеки Haskell 98» — перевод «Haskell 98 Language and Libraries», описанного ниже, в разделе про Haskell.
  • «Введение в программирование на Лиспе» (Л. В. Городняя) — вводный курс по программированию на языке Lisp с примерами решения задач на этом языке.
  • «Основы функционального программирования» (Л. В. Городняя) — учебник по практическому программированию на языке Lisp.
  • «Парадигмы программирования» (Л. В. Городняя) — курс, рассматривающий различные парадигмы программирования — функциональное, объектно-ориентированное, императивное и другие.
  • «Введение в теорию программирования. Функциональный подход» (С.В. Зыков ) — еще один учебник по ФП. Здесь для примеров используется язык Standard ML.
  • «Основы программирования на языке Пролог» (П. А. Шрайнер) — учебный курс по логическому программированию и языку Пролог.

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

«Типы в языках программирования» (Пирс)

Эта книга является переводом известной книги Types and Programming Languages Бенджамина Пирса (Benjamin C. Pierce). В книге рассматриваются различные аспекты использования типов в языках программирования: математические основы, различные типовые системы, вывод типов и т.п.

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

Другие книги, имеющие отношение к ФП

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

    В 1992 году был выпущен перевод известной книги Implementing functional languages: a tutorial, написанной Simon Peyton Jones & Dav >Наряду с книгами, описывающими общие вопросы программирования на функциональных языках и математические основы лямбда-исчисления, в СССР и России издавались и книги по конкретным функциональным и декларативным языкам программирования. Достаточно широко представлена информация о языках Lisp, Haskell, Prolog и других.


Языку Lisp, являющемуся самым старым функциональным языком, в СССР было посвящено несколько публикаций (хотя их не так много, по сравнению с языком Пролог).

В 70-х гг. было выпущено сразу несколько книг по Лиспу:

  • В 1976 году вышел перевод книги У. Маурера «Введение в программирование на языке ЛИСП» (Maurer W. D., The Programmer’s Introduction to LISP), содержавшей описания языка Лисп и множество примеров и задач на его использование.
  • Через год Московским Энергетическим Институтом было издано учебное пособие по программированию на языке Lisp 1.5, написанное Е. Семеновой. Пособие содержит описание языка Lisp 1.5 и примеры его использования для решения учебных задач.
  • И в 1978 году была выпущена книга С.С. Лаврова и Г.С. Силагадзе «Автоматическая обработка данных. Язык ЛИСП и его реализация», описывающая язык Лисп и рассматривающая вопросы реализации этого языка.

В 1990 году вышел в свет широко известный двухтомник «Мир Лиспа», являющийся переводом одноименной книги финских авторов Э. Хювёнен и И. Сеппянен. В первом томе содержится описание языка Common Lisp, включая типы данных и наиболее часто используемые функции, ввод и вывод данных, обработку символьных данных и т.п. Кроме того, часть первого тома посвящена введению в методы ФП: использование рекурсии, функций высшего порядка, замыканий и макросов. Второй том содержит введение в другие методы программирования — логическое и объектное, описание среды программирования Лисп, а также большое количество примеров программ на этом языке, включая простой интерпретатор Лиспа.

Из более современных книг стоит упомянуть книги, выпущенные в рамках проекта Интуит, перевод ANSI Common Lisp (также доступный в электронном виде по свободной цене) а также книги, которые планируется выпустить в скором времени.

Clojure

Книг о Clojure опубликованных на русском языке не было достаточно долгое время. Эта ситуация была исправлена выпуском в 2013-м году книги Программирование в Clojure которая является переводом Clojure Programming издательства O’Reilly. Перевод был сделан очень хорошо, так что можно рекомендовать эту книгу для тех, кто пока не совсем хорошо владеет английским языком, но заинтересовался Clojure.

Существует также неофициальный перевод 2-го издания книги Programming Clojure. Пока непонятно — будет ли он издан на бумаге, но электронная версия пока доступна.

Кроме того, на русском языке опубликовано несколько статей — Язык программирования Clojure, опубликованная в рамках проекта IBM developerWorks, и статья Clojure, или «Вы все еще используете Java? Тогда мы идем к вам!», опубликованная в 4-м номере журнала «Практика функционального программирования» (более свежая версия этой статьи доступна на моем сайте).

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

Логическое программирование и язык Пролог

За последние тридцать лет в СССР (а затем и в России) было выпущено достаточно большое количество книг на темы логического программирования и искусственного интеллекта вообще и языка Пролог в частности (особенно много их было издано в 80-х гг.). Этот далеко не полный список включает следующие книги:

  • Иван Братко. «Программирование на языке Пролог для искусственного интеллекта». Первое издание на русском языке вышло в 1990 году. В настоящее время в магазинах доступно третье издание этой книги, выпущенное в 2004 году. Первая часть книги полностью посвящена языку Пролог и методам работы с ним, а во второй части рассматриваются прикладные вопросы использования данного языка: построение экспертных систем, решение задач поиска, обучение машин, обработка лингвистической информации и т.п.
  • Клоксин У., Меллиш К. «Программирование на языке пролог». Эта книга, изданная в 1987 году, содержит только описание языка Пролог и особенностей его использования.
  • А. Адаменко, А. Кучуков. «Логическое программирование и Visual Prolog». Книга издана в 2003 году и содержит небольшое введение в логическое программирование, в то время как основная часть книги посвящена вопросам программирования на Прологе с учетом особенностей Visual Prolog.
  • Дж. Малпас. «Реляционный язык Пролог и его применение». Данная книга является подробным описанием языка Пролог и различных приемов программирования на этом языке (обработка текстов, представление знаний); содержит много примеров.
  • С. Чери, Г. Готлоб, Л. Танка «Логическое программирование и базы данных». Книга рассматривает вопросы организации баз данных логических высказываний, включая краткое описание основ логического программирования и языков Пролог и Дейталог.
  • Л. Стерлинг, Э. Шапиро. «Искусство программирования на языке Пролог» (The Art of Prolog: Advanced Programming Techniques). Выпущенная в 1990 году, книга английских ученых содержит материалы по теории логического программирования, достаточно подробно описывает язык Пролог и содержит большое количество примеров программирования на этом языке, включая систему для решения уравнений и компилятор простого языка программирования.
  • Ц. Ин, Д. Соломон. «Использование турбо-пролога». Книга содержит описание принципов работы со средой программирования Турбо-Пролог, включая такие вопросы как использование машинной графики, создание многооконного интерфейса и т.п.
  • Дж. Макаллистер. «Искусственный интеллект и Пролог на микроЭВМ». Книга в краткой форме содержит сведения по языку Пролог, логике, базам знаний и экспертным системам. В первую очередь предназначалась для владельцев небольших компьютеров серии Спектрум и т.п.
  • Дж. Стобо. «Язык программирования Пролог». Данная книга является переводом книги «Problem Solving with Prolog» и описывает язык Пролог и его применение для решения различных задач — построения баз знаний, системы решения задач и других.
  • Дж. Доорс, А.Р. Рейблейн, С. Вадера. «Пролог — язык программирования будущего». Книга содержит краткое описание языка Пролог, практических приемов работы с ним, а также решения некоторых логических задач.
  • Н. И. Цуканова, Т. А. Дмитриева Логическое программирование на языке Visual Prolog небольшая книга, описывающая основные приемы работы с Visual Prolog.

Haskell

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

Книги о Haskell Романа Душкина

В 2006—2007 гг. Роман Душкин, читавший в МИФИ в 2001—2006 гг. курсы по ФП, выпустил две книги, посвященные языку программирования Haskell.

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

Стоит отметить, что книга содержит достаточно большое количество математики и написана суховатым языком, что делает ее излишне теоретизированой с точки зрения программиста-практика и затрудняет восприятие. Кроме того, в книге не так много примеров, которые показывали бы применимость языка в повседневной разработке (если сравнивать с книгой Real World Haskell, которая является хорошим образцом в этом деле). Еще одной вещью, затрудняющей чтение книги является качество издания — верстки самой книги и бумаги, на которой она напечатана.

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

Основная часть книги посвящена стандартным библиотекам, входящим в состав Hugs98 & GHC: начиная с Prelude и включая основные библиотеки (Control, System, Data, Text). Для каждой библиотеки приводится описание определенных в ней типов, классов и функций. Приводимые в справочнике определения функций могут использоваться в качестве примеров по написанию «правильного» кода на Haskell и являются хорошим подспорьем в работе.

В ноябре 2009 года была выпущена (при поддержке проекта «Практика функционального программирования») еще одна книга Романа Душкина. Она называется «Практика работы на языке Haskell» и рассматривает инструментальные средства языка Haskell, такие как компиляторы и интерпретаторы Hugs и GHC, поддержку разработки в среде Eclipse, различные утилиты (hlint, darcs, cabal и другие) и различные библиотеки: Parsec, для разработки парсеров, HaskellDB для работы с базами данных, разработки сетевых и графических приложений. По каждой из подсистем дается небольшое описание и примеры использования.

В 2011-м году была выпущена еще одна книга — «14 занимательных эссе о языке Haskell и функциональном программировании», в электронном виде она доступна бесплатно с сайта автора. А в 2012-м году, вышло продолжение этой книги: Другие 14 эссе о языке Haskell и функциональном программировании — серьёзные.

«Функциональное программирование» (Роганова)

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

К недостаткам пособия можно отнести то, что отсутствие материала по теоретическим основам ФП (лямбда-исчисление и т.п.) требует изучения дополнительных материалов (которые, к сожалению, не указаны в списке литературы). Кроме того, в части описания языка Haskell мало внимания уделено таким вопросам, как ввод/вывод данных, разбор данных и т.п.

Перевод книги «Learn You a Haskell for Great Good!»

Весной 2012-го года, издательство ДМК-Пресс выпустило перевод известного учебника по языку Haskell: Learn You a Haskell for Great Good!». Перевод называется Изучай Haskell во имя добра!, а исходный код черновиков перевода можно найти в отдельном репозитории.

Учебник по Haskell Антона Холомьёва

Антон Холомьёв написал (хотя работа все еще продолжается) учебник по Haskell, который описывает не толькосам язык, но и теоретические основания лямбда-исчисления, теории категорий и то, как это все связано с Haskell. Исходный текст учебника и версия в формате PDF доступны в репозитории на github.

Учебное пособие по Haskell Григория Макеева

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

Переводы документации

М. Ландина и В. Роганов в 2005 году выполнили перевод The Haskell 98 Report — основного документа, который определяет синтаксис языка Haskell, а также состав основных библиотек этого языка. Перевод этого документа доступен с сервера haskell.ru как в варианте для печати, так и в online-версии.

Денис Москвин сделал перевод хорошо известного учебника по языку Haskell — Gentle Introduction To Haskell. Данный учебник описывает основные возможности языка Haskell и наиболее часто используемые функции стандартных библиотек, включая ввод и вывод, и может использоваться для изучения основ языка. Перевод учебника доступен с сервера RSDN и состоит из двух частей — часть 1 и часть 2.

Семейство языков ML

О семействе языков ML (Standard ML, Objective Caml, Caml Light) на русском языке существует сравнительно немного литературы. В качестве небольшого введения в программирование на языке Caml Light можно использовать курс лекций «Введение в функциональное программирование», описанный выше.

Кроме того, существует незаконченный перевод книги Developing Applications With Objective Caml — переведено 11 глав, описывающих сам язык OCaml и базовые библиотеки, их можно использовать в качестве учебника по данному языку.

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

Весной 2011-го года, в издательстве «Символ-Плюс» под названием Программирование на F# вышел перевод книги Programming F#, выпущенной издательством O’Reilly. Данная книга описывает 1-ю версию языка, хотя в данный момент уже доступна вторая версия, со многими улучшениями.

Издательство «ДМК Пресс» также участвует в выпуске литературы по функциональному программированию. В апрелее 2011-го года, там была выпущена книга Дмитрия Сошников Функциональное программирование на F#, которая представляет собой небольшое введение в этот язык, без глубокого погружения в лямбда-исчисление и синтаксис языка, но охватывает основные практические вопросы применения этого языка. Особенно полезной является 7-я глава, которая содержит решения конкретных задач, от математических вычислений, до веб-программирования, графики и программирования для Windows Phone 7.

Erlang

Весной 2012-го года издательство ДМК-Пресс выпустило перевод книги Erlang Programming под названием Программирование в Erlang, но пока неизвестно — будет ли эта книга доступна в электронном виде.

Scala

Еще одним проектом издательства ДМК-Пресс является перевод книги Scala for the Impatient, который вышел под названием SCALA для нетерпеливых. Перевод сделан достаточно хорошо и эту книгу можно использовать для быстрого ознакомления с языком. А больше книг про Scala вы найдете ниже в разделе англоязычной литературы.

Планируется выпустить

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

Еще одна группа энтузиастов начала работу над переводом знаменитой книги On Lisp Пола Грема (Paul Graham). Вы можете помочь в улучшении этого материала путем вычитки переведенных глав или присоединившись к переводу текста.

Англоязычная литература

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

Общие вопросы ФП

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

  • Purely Functional Data Structures — отличная книга Криса Окасаки (Chris Okasaki) в которой описываются методы работы со сложными структурами данных в «чистых» функциональных языках.
  • Книга The Functional Approach to Programming (Guy Cousineau, Michel Mauny), описывающая все основные вопросы ФП, может использоваться в качестве учебника по ФП. Для примеров используется язык Caml.
  • Недавно выпущенная книга Ричарда Бёрда Pearls of Functional Algorithm Design, описывает подходы к решению разных задач с помощью функционального программирования на языке Haskell (эта книга также доступна и на русском языке);
  • В книге Algorithms: A Functional Programming Approach рассматриваются вопросы реализации различных алгоритмов на «чистых» функциональных языках, включая некоторые темы, описанные в книге «Purely Functional Data Structures». Для примеров используется Haskell;
  • Книга Programming Languages: Application and Interpretation (Shriram Krishnamurthi) является учебником для курса «Языки программирования». В ней рассматриваются различные аспекты проектирования и разработки языков программирования. Для примеров используется язык Scheme.
  • Книга How to Design Programs: An Introduction to Programming and Computing (имеющаяся в свободном доступе и поставляемая вместе с PLT Scheme), является учебником по программированию, демонстрирующим различные подходы к разработке программ. Для примеров в книге используется язык Scheme.
  • Foundations for Programming Languages (Foundations of Computing) Джона Митчелла посвященная исследованию систем типов и прочих вопросов реализации языков программирования (имеется и перевод на русский язык под названием Основания языков программирования).
  • Practical Foundations for Programming Languages написанная Робертом Харпером посвящена теоретическим основаниям языков программирования, отталкиваясь от теории типов. Эта книга также свободно доступна в виде черновой версии.
  • Книга Programming Language Concepts (Undergraduate Topics in Computer Science) использует F# для демонстрации основных концепций языков программирования, а также освящает некоторые вопросы реализации языков программирования, такие как сборка мусора и т.п., включая реализацию некоторых подсистем на примере реализации небольшого языка.
  • книга Concrete Abstractions. An Introduction to Computer Science Using Scheme (также имеется в свободном доступе) старается ознакомить читателя с основными концепциями computer science и программирования.
  • Basic Category Theory for Computer Scientists — данная книга рассматривает теорию категорий, лежащую в основе некоторых приемов, используемых в ФП (в частности, монад в языке Haskell);
  • Category Theory for Computing Science является введением в теорию категорий;
  • Книга Lambda-Calculus and Combinators: An Introduction посвящена изложению теоретических основ лямбда-исчисления;
  • Software Foundations — книга Бенджамина Пирса с коллегами, является основной для курса который читается в университете Пенсильвания. Основными темами курса являются логика, функциональное программирование, доказательство корректности программ (на базе Coq);
  • An Introduction to Functional Programming Through Lambda Calculus — еще одно введение в функциональное программирование и лямбда-исчисление;
  • Computational Semantics with Functional Programming;
  • Conceptual Mathematics: A First Introduction to Categories — подробное и хорошо написанное введение в теорию категорий, также может быть полезна при изучении функциональных языков.
  • Книга Interactive Theorem Proving and Program Development (Coq book) посвящена вопросам доказательства корректности программ. В качестве утилиты для доказательства теорем, используеся Coq.
  • Certified Programming with Dependent Types (бета-версия, доступная бесплатно) — еще одна книга, посвященная доказательству корректности программ, которая также использует Coq;
  • Learn you an Agda and Achieve Enlightenment! — книга которая должна стать введением в язык Agda.
  • Programming in Martin-Löf’s Type Theory: An Introduction — свободно-распространяемая книга, посвященная теории типов;
  • Type Theory and Functional Programming — еще одна свободная книга, посвященная теории типов;
  • Lectures on the Curry-Howard Isomorphism — в книге описывается связь между теорией доказательств и теорией типов.
  • The Lambda Calculus. Its Syntax and Semantics подробно описывает lambda calculus.
  • Pattern Calculus: Computing with Functions and Structures описывает связь pattern calculus с лямбда-исчислением, языками программирования и т.п.
  • The Functional Approach to Data Management: Modeling, Analyzing and Integrating Heterogeneous Data описывает как подходы функционального программирования могут быть использованы при работе с данными.
  • Lambda Calculus with Types (Perspectives in Logic) — еще одна книга посвященная типизированному лямбда исчислению.
  • The Parametric Lambda Calculus: A Metamodel for Computation описывает мета-модель рассуждений о различных видах вычислений.
  • Lambda-calculus, Combinators and Functional Programming является введением в лямбда-исчисление и комбинаторы.

Больше книг вы можете найти на страницах проекта Free Tech Books.

Реализация языков программирования

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

  • Книга Design Concepts in Programming Languages посвящена теоретическим и практическим аспектам разработки языков программирования.
  • Книга The Implementation of Functional Programming Languages, написанная Simon Peyton Jones и изданная в 1987 году, описывает такие темы, как лямбда-исчисление, вывод и проверка типов, сопоставление с образцом (pattern-matching), и использование этих приемов при реализации функциональных языков программирования.
  • Книга Implementing functional languages: a tutorial, написанная Simon Peyton Jones & Dav >Имеется несколько книг, которые посвящены различным подходам к программированию, проиллюстрированные разными языкам программирования, включая функциональные. Сюда можно отнести следующие книги:

  • Книга Advanced Programming Language Design (online-версия) содержит информацию о разных подходах к программированию, в том числе и несколько глав о функциональном и логическом программировании.
  • Concepts, Techniques, and Models of Computer Programming — описывает основные парадигмы программирования и различные модели вычислений — объектно-ориентированную, функциональную, императивную и т.д.
  • Concepts in Programming Languages — еще одна книга Джона Митчелла, посвященная языкам программирования;
  • Programming Language Pragmatics, 3ed рассматривает разные языки программирования, включая F# и Scheme.
  • Essentials of Programming Languages от автора книг Little/Seasoned/Reasoned Schemer и других. В книге рассматриваются основные концепции языков программирования.

ФП для программистов на других языках

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

  • Книга Functional programming for Java developers (от автора книги «Programming Scala») показывает основные приемы и подходы функционального программирования, используя язык Java для примеров. Основная цель книги — заинтересовать программистов на Java в новых подходах и преимуществах функционального программирования;
  • Издательство Wiley опубликовало книгу Functional Programming in C#: >Ниже перечислены наиболее интересные книги на английском языке, посвященные конкретным функциональным языкам программирования.

Достаточно хорошее введение в конкретные языки функционального программирования можно найти в книге Seven Languages in Seven Weeks издательства Pragmatic Bookshelf. В книге описываются основы программирования на 7 языках (Ruby, Io, Prolog, Scala, Erlang, Clojure, Haskell), показываются базовые концепции и небольшие примеры. На мой взгляд этого может быть достаточно чтобы понять — захотите ли вы продолжать изучать конкретный язык программирования.

Haskell

Среди публикаций, посвященных языку Haskell, я хотел бы отметить следующие:

  • Introduction to Functional Programming using Haskell Ричарда Бёрда является учебником по функциональному программированию, использующим Haskell в качестве основного языка. В нем рассмотрены базовые концепции ФП и их применение в Haskell. Книга содержит много примеров и упражнений для самостоятельного решения.
  • Real World Haskell является отличной книгой по языку Haskell, поскольку, кроме описания самого языка, содержит множество примеров, показывающих применение Haskell в реальной жизни: программирование баз данных и графических интерфейсов, разбор данных, тестирование приложений и многое другое. Эта книга находится в свободном доступе на официальном сайте.
  • The Haskell Road To Logic, Maths And Programming показывает применение Haskell в математике и логике.
  • Programming in Haskell, написанная Graham Hutton, описывает язык Haskell немного суховато, но может использоваться в качестве справочника теми, кто уже знаком с этим или другими функциональными языками, например, OCaml или Standard ML. Эта книга также используется в курсе видео-лекций Эрика Майера (Erik Meijer) на Channel9.
  • Книга Haskell: The Craft of Functional Programming посвящена описанию языка Haskell и принципов программирования на этом языке, и включает отдельные главы по работе с типами данных, классами типов и т.п.
  • The Haskell School of Expression: Learning Functional Programming through Multimedia показывает практические аспекты применения Haskell, при этом описывает достаточно сложные темы, такие как взаимодействие с внешним миром, проектирование программ на Haskell и т.д.
  • Издательство O’Reilly выпустило весной 2012-го года книгу Developing Web Applications with Haskell and Yesod посвященную разработке веб-приложений используя фреймворк Yesod. Эта книжка также свободно доступна на сайте проекта.
  • В августе 2013-го года издательство O’Reilly планирует выпустить книгу Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming написанную Simon Marlow. Черновики этой книги уже доступны для чтения на сайте книги.

Кроме напечатанных книг и учебников, имеются и материалы, доступные online. К наиболее интересным можно отнести:

    Learn You a Haskell for Great Good!: A Gu >Книга Programming Erlang. Software for a Concurrent World, написанная Джо Армстронгом (Joe Armstrong), долгое время являлась практически единственным доступным печатным изданием, посвященным языку Erlang, поскольку выпущенная ранее книга «Concurrent Programming in Erlang» стала уже библиографической редкостью (в интернете можно найти первую часть этой книги). «Programming Erlang» описывает Erlang простым языком и знакомит читателя с его основным функционалом. Кроме самого языка, книга описывает более сложные темы: базы данных, использование OTP и т.п. Осенью 2013-го года издательство планирует выпустить 2-е издание этой книги.

В 2009-м году издательство O’Reilly выпустило книгу Erlang Programming, описывающую как сам язык, так и инфраструктурные вопросы, включая OTP, программирование графических приложений, test-driven разработку, отладку и т.д. Эта книга более подробная чем книга Армстронга.

Кроме того, издательство O’Reilly в начале 2013-го года выпустило книгу Introducing Erlang, которая должна служить кратким введением в сам язык и основные концепции OTP. Дополнением для этой книги является Études for Erlang являющяяся сборником упражнений, не включенных в основную книгу.

Книга Erlang and OTP in Action, выпущена издательством Manning осенью 2010 года, и посвящена практическим аспектам использования OTP, а также вопросам использования Erlang’а с библиотеками на других языках программирования. Предполагается, что читатель уже немного знаком с языком Erlang.

Успех книги Learn You a Haskell for Great Good! привел к созданию аналогичного проекта и для языка Erlang: Learn You Some Erlang for Great Good!. Онлайн версия книги также бесплатно доступна на сайте проекта.

В 2012-м году, издательство Springer выпустило необычную для них книгу: Handbook of Neuroevolution Through Erlang, которая описывает как Erlang был использован для построения нейронных сетей (neural networks).

Кроме того, планируется выпуск следующих книг, посвященных как самому языку Erlang, так и применению его в конкретных задачах:

  • Erlang for .NET Developers — эта книга была анонсирована в конце 2011-го года, но пока неизвестно когда она будет выпущена.
  • Addison-Wesley планирует выпустить книгу Building Scalable Applications with Erlang, которая должна служить введением в программирование на Erlang и OTP.
  • Pragmatic Bookshelf планирует выпустить книгу Programming Elixir, посвященную языку Elixir, который был создан для Erlang VM.
  • O’Reilly также планирует выпустить книгу посвященную языку Elixir под названием Introducing Elixir. Getting Started in Functional Programming.

Caml & Objective Caml

Вопросам программирования на языке Objective Caml (OCaml) посвящено несколько книг.

  • Наиболее известной является свободно доступная книга Developing Applications with Objective Caml, которая не только описывает сам язык OCaml, но и рассматривает различные вопросы программирования с его использованием.
  • Недавно также появилась свободно распространяемая книга Introduction to Objective Caml, которая содержит достаточно подробное описание языка и примеры его применения.
  • Книга OCaml for Scientists посвящена вопросам использования OCaml для «научного программирования» — обработки данных, математических вычислений, визуализации данных и оптимизации кода для лучшей производительности.
  • Еще одна книга — Practical OCaml, описывает язык OCaml и приемы программирования на нем. К сожалению, по многочисленными отзывами читателей, книга написана не очень хорошо.
  • Книга OCaml from the Very Beginning является учебником по OCaml, кроме описания языка, в ней очень много упражнений (с ответами), так что она может быть полезна в качестве учебного пособия при преподавании этого языка.
  • Свободно доступная книга Think OCaml. How to Think Like a Computer Scientist является введением в программирование пользуясь языком OCaml в качестве основы.
  • Еще одна свободно доступная книга: Unix system programming in OCaml написанная Xavier Leroy и Didier Rémy рассказывает как OCaml может использоваться для программирования для Unix, включая управление потоками и процессами, работу с файлами, взаимодействие через сокеты и т.д.

Технический отчет The ZINC experiment: an economical implementation of the ML language, написанный Xavier Leroy в 1990 году, представляет собой подробное описание реализации языка ML и может быть интересен тем, кто интересуется внутренним устройством Caml & OCaml.

А осенью 2013-го года, издательство O’Reilly планирует издать книгу Real World OCaml которая должна стать таким же популярным введением в язык OCaml как и Real World Haskell стал для языка Haskell. Текст книги в электронном виде также доступен на отдельном сайте.

В настоящее время языку F# посвящено достаточно большое количество книг.

Foundations of F#, выпущенная в 2007-м году, описывает основы языка и показывает разные методы программирования на нем, включая создание пользовательских интерфейсов и работу с базами данных. В конце 2009-го года вышла новая версия этой книги, под названием Beginning F#.

Книга Expert F# 3.0 в свою очередь посвящена более сложным вопросам применения F# для разработки программ, таким как взаимодействие с кодом, написанным на других языках, использование библиотек .Net, разбор данных, асинхронное программирование и т.д.

F# for Scientists является версией книги «OCaml for Scientists», адаптированной для языка F#, и содержит информацию по разным аспектам применения F# в «научном программировании» — визуализации данных, работе с базами данных, обработке данных и т.д.

В октябре 2009-го года издательство O’Reilly выпустило книгу Programming F#, которая содержит описание актуальной версии языка F#, начиная с рассмотрения основ функционального и объектно-ориентированного программирования на данном языке, использование библиотек платформы .Net, метапрограммирование с помощью доступных средств платформы, а также использование возможностей языка для асинхронного и параллельного программирования. Кроме этого, в приложениях приводится информация об имеющихся библиотеках для обработки и визуализации данных. В 2012-м году, было выпущено 2-е издание этой книги, которое описывает F# 3.0.

Кроме того, издательство O’Reilly выпустило еще одну небольшую книгу посвященную разработке на F#: Building Web, Cloud, and Mobile Solutions with F#.

В конце 2009-го года, издательство Manning опубликовало книгу Functional Programming for the Real World: With Examples in F# and C#, которая описывает декларативный подход к разработке программ, и иллюстрирует его с помощью примеров на языках F# и C#. Данная книга может быть интересна для программистов, имеющих опыт разработки для платформы .Net, и желающих ознакомиться с разными подходами к разработке программ.

Flying Frog Consultancy также выпустило книгу Visual F# 2010 for Technical Computing, которая описывает версию F#, поставляемую в составе Visual Studio 10.

А летом 2010-го года в издательстве Wrox вышла книга Professional F# 2.0.

Также, через Амазон можно купить в электронном виде книгу Friendly F# (Fun with game programming), которая знакомит с F# на примере разработки игр.

А издательство Manning планирует выпустить в 2013-м году книгу F# Deep Dives, которая описывает использование F# для решения конкретных задач.


Среди свободных ресурсов стоит отметить книгу The F# Survival Guide, которая содержит достаточно полную информацию об основах функционального программирования и самом языке F#. Еще одним полезным ресурсом может оказаться сайт F# for fun and profit.

Книга F# for C# Developers издательства Microsoft Press является введением в язык F# для разработчиков которые уже умеют опыт разработки на языке C# и платформе .Net.

Standard ML

По языку Standard ML также выпущено достаточно большое количество книг:

  • Книга ML for the Working Programmer является практическим введением в этот язык, описывающим сам язык и демонстрирующим некоторые приемы программирования на нем;
  • Книга The Little MLer является кратким справочником по языку с примерами программ;
  • Книга «Unix System programming with Standard ML» (pdf) посвящена демонстрации применимости функциональных языков в повседневной работе;
  • Книга Elements of ML Programming, ML97 Edition, также описывающая сам язык и методы программирования на нем, может использоваться как введение в язык Standard ML.
  • Elementary Standard ML — введение в язык Standard ML
  • Programming in Standard ML — черновик книги Роберта Харпера является введением в язык Standard ML.

Несколько книг посвящены изложению стандарта языка. К ним можно отнести книги The Definition of Standard ML и The Standard ML Basis Library, которые содержат подробную информацию о языке и стандартной библиотеке.

Кроме описанных ранее русскоязычных книг по языку Lisp, существует большое количество книг на английском языке, посвященных Lisp и его диалектам:

  • Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP — классическая книга Питера Норвига (Peter Norvig), посвященная вопросам искусственного интеллекта, показывает применение языка Common Lisp для решения некоторых задач искусственного интеллекта.
  • ANSI Common Lisp, написанная Полом Гремом (Paul Graham), предназначена для начинающих программировать на Common Lisp. Книга содержит описание языка и примеры его использования.
  • On Lisp, также написанная Полом Гремом, раскрывает более сложные вопросы программирования на Common Lisp: создание макросов, использование макросов для построения domain-specific languages (DSL) и т.п.
  • Книги Object-Oriented Programming in Common Lisp: A Programmer’s Guide to CLOS и The Art of Metaobject Protocol содержат подробную информацию о программировании с использованием Common Lisp Object System. При этом, вторая книга в большей степени посвящена вопросам реализации Metaobject Protocol, лежащего в основе CLOS, и рекомендуется всем, кто интересуется вопросами объектно-ориентированного программирования (ООП).
  • Книга Let Over Lambda посвящена рассмотрению сложных тем программирования на Common Lisp — созданию и использованию макросов, правильному проектированию программ и т.п.
  • Книга Common Lisp: The Language, 2ed (также доступна online) является полным справочником по языку Common Lisp.
  • Successful Lisp: How to Understand and Use Common Lisp — еще одна книга для начинающих программировать на Lisp’е. Книга также имеет online версию.
  • Lisp in Small Pieces — достаточно известная книга по Lisp. В ней рассматриваются реализации языков Lisp и Scheme, включая программирование с использованием продолжений 5 , построение интерпретатора и компилятора этих языков, поддержку макросов и многое другое.
  • Свободно доступная книга Common Lisp: A Gentle Introduction to Symbolic Computation является достаточно подробным введением в программирование на Common Lisp. Эта книга также доступна в печатном виде.

Осенью 2010-го года, издательство No Starch Press выпустило еще одну книгу по Lisp — Land of LISP: Learn to Program in LISP, One Game at a Time!. Кроме того, у книги есть отдельный сайт, где можно найти более подробную информацию о книге.

Всеволод Дёмкин долгое время интервьюировал известных разработчиков на Commom Lisp, и сейчас эти итервью доступны в виде отдельной книги — Lisp Hackers. Interviews with 100x More Productive Programmers, доступной бесплатно в электронной форме.

Издательство O’Reilly планировало выпустить книгу о Common Lisp под названием «Lisp Outside the Box», и несколько глав уже доступно для чтения на сайте проекта, но он был прекращен. Как видно из оглавления, в книге планировалось рассмотреть широкий круг вопросов — от основ Common Lisp, до разработки приложений для веб и десктопа, а также работы с конкретными библиотеками и средами разработки.

Scheme

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

Книги описывают как сам язык, так и различные аспекты его использования. Эти книги могут использоваться как справочники по языку и являются хорошим дополнением к книгам Structure and Interpretation of Computer Programs и How to Design Programs, в которых язык Scheme использован для примеров.

Летом 2013-го года выпущена книга Realm of Racket посвященная языку Racket (бывший PLT Scheme). На создание этой книги сильно повлиял выход книги «Land of Lisp (автор этой книги также соавтор Realm of Racket).

Prolog

Количество англоязычных книг по Прологу достаточно велико. Ниже приведен лишь небольшой список имеющейся литературы — я старался отобрать наиболее интересные книги:

  • Logic Programming with Prolog — хорошая книга по Prolog начального уровня. В ней описываются основные принципы программирования на Prolog вместе с примерами решения конкретных задач.
  • Programming in Prolog: Using the ISO Standard — еще один учебник по Прологу, демонстрирующий основные принципы программирования на этом языке.
  • Clause and Effect: Prolog Programming for the Working Programmer является небольшим введением в Пролог для программистов, владеющих другими языками.
  • Learn Prolog Now! — вводный курс по программированию на Prolog. Также доступна онлайн-версия этой книги, но она немного отличается от печатной;
  • The Craft of Prolog — книга для людей, которые уже изучили Prolog, но хотят углубить свои знания;
  • Книга The Art of Prolog, Second Edition: Advanced Programming Techniques посвящена вопросам использования языка, которые обычно не рассматриваются в книгах, предназначенных для изучения самого языка: построение интерпретаторов и компиляторов, преобразование программ, теории логического программирования.
  • The Practice of Prolog — эта книга показывает как проектировать и организовывать достаточно большие программы на Prolog.
  • Prolog Programming in Depth — еще одна книга, посвященная «сложным» аспектам применения Пролога: взаимодействию с внешним миром, императивному программированию на Прологе, построению экспертных систем и т.п.

Также имеется ряд свободно доступных ресурсов имеющих отношение к Prolog и логическому программированию:

Scala

Язык Scala становится достаточно популярным, и начал использоваться в коммерческих проектах, таких как Twitter, LinkedIn, и других. По данному языку существует достаточно большое количество литературы на английском языке:

  • На сайте проекта кроме спецификации языка, также выложены «A Brief Scala Tutorial» и «Scala by Example», которые позволяют достаточно быстро ознакомиться с данным языком. Также полезным является раздел Learning Scala который содержит ссылки на литературу, лекции и другие материалы.
  • Programming in Scala: A Comprehensive Step-by-step Gu Reilly доступна бета-версия данной книги.
  • Programming Scala: Tackle Multi-Core Complexity on the Java Virtual Machine (издательство Pragmatic Programmers) является достаточно кратким, по сравнению с другими книгами, введением в программирования на Scala, затрагивая основные темы — взаимодействие с JVM, конкуретное программирование, сопоставление с образцом, и т.д. Книга предполагает наличие опыта программирования на языке Java.
  • Beginning Scala (издательство Apress) также, как и предыдущая книга, является небольшим практическим введением в программирование на Scala, рассматривая основные возможности языка на практических примерах.
  • Книга The Definitive Guide to Lift: A Scala-based Web Framework (издательство Apress) представляет собой достаточно полное описание популярного веб-фреймворка Lift, разработанного для языка Scala.
  • Осенью 2010-го года была выпущена книга Steps in Scala: An Introduction to Object-Functional Programming.
  • Осенью 2011-го издательством Manning была выпущена книга Lift in Action: The Simply Functional Web Framework for Scala, которая достаточно подробно описывает Lift — Web-фреймворк для Scala.
  • А зимой 2012-го вышла книга Actors in Scala которая детально описывает использование акторов при программировании на Scala.
  • Еще одной полезной книгой является Programming Concurrency on the JVM: Mastering Synchronization, STM, and Actors, которая описывает разные подходы к конкурентному программированию, в том числе и на Scala, Clojure и других языках.
  • Фреймворк Akka очень часто используется со Scala, поэтому вам могут быть полезными книги Akka Concurrency, Akka Essentials и Composable Futures with Akka 2.0.
  • Twitter, который активно использует Scala, сделал свободно доступными два ресурса для изучения Scala: Scala School! From ∅ to Distributed Service и Effective Scala — оба ориентированы на начинающих изучать данный язык (для них также есть и русские версии: Scala Школа! и Эффективная Scala).
  • Весной 2012 года была выпущена книга Scala for the Impatient — она описывает язык, начиная с простых конструкций, и заканчивая сложными вещами.
  • Книга Scala in Action издательства Manning служит введением в программирование на этом языке.
  • Также весной 2012-го года, вышла книга Scala in Depth описывает сложные вопросы использования этого языка.
  • Осенью 2012-го года вышла книга Introduction to the Art of Programming Using Scala. С подробным содержанием этой книги можно ознакомиться на специальном сайте.
  • Книга Testing in Scala посвящена использованию тестовых фреймворков ScalaTest и Spec2, а также описывает как интегрировать тесты в проекты SBT.
  • Книга Pragmatic Enterprise Scala описывает как Scala может применяться вместе с технологиями применяющимися в Java Enterprise Edition.

К изданию планируются следующие книги:

  • издательством Apress будет выпущена книга Pro Scala: Monadic Design Patterns for the Web;
  • Издатетельство Manning планирует в выпустить несколько книг по Scala (Все книги доступны в рамках программы раннего доступа (MEAP)):
    • Functional Programming in Scala не описывает сам язык, но показывает как его использовать для разработки в функциональном стиле программирования.
    • А книга Play for Scala описывает веб-фреймворк Play.
    • Scalatra in Action описывает web-фреймворк Scalatra, который является более простым по сравнению с Lift или Play.
    • SBT in Action описывает систему сборки SBT которая применяется при сборке кода на Scala.
  • Книга Atomic Scala должна служить введением в язык Scala.
  • Книга ScalaCheck: The Definitive Guide описывает библиотеку ScalaCheck.
  • Издательство O’Reilly планирует выпустить осенью 2013-го года книгу Scala Cookbook которая должна содержать рецепты для решения конкретных задач.
  • Издательство Pragmatic Bookshelf планирует выпустить в 2013-м году книгу Functional Programming Patterns in Scala and Clojure: Write Lean Programs for the JVM.
  • Также ведется работа над книгой Scala on Android: How to do efficient Android programming with Scala, которая должна содержать информацию о том, как разрабатывать приложения для Android с использованием Scala.

Кроме книг и веб-сайтов, для Scala начали создаваться и онлайн-курсы, такие как http://www.scalacourses.com/ или Functional Programming Principles in Scala который проводится самим автором языка. Основное преимущество этих курсов заключается в наличии заданий и возможности получения ответов на свои вопросы на форумах.

Clojure

Clojure — недавно появившийся Lisp’ообразный язык программирования для Java Virtual Machine (JVM). В отличии от других реализаций, он не совместим полностью ни с Common Lisp, ни с Scheme, а реализует свое подмножество Lisp. Отказ от совместимости с другими реализациями, позволил реализовать некоторые интересные вещи, как неизменяемость данных, неявную параллелизацию кода, очень простую модель конкурентного программирования и другие вещи, при этом обеспечивая возможность двухстороннего взаимодействия с кодом на Java.

В 2009-м году в серии Pragmatic Programmers вышла книга Programming Clojure. Эта книга представляет собой достаточно хорошее введение в язык, описывая основные возможности языка (версии 1.0, существовавшей на время выхода книги). Но в качестве справочника необходимо использовать соответствующий раздел сайта языка, поскольку в книге в основном дается описание концепций языка. Весной 2012-го года, вышло второе издание этой книги, которое было обновлено описанием новых возможностей языка.

В мае 2010-го года вышла книга Practical Clojure. The Definitive Guide, которая содержит описание всех возможностей языка в достаточно кратком изложении. Но при этом в книге отсутствует описание инфраструктурных вещей, таких как среды разработки, утилиты для сборки кода и т.д.

В 2011-м году, издательство Manning выпустило две книги про Clojure: Clojure in Action и The Joy of Clojure. Thinking the Clojure Way. Первая книга является введением в этот язык программирования, с разными примерами его использования, в то время как вторая книга ориентирована на людей уже знакомых с Clojure, но которые хотят научиться лучше программировать на этом языке (у меня в блоге есть более подробная рецензия на эту книгу). Издательство Manning также планирует выпустить 2-е издание этой книги.

Весной 2012-го года издательство O’Reilly выпустило книгу Clojure Programming авторами которой являются известные разработчики языка и различных библиотек. Книга представляет подробное описание самого языка и некоторых библиотек, рассказывает о его практическом применении.

Издательство Developer.Press выпустило небольшую книжку под названием Clojure Made Simple которая описывает самые основы языка — типы данных, функции и т.п. Правда в книге почти не упоминаются возможности в части конкуретного программирования.

Издательство Packt также не обошло Clojure своим вниманием и выпустило книгу Clojure Data Analysis Cookbook которая описывает как Clojure может быть использована для анализа данных, включая использование Incanter.

Издательство No Starch Press также должно выпустить книгу по Clojure под названием Meet Clojure.

Издательство O’Reilly решило издать еще одну книгу о Clojure — Clojure Cookbook, и каждый может принять участие в написании рецептов, которые будут включены в эту книгу.

Среди свободных источников информации можно отметить Clojure Notes, который использовался в курсе обучения Clojure и книгу Clojure Programming, создаваемую в рамках проекта Wikibooks. Также свободно доступна и Clojure-версия книги «Casting SPELs in Lisp».

Параллельно с Clojure, разрабатывается и язык ClojureScript, который позволяет вам разрабатывать веб-приложения выполняемые в броузере. Издательство O’Reilly выпустило небольшую книгу ClojureScript: Up and Running которая кратко описывает основные принципы разработки с использованием ClojureScript, включая информацию о существующих библиотеках.

Рекомендации

Если вы хотите познакомиться с принципами создания функциональных языков программирования, то на русском языке базовую информацию вы почерпнете из книг «Структура и интерпретация компьютерных программ», «Функциональное программирование», «Функциональное программирование. Применение и реализация» (Хендерсон) и «Реализация функциональных языков». Из книг на английском языке я могу порекомендовать книги, перечисленные в разделе «Реализация функциональных языков программирования».

Заинтересовавшиеся Common Lisp могут начать его изучение с книги Practical Common Lisp (существующей и на русском языке), которая даст информацию по основным аспектам языка. Более сложные аспекты работы с Lisp описаны в On Lisp, The Art of Metaobject Protocol, Lisp in Small Pieces и других англоязычных книгах.

Для обучения функциональному программированию на языке Haskell можно порекомендовать книгу Introduction to Functional Programming using Haskell Ричарда Бёрда. Для желающих узнать о практическом применении Haskell хорошим выбором будет книга Real World Haskell в которой приводятся практические примеры использования Haskell. Среди учебников можно отметить Yet another Haskell tutorial и A Gentle Introduction to Haskell 98 (также доступный на русском языке), ну и конечно Learn You a Haskell for Great Good!.

Для изучения Erlang я бы посоветовал начать либо с книги Erlang Programming от O’Reilly, либо с Erlang and OTP in Action, выпущенной в Manning — обе эти книги обеспечивают достаточно полное описание как самого языка, так и OTP.

Для изучения Scala вы можете выбрать несколько книг. Если вам хочется сразу начать программировать, то в этом случае посмотрите на Scala for the Impatient. Если же вам хочется начать с более глубого изучения языка, то в этом случае начните с Programming in Scala: A Comprehensive Step-by-step Guide. Ну а после этих книг, можете продолжить изучение с помощью Scala in Depth и других книг.

Для Clojure, наиболее актуальными книгами являются Clojure Programming (более детальная) и 2-е издание Programming Clojure. А вот после этих книг, я очень советую прочитать The Joy of Clojure. Thinking the Clojure Way — вы не пожалеете.

Для ознакомления с языками семейства ML существует достаточно много литературы. Выбравшим OCaml лучше начать с книги Introduction to Objective Caml, используя её вместе со справочником по языку, а потом переходить к Developing Applications with Objective Caml и другим книгам из списка выше. А изучение F# стоит начать с Expert F# 2.0 или Begining F# и продолжить с F# for Scientists.

Для Prologа выбор книг достаточно велик — начать можно с книги Братко «Программирование на языке Пролог для искусственного интеллекта», а затем переходить к книгам на английском языке, перечисленным выше.

Заключение

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

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

2. Тут необходимо отметить серию учебников и учебных курсов проекта Интуит.

3. Хочется отметить, что ведется работа над версией курса лекций, адаптированной для языка OCaml, который является развитием Caml Light, но не полностью совместим с ним.

4. Это, к сожалению, беда многих советских и российских учебников.

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

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

Содержимое разработки

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ

ИНСТИТУТ ИМЕНИ М. Е. ЕВСЕВЬЕВА»

Кафедра информатики и вычислительной техники

Выполнила студентка группы МДМ-113

Романчукова Елена Ивановна

Проверила: Т. В. Кормилицына,

канд. физ.-мат. н., доцент

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

Свойства функциональных языков 5

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

Список используемых источников 12

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

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

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

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

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

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

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

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

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

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

В первую очередь большинство функциональных языков программирования реализуются как интерпретаторы, следуя традициям Lisp’а. Интерпретаторы удобны для быстрой отладки программ, исключая длительную фазу компиляции, тем самым укорачивая обычный цикл разработки. Однако с другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения в несколько раз. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, Objective Caml) или код на C/C++ (например, Glasgow Haskell Compiler). Что показательно, практически каждый компилятор с функционального языка реализован на этом же самом языке.

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

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

Кратность и простота;

Функции – это значения;

Чистота (отсутствие побочных эффектов);

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


Краткость и простота

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

Пример 1. Быстрая сортировка Хоара на C.

void quickSort (int a[], int l, int r)

int x = a[(l + r) / 2];

Пример 2. Быстрая сортировка Хоара на абстрактном функциональном языке.

quickSort ([h : t]) = quickSort (n | n t, n h)

Пример 2 следует читать так:

1. Если список пуст, то результатом также будет пустой список.

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

Пример 3. Быстрая сортировка Хоара на языке Haskell.

quickSort (h : t) = quickSort [y | y = h]

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

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

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

Пример 4. Определение N-ого числа Фибоначчи.

fibb (N) = fibb (N – 2) + fibb (N – 1)

Практически все современные языки программирования являются строго типизированными языками (возможно, за исключением JavaScript и его диалектов, не существует императивных языков без понятия «тип»). Строгая типизация обеспечивает безопасность. Программа, прошедшая проверку типов просто не может выпасть в операционную систему с сообщением, подобным «access violation», особенно это касается таких языков, как C/C++ и Object Pascal, где применение указателей является типичным способом использования языка. В функциональных языках большая часть ошибок может быть исправлена на стадии компиляции, поэтому стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерировать более эффективный код и тем самым ускорять выполнение программ.

Рассматривая пример с быстрой сортировкой Хоара, можно увидеть, что помимо уже упомянутых отличий между вариантом на языке C и вариантом на абстрактном функциональном языке, есть ещё одно важное отличие: функция на C сортирует список значений типа int (целых чисел), а функция на абстрактном функциональном языке – список значений любого типа, который принадлежит к классу упорядоченных величин. Поэтому последняя функция может сортировать и список целых чисел, и список чисел с плавающей точкой, и список строк. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать quickSort и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным полиморфизмом, и поддерживается большинством функциональных языков.

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

В языке C++ имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные quickSort. В стандартную библиотеку C++ STL входит такая функция и множество других полиморфных функций. Но шаблоны C++, как и родовые функции Ada, на самом деле порождают множество перегруженных функций, которые, кстати, компилятор должен каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция quickSort – это одна единственная функция.

В некоторых языках, например, в Ada, строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Чтобы избежать этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста. Этот механизм называется механизмом вывода типов. Известно несколько таких механизмов, однако большинство из них являются разновидностями модели типизации Хиндли-Милнера, разработанной в начале 80-х годов XX века. Таким образом, в большинстве случаев можно не указывать типы функций.

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

Функции – это значения

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

Можно воспользоваться функцией map для возведения в квадрат всех элементов некоторого списка:

squareList = map (square, [1, 2, 3, 4])

Результатом выполнения этой инструкции будет список [1, 4, 9, 16].

Чистота (отсутствие побочных эффектов)

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

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

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

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

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

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

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

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

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

1. Получение остаточной процедуры.

Если даны следующие объекты:

x3, . xn — неизвестные значения параметров.

Требуется получить остаточную процедуру P1 (x3, . xn). Эта задача решается только на узком классе программ.

2. Построение математического описания функций.

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

3. Определение формальной семантики языка программирования.

4. Описание динамических структур данных.

5. Автоматическое построение «значительной» части программы по описанию структур данных, которые обрабатываются создаваемой программой.

6. Доказательство наличия некоторого свойства программы.

7. Эквивалентная трансформация программ.

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

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

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

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.

Internet-ресурсы по функциональному программированию

www.haskell.org – очень насыщенный сайт, посвящённый функциональному программированию в общем и языку Haskell в частности. Содержит различные справочные материалы, список интерпретаторов и компиляторов Haskell’а (в настоящий момент все интерпретаторы и компиляторы бесплатны). Кроме того, имеется обширный список интересных ссылок на ресурсы по теории функционального программирования и другим языкам (Standard ML, Clean).

cm.bell-labs.com/cm/cs/what/smlnj – Standard ML of New Jersey. Очень хороший компилятор. В бесплатный дистрибутив помимо компилятора входят утилиты MLYacc и MLLex и библиотека Standard ML Basis Library. Отдельно можно взять документацию по компилятору и библиотеке.

www.harlequin.com/products/ads/ml/ – Harlequin MLWorks, коммерческий компилятор Standard ML. Однако в некоммерческих целях можно бесплатно пользоваться версией с несколько ограниченными возможностями.

caml.inria.fr – институт INRIA. Домашний сайт команды разработчиков языков Caml Light и Objective Caml. Можно бесплатно скачать дистрибутив Objective Caml, содержащий интерпретатор, компиляторы байт-кода и машинного кода, Yacc и Lex для Caml, отладчик и профайлер, документацию, примеры. Качество компилированного кода у этого компилятора очень хорошее, по скорости опережает даже Standard ML of New Jersey.

clean/ – содержит дистрибутив компилятора с языка Clean. Компилятор коммерческий, но допускается бесплатное использование в некоммерческих целях. Из того, что компилятор коммерческий, следует его качество (очень быстр), наличие среды разработчика, хорошей документации и стандартной библиотеки.

Список используемых источников

1. Хювёнен Э., Сеппенен И. Мир Lisp’а. В 2-х томах. М.: Мир, 1990.

2. Бердж В. Методы рекурсивного программирования. М.: Машиностроение, 1983.

3. Филд А., Харрисон П. Функциональное программирование. М.: Мир, 1993.

4. Хендерсон П. Функциональное программирование. Применение и реализация. М.: Мир, 1983.

5. Джонс С., Лестер Д. Реализация функциональных языков. М.: Мир, 1991.

6. Henson M. Elements of functional languages. Dept. of CS. University of Sassex, 1990.

7. Fokker J. Functional programming. Dept. of CS. Utrecht University, 1995.

8. Thompson S. Haskell: The Craft of Functional Programming. 2-nd edition, Addison-Wesley, 1999.

9. Bird R. Introduction to Functional Programming using Haskell. 2-nd edition, Prentice Hall Press, 1998.

Итак, вы хотите научиться функциональному программированию (Часть 1)

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

Обучение вождению

Когда мы только учились водить машину, мы старались изо всех сил. Конечно, это выглядело легко, когда мы смотрели, как водят другие люди. Но на деле всё оказывалось сложнее.

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

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

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

Вспомните, на что был похож первый раз за рулём другой машины? Было ли это похоже на самый первый раз за рулём машины вообще? Даже не близко. В первый раз всё было таким незнакомым. Конечно, мы сидели до этого в машине, но только в роли пассажира. На этот раз мы оказывались в сидении водителя. Один на один со всеми рычагами, кнопками и педалями.

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

После всего этого мы вели свою машину как по маслу. Но почему в этот раз всё было так просто по сравнению с первым разом?

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

Может, несколько вещей были реализованы как-то иначе и, может быть, они имели какие-то дополнительные функциональные возможности, но мы и так не использовали их во всём нашем водительском опыте. Рано или поздно мы изучали всё новые примочки. Как минимум, те, что нам реально требовались.

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

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

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

Ваш первый космический корабль

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

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

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


Однако физика не изменилась. Путь, по которому вы двигаетесь, находится в пределах всё той же Вселенной.

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

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

Забудьте всё, что вы знаете

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

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

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

Вспомните, как вы, чтобы выехать с проезжей части, давали задний ход на машине. Но на космическом корабле нет механизма реверса. Теперь вы должны подумать: “ЧТО? НЕТ ЗАДНЕГО ХОДА? КАК Я ДОЛЖЕН ВОДИТЬ БЕЗ ЗАДНЕГО ХОДА?”.

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

Изучение функционального программирования требует времени. Запаситесь терпением.

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

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

Пожалуйста, не спешите. С этого момента не торопитесь и находите время, чтобы понять примеры кода. Лучше будет даже сделать небольшую паузу в прочтении после этой части статьи и дать озвученным идеям “устаканиться”. Затем возвращайтесь к чтению.

Самое главное — это то, чтобы вы поняли.

Чистота

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

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

Вот пример чистой функции:

Заметьте, что функция add не прикасается к переменной z . Она не читает её значения и ничего не пишет в неё. Функция читает только x и y , свои входные данные, и возвращает результат их суммы.

Это и есть чистая функция. Если функция add имеет доступ к переменной z , она больше не может быть чистой.

Это пример другой чистой функции:

Если функция justTen чистая, она может возвращать только значение-константу. Почему?

Потому что мы не даём ей никаких входных данных. А значит, чтобы быть чистой, она не должна изменять никаких переменных, кроме тех, что были ей переданы. Единственное, что может возвратить такая функция — константа.

Пока функции, не принимающие параметров, не работают, они не очень полезны. Было бы лучше объявить justTen просто как константу.

Более полезные чистые функции принимают хотя бы один параметр.

Взгляните на этот пример:

Посмотрите, эта функция ничего не возвращает. Она складывает x и y , записывает результат в переменную z , но не возвращает её.

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

Все полезные чистые функции должны возвращать что-нибудь.

Давайте рассмотрим пример с первой функцией add ещё раз:

Обратите внимание, что add(1, 2) в результате всегда даёт 3 . Конечно, сюрприз не большой, но это потому что функция чистая. Если бы функция add брала значение откуда-то снаружи, вы бы никогда не могли наверняка предсказать её поведение.

Чистая функция всегда возвращает одинаковые значения для одинаковых входных данных .

Поскольку чистые функции не могут изменять внешние переменные, все эти функции являются нечистыми:

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

Чистые функции не имеют побочных эффектов.

В таких языках императивного программирования как JavaScript, Java и C# побочные эффекты везде. Это делает отладку проблематичной, потому что в коде Вашей программы переменная может быть изменена где угодно. В общем, если у Вас баг из-за переменой, принявшей неверное значение в неподходящее время, где Вы будете искать ошибку? Везде? Так дело не пойдёт.

На этом месте, вы, вероятно, думаете: “КАК, ЧЁРТ ПОБЕРИ, Я СДЕЛАЮ ХОТЬ ЧТО-НИБУДЬ ОДНИМИ ТОЛЬКО ЧИСТЫМИ ФУНКЦИЯМИ?”.

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

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

Неизменяемость

Вы помните, когда впервые увидели следующий код:

И тот, кто учил вас программированию, говорил забыть изученное на уроках математики. Ведь в математике x никогда не мог равняться x + 1 .

Но в императивном программировании данный код означает «взять текущее значение x , прибавить к нему 1 , положить результат обратно в x ».

Что ж, в функциональном программировании выражение x = x + 1 недопустимо. Так что Вам надо вспомнить то, что вы забыли из математики. Если так можно выразиться.

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

Сохранённые значения всё ещё называются переменными по историческим причинам, но они являются константами, то есть x, однажды приняв какое-либо значение, сохраняет его на всю жизнь.

Не волнуйтесь, x – это обычно локальная переменная, так что её жизнь достаточно коротка. Но пока она жива, она никак не изменится.

Вот пример переменной-константы в Elm — чистом языке функционального программирования для web-разработки:

Если вы не знакомы с синтаксисом семейства языков программирования ML, позвольте мне объяснить. addOneToSum – это функция, принимающая 2 параметра: y и z .

Внутри блока let x приписывается значение 1 , то есть он равен 1 до конца своей жизни. Его жизнь кончается, когда происходит выход из функции, или, более точно, когда исполняется блок let .

Внутри блока in вычисления могут включать значения, объявленные в блоке let , а именно: x . Возвращается результат вычисления x + y + z или, в точности, возвращается 1 + y + z , так как x = 1 .

И снова я могу услышать, как вы вопрошаете: “КАК, ЧЕРТ ПОБЕРИ, Я ДОЛЖЕН СДЕЛАТЬ ХОТЬ ЧТО-НИБУДЬ БЕЗ ПЕРЕМЕННЫХ?!”.

Давайте подумаем, когда обычно мы хотим изменить переменную. Всего две основных причины, которые приходят на ум: многозначные изменения (например, изменение отдельного значения объекта или записи) и однозначные изменения (например, счётчики цикла).

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

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

Да, кстати, и всё это без циклов.

“СНАЧАЛА БЕЗ ПЕРЕМЕННЫХ, А ТЕПЕРЬ ЕЩЁ И БЕЗ ЦИКЛОВ? Я ТЕБЯ НЕНАВИЖУ. ”

Попридержите коней. Это не значит, что мы не можем использовать циклы, просто здесь нет таких характерных операторов как for , while , do , repeat и так далее.

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

Вот два примера реализации цикла в JavaScript.

Обратите внимание, как рекурсия в функциональном подходе осуществляет то же самое, что и оператор цикла for , вызывая саму себя с новым параметром запуска (start + 1) и с новым счетчиком (acc + start) . Она не изменяет старых значений. Вместо этого она использует новые значения, высчитанные из старых.

К сожалению, такие примеры не очевидны в JavaScript (даже если вы потратили некоторое время на их изучение) по двум причинам. Во-первых, синтаксис JavaScript засорён, а во-вторых, вы, вероятно, не привыкли думать рекурсивно.

Пример на языке Elm читать и, следовательно, понимать легче:

Так этот код выполняется:

Вам скорее всего кажется, что циклы for гораздо легче для понимания. Хотя это спорно и скорее всего является вопросом осведомлённости, не-рекурсивные циклы подразумевают изменчивость, что по своей сути плохо.

Я не объясняю здесь преимущества использования парадигмы неизменяемости, но вы можете посмотреть параграф под названием Global Mutable State в статье Why Programmers Need Limits, если хотите изучить эту тему.

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

Также, если программа многопоточная, исполнение никакого потока не разрушит ваши планы. Поскольку значение — константа и если поток захочет изменить его, ему придётся создать новое значение из старого.

Ещё в середине девяностых я написал игровой движок для Creator Crunch и самый большой источник ошибок был связан с вопросом многопоточности. Я хотел бы знать про неизменяемость в то время. Но тогда меня больше волновала разница между двух и четырёх скоростными приводами CD-ROM при игре.

Неизменяемость делает код проще и безопаснее.

Мой мозг.

Пока что достаточно.

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

Кафедра математических и информационных технологий СПбАУ РАН

Main menu

Видео о кафедре

Семинары

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

Программа курса

Лямбда-исчисление.

Введение. Функциональное и императивное программирование.
Лямбда-исчисление. Применение и абстракция. Свободные и связанные переменные.

Комбинаторы. Функции нескольких переменных, каррирование. Подстановка, лемма подстановки.

Бета-преобразование. Эта-преобразование. Расширение чистого
лямбда-исчисления: дельта-преобразование.

Лямбда-исчисление как язык программирования. Булевы значения,
пары. Каррирование. Числа Чёрча, простейшие операции над ними.

Рекурсия. Редукция.

Теорема о неподвижной точке, Y-комбинатор. Редексы.
Одношаговая и многошаговая редукция. Нормальная форма. Редукционные графы.

Теорема Чёрча-Россера. Следствия: редуцируемость к нормальной форме,
единственность нормальной формы.

Cтратегии редукции. Теорема о нормализации. Механизмы вызова в функциональных языках.

Числа Чёрча: предшествование, вычитание. Примитивная рекурсия. Списки.
Комбинаторы неподвижной точки Карри и Тьюринга.

Просто типизированное лямбда-исчисление.

Роль типов в языках программирования. Предтермы. Утверждения о
типизации. Контексты.

Правила типизации по Карри и по Чёрчу. Деревья вывода типов.
Свойства типизированного лямбда-исчисления. Связь между системами Карри
и Чёрча.

Проблемы разрешимости. Сильная и слабая нормализация. Соответствие
Карри-Говарда.

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

Введение в Haskell.

Стандарт языка. Компилятор GHC. Интерпретатор GHCi. Hoogle. Связывание.
Кодирование функций. Рекурсия.

Основные синтаксические конструкции. Система модулей.


Частичное применение, каррирование. Инфиксные операторы, сечения. Бесточечный стиль.

Кодирование рекурсивных функций.

Программирование на языке Haskell.

Ошибки. Основание. Строгие и нестрогие функции. Ленивое и энергичное
исполнение. Функция seq.

Алгебраические типы данных. Сопоставление с образцом, его семантика.

Объявления type и newtype. Метки полей.

Списки, стандартные функции для работы с ними. Функции высших порядков.
«Бесконечные» структуры данных. Генерация (выделение) списков.

Система типов Haskell.

Параметрический и специальный полиморфизм. Классы типов. Объявления
представителей (instance declaration). Пример: классы Eq и Ord.

Операторы над типами как параметры в определении класса. Класс типов Functor.

Реализация классов типов.

Стандартные классы типов: Enum и Bound, Num и его наследники, Show и Read.

Аппликативные функторы и свёртки.

Законы для функторов. Класс типов Applicative и его представители.
Два способа объявления списка аппликативным функтором. Класс Alternative.

Моноиды. Представители класса типов Monoid.

Свёртки списков. Правая и левая свёртки. Ленивые и энергичные версии свёрток.

Класс типов Foldable.

использование аппликативных функторов и свёрток.

Монады.

Монады. Класс типов Monad. Пример: монада Identity.

Законы класса типов Monad. do-нотация.

Монада Maybe: вычисления, которые могут завершиться неудачей.

Монада списка: вычисления со множественными результатами.

Программирование с помощью стандартных монад.

Использование монад.

Ввод-вывод в чистых языках. Монада IO. Взаимодействие с файловой системой.
Монады для записи в лог, чтения из внешнего окружения и работы с изменяемым состоянием: Reader, Writer, State.

Ввод-вывод. Работа с псевдослучайными величинами.

Трансформеры монад.

Класс Alternative. Парсеры регулярных выражений. Класс MonadPlus.

Монада Error: вычисление, которое может вызвать исключение.

Монада Cont: управление порядком вычислений.

Проблема комбинирования монадических эффектов. Трансформеры монад.

Монадические вычисления с множественными эффектами.

Вывод типов.

Вывод типов. Главный (наиболее общий) тип. Свойства подстановки типов.

Унификатор, теорема унификации. Главная пара. Алгоритм Хиндли-Милнера.

Реализация алгоритма вывода типов на Haskell.

Полиморфные системы типов.

Сильный и слабый полиморфизм. Let-полиморфизм. Полиморфизм высших рангов.
Универсальные абстракция и применение. Импредикативность. Сильная нормализация.
Программирование в полиморфных системах.

Система с зависимыми типами. Семейства типов. Виды для семейств типов. Тип зависимого произведения.

Обобщенные алгебраические типы данных (GADTs). Экзистенциальные типы.
Семейства типов в Haskell. Программирование на типах.

Параметричность.

Параметричность как свойство полиморфных систем. Теорема Рейнольдса.
Свободные теоремы для полиморфных типов.

Оптимизации с помощью правил переписывания в GHC. Правило fold/build.

Чисто функциональные структуры данных.

Неизменяемые структуры данных и эффективные алгоритмы для них. Роль
ленивости.
Аммортизированная сложность. Зипперы. Список с произвольным доступом
(flexible array).

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

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

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

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

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

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

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

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

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

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

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

Кстати, бинарные операции » + «, » — «, » * «, » / «, которые записываются в выражениях, являются «математическими» функциями над двумя аргументами — операндами. Их используют настолько часто, что синтаксис языка программирования имеет для них более короткую запись . Модуль operator позволяет представлять эти операции в функциональном стиле:

Полезные ресурсы для программистов

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

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

Интеллектуальные и умные

1. ХабрХабр
Конечно, на Хабре не только статьи об IT, но и масса занимательной информации по дизайну, менеджменту, обучению и т.д. Однако, если вы спросите у программиста, что он читает чаще всего, ответ будет один – Хабр.
2. RSDN
Стоящий ресурс, на котором вы можете найти книги, обсудить проблемы на форуме, прочитать статьи по актуальным вопросам. Разработчики создавали этот ресурс, чтобы восполнить пробелы в знаниях программистов и компенсировать нехватку материалов на русском языке. Согласитесь, получилось неплохо?
3. Microsoft Developer Network
Если вам интересны продукты компании Microsoft, тогда онлайн журнал поможет вам ознакомиться с ними более детально.
4. SQL.ru
Если вы думаете, что это ресурс об SQL, то ошибаетесь. Программисты найдут неплохой форум, подборку отличной литературы, что особенно полезно новичкам, предложения по работе и не только.
5. Хакер
Сайт журнала «Хакер». Несмотря на то, что здесь немного специализированной информации по программированию, вы найдете массу околотематических статей. Кроме того, только тут множество советов и рекомендаций по защите от взломов.
6. ACMQUEUE
Статьи, видео, аудио по тематике. На английском языке, зато полезно и по делу.
7. The Register
Нельзя не отметить данный новостной ресурс. О последних событиях в IT-сфере, разработках и продуктах, вы, без сомнения, узнаете именно на The Register.
8. OpenNET
Отличный профессиональный ресурс, где масса новостей, форум и полезные материалы.
9. DOU
Нужно, потому что тут есть вакансии, оповещения о семинарах, тренингах, онлайн-конференциях и прочих необходимых вещах. Еще Ленин завещал учиться, поэтому такие ресурсы лишними не бывают.
10. Driver.ru
Огромная библиотека драйверов. Особенно полезно для молодых мастеров.

Обучение (и не обязательно платное)

1. MITOPENCOURSEWARE
Более 2000 курсов по различной тематике. Бесплатные ресурсы предлагают вам учебники, руководства, проекты, мультимедийные материалы и многое другое.
2. COURSERA
Уникальный проект, разработанный профессорами Стенфордского университета. Более 200 курсов из 33 стран мира. И все это бесплатно!
3. TheCodePlayer
Если вы часто заглядываете программисту через плечо и пытаетесь понять, чем он занимается, посетите данный ресурс. Пошаговые видео-руководства демонстрируют, как создаются с нуля крутейшие вещи.
4. Codecademy
Обучайтесь самостоятельно или с друзьями. Здесь довольно весело и, между прочим, бесплатно!
5. GENERAL ASSEMBLY
Интересные и полезные livestream. Вы можете приобрести электронный билет и получить доступ.
6. ELOQUENT JAVASCRIPT
Введение в Java Script и программирование. Отличная книга с примерами и разборами.
7. Learn Ruby
Всем, кто интересуется Ruby, это, без сомнений, придется по душе.
8. LCodeTHW
Изначально это был проект по изучению Python, однако впоследствии значительно расширился до Ruby, C, SQL, Regex.
9. udemy
Огромное количество, как платных, так и бесплатных курсов. Примечательно, что среди лекторов есть Марк Цукерберг.
10. treehouse
Более 600 видео-уроков по языкам программирования и не только. За ежемесячную плату.

Общение и обмен знаниями

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

Структура программного обеспечения

Читайте также:

  1. A.3.1 Структура процедурного программного обеспечения
  2. I. ПОНЯТИЕ, ПРЕДМЕТ, ЦЕЛИ И ЗАДАЧИ КУРСА. СТРУКТУРА КУРСА, ВЗАИМОСВЯЗЬ С ДРУГИМИ УЧЕБНЫМИ ДИСЦИПЛИНАМИ.
  3. I. ПОНЯТТЯ ВИДУ І ПОПУЛЯЦІЇ. СТРУКТУРА ТА ХАРАКТЕРИСТИКА ПОПУЛЯЦІЇ.
  4. I. ПОНЯТТЯ ВИДУ І ПОПУЛЯЦІЇ. СТРУКТУРА ТА ХАРАКТЕРИСТИКА ПОПУЛЯЦІЇ.
  5. I. Разрабатывается общая структура ИС с выделением функциональных и обеспечивающих подсистем.
  6. I. Страховой рынок и его структура.
  7. II. Структура индивидуального логопедического занятия.
  8. II. Структура Уложения
  9. III. Внутренняя структура политического процесса с позиций отношений субъект объект, или субъект – субъект, изучался поведенческим подходом.
  10. V Структура субъективного мира человека
  11. Аварии на системах жизнеобеспечения
  12. Автоматизированная система документационного обеспечения

Тема 3. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

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

Структура программного обеспечения

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

· на обеспечение устойчивой работы компьютера и вычислительной сети;

· на создание условий для нормальной работы прикладных про­грамм;

· на выполнение вспомогательных операций;

· на диагностику аппаратной части компьюте­ра и вычислительной сети;

Все множество системных программ можно разделить на две большие группы: базовое ПО и сервисные системы. Базовое программное обеспе­че­ние — это мини­мальный набор про­граммных средств, обеспечивающих ра­боту компьютера.

Базовый подкласс ПО включает:

· операционные системы(ОС) — комплекс программ, управляющих про­цес­сом вы­пол­нения прикладных программ, планированием и управлением вычис­литель­ными ресур­сами ПК (ОС берет на себя выполне­ние таких операций, как кон­троль работоспо­собности оборудова­ния ПК; выпол­не­ние проце­дуры на­чальной за­грузки; управле­ние работой всех уст­ройств ПК; управле­ние фай­ловой систе­мой; взаимодействие пользователя с ПК; за­грузка и выполне­ние при­клад­ных про­грамм; распределение ресурсов ПК — опе­ративной памяти, процессорного вре­мени и пери­ферийных уст­ройств между при­кладными програм­мами).

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

· сетевые операционные системы — комплекс программ, обес­печивающих обра­ботку, передачу и хранение данных в сети.

До недавнего времени на большинстве ПК была установлена операци­онная сис­тема MS DOS, которая была создана в 1981 г. фир­мой Microsoft (заметим, что она не была ори­гинальной разработкой самой Microsoft — ком­пания Билла Гейтса лишь дорабо­тала «операци­онку» под названием QDOS, созданную другой компанией). До появления Windows дисковая операцион­ная система MS DOS была самой популярной и массовой в применении. В ее среде создано целое поколение программного продукта. На основе MS DOS в процессе развития компьютерных технологий появился Windows (с 1996 г. MS DOS включена в состав операционной среды Windows 95). Основные компоненты ОС, развитые в среде MS DOS, являются классикой, и орга­нично включены в Windows на новом этапе раз­вития программного обеспе­чения в целом и его сердцевины — операционных систем.

MS DOS 16-разрядная однозадачная операционная сис­тема, обладающая «интер­фейсом ко­манд­ной строки», компактна, предъяв­ляет скром­ные требо­ва­ния к аппаратуре и вы­полняет необ­ходимый мини­мум функций для поль­зователей и программ. Основ­ные недос­татки DOS:

· главным ее уяз­вимым ме­стом является работа с ограниченной оператив­ной памятью (в эпоху созда­ния MS-DOS оперативная па­мять большин­ства компьюте­ров не превышала 256 ки­лобайт. DOS мог­ла работать с 640 ки­лобай­тами ОП, и Билл Гейтс ут­верждал, что никому и никогда не понадо­бится больший объем, но время шло и появились программы, ко­то­рым требовался для работы больший объем опера­тив­ной памяти и при­ходи­лось ис­пользовать специальные про­граммы — ме­неджеры памяти, но и они не ре­шали проблему);

· вторым недос­татком DOS была не­возможность работы в полно­ценном гра­фическом ре­жиме (хотя то­гдашние ком­пь­ютеры уже могли бы обеспе­чить его под­держку);

· третьим недостат­ком MS-DOS была однозадачность.

Операционные системы се­мейства DOS, несмотря на свою про­стоту и экономичность, мо­рально устарели, и на смену им пришли опе­рацион­ные системы нового поко­ления. К числу таких ОС относятся операционные сис­темы се­мейства Windows, операци­онные системы семейства Unix и др.

Сервисные системы — предназначены для обслуживания компьютера (расши­ряют возможности базового ПО). По функциональному признаку среди сервисного ПО можно выделить:

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

· антивирусные программы (обеспечивающие защиту компь­ютера, обнаруже­ние и восстановление зараженных файлов);

· программы архивирования данных (обеспечивают процесс сжатия ин­форма­ции в файлах с целью уменьше­ния объема памяти для ее хранения);

· программы обслуживания сети.

· программы диагностики работоспособности компьютера;

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

Системы программирования или инструментальные системы— это про­грамм­ные продукты, поддержки технологии программирования. В рамках этого на­правле­ния существуют средства для создания приложений, вклю­чающие:

· локальные средства, обеспечивающие выполнение отдельных работ по созда­нию программ;

· интегрированные среды разработчиков программ, обеспечивающие вы­полне­ние комплекса взаимосвязанных работ по созданию программ.

Локальные средства разработки про­грамм включают языки и системы про­грам­мирования, а также инструментальную среду пользователя. Сущест­вуют ма­шинные языки программирования (воспринимаемые аппаратной ча­стью компью­тера ма­шин­ные коды), машинно-ориентированные языки (языки программирова­ния, кото­рые отражают структуру конкретного типа компью­тера – ассемб­леры), алго­ритмические (универсальные) языки, не зависящие от архитектуры компьютера, напри­мер, Фор­тран (Fortran), Ко­бол (Cobol), Алгол (Algol), Пас­каль (Pascal), Бейсик (Basic), Си (C), Си++ (C++) и др.; процедурно-ориентированные языки (где име­ется возмож­ность описания про­граммы как совокупности процедур – подпро­граммы), про­блемно-ориен­тированные языки (предназначенные для решения задач оп­реде­ленного класса), интегрирован­ные системы программирования. Заметим, что класси­фикация языков программирования не закреплена ГОСТами (в учебных це­лях обычно проводится их классификация по различным призна­кам). Про­грамма, подго­товленная на языке программи­рования, проходит этап трансля­ции, отладки и тести­рования.

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

Кроме того, существуют средства для создания сложных информацион­ных сис­тем (CASE – технология). Проектирование информационных систем представ­ляет собой трудоемкую и дли­тельную работу, требующую высокой ква­лификации участ­вующих в ней специалистов. В недале­ком прошлом про­ектирование нередко выпол­нялось на интуитивном уровне неформализован­ными методами, включаю­щими в себя элементы искусства, практический опыт, экспертные оценки и дорого­стоящие экспериментальные проверки ка­чества функционирования. В начале 70-х гг. в США был отмечен кризис про­граммирования (software crisis). Это выра­жалось в том, что боль­шие проекты стали выполняться с отставанием от гра­фика или с превышением сметы рас­хо­дов, разработанный продукт не обладал тре­буемыми функцио­нальными возможностями, произ­водительность его была низка, ка­чество получаемого про­граммного обеспечения не устраивало потре­бителей. Потребность кон­тролировать процесс разработки ПО, прогнози­ровать и гаран­тировать стои­мость разработки, сроки и качество ре­зультатов привела к необ­ходимости пере­хода от кус­тарных к индустриальным способам создания ПО и по­явле­нию совокупности инже­нерных методов и средств создания ПО, объеди­нен­ных общим названием «программная инжене­рия» (software engineering). В основе про­граммной инженерии лежит сле­дующая идея: проектиро­вание ПО является фор­мальным процессом, который можно изучать и совершенство­вать. К концу 80-х гг. было проведено много исследований в области про­грамми­рования (разработка и внедрение языков высокого уровня, мето­дов струк­турного и модульного програм­мирования, языков проектирова­ния и средств их под­держки, формальных и нефор­мальных языков описания сис­темных требований и спецификаций и т. д.). Термин CASE (Computer Aided Software Engineering) имеет весьма широкое толкование. Первоначально зна­чение термина CASE ограни­чива­лось вопросами автоматизации раз­работки только лишь программного обеспече­ния, а в на­стоящее вре­мя оно при­обрело новый смысл и охватывает про­цесс разра­ботки сложных инфор­мационных систем в целом. CASE-технология представляет собой совокупность методов про­ектирования информационных сис­тем, а также набор инструментальных средств, позво­ляющих в наглядной форме моделировать предметную об­ласть, ана­лизиро­вать эту модель на всех ста­диях раз­работки и со­провожде­ния, разрабатывать приложения в соответствии с информаци­он­ны­ми потреб­ностями пользователей. Большинство существующих CASE-средств осно­вано на методах структурного или объектно-ори­ентированного анализа и проек­тирования, использую­щих специфи­кации в виде диаграмм или текстов для описания внешних требова­ний, свя­зей между моделями системы, дина­мики поведе­ния сис­темы и архитектуры про­граммных средств.

Прикладные программы — предназна­чены для реше­ния прикладных задач пользо­вателя (обеспечивает выполнение необходи­мых пользова­телю за­дач на ком­пью­тере). Условно (по их назначению) можно выделить следую­щие под­классы:

· программы обработки текстов;

· программы обработки фото- и видеоизображений;

· программы подготовки презентаций;

· системы управления базами данных;

· программы эко­номического и статистического анализа;

· сис­темы автомати­зированного проектирования (САПР);

· сетевое программное обеспечение (программы для работы с электронной почтой, доступ к ви­деоконференциям, браузеры Интернет и т.д.);

Прикладное программное обеспе­че­ние состоит из пакетов прикладных про­грамм (ППП) и прикладных про­грамм пользователя.

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

Дата добавления: 2014-01-11 ; Просмотров: 7689 ; Нарушение авторских прав? ;

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

Мастер Йода рекомендует:  NLP – это весело! Обработка естественного языка на Python
Добавить комментарий