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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 3

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

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

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

1.3 Задачи, решаемые в функциональном программировании 12

2 Язык F#  13

2.1 Состав инсталляционных пакетов F# 14

2.2 Основные возможности языка 15

2.3 Библиотеки F# 17

2.4 Основные понятия языка F# 17

2.4.1 Выражения 17

2.4.2 Типы 18

2.4.3 Декларации 19

2.4.4 Проверка и вывод типов 20

2.4.5 Функции 21

2.4.6 Функциональный тип 21

2.5 Работа в F# 23

2.5.1 Примеры кода 23

2.5.2 Пример – построение множества Мандельброта 26

ЗАКЛЮЧЕНИЕ 31

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 32

 

 

ВВЕДЕНИЕ

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

Выполнение  программы на функциональном языке, говоря неформально, заключается в  вызове функции, аргументами которой  являются значения других функций, которые  в свою очередь также могут  быть суперпозициями в общем случае произвольной глубины. С точки зрения программиста, основная часть программы  состоит из совокупности определений  функций, как правило, рекурсивных. Такая особенность функциональных языков обусловливает ряд достоинств, к основным из которых, относятся  следующие. Прежде всего это присущая определению функций декларативность, позволяющая писать программы в  терминах того, что надо делать, а  не как это делается, Далее, бесспорным преимуществом этих языков, существенно повышающим надежность программировании, является свойство прозрачности по ссылкам — то, что и понимается под функциональностью языка. И наконец, имеющаяся возможность формального преобразования функциональных программ с целью их оптимизации. Все это делает функциональное программирование весьма привлекательным как в теоретическом, так и в практическом аспектах. Говори о существующей практике применения функциональных языков, необходимо в первую очередь указать такую область, как интеллектуальные автоматизированные системы. Здесь функциональные языки прошли наиболее полную апробацию и признаны вполне адекватным инструментом [1] .

 

 

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

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

Теоретические основы императивного программирования были заложены ещё в 30-х годах XX века Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, также родилась в 20-х — 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать Мозеса Шёнфинкеля (Германия и Россия) и Хаскелла Карри (Англия), разработавших комбинаторную логику, а также Алонзо Чёрча (США), создателя λ-исчисления.

Теория так и оставалась теорией, пока в начале 50-х прошлого века Джон Мак-Карти не разработал язык Lisp, который стал первым почти функциональным языком программирования и на протяжении многих лет оставался единственным таковым. Хотя Lisp всё ещё используется (как, например, и FORTRAN), он уже не удовлетворяет некоторым современным запросам, которые заставляют разработчиков программ взваливать как можно большую ношу на компилятор, облегчив тем самым свой непосильный труд. Необходимость в этом, конечно же, возникла из-за всё более возрастающей сложности программного обеспечения [2].

В связи с этим обстоятельством  всё большую роль начинает играть типизация. В конце 70-х — начале 80-х годов XX века интенсивно разрабатываются  модели типизации, подходящие для функциональных языков. Большинство этих моделей  включали в себя поддержку таких  мощных механизмов как абстракция данных и полиморфизм. Появляется множество  типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается  число диалектов.

В первую очередь большинство функциональных языков программирования реализуются  как интерпретаторы, следуя традициям Lisp’а. Интерпретаторы удобны для быстрой  отладки программ, исключая длительную фазу компиляции, тем самым укорачивая обычный цикл разработки. Однако с  другой стороны, интерпретаторы в сравнении  с компиляторами обычно проигрывают  по скорости выполнения в несколько раз. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, Objective Caml) или код на C/C++ (например, Glasgow Haskell Compiler). Что показательно, практически каждый компилятор с функционального языка реализован на этом же самом языке.

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

1. Lisp (List processor). Считается первым функциональным языком программирования. Нетипизирован. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов по значению. Существует объектно-ориентированный диалект языка - CLOS.
2. ISWIM (If you See What I Mean). Функциональный язык-прототип. Разработан Ландиным в 60-х годах для демонстрации того каким может быть язык функционального программирования. Вместе с языком Ландин разработал и специальную виртуальную машину для исполнения программ на ISWIM-е. Эта виртуальная машина, основанная на вызове-по-значению получила название SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.
3. Scheme. Диалект Lisp-а, предназначенный для научных исследований в области компьютерной науки. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем Common Lisp.
4. ML (Meta Language). Семейство строгих языков с развитой полиморфной системой типов и параметризуемыми модулями. ML преподается во многих западных университетах (в некоторых даже как первый язык программирования).
5. Standard ML. Один из первых типизированных языков функционального программирования. Содержит некоторые императивные свойства, такие как ссылки на изменяемые значения и поэтому не является чистым. При вычислениях использует вызов-по-значению. Очень интересная реализация модульности. Мощная полиморфная система типов. Последний стандарт языка - Standard ML-97, существует формальное математическое определения синтаксиса, статической и динамической семантик языка.
6. Caml Light и Objective Caml. Как и Standard ML принадлежит к семейству ML. Objective Caml отличается от Caml Light в основном поддержкой классического объектно-ориентированного программирования. Также как и Standard ML строгий, но имеет некоторую встроенную поддержку отложенных вычислений.
7. Miranda. Разработан Дэвидом Тернером, в качестве стандартного функционального языка, использовавшего отложенные вычисления. Имеет строгую полиморфную систему типов. Как и ML преподавается во многих университетах. Оказал большое влияние на разработчиков языка Haskell.
8. Haskell. Один из самых распространенных нестрогих языков. Имеет очень развитую систему типизации. Несколько хуже (на мой взгляд) разработана система модулей. Последний стандарт языка - Haskell 98.
9. F#. Поддерживает функциональное программирование в дополнение к императивному (процедурному) и объектно-ориентированному программированию. Структура F# во многом схожа со структурой OCaml с той лишь разницей, что F# реализован поверх библиотек и среды исполнения .NET.
10. Gofer (GOod For Equational Reasoning). Упрощенный диалект Haskell. Предназначен для обучения функциональному программированию.
11. Clean. Специально предназначен для параллельного и распределенного программирования. По синтаксису напоминает Haskell. Чистый. Использует отложенные вычисления. С компилятором поставляется набор библиотек (I/O libraries), позволяющие программировать графический пользовательский интерфейс под Win32 или MacOS [3].

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

Рисунок 1 – Хронология возникновения  функциональных языков

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

1. Краткость и простота. Программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных языках.

Для примера ниже приведено сравнение программы на C и на абстрактном функциональном языке на примере сортировки списка быстрым методом Хоара.

Быстрая сортировка Хоара на 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);

        }

    }

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

quickSort ([]) = []

quickSort ([h : t]) = quickSort (n | n ⊆ t, n <= h) + [h] + quickSort (n | n ⊆ t, n > h)

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

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

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

2. Строгая типизация. Практически все современные языки программирования являются строго типизированными языками (возможно, за исключением JavaScript и его диалектов). Строгая типизация обеспечивает безопасность. Программа, прошедшая проверку типов просто не может выпасть в операционную систему с сообщением, подобным "access violation", особенно это касается таких языков, как C/C++ и Object Pascal, где применение указателей является типичным способом использования языка. В функциональных языках большая часть ошибок может быть исправлена на стадии компиляции, поэтому стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерировать более эффективный код и тем самым ускорять выполнение программ.

Рассматривая пример с быстрой  сортировкой Хоара, можно увидеть, что помимо уже упомянутых отличий  между вариантом на языке C и вариантом  на абстрактном функциональном языке, есть ещё одно важное отличие: функция  на C сортирует список значений типа int (целых чисел), а функция на абстрактном  функциональном языке — список значений любого типа, который принадлежит  к классу упорядоченных величин. Поэтому последняя функция может сортировать и список целых чисел, и список чисел с плавающей точкой, и список строк. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать quickSort и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным полиморфизмом, и поддерживается большинством функциональных языков.

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

В языке C++ имеется такое понятие, как шаблон, которое позволяет  программисту определять полиморфные  функции, подобные quickSort. В стандартную  библиотеку C++ STL входит такая функция  и множество других полиморфных  функций. Но шаблоны C++, как и родовые  функции Ada, на самом деле порождают  множество перегруженных функций, которые, кстати, компилятор должен каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция quickSort —  это одна единственная функция.

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

3. Модульность. Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с чётко определёнными связями между ними. Тем самым облегчается процесс проектирования и последующей поддержки больших программных систем. Поддержка модульности не является свойством именно функциональных языков программирования, однако поддерживается большинством таких языков. Существуют очень развитые модульные императивные языки. В качестве примеров подобных языков можно привести Modula-2 и Ada-95.
4. Функции — это значения. В функциональных языках (равно как и вообще в языках программирования и математике) функции могут быть переданы другим функциям в качестве аргумента или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются функциями высших порядков или функционалами. Самый, пожалуй, известный функционал, это функция map. Эта функция применяет некоторую функцию ко всем элементам списка, формируя из результатов заданной функции другой список.
5. Чистота (отсутствие побочных эффектов). В императивных языках функция в процессе своего выполнения может читать и модифицировать значения глобальных переменных и осуществлять операции ввода/вывода. Поэтому, если вызвать одну и ту же функцию дважды с одним и тем же аргументом, может случиться так, что в качестве результата вычислятся два различных значения. Такая функция называется функцией с побочными эффектами.

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

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

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

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

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

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