Лекция
Привет, мой друг, тебе интересно узнать все про функциональное программирование, тогда с вдохновением прочти до конца. Для того чтобы лучше понимать что такое функциональное программирование , настоятельно рекомендую прочитать все из категории Функциональное программирование.
функциональное программирование ставит своей целью
придать каждой программе простую математическую интерпретацию.
Эта интерпретация должна быть независима от деталей исполнения и
понятна людям, которые не имеют научной степени в предметной области.
Лоренс Паулсон
Прежде чем начать описание собственно функционального программирования, необходимо обратиться к истории программирования вообще. В 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.
В качестве основных свойств функциональных языков кратко рассмотрим следующие:
Программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных языках. Об этом говорит сайт https://intellect.icu . Сравним программы на C и на абстрактном функциональном языке на примере сортировки списка быстрым методом Хоара (пример, уже ставший классическим при описании преимуществ функциональных языков).
Пример 1. Быстрая сортировка Хоара на C.
void quickSort (int a[], int l, int r)
{
int i = l;
int j = r;
int x = a[(l + r) / 2];
do
{
while (a[i] < x) i++;
while (x < a[j]) j--;
if (i <= j)
{
int temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
}
while (i <= j);
if (l < j) quickSort (a, l, j);
if (i < r) quickSort (a, i, r);
}
Пример 2. Быстрая сортировка Хоара на абстрактном функциональном языке.
quickSort ([]) = [] quickSort ([h : t]) = quickSort (n | n t, n <= h) + [h] + quickSort (n | n t, n > h)
Пример 2 следует читать так:
1. Если список пуст, то результатом также будет пустой список.
2. Иначе (если список не пуст) выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет являться конкатенация (сращивание) отсортированного списка из всех элементов хвоста, которые меньше либо равны голове, списка из самой головы и списка из всех элементов хвоста, которые больше головы.
Пример 3. Быстрая сортировка Хоара на языке Haskell.
quickSort [] = [] quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]
Как видно, даже на таком простом примере функциональный стиль программирования выигрывает и по количеству написанного кода и по его элегантности.
Кроме того, все операции с памятью выполняются автоматически. При создании какого-либо объекта под него автоматически выделяется память. После того как объект выполнит свое предназначение, он вскоре будет также автоматически уничтожен сборщиком мусора, который является частью любого функционального языка.
Еще одним полезным свойством позволяющим сократить программу является встроенный механизм сопоставления с образцом. Это позволяет описывать функции как индуктивные определения. Например:
Пример 4. Определение N-ого числа Фибоначчи.
fibb (0) = 1 fibb (1) = 1 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. Эта функция применяет некоторую функцию ко всем элементам списка, формируя из результатов заданной функции другой список. Например, определив функцию возведения целого числа в квадрат как:
square (N) = N * N
Можно воспользоваться функцией 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. Получение остаточной процедуры.
Если даны следующие объекты:
P (x1, x2, ..., xn) — некоторая процедура.
x1 = a1, x2 = a2 — известные значения параметров.
x3, ..., xn — неизвестные значения параметров.
Требуется получить остаточную процедуру P1 (x3, ..., xn). Эта задача решается только на узком классе программ.
2. Построение математического описания функций.
Пусть имеется программа P. Для нее определены входные значения и выходные значения . Требуется построить математическое описание функции
f : Dx1, ..., Dxn -> Dy1, ..., Dym.
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.
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.
www.cs.kun.nl/~clean/ — содержит дистрибутив компилятора с языка Clean. Компилятор коммерческий, но допускается бесплатное использование в некоммерческих целях. Из того, что компилятор коммерческий, следует его качество (очень быстр), наличие среды разработчика, хорошей документации и стандартной библиотеки.
Я хотел бы услышать твое мнение про функциональное программирование Надеюсь, что теперь ты понял что такое функциональное программирование и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Функциональное программирование
Комментарии
Оставить комментарий
Функциональное программирование
Термины: Функциональное программирование