Вверх – к монадам, вниз – к регистрам

8 январь, 2008 - 12:43Андрей Зубинский

В конце первой статьи, о лямбда-исчислении, было обещано, что дальше будет страшно. Это «дальше» наступило. Страшно будет.

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

Собирательное, из материалов по Haskell

Одна из самых специфических особенностей функционального программирования (ФП) заключается в том, что традиционные в императивном мире (какой бы язык вы не учили – С, С++, C#, Java, любой клон Pascal, – вы почти никогда не выходили за пределы императивного мира) способы освоения инструментария просто не работают. И это еще мягко сказано. Практически для всего, что принадлежит императивному миру, находятся прекрасные адекватные модели в мире физическом (аналогии типа «стек – стопка тарелок», «очередь – очередь в магазин», «адрес ячейки памяти – адрес квартиры N в доме M на улице K», давно стали классикой), но стоит хоть чуть-чуть прикоснуться к миру чистой математики, как аналогии с реальным миром перестают работать. Например, для понятия «монада» придумано столько просто неудачных и на удивление неточных толкований на основе аналогий, что за их классификацию лучше не браться. Правда, есть высказанная в эпиграфе точка зрения, начинающаяся со слов «к счастью...». К несчастью же, профессиональное функциональное программирование принципиально невозможно без адекватного знания его математических основ.

К слову...

Когда речь заходит о недостатках функционального программирования, сказанное в предыдущем абзаце обычно не упоминается. А зря. Речь идет об исключительно серьезной вещи – о соответствии системы подготовки и регенерации мастеров и ремесленников (объединяемых размытым термином «специалисты») требованиям инструментария, используемого в отрасли. В императивном программировании, например, самоучка может сравнительно легко достичь уровня весьма неплохого ремесленника – именно благодаря близости используемого понятийного аппарата к реальному, физическому миру. Впрочем, в правоте этого очевидного утверждения многие читатели убедились на собственном опыте. В функциональном программировании же от будущего ремесленника потребуется очень специфическая фундаментальная математическая подготовка. И, заметьте, нужна она будет именно для достижения уровня ремесленника – потому что необходимые разделы математики и логики, в которых функциональный программист должен быть, мягко говоря, неплохо подготовлен, трудно отнести к «прикладным». В то же время императивного программиста высокая математическая подготовка обычно переводит из категории ремесленника в класс мастера, потому что обычно (заметьте упор на это слово) императивный программист как математик совершенствуется именно в прикладных областях (достаточно взглянуть на содержание томов великой энциклопедии программистского мастерства – «Искусства программирования» Д. Кнута). С другой стороны, трудно подвергнуть сомнению следующее соображение – хорошая математическая подготовка, требуемая функциональным программированием даже от ремесленника, повышает его уровень математической культуры, чем облегчает переход в класс мастеров. Математическая подготовка, играющая роль высокого барьера требований на «входе в профессию», – вещь весьма специфическая в условиях, когда потребность в программном обеспечении растет как на дрожжах. Конечно, допустимо утверждение, что лучше несколько идеальных программ, чем очень много таких, какие есть сейчас. Но оно совершенно не соответствует реальности – программное обеспечение давно превратилось в самый легкий (масса строго равна нулю) и удивительно функциональный компонент, необходимый для производства чуть ли не всего, и благодаря такой специфике ПО его использование в материальных артефактах будет только возрастать. Соответственно, программистов надо будет больше, и от этого никуда не деться, разве что полностью изменить ход развития цивилизации, вернувшись в пещеры.

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

На грани миров

В предыдущей статье этого короткого цикла мы уже определили функциональное программирование как цепочку из редукции функции, применяемой к результатам редукции функции, которая применяется к результатам... соединяющую некие входные данные с выходом. «Исполняется» вся эта цепочка машиной Черча, которая есть чистая абстракция, и входы-выходы здесь столь же абстрактны, как и сама машина. К сожалению, мы живем в несовершенном физическом мире, и в большинстве программ нас интересует даже не столько формальная их правильность, сколько возможность получения конкретного результата их работы на материальном вычислителе – например, изображение на растровом дисплее (который для машины Черча находится просто в другой Вселенной). Ради получения конкретного результата мы даже готовы пойти на компромисс и мириться с несовершенством используемых программ – в несовершенном мире это далеко не самое страшное. Очевидно, что на стыке миров – абстрактной машины Черча и нашего физического мира – в функциональном программировании должно быть что-то особенное.

Кстати, вопрос о том, каким оно может быть, это особенное, о том, что может находиться на грани между абстрактным и физическим, далеко не нов, над поиском ответа на него трудились лучшие умы человечества. Еще четыреста с лишним лет назад Рене Декарт, размышляя над пограничной областью абстрактного разума и физического тела, предположил, что в этой области находится шишковидная железа – эпифиз, в которой ощущения тела порождают доступные мозгу образы, а целенаправленные мысли мозга инициируют физические действия тела. Сегодня же изучение фундаментальных механизмов ФП «по аналогии» приводит некоторого гражданина N к своему представлению о «шишковидной железе» с одной поправкой – Рене Декарт все-таки был гений, а рядовой гражданин N – просто рядовой гражданин N (и ничего обидного в этом нет).

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

Категории, функторы, монады

Начнем издалека. С теории категорий. В первой части статьи мы говорили о типе функции как о двух множествах – допустимых аргументов («вход», I) и отображаемых значений («выход», U). Давайте подумаем – сколько для каждой пары множеств «вход-выход» может существовать функций определяемого парой типа? Например, говоря императивным языком, – сколько может быть возможных функций типа int f(int) (автор надеется, что этот общеупотребимый С-подобный псевдокод пояснений не требует)? Очевидно – очень много, т. е. некоторое множество. Назовем его F. Очевидно, все элементы этого множества – функции, преобразующие множество целых чисел (Integer) в множество целых чисел (математики говорят – отображающие множество Integer само в себя). Для элементов множества F (т. е. для функций) в некоторых разделах математики используется название морфизмов, а для множеств I и U – объектов. Мы записываем тот факт, что функция f отображает множество I в множество U так: f : I >U, и называем его типом функции f (или морфизма).

Предположим, что в императивном мире у нас есть две функции int f(char) и double g(int), а также лютый изверг менеджер проекта, который за всякое преобразование типов (явное ли, неявное ли) сразу увольняет. Любой императивный программист сразу скажет, что можно в таких условиях сделать с этими функциями – только вызвать g() с параметром, являющимся результатом вызова f(). Потому что тип, возвращаемый f(), совпадает с типом, принимаемым g(). На функциональном языке то же самое описывается как f: C>I и g: I>D, где C, I и D – множества символов, целых чисел и чисел двойной точности с плавающей точкой. Императивный вызов g(f()) мы назовем композицией функций g и f и будем обозначать так: g ° f. А теперь взглянем на композицию функций чуть по-другому, как на новую функцию, о которой мы можем сказать очевидное: g ° f: C>D. Для дальнейшего продвижения нам надо определить одну специфическую функцию, и сделаем мы это в императивном стиле: тип idf(тип x) { return x}. То есть эта функция, примененная к любому элементу множества «вход», возвращает сам этот элемент. Idf() называют функцией эквивалентности (identity function).

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

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

Теперь давайте все то же самое запишем на... функциональном языке программирования Haskell, несмотря на то, что мы ни слова фактически о нем не сказали. Этот пример на самом деле нужен для того, чтобы еще раз продемонстрировать степень сближения абстрактной математики и ФП.

Итак, использованное нами ранее математическое описание функции (или морфизма) f: I > U в Haskell-нотации выглядит практически немодифицированным, разве что «::» в Haskell для удобства принято читать как «имеет тип»: f :: I → U. Мы только что объявили Haskell-функцию с указанием ее типа (естественно, именно эта запись будет правильным Haskell-кодом, если типы I и U определены).

А теперь давайте вспомним следующий псевдокод в императивном стиле тип idf(тип x) { return x}. На Haskell мы можем объявить функцию эквивалентности, которая действительно будет работать со всеми возможными типами, не прибегая к «псевдокодовым» приемам: idf :: forall t. t → t. Эта запись, несмотря на в каком-то смысле прозрачность, демонстрирует сразу несколько фундаментальных понятий. Для начала попробуем прочитать ее «человеческим языком», не прибегая ни к каким догадкам: idf имеет тип для_всех t подозрительная_точка преобразователь объектов t в объекты t. «Для_всех», forall, ключевое слово Haskell, является так называемым квантором общности (вообще-то мы все его учили еще в школьной алгебре при доказательствах теорем, но вот блокировать на клавиатуре символ «A», которым принято его обозначать, непозволительная роскошь). А вот «подозрительная точка» в Haskell – точный эквивалент ранее описанного в определении композиции функций символа «0». То есть если на Haskell мы пишем f.g, это означает на императивном псевдокоде f(g()). Из этого замечания, кстати, сразу напрашивается вывод – типами в Haskell можно оперировать так же, как функциями. На самом деле, раз мы говорим о той части Haskell, в которой «работает» теория категорий, это «открытие» мы уже сделали. Когда указали, что элементами объектов категории может быть что угодно.

Итак, только что двумя объявлениями Haskell мы описали... категорию. Давайте повторим эти объявления и убедимся в этом:

f :: I -> U
g:: U -> V
h:: V -> W
idf :: forall t. t -> t

Морфизмы здесь – функции f, g и h, объекты также указаны явно – I, U, V, W, композиция морфизмов допустима, потому что операция композиции в языке существует («.»), информация о типе морфизмов приводится в объявлениях функций, и наконец, функция эквивалентности тоже определена.

Логика подсказывает, что целью построения абстракций является облегчение операций с ними. Категории не являются исключением. А раз они по сути являются множествами (пусть с множествами дополнений, не важно), напрашивается формализация операции отображения одного множества на другое, т. е. одной категории на другую. Такие отображения, характеризующиеся особым поведением, принято называть функторами. Особенность поведения функторов – сохранение структуры, или дополнительной информации. В частности, функтором может быть такое отображение одной категории на другую (затрагивающее одновременно объекты и морфизмы), которое одновременно сохраняет информацию о типах, не нарушает «работоспособность» функций эквивалентности и использует только законную в этом мире операцию – композицию функций. Да, это звучит непросто. Но ничего не поделаешь.

Давайте подумаем, с помощью чего мы можем создать в функциональном мире простую структуру данных – список? Формально у нас есть только один описанный нами абстрактный механизм – отображение функтором одной категории на другую. Это позволит отобразить и один объект (вы еще не забыли, что это – множество?) на другой (например, множество символов – в множество с одним элементом – списком символов), и то же самое сделать со специфическими функциями. В терминах Haskell полноценные (с математической точки зрения) функторы реализуются посредством классов типов (не следует путать с классами в императивных объектно-ориентированных языках программирования).

На пути к определению той самой «шишковидной железы», которая отделяет абстрактную машину Черча от реального мира, осталось указать одно направление (естественно, каждый фрагмент статьи, посвященный категориям ли, факторам ли, не может претендовать даже на «введение в дисциплину» – это всего лишь определение направлений, по которым вам предстоит двигаться самостоятельно, если вы на это решитесь). Чтобы спуститься поближе к приземленным регистрам и адресам, мы вынуждены подняться на уровень абстракции выше и говорить уже о функциях, оперирующих функторами, о так называемых естественных преобразованиях. Предположим, мы говорим о двух функторах F1 и F2, отображающих одну и ту же категорию C1 в категорию С2. Естественным преобразованием будет множество таких морфизмов (функций) из категории С2, которые всегда отображают объект F1(C1) на объект F2(C1). Доказано, что для каждого объекта категории C1 есть один такой морфизм в категории C2.

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

В статье мы не можем позволить себе рассматривать формальные требования, которым должны подчиняться функтор и преобразования, определяющие монаду, да и такой задачи автор перед собой не ставил. Мы упорно карабкались вверх по уровням абстракций одного из самых современных разделов абстрактной алгебры с двумя целями – выстроить понятийный ряд, по которому нужно двигаться для достижения определенного уровня профессионализма в функциональном программировании и продемонстрировать важнейший его нюанс. А именно, лавинообразное нарастание уровня абстрактности математического аппарата при движении «вниз», к объектам реального мира. Обычно адепты ФП об этом нюансе стараются «забывать», предпочитая оперировать исключительно неоспоримыми достоинствами функционального подхода.

А теперь можно попробовать взглянуть на монаду из императивного мира. Мы не будем множить плохие аналогии и воспользуемся той одной не очень плохой, которая кажется автору статьи удачной хоть в каком-то смысле. Но чтобы подчеркнуть абстрактный (и даже сюрреалистический) характер аналогии, вспомним о... коте Шредингера. Несчастная жертва хорошо хоть что мысленного эксперимента великого физика Шредингера посажена в закрытый ящик с управляемым радиоактивным ядром источником ядовитого газа. Если радиоактивное ядро распадается, ядовитый газ заполняет ящик. И коту, само собой, плохеет. Вероятность того, что радиоактивное ядро распадается за 1 час, равна 50%. Парадокс кота Шредингера утверждает, что пока ящик не открыт наблюдателем, кот в нем жив и мертв одновременно. Как только ящик открывается, что означает – над ядром начинают производиться наблюдения, кот принимает одно из возможных конкретных состояний. Иными словами, открывать ящик с котом Шредингера нельзя – теряется смысл. А совсем иными словами, ящик можно считать... монадой, а нечто типа M cat (в терминах Haskell) – ящиком М с чем-то типа cat внутри. При этом даже если известно, что тип cat (или множество допустимых значений) состоит из всего двух значений – Live и Dead, снаружи ящика определить, какое из значений там сейчас, – принципиально невозможно. Если мы хотим, чтобы в ящике появилась вместо кота собака, т. е. преобразовать cat в dog, мы можем это сделать только одним способом – поместить в ящик функцию типа cat → dog с инструкциями по ее применению к содержимому ящика. Для описания подобных действий монада предлагает специальную функцию (return), которая что-то помещает в ящик, и оператор «связывания» (bind), который применяет указанную программистом функцию к тому, что находится в ящике.

Итак, мы добрались до того уровня непонятности функционального программирования, за который его и любят настоящие фанатики. А теперь самое время определиться – или запасаться учебником по абстрактной алгебре (для начала – прекрасной старой, 1979 года, книгой издательства «Мир» «Элементарное введение в абстрактную алгебру», автор – Э. Фрид, для начала потому, что о том, с чего мы начали (о категориях), в этой книге говорится несколько слов строго на последней 194 странице, но без начал всерьез в теории категорий не продвинуться ни на шаг) и терпением, или... Выбирать вам.