среда, 2 декабря 2009 г.

Следствия чистоты языка

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

Другим мотивом послужило повышение внимания к теме Хаскеля со стороны некоторых программистов [lisp-univ-etc]. Есть ряд заблуждений и мифов относительно языка. Поэтому хотелось бы некоторые вещи прояснить для самого себя.

Итак, начало следует.

1. Чистота языка и ленивость.

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

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

2. Чистота монад.

Монады строятся на основе чистых функций, и потому они чисты. Несколько особняком стоят монады IO и ST, которые используют внутренности компилятора. Монада ST опирается на квантор всеобщности при своем запуске, который и гарантирует чистоту. Монада же IO по большому счету должна запускаться всего один раз самой исполняемой средой и на самом верхнем уровне, используя значение main. Этот запуск осуществляется всего один раз, и именно он привносит побочный эффект. Но запуск происходит как бы уже “за пределами” языка, и все формально остается чистым.

3. Монады как вычисления.

Монады можно воспринимать как вычисления, обычно отложенные. Когда нам нужно выразить побочный эффект мы не возвращаем конкретное вычисленное значение x, которое кстати может разниться от запуска к запуску. Вместо этого мы возвращаем само вычисление, которое уже позволяет получить x при некоторых начальных условиях. Такое вычисление можно обернуть в монаду m. Тогда само вычисление обозначим как m x.

Для получения результата вычисления существуют многочисленные функции, чьи названия начинаются со слова run: runST, runState, runWriter и т.д.

Другой способ запуска вычисления – это передача самого вычисления другому вычислению. Тогда первое вычисление становится частью второго. Здесь используются функции lift и liftIO. Это приводит нас к понятию монады-трансформера. Большинство монад, за исключением IO, имеют свои дубликаты – трансформеры, которые сами являются вычислениями и дополнительно могут быть контейнерами для других вычислений (монад). Монада IO является крайней, и у нее не может быть трансформера.

Кроме этого, вычисления могут непосредственно содержать вычисленные данные. Например, монады List и Identity так и делают. Поэтому дополнительный запуск вычисления им не нужен.

4. Программа как вычисление.

Программа на Хаскеле заключена в значении main, которое имеет тип IO (). То есть, это - некоторое вычисление в монаде IO, которое возвращает значение типа (). Причем само значение main является чистым. Для его получения не могут быть использованы никакие побочные эффекты, даже если то вычисление, которое задает main, их производит. Ведь мы не вычисляем, а возвращаем лишь вычисление!

Это принципиально отличается от большинства языков. На C++ функция main() выполняет последовательно программу. В Хаскеле main возвращает отложенное вычисление, которое еще надо запустить. Такой запуск осуществляется извне самой исполняющей средой Хаскеля. Просто другой взгляд на вещи.

5. Выражение побочного эффекта через чистые функции.

Мы не можем в чистом языке вызвать функцию, производящую побочный эффект. Но как показывает пример main, мы можем вернуть отложенное вычисление, которое уже при своем запуске произведет заданный побочный эффект. Это – ключевая идея.

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

Вопрос в том, насколько полным является базис, т.е. в данном случае набор примитивов, возвращающих значения в монаде IO. Поскольку в Хаскеле есть FFI, то мы можем считать такой базис достаточно полным.

6. Почему ленивость?

Чистый язык не обязан быть ленивым. Он вполне мог бы быть энергичным. Но тут возникает проблема.

Итак, main возвращает отложенное вычисление в монаде IO. Но будь язык энергичным, мы должны были бы полностью сконструировать в памяти все вычисление. И сделать это сразу после запуска до начала реального выполнения программы. Это было бы неэффективно как с точки зрения скорости исполнения, так и с позиции потребления памяти.

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

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

7. Монады как связующее звено.

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

Во-первых, такая операция может быть представлена в чистом языке только как отложенное вычисление m x. Предположим, что есть следующая операция m y. Для создания последовательности из этих вычислений естественным будет формирование некоторой функции от двух аргументов, где первым аргументом будет первое вычисление, а вторым – последующее:

                f :: m x -> m y -> ?

Чтобы сохранить оба вычисления мы должны вернуть новое. Тогда можем вернуть либо m x, либо m y. Выберем второе. Так мы получили функцию “then”:

                (>>): m x -> m y -> m y

В общем случае второе вычисление может зависеть от результата первого вычисления. Приходим к функции “bind”:

                (>>=): m x -> (x -> m y) -> my

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

Иногда нам нужно вычисление, которое только и делает, что просто вычисляет заданное фиксированное значение x. Для этого вводится функция “return”:

                return: x -> m x

Так мы пришли к более полному определению типо-класса монад.

8. Ленивость монад.

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

Например, монада IO опирается на этот порядок и производит операции ввода-вывода строго последовательно. Но так поступают не все монады. Например, монада Maybe может просто проигнорировать оставшуюся часть вычислений, а монада Backwards State, вообще, распространяет состояние в порядке обратном следованию! Такое возможно только в ленивом языке.

Итог.

Получается, что чистота, ленивость и монады взаимосвязаны. Последние два являются следствием чистоты. Но это не значит, что ленивость и монады характерны только для Хаскеля. Частично они присутствует и в других языках. Например, монады есть в F#. Это – совершенно другой язык смешанного типа с энергичной стратегией вычислений. Но наиболее красиво и целостно это все выглядит именно в Хаскеле.