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

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

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

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

ОБРАЗОВАНИЯ «МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ

ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ

М. Е. ЕВСЕВЬЕВА»

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

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

Проект на тему:

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

Выполнил: Ашыров Г.

группа МДИ – 118

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

Саранск 2021

Содержание

Введение 3

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

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

3. Краткость и простота 7

4. Строгая типизация 9

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

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

Список использованных источников 17

Введение

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

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

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

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

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

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

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

 

 

 

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. Краткость и простота

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

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-машину.

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

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

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

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

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

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

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

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.

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.