ДУШКИН Роман Викторович
[email protected] http://roman-dushkin.narod.ru/
ФП 02005-04 01 Себастиан Сильван (Sebastian Sylvan)
Взам. инв. № Инв. № дубл.
Подп. и дата
СИЛЬНЫЕ СТОРОНЫ ЯЗЫКА HASKELL
Инв. № подл.
Подп. и дата
[email protected]
2006
Копирова
Формат
АННОТАЦИЯ Языки программирования, такие как C/C++/Java/Python, называются императивными языками программирования потому, что они задают последовательность действий. Программист последовательно указывает компьютеру, как выполнить задание, шаг за шагом. Функциональные языки программирования работают иначе. Вместо выполнения действий последовательно, они вычисляют выражения.
парадигма
программирования,
Haskell,
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Ключевые слова: функциональная преимущества языка Haskell
ФП 02005-04 01 ИзмЛист № докум. Разраб. Душкин Р. Пров. Н. контр. Утв.
Подп. Дата
Лит. Функциональное программирование Копирова
Лист Листов 2 21
Формат
ФП 02005-04 01
СОДЕРЖАНИЕ 1. ЧТО ТАКОЕ ФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ ПРОГРАММИРОВАНИЯ? .......................5 1.1. Уровень абстракции ..........................................................................................................5 1.2. Использование функциональных языков программирования ......................................6 1.3. Функции и побочные эффекты в функциональных языках ..........................................6 1.4. Заключение.........................................................................................................................8 2. ЧТО МОЖЕТ ЯЗЫК HASKELL ПРЕДЛОЖИТЬ ПРОГРАММИСТУ? .............................9 2.1. Чистота................................................................................................................................9 2.2. Отложенные (ленивые) вычисления ................................................................................9 2.3. Строгая типизация .............................................................................................................9 2.4. Ясность .............................................................................................................................11 2.5. Язык Haskell и ошибки....................................................................................................14 2.6. Язык Haskell против ООП...............................................................................................15 2.7. Модульность ....................................................................................................................17 3. ЭПИЛОГ ..................................................................................................................................19
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
2.8. Быстродействие языка Haskell .......................................................................................17
Лист
ФП 02005-04 01 ИзмЛист № докум.
3
Подп. Дата Копирова
Формат
ФП 02005-04 01
СПИСОК СОКРАЩЕНИЙ — абстрактный тип данных
ООП
— объектно-ориентированное программирование
ЭВМ
— электронно-вычислительная машина
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
АТД
Лист
ФП 02005-04 01 ИзмЛист № докум.
4
Подп. Дата Копирова
Формат
ФП 02005-04 01
1. ЧТО ТАКОЕ ФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ ПРОГРАММИРОВАНИЯ? 1.1. Уровень абстракции Существуют две фундаментальные области в программировании ЭВМ — управление ресурсами и упорядочение планирования вычислительного процесса. Управление ресурсами (выделение регистров и памяти) было предметом значительного отвлечения, большинство новых языков (императивных, а также функциональных) снабжается инструментом сборки мусора для того, чтобы убрать управление ресурсами из задачи и позволить программисту сосредоточить своё внимание на алгоритме, а не на бухгалтерской задаче выделения памяти.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Упорядочение планирования вычислительного процесса тоже подверглось некоторой абстракции, хотя и не в такой степени. Императивные языки избавляются от этого путём введения новых ключевых слов и стандартных библиотек. Большинство императивных языков имеют, например, специальные синтаксические структуры для построения цикла, вам больше не надо брать организацию цикла на себя. Но императивные языки основаны на идеи последовательного программирования — они никогда не смогут полностью её избежать. Единственным путём повышения уровня абстракции в области последовательного программирования в императивных языках, является введение дополнительных ключевых слов или стандартных функций, хотя они и загромождают язык (смотрите Python и Java). Эти близкие отношения между императивными языками и задачами упорядочивания планирования команд означают, что императивные языки никогда не смогут не использовать последовательность вычислений (если смогут, то они больше не будут императивными языками!), а значит, по существу они никогда не достигнут такого же уровня абстракции, которого могут достигнуть языки функционального программирования. В языке Haskell упорядочения планирования вычислительного процесса нет. вы только заботитесь о том, что должна вычислить программа, а не о том, как и когда это вычислено. Это делает язык Haskell более гибким и удобным в использовании языком. Язык Haskell является частью решения проблемы, а не частью самой проблемы.
Лист
ФП 02005-04 01 ИзмЛист № докум.
5
Подп. Дата Копирова
Формат
ФП 02005-04 01
1.2. Использование функциональных языков программирования вы, скорее всего, уже использовали язык функционального программирования, даже не зная об этом! Язык выражений в Microsoft Excel функциональный. вы не пишите никаких последовательностей, вы просто говорите программе, что содержимое ячейки является результатом комбинирования других ячеек каким-либо образом («= A1 + A2» например). Так что всё это время вы программировали на языке функционального программирования, и вероятно даже не считали это программированием — вот почему функциональное программирование более наглядно. Вещи ведут себя так, как вы ожидаете. Функциональное программирование кажется странным, только если вы привыкли использовать императивную модель программирования. Непрограммистам функциональные языки предоставляют меньший семантический интервал между программистом и языком.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
1.3. Функции и побочные эффекты в функциональных языках Функции играют важную роль в функциональных языках программирования. Функции считаются значениями, точно так же как Int или String. Функция может возвратить другую функцию, она может принять функцию как параметр и даже может быть сконструирована с помощью компоновки других функций. Таким образом, можно достичь лучшей «склейки» модулей для получения программы. Например, функция, которая вычисляет некоторое выражение, может участвовать в вычислении как аргумент, становясь более модульной. Также можно сконструировать функцию с помощью другой функции. Например, можно определить функцию «дифференцирования», которая будет численно дифференцировать заданную функцию. Таким образом, если у нас есть функция f, тогда можно определить f’ = дифференцировать f, и использовать её как обычно в математическом контексте. Такой тип функций называет функциями высокого порядка, и как описал их Джон Хьюз: «Мощное название, для мощных функций». Вот короткий пример на языке Haskell функции numOf, которая подсчитывает количество элементов в списке, удовлетворяющих некоторому свойству: numOf p xs = length (filter p xs)
Лист
ФП 02005-04 01 ИзмЛист № докум.
6
Подп. Дата Копирова
Формат
ФП 02005-04 01
Мы обсудим синтаксис языка Haskell позже, а в этой строке говорится о том, что можно «получить результат, отфильтровав список xs с помощью предиката p и вычислить длину результата». Теперь p у нас функция, которая берёт элемент и возвращает True или False, в зависимости от того, проходит элемент тест или нет. Таким образом, numOf — функция высокого порядка, и некоторые выполняемые функции передаются в неё как аргумент. Необходимо заметить, что filter — также функция более высокого порядка, использующая функцию тестирования как аргумент. Давайте более подробно рассмотрим эту функцию и определим из неё несколько более специализированных функций. numOfEven xs = numOf even xs
Здесь мы определяем функцию numOfEven, которая высчитывает количество одинаковых элементов в списке. Обратите внимание, что нам не нужно явно определять xs как параметр. Мы можем просто написать numOfEven = numOf even. Весьма чёткое определение. Теперь давайте определим функцию, которая вычисляет количество элементов, большее или равное 5:
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
numOfGE5 xs = numOf (>=5) xs
Здесь тестовая функция «>= 5», которая передаётся в numOf для обеспечения нужной функциональности. Теперь должно быть понятно, как модульность функционального программирования даёт нам возможность определять общие функции, где часть функциональности передаётся в качестве аргумента, что в свою очередь позволяет создавать любые специализированные функции. Приведённый пример довольно тривиален. Нетрудно переписать определения для всех функций, приведённых выше; для более сложных функций это может оказаться сложной задачей. Можно, например, написать лишь одну функцию для прохода по автоматически балансирующемуся бинарному дереву (так называемому красно-чёрному дереву), имея часть функциональности как параметр (например, функцию сравнения). Это позволит совершить обход всего дерева, лишь подставляя нужную функцию. Таким образом, можно сосредоточить свои усилия на том, чтобы убедиться, что главная функция верна, тогда и специализированные функции будут верны. Не говоря уже о том, что вам не придется копировать код во всём проекте. Эта идея может быть использована и в императивных языках. Например, в языке Java часто бывает нужен объект-компаратор для деревьев и других стандартных структур данных. Различие состоит в том, что язык Haskell предлагает более интуитивно понятный и элегантный способ (создание отдельного типа для сравнения двух типов, и последующая
Лист
ФП 02005-04 01 ИзмЛист № докум.
7
Подп. Дата Копирова
Формат
ФП 02005-04 01
передача объекта этого типа — едва ли элегантный способ), который применятся довольно часто (и не только в стандартных библиотеках). Основная идея функциональных языков — это то, что результат выполнения функции определяется исключительно входными данными. Никаких побочных эффектов! Это также применимо и к переменным — переменные в языке Haskell не изменяются (это наверняка не совпадает с вашим прошлым опытом, например в математике).
Убрав побочные эффекты из выражений, мы можем вычислять выражения в любой последовательности (правда, не все функциональные языки это используют). Функция всегда будет выдавать один и тот же результат при одинаковых входных параметрах. Такое определение ликвидирует целый класс ошибок в императивных программах. Вообще-то, можно сказать, что источником большинства ошибок в больших системах можно считать побочные эффекты. Источником, если не прямым, то из-за некорректного проектирования, ставшим возможным только благодаря применению побочных эффектов. Функциональные программы в большинстве случаев имеют меньше ошибок!
1.4. Заключение Из-за того, что функциональные языки программирования интуитивно более понятны и дают большее количество простых способов решения задачи, программы на таких зыках короче (от 2 до 10 раз). Семантика в большинстве случаев гораздо ближе к проблеме, чем в императивных языках, а значит можно легче определить, правильна функция или нет. Кроме того, язык Haskell не позволяет использовать побочные эффекты, что ведёт к уменьшению ошибок. Таким образом, программы на языке Haskell легче писать, они более стабильны и легче в обслуживании.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Возможно, это может быть трудно для понимания программистами, использующими императивные языки (где большинство программ почти полностью состоит из присваиваний значений переменным). Но когда вы постигнете функциональную парадигму программирования, вы увидите преимущества. Итак когда вы начинаете думать: «Как-то это слишком странно, вернусь-ка я обратно к С++», — заставьте себя продолжать изучать язык Haskell, потом вы будете рады, что сделали это.
Лист
ФП 02005-04 01 ИзмЛист № докум.
8
Подп. Дата Копирова
Формат
ФП 02005-04 01
2. ЧТО МОЖЕТ ЯЗЫК HASKELL ПРЕДЛОЖИТЬ ПРОГРАММИСТУ? Язык Haskell это современный язык общего назначения, который был разработан для того, чтобы объединить в себе коллективные знания сообщества приверженцев функционального программирования в целях создания одного элегантного, мощного и общедоступного языка.
2.1. Чистота В отличие от некоторых других языков функционального программирования язык Haskell является чистым. Он не допускает никаких побочных эффектов. Это, несомненно, самая важная особенность языка Haskell. Мы уже коротко обсудили преимущества чистого, без побочных явлений, языка программирования — нам больше нечего сказать по этому поводу. вам нужно самим попробовать.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
2.2. Отложенные (ленивые) вычисления Ещё одной особенностью языка Haskell является то, что он является языком с отложенными вычислениями. Это означает, что ничего не будет вычислено, пока не должно будет быть вычислено. Например, можно определить в бесконечной рекурсии бесконечный список чисел. Только те элементы списка, которые на самом деле будут использованы, будут вычислены. Это дает возможность для решения многих проблем использовать очень элегантные методы. Типичным образцом решения проблемы могло бы быть задание списка всех возможных методов решения с последующим отсеиванием неправильных. Оставшийся список впоследствии будет содержать только допустимые решения. Отложенные вычисления делают эту операцию очень прозрачной. Если вам нужно одно решение, то вы можете просто извлечь первый элемент из получившегося списка — механизм ленивых вычислений удостоверится, что ничего ненужного не посчитано.
2.3. Строгая типизация Более того, язык Haskell строго типизированный язык, что значит только то, что значит. Невозможно неосторожно привести Double к Int или вызвать метод по пустому указателю. Это ведёт к меньшему количеству ошибок. В некоторых случаях может быть нужно явно приводить Int к Double тогда, когда вам это нужно перед выполнением какой-то
Лист
ФП 02005-04 01 ИзмЛист № докум.
9
Подп. Дата Копирова
Формат
ФП 02005-04 01
операции, но на практике такое случается нет так часто, чтобы вызвать неудобства. В действительности, принудительное явное приведение часто помогает выделить проблемную часть кода. В других языках там, где это приведение выполняется неявно, проблемы часто возникают когда компилятор обращается с Double как с Int или с Int как с указателем. В отличие от других языков, типы в языке Haskell определяются автоматически. Это означает, что вам очень редко придется объявлять типы ваших функций, кроме тех случаев, которые оговорены документацией кода. Язык Haskell посмотрит на то, как вы используете переменные, и сделает вывод о том, какой должен быть тип у переменных — после этого будет проведена проверка типов для того, чтобы убедиться, что нет несовпадения типов.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Так что вы получаете преимущества строгой типизации (ошибки отлавливаются во время компиляции чаще, чем во время выполнения) без преград, сопутствующих другим языкам. Кроме того, язык Haskell будет делать вывод для большинства общепринятых типов переменных. Так что если вы пишите, например, функцию сортировки без описания типа, язык Haskell удостоверится, что она будет работать для всех значений, которые могут быть отсортированы. Сравним с тем, как бы вы делали это в языке Java. Для достижения полиморфизма, вам пришлось бы использовать базовые классы, а после этого объявить ваши переменные как экземпляры подкласса этого базового класса. Всё это означает «тонны» дополнительной работы и абсурдные запутанные объявления, только для того, чтобы показать существование переменной. К тому же для явного приведения типов придётся произвести множество преобразований типов — явно не самое элегантное решение. Если вы хотите написать полиморфную функцию на языке Java, вы, скорее всего, объявите параметры, как объекты типа Object, что по существу позволяет программисту посылать что угодно функции, даже объекты, которые логически не могут пройти в функцию. Результатом является то, что большинство функций, которые вы пишите на языке Java, не являются общими, они только работают с одним типом данных. Также вы перемещаете проверку ошибок из проверки во время компиляции во время исполнения. В больших системах, в которых некоторые функциональные возможности редко используются, эти ошибки могут быть не отловлены до тех пор, пока они не станут причиной фатального краха системы в самое неподходящее время. Язык Haskell предоставляет элегантный, лаконичный и безопасный путь для написания ваших программ. Программа не приведёт к фатальной ошибке неожиданно, и больше не будет дампов.
Лист
ФП 02005-04 01 ИзмЛист № докум.
10
Подп. Дата Копирова
Формат
ФП 02005-04 01
2.4. Ясность Ещё одна особенность языка Haskell, которая очень важна для программиста, хотя и не значащая ничего в показателях стабильности и быстродействия, это ясность языка Haskell. Проще говоря: программа работает так, как вы ожидаете. Для иллюстрации ясности языка Haskell давайте взглянем на небольшой пример. Мы отдали предпочтение функции QuickSort, так как это простой алгоритм, который в действительности является полезным. Мы взглянем на две версии — одну написанную на языке C++, императивном языке, и одну на языке Haskell.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Обе версии используют только базовые возможности доступные программисту без импортирования каких-либо дополнительных модулей (в противном случае мы могли бы вызвать функцию sort из стандартных библиотек каждого языка и покончить с этим!). Соответственно, мы используем стандартный список примитивов каждого языка (list в языке Haskell и array в языке C++). Обе версии должны обладать возможностью реконфигурации (что делается автоматически в языке Haskell и с помощью шаблонов в языке С++). Обе версии должны использовать один и тот же рекурсивный алгоритм. Вам следует заметить, что это не замышлялось как точное сравнение между двумя языками. Здесь намеревалось показать ясность языка Haskell, а версия на языке С++ была просто включена для сравнения (и скорее всего была бы закодирована по-другому, если бы использовалась библиотека STL). template
void qsort (T *result, T *list, int n) { if (n == 0) return; T* smallerList; T* largerList; smallerList largerList T pivot int numSmaller int numLarger
= = = = =
new T[n]; new T[n]; list[0]; 0; 0;
for (int i = 1; i < n; i++) if (list[i] < pivot) smallerList[numSmaller++] = list[i]; else largerList[numLarger++] = list[i]; qsort (smallerList, smallerList, numSmaller); qsort (largerList, largerList, numLarger);
Лист
ФП 02005-04 01 ИзмЛист № докум.
11
Подп. Дата Копирова
Формат
ФП 02005-04 01
int pos = 0; for (int i = 0; i < numSmaller; i++) result[pos++] = smallerList[i]; result[pos++] = pivot; for (int i = 0; i < numLarger; i++) result[pos++] = largerList[i]; delete [] smallerList; delete [] largerList; return; }
Я не буду объяснять этот код дальше, просто заметьте, как он сложен и запутан на первый взгляд. Сейчас давайте посмотрим на версию функции QuickSort в языке Haskell, которая может быть приблизительно такой же.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
qsort [] qsort (x:xs)
= =
[] qsort less ++ [x] ++ qsort more where less = filter (<x) xs more = filter (>=x) xs
Давайте подробно проанализируем этот код, тем более что в нём используется достаточно много синтаксиса языка Haskell, который вы можете не знать. Функция называется qsort и принимает список параметров. Мы описываем функцию в языке Haskell вот так: funcname a b c = expr, где funcname — имя функции, a, b и c — параметры, а expr — выражение которое должно быть вычислено (чаще всего используя параметры). Функции объявляются простым написанием имени функции вначале и параметрами после. Язык Haskell не использует параметры для применения функций. Функции имеют более высокий приоритет, чем всё остальное, так что «f 5 * 2», например, применит f к 5 а потом умножит на 2, а если вы хотите чтобы умножение происходило раньше функционального применения, то вам следует использовать круглые скобки вот таким образом «f (5 * 2)». Давайте-ка вернемся к функции QuickSort. Сперва мы видим, что у нас два определения функции. Это называется сопоставление образов, и мы можем кратко сказать, что оно будет тестировать прохождение аргументов в функцию сверху вниз и использовать первое определение, которое подойдёт.
Лист
ФП 02005-04 01 ИзмЛист № докум.
12
Подп. Дата Копирова
Формат
ФП 02005-04 01
Первое определение сопоставляется с [], что в языке Haskell обозначает пустой список (список из 1, 2 и 3 — [1, 2, 3], поэтому разумно использовать две скобки как пустой список). Таким образом, когда мы пробуем отсортировать пустой список, мы получаем пустой список, довольно разумно, не правда ли? Образец второго определения сопоставляется со списком, содержащим хотя бы один элемент. Это происходит, когда (x:xs) используется как аргумент: таким образом, L : [1, 2, 3] возвращает [1, 1, 2, 3], просто добавляя элемент в начало списка. Таким образом, образ, сопоставляющийся с (x:xs), сопоставляется со списком с головой x и хвостом xs (который может являться или не являться пустым списком). Другими словами, (x:xs) — это список, содержащий хотя бы один элемент.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Так как мы будем использовать голову списка в дальнейшем, мы можем весьма элегантно извлечь её, используя сопоставление образов. Можно считать его именованием содержания списка. Это можно проделать с любой структурой данных, не только со списком. Можно сопоставить образ с именем произвольной переменной, и затем использовать функцию головы для нахождения головы списка. Теперь, если у нас есть непустой список, отсортированный список получается сортировкой всех элементов, меньших x, затем мы сортируем все элементы больше x и ставим их в конец. Мы делаем это с помощью оператора конкатенации списков ++. Обратите внимание, что x не является списком, и ++ не будет работать над ним, поэтому мы создаём список из одного элемента. Таким образом, функция может быть описана так: «Чтобы отсортировать список, расположите голову списка между отсортированными списками всех элементов больших головы и всех элементов меньших головы». Это можно прекрасно сделать обычным алгоритмом. Это весьма свойственно языку Haskell. Описание функции обычно весьма и весьма похоже на неформальное описание функции. Поэтому можно сказать, что у языка Haskell меньше семантических «дыр», чем у других языков. Но подождите, мы ещё не закончили! Как вычисляется список? Вспомните, что нам не важна последовательность в языке Haskell, и поэтому, мы определили их как функцию, использующую нотацию where (которая позволяет любому определению использовать параметр функции, к которой оно принадлежит). Мы используем стандартную функцию filter, не будем заострять внимание на этом, но строка less = filer (< x) xs будет использовать фильтр (< x) xs для «просеивания» списка xs. Вы можете видеть, что мы передаём функцию, которая будут использована для фильтрации списка для фильтра, что является примером функции высокого порядка. Функция (< x) должна читаться так: «функция меньшая x» и она будет возвращать True если переданный в неё элемент меньше x (обратите внимание, как просто было
Лист
ФП 02005-04 01 ИзмЛист № докум.
13
Подп. Дата Копирова
Формат
ФП 02005-04 01
создать функцию «на лету»: мы ставим «< x» и «меньше чем х» в скобки и передаём в функцию — функции просто другой способ отображения значений). Все элементы, которые проходят тест, становятся выходными из функции фильтра. Похожим образом, функция (>= x) используется для фильтрации списка всех элементов, больших или равных x. Теперь, после того как был объяснён синтаксис, перечитайте определения функций. Заметьте, как мало времени требуется для понимания того, что функция делает. Определения функции в языке Haskell объясняет что вычисляется, а не как вычисляется. Если вы уже забыли синтаксис, не волнуйтесь! Мы рассмотрим его в учебном пособии более конкретно. Самая главная идея, которую нужно вынести из этого примера — это то, что код Haskell элегантен и интуитивно понятен.
2.5. Язык Haskell и ошибки Мы уже несколько раз констатировали то, что многие особенности языка Haskell помогают бороться с распространением ошибок. Давайте перечислим их.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Программы на языке Haskell содержат меньше ошибок, потому что язык Haskell: 1) Чистый. Нет побочных эффектов. 2) Строго типизированный. Не может быть неоднозначного использования типов. И нет дампов! 3) Лаконичный. Программы короче, что позволяет просто взглянуть на функцию и «уяснить всё сразу», чтобы убедиться в том, что функция правильная. 4) Высокоуровневый. Программы на языке Haskell чаще всего читаются так, как описание алгоритма. Это позволяет проще проводить проверку того, что функция делает то, что утверждает алгоритм. Так как кодирование происходит на более высоком уровне абстракции, оставляя детали компилятору, то существует меньше мест, куда может закрасться ошибка. 5) Управляет памятью. Не надо заботиться о «повисших» ссылках — сборщик мусора позаботится о них. Программист может беспокоиться о выполнении алгоритма, а не о подсчёте памяти. 6) Модульный. Язык Haskell предоставляет более сильный механизм составления вашей программы из уже разработанных модулей. Таким образом, программы могут быть более модульными. Часто использование модульных функций может быть соответственно проверенно на корректность по индукции. Комбинирование двух функций, для которых доказана корректность, также даст правильный результат (при условии, что комбинация корректна).
Лист
ФП 02005-04 01 ИзмЛист № докум.
14
Подп. Дата Копирова
Формат
ФП 02005-04 01
Кроме того, большинство людей сходятся во взглядах, что вы просто думаете подругому, решая проблему на функциональном языке. Вы подразделяете задачу на всё меньшие и меньшие задачи, а после этого вы пишите эти маленькие (и «почти всегда гарантированно правильные») задачи, которые объединяются разными способами для достижения конечного результата. Там просто нет места для ошибок!
2.6. Язык Haskell против ООП Важнейшее преимущество объектно-ориентированных языков программирования — это возможность группировать данные с помощью функций, которые действуют на них вместе, в объект — это даёт отличную инкапсуляцию данных (разделение интерфейса и реализации) и полиморфизм (позволяется набору типов данных вести себя одинаково). Но: Инкапсуляция и полиморфизм есть не только в ООП!
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
В языке Haskell есть инструментарий для абстракции данных. К сожалению, к нему нельзя перейти, не объяснив модульной системы и того, как работают в языке Haskell абстрактные типы данных, что далеко выходит за рамки этой статьи. Далее приведено короткое объяснение того, как АТД и полиморфизм работают в Haskell. Инкапсуляция данных производится в языке Haskell определением каждого типа данных в отдельном модуле, из этого модуля вы только экспортируете интерфейс. Внутри может содержаться набор функций, которые могут взаимодействовать с данными, но интерфейс — это единственное что видно снаружи модуля. Заметьте, что типы данных и функции, которые действуют на тип данных, не сгруппированы в «объект», но они (обычно) собраны в одном модуле, и таким образом можно выбрать лишь экспортировать определённые функции (но не конструкторы для типов данных), делая эти функции единственным способом манипулирования типами данных — «спрятать» реализацию от интерфейса. Полиморфизм создаётся использованием типов классов. Теперь, если вы программировали на языке С++ или языке Java, вы можете проассоциировать классы на нечто, похожее на шаблон объекта, но в языке Haskell это не так. Тип классов в языке Haskell следует понимать в прямом смысле. Это набор правил для определения того, входит ли тип в класс. Таким образом, язык Haskell разделяет экземпляры классов и создание типов данных. Вы можете определить тип «Порше» как отдельный экземпляр типа «Машина». Все функции, применённые к другим членам класса типа «Машина», могут быть применены к «Порше» с тем же успехом.
Лист
ФП 02005-04 01 ИзмЛист № докум.
15
Подп. Дата Копирова
Формат
ФП 02005-04 01
Тип, который включается в язык Haskell — это экземпляр класса Show, для которого тип может быть проиллюстрирован с помощью функции show, которая переводит тип данных в строку. Следовательно, почти все типы в языке Haskell можно вывести на экран, применяя show к ним для перевода их в строку, а затем используя требуемую IO функцию (более подробно в учебниках). Заметьте, как это похоже на определение объекта в ООП, когда затрагивается полиморфизм.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Система языка Haskell более интуитивно понятна для оперирования с полиморфизмом. Вам не надо волноваться о правильной иерархической структуре наследования, или вообще думать о том, есть ли иерархия. Класс — просто класс, а типы — экземпляры этого класса, и соблюдение иерархических отношений родитель-наследник не обязательны. Если тип данных удовлетворяет требованиям класса, тогда он может быть экземпляром этого класса. Просто, не правда ли? Помните пример функции QuickSort? Помните, что говорилось о полиморфизме? Секрет полиморфизма в функции qsort, состоит в том, что он определён так, что может работать на любом типе данных из класса Ord. Класс Ord имеет определённый набор функций, среди них «<» и «>=», которые необходимы для нас, т.к. мы всего лишь желаем узнать больше ли x заданный элемент или нет. И если бы нам нужно было определить Ord-функции для нашего типа «Порше» (необходимо применить, скажем, «<=» или «==», далее язык Haskell сам всё определит) как случай типа Ord, мы могли бы использовать отсортированные списки «Порше» при помощи функции qsort (правда сортировка элементов типа «Порше» может не иметь смысла). Заметьте, что мы никогда не говорим каким классам элементы списка должны принадлежать — язык Haskell определит это автоматически, просто посмотрев какие функции мы используем (в функции qsort важны только «<» и «>=»). Таким образом, можно сделать вывод: в язык Haskell входят механизмы для инкапсуляции данных, равные или превосходящие по своим возможностям механизмы ООП. Единственное, чего нет в языке Haskell — это способа группировки функций в объект (кроме создания типа данных, который включает функцию: помните функция — это данные!). Это представляется незначительным недостатком. Для того чтобы применить функцию к объекту, напишите «func obj a b c» вместо чего-то вроде «obj.func a b c».
Лист
ФП 02005-04 01 ИзмЛист № докум.
16
Подп. Дата Копирова
Формат
ФП 02005-04 01
2.7. Модульность Центральной идеей в компьютерной науке является модульность. Вот общедоступная аналогия: например, вы хотели сделать деревянный стул. Если вы сделали его части отдельно, а потом склеили их, то задача решается просто. Но если бы вам пришлось вырезать весь стул из цельного куска дерева, то это оказалось бы действительно немного труднее. Джону Хьюз пришлось рассказать об этом в теме его статьи «Сильные стороны функционального программирования»: Языки, которые стремятся повысить производительность, должны хорошо поддерживать модульное программирование. Но новых правил обзора и механизмов раздельной компиляции недостаточно — модульность означает больше, чем просто модули. Наша возможность разбивать задачу на части непосредственно зависит от нашей возможности собирать решения вместе. Для того чтобы способствовать модульному программированию, язык должен предоставлять хороший связующий элемент. Языки функционального программирования предоставляют два новых вида связующих элементов — функции высокого порядка и отложенные вычисления.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
2.8. Быстродействие языка Haskell Позвольте мне для начала ясно заявить, что все нижеупомянутое относится только к общим случаям, в которых скорость не является важной. Там, где можно принести в жертву некоторое увеличение времени выполнения для гораздо большего уменьшения времени разработки. Существуют обстоятельства, когда скорость имеет значение, поэтому нижеследующий раздел не будет касаться их в той же степени. В настоящее время некоторые программисты на языке C++ могут утверждать, что вышеупомянутая версия функции QuickSort на языке C++ вероятно немного быстрее, чем версия на языке Haskell. И это, скорее всего, окажется правдой. Как общее правило язык C++ должен быть быстрее, чем язык Haskell, так что нет смысла что-нибудь ещё заявлять. Впрочем, для подавляющего большинства приложений разница в скорости будет незначительной. А сейчас я вас спрашиваю: «Как много программ вы можете вспомнить, которые затрачивают значительное количество времени на сортировку списков?» Немного. Некоторые алгоритмы сжатия делают это, вот и все. Едва ли не все программы, которыми сейчас пользуются, обладают примерно одинаковой продолжительностью обработки своих функций. Самыми примечательными исключениями являются такие приложения, как кодировщик MPEG и искусственные эталонные тесты, которые тратят большую часть своего времени выполнения внутри небольшой части кода.
Лист
ФП 02005-04 01 ИзмЛист № докум.
17
Подп. Дата Копирова
Формат
ФП 02005-04 01
Если вам на самом деле необходимо быстродействие во что бы то ни стало, то рассмотрите язык C вместо языка Haskell. В программировании на компьютере существует старое правило, которое называется «правило 80/20». Оно утверждает, что 80% времени тратится на 20% кода. Это, скорее всего, так для любого маленького приложения, и, может быть, и для нескольких больших тоже. Но с увеличением приложений, они обычно попадают в часть-80; они обычно не «выполняют одни и те же действия чаще», а «выполняют больше действий». Так что для больших программ часть-80 становится больше, а часть-20 становится меньше.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Лучшим правилом было бы: «30% времени тратиться на 1% кода, а оставшиеся 70% времени тратятся на оставшиеся 99% процентов кода.» Но не звучит ли это очень остроумно, а? Приложения стремятся увеличить свою функциональность, тем самым, расширяя продолжительность обработки по большему числу функций. Следствием этого, является то, что любая заданная функция в вашей системе не будет иметь важности, когда речь зайдет и оптимизации скорости выполнения. Возможно, есть всего несколько функций, достаточно важных для того, чтобы их оптимизировать. Эти важные функции могут быть написаны на языке C. Язык C может, и скорее всего это случится, захватить власть ассемблера в программировании — вы будете использовать его в действительно критичных ко времени частях вашей системы, но не во всей системе полностью. Давайте продолжим подниматься на более высокие уровни абстракции, точно так же, как мы делали это прежде. Время программиста почти всегда стоит дороже процессорного времени. Мы больше не пишем приложения на ассемблере — по той же причине нам больше не следует писать приложения на языке С. В конце концов, помните, что оптимизация алгоритма даёт гораздо больший результат, чем оптимизация кода. Там, где такие факторы как время разработки и стабильность не играют никакой роли, можно быть уверенным, что язык C лучше языка Haskell. Но в реальном мире время разработки очень много значит. Если вы можете написать приложение на языке Haskell в десять раз быстрее чем на языке С (от себя и из опыта других людей могу вас уверить, что это не так уж и удивительно), то у вас появляется куча времени, которое вы можете потратить на оптимизацию алгоритма. Так что в реальном мире, когда у нас нет неограниченного количества времени на написание ваших программ, программы на языке Haskell могут очень часто быть быстрее программ на языке C.
Лист
ФП 02005-04 01 ИзмЛист № докум.
18
Подп. Дата Копирова
Формат
ФП 02005-04 01
3. ЭПИЛОГ Так если язык Haskell так хорош, почему он не стал «массовым» языком? Ну, одной из причин является то, что, скорее всего, операционная система написана на языке C или на каком-нибудь другом императивном языке, так что, если ваше приложение преимущественно взаимодействует с операционной системой, то вам будет проще использовать императивные языки. Другая причина малого распространения языка Haskell и других функциональных языков — это то, что в основном языки программирования редко считаются инструментами (хотя и являются ими). Для большинства людей их любимый язык программирования сродни религии — они даже представить себе не могут, что какой-то другой язык может выполнить задачу лучше и быстрее. Есть такая статья Пола Грэма «Разрушение стереотипов», в которой описан его опыт использования языка Lisp (ещё одного функционального языка программирования) в новой компании. В ней он использует аналогию, которую он назвал «Парадокс Blub».
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
В ней говорится примерно следующее: Если любимым языком у программиста является язык Blub, который находится гдето посередине «спектра мощности», то он может сравнить его только с языками, которые находятся в нижней части спектра. Он может взглянуть на язык COBOL и сказать: «Как кто-нибудь что-нибудь может делать на этом языке — у него же нет функции X. — X присутствует в языке Blub.» Тем не менее, для программиста будет непростой задачей просмотреть другую часть спектра. Если он начнет изучать языки, которые находятся в верхней части спектра, то они покажутся ему «непонятными», так как программист на языке Blub думает «на языке Blub» и, скорее всего, не видит полезности разнообразных функциональных возможностей более мощного языка программирования. Само собой разумеется, что это по индуктивности наводит на мысль о том, что, чтобы иметь возможность сравнивать все языки, надо поместить себя на верхушку спектра мощности. Моё мнение, что функциональные языки, по определению, ближе к вершине спектра мощности, чем императивные. Одной из причин того почему «массы» не используют язык Haskell, является то, что люди считают, что их язык делает «всё, в чем они нуждаются». И конечно он делает, потому что они думают «на языке Blub». Языки программирования — не технология — это образ мышления. И если вы не думаете на языке Haskell, вам будет трудно увидеть полезность языка Haskell — даже если язык Haskell предоставит вам возможность писать приложения лучше за короткий промежуток времени.
Лист
ФП 02005-04 01 ИзмЛист № докум.
19
Подп. Дата Копирова
Формат
ФП 02005-04 01
Будем надеяться, что эта статья помогла вам сломать в себе парадокс Blub. Даже если вы еще не способны «думать на языке Haskell», я надеюсь, что вы, по крайней мере, осведомлены об ограниченности ваших рамок мышления, продиктованных вашим текущим «любимым» языком программирования, и что у вас теперь есть стимул для их расширения путём изучения чего-нибудь нового.
Инв. № подл.
Подп. и дата
Взам. инв. № Инв. № дубл.
Подп. и дата
Если вы предались изучению функционального языка программирования (для достижения лучшего взгляда на спектр мощности), то я убежден, что язык Haskell — это ваш лучший выбор.
Лист
ФП 02005-04 01 ИзмЛист № докум.
20
Подп. Дата Копирова
Формат
Лист регистрации изменений Номера листов (страниц) Изм. изменённых
заменённых
новых
аннулированных
Всего листов (страниц) в докум.
№ документа
Входящий № сопроводительного докум. и дата
Подп.
Дата
