Функциональное программирование на Haskell : Часть 1. Введение

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

Алексей Бешенов, технический писатель, независимый специалист

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



18.02.2010

Императивное программирование

Наиболее распространены императивные языки, в которых вычисление сводится к последовательному выполнению инструкций. Решение задачи на императивном языке сводится к описанию того, что необходимо проделать, чтобы получить результат. Классические примеры – FORTRAN (1957), ALGOL (1958) и C (1972).

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

Переменные рассматриваются как изменяющиеся во времени ячейки памяти. Текущие значения переменных в программе образуют изменяющееся состояние.

Пример императивного кода – процедура для вычисления факториала на C:

int fac (int n) {
  int x = 1;

  while (n > 0) {
    x = x*n;
    n = n-1;
  }

  return x;
}

Здесь повторение операции умножения выражено через цикл. В процессе вычисления изменяются значения переменных x и n.

Инициализация:
n := 3;
x := 1;

Первый виток цикла:
x := 1*3 = 3;
n := 3-1 = 2;

Второй виток цикла:
x := 3 * 2 = 6;
n := 2 - 1 = 1;

Третий виток цикла:
x := 6 * 1 = 6;
n := 1 - 1 = 0;

Результат — 6

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


Функции и функциональность

В математическом смысле функция f : X → Y – это правило, сопоставляющее элементу x из множества X (области) элемент y = f x из множества Y (кообласти).

Рисунок 1. Функция f : X → Y
Рисунок 1. Функция f : X → Y

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

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

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

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

fac 0 = 1
fac n = n * fac (n-1)

nформальный аргумент функции fac. В правой части после знака = описано, что функция делает со своим аргументом. Базовые функции для умножения и вычитания записаны через инфиксные (указываемые между аргументами) операторы * и -.

Здесь уравнений два. При вычислении функции уравнения просматриваются по порядку. Если n = 0, то будет использовано первое уравнение. Если n ≠ 0, то оно не подойдет, и задействуется второе.

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

Далее мы будем уделять основное внимание синтаксису и семантике языка Haskell.

Запись в математикеЗапись в Haskell
f(x)f x
f(x,y)f x y
f(g(x))f (g x)
f(g(x),h(y))f (g x) (h y)
f(x) + g(x)f x + g x
f (x+y)f (x+y)
f(-x)f (-x)

Таблица 1. Запись применения функции в математике и в Haskell

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

Используется рекурсия, т. е. fac определяется через саму себя. Такое определение работает, потому что fac выражается через более простой случай и, в конечном счете (если n ≥ 0), доходит до базового случая n = 0. Вычисление fac 3 по такому определению можно произвести так (на каждом шаге подчеркнуты упрощаемые выражения):

fac 3 → 3 * fac 2
      → 3 * (2 * fac 1)
      → 3 * (2 * (1 * fac 0))
      → 3 * (2 * (1 * 1))
      → 3 * (2 * 1)
      → 3 * 2
      → 6

Здесь мы применили f к значению 3. При этом 3 называется фактическим аргументом.

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

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

Обратите внимание, что для n < 0 наше определение будет вычисляться бесконечно, поэтому наша функция является частичной (если ее областью считать все целые числа).

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

При k ≥ 0 мы имеем выражение, где в знаменателе стоит только что определенный факториал числа k, а в числителе – убывающая факториальная степень (falling factorial power)

Запишем для нее рекурсивное определение:

ffp r 0 = 1
ffp r k = (r-k+1) * ffp r (k-1)

В первом уравнении r не используется, поэтому можно использовать заменитель _ и писать ffp _ 0 = 1.

Можно убедиться, что

(проверьте это). Поэтому уравнения факториала можно заменить на

fac n = ffp n n

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

Рисунок 2. Черный ящик, вычисляющий убывающую факториальную степень
Рисунок 2. Черный ящик, вычисляющий убывающую факториальную степень

Возьмем еще один черный ящик (/) с двумя входами x и y и выходом, равным частному x/y:

будет вычислять такая схема:

Рисунок 3. Схема из черных ящиков, вычисляющая биномиальный коэффициент
Рисунок 3. Схема из черных ящиков, вычисляющая биномиальный коэффициент

Она соответствует выражению

ffp r k / fac k

Определим искомую функцию:

binc r k | k >= 0    = ffp r k / fac k
         | otherwise = 0

Такая запись называется уравнением с условиями (сравните с математической записью определения). После | и до знака = стоят условия. «otherwise» означает «иначе». Подробно это будет рассмотрено в последующих статьях.

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

Пример вычисления binc 6 2:

binc 6 2 → ffp 6 2 / fac 2
         → (5 * ffp 6 1) / fac 2
         → (5 * (6 * ffp r 0)) / fac 2
         → (5 * (6 * 1)) / fac 2
         → (5 * 6) / fac 2
         → 30 / fac 2
         → 30 / ffp 2 2
         → 30 / (1 * ffp 2 1)
         → 30 / (1 * (2 * ffp r 0))
         → 30 / (1 * (2 * 1))
         → 30 / (1 * 2)
         → 30 / 2
         → 15

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

Это приводит к важному понятию чистоты.


Чистота

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

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

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

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

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

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

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

Язык без побочных эффектов называется чисто функциональным.

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

Примеры чисто функциональных языков: Miranda, Haskell и Clean.

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


Ленивость и нестрогость

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

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

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

Например, наша функция binc всегда будет требовать значение k, но значение r требуется, только если k ≥ 0.

В соответствии с этим, говорят о языках со строгой семантикой и языках с нестрогой семантикой. («Нестрогость» и «ленивость» – не одинаковые, но близкие понятия.)

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

В нестрогом языке вычисление производится по необходимости. Если f нестрогая, то вычисление f e может завершиться, даже если вычисление e не завершается.

Например,

[fac 1, fac 0, fac (-1)]

обозначает список из трех элементов. Вычисление fac (-1) зацикливается. Значит, вычисление списка также зациклится.

Пусть теперь функция length возвращает длину списка. Выражение

length [fac 1, fac 0, fac (-1)]

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

Примеры нестрогих языков: Miranda и Haskell. Строгие языки – ML и Scheme.

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

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


Краткая история

Функциональное программирование черпает идеи из комбинáторной логики и лямбда-исчисления.

Одними из первых языков с функциональным стилем были LISP (1958), APL (1964), ISWIM (1966) и FP (1977).

К концу 1980-х годов уже имелось много функциональных языков. Среди тех, которые оказали значительное влияние на Haskell:

  • ML (1973) – первый язык с типизацией Хиндли–Милнера.
  • SASL, KRC, Miranda (1972–1985) – одни из первых ленивых языков.
  • Hope(1980) – один из первых языков с алгебраическими типами данных. Haskell разрабатывался многочисленной группой исследователей с 1987 г. Он назван в честь Хаскелла Карри.
Рисунок 4. Происхождение Haskell
Рисунок 4. Происхождение Haskell

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

Нововведения Haskell – монады и классы типов. Другие сильные стороны, заимствованные из других языков – каррирование, алгебраические типы данных, сопоставление с образцом. (Здесь мы просто приводим набор ключевых слов; все эти понятия скоро будут разъяснены.)

Последнее зафиксированное описание – Haskell 98, однако язык постоянно развивается и усложняется; сейчас планируется выход Haskell'.

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

  • Компиляторы и другие средства разработки.
  • Распределенная система управления версиями Darcs.
  • Оконный менеджер xmonad.
  • Сервер Web-приложений HAppS.
  • Интерпретатор/компилятор Pugs для языка Perl 6.
  • Операционная система House.
  • Язык описания аппаратных средств Lava.
  • Система обработки натурального языка LOLITA.
  • Системы доказательства теорем Equinox / Paradox и Agda.

Основные источники информации по Haskell

У Haskell имеется широкое и дружелюбное сообщество.

Основной источник информации – сервер haskell.org.

На нем имеются списки рассылки, в том числе:

  • haskell-cafe@haskell.org – свободное обсуждение.
  • beginners@haskell.org – более простые темы для новичков.

    Есть очень оживленный IRC-канал #haskell на irc.freenode.net. В нем можно быстро получить любезный ответ практически на любой вопрос.

    Множество тематических блогов собирается на http://planet.haskell.org/

  • Хорошим введением в Haskell может быть руководство A Gentle Introduction to Haskell 98.
  • Документацию по обширным библиотекам смотрите по адресу http://haskell.org/ghc/docs/latest/html/libraries/
  • Формальный отчет – The Haskell 98 Report.

Редактирование и выполнение кода

Реализации Haskell

Формально, Haskell не имеет какой-то одной «стандартной» реализации.

Для интерактивной работы подойдет легковесный интерпретатор Hugs.

Также есть интересный проект Yhc, компилирующий исходные тексты в байткод, и Helium – учебный вариант Haskell, дружественный к новичкам (например, выдающий более ясные сообщения об ошибках). Однако они еще находятся в процессе разработки.

Де-факто стандартным стал компилятор/интерпретатор GHC. Он является наиболее продвинутым, во всём соответствует стандарту и предлагает ряд экспериментальных расширений. Мы сконцентрируемся на нем.

GHC можно загрузить по адресу http://haskell.org/ghc/. Если вы используете GNU/Linux, то посмотрите готовые сборки в своем дистрибутиве. Для MacOS X и Windows можно также найти бинарные файлы. (Учтите, что сборка GHC прямо из исходников может быть довольно утомительным занятием.)

Нас в первую очередь будет интересовать интерактивная программа ghci, в которой удобно испытывать учебные примеры.

Итак, после установки GHC вы можете запустить в терминале ghci:

$ ghci
ghci, version 6.10.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude>

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

Символ > означает, что ghci ожидает пользовательский ввод. Это могут быть выражения Haskell, а также команды для интерпретатора.

Клавишами ← и → можно перемещать курсор по командной строке ghci. ↑ и ↓ пролистывают историю команд назад и вперед.

Вместо Prelude> или других имен модулей мы дальше будем писать ghci> (если хотите сделать так же, выполните в ghci команду :set prompt "ghci> ").

Для начала ghci можно использовать как продвинутый калькулятор:

ghci> 1*2 + 2*3 + 3*5
23
ghci> 23^23
20880467999847912034355032910567
ghci> gcd 3020199 1161615
232323

Операторы совпадают с принятыми в других языках (таблица 2).

13.4 + 9.6Сложение
5.75 * 4.0Умножение
36.4 - 13.4Вычитание
287.5 / 12.5Деление
1.873^5Возведение в целую степень
1.456**8.35Возведение в вещественную степень

Таблица 2. Арифметические операторы из Prelude

Для них используется инфиксная запись и соответствующий приоритет. Например, 2*3+4 соответствует (2*3)+4, а 2^3^4 – 2^(3^4). Чтобы изменить принятый приоритет, можно расставить скобки.

В ghci имеется специальная переменная it, равная значению последнего успешно вычисленного выражения.

ghci> 15 - 2
13
ghci> it + 10
23

Редактирование исходного кода

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

Другие средства разработки описаны на странице http://haskell.org/haskellwiki/Libraries_and_tools/Program_development

Для кода Haskell используется расширение файлов .hs.

Если вы запишете код на Haskell в файл foo.hs, то определения загружаются в ghci командой :load foo. Параллельно файл можно редактировать и при необходимости перезагружать определения при помощи :reload.

Текущая директория изменяется командой :cd (например, :cd /home/bob).

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

$ ghci
ghci, version 6.10.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load fph01.lhs
[1 of 1] Compiling Main             ( fph01.lhs, interpreted )
Ok, modules loaded: Main.
*Main> ffp 6 6
720
*Main> fac 6
720
*Main> binc 6 2
15.0
*Main> binc 6.5 4
23.4609375

Эти и другие команды можно сокращать – вместо :load использовать :l, вместо :reload – :r и так далее.

Список команд интерпретатора выводит :help. Для выхода из ghci нужно набрать :quit.

В ходе нашего изложения часто будут встречаться простые примеры, состоящие из одного-двух уравнений. Их можно сразу вводить в ghci при помощи let:

ghci> let double x = 2*x
ghci> double 23
46

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

ghci> let { fac 0 = 1; fac n = n * fac (n-1) }
ghci> fac 23
25852016738884976640000

Заключение

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

Прилагаемые файлы:fph01.lhs

Ресурсы

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


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

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


  • Bluemix

    Узнайте больше информации о платформе IBM Bluemix, создавайте приложения, используя готовые решения!

  • developerWorks Premium

    Эксклюзивные инструменты для построения вашего приложения. Узнать больше.

  • Библиотека документов

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=468751
ArticleTitle=Функциональное программирование на Haskell : Часть 1. Введение
publish-date=02182010