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

Размещено на http://www.allbest.ru/

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

Факультет радиофизики и электроники

Кафедра информатики и компьютерных систем

Дипломная работа по теме:

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

Минск

2014



ВВЕДЕНИЕ

В настоящее время разработка и использование сложных программных систем невозможно без учета существующей тенденции увеличения ядер в процессорах. Вследствие этого возникает необходимость в инструментах для параллельного программирования, которые бы обеспечили быструю и качественную разработку программного обеспечения. Повсеместно использующийся объектно-ориентированный подход затрудняет написание параллельных программ, поэтому в последнее время растет интерес к парадигме функционального программирования и оно начинает интенсивнее использоваться в индустрии разработки программного обеспечения. В частности корпорация Microsoft включила в состав своей последний среды разработки Visual Studio 2010 функциональный язык F#, много функциональных возможностей добавилось в язык C#, включая функциональное ядро LINQ.

Целями данной работы являются:

Определение эффективности главной концепции мультипарадигменного языка F# - функционального программирования.

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

Для реализации целей была поставлена задача по сравнению эффективности программирования на различных .NET языках (С++, С#, F#) на примере оконного приложения, реализующего графическую обработку изображения недетерминированного фрактала - множества Мандельброта. Построение данного множества является стандартной задачей для анализа параллельных возможностей языка. В качестве критерия эффективности будет выступать скорость работы программ, в качестве дополнительных критериев - удобство написания и повторного использования кода, его безопасность.



1. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ F#

1.1 Анализ существующих функциональных языков

язык программирование функция матрица

История

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

Истоки математических основ функционального подхода к программированию следует искать в ранних работах М. Шенфинкеля (Moses Schцnfinkel), которые, нужно отметить, малоизвестны, т.к. довольно далеки по времени от работ, непосредственно связанных с функциональным подходом. Еще в 1924 году он разработал простую (simple) теорию функций, которая фактически являлась исчислением объектов-функций и предвосхитила появление лямбда-исчисления.

Затем, в 1934 году, А. Черч (Alonso Church) предложил лямбда-исчисление и применил его для исследования теории множеств. Не вызывает сомнений тот факт, что разработанная им теория конечных последовательностей в форме исчисления лямбда-конверсий положила начало математическому исчислению, формализующему понятие функции. Вклад ученого был настолько фундаментальным, что теория до сих пор называется лямбда-исчислением и часто именуется в литературе лямбда-исчислением Черча.

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

Теорию и практику программирования существенно обогатило моделирование среды вычислений в форме абстрактной машины, построенной на основе категориальной комбинаторной логики, созданной Х. Карри (Haskell B. Curry). В 1940 году он предложил теорию функций без переменных (иначе называемых комбинаторами), известную в настоящее время как комбинаторная логика. Эта теория является развитием лямбда-исчисления и представляет собой формальный язык, аналогичный языку функционального программирования и позволяющий более наглядно моделировать вычисления в среде абстрактных машин, в значительной мере схожих с виртуальной машиной .NET.

В 50-х годах XX столетия появилась первая реализация функционального языка программирования в виде языка LISP. Он был предложен Джоном Мак-Карти (John McCarthy) в качестве средства исследования границ применимости компьютеров, в частности, методом решения задач искусственного интеллекта. Лисп послужил эффективным инструментом экспериментальной поддержки теории программирования и развития сферы его применения.

Позднее, уже в 60-х г.г. Р. Хиндли (Roger Hindley) разработал выводимость типов (type inference), т.е. возможность неявно определить тип выражения, исходя из типов выражений, которые его окружают. Именно эта возможность широко используется в современных языках программирования, таких как SML и Haskell.

Также в 60-х г.г. П. Лендин (Peter Landin) создал первую абстрактную машину на основе расширенного лямбда-исчисления. Машина получила название SECD и формализовала вычисления на языке программирования ISWIM (If you See What I Mean), который впоследствии стал прообразом языка функционального программирования ML.

Наконец, в 70-х г.г. Р. Милнер (Robin Milner) создал полиморфную систему типизации для языка функционального программирования ML, которая вместе с развернутым описанием того же автора положила начало стандартизации этого языка программирования. В 1971 г теория решеток Д. Скотта (Dana S. Scott) стала основой для моделирования вычисления значения функции (или семантики) языка программирования [1].

Функциональный подход породил целое семейство языков, родоначальником которых, как уже отмечалось, стал язык программирования LISP. Позднее, в 70-х годах, был разработан первоначальный вариант языка ML, который впоследствии развился, в SML, а также ряд других языков, из которых, пожалуй, самым «молодым» является созданный совсем недавно - в 2006 году мультипарадигменный язык Nemerle.

Рассмотрим эволюцию языков программирования, развивающихся в рамках функционального подхода, в частности семейства Lisp, ML, Haskell.

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

Семейство Lisp

Ранние языки функционального программирования, которые берут свое начало от классического языка LISP (LISt Processing; современное написание: Lisp). Традиционный Лисп имеет динамическую систему типов. Язык является функциональным, но многие поздние версии обладают также чертами императивности, к тому же, имея полноценные средства символьной обработки становится возможным реализовать объектно-ориентированность, примером такой реализации является платформа CLOS.

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

Одной из необычных особенностей семейства языков Лисп является возможность использования макросов для создания встроенного предметно-ориентированного языка программирования. Обычно, в большом количестве проектов, написанных на языке Лисп, модуль может быть написан на множестве подобных миниязыков, то есть, один может использовать SQL-диалект языка Лисп, а другой может быть написан на диалекте, ориентированном на графический интерфейс пользователя или вывод на принтер и т. д. [3].

Первые области применения языка Лисп были связаны с символьной обработкой данных и процессами принятия решений. Наиболее популярный сегодня диалект Common Lisp является универсальным языком программирования. Он широко используется в самых разных проектах: Интернет-серверы и службы, серверы приложений и клиенты, взаимодействующие с реляционными и объектными базами данных, научные расчёты и игровые программы.

Одно из направлений использования языка Lisp -- его использование в качестве скриптового языка, автоматизирующего работу в ряде прикладных программ:

Lisp используется как язык сценариев в САПР AutoCAD (диалект AutoLISP);

его диалект -- SKILL -- используется для написания скриптов в САПР Virtuoso Platform компании Cadence Design Systems;

Lisp является одним из базовых средств текстового редактора Emacs (диалект EmacsLISP);

Lisp используется как язык сценариев в издательском программном обеспечении Interleaf/Quicksilver (диалект Interleaf Lisp);

в оконном менеджере Sawfish применяется специальный диалект Лиспа Rep, который в значительной степени повторяет диалект Лиспа от Emacs;

диалект Scheme используется в качестве одного из скриптовых языков в графическом процессоре Gimp;

диалект GOAL используется для высокодинамичных трёхмерных игр;

Lisp может использоваться для написания скриптов в аудиоредакторе Audacity [4].

Семейство ML

ML (Meta Language) -- семейство строгих языков функционального программирования с развитой полиморфной системой типов и параметризуемыми модулями. Подобная система типов была раньше предложена Роджером Хиндли в 1969 году и сейчас часто называется системой Хиндли-Милнера. Не является чистым функциональным языком, так как он включает и императивные инструкции.

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

Можно выделить особенности ML:

ML является интерактивным языком. Каждое введенное предложение анализируется, компилируется и исполняется, и значение, полученное в результате исполнения предложения, вместе с его типом выдается пользователю

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

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

ML содержит надежно типизированный механизм обработки исключительных событий

ML содержит средства разбиения программ на модули, обеспечивающие возможность разработки больших программ по частям [5].

В середине 80-х годов ML распался на два диалекта, которые в данный момент обычно рассматривают как различнные языки: Objective CaML и Standard ML.

Язык CaML поддерживает функциональную, императивную и объектно-ориентированную парадигмы программирования. Был разработан в 1985 году во французском институте INRIA, который занимается исследованиями в области информатики. Самый распространённый в практической работе диалект языка ML. Его реализация содержит много возможностей, не имеющих прямого отношения к функциональному подходу, но необходимых для практического языка программирования:

Компилятор в байт-код (генерирует компактный и достаточно эффективный код)

Компилятор в машинный код для многих платформ (в том числе x86, SPARC, Alpha etc.). Порождаемый транслятором код обладает эффективностью сравнимой с С ( различие в скорости как правило от двукратного проигрыша до 3-кратного выигрыша - последнее имеет место за счет более эффективной работы с кучей).

Как нативный (native), так и байт-код порождаются в виде исполняемого файла.

Текстовый отладчик (с функциональностью близкой к GNU Debugger)

Генераторы лексических и синтаксических анализаторов (OCamlLex, OCamlYacc) [6].

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

Standard ML -- модульный функциональный язык программирования общего назначения.

По сравнению с ранними функциональными языками, SML обладает рядом несомненных достоинств. К ним, в первую очередь, относятся:

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

статическая типизация: все ошибки несоответствия типов выявляются уже на стадии контроля соответствия типов в ходе трансляции (а не во время выполнения программы, как в LISP и Scheme);

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

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

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

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

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

Из последних реализаций нужно отметить мультипарадигменный язык Nemerle, который в функциональном подходе будет родственен языкам семейства ML, включая их особенности:

функции высшего порядка;

сопоставление с образцом (pattern matching);

алгебраические типы;

локальные функции;

кортежи и анонимные типы;

частичное применение;

мощный вывод типов;

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

Основные концепции языка Nemerle:

Типобезопасные «гигиеничные» макросы и квазицитирование c возможностью расширения синтаксиса.

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

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

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

Отсутствие четкой границы между инструкцией (statement) и выражением (expression). «Everything is expression». Например, условный оператор может находиться внутри арифметического выражения. Нет необходимости в инструкциях return, break, continue.

Алгебраические типы данных, кортежи и сопоставление с образцом.

Упрощенный синтаксис работы со списками. Списочные литералы.

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

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

Hope, Miranda, Haskell

Язык Hope появился в 70х годах в Эдинбургском Университете. Hope является первым языком, в котором появились отложенные вычисления и алгебраические типы, но в нем отсутствует возможность неявного объявления типов. В последующих версиях языка добавилась поддержка отложенных вычислений[7]. Язык является важным этапом в жизни функционального программирования, он послужил основой для таких языков как Miranda и Haskell, но сам распространения не получил.

Язык Miranda был разработан в 1985 году, он стал первым коммерчески поддерживаемым чисто функциональным языком программирования. Его чистая функциональность обеспечивает отсутствие побочных эффектов, так как в языке нет состояния, нет переменных. Выделим также другие особенности языка:

Miranda поддерживает функции в качестве данных.

Miranda является «ленивым» (нестрогим) языком, поддерживаются нестрогие функции и бесконечные размерности.

Реализованы генераторы списков (list comprehensions), т.е. создание списков при помощи математических выражений.

В основе языка лежит полиморфная строгая типизация.

Абстрактные типы данных и модули.

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

Так как при синтаксическом анализе программы используется интеллектуальный разбор, редко появляется необходимость использовать скобки или другие ограничители при ее написании. Также в Miranda не нужно описывать типы при объявлении переменных так как в языке присутствует система вывода типов. В языке существует лишь несколько встроенных типов:

числа (целые неограниченной размерности и числа с плавающей точкой двойной точности)

символы

списки

кортежи

функции[8]

Miranda была относительно популярна в 1980-х годах, но оставалась проприетарным программным обеспечением. Это затрудняло развитие и исследования возможностей ленивого функционального программирования, поэтому буквально за пару лет появилось более десятка схожих языков. Чтобы объединить усилия разных разработчиков, в 1987 г. на конференции по функциональным языкам программирования и компьютерной архитектуре в Орегоне (FPCA'87) было решено создать комитет для разработки открытого стандарта.

В 1990 г. была предложена первая версия языка Haskell 1.0. В дальнейшем работа комитета продолжилась, и в 1999 г. был опубликован «The Haskell 98 Report», который стал стабильным стандартом языка на много лет. Язык, однако, продолжал бурно развиваться, компилятор GHC (Glasgow Haskell Compiler) был фактическим стандартом в отношении новых возможностей. Последняя версия языка -- Haskell 2010 -- была объявлена в конце 2009 г, но последней «значительной» версией (стандартом) остаётся Haskell 98 [9].

Haskell является чисто функциональным языком программирования общего назначения, который включает много последних инноваций в разработке языков программирования. Haskell обеспечивает функции высокого порядка, нестрогую семантику, статическую полиморфную типизацию, определяемые пользователем алгебраические типы данных, сопоставление с образцом, описание списков, модульную систему, монадическую систему ввода - вывода и богатый набор примитивных типов данных, включая списки, массивы, целые числа произвольной и фиксированной точности и числа с плавающей точкой. Haskell является и кульминацией, и кристаллизацией многих лет исследования нестрогих функциональных языков [10].

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

возможность использования лямбда-абстракции;

функции высшего порядка;

частичное применение;

недопустимость побочных эффектов (чистота языка);

ленивые вычисления (lazy evaluation);

сопоставление с образцом, функциональные образцы (pattern matching);

параметрический полиморфизм (в т.ч. абстрагирование от конструктора типа) и полиморфизм классов типов;

статическая типизация;

автоматическое выведение типов (основано на модели типизации Хиндли -- Милнера);

алгебраические типы данных;

параметризуемые типы данных;

рекурсивные типы данных;

абстрактные типы данных (инкапсуляция);

генераторы списков (list comprehensions);

охраняющие выражения (guards) -- выражения, которые предназначены для ограничения вычислительных процессов и направления их по определённому направлению в зависимости от условия охраны[11];

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

возможность интеграции с программами, реализованными на императивных языках программирования посредством открытых интерфейсов (стандартное расширение языка Foreign Function Interface);

Среди возможностей компилятора GHC нужно отметить три варианта компиляции: непосредственно в машинные коды целевой архитектуры, компиляция через промежуточный код на языке C или C--, компиляция в язык LLVM (Low Level Virtual Machine).

Со времени принятия последнего стандарта языка (Haskell98) прошло много времени, и с тех пор ведущие реализации языка (ghc и hugs) были расширены множеством дополнительных возможностей:

Полиморфизм 2-го и высших рангов (rank-2 and rank-N polymorphism)

Функциональные зависимости (FD, functional dependencies)

В 2009 году сформировалась концепция Haskell Platform -- стандартного дистрибутива языка, включающего кроме компилятора (GHC), также дополнительный инструментарий (систему сборки и развёртывания пакетов Cabal) и набор популярных библиотек. Сейчас Haskell Platform -- это рекомендованный базовый дистрибутив для разработчиков. Готовые сборки Haskell Platform доступны для Windows, MacOS X и ряда дистрибутивов Linux.

Развитием ранних языков программирования стали языки функционального программирования с сильной типизацией, характерным примером которых является классический ML, и далее, его прямой потомок, SML. В языках с сильной типизацией каждая конструкция (или выражение) должно иметь тип. При этом в более поздних языках функционального программирования, однако, нет необходимости явного приписывания типа, и типы изначально неопределенных выражений могут выводиться (до запуска программы), исходя из типов связанных с ними выражений.

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

На современном этапе развития возникли языки функционального программирования «нового поколения» со следующими расширенными возможностями: сопоставление с образцом (Scheme, F#, Nemerle), параметрический полиморфизм (SML) и так называемые «ленивые» (по мере необходимости) вычисления (Haskell, Miranda, F#,)[12].

1.3 Преимущества функционального программирования

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

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

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

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

Благодаря реализации механизма сопоставления с образцом, такие языки функционального программирования как ML и Haskell весьма хорошо применимы для символьной обработки.

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

простота тестирования и верификации программного кода на основе возможности построения строгого математического доказательства корректности программ;

унификация представления программы и данных (данные могут быть инкапсулированы в программу как аргументы функций, означивание или вычисление значения функции может производиться по мере необходимости);

безопасная типизация: недопустимые операции над данными исключены;

динамическая типизация: возможно обнаружение ошибок типизации во время выполнения;

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

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

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

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

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

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

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

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

Часто к ним относят нелинейную структуру программы и относительно невысокую эффективность реализации. Второй недостаток постепенно исправляется с новыми версиями компиляторов. Тем не менее, программирование с использованием математического понятия функции вызывает некоторые трудности, поэтому функциональные языки, в той или иной степени предоставляют и императивные возможности [2].

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

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

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

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

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

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

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

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



1.4 Язык F#: особенности, преимущества, недостатки, области применения

Функциональный язык F# был разработан в 2002 г. Доном Саймом (Don Syme) в Microsoft Research в Кембридже. В настоящее время его разработку ведет Microsoft Developer Division, и распространяется вместе с .NET Framework и Visual Studio как часть Visual Studio 2010.

F# входит в семейство ML-языков, унаследовав все преимущества этого семейства, а также поддерживает большинство функциональных возможностей нестрогих языков (например Haskell), таких как отложенные вычисления, бесконечные последовательности, монады. Одной из важных особенностей языка является поддержка Microsoft, что служит хорошим подспорьем для его развития и расширения сферы применения. Перечислим важнейшие характеристики этого языка:

F# -- мультипарадигменный язык программирования. Акцент сделан на функциональности, но на нем можно писать функциональный, императивный и объектно-ориентированный код. Это предоставляет программисту возможность ухода от табий ООП и более гибко рассматривать проблему.

F# использует вывод типов, что приводит к более лаконичным программам.

F# -- это .NET-язык программирования.

F# -- компилируемый язык программирования, при этом в качестве промежуточного языка используется язык Common Intermediate Language (CIL), так же как и в программах, написанных на языках C# или VB.NET.

F# включен в стандартный набор Visual Studio 2010

У него есть интерактивная среда программирования (REPL) как для Ruby и Python, называемая F# Interactive Window.

Рассмотрим технические особенности F#, которые делают его особенно привлекательным для написания программ:

Статически типизированный. F# является статически типизированным языком, в отличие, например, от динамически типизированного Ruby. Это означает, что информация о типах известна во время компиляции. Благодаря этому код исполняется намного быстрее и есть возможность узнавать о большинстве ошибок еще на этапе компиляции.

Лаконичный. В дополнение к выведению типов, F# также использует значимые пробелы. Если сместить строки под if-конструкцией на несколько пробелов вправо, компилятор расценит их как тело оператора (light синтаксис). Это избавляет от необходимости засорять код фигурными скобками и сохраняет вертикальное пространство. Меньше кода на странице означает возможность одновременно видеть большую часть программы, и меньше переключать контекст просматривая код.

Расширяемый. Это означает возможность использования F# в крупных проектах уровня предприятий

Исследуемый. В F# вам нет необходимости обращаться к дизайну, чтобы понять, как все работает. Можно быстро прототипировать решения F#, а также экспериментировать с алгоритмами и подходами с помощью F# Interactive Window. Опираясь на лаконичную природу F#, не нужно писать много кода, чтобы экспериментировать с программами.

Библиотеки. F# поставляется со своей собственной библиотекой для написания функционального или другого кода[16]. Платформа .NET позволяет использовать множество уже существующих библиотек.

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

Microsoft интегрировала среду разработки F# в Visual Studio 2010 и планирует активно внедрять данный язык в разработку программных систем, которые сами с течением времени смогут масштабироваться, например в зависимости от количества пользователей, данное достоинство нельзя просто реализовать в императивных языках программирования.

Области применения F#:

Симуляция.

Вычислительные финансы.

Обработка крупномасштабных данных.

Языково-ориентированное программирование.

Написание анализаторов кода.

Расширяемый F# код.

Многопоточное программирование.

Параллельное программирование.

Асинхронное программирование.

Примером использования F# является коммерческий продукт WebSharper фирмы IntelliFactory. Это платформа для создания клиентских web-приложений. Она позволяет писать клиентский код на F#, который затем будет оттранслирован на JavaScript. Такая трансляция распространяется на достаточное большое подмножество F#, включая функциональное ядро языка, алгебраические типы данных, классы, объекты, исключения и делегаты. Также поддерживается значительная часть стандартной библиотеки F#, включая работу с последовательностями (sequences), событиями и асинхронными вычислительными выражениями (async workflows). Всё может быть автоматически оттранслировано на целевой язык JavaScript. Кроме того, поддерживается некоторая часть стандартных классов самого .NET, и объём поддержки будет расти [17].



2. ПРОГРАММИРОВАНИЕ ДЛЯ МНОГОЯДЕРНЫХ ПРОЦЕССОРОВ

2.1 Параллельное программирование для многоядерных процессоров

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

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

В 2001 году был исчерпан ресурс повышения тактовой частоты процессора. Для рядового пользователя это прошло незамеченным, поскольку организация массового производства процессоров с тактовой частотой более 3 ГГц растянулась на несколько лет. К 2005 году был освоен серийный выпуск 3-гигагерцевых процессоров, и оказались в основном исчерпанными ресурсы архитектурного совершенствования отдельно взятого процессора. В апреле 2005 года Intel и AMD одновременно приступили к продаже двухъядерных процессоров для персональных компьютеров -- по сути, двух процессоров на одной подложке. Теперь забота о повышении скорости исполнения программ полностью ложится на плечи кодировщиков.

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

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

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

Идея распараллеливания по данным еще проще. Если имеется каждому из N процессоров предоставить равную часть данных для обработки, то производительность увеличится в N раз. Если в задаче нельзя выделить участки, допускающие параллельную обработку, или массив однотипных операндов для конвейеризации, то сократить время ее выполнения не удастся. Это описывается законом Амдала, который определяет максимально достижимую производительность.

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

специализация (применение внутри процессоров блоков, оптимизированных под определенный вид вычислений, например математических сопроцессоров);

кэширование;

спекулятивные вычисления.

Серийно изготавливаемые компьютеры позволяют создать дешевую альтернативу суперкомпьютерам, например кластерную систему. При этом основная задача сводится к программированию созданной системы.

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

Алгоритм должен допускать распараллеливание.

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

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

Физическому параллелизму присуща зависимость глобальной структуры алгоритма от топологии вычислительной платформы. Процесс создания максимально эффективного алгоритма практически не автоматизируется и связан с большими трудозатратами на поиск специфической структуры алгоритма, оптимальной для конкретной топологии целевой системы. Найденная структура обеспечит минимальное время получения результата, но, скорее всего, будет неэффективна для другой конфигурации. Более суровое следствие зависимости структуры алгоритма от вычислительной платформы -- тотальная непереносимость не только исполняемых кодов, но и самого исходного текста.

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

взаимные блокировки параллельных участков;

несинхронный доступ, или гонки;

возможность зависания параллельных участков;

опасность использования сторонних процедур и библиотек;

набор специализированных средств отладки физически параллельных программ;

нелокальный характер ошибок;

динамический характер ошибок и, как следствие, влияние средств отладки программ на корректность исполнения последних.

Если параллельные (а вернее, независимые) сущности выделяются на основе соображений удобства программирования (в первую очередь, для снижения сложности описания системы), то говорят о логическом параллелизме.

Логический параллелизм на уровне операционных систем является многозадачным; при этом имеется выделенная задача (планировщик), которая занимается переключением процессора с одной задачи на другую. Алгоритмы переключений могут быть как примитивными, так и весьма сложными. Самый простой -- алгоритм разделения по времени. Планировщик работает с очередью задач и активизируется по прерываниям от таймера с некоторым заданным периодом. После активизации он сохраняет контекст текущей задачи, ставит ее в конец очереди, восстанавливает контекст следующей задачи из очереди и запускает ее на исполнение.

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

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

«Мелкозернистый» логический параллелизм эффективен в задачах управления сложным промышленным оборудованием. Необходимость отражения параллелизма процессов, осуществляемых на объекте управления, требует создания по меньшей мере сотни параллельно исполняемых процессов. Сжатие информации достигается при логическом параллелизме за счет упрощенного описания комбинаций независимых случаев: описание алгоритма как набора независимых частей -- это описание суммы ситуаций, а монолитное описание -- это описание произведения ситуаций.

Преимущества «мелкозернистого» логического параллелизма заставляют искать пути снижения накладных расходов, присущих многозадачности. Известные решения для операционных систем -- легковесные процессы (light-weight process). Переключение процессора на поток минимизировано вплоть до операций сохранения/восстановления этих указателей. Планировщик по-прежнему присутствует и активизируется по прерываниям от таймера.

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

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

К моменту появления многоядерных процессоров уже существовали такие технологии как OpenMP (Open Multi-Processing) и MPI(Message Passing Interface) для многопроцессорных систем. Обе они могут применяться для написания программ для многоядерных процессоров. Сравним эти технологии.

Достоинства OpenMP:

На OpenMP программы легче писать и отлаживать чем на MPI

Поэтапное распараллеливание - директивы могут постепенно добавляться в программу

Программы могут выполняться также последовательно

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

Программы просты для понимания, облегчена их поддержка

Недостатки OpenMP:

Программы могут быть исполнены лишь на многопроцессорных или многоядерных системах с общей памятью.

Необходим компилятор поддерживающий openMP.

В основном можно использовать только для распараллеливания циклов.

Достоинства MPI:

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

Каждый процесс имеет свои локальные переменные.

Покрывает больший спектр задач чем openMP.

Недостатки MPI:

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

Трудно отлаживать.

Производительность ограничена связями между вычислительными узлами [19].

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

Разработки компании Microsoft избавляют программиста от необходимости управления потоками и взаимоблокировками на низком уровне. Visual Studio 2010 и .NET Framework 4 улучают поддержку параллельного программирования, путем предоставления новой среды выполнения, новых типов библиотек класса и новых средств диагностики. Эти функциональные возможности упрощают параллельную разработку, что позволяет разработчикам писать эффективный, детализированный и масштабируемый параллельный код с помощью естественных выразительных средств без необходимости непосредственной работы с потоками или пулом потоков [20].

Параллельная модель программирования в .NET 4.0 включает две возможности:

TPL(Task Parallel Library) - улучшенное средство для работы с потоками - программист работает не с потоками а с задачами. Содержит два главных класса: Task и Parallel. Класс Parallel в частности библиотека содержит параллельные реализация таких конструкций как For, Foreach, Invoke.

PLINQ(Parallel Language-Integrated Query) - известная библиотеки LINQ с возможностью параллельного исполнения запросов [21].

Язык F# может использовать эти возможности .NET для написания параллельных программ, но в его активе имеются и свои инструменты для этих целей.

Асинхронные потоки операций - один из самых интересных примеров практического использования вычислительных выражений. Код, выполняющий какие либо неблокирующие операции ввода-вывода, как правило сложен для понимания, поскольку представляет из себя множество callback-методов, каждый из которых обрабатывает какой-то промежуточный результат и возможно начинает новую асинхронную операцию. Асинхронные потоки операций позволяют писать асинхронный код последовательно, не определяя callback-методы явно. Для создания асинхронного потока операций используется блок async: