Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м исправил ударения: больш́их — больши́х
м Кавычки "" -> «», пробелы т.д. -> т. д.
Строка 8:
Перед началом описания непосредственно [[w:Функциональное программирование|функционального программирования]] следует обратиться к истории [[w:Программирование|программирования]] вообще. В 1940-х годах появились первые цифровые [[w:Компьютер|компьютеры]], которые программировались переключением различного рода тумблеров, проводков и кнопок. Число таких переключений достигало порядка нескольких сотен и росло с усложнением программ. Потому следующим шагом развития программирования стало создание всевозможных [[w:Язык ассемблера|ассемблерных языков]] с простой [[w:Мнемоника|мнемоникой]].
 
Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, а всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Шагом после ассемблера стали так называемые [[w:Процедурное программирование|императивные языки]] [[w:Высокоуровневый язык программирования|высокого уровня]]: [[w:Бейсик|Бейсик]], [[w:Паскаль|Паскаль]], [[w:Си (язык программирования)|Си]], [[w:Ada|Ada]] и прочие, включая [[w:Объектно-ориентированное программирование|объектно-ориентированные]]. Императивными («предписывающими») такие языки названы потому, что ориентированы на последовательное исполнение инструкций, работающих с памятью (т. е. [[w:Присваивание (программирование)|присваиваний]]), и итеративные [[w:Цикл (программирование)|циклы]]. Вызовы функций и процедур, даже [[w:Рекурсия|рекурсивные]], не избавляли такие языки от явной императивности.
 
В [[w:Парадигма программирования|парадигме]] функционального программирования краеугольный камень, — это [[w:Функция (программирование)|функция]]. Вспомнив историю [[w:Математика|математики]], можно оценить возраст понятия «функция»: ему уже́ около четырёхсот лет, и математики придумали очень много теоретических и практических аппаратов для оперирования функциями, начиная от обыкновенных операций [[w:Дифференцируемая функция|дифференцирования]] и [[w:Интеграл Римана|интегрирования]], заканчивая заумными [[w:Функциональный анализ|функциональными анализами]], теориями [[w:Нечёткое множество|нечётких множеств]] и функций [[w:Комплексное число|комплексных переменных]].
 
Математические функции выражают связь между исходными данными и итоговым продуктом некоторого процесса. Процесс [[w:Вычисление|вычисления]] также имеет вход и выход, поэтому функция — вполне подходящее и адекватное средство описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно через самих себя. При выполнении программы функции получают параметры, вычисляют и возвращают результат, при необходимости вычисляя значения других функций. На функциональном языке программист не должен описывать порядок вычислений. Нужно просто описать желаемый результат как систему функций.
Строка 20:
Как известно, теоретические основы императивного программирования были заложены ещё в [[w:1930-е|1930-х]] годах [[w:Тьюринг, Алан Матисон|Аланом Тьюрингом]] и [[w:Нейман, Джон фон|Джоном фон Нейманом]]. Теория, положенная в основу функционального подхода, также родилась в 20-х — 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать [[w:Шёнфинкель, Мозес|Мозеса Шёнфинкеля]] и [[w:Карри, Хаскелл|Хаскелла Карри]], разработавших [[w:Комбинаторная логика|комбинаторную логику]], и [[w:Чёрч, Алонзо|Алонзо Чёрча]], создателя [[w:Лямбда-исчисление|λ-исчисления]].
 
Теория так и оставалась теорией, пока в начале 1950-х годов [[w:МакКартиМаккарти, Джон|Джон МакКартиМаккарти]] не разработал язык [[w:Лисп|Лисп]], который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется (также как и [[w:Фортран|Фортран]]), после многих лет эволюции он удовлетворяет современным запросам, которые заставляют разработчиков программ взваливать как можно бо́льшую но́шу на [[w:Компилятор|компилятор]], облегчив так свой труд. Нужда в этом возникла из-за всё более возрастающей сложности [[w:Программное обеспечение|программного обеспечения]].
 
В связи с этим обстоятельством всё бо́льшую роль начинает играть [[w:Типизация|типизация]]. В конце 70-х — начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как [[w:Абстракция данных|абстракция данных]] и [[w:Полиморфизм в языках программирования|полиморфизм]]. Появляется множество типизированных функциональных языков: [[w:ML|ML]], [[w:Scheme|Scheme]], [[w:Hope|Hope]], [[w:MirandaМиранда (язык программирования)|Miranda]], [[w:Clean|Clean]] и многие другие. Вдобавок постоянно увеличивается число диалектов.
 
В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного [[w:Haskell|Haskell]] в честь [[w:Карри, Хаскелл Брукс|Хаскелла Карри]], была создана в начале 90-х годов. Ныне действителен стандарт Haskell-98.
 
Большинство функциональных языков программирования реализуются как [[w:Интерпретация (информатика)|интерпретируемые]], следуя традициям Лиспа (примечание: большая часть современных реализаций Лиспа содержат компиляторы в [[w:Машинный код|машинный код]]). Таковые удобны для быстрой отладки программ, исключая длительную фазу [[w:Компиляция|компиляции]], укорачивая обычный [[w:Разработка программного обеспечения|цикл разработки]]. С другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, [[w:OCaml|Objective Caml]]) или код на [[w:Си (язык программирования)|Си]]/[[w:C++|Си++]] (например, [[w:Glasgow Haskell Compiler|Glasgow Haskell Compiler]]). Что показательно, практически каждый компилятор с функционального языка реализован на этом же са́мом языке. Это же характерно и для современных реализаций Лиспа, кроме того среда разработки Лиспа позволяет выполнять компиляцию отдельных частей программы без остановки программы (вплоть до добавления методов и изменения определений [[w:Класс (программирование)|классов]]).
 
В этом курсе для описания примеров функционального программирования будет использован либо некий абстрактный функциональный язык, приближенный к математической нотации, либо Haskell, бесплатные компиляторы которого можно скачать с сайта [http://www.haskell.org/ haskell.org].
Строка 37:
*[[w:Модульность (программирование)|модульность]];
*функции — это значения;
*[[w:Чистота функции|чистота]] (отсутствие [[w:Побочный эффект (программирование)|побочных эффектов]]);
*[[w:Ленивые вычисления|отложенные (ленивые) вычисления]].
 
=== Краткость и простота ===
 
Программы на функциональных языках обычно короче и проще, чем те же самые программы на императивных языках. Сравним программы на [[w:Си (язык программирования)|Си]] и на абстрактном функциональном языке на примере [[w:Алгоритм сортировки|сортировки]] [[w:Список (информатика)|списка]] [[w:Быстрая сортировка|быстрым методом]] [[w:Хоар, Чарльз Энтони Ричард|Хоара]] (пример, уже ста́вший классическим при описании преимуществ функциональных языков).
 
'''Пример 1. Быстрая сортировка Хоара на [[w:Си (язык программирования)|Си]]'''
 
<!-- <code>void quickSort (int a[], int l, int r)
Строка 67:
}</code> -->
<source lang="C">
void qsort(int * ds, int *de, int *ss){
int vl = *ds, *now = ds, *inl = ss, *ing = ss + (de - ds);
if ( de <= ds + 1 ) return;
for( ; now != de; ++now ){
if ( *now <= vl ) *inl++ = *now;
else *ing-- = *now;
}
*++inl = vl;
qsort(ds, ds + (inl - ss), ss);
qsort(ds + (inl - ss), de, inl + 1);
}
</source>
Строка 93:
 
#Если список пуст, то результатом также будет пустой список.
#Иначе выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет [[w:Конкатенация|конкатенация]] (сращивание) отсортированного списка из всех элементов хвостхвоста меньших либо равных голове, списка из самой головы и списка из всех элементов хвоста бо́льших головы.
 
'''Пример 3. Быстрая сортировка Хоара на языке [[w:Haskell|Haskell]]'''
 
<code>quickSort [] = []
Строка 116:
=== Строгая типизация ===
 
Из современных языков программирования многие суть строго типизированные. Строгая типизация позволяет компилятору [[w:Оптимизация компилятора|оптимизировать]] программы, использовать конкретные типы и [[w:Контейнер (программирование)|контейнеры]] конкретных типов вместо [[w:Шаблон (программирование)|шаблонных]], вариантных типов, более громоздких в реализации. Кроме того, строгая типизация позволяет оградиться от части ошибок, связанных с неожидаемым "«видом"» входных (и выходных) данных, причем это происходит на стадии компиляции, не отнимая на такие проверки время при работе программы. Система типов также способствует "«документированию"» программы: любая [[w:Подпрограмма|подпрограмма]] является функцией в математическом смысле слова, отображая одно множество (входное) на другое (выходное), и типы определяют эти множества. Читабельность программ повышается, если используются псевдонимы типов или сложные типы, собранные на основе простых, вместо базовых элементарных ''целых'', ''строк'' и т.&nbsp;п.
 
В примере с быстрой сортировкой Хоара видно, что есть ещё одно важное отличие между вариантом на Си и вариантом на Хаскеле: функция на Си сортирует список значений типа <code>int</code> ([[w:Целое число|целых чисел]]), а функция на абстрактном функциональном языке — список значений любого типа, принадлежащего к классу упорядоченных величин. Последняя функция может сортировать и список целых чисел, и список [[w:Вещественное число|чисел с плавающей точкой]], и список [[w:Строковый тип|строк]]. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функцию <tt>quickSort</tt> и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным [[w:Полиморфизм в языках программирования|полиморфизмом]], и поддерживается большинством функциональных языков.
Строка 122:
Ещё одно проявление полиморфизма — [[w:Перегрузка функции|перегрузка функций]], позволяющая давать разным, но подобным функциям одинаковые имена. Типичный пример перегруженной операции — обычная [[w:Сложение (математика)|операция сложения]]. Функции сложения для целых чисел и чисел с плавающей точкой различны, но для удобства они носят одно имя. Некоторые функциональные языки помимо параметрического полиморфизма поддерживают и перегрузку операций.
 
В языке [[w:C++|Си++]] имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные <tt>quickSort</tt>. В стандартную библиотеку Си++, — [[w:Standard Template Library|STL]], — входит такая функция и множество других полиморфных функций. Но шаблоны Си++, как и родовые функции [[w:Ада (язык программирования)|Ады]], на самом деле порождают множество перегруженных функций, которые, кстати, нужно каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере [[w:Машинный код|кода]]. А в функциональных языках полиморфная функция <tt>quickSort</tt> — это одна единственная функция.
 
В некоторых языках, например в [[w:Ada|Аде]], строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Для избежания этого, в строго типизированные функциональные языки встроен механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста, — механизм [[w:Приведение типа|вывода типов]]. Известно несколько таких механизмов, однако большинство из них суть разновидности модели типизации [[w:Хиндли, Роджер|Хиндли]] — [[w:Милнер, Робин|Милнера]], разработанной в начале 1980-х. Поэтому в большинстве случаев можно не указывать типы функций.
 
=== Модульность ===
 
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей ([[w:Модульность (программирование)|модулей]]) с чётко определёнными связями между ними. Так облегчается процесс проектирования и последующей поддержки больши́х программных систем. Поддержка модульности не есть свойство именно функциональных языков программирования, но поддерживается большинством таких языков. Существуют очень развитые модульные императивные языки. Примеры: [[w:Модула-2 (язык программирования)|Modula-2]] и [[w:Ада (язык программирования)|Ada-95]].
 
=== Функции суть значения ===
 
В функциональных языках, равно как и вообще в языках программирования и [[w:Математика|математике]], функции могут быть переданы другим функциям в качестве [[w:Аргумент (программирование)|аргумента]] или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются [[w:Функция высшего порядка|функциями высших порядков]] или [[w:Функционал|функционалами]]. Самый, пожалуй, известный функционал — функция <tt>map</tt>. Она применяет некоторую функцию ко всем элементам списка, формируя из результатов заданной функции другой список. Например, определив функцию возведения целого числа в квадрат как:
 
<code>square (N) = N * N</code>
Строка 145:
(отсутствие побочных эффектов)
 
В императивных языках функция в процессе своего выполнения может читать и изменять значения глобальных [[w:Переменная (программирование)|переменных]] и осуществлять операции [[w:ввод/-вывод|ввода/-вывода]]. Поэтому, если вызвать одну и ту же функцию дважды с одним и тем же аргументом, может случиться так, что в качестве результата вычислятся два различных значения. Такая функция называется функцией с побочными эффектами.
 
Описывать функции без побочных эффектов позволяет практически любой язык. Однако некоторые языки поощряют или даже требуют от функции побочных эффектов. Например, во многих объектно-ориентированных языках в функцию-член класса передаётся скрытый параметр (чаще он называется <tt>this</tt> или <tt>self</tt>), который эта функция неявно изменяет.
 
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путём разбора и сбора существующих. О ненужных объектах позаботится встроенный в язык [[w:Сборка мусора|сборщик мусора]]. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов. Однако это не мешает этим языкам имитировать некоторые полезные императивные свойства, такие как [[w:Обработка исключений|исключения]] и изменяемые [[w:Индексный массив|массивы]].
 
Каковы же преимущества чистых функциональных языков? Помимо упрощения анализа программ есть ещё одно — [[w:Параллельные вычислениявычислительные системы|параллелизм]]. Раз все функции для вычислений используют только свои параметры, мы можем вычислять независимые функции в произвольном порядке или параллельно, на результат вычислений это не повлияет. Причём параллелизм этот может быть организован не только на уровне компилятора языка, но и на уровне архитектуры. В нескольких научных лабораториях уже разработаны и используются экспериментальные [[w:Компьютер|компьютеры]], основанные на подобных архитектурах. В качестве примера можно привести Lisp-машину.
 
=== Отложенные вычисления ===
 
В традиционных языках программирования (например, [[w:C++|Си++]]) вызов функции приводит к вычислению всех аргументов. Этот метод вызова функции называется вызов по значению. Если какой-либо аргумент не использовался в функции, то результат вычислений пропадает, следовательно, вычисления были произведены впустую. В каком-то смысле противоположностью вызова по значению является вызов по необходимости. В этом случае аргумент вычисляется, только если он нужен для вычисления результата. Примером такого поведения можно взять оператор [[w:конъюнкция|конъюнкции]] всё из того же [[w:C++|Си++]] (<tt>&&</tt>), который не вычисляет значение второго аргумента, если первый аргумент имеет ложное значение.
 
Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим. На самом деле, в таких языках порядок вычисления строго определён. В качестве примера строгих языков можно привести [[w:Scheme|Scheme]], [[w:Standard MLSML|Standard ML]] и [[w:CaMLCaml Light|CaMLCaml]]. Языки, использующие отложенные вычисления, называются нестрогими. [[w:Haskell|Haskell]] — нестрогий язык, так же как, например, [[w:Gofer|Gofer]] и Miranda. Нестрогие языки зачастую являются чистыми.
 
Очень часто строгие языки включают в себя средства поддержки некоторых полезных возможностей, присущих нестрогим языкам, например бесконечных списков. В поставке [[w:Standard ML|Standard ML]] присутствует специальный модуль для поддержки отложенных вычислений. А [[w:OCaml|Objective Caml]] помимо этого поддерживает дополнительное специальное слово <tt>lazy</tt> и конструкцию для списков значений, вычисляемых по необходимости.
 
== Решаемые задачи ==
Строка 169:
Если даны следующие объекты:
 
*<math>P (x_{1},\, x_{2},\, \ldots, \,x_{n})</math> — некоторая процедура.
*<math>x_{1} = a_{1},\: x_{2} = a_{2}</math> — известные значения параметров.
*<math>x_{3},\, \ldots,\, x_{n}</math> — неизвестные значения параметров.
 
Требуется получить остаточную процедуру <math>P_{1} (x_{3},\, \ldots,\, x_{n})</math>. Эта задача решается только на узком классе программ.
 
'''2.&nbsp;Построение математического описания функций.'''
Строка 199:
В этом разделе приведено краткое описание некоторых языков функционального программирования (очень немногих). Дополнительную информацию можно почерпнуть, просмотрев ресурсы, перечисленные в следующем разделе.
 
#'''[[w:Лисп|Лисп]]''' (List processor). Считается первым функциональным языком программирования. Поддерживает динамическую и факультативно статическую типизацию. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. В стандарт Common Lisp входит Common Lisp Object System (CLOS) - объектная система Common Lisp, которая по многим параметрам превосходит объектные системы в других языках (поддерживает метаобъектный протокол, мультиметоды и т.&nbsp;д.).
#'''ISWIM''' (If you See What I Mean). Функциональный язык-прототип. Разработан Питером Ландиным в 60-х&nbsp;годах XX&nbsp;ве́ка для демонстрации того, каким может быть язык функционального программирования. Вместе с языком П.&nbsp;Ландин разработал и специальную виртуальную машину для исполнения программ на ISWIM’е. Эта виртуальная машина, основанная на вызове-по-значению, получила название SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.
#'''[[w:Scheme|Scheme]]'''. Диалект Lisp’а, предназначенный для научных исследований в области computer science. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем Common Lisp.
Источник — https://ru.wikibooks.org/wiki/Основы_функционального_программирования/Вводная_лекция