Викиучебник

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

Учебник Обсуждение

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

Версия от 23:23, 18 января 2008

571 байт добавлено ,  14 лет назад
м
Кавычки "" -> «», пробелы т.д. -> т. д.
м (исправил ударения: больш́их — больши́х)
м (Кавычки "" -> «», пробелы т.д. -> т. д.)
Перед началом описания непосредственно [[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:Вычисление|вычисления]] также имеет вход и выход, поэтому функция — вполне подходящее и адекватное средство описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно через самих себя. При выполнении программы функции получают параметры, вычисляют и возвращают результат, при необходимости вычисляя значения других функций. На функциональном языке программист не должен описывать порядок вычислений. Нужно просто описать желаемый результат как систему функций.
Как известно, теоретические основы императивного программирования были заложены ещё в [[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].
*[[w:Модульность (программирование)|модульность]];
*функции — это значения;
*[[w:Чистота функции|чистота]] (отсутствие [[w:Побочный эффект (программирование)|побочных эффектов]]);
*[[w:Ленивые вычисления|отложенные (ленивые) вычисления]].
 
=== Краткость и простота ===
 
Программы на функциональных языках обычно короче и проще, чем те же самые программы на императивных языках. Сравним программы на [[w:Си (язык программирования)|Си]] и на абстрактном функциональном языке на примере [[w:Алгоритм сортировки|сортировки]] [[w:Список (информатика)|списка]] [[w:Быстрая сортировка|быстрым методом]] [[w:Хоар, Чарльз Энтони Ричард|Хоара]] (пример, уже ста́вший классическим при описании преимуществ функциональных языков).
 
'''Пример 1. Быстрая сортировка Хоара на [[w:Си (язык программирования)|Си]]'''
 
<!-- <code>void quickSort (int a[], int l, int r)
}</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>
 
#Если список пуст, то результатом также будет пустой список.
#Иначе выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет [[w:Конкатенация|конкатенация]] (сращивание) отсортированного списка из всех элементов хвостхвоста меньших либо равных голове, списка из самой головы и списка из всех элементов хвоста бо́льших головы.
 
'''Пример 3. Быстрая сортировка Хоара на языке [[w:Haskell|Haskell]]'''
 
<code>quickSort [] = []
=== Строгая типизация ===
 
Из современных языков программирования многие суть строго типизированные. Строгая типизация позволяет компилятору [[w:Оптимизация компилятора|оптимизировать]] программы, использовать конкретные типы и [[w:Контейнер (программирование)|контейнеры]] конкретных типов вместо [[w:Шаблон (программирование)|шаблонных]], вариантных типов, более громоздких в реализации. Кроме того, строгая типизация позволяет оградиться от части ошибок, связанных с неожидаемым "«видом"» входных (и выходных) данных, причем это происходит на стадии компиляции, не отнимая на такие проверки время при работе программы. Система типов также способствует "«документированию"» программы: любая [[w:Подпрограмма|подпрограмма]] является функцией в математическом смысле слова, отображая одно множество (входное) на другое (выходное), и типы определяют эти множества. Читабельность программ повышается, если используются псевдонимы типов или сложные типы, собранные на основе простых, вместо базовых элементарных ''целых'', ''строк'' и т.&nbsp;п.
 
В примере с быстрой сортировкой Хоара видно, что есть ещё одно важное отличие между вариантом на Си и вариантом на Хаскеле: функция на Си сортирует список значений типа <code>int</code> ([[w:Целое число|целых чисел]]), а функция на абстрактном функциональном языке — список значений любого типа, принадлежащего к классу упорядоченных величин. Последняя функция может сортировать и список целых чисел, и список [[w:Вещественное число|чисел с плавающей точкой]], и список [[w:Строковый тип|строк]]. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функцию <tt>quickSort</tt> и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным [[w:Полиморфизм в языках программирования|полиморфизмом]], и поддерживается большинством функциональных языков.
Ещё одно проявление полиморфизма — [[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>
(отсутствие побочных эффектов)
 
В императивных языках функция в процессе своего выполнения может читать и изменять значения глобальных [[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> и конструкцию для списков значений, вычисляемых по необходимости.
 
== Решаемые задачи ==
Если даны следующие объекты:
 
*<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;Построение математического описания функций.'''
В этом разделе приведено краткое описание некоторых языков функционального программирования (очень немногих). Дополнительную информацию можно почерпнуть, просмотрев ресурсы, перечисленные в следующем разделе.
 
#'''[[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/Служебная:Сравнение_версий/26206