`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

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

Статья опубликована в №49 (617) от 25 декабря

+22
голоса

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

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

Собирательное, из материалов по 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 странице, но без начал всерьез в теории категорий не продвинуться ни на шаг) и терпением, или... Выбирать вам.

+22
голоса

Напечатать Отправить другу

Читайте также

Вот как было сказано говорится пошло - еще страшне.

Но зачем делать страшно?
Зачем усложнять и без того не простой процесс программирования осмыслением каких-то малопонятными монад?

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

Ну начнем аналитически избавляться от страшного.

Девайте посмотрим на язык программирования C надеюсь многие со мной согласятся что язык C вытесним во многих применениях языки PL/1 PL/2 (многочисленные их отклонения включительно с некогда упомянутым Автором статьи PL/M).

Теперь давайте сравним синтаксис PL/* и C. Как видим язык C пошел по пути наибольшего вытеснения неких понятий о монадах. Преобразование типов, выполнялось некогда простым обращением к тем либо инным ячейкам память или резервированием большего объема памать нежели это требовалось. И как видим такой подход оказался оправданым. То есть некие монады (если я правильно понял Автора статьи) ограничивались логикой вещей. А классический Run-time модуль никоим образом не исключал возможности применения рекурсии, со всеми (или по крайней мере со многими) "прелестями" функциональных языков. (это я о языке C).

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

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

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

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

И тут есть такой привкус "...as somebody ate it." из песни того кто также пел "...I make no apologies, for linking my thinking with computer technologies." То есть присутствует некий факт новизны, которая есть повторением чего-то чс чем мы были и так знакомы и уже успели привыкнуть.

Но может это что-то перестало удовлетворять наши потребности может иногда его нада очень интелегентно реформировать?

--DawnON.com

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

Вот история, впомнилась.
Как-то гулял по книжному рынку,
и наткнулся на книжку по Абстрактоной Алгебре,
какраз после того как у вас о оной дисциплине
в обзоре сайтов заметка была (точнее о ее авторе).
И как не странно книжка далеко не свежая.

Потом как-то прошелся по рядам с новой литературой,
и попросил книжек по импульсной технике,
максимум нашел околовсяческие справочники радиолюбителей, и книжку по блокам питания (не совсем то что нужно, или даже совсем не то).
Потому пошел туда где лежала несвежая книжка по абстрактной алгебре,
и поитересовался книгами о импульсной технике. "Да" - говорят - "есть". Например в одной книжке я прочитал что у импульсном режиме радоелектронная лампа имеет больший КПД чем в пропорциональном.
Где-то импульсный преобразователь на електронной лампе достигает
КПД почти 50%!!! (Впечетляет.)

Вот картинки из другой книженки.

electronic tubes cooling

(Радиоелектронные лампы с воздушным и водяным охлаждением соответственно.)

Не кажется ли что и абстрактная алгебра в ее применении к компьютерам так же устарела как и елементная база електроники 50-х годов?
Может что-то надо пересмотреть?

--DawnON.com

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT