Краткость и простота

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

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

Лекция №18

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

· краткость и простота;

· строгая типизация;

· модульность;

· функции — это значения;

· чистота (отсутствие побочных эффектов);

· отложенные (ленивые) вычисления.

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

}

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

quickSort ([]) = []

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

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

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

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

Пример 3. Быстрая сортировка Хоара на языке Haskell.

quickSort [] = []

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

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

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

Ещё одним полезным свойством позволяющим сократить программу является встроенный механизм сопоставления с образцом. Это позволяет описывать функции как индуктивные определения. Например:

Пример 4. Определение N-ого числа Фибоначчи.

fibb (0) = 1

fibb (1) = 1

fibb (N) = fibb (N – 2) + fibb (N – 1)

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