III Международная студенческая научная конференция Студенческий научный форум - 2011

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

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

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

Синтаксис языка предполагает реализацию программ из небольших блоков - функций, которые могут выполняться в произвольном порядке. Одним из преимуществ реализации программ небольшими блоками можно впоследствии реализовать их работу параллельно. Также код совместим с различными платформами: Windows, Linux, Mac.

Для работы необходимо установить среду разработки. На текущий момент их две - HUGS (интерпретатор) и GHС (содержит интерпретатор и компилятор). GHС является более предпочтительной, т.к. включает в себя большое количество библиотек. GHС доступен по этому адресу для различных платформ:

http://hackage.haskell.org/platform/

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

Сравнение списков с целыми числами:

ghci> [3,2,1] > [2,1,0] True

Сравнение списков символов:

ghci > [´a´,´b´,´c´] < [´e´,´g´,´z´] True

Извлечение последнего элемента из списка:

ghci> tail [5,4,3,2,1]

[4,3,2,1]

Вычисление длины списка:

ghci> length [5,4,3,2,1]

5

Переворот списка:

ghci> reverse [5,4,3,2,1]

[1,2,3,4,5]

Построение списка с заданным шагом:

ghci> [3,6..20]

[3,6,9,12,15,18]

Извлечение нескольких элементов из бесконечного списка:

ghci > take 10 [13,16..]

[13,16,19,22,25,28,31,34,37,40]

Быстрая сортировка

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

quickSort [ ] = [ ]

quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++

quickSort [y | y <- t, y >= h]

Примеры работы:

Сортировка списка целых чисел:

quickSort [3,6,1,1,5,76,2,8,0,8,6,7,21]

[0,1,1,2,3,5,6,6,7,8,8,21,76]

Сортировка списка чисел с плавающей точкой:

quickSort [3.8,3.3,6.0,1.1,1.5,5.0,7,2.5,8.8,0.0,8.1,6.4,7.0,21.8]

[0.0,1.1,1.5,2.5,3.3,3.8,5.0,6.0,6.4,7.0,7.0,8.1,8.8,21.8]

Сортировка симвлолов:

quickSort [´a´,´h´,´b´,´z´,´g´,´j´,´u´]

"abghjuz"

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

На одном из ресурсов в сети интернет рассмотрено 3 способа реализации программы сортировки, в качестве четвертого используется стандартная библиотека сортировки:

http://en.literateprograms.org/Quicksort_(Haskell)

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

Для сравнения скорости работы с сайта была скачана программа, а также в качестве пятого примера добавлена функция, представленная выше. Необходимые правки кода для запуска четвертого примера произведены. Размер списка 1000000. Запуск программы производился с ключами +RTS -sstderr, которые позволяют оценить производительность.

 

Функция	Время работы	allocated in the heap (bytes)
qsort1	3.15	1,674,094,796
qsort2	1.97	1,270,039,088
qsort3	1.48	915,074,544
GHC List.sort	4.96	1,379,894,848
quickSort	2.81	1,630,874,364

 

Также следует отметить, что первый и последний пример оказались самыми ресурсоемкими по параметру "allocated in the heap".

Для сравнения приводится текст аналогичной процедуры на Паскале (Delphy 7.0):

{Алгоритм быстрой сортировки с применением технологии MPI}

Program MpiSort;

Uses Crt,mpi; Const N=100;

Type

List=array[1..n] of integer; {Список (одномерный массив)}

Var

a: List;

k,x,z: integer;

teg, numprocs, myid : longint;

status : MPI_Status;

Function Part(l, r: integer):integer; Var

v, i, j, b: integer;

begin V:=a[r]; I:=l-1; j:=r; repeat

for b:=1 to 2 do case myid of

0: if (b=1) then begin repeat

dec(j)

until (a[j]<=v) or (j=i+1); end else

begin MPI_Recvmailto:@x,1,MPI_DOUBLE,1,teg,MPI_COMM_WORLD,status); i:=x;

end;

1: if (b=2) then begin repeat

inc(i)

until (a[i]>=v) or (i=j-1); z:=i; MPI_Semailto:@z,1,MPI_DOUBLE,0,teg,MPI_COMM_WORLD); end;

end; b:=a[i]; a[i]:=a[j]; a[j]:=b; until i>=j; a[j]:=a[i]; a[i]:= a[r]; a[r]:=b; part:=i;

end;

{Процедура сортировки} procedure QuickSort(l, t: integer); var i: integer;

begin

if l<t then begin i:=part(l, t);

QuickSort(l,i-1); QuickSort(i+1,t); end;

end;

{Ядро программы}

Begin MPI_Init(argc,argv); teg := 0;

MPI_Comm_size(MPI_COMM_WORLD, numprocs); MPI_Comm_rank(MPI_COMM_WORLD, myid);

ClrScr; Randomize;

for k:=1 to N do Begin a[k]:=Random(1000); Write(a[k]:5);

End; QuickSort(1,n); MPI_Finalize; WriteLn;

for k:=1 to N do

Write(a[k]:5);

ReadLn; End.

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

Код для цитирования: Скопировать