Реферат: "Функциональное программирование"

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ М. Е. ЕВСЕВЬЕВА»

Физико–математический факультет

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

РЕФЕРАТ

ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

Автор работы________________________________________ С. А. Кошелева

Направления подготовки 44.03.05 Педагогическое образование

Профиль Информатика. Математика

Руководитель работы: канд. физико – матем. наук, доцент___________________________________________ Т. В. Кормилицына

Оценка __________

Саранск 2021

Содержание

Введение 3

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

2. Особенности функционального программирования 6

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

4. Обзор языков функционального программирования 18

Заключение 20

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

Введение

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

Лоренс Паулсон

Язык программирования – формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет наборлексических, синтаксических и семантических правил, определяющих внешний вид программы и действия, которые выполнит исполнитель (обычно – ЭВМ) под её управлением.

Языки программирования классифицируются следующим образом:

1. императивные – программа представляет собой явное описание последовательности манипуляций над данными в памяти компьютера;

2. декларативные – программа содержит описание цели и средств её достижения. Они в свою очередь делятся на:

* функциональные – программа содержит описание функций, вызывающих друг друга;

* логические – программа состоит из описания фактов, правил и цели.

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

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

Как известно, теоретические основы императивного программирования были заложены ещё в 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). Что показательно, практически каждый компилятор с функционального языка реализован на этом же самом языке.

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

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

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

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

4. Функциональное программирование есть программирование, управляемое данными. В строго функциональном языке однажды созданные (введенные) данные не могут быть изменены .

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

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

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

Требования к строго функциональному языку:

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

2. Отсутствует оператор присваивания.

3. Переменная обозначает только имя структуры.

4. В языке присутствуют функционалы.

Простой пример функционального языка – это Excel. В нём каждую формулу в ячейках можно считать функцией, которая зависит от значений в других ячейках. Пользователь явно не задаёт последовательность вычисления, Excel выполняет это самостоятельно. Из-за отсутствия последовательности действий, многие типичные для императивного языка операции заменяются на функциональные аналоги. Например, вместо цикла приходится использовать рекурсию (определение функции через саму себя, как в примере с числами Фибоначчи). Это непривычно для человека, привыкшего программировать в императивном стиле, и отчасти мешает широкому распространению функциональных языков. Функциональные языки получили в последнее время достаточно широкое распространение, так как во многих случаях позволяют более лаконично представить решение задачи. Примеры функциональных языков: Lisp, Haskell, F#, OCaml и т.д.

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

1. Повышение надёжности кода.

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

2. Удобство организации модульного тестирования.

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

3. Возможности оптимизации при компиляции.

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

4. Возможности параллелизма.

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

Недостатки функционального программирования:

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

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

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

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

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

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

• Модульность;

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

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

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

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

Программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных языках. Сравним программы на 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]

while (x

if (i

{

int temp = a[i];

a[i++] = a[j];

a[j––] = temp;

}

}

while (i

if (l

if (i

}

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

quickSort ([]) = []

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

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

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

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

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

quickSort [] = []

quickSort (h : t) = quickSort [y | 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 (x₁, x₂, ..., x_n) — некоторая процедура.

x₁ = a₁, x₂ = a₂ — известные значения параметров.

x₃, ..., x_n — неизвестные значения параметров.

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

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

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

f : Dx₁, ..., Dx_n – Dy₁, ..., Dy_m.

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

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

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

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

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

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

1. Обзор языков функционального программирования

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

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

ISWIM. Функциональный язык-прототип. Разработан Ландиным в 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.

Заключение

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

Теоретические основы функционального программирования были заложены ещё в 20–х годах XX столетия после разработки таких мощных вычислительных формализмов, как комбинаторная логика и λ–исчисление. Впоследствии λ–исчисление стало базисом всех разработанных функциональных языков, начиная от первого функционального языка Lisp, заканчивая последней разработкой – языком Haskell–98.

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

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.