МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Факультет радиофизики и электроники
Кафедра
информатики и компьютерных систем
Дипломная работа по теме:
Анализ
эффективности функционального программирования на языке F# для многоядерных
процессоров
Минск
ВВЕДЕНИЕ
В настоящее время разработка и использование сложных программных систем невозможно без учета существующей тенденции увеличения ядер в процессорах. Вследствие этого возникает необходимость в инструментах для параллельного программирования, которые бы обеспечили быструю и качественную разработку программного обеспечения. Повсеместно использующийся объектно-ориентированный подход затрудняет написание параллельных программ, поэтому в последнее время растет интерес к парадигме функционального программирования и оно начинает интенсивнее использоваться в индустрии разработки программного обеспечения. В частности корпорация Microsoft включила в состав своей последний среды разработки Visual Studio 2010 функциональный язык F#, много функциональных возможностей добавилось в язык C#, включая функциональное ядро LINQ.
Целями данной работы являются:
Определение эффективности главной концепции мультипарадигменного языка F# - функционального программирования.
Исследование эффективности параллельного программирования на функциональном языке F#.
Для реализации целей была поставлена задача по
сравнению эффективности программирования на различных .NET языках (С++, С#, F#)
на примере оконного приложения, реализующего графическую обработку изображения
недетерминированного фрактала - множества Мандельброта. Построение данного
множества является стандартной задачей для анализа параллельных возможностей
языка. В качестве критерия эффективности будет выступать скорость работы
программ, в качестве дополнительных критериев - удобство написания и повторного
использования кода, его безопасность.
1. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ F#
.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 - его использование в качестве скриптового языка, автоматизирующего работу в ряде прикладных программ:используется как язык сценариев в САПР AutoCAD (диалект AutoLISP);
его диалект - SKILL - используется для написания скриптов в САПР Virtuoso Platform компании Cadence Design Systems;является одним из базовых средств текстового редактора Emacs (диалект EmacsLISP);используется как язык сценариев в издательском программном обеспечении Interleaf/Quicksilver (диалект Interleaf Lisp);
в оконном менеджере Sawfish применяется специальный диалект Лиспа Rep, который в значительной степени повторяет диалект Лиспа от Emacs;
диалект Scheme используется в качестве одного из скриптовых языков в графическом процессоре Gimp;
диалект GOAL используется для высокодинамичных трёхмерных игр;может использоваться для написания скриптов в аудиоредакторе Audacity [4].
Семейство ML(Meta Language) - семейство строгих языков функционального программирования с развитой полиморфной системой типов и параметризуемыми модулями. Подобная система типов была раньше предложена Роджером Хиндли в 1969 году и сейчас часто называется системой Хиндли-Милнера. Не является чистым функциональным языком, так как он включает и императивные инструкции.
В основе строгой и статической системы типов языка лежит лямбда-исчисление, к которому добавлена строгая типизация. Строгая система типов делает возможности для оптимизации, поэтому вскоре появляется компилятор языка. В системе типов Хиндли-Милнера ограниченно полиморфная система типов, где большинство типов выражений может быть выведено автоматически. Это дает возможность программисту не описывать явно типы функций, но сохранить строгий контроль типов.
Можно выделить особенности ML:является интерактивным языком. Каждое введенное предложение анализируется, компилируется и исполняется, и значение, полученное в результате исполнения предложения, вместе с его типом выдается пользователюимеет полиморфную систему типов. Каждое допустимое предложение языка обладает однозначно определяемой наиболее общей типизацией, которая определяет контексты, в которых предложение может быть использовано.поддерживает абстрактные типы данных. Абстрактные типы весьма полезный механизм в модульном программировании. Новые типы данных могут быть определены вместе с набором операций над значениями этих типов в ML области действия идентификаторов определяются статически. Смысл всех идентификаторов в программе определяется статически, что позволяет создавать более модульные и более эффективные программысодержит надежно типизированный механизм обработки исключительных событийсодержит средства разбиения программ на модули, обеспечивающие возможность разработки больших программ по частям [5].
В середине 80-х годов ML распался на два диалекта, которые в данный момент обычно рассматривают как различнные языки: Objective CaML и Standard ML.
Язык CaML поддерживает функциональную, императивную и объектно-ориентированную парадигмы программирования. Был разработан в 1985 году во французском институте INRIA, который занимается исследованиями в области информатики. Самый распространённый в практической работе диалект языка ML. Его реализация содержит много возможностей, не имеющих прямого отношения к функциональному подходу, но необходимых для практического языка программирования:
Компилятор в байт-код (генерирует компактный и достаточно эффективный код)
Компилятор в машинный код для многих платформ (в том числе x86, SPARC, Alpha etc.). Порождаемый транслятором код обладает эффективностью сравнимой с С ( различие в скорости как правило от двукратного проигрыша до 3-кратного выигрыша - последнее имеет место за счет более эффективной работы с кучей).
Как нативный (native), так и байт-код порождаются в виде исполняемого файла.
Текстовый отладчик (с функциональностью близкой к GNU Debugger)
Генераторы лексических и синтаксических анализаторов (OCamlLex, OCamlYacc) [6].
К достоинствам языка относят строгую типизацию, развитую систему модулей, автоматическую сборку мусора, эффективность, кроссплатформенность.ML - модульный функциональный язык программирования общего назначения.
По сравнению с ранними функциональными языками, SML обладает рядом несомненных достоинств. К ним, в первую очередь, относятся:
безопасность программного кода, т.е. гарантия отсутствия переполнения памяти (в случае корректно написанной программы) и, соответственно, защиты от потенциальной неустойчивости работы системы посредством искусственного создания этого переполнения;
статическая типизация: все ошибки несоответствия типов выявляются уже на стадии контроля соответствия типов в ходе трансляции (а не во время выполнения программы, как в LISP и Scheme);
выводимость типов (нет необходимости явно указывать тип каждого выражения, при этом результирующий программный код становится более удобочитаемым, его легче хранить и повторно использовать).
К числу других преимуществ языка функционального программирования SML следует отнести параметрический полиморфизм (возможность обрабатывать аргументы абстрактного типа). При этом трудозатраты на разработку программного обеспечения сокращаются за счет универсальности разрабатываемых функций (скажем, становится возможным написать унифицированную функцию для упорядочения по возрастанию элементов списка, которая сможет упорядочивать и список из целочисленных элементов, и список из символьных строк).
Еще одним мощным средством, облегчающих символьную обработку (в частности, декомпозицию и верификацию программ), является механизм сопоставления с образцом.
Построение программ из модулей способствует разделению интерфейсной части (описательной части) и реализации (содержательной части) функций, что обеспечивает унификацию и сокращает время создания сложных программных проектов, облегчая тестирование на соответствие спецификациям заказчика.
Обработка исключительных ситуаций, которые описывают ход выполнения программы в случае возникновения тех или иных относительно редких событий, а также теоретически интересного механизма продолжений, создают возможность реализации программных систем, взаимодействующих с пользователем в реальном времени.
Из последних реализаций нужно отметить мультипарадигменный язык Nemerle, который в функциональном подходе будет родственен языкам семейства ML, включая их особенности:
функции высшего порядка;
сопоставление с образцом (pattern matching);
алгебраические типы;
локальные функции;
кортежи и анонимные типы;
частичное применение;
мощный вывод типов;
Вдобавок к императивным и функциональным парадигмам, Nemerle обладает мощной системой макросов, которые предоставляют пользователю возможность добавлять новые конструкции в язык и описывать решение задач в декларативном стиле с помощью создания собственных предметно-ориентированных языков программирования (DSL).
Основные концепции языка Nemerle:
Типобезопасные «гигиеничные» макросы и квазицитирование c возможностью расширения синтаксиса.
Наличие локальных функций (лексических замыканий). Функция является полноправным объектом, то есть может быть сохранена в переменной, передана в качестве аргумента в другую функцию или возвращена из функции.